Research map / Learning theory and algorithms / Clustering
Graph Minimum Factor Distance and Its Application to Large-Scale Graph Data 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.
Proposes MMFD (and low-rank, clustering, and MFD variants), a closed-form pseudo-metric between graphs that treats adjacency matrices as indefinite kernel matrices over discrete distributions, enabling fast large-scale graph clustering.
Problem
Comparing graphs (distance or similarity) is fundamental for graph classification and clustering but remains costly and hard to scale to large graph datasets, especially with indefinite adjacency matrices.
Approach
Treat adjacency matrices as kernel matrices of an unknown indefinite kernel on two discrete distributions, make them PSD via absolute eigenvalues, and compare mean embeddings after optimal orthogonal alignment; this yields a closed-form distance (MMFD), a low-rank variant, and a 1-D K-means clustering reducing cost to linear in number of graphs. MFD generalizes to nonlinear kernels with an iterati
Key results
- On AIDS, MMFD and MFD reach 98.80% and 99.45% clustering ACC versus 96.77% for the best baseline DCGLC.
- On PROTEINS, MFD reaches 72.60% ACC and 14.18 NMI; on REDDIT-MULTI-5K, MMFD reaches 35.97% ACC versus 33.24% for DCGLC.
- MMFDLR computes distances on AIDS in 0.26 s versus 25544.26 s for entropic GWD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MFD instead of the strongest listed baseline | Graph clustering · AIDS | ACC: 96.77±0.33 -> 99.45±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · AIDS | NMI: 76.01±15.23 -> 93.82±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · AIDS | ARI: 85.74±1.45 -> 97.47±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · PROTEINS | ACC: 68.89±2.04 -> 72.60±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · PROTEINS | NMI: 12.42±0.00 -> 14.18±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · PROTEINS | ARI: 14.32±2.88 -> 19.67±0.00 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · ENZYMES | ACC: 28.55±0.20 -> 30.33±1.16 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · ENZYMES | NMI: 6.57±0.20 -> 8.45±0.26 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · ENZYMES | ARI: 3.78±0.47 -> 4.42±0.33 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · REDDIT-MULTI-5K | ACC: 33.24±2.34 -> 35.35±0.01 | Helped |
| Use MFD instead of the strongest listed baseline | Graph clustering · REDDIT-MULTI-5K | NMI: 17.68±0.17 -> 17.28±0.03 | Hurt |
| Use MFD instead of the strongest listed baseline | Graph clustering · REDDIT-MULTI-5K | ARI: 11.20±0.84 -> 14.90±0.02 | Helped |
Surprising findings
- MMD on the same features performs poorly (e.g., 50.10% ACC on AIDS), showing that alignment via orthogonal matrices is essential.
Limitations
- MFD has no closed-form solution and higher computational cost than MMFD.
- MMFD(G1,G2)=0 does not guarantee graph identity (e.g., any two complete graphs give zero distance).
- The MFD variant in Appendix A.3 was not evaluated numerically due to cost.
Experimental setup
Datasets: AIDS PROTEINS ENZYMES REDDIT-MULTI-5K
Benchmarks: AIDS PROTEINS ENZYMES REDDIT-MULTI-5K
Metrics: ACC NMI ARI running time
Baselines: SP kernel GK kernel RW kernel WL kernel LT kernel WL-OA kernel InfoGraph GraphCL JOAO GWF GLCC DCGLC
Builds on: maximum mean discrepancy Gromov-Wasserstein distance randomized SVD Weisfeiler-Lehman subtree kernel
Closest papers by meaning
- MMD Graph Kernel: Effective Metric Learning for Graphs via Maximum Mean Discrepancy (ICLR 2024 · similarity 0.88)
- Graphon based Clustering and Testing of Networks: Algorithms and Theory (ICLR 2022 · similarity 0.88)
- Fast Approximation of Similarity Graphs with Kernel Density Estimation (NeurIPS 2023 · similarity 0.87)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.85)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.85)
- Local Graph Clustering with Noisy Labels (ICLR 2024 · similarity 0.85)
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.