acceptodds
Under review as a conference paper at ICLR 2027

Constant-Factor Local Approximation for Bipartite Densest Subgraph

Abstract

Given a vertex in a large bipartite graph , can one quickly find a small densely connected region near ? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are and , its density is , where is the number of edges between and . We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph with at most vertices per side, our algorithm, starting from any vertex in , uses neighbour queries to find a subgraph of density on vertices, for every fixed . Our result improves upon the result of Andersen (2010), whose approximation guarantee depends logarithmically on the maximum degree. We complement this upper bound with information-theoretic and computational limitations showing that the quadratic dependence on in the output size is essentially unavoidable for constant-factor approximation. Our main technical innovation is an adaptation of the Lovasz–Simonovits curve to the bipartite density problem, based on weak- norm bounds.

Primary area:
learning theory
Keywords:
densest subgraph, local algorithms

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_1Qq8OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors provide a a deterministic, local, constant-factor approximation for the following bipartite density problem: given a vertex v in a bipartite graph G (which is guaranteed to be part of a rho-dense cohesive subgraph with k vertices on either side), it makes roughly O(k^4) local queries and outputs a dense subgraph (of at least the cohesive density rho) with roughly O(k^2) vertices. This output subgraph is “local” to v (it need not contain v, but is not too far in graph distance from it). The result is notably independent of the size of the graph, and its maximum degree, and thereby improves on a 2010 result by Andersen. It complements its upper bounds by essentially excluding o(k^2) outputs for deterministic algorithms whose query budget depends only on k, and for FPT algorithms assuming the Strongish Planted Clique Hypothesis. These show essentially that the results are optimal, up to some small factors. The technique starts from the pruned power iteration technique by Andersen, and uses a running prefix-based approach with a Lovasz-Simonovits-type of a win-win argument, wherein each sweep either finds a dense prefix pair, or a certificate of an upper bound on the sum that become “too low” with the remaining mass.

Critical strengths

While I am familiar with but not an expert on this line of work, I was sufficiently convinced by the motivation: from the graph theoretic point of view, it is conceivable that dense interaction blocks can have many external edges that effectively hide the interactions, and serve as obstructions to standard local clustering assumptions. Indeed, removing the best known degree-dependent approximation loss due to Andersen seems to resolve a mismatch between a density objective insensitive to boundary edges and guarantees sensitive to them. The main technical contribution of combining weak-ℓp\ell_p prefix bounds followed by the peeling process that controls degrees while keeping enough target edges is an elegant and substantial advance. I enjoyed reading these steps, and appreciated that they were complemented by the lower bounds (or rather, obstructions in the arguments) presented in Section 3.

The paper engages with interesting literature in important areas, such as the Liu-Gleich NeurIPS 2020 p-norm methods for semi-supervised learning on graphs, and local clustering with noisy labels, the setting by Luca et al. in ICLR 2024. I wonder if the worst-case density guarantees can lead to statistical recovery processes easily at all.

All in all, this is a well-written paper, and interesting. The AI use is acknowledged (and I view it to be fair and responsible).

Critical weaknesses

The arguments appear sound (based on what I checked of the proofs — much of the technical details are in the appendix and I did not verify them). Practical implications, however, are somewhat less convincing. For instance, as the authors state at the outset, before 1.1, the output might just be a large star, and could be disjoint from the given vertex v. In these contexts, it is harder to tie the results into the identification of fraudulent entities or meaningful communities, which are the “practical” motivations of this work.

In spite of this admittedly rather nitpicky concern, I will clarify that the results are interesting in their own right. I did not find any substantial weakness with the technical content or the presentation.

Questions for authors

Minor comments: it might be helpful to situate the readers with a comparison table for Andersen, Liu (2026), and the new guarantees; also, I would have appreciated a small worked example of peeling followed by a prefix sweep; change “there exists powers” to “there exist powers” on line 146.

1 comment

We thank the reviewer for their thoughtful and encouraging review!

