Research map / Graph learning / Graph algorithms and clustering
Optimal community detection in dense bipartite graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives non-asymptotic minimax separation rate for detecting a planted k1×k2 dense community in n1×n2 bipartite Erdős–Rényi graphs, with matching upper and lower bounds in the dense regime, using truncated degree tests.
Problem
Detecting a planted bipartite dense community of size k1×k2 in a bipartite random graph versus a bipartite Erdős–Rényi null; characterizing the minimax separation rate non-asymptotically for all n1,n2,k1,k2.
Approach
Introduces truncated-degree and max truncated-degree tests built from hard-thresholded nonlinear (Bennett-function) statistics of the adjacency matrix, adapting the truncated chi-squared test to Bernoulli matrices, and combines them with the total degree test to match a second-moment lower bound for any configuration of sizes.
Key results
- Lower bound: (delta*)^2 >= c p0(1-p0) R holds for any n1,n2,k1,k2 without the density assumption, via second moment method.
- Upper bound: a combination of total degree, truncated degree and max truncated degree tests achieves risk below eta when delta^2 >= C p0(1-p0) R under the graph density assumption, matching the lower bound up to constants.
- Identifies a new phase transition at n1 k2 log(n2) / k1^2 ~ 1 in imbalanced bipartite graphs, not present in non-bipartite settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine total-degree, truncated-degree, and max-truncated-degree tests | proposed test Δ* · dense bipartite community detection | minimax separation rate | Helped |
Surprising findings
- The max scan test can be replaced by a max truncated degree test with lower time complexity, O(k1 n2 binom(n1,k1)) versus O(k1 k2 binom(n1,k1) binom(n2,k2)) for the scan.
Limitations
- Upper bound requires a dense-graph assumption on p0 (e.g., p0 >= C/(k1k2) log of binomial products), excluding sparse regimes.
- Tests require knowledge of p0, k1 and k2; adaptivity is left for future work.
- Max truncated degree test is computationally infeasible for moderate-size datasets; computational gap conjectured.
Experimental setup
Metrics: minimax risk (type I + type II error) minimax separation rate
Baselines: total degree test scan test Arias-Castro and Verzelen (2014) bounds Bipartite community detection results (Liu and Li-type analysis)
Builds on: truncated chi-squared test (Gaussian sequence model) Arias-Castro and Verzelen planted subgraph detection framework second moment method
Closest papers by meaning
- Phase transition for detecting a small community in a large network (ICLR 2023 · similarity 0.89)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.87)
- The Geometric Block Model (AAAI 2018 · similarity 0.87)
- Robustness of Community Detection to Random Geometric Perturbations (NeurIPS 2020 · similarity 0.87)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.86)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.