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