We agree that exploring the connection between worst-case density approximation and statistical recovery is an interesting direction for future work. In particular, it would be interesting to investigate whether our techniques can yield recovery guarantees in suitable planted models.

Reviewer_SXrLOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper gives a deterministic constant-factor local approximation algorithm for the bipartite densest subgraph problem. Given a bipartite graph G=(L∪˙R,E)G=(L\mathbin{\dot\cup}R,E), the density of nonempty sets S⊆LS\subseteq L and T⊆RT\subseteq R is d(S,T):=e(S,T)/∣S∣∣T∣d(S,T):=e(S,T)/\sqrt{|S||T|}. The guarantee concerns cohesive target sets, meaning that every target vertex has at least half the average internal degree of its side. For any such target with at most kk vertices per side, the algorithm succeeds from every starting vertex in S∪˙TS\mathbin{\dot\cup}T and returns sets X,YX,Y of density Ωε(d(S,T))\Omega_\varepsilon(d(S,T)) on Oε(k2+ε)O_\varepsilon(k^{2+\varepsilon}) vertices, using Oε(k4+ε)O_\varepsilon(k^{4+\varepsilon}) neighbor queries and O~ε(k4+ε)\widetilde O_\varepsilon(k^{4+\varepsilon}) time, for every fixed ε>0\varepsilon>0. These bounds are independent of the graph size and maximum degree. The main improvement over Andersen’s algorithm is the removal of the maximum-degree dependence from the approximation guarantee and the worst-case locality bounds. The paper also establishes limitations on reducing the output size below the quadratic scale.

The algorithm builds on pruned power iteration and a Lovász–Simonovits-type win–win argument: either a sweep over prefixes of consecutive vectors finds a sufficiently dense pair, or the absence of such a pair bounds the next vector’s prefix sums. Using a weak-ℓp\ell_p norm with p>2p>2 avoids the logarithmic accumulation that arises in the corresponding weak-ℓ2\ell_2 analysis. An equally important ingredient is asymmetric vertex peeling.

I find the problem natural and interesting, the results strong, and the combination of weak-ℓp\ell_p analysis with degree-controlling peeling technically appealing. My overall assessment is positive, and I would lean toward acceptance on the strength of the theoretical contribution. My main reservations concern practical relevance without experimental evidence and the distinction between finding a dense nearby subgraph and recovering the target structure.

Critical strengths
  1. The problem is natural, and the removal of degree dependence is strong.

  2. The algorithmic analysis is interesting and well integrated.

  3. The lower bounds help explain the output-size tradeoff.

Critical weaknesses
  1. The lack of experiments is my main reservation regarding the application-oriented motivation, especially for a venue such as ICLR.

  2. The returned sets may not intersect the target or contain the starting vertex, so the result only guarantees approximation, not recovery of the target.

Questions for authors
  1. See the weaknesses.

  2. In the abstract, “cohesive” should be defined intuitively—for example, by saying that each target vertex has at least half the average internal degree on its side.

2 comments

We thank the reviewer for the careful assessment, editorial comment and the positive evaluation of the theoretical contribution.

  • Experiments.

While the main contribution of our paper is theoretical, we added an empirical evaluation – please see Appendix E. We compare the performance of our algorithm to that of Andersen’s algorithm on both synthetic and real instances. In both cases we plot the query budget vs density tradeoff curve. We consider the original algorithm of Andersen, as well as an improved version of it that considers prefixes of level sets, as in our algorithm (we refer to it as Andersen++) – the latter version performs consistently better. Besides the vanilla version of our algorithm as presented in the paper we consider a slightly fine tuned version – with σ2\sigma^2 multiplied by 16 and (3/4)t(3/4)^t replaced by 0.9t0.9^t.

For the synthetic experiments, we first design an asymptotic family of input instances where Andersen’s algorithm provably outputs no better than $ (\log n)^{1/4}$-approximation, and then implement a finite version of this instance. As predicted by theoretical bounds, our algorithm finds the planted solution whereas Andersen’s algorithm does not. Our solution has density about 65, whereas the one found by Andersen’s algorithm has density about 43 – please see Fig. 2. Andersen’s algorithm wins slightly at low query budgets by finding a few stars.

