Research map / Learning theory and algorithms / Clustering
Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering
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 theoretical properties of biharmonic distance on graph edges (electrical-flow, cut sparsity, Foster-type identities), generalizes it to k-harmonic distance, and proposes biharmonic k-means and Girvan-Newman clustering evaluated on kNN graphs from UCI datasets.
Problem
Effective resistance captures pair connectivity but not how important an edge is to global graph topology; biharmonic distance is a spectral distance whose theoretical properties and applications are poorly understood.
Approach
Shows squared biharmonic distance of an edge equals the normalized total electrical-flow usage of that edge over all vertex pairs, links it to cut sparsity, and generalizes it to k-harmonic distance (L^{k+}) with a k-harmonic Foster's theorem; uses these to design biharmonic k-means and Girvan-Newman clustering.
Key results
- Biharmonic k-harmonic clustering reached purity up to 0.933 on Iris (nn=100), versus 0.661 for spectral clustering at the same setting.
- Biharmonic distance was highly correlated with current-flow centrality on sparse kNN graphs, while 5-harmonic distance was often almost perfectly correlated with current-flow centrality.
- Effective resistance was the most resilient centrality measure to random edge additions, followed by biharmonic distance and current-flow centrality.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use biharmonic distance instead of effective resistance for clustering | Graph clustering algorithms · Synthetic and real-world clustering datasets | cluster purity | Helped |
| Use k-harmonic distance instead of spectral clustering | k-harmonic clustering algorithms · Synthetic and real-world clustering datasets | cluster purity | Mixed |
| Increase k above 2 (ablation) | k-harmonic clustering algorithms · Synthetic and real-world clustering datasets | cluster purity | Helped |
| Use effective resistance instead of biharmonic distance | Edge centrality measures · Nearest-neighbor graphs from Cancer, Wine, and Iris | resilience to graph perturbations | Helped |
| Use biharmonic distance or current-flow centrality instead of 5-harmonic distance | Edge centrality measures · Nearest-neighbor graphs from Cancer, Wine, and Iris | resilience to graph perturbations | Helped |
| Use 5-harmonic distance instead of other centrality measures (ablation) | Edge centrality measures · Nearest-neighbor graphs from Cancer, Wine, and Iris | Spearman rank correlation with current-flow centrality | Helped |
Surprising findings
- 5-harmonic distance was often almost perfectly correlated with current-flow centrality, which the theory does not explain.
- Best clustering results were often obtained at k>2 rather than at the biharmonic value k=2.
Limitations
- Theoretical results are mostly for edges; general vertex-pair biharmonic properties are open.
- Theory for k-harmonic distance does not generalize fully beyond k=2 and the best k is not known a priori.
- Experiments are limited to small UCI-based kNN graphs and synthetic block graphs.
Experimental setup
Datasets: Breast Cancer (UCI) Wine (UCI) Iris (UCI)
Benchmarks: Breast Cancer kNN graphs Wine kNN graphs Iris kNN graphs block stochastic graphs
Metrics: cluster purity Spearman rank correlation runtime
Baselines: Spectral Clustering Girvan-Newman Effective resistance k-means Current-flow centrality Betweenness centrality
Builds on: effective resistance Girvan-Newman algorithm spectral clustering Foster's theorem Cheeger's inequality
Closest papers by meaning
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.86)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.84)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.84)
- Graph Minimum Factor Distance and Its Application to Large-Scale Graph Data Clustering (ICML 2025 · similarity 0.83)
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges (ICML 2025 · similarity 0.83)
- Why the Metric Backbone Preserves Community Structure (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.