Exact Densest 𝒫-Partite Subgraph Solver

(Proceedings of the VLDB Endowment, Vol. 17, No. 4 ISSN 2150-8097. doi:10.14778/3636218.3636226)

Given a typed graph and a meta-path 𝒫 = (A₁,…,A_k), it returns the family 𝒱 = (V₁,…,V_k), V_j ⊆ V(A_j), maximizing

        rho(V) = |F(V)| / (|V_1| * ... * |V_k|)^(1/k)

where F(𝒱) is the set of 𝒫-instances induced by 𝒱. The reported final_rho is that maximum, computed exactly.

---

What is in the paper and what is in this code

Optimisations present here and not described in the paper due to limited space, i.e., applications of lemmas 7 and 9, and some trivial upper-bound-based prunings:

• Extra M-space prunings. Several independent upper bounds are computed per key and per box, and the cheapest sufficient one wins: a support-prefix bound, a coordinate-coupled box bound, a corner-cover test over accumulated linear constraints, a box-size feasibility test that can also tighten a box's upper corner in place, and an adjacent-edge support bound. A key or a whole box is dropped as soon as any of them certifies it cannot improve the incumbent.
• Constraint accumulation and reuse. Certificates discovered while rejecting one key are retained as linear constraints in log-M space and reused to reject later keys without any flow call. Log-cube certificates (ℓ∞ balls in log-M space) do the same for a neighbourhood of keys at once.
• Warm-started flow. The factorized flow network is rebuilt incrementally between neighbouring keys, with a retract-and-climb ladder, rather than solved from scratch. There is a cost model that chooses between the compact and full oracle per call.
• A τ-grid cache. Threshold counts are bucketed on a coarse multiplicative grid so that repeated bound evaluations hit a cache instead of recounting.
• Heuristics that affect order, not correctness. Box priority, key scoring, a peel-based warm start for the incumbent, and an adaptive warmup phase before the box search begins. These decide what is examined first. A different choice would change the runtime and the counters this program prints, and would not change final_rho.

---

Layout

Single translation unit: src/main.cpp includes the headers, so the split is an organisational one with no effect on code generation or speed.

File	Contents
src/common.hpp	includes, numeric tolerances, flow and solver counters, RSS probe
src/types.hpp	value types: keys, witnesses, constraints, log-cubes, and their helpers
src/flow.hpp	max-flow engines: Dinic and push-relabel
src/graph.hpp	the typed graph, instance counting, and both input loaders
src/flow_templates.hpp	reusable network skeletons (full and factorized)
src/solver.hpp	DPSolver: the box-M search, its bounds, prunings and oracles
src/main.cpp	command-line parsing only

DPSolver is still a large class. The split above separates the parts with clean boundaries (flow engines, graph and loading, value types, network skeletons); the search, its bounds and its pruning share enough mutable state that separating them further was not attempted here, because the value of this code is that it computes the reference optimum and a refactor that changed the answer would be worse than a monolith that does not.

---

Build

make                 # g++ -O3 -std=c++17 -o main_opt src/main.cpp
make native          # adds -march=native (faster, not portable)
make debug           # -O0 -g with ASan and UBSan

C++17 and a 64-bit Unix environment. Single-threaded, no external dependencies.

Input

Mode A, typed edge list (recommended). One edge per line:

u_id  u_type  v_id  v_type

Whitespace or commas separate fields, # begins a comment, trailing columns are ignored. A vertex's identity is the (id, type) pair, so the same numeric id under two types does not collide. Duplicate edges are removed. The loader aborts loudly if a meta-path type is absent from the data or if the meta-path repeats a type.

Mode B, legacy directory. --root DIR containing path.txt (meta-path as type ids), node_types.txt (vertex_id type_id), and edges.txt (u_id v_id).

Usage

./main_opt --typed-edges graph.txt --meta-path "user,movie,genre" \
           --box-leaf-threshold 4096 --box-size-tighten --cube-budget 0

Quote the meta-path. That flag set is the tuned default.

Flag	Meaning
--typed-edges FILE	typed edge-list input
--meta-path "a,b,c"	meta-path as comma-separated type names
--root DIR	legacy directory input
--box-leaf-threshold N	enumerate a box directly once it holds ≤ N keys
--box-size-tighten	tighten box bounds before recursing
--cube-budget 0	recommended default
--ball-verify	re-solve a sample of skipped keys exactly, as a cross-check (slower)
--verbose	per-key and per-leaf progress on stderr

k = 2, 3, 4 are supported directly and k ≥ 5 is handled.