Research map / Graph learning / Graph algorithms and clustering
Why the Metric Backbone Preserves Community Structure
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.
Proves that the metric backbone (union of all-pairs shortest paths) of weighted stochastic block models approximately preserves the relative edge densities between communities, so spectral clustering on it recovers communities, and shows it is an effective sparsifier including for q-NN graphs.
Problem
Whether removing semi-metric edges (keeping only the metric backbone) dilutes or destroys community structure in weighted networks, given that inter-community bridge edges tend to be metric while dense intra-community edges tend to be semi-metric.
Approach
Characterizes the metric backbone of weighted SBMs via first-passage percolation: the probability an edge between blocks a and b survives is asymptotically proportional to p_ab, with a common factor (log n)/(n rho_n), so the backbone thins all block pairs nearly uniformly and preserves community structure.
Key results
- Theorem: the ratio p^mb_ab / p_ab scales as (log n)/(n rho_n) times a constant depending only on lambda_ab and tau, so p^mb_ab/q^mb_ab approx p_0/q_0 in the planted partition model.
- On the full MNIST q-NN graph, the approximate metric backbone with sqrt(n)/2 neighbors reaches spectral clustering ARI 0.563 vs 0.533 for the 10-NN graph, with 373k edges vs 551k.
- On the metric backbone, spectral sparsification and the metric backbone retain community structure equally well across datasets and clustering algorithms, while thresholding often yields disconnected small components.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Spectral clustering · MNIST | ARI: 0.533 -> 0.563 ± 0.011 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Spectral clustering · FashionMNIST | ARI: 0.411 -> 0.425 ± 0.006 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Spectral clustering · HAR | ARI: 0.519 -> 0.492 ± 0.001 | Hurt |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Poisson learning · MNIST | ARI: 0.814 ± 0.015 -> 0.821 ± 0.021 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Poisson learning · FashionMNIST | ARI: 0.526 ± 0.010 -> 0.544 ± 0.014 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Poisson learning · HAR | ARI: 0.618 ± 0.039 -> 0.636 ± 0.037 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Graph · MNIST | edges: 550,653 -> 373,379 ± 3,018 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Graph · FashionMNIST | edges: 578,547 -> 272,063 ± 857 | Helped |
| Use the approximate metric backbone of q=√n/2-NN instead of G10 | Graph · HAR | edges: 77,526 -> 37,535 ± 977 | Helped |
Surprising findings
- Contrary to the intuition that bridge edges are metric and intra-community edges are semi-metric (thinning intra-community edges more), the metric backbone thins edges approximately uniformly across block pairs and preserves community structure.
Limitations
- Theory assumes asymptotic regime with fixed k, block matrix B and cost distributions with positive density at zero (Assumption on F'(0) = lambda > 0).
- Spectral recovery theorem requires tau_max = tau_min and invertible T, which restricts the setting.
- Experiments rely on proximity-to-distance transform c = 1/p - 1 and on a limited set of datasets and clustering algorithms.
Experimental setup
Datasets: MNIST FashionMNIST HAR Primary school contact network
Benchmarks: MNIST FashionMNIST HAR Primary school
Metrics: adjusted Rand index number of edges
Baselines: threshold graph spectral sparsification q-nearest neighbor graph
Builds on: first-passage percolation Spielman-Srivastava spectral sparsification Bayesian stochastic block model inference Leiden algorithm
Closest papers by meaning
- Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering (ICML 2024 · similarity 0.83)
- How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.83)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.82)
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.82)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.82)
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.82)
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.