{"id":"9a0eca38-db68-44fd-9323-47339fea8dd9","arxiv_id":"2508.18616","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"BD-Index answers (α,β)-dense subgraph queries in a bipartite graph in O(|D|) optimal time using O(|E|) space, with two dynamic maintenance strategies costing O(p·|E|^1.5) and O(p·|E|) per update.","lead":"This paper introduces BD-Index, an index that answers (α,β)-dense subgraph queries in bipartite graphs in time proportional to the size of the answer while using memory linear in the graph size. It also provides two update strategies for edge insertions and deletions, trading update speed against memory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Time-efficient maintenance hinges on an unproven path-reversal invariant; a single failure silently corrupts BD-Index, so the O(p|E|) update claim is not established.","rationale":"The reader's weakest assumption correctly identifies the single most load-bearing concern: the path-reversal invariant underlying the time-efficient maintenance algorithms. The static parts of the paper (optimal query time, linear space, index construction) are better supported: Theorem 4 is straightforward, the space bound is plausible though its proof has a weakly justified inequality, and the experiments show memory close to 8|E| bytes. The dynamic maintenance is where correctness is essential and least secure. A failure of the invariant does not merely degrade performance; it makes the index answer wrong queries silently, because OrientationToRank trusts the maintained orientation. The proof as written is not a proof: it cites the wrong theorem (Theorem 2 is the hierarchical property, not a reachability-rank lemma), asserts a monotonicity step that Lemma 2 does not imply, and omits the explicit verification of Definition 4 after reversal. This is not a disagreement with the consensus but an internal gap: either the invariant is true and needs a careful proof, or it is false and the central contribution of the paper fails. The proposed differential stress test is a concrete, feasible check because the authors provide code, and it would settle whether a counterexample exists. The reader's verdict is CONDITIONAL, and my read does not change that; the paper should not be fully accepted until the path-reversal correctness is established. Other issues, such as the claim that p is a small constant despite Table 2 showing p up to 371, affect efficiency claims but not the core correctness of the index, so they are secondary to this concern.","tokens_in":39590,"tokens_out":9415,"duration_ms":84349,"concrete_test":"Randomized differential stress test: on small bipartite graphs (e.g., 20 U-nodes, 20 V-nodes, 100 edges), run 10,000 random edge insertions and deletions using BD-Insert-T and BD-Delete-T. After every update, verify (1) the maintained orientation satisfies both conditions of Definition 4, and (2) the ranks output by OrientationToRank match ranks obtained by an independent brute-force implementation of Definition 1, for all relevant (alpha, beta) pairs. Report the first update where either check fails. If none fail, the invariant is empirically supported; if any fail, Theorems 11 and 13 are false and the O(p|E|) maintenance claim collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The O(p|E|) update-time claims of BD-Insert-T and BD-Delete-T depend entirely on the invariant that one path reversal restores the egalitarian orientation after each edge insertion (Algorithm 6, lines 5-6) or deletion (Algorithm 7, lines 7-11). The proof of this invariant is not rigorous. In Theorem 11, reachability from vmin to v1 is used to infer r_alpha(vmin) >= r_alpha(v1), which is plausible, but the next step claims that 'since d_vmin <= d_v1, we also have r_alpha(vmin) <= r_alpha(v1)'. This does not follow from Lemma 2, whose property (1) only guarantees d_v is in {r_alpha(v), r_alpha(v)+1}; two nodes with equal indegree can have ranks differing by 1. The proof also never explicitly checks intermediate U nodes on the reversed path or verifies condition (2) of Definition 4 after the reversal. If the invariant fails for some update sequence, OrientationToRank (Algorithm 5) will compute incorrect alpha-ranks, and BD-Index will silently return wrong D_{alpha,beta} answers. The same gap appears in Theorem 13 for deletions. Since the correctness of the entire dynamic index rests on this step, the O(p|E|) maintenance claim is not yet established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes BD-Index, a linear-space index for (α,β)-dense subgraph queries in bipartite graphs. It introduces α-rank and β-rank, organizes nodes into sorted lists, and claims to answer any query in optimal output-sensitive time O(|D_{α,β}|) using Θ(|E|) space. The paper also gives a construction algorithm based on the authors' prior DSS++/Divide algorithms, plus two dynamic maintenance strategies: a space-efficient one with O(p·|E|^{1.5}) update time and a time-efficient one with O(p·|E|) update time based on a newly defined 'egalitarian orientation'. Experiments on 10 large real-world graphs report large query speedups and scalable index construction. The static query and space claims are largely coherent, but the dynamic maintenance part has significant gaps in the proofs of the update theorems and of the path-reversal invariant, and the maintenance algorithms do not handle changes in the parameter p.","tokens_in":39867,"tokens_out":28815,"duration_ms":289297,"significance":"If the static results hold, BD-Index is a practically significant contribution: it achieves output-optimal query time with linear space, and the reported 3–4 orders of magnitude speedup over the online DSS++ baseline on 10 datasets is impressive. The paper also ships a source-code link and a full version, which is commendable for reproducibility. The dynamic maintenance claims are the main potential differentiator, but their correctness is not yet established; the O(p|E|) update-time result rests on an unproven path-reversal invariant and on update theorems whose proofs are informal. The static index itself is a useful repackaging of the hierarchical structure from prior work, and the experimental study is extensive.","major_comments":[{"comment":"The proof that a single path reversal restores the egalitarian orientation is incomplete. Theorem 11 compares only vmin and v1 and then asserts that reversing the path leaves the orientation 'still egalitarian'; it does not verify condition (2) of Definition 4 for all pairs of V-nodes, including pairs whose reachability is newly created by the reversed edges, and it does not explicitly analyze the indegree changes of intermediate U-nodes and V-nodes on the path. Theorem 13 has the same structure for the deletion cases. Because the correctness of BD-Insert-T and BD-Delete-T, and hence the entire O(p·|E|) update-time claim, rests on this invariant, a complete proof must be supplied or the claim should be treated as unproven.","section":"§5.2, Theorems 11 and 13; Algorithms 6 and 7"},{"comment":"The maintenance algorithms fix p as the loop bound and never update it. The value p is defined as the largest integer with D_{p,p} non-empty, and Theorems 6–7 allow ranks to change by ±1 after an edge update. The paper gives no argument that p is invariant under a single edge insertion or deletion; a single insertion can in principle make D_{p+1,p+1} non-empty, and a deletion can empty D_{p,p}. In either case BD-Index (Definition 3) and the set of egalitarian orientations (Section 5.2) require an additional or fewer layer, but no mechanism for adding or removing layers is described. The maintenance algorithms therefore do not correctly maintain the index for graphs whose p changes.","section":"§4.2 and §5.2, Algorithms 3, 4, 6, 7"},{"comment":"No initialization procedure for the egalitarian orientations is given. Section 5.2 begins 'Given all egalitarian orientations ⃗E', but Algorithm 2 (Build-BD-Index) constructs only ranks and node lists via DSS++/Divide-a/Divide-b, and Algorithm 5 (OrientationToRank) converts an orientation into ranks, not the reverse. Without a method to construct the initial 2p+2 egalitarian orientations from the static graph, the time-efficient maintenance strategy cannot be bootstrapped on any existing dataset; the experiments in Section 6.2 must therefore be relying on an unstated initialization step.","section":"§5.2 and §5.1"},{"comment":"The update theorems underlying BD-Insert-S and BD-Delete-S are not proved at the level of detail required. The proofs invoke the egalitarian orientation (Definition 4) and Lemma 2 before those are introduced, and they rely on statements such as 'it is easy to verify that the updated ⃗E still satisfies the condition in Definition 1' for all β' outside a single value. Adding a directed edge can create new S-to-T paths in the orientation, so the claim that only one β layer changes needs an explicit and careful argument. Since BD-Insert-S and BD-Delete-S call DSS++ on the basis of exactly this claim, the correctness of the space-efficient maintenance strategy is not fully established.","section":"§4.1, Theorems 6 and 7"}],"minor_comments":[{"comment":"The text says 'BD-Insert-S and BD-Insert-D', but the deletion algorithm is named BD-Delete-S; please correct the name.","section":"§4.2, first paragraph"},{"comment":"There are several typos: 'maintence' (Section 1), 'dirctly' (Section 5), and 'acorss' (Section 6, Exp-4). Please proofread.","section":"Throughout"},{"comment":"The statement 'if a node x can reach node y, then r_α(x) ≥ r_α(y)' is used in Theorem 11 but is not stated as a lemma; it follows from Definition 1 and the definition of rank, but it should be stated and proved explicitly rather than attributed to Theorem 2.","section":"§5.1, Theorem 10 proof"},{"comment":"The step 'Lemma 1 implies that the nodes in D^V_{α,r_max} have degrees greater than r_max, which leads to |D^U_{α,r_max}| > r_max' is terse; it is true only because every neighbor of a V-node in D_{α,β} is also in D_{α,β}, but this closure property should be stated explicitly.","section":"§3.3, Theorem 5 proof"},{"comment":"The asymmetry between I^U_BD (nodes with r_α ≥ α) and I^V_BD (nodes with r_β > β) is confusing at first reading; a sentence explaining that the asymmetry mirrors the query split α ≤ β versus α > β would help.","section":"§3.1, Definition 3"}],"recommendation":"major_revision","confidential_remarks":"The static index contribution is sound in outline and the experimental study is extensive, but the dynamic maintenance part—which is one of the paper's headline contributions—currently rests on informal proofs and an unaddressed p-update mechanism. I would not reject outright if the authors can supply the missing path-reversal proof and an initialization/adjustment procedure for p. The heavy reliance on the authors' own prior paper [50] for Theorems 1 and 2 is legitimate, but the new definitions and theorems introduced here need to stand on their own."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The static core of this paper is good and worth engaging with. The BD-Index idea—organizing nodes into ranked lists so a query is just a scan of the result set—is simple and effective, and the Θ(|E|) space proof is the genuinely new part. The query correctness and the space bound hold together, and the experiments showing 3–4 orders of magnitude speedup over the online DSS++ baseline on 100M-edge graphs are credible in direction, even if the figure rendering in the arXiv text is unusable. Rank-ordered lists were already used for (α,β)-cores, so the index concept is not brand new, but applying it to the flow-based dense model with a linear-space proof is a real contribution.\n\nThe soft spots are real but concentrated. The dynamic maintenance section is where I would push back. The space-efficient BD-Insert-S and BD-Delete-S are fine: they invoke DSS++ per α and the O(p·|E|^1.5) bound follows directly. The time-efficient BD-Insert-T and BD-Delete-T, however, rest on the claim that one path reversal restores the egalitarian orientation after each update. The stress-test note is right: the proof in Theorem 11 does not justify the step from indegree comparisons to rank comparisons. Lemma 2 only gives indegree ∈ {rank, rank+1}, so equal indegrees do not force equal ranks. The proof also never checks intermediate U nodes on the reversed path or verifies condition (2) of Definition 4 after reversal. Theorem 13 has the same gap for deletions. Since a single failure would silently corrupt the index via OrientationToRank, the O(p|E|) update claim is not established as written. This is fixable—the invariant may well be true—but it needs a rigorous proof, not a sketch.\n\nTwo smaller issues. The paper leans on the authors' prior work [50] for the model's core theorems (hierarchical property, dense-inside/sparse-outside), which is legitimate but means the index's correctness is only as solid as that paper. Also, the abstract and Section 3.4 call p a small constant, but Table 2 shows p up to 371 on HE and 156 on WI, which undermines that claim without invalidating the results.\n\nBottom line: the static index and the space-efficient maintenance are solid work. The time-efficient maintenance needs a rigorous proof of the path-reversal invariant. This deserves a serious referee and likely a conditional accept after revision.","headline":"A solid index-and-maintenance paper for (α,β)-dense subgraph queries whose static side is convincing and whose dynamic side has a real proof gap that needs fixing before the O(p|E|) update claim can be trusted.","tokens_in":40408,"tokens_out":644,"would_cite":true,"duration_ms":8779,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An index that answers (α,β)-dense subgraph queries in time proportional to the result set, using only linear space, and updates in near-linear time.","keywords":["bipartite graphs","dense subgraph","(α,β)-dense subgraph","index structure","dynamic graph maintenance","egalitarian orientation","α-rank","query processing"],"falsifier":"Run the insertion or deletion algorithm on a small bipartite graph and after each update check Definition 4 directly: every U-node's indegree equals $\\min(\\alpha, \\deg(u))$ and no V-to-V path has indegree gap at least two. Any update sequence where the single path reversal leaves a violated orientation, or where Query-BD-Index disagrees with a brute-force recomputation of $D_{\\alpha,\\beta}$ on the updated graph, disproves the update claim.","tokens_in":1757,"feed_emoji":"⚡","tokens_out":1691,"duration_ms":60166,"temperature":0.7,"pith_summary":"The paper's central claim is that all (α,β)-dense subgraph queries on a bipartite graph can be answered in time proportional to the size of the answer only, not the whole graph, using an index that takes memory proportional to the number of edges. It introduces BD-Index, built on two node orderings called α-rank and β-rank, which exploit the fact that denser subgraphs nest inside sparser ones. The paper further claims that the index can be kept up to date under single-edge insertions and deletions in O(p·|E|^1.5) time with linear space, or in O(p·|E|) time when extra orientation structures are stored. If these claims hold, dense-subgraph queries that previously required seconds, about 21.5 seconds on a 112-million-edge graph, would take milliseconds on the same graph.","feed_headline":"One index answers dense-subgraph queries in milliseconds","feed_subtitle":"New bipartite index returns (α,β)-dense subgraphs in time proportional to result size, with memory about equal to the graph.","key_machinery":"The central objects are α-rank and β-rank: for a fixed α, $r_\\alpha(x)$ is the largest β such that node x lies in $D_{\\alpha,\\beta}$. The load-bearing identity is $D_{\\alpha,\\beta} = \\{x \\mid r_\\alpha(x) \\ge \\beta\\} = \\{x \\mid r_\\beta(x) \\ge \\alpha\\}$, which follows from the hierarchical nesting property of dense subgraphs. The index stores nodes in lists sorted by these ranks, with pointers marking the first node at each threshold, so a query is one pointer lookup plus a suffix traversal. For updates, the machinery is the egalitarian orientation: an orientation in which every U-node has indegree $\\min(\\alpha, \\deg(u))$ and no path between V-nodes connects indegrees differing by two or more. From such an orientation, the algorithm OrientationToRank recovers all ranks in $O(|E|)$ time by iterated reachability searches, and the update algorithms restore the orientation by reversing a single path.","core_discovery":"On its own terms, the paper establishes that for a bipartite graph $G=(U,V,E)$, every non-empty dense subgraph $D_{\\alpha,\\beta}$ is exactly the suffix of a node list sorted by the rank $r_\\alpha(x)$, the largest $k$ with $x \\in D_{\\alpha,k}$, and symmetrically for $r_\\beta$. Because the family $\\{D_{\\alpha,\\beta}\\}$ is nested, the whole family can be stored as $2(p+1)$ sorted node lists plus pointers, occupying $\\Theta(|E|)$ space, and a query only scans the suffix of one list, giving $O(|D_{\\alpha,\\beta}|)$ time. The paper also claims a single-path reversal update rule: after inserting or deleting one edge, reversing one carefully chosen path in an egalitarian orientation restores the conditions from which all ranks can be recomputed in linear time, yielding $O(p\\cdot|E|)$ per update with $O(p\\cdot|E|)$ space.","pith_inferences":["The rank-and-suffix-list scheme should transfer to other nested subgraph families with a similar dense-inside, sparse-outside property, such as (α,β)-cores, an extension the paper notes but does not develop.","The single-path-reversal invariant is the natural stress-test target: an adversarial sequence of edge updates that ever requires more than one reversed path would break the claimed $O(p\\cdot|E|)$ update time.","Construction cost amortizes once query volume is high; the paper's batch experiment suggests index-based processing overtakes online computation at batch sizes around 300 queries, so a streaming system could decide dynamically when to switch to the index.","Batching many updates before recomputing orientations may reduce the per-update cost further on very large graphs, since the time-efficient algorithms still pay a full graph traversal for each single edge change."],"forward_implications":["Any (α,β) query can be answered in time linear in the result size, independent of graph size, making dense-subgraph search feasible at billion-edge scale.","The index uses memory $\\Theta(|E|)$, roughly the size of the graph itself, about 8|E| bytes in the experiments, so it can be kept in RAM for large graphs.","On the 112.3-million-edge LI graph, the average query time drops to 2.74 milliseconds, compared with 21.49 seconds for the previous flow-based online algorithm.","Dynamic graphs can keep the index current at $O(p\\cdot|E|^{1.5})$ per edge update in linear space, or $O(p\\cdot|E|)$ per update when $O(p\\cdot|E|)$ of auxiliary orientations are stored.","The update theorems imply that after an edge insertion or deletion, the ranks of affected nodes change by at most one, so only a single layer of one node list needs repair."],"supporting_citations":[{"why":"Defines the (α,β)-dense subgraph model, the hierarchical property, the DSS++ algorithm, and the Divide-a/Divide-b routines that BD-Index construction calls.","marker":"[50]"},{"why":"Supplies the (α,β)-core model and its hierarchy, which motivates the extension remark and provides the comparison model with a similar index structure.","marker":"[26]"},{"why":"Establishes that the parameter p is typically a small constant in real-world graphs, which the construction and update complexity bounds rely on.","marker":"[48]"},{"why":"Provides unipartite density decomposition maintenance methods that the paper cites as inapplicable to the two-dimensional bipartite setting, motivating the new maintenance algorithms.","marker":"[49]"},{"why":"Provides the real-time recommendation workload of roughly 100,000 queries per second used to justify the latency targets and cost amortization argument.","marker":"[47]"},{"why":"Gives the sub-0.5-second response-time expectation for recommendations, used to argue that online flow-based query processing is impractical.","marker":"[25]"}],"fun_headline_variants":["Optimal queries, linear space: BD-Index for bipartite graphs","Query (α,β)-dense subgraphs in time proportional to size","Dynamic updates for bipartite dense subgraph index: two strategies","Optimal-time dense subgraph queries via suffix lists"],"cache_read_input_tokens":42496,"weakest_assumption_plain":"The load-bearing premise is that after every single edge insertion or deletion, reversing just one path, to the minimum-indegree reachable V-node for insertion or to the maximum-indegree reachable V-node for deletion, always restores the egalitarian orientation; if that invariant ever fails, the rank computation and the index silently become wrong.","fun_headline_variants_meta":{"raw":{"variants":["Optimal queries, linear space: BD-Index for bipartite graphs","Query (α,β)-dense subgraphs in time proportional to size","Dynamic updates for bipartite dense subgraph index: two strategies","Optimal-time dense subgraph queries via suffix lists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001609,"raw_usage":{"total_tokens":6475,"prompt_tokens":1079,"completion_tokens":5396,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":695,"completion_tokens_details":{"reasoning_tokens":5322}},"tokens_in":695,"tokens_out":5396,"duration_ms":37376,"temperature":1.0,"reasoning_tokens":5322,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:56:57.296502+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the insertion or deletion algorithm on a small bipartite graph and after each update check Definition 4 directly: every U-node's indegree equals $\\min(\\alpha, \\deg(u))$ and no V-to-V path has indegree gap at least two. Any update sequence where the single path reversal leaves a violated orientation, or where Query-BD-Index disagrees with a brute-force recomputation of $D_{\\alpha,\\beta}$ on the updated graph, disproves the update claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the (α,β)-dense subgraph model, the hierarchical property, the DSS++ algorithm, and the Divide-a/Divide-b routines that BD-Index construction calls."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that the parameter p is typically a small constant in real-world graphs, which the construction and update complexity bounds rely on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides unipartite density decomposition maintenance methods that the paper cites as inapplicable to the two-dimensional bipartite setting, motivating the new maintenance algorithms."}],"review_version":2}