Research map / Learning theory and algorithms / Matrix and tensor methods
Fitting Networks with a Cancellation Trick
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.
Proposes the logit-DCBM network model and a cancellation trick that yields closed-form estimates of nonlinear factors, plus R-SCORE, a recursive spectral community detection algorithm with Hamming error bounds.
Problem
Community detection in networks with degree heterogeneity under a logit-link latent variable model (logit-DCBM), where the nonlinear factors make the model non-low-rank and the beta-model parameters hard to fit.
Approach
A cancellation trick: ratios of two cycle-count sums cancel the nonlinear factors N_ij, giving closed-form estimates of theta and P; R-SCORE iterates SCORE with refitting that divides out estimated N to approximately restore a low-rank structure.
Key results
- In simulations (n=2400-5500), R-SCORE substantially reduces error relative to SCORE across four settings, typically converging within about one iteration.
- R-SCORE outperforms the npMLE baseline in Experiment 3 across beta_2 values while running about 50 times faster (6 s vs over 300 s per repetition).
- Theory: Hamming error of R-SCORE is n^{-min{1-2beta, 6beta}} versus n^{-min{1-2beta, 4beta}} for SCORE under theta ~ n^{-beta}, so R-SCORE is faster when beta < 1/6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use R-SCORE instead of SCORE directly | logit-DCBM community detection · Simulated networks, Experiment 1 (Settings A–D) | Hamming error rate | Helped |
| Use R-SCORE instead of SCORE directly | logit-DCBM community detection · Simulated network, Experiment 2 | Hamming error rate | Helped |
| Use R-SCORE instead of npMLE | logit-DCBM community detection · Simulated network, Experiment 2 | Hamming error rate | Helped |
| Use R-SCORE instead of npMLE | logit-DCBM community detection · Simulated networks, Experiment 3 | Hamming error rate | Helped |
| Use R-SCORE instead of npMLE | logit-DCBM community detection · Simulated networks, Experiment 3 | runtime: 6 seconds; more than 300 seconds | Helped |
| Replace direct SCORE with R-SCORE | logit-DCBM community detection · Sparse region, 0 < β < 1/6 | Hamming error rate: C n^{-a_0(β)}; C n^{-a_1(β)} | Helped |
| Replace direct SCORE with R-SCORE | logit-DCBM community detection · 1/6 < β < 1/2 | Hamming error rate: C n^{-a_0(β)}; C n^{-a_1(β)} | No clear effect |
| Use the cancellation-based refitting step and normalize the adjacency matrix by the estimated N | R-SCORE · Simulated logit-DCBM networks, Experiments 1–3 | Hamming error rate | Helped |
Surprising findings
- The paper's own rate analysis conjectures R-SCORE is at least as fast as SCORE across the whole range, and the stated bound may be conservative for beta > 1/6.
Limitations
- Theory relies on many technical conditions (balanced communities, theta of same order, spectral gap), with results stated only for one iteration.
- Theoretical rate for R-SCORE may be conservative beyond beta < 1/6; the conjecture that R-SCORE dominates SCORE in all ranges is unproven.
- Experiments are limited to simulated networks; no real-data evaluation is reported in the provided text.
Experimental setup
Datasets: simulated logit-DCBM networks
Benchmarks: simulated logit-DCBM networks
Metrics: Hamming error rate
Baselines: SCORE npMLE
Builds on: SCORE degree-corrected block model beta-model latent space model
Closest papers by meaning
- Phase transition for detecting a small community in a large network (ICLR 2023 · similarity 0.86)
- On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations (ICML 2017 · similarity 0.85)
- Completely random measures for modelling block-structured sparse networks (NeurIPS 2016 · similarity 0.85)
- Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting (ICML 2024 · similarity 0.84)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.83)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.83)
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.