Research map / Learning theory and algorithms / Sample complexity
Network two-sample test for block models
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 SBM-TS, a two-sample test for unlabeled networks of different sizes that matches SBM connectivity matrices via spectral matching, and derives a chi-squared null distribution with consistency guarantees.
Problem
Two-sample testing of network distributions without vertex correspondence and with possibly different numbers of nodes, which requires matching community labels/permutations of SBM parameters across networks.
Approach
Estimate block connectivity matrices per network, align them to a common labeling via an efficient spectral matching algorithm (eigenvector sign recovery plus linear assignment), pool block sums and counts across samples, and form a variance-normalized chi-squared-type statistic with asymptotic chi-squared(K(K+1)/2) null.
Key results
- On the simple 2-block SBM experiment at n=100, eps=0.1, SBM-TS reaches power 1.0 while ASE achieves 0.27.
- On the general SBM with random B and K=2, mean AUC is 0.95 for SBM-TS versus 0.62 for ASE and 0.70 for NCLM; at K=20 SBM-TS AUC is 0.81 versus about 0.5 for baselines.
- On RDPG experiments, SBM-TS essentially attains perfect ROC while ASE-MMD performs poorly due to lack of rotation matching.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SBM-TS instead of ASE | 2-SBM two-sample test · n=100, ε=0.05 | power: 0.09 -> 0.776 | Helped |
| Use SBM-TS instead of ASE | 2-SBM two-sample test · n=200, ε=0.02 | power: 0.09 -> 0.599 | Helped |
| Use SBM-TS instead of ASE | 2-SBM two-sample test · n=500, ε=0.02 | power: 0.01 -> 1 | Helped |
| Use SBM-TS instead of ASE | 2-SBM two-sample test · n=1000, ε=0.01 | power: 0.14 -> 1 | Helped |
| Use SBM-TS instead of ASE | General SBM test · K=2 | AUC: 0.62 -> 0.95 | Helped |
| Use SBM-TS instead of NCLM | General SBM test · K=2 | AUC: 0.70 -> 0.95 | Helped |
| Use SBM-TS instead of ASE | General SBM test · K=3 | AUC: 0.54 -> 0.91 | Helped |
| Use SBM-TS instead of NCLM | General SBM test · K=3 | AUC: 0.64 -> 0.91 | Helped |
| Use SBM-TS instead of ASE | General SBM test · K=15 | AUC: 0.49 -> 0.83 | Helped |
| Use SBM-TS instead of NCLM | General SBM test · K=15 | AUC: 0.50 -> 0.83 | Helped |
| Use SBM-TS instead of ASE | General SBM test · K=20 | AUC: 0.48 -> 0.81 | Helped |
| Use SBM-TS instead of NCLM | General SBM test · K=20 | AUC: 0.50 -> 0.81 | Helped |
Surprising findings
- ASE-MMD's null distribution is bimodal under RDPG because it ignores orthogonal rotation mismatch between embeddings.
Limitations
- Matching guarantees require (theta, eta)-friendly connectivity matrices with eigenvalue gaps.
- Power degrades as K grows because block estimates become noisier and approximate matching is harder.
- Theory assumes K known; K is chosen by a parametric bootstrap heuristic in practice.
Experimental setup
Datasets: COLLAB SW-GOT networks
Benchmarks: COLLAB SW-GOT
Metrics: power ROC curve AUC
Baselines: NCLM ASE-MMD
Builds on: NCLM ASE-MMD spectral clustering
Closest papers by meaning
- From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple Graphs (AAAI 2025 · similarity 0.88)
- Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models (NeurIPS 2019 · similarity 0.88)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.88)
- Completely random measures for modelling block-structured sparse networks (NeurIPS 2016 · similarity 0.87)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.85)
- Robust Graph Matching when Nodes are Corrupt (ICML 2024 · similarity 0.84)
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.