For experiments on real data we use four real bipartite graphs: MovieLens 1M, MovieLens 25M, Wikipedia user–page interactions, and Amazon Video Games. Here our algorithm outperforms Andersen and the improved Andersen++ on low query budgets. It does so not simply by finding stars, but by finding nontrivial subgraphs of average degree above 2 – please see Section E.2 for more details. At higher budgets Andersen++ outperforms our algorithm, and the comparison with Andersen is mixed (but mostly in our favor). These results provide an initial evaluation of the density achieved with limited graph access and identify both the potential advantages and the limitations of our approach. Evaluating running time and application-specific recovery remains future work.

  • On target recovery.

We agree that the theorem does not guarantee recovery of a substantial portion of the target. There are two additional properties relevant to the reviewer’s concern. First, seed inclusion can be enforced while preserving all asymptotic guarantees. If v∈Lv\in L, returning X′=X∪vX'=X\cup{v} together with YY satisfies d(X′,Y)≥∣X∣∣X∣+1⋅d(X,Y)≥d(X,Y)2.d(X',Y)\ge\sqrt{\frac{|X|}{|X|+1}}\cdot d(X,Y)\ge\frac{d(X,Y)}{\sqrt2}. This adds at most one output vertex and requires no additional neighbor queries. The case v∈Rv\in R is symmetric. Thus the output can be required to contain the starting vertex and, consequently, to intersect the target.

Second, every returned vertex lies within graph distance Oϵ(log⁡(2k))O_\epsilon(\log(2k)) of vv in GG. Hence proximity to the starting vertex has a precise graph-distance guarantee in addition to the query-complexity guarantee (see also Lemma B.3).

These properties address seed inclusion and proximity. Recovery of a substantial portion of the target remains beyond the theorem’s guarantee. We will emphasize this distinction in the application discussion and clarify that obtaining substantial recovery under additional structural assumptions is a direction for further work.

Dear reviewer,

We would appreciate hearing whether our responses have addressed your questions, and we would be happy to provide any further clarification.

Best regards, The Authors

Reviewer_5DpAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

For the problem of finding a small densely connected region near a given vertex, the authors’ main contribution is to provide a constant-factor local approximation for the densest subgraph that is independent of the maximum degree. Starting from any vertex in a cohesive target with at most k vertices on each side, it returns a constant-factor dense pair using query and output bounds depending on k, not on the graph size or maximum degree. Their technical approach adapts prefix sweeps and the Lovász–Simonovits analysis using weak-ℓp\ell_p bounds and vertex peeling.

Critical strengths
  • The proposed objective targets dense bipartite regions even when the regions have many external edges. This feature addresses a real limitation of conductance-based local clustering.
  • The proposed approach has independence from the maximum degree for the proposed approximation guarantee. This is the main advance over the state-of-the-art, according to the authods.
  • The weak-ellpell_p prefix-sum analysis and peeling construction provide strong explanation for controlling degree effects. The lower bounds established in the paper explain the near-quadratic output size.
Critical weaknesses
  • A major weakness is the lack of empirical evaluation.
  • While the theoretical independence from |V| and Δ\Delta is valuable, what is its practical impact?
  • Novelty over Andersen’s local dense-subgraph method is not clear.
Questions for authors
  • What is the potential to extend your results to a general (non-bipartite graph) setting?
  • How easy or hard is this problem?
  • Can you clarify the novelty of your contributions from Andersen’s local dense-subgraph method?
  • How will you compensate the lack of empirical insights on the bounds and the problem settings?
2 comments

We thank the reviewer for their careful reading and their assessment of the paper’s clarity and soundness.

  • Experiments.

