Research map / Graph learning / Graph algorithms and clustering
Practical Methods for Graph Two-Sample Testing
Debarghya Ghoshdastidar, Ulrike von Luxburg
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Asymp-Normal instead of Boot-Spectral or Boot-Frobenius | Graph two-sample testing with m=2 · Two-community stochastic block models | test power | Improved |
| Use Asymp-Normal instead of Boot-Frobenius | Graph two-sample testing with m=4 · Two-community stochastic block models | test power | No clear effect |
| Use Boot-Spectral instead of Asymp-Normal | Graph two-sample testing with m=4 · Small graph sizes | test power | Mixed |
| Use Asymp-Chi2 in the small-m regime | Graph two-sample testing · Small populations | test power | Hurt |
| Use Asymp-Chi2 only when the population size is much larger than graph size | Graph two-sample testing · Large populations | test reliability | Improved |
| Increase edge density | Graph two-sample tests · Stochastic block models with m>1 | test power | Improved |
| Use Boot-EPA instead of Asymp-TW | Testing two large graphs · Low-rank block models with correctly specified rank r=2 | test power | Improved |
| Use Boot-ASE with the true rank | Testing two large graphs · Low-rank block models with r=2 | type-I error rate | Hurt |
| Overestimate the rank parameter from r=2 to r=4 (ablation) | Boot-ASE · Two large graphs | test reliability | Hurt |
| Overestimate the rank parameter from r=2 to r=4 (ablation) | Boot-EPA · Two large graphs | test reliability | Hurt |
| Overestimate the rank parameter from r=2 to r=4 (ablation) | Asymp-TW · Two large graphs | test reliability | No clear effect |
| Increase edge density | Asymp-TW · Testing two large graphs | test power | Improved |
Closest papers by meaning
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.82)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.80)
- Sample Complexity of Correlation Detection in the Gaussian Wigner Model (ICML 2025 · similarity 0.79)
- Calibration without labels in multiple testing (NeurIPS 2026 · similarity 0.79)
- Hypothesis Testing for Generalized Thurstone Models (ICML 2025 · similarity 0.79)
- Test-time Adaptation on Graphs via Adaptive Subgraph-based Selection and Regularized Prototypes (ICML 2025 · similarity 0.79)
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.
