Optimal $(\alpha,\beta)$-Dense Subgraph Search in Bipartite Graphs

Guoren Wang; Qi Zhang; Rong-Hua Li; Yalong Zhang

REVIEW 4 major objections 5 minor 55 references

Optimal $(\alpha,\beta)$-Dense Subgraph Search in Bipartite Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An index that answers (α,β)-dense subgraph queries in time proportional to the result set, using only linear space, and updates in near-linear time.

desk verdict 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. read the letter →

arxiv 2508.18616 v1 pith:FTVVMJEA submitted 2025-08-26 cs.DB

Yalong Zhang , Rong-Hua Li , Qi Zhang , Guoren Wang This is my paper · ORCID

classification cs.DB

keywords bipartitegraphsdensesubgraph(αβ)-denseindexstructuredynamicgraphmaintenanceegalitarianorientationα-rankqueryprocessing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Two 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.

Bottom 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.

Referee Report

4 major / 5 minor

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.

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 (4)

[§5.2, Theorems 11 and 13; Algorithms 6 and 7] 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.
[§4.2 and §5.2, Algorithms 3, 4, 6, 7] 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.
[§5.2 and §5.1] 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.
[§4.1, Theorems 6 and 7] 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.

minor comments (5)

[§4.2, first paragraph] The text says 'BD-Insert-S and BD-Insert-D', but the deletion algorithm is named BD-Delete-S; please correct the name.
[Throughout] There are several typos: 'maintence' (Section 1), 'dirctly' (Section 5), and 'acorss' (Section 6, Exp-4). Please proofread.
[§5.1, Theorem 10 proof] 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.
[§3.3, Theorem 5 proof] 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.
[§3.1, Definition 3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the index and maintenance derivations are self-contained given the cited (α,β)-dense subgraph model; self-citations supply prior independent results, not re-imported conclusions.

full rationale

The paper's query result D_{α,β} is the input object, not an output derived from fitted values. α-rank/β-rank are defined directly from D_{α,k}, and Theorem 3 re-expresses D_{α,β} as a threshold set over these ranks; this is an index representation lemma, not a prediction. Query-BD-Index simply scans the precomputed list, so O(|D_{α,β}|) time is the stated construction of the index rather than a derived empirical claim. The space bound Θ(|E|) is argued from Lemma 1 and the cited dense-inside/sparse-outside property, and the maintenance theorems are proved from the egalitarian-orientation invariants, with no fitted parameters. Citations to [50] provide the definition of the model, the hierarchical/density properties, and DSS++/Divide-a/Divide-b building blocks; these are prior-work theorems used as hypotheses, not conclusions of this paper, and nothing in the present derivation is justified solely by a self-citation that itself depends on this paper's results. The abbreviated arguments in Theorems 11 and 13 raise a proof-completeness/correctness risk about path reversal, but a suspected gap in an invariant proof is not circularity: it does not make the claimed O(p|E|) update result equivalent by definition to its assumptions.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The central claims rest on theorems taken from the authors' prior work [50], on an implicit edge-count fact about D_{0,0}, and on an unstated reachability-rank monotonicity property used in the path-reversal arguments. No free parameters are fitted: p is a graph property, not a tuned constant.

assumptions (5)

domain assumption Hierarchical property: for α+ ≥ α and β+ ≥ β, D_{α+,β+} ⊆ D_{α,β} (Theorem 2, cited from [50]).
Underpins the rank definitions and Theorem 3; taken as given from the authors' earlier work rather than proved here.
domain assumption Dense-inside/sparse-outside bounds for D_{α,β} (Theorem 1, cited from [50]).
Used in the Θ(|E|) space proof of Theorem 5 and in the Ω(|E|) lower-bound argument.
domain assumption DSS++, Divide-a and Divide-b compute (α,β)-dense subgraphs correctly in O(|E|^1.5) and O(|E|^1.5 log|U∪V|) time (from [50]).
Index construction (Algorithm 2) and the space-efficient maintenance algorithms invoke these as subroutines; correctness and complexity of the index inherit these bounds.
ad hoc to paper D_{0,0} contains every edge of G, so |E(D_{0,0})| = |E|.
Needed for the Ω(|E|) space proof (Theorem 5) to equate Σ E^Δ_t with |E|; not stated explicitly in the paper but follows from Definition 1.
ad hoc to paper In an egalitarian orientation, if a node x can reach node y, then r_α(x) ≥ r_α(y).
Used implicitly in Theorems 8, 11 and 13 to justify path-reversal maintenance; it is derivable from the egalitarian characterization of D_{α,β} (Theorem 10) but is never stated as a lemma.

invented entities (1)

Egalitarian orientation
purpose: A directed orientation of the bipartite graph (for a given α) in which each U node has indegree exactly α (or its full degree when smaller) and no two V nodes connected by a directed path have indegrees differing by 2 or more; maintained to enable O(p|E|) index updates.
This is a new mathematical construct introduced by the paper. It has no falsifiable handle outside the paper; its correctness rests entirely on the internal proofs (Theorem 10 and the path-reversal invariants in Theorems 11 and 13), which are the least rigorous part of the manuscript.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal $(\alpha,\beta)$-Dense Subgraph Search in Bipartite Graphs." pith.science (2026). https://pith.science/paper/FTVVMJEA

@misc{pith2026250818616,
  author       = {Pith},
  title        = {Pith review of: Optimal $(\alpha,\beta)$-Dense Subgraph Search in Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FTVVMJEA}},
  note         = {Machine review of arXiv:2508.18616}
}