While the main contribution of our paper is theoretical, we added an empirical evaluation – please see Appendix E. We compare the performance of our algorithm to that of Andersen’s algorithm on both synthetic and real instances. In both cases we plot the query budget vs density tradeoff curve. We consider the original algorithm of Andersen, as well as an improved version of it that considers prefixes of level sets, as in our algorithm (we refer to it as Andersen++) – the latter version performs consistently better. Besides the vanilla version of our algorithm as presented in the paper we consider a slightly fine tuned version – with σ2\sigma^2 multiplied by 16 and (3/4)t(3/4)^t replaced by 0.9t0.9^t.

For the synthetic experiments, we first design an asymptotic family of input instances where Andersen’s algorithm provably outputs no better than (log⁡n)1/4(\log n)^{1/4}-approximation, and then implement a finite version of this instance. As predicted by theoretical bounds, our algorithm finds the planted solution whereas Andersen’s algorithm does not. Our solution has density about 65, whereas the one found by Andersen’s algorithm has density about 43 – please see Fig. 2. Andersen’s algorithm wins slightly at low query budgets by finding a few stars.

For experiments on real data we use four real bipartite graphs: MovieLens 1M, MovieLens 25M, Wikipedia user–page interactions, and Amazon Video Games. Here our algorithm outperforms Andersen and the improved Andersen++ on low query budgets. It does so not simply by finding stars, but by finding nontrivial subgraphs of average degree above 2 – please see Section E.2 for more details. At higher budgets Andersen++ outperforms our algorithm, and the comparison with Andersen is mixed (but mostly in our favor).

  • Novelty over Andersen.

Independence from ∣V∣|V| is already present in Andersen’s result. Our contribution is a constant-factor approximation whose approximation ratio, output size, and query bound are all independent of Δ\Delta. For every fixed ϵ>0\epsilon > 0, we obtain constant approximation for the density (for a constant depending on ϵ\epsilon), Oϵ(k2)O_\epsilon(k^2) output vertices, and Oϵ(k4)O_\epsilon(k^4) queries, starting from every vertex of a cohesive target with at most kk vertices per side (Theorem 1.2).

Andersen’s approximation ratio is O(Δlog⁡k)O(\sqrt{\Delta \log k}), with O(k2Δlog⁡k)O(k^2 \Delta \log k) output vertices and queries. Liu (2026) obtains O(k)O(k) output vertices with the same degree-dependent ratio. For arbitrary targets, our starting-vertex guarantee matches Andersen’s through a subgraph containing at least half the target edges.

Conceptually, on top of an algorithmic change (sweeps compared to dyadic-set extraction of dense subgraph from a power-iteration-like process), our proof significantly diverges from Andersen’s prefix extraction in two places. We use weak-ℓp\ell_p prefix-sum bounds with p<1p < 1, so the contributions across dyadic scales form a geometric sum instead of accumulating logarithmically. We also use peeling to bound receiving degrees in terms of the target’s internal-degree thresholds while preserving enough target edges. Together, these steps remove the maximum degree from the approximation analysis.

  • Practical significance of degree independence.

A target’s density is unchanged when edges are added outside its induced subgraph. While the output of Andersen’s algorithm can deteriorate as these edges increase Δ\Delta, ours remains a constant fraction of the same target density. Thus the guarantee applies even when the target vertices have many external interactions.

  • General graphs.

For the same two-set Kannan–Vinay density, the result extends to general undirected graphs through the bipartite double cover. This preserves the target density, and every neighbor query in the cover requires one query in the original graph. The returned sets correspond to two possibly overlapping vertex sets.

  • How hard is the problem?

With unrestricted output size and access to the entire graph, a globally densest pair is computable in polynomial time by linear programming (Charikar, 2000). The difficulty here is to approximate a small unknown target while bounding both queries and output size in terms of kk alone. Our constant-factor approximation uses Oϵ(k2)O_\epsilon(k^2) output vertices and no deterministic constant-factor approximation can guarantee o(k2)o(k^2) output vertices when its query bound depends only on kk. Under the Strongish Planted Clique Hypothesis, this remains impossible even with running time kO(1)k^{O(1)} (Theorem 1.3).

Reviewer_5DpAOpenReview ↗

Thank you!

Thank you for the clarifications and the new information. I have changed my review.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.