Research map / Learning theory and algorithms / Sample complexity
Sample Complexity of Correlation Detection in the Gaussian Wigner Model
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 the optimal sample size (induced subgraph size s ~ sqrt(n log n / log(1/(1-rho^2))) ∨ sqrt(n)) for detecting edge correlation between two Gaussian Wigner graphs under unlabeled vertex sampling, and proposes a clique-based polynomial-time approximate detector.
Problem
Detecting correlation between two random Gaussian Wigner graphs, observed only through independently sampled induced subgraphs with unlabeled vertices, and determining the sample size needed for reliable detection.
Approach
Characterizes the sharp sample-complexity threshold for induced-subgraph correlation detection by combining a max-overlap/MMSE-type test statistic (possibility) with a conditional second-moment analysis over a core set of vertices induced by cycles of the correlated functional digraph (impossibility), and adds a clique-seeded iterative mapping algorithm for efficiency.
Key results
- Theorem gives matching possibility and impossibility thresholds for induced-subgraph size s, of order sqrt(n log n / log(1/(1-rho^2)) ∨ n), up to constants.
- On synthetic data (n=50, s=30, eps=0.01), GED-based test AUC is 0.53, 0.73, 0.88 at rho=0.98, 1-1e-6, 1-1e-7, while the proposed algorithm reaches AUC 0.92, 1, 1 under the same settings.
- AUC increases from 0.52 to 1 as sample size s grows from 10 to 50 at rho=0.98 (n=50).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase sample size s from 10 to 50 | Clique-Based Detection Algorithm · Synthetic Gaussian Wigner graphs, n=50, ρ=0.98 | AUC: 0.52 to 1 | Helped |
| Increase correlation coefficient ρ from 0.95 to 0.99 | Clique-Based Detection Algorithm · Synthetic Gaussian Wigner graphs, n=50, s=40 | AUC: 0.55 to 1 | Helped |
| Use the Clique-Based Detection Algorithm instead of the GED-based test | Synthetic Gaussian Wigner graphs, n=50, s=30 · ρ=0.98, 1-10^{-6}, and 1-10^{-7} | AUC: 0.53,0.73, and 0.88 -> 0.92,1,1 | Helped |
| Use K1=4 and K2=3 instead of K1=2 and K2=1 (ablation) | Clique-Based Detection Algorithm · Synthetic Gaussian Wigner graphs, n=50, ρ=0.99 | Correlation detection performance | Helped |
Surprising findings
- Detection is impossible even when correlation is strong if s^2 = o(n), since the common vertex set is then empty with high probability.
Limitations
- Efficient algorithm has no theoretical guarantee; only empirical evaluation on small synthetic graphs (n=50).
- Analysis restricted to Gaussian Wigner model; extension to Erdos-Renyi is stated as future work.
- Possibility results for the MLE-like statistic are proven via exhaustive search, which is computationally inefficient (binom(s,m)^2 m!).
Experimental setup
Datasets: synthetic Gaussian Wigner graph pairs (100 independent, 100 correlated)
Benchmarks: synthetic Gaussian Wigner graph pairs
Metrics: AUC ROC curve (Type I vs Type II error)
Baselines: Graph Edit Distance (GED) pairwise edge-difference test (K1=2, K2=1)
Builds on: Gaussian Wigner correlated graph detection (fully observed) low-degree likelihood ratio conditional second moment method
Closest papers by meaning
- Phase Transitions in the Detection of Correlated Databases (ICML 2023 · similarity 0.88)
- Attributed Network Alignment: Statistical Limits and Efficient Algorithm (ICML 2026 · similarity 0.87)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.85)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.85)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.84)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · 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.