abstract

Dense subgraph search in bipartite graphs is a fundamental problem in graph analysis, with wide-ranging applications in fraud detection, recommendation systems, and social network analysis. The recently proposed $(\alpha, \beta)$-dense subgraph model has demonstrated superior capability in capturing the intrinsic density structure of bipartite graphs compared to existing alternatives. However, despite its modeling advantages, the $(\alpha, \beta)$-dense subgraph model lacks efficient support for query processing and dynamic updates, limiting its practical utility in large-scale applications. To address these limitations, we propose BD-Index, a novel index that answers $(\alpha, \beta)$-dense subgraph queries in optimal time while using only linear space $O(|E|)$, making it well-suited for real-world applications requiring both fast query processing and low memory consumption. We further develop two complementary maintenance strategies for dynamic bipartite graphs to support efficient updates to the BD-Index. The space-efficient strategy updates the index in time complexity of $O(p \cdot |E|^{1.5})$ per edge insertion or deletion, while maintaining a low space cost of $O(|E|)$ (the same as the index itself), where $p$ is typically a small constant in real-world graphs. In contrast, the time-efficient strategy significantly reduces the update time to $O(p \cdot |E|)$ per edge update by maintaining auxiliary orientation structures, at the cost of increased memory usage up to $O(p \cdot |E|)$. These two strategies provide flexible trade-offs between maintenance efficiency and memory usage, enabling BD-Index to adapt to diverse application requirements. Extensive experiments on 10 large-scale real-world datasets demonstrate high efficiency and scalability of our proposed solutions.

Figures

Figures reproduced from arXiv: 2508.18616 by the authors.

**Figure 1.** An example graph 𝐺 = (𝑈 ,𝑉 , 𝐸) and its orientation. node 𝑣4 due to the higher 𝛽 value, resulting in a denser subgraph. Further increasing 𝛽 to 3 yields no subgraph satisfying the density requirement, thus, 𝐷1,3 = ∅. In practical applications (such as e-commerce recommendation and fraud detection), it is often necessary to frequently query 𝐷𝛼,𝛽 for different combinations of (𝛼, 𝛽) parameters. This necessitates the d… view at source ↗

**Figure 2.** Example of BD-Index and querying 𝐷0,2. verifies that 𝛼 < I 𝑈 𝐵𝐷 .𝑠𝑖𝑧𝑒 = 2 and 𝛽 < I 𝑈 𝐵𝐷 [𝛼].𝑠𝑖𝑧𝑒 = 4, confirming that 𝐷𝛼,𝛽 ≠ ∅. The algorithm then retrieves all nodes from I 𝑈 𝐵𝐷 [𝛼][𝛽] = 𝑢5 to the end of the node list, which includes {𝑢5, 𝑣4, 𝑣1, 𝑢1, 𝑣2, 𝑣3, 𝑢4, 𝑢3, 𝑢2}, as the query result 𝐷𝛼,𝛽 . Next, we prove the correctness of Query-BD-Index and establish its optimal query time complexity. Theorem 4. Query-BD… view at source ↗

**Figure 3.** Example of computing 𝑟𝛼 from an egalitarian orientation. Intuition behind egalitarian orientation. The term “egalitarian” in egalitarian orientation refers to the balancing of indegrees among nodes in 𝑉 . Suppose there exists a path 𝑣𝑠 ↝ 𝑣𝑡 in an orientation 𝐸⃗ such that 𝑣𝑠 , 𝑣𝑡 ∈ 𝑉 and 𝑑⃗ 𝑣𝑡 (𝐸⃗) − 𝑑⃗ 𝑣𝑠 (𝐸⃗) ≥ 2. By reversing this path (i.e., reversing the direction of all edges along the path), the indegree of 𝑣… view at source ↗

Figures from the paper (8 more)

**Figure 6.** Figure 6: Memory usage of graph and BD-Index [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 5.** Figure 5: Running time with varying 𝛼 and 𝛽 on dataset LI. the running times of Online, Online++, and Query-BD-Index are 49.84 seconds, 29.82 seconds, and 0.0034 seconds, respectively. On the large-scale dataset LI with over 100 million edges, the maximum query time of Online, …

**Figure 7.** Figure 7: Scalability test of Build-BD-Index algorithm. results align well with the theoretical 𝑂(∣𝐸∣) space complexity of BD-Index, highlighting its highly space-efficient advantage. Exp-4: Index construction time [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]

**Figure 9.** Figure 9: Memory usage of two maintenance approaches. [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]

**Figure 10.** Figure 10: Scalability test of maintenance algorithms (mea [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]

**Figure 11.** Figure 11: Runtime of maintenance algorithms with differ [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]

**Figure 12.** Figure 12: Query turnaround time and update turnaround time of different algorithms on dataset AM-app. 10² 10³ Batch size 10¹ 10² 10³ Runtime (sec) Build-BD-Index + Query-BD-Index Online Online++ (a) Batch-query results. 10 10¹ 10² 10³ 10 Batch size 10¹ 10² 10³ Runtime (sec) Bui…

**Figure 13.** Figure 13: Batch-query and batch-update results on the temporal AM dataset. (details in [PITH_FULL_IMAGE:figures/full_fig_p016_13.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 49 canonical work pages

[50]

Yalong Zhang, Rong-Hua Li, Qi Zhang, Hongchao Qin, Lu Qin, and Guoren Wang. 2025. Density Decomposition of Bipartite Graphs. Proc. ACM Manag. Data 3, 1, Article 30 (Feb. 2025), 25 pages

work page 2025
[1]

Mohammad Allahbakhsh, Aleksandar Ignjatovic, Boualem Benatallah, Amin Beheshti, Elisa Bertino, and Norman Foo. 2013. Collusion Detection in Online Rating Systems. In Web Technologies and Applications - 15th Asia-Pacific Web Conference, APWeb 2013, Sydney, Australia, April 4-6, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7808) , Yoshiharu Is...

work page doi:10.1007/978-3-642-37401-2_21 2013
[2]

Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. 2000. Greedily Finding a Dense Subgraph. J. Algorithms 34, 2 (2000), 203–221

work page 2000
[3]

Bahman Bahmani, Ashish Goel, and Kamesh Munagala. 2014. Efficient Primal- Dual Graph Algorithms for MapReduce. InW A W 2014, Vol. 8882. Springer, 59–78

work page 2014
[4]

Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest Subgraph in Streaming and MapReduce. Proc. VLDB Endow. 5, 5 (2012), 454–465

work page 2012
[5]

Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. 2013. CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In WWW 2013. 119–130

work page 2013
[6]

Tsourakakis, Di Wang, and Junxing Wang

Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting Dens- est Subgraphs Without Flow Computations. In WWW. 573–583

work page 2020
[7]

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. 2013. Exact and approximation algorithms for densest k-subgraph. In W ALCOM 2013. Springer, 114–125

work page 2013

Show all 55 references

[8]

Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX 2000s, Vol. 1913. Springer, 84–95

2000
[9]

Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In SODA. SIAM, 1531–1555

2022
[10]

Jiujian Chen, Kai Wang, Ronghua Li, Hongchao Qin, Xuemin Lin, and Guoren Wang. 2024. Maximal Biclique Enumeration: A Prefix Tree Based Approach. In ICDE 2024. IEEE, 2544–2556

2024
[11]

Calvin Chi, Yuting Ye, Bin Chen, and Haiyan Huang. 2021. Bipartite graph- based approach for clustering of cell lines by gene expression-drug response associations. Bioinform. 37, 17 (2021), 2617–2626

2021
[12]

Francesco Colace, Massimo De Santo, Luca Greco, Vincenzo Moscato, and Anto- nio Picariello. 2015. A collaborative user-centered framework for recommending items in Online Social Networks. Comput. Hum. Behav. 51 (2015), 694–704

2015
[13]

Qiangqiang Dai, Rong-Hua Li, Donghang Cui, Meihao Liao, Yu-Xuan Qiu, and Guoren Wang. 2024. Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee. Proc. ACM Manag. Data 2, 3 (2024), 135

2024
[14]

Yizhou Dai, Miao Qiao, and Lijun Chang. 2022. Anchored Densest Subgraph. In SIGMOD 2022. ACM, 1200–1213

2022
[15]

Apurba Das and Srikanta Tirthapura. 2018. Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph. IEEE Trans. Multi Scale Comput. Syst. 4, 3 (2018), 231–242

2018
[16]

Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017. Efficient Fault-Tolerant Group Recommendation Using alpha-beta-core. In CIKM 2017. ACM, 2047–2050

2017
[17]

Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015. Efficient Densest Subgraph Computation in Evolving Graphs. In WWW 2015. ACM, 300–310

2015
[18]

Andrew V Goldberg. 1984. Finding a maximum density subgraph . Technical Report. University of California Berkeley, Berkeley, CA, USA

1984
[19]

Dmitry I. Ignatov. 2019. Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters. In ICFCA, Vol. 2378. 28–32

2019
[20]

Kuznetsov, Amedeo Napoli, and Sébastien Duplessis

Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli, and Sébastien Duplessis
[21]

Barrie Kersbergen, Olivier Sprangers, and Sebastian Schelter. 2022. Serenade - Low-Latency Session-Based Recommendation in e-Commerce at Scale. In SIG- MOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 , Zachary G. Ives, Angela ...

2022
[22]

Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In ICALP 2009, Vol. 5555. Springer, 597–608

2009
[23]

Ravi Kumar, Andrew Tomkins, and Erik Vee. 2008. Connectivity structure of bipartite graphs via the KNC-plot. In WSDM 2008. ACM, 129–138

2008
[24]

Michael Ley. 2002. The DBLP Computer Science Bibliography: Evolution, Re- search Issues, Perspectives. In SPIRE 2002, Vol. 2476. Springer, 1–10

2002
[25]

Greg Linden, Brent Smith, and Jeremy York. 2003. Amazon.com Recommenda- tions: Item-to-Item Collaborative Filtering. IEEE Internet Comput. 7, 1 (2003), 76–80. https://doi.org/10.1109/MIC.2003.1167344

2003 arXiv
[26]

Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou
[27]

Xiaowen Liu, Jinyan Li, and Lusheng Wang. 2008. Quasi-bicliques: Complexity and Binding Pairs. In COCOON, Vol. 5092. 255–264

2008
[28]

Wensheng Luo, Qiaoyuan Yang, Yixiang Fang, and Xu Zhou. 2023. Efficient Core Maintenance in Large Bipartite Graphs. Proc. ACM Manag. Data 1, 3 (2023), 208:1–208:26

2023
[29]

Bingqing Lyu, Lu Qin, Xuemin Lin, Ying Zhang, Zhengping Qian, and Jingren Zhou. 2020. Maximum Biclique Search at Billion Scale. Proc. VLDB Endow. 13, 9 (2020), 1359–1372

2020
[30]

Chenhao Ma, Reynold Cheng, Laks V. S. Lakshmanan, and Xiaolin Han. 2022. Finding Locally Densest Subgraphs: A Convex Programming Approach. Proc. VLDB Endow. 15, 11 (2022), 2719–2732

2022
[31]

Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, and Xiaolin Han. 2022. A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery. In SIGMOD 2022. ACM, 845–859

2022
[32]

Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. 2020. Efficient Algorithms for Densest Subgraph Dis- covery on Large Directed Graphs. In SIGMOD 2020. ACM, 1051–1066

2020
[33]

Muhammad Anis Uddin Nasir, Aristides Gionis, Gianmarco De Francisci Morales, and Sarunas Girdzijauskas. 2017. Fully Dynamic Algorithm for Top-k Densest Subgraphs. In CIKM 2017. ACM, 1817–1826

2017
[34]

Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In KDD. 965–974

2015
[35]

Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. 2012. Dense Subgraphs on Dynamic Networks. In DISC 2012, Vol. 7611. Springer, 151– 165

2012
[36]

Saurabh Sawlani and Junxing Wang. 2020. Near-optimal fully dynamic densest subgraph. In STOC 2020. ACM, 181–193

2020
[37]

Kelvin Sim, Jinyan Li, Vivekanand Gopalkrishnan, and Guimei Liu. 2009. Mining maximal quasi-bicliques: Novel algorithm and applications in the stock market and protein networks. Stat. Anal. Data Min. 2, 4 (2009), 255–273

2009
[38]

Nikolaj Tatti. 2019. Density-Friendly Graph Decomposition. ACM Trans. Knowl. Discov. Data 13, 5 (2019), 54:1–54:29

2019
[39]

de Vries, and Marcel J

Jun Wang, Arjen P. de Vries, and Marcel J. T. Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In SIGIR

2006
[40]

Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient Bitruss Decomposition for Large-scale Bipartite Graphs. In ICDE 2020. IEEE, 661–672

2020
[41]

Yue Wang, Ruiqi Xu, Xun Jian, Alexander Zhou, and Lei Chen. 2022. Towards Distributed Bitruss Decomposition on Bipartite Graphs. Proc. VLDB Endow. 15, 9 (2022), 1889–1901

2022
[42]

Xiaowei Ye, Rong-Hua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang
[43]

Xiaowei Ye, Rong-Hua Li, Lei Liang, Zhizhen Liu, Longlong Lin, and Guoren Wang. 2024. Efficient and Effective Anchored Densest Subgraph Search: A Convex-programming based Approach. In KDD 2024. ACM, 3907–3918

2024
[44]

Ziqi Yin, Qi Zhang, Wentao Zhang, Rong-Hua Li, and Guoren Wang. 2023. Fairness-aware Maximal Biclique Enumeration on Bipartite Graphs. In ICDE

2023
[45]

Kaiqiang Yu, Cheng Long, Shengxin Liu, and Da Yan. 2022. Efficient Algorithms for Maximal k-Biplex Enumeration. In SIGMOD 2022. ACM, 860–873

2022
[46]

Kaiqiang Yu, Cheng Long, Deepak P, and Tanmoy Chakraborty. 2023. On Efficient Large Maximal Biplex Discovery. IEEE Trans. Knowl. Data Eng. 35, 1 (2023), 824– 829

2023
[47]

Qiang Zhang, Zhipeng Teng, Disheng Wu, and Jiayin Wang. 2024. An Enhanced Batch Query Architecture in Real-time Recommendation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM 2024, Boise, ID, USA, October 21-25, 2024 , Edo...

2024
[48]

Yalong Zhang, Ronghua Li, Qi Zhang, Hongchao Qin, Lu Qin, and Guoren Wang
[49]

Yalong Zhang, Ronghua Li, Qi Zhang, Hongchao Qin, and Guoren Wang. 2024. Efficient Algorithms for Density Decomposition on Large Static and Dynamic Yalong Zhang, Rong-Hua Li, Qi Zhang, and Guoren Wang Graphs. Proc. VLDB Endow. 17, 11 (2024), 2933–2945

2024
[51]

Zhaonian Zou. 2016. Bitruss Decomposition of Bipartite Graphs. In DASFAA 2016, Vol. 9643. Springer, 218–233

2016
[2011]

Mining gene expression data with pattern structures in formal concept analysis. Inf. Sci. 181, 10 (2011), 1989–2001

2011
[2019]

InWWW 2019

Efficient (a,𝛽)-core Computation: an Index-based Approach. InWWW 2019. ACM, 1130–1141

2019
[2023]

Efficient Biclique Counting in Large Bipartite Graphs. Proc. ACM Manag. Data 1, 1 (2023), 78:1–78:26

2023
[2024]

Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs. Proc. VLDB Endow. 17, 11 (2024), 2722–2734

2024

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [50]

Yalong Zhang, Rong-Hua Li, Qi Zhang, Hongchao Qin, Lu Qin, and Guoren Wang. 2025. Density Decomposition of Bipartite Graphs. Proc. ACM Manag. Data 3, 1, Article 30 (Feb. 2025), 25 pages

work page 2025

[2] [1]

Mohammad Allahbakhsh, Aleksandar Ignjatovic, Boualem Benatallah, Amin Beheshti, Elisa Bertino, and Norman Foo. 2013. Collusion Detection in Online Rating Systems. In Web Technologies and Applications - 15th Asia-Pacific Web Conference, APWeb 2013, Sydney, Australia, April 4-6, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7808) , Yoshiharu Is...

work page doi:10.1007/978-3-642-37401-2_21 2013

[3] [2]

Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, and Takeshi Tokuyama. 2000. Greedily Finding a Dense Subgraph. J. Algorithms 34, 2 (2000), 203–221

work page 2000

[4] [3]

Bahman Bahmani, Ashish Goel, and Kamesh Munagala. 2014. Efficient Primal- Dual Graph Algorithms for MapReduce. InW A W 2014, Vol. 8882. Springer, 59–78

work page 2014

[5] [4]

Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest Subgraph in Streaming and MapReduce. Proc. VLDB Endow. 5, 5 (2012), 454–465

work page 2012

[6] [5]

Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. 2013. CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In WWW 2013. 119–130

work page 2013

[7] [6]

Tsourakakis, Di Wang, and Junxing Wang

Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting Dens- est Subgraphs Without Flow Computations. In WWW. 573–583

work page 2020

[8] [7]

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th Paschos. 2013. Exact and approximation algorithms for densest k-subgraph. In W ALCOM 2013. Springer, 114–125

work page 2013