Research map / Graph learning / Graph algorithms and clustering
Graph embedding and spectral sparsification
Scale graph embeddings via coarsening and spectral sparsification.
126 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Graph algorithms and clustering, keyword cluster “search · directed · causal”
State History Benchmarks Tried Baselines Checklist Preprints Who Export
Where it stands
Quiet None of the tracked benchmarks has a report from 2025–26.
26 papers in 2023–24 and 21 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 13.3% to 10.4%.
No longer reported by papers here: PROTEINS (accuracy, last in 2024); ENZYMES (accuracy, last in 2023); Cora (accuracy (%), last in 2023); MUTAG (accuracy, last in 2024); Citeseer (accuracy (%), last in 2023); Pubmed (accuracy (%), last in 2023).
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity (NeurIPS 2016 · 187 citations)
- 2017 · Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (NeurIPS 2017 · 259 citations)
- 2018 · Watch Your Step: Learning Node Embeddings via Graph Attention (NeurIPS 2018 · 140 citations)
- 2019 · Wasserstein Weisfeiler-Lehman Graph Kernels (NeurIPS 2019 · 60 citations)
- 2020 · Scalable Probabilistic Matrix Factorization with Graph-Based Priors (AAAI 2020 · 26 citations)
- 2021 · Movie Summarization via Sparse Graph Construction (AAAI 2021 · 24 citations)
- 2022 · Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction (CVPR 2022 · 14 citations)
- 2023 · Network Regression with Graph Laplacians (NeurIPS 2023 · 6 citations)
- 2024 · Gaussian Processes on Cellular Complexes (ICML 2024 · 2 citations)
- 2025 · GeoMM: On Geodesic Perspective for Multi-modal Learning (CVPR 2025 · 2 citations)
- 2026 · Unfolded Laplacian Spectral Embedding: A Theoretically Grounded Approach to Dynamic Network Representation (ICML 2026 · 0 citations)
Earliest papers here
- Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity (NeurIPS 2016 · 187 citations)
- On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016 · 120 citations)
- The Multiscale Laplacian Graph Kernel (NeurIPS 2016 · 111 citations)
Benchmark records
The best number each year that beat every earlier one, among papers of this approach reporting their own method. Numbers are extracted by AI from each paper's text; check the paper before citing.
PROTEINS · accuracy (higher is better)
8 papers, 2016–2024 · not reported since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2016 | 76.4 | On Valid Optimal Assignment Kernels and Applications to Graph Classification (NeurIPS 2016 · 120 citations) |
| 2021 | 76.5 | Wasserstein Embedding for Graph Learning (ICLR 2021 · 4 citations) |
ENZYMES · accuracy (higher is better)
7 papers, 2016–2023 · not reported since 2023
| Year | Best so far | Set by |
|---|---|---|
| 2016 | 61.81 | The Multiscale Laplacian Graph Kernel (NeurIPS 2016 · 111 citations) |
| 2021 | 77 | Isolation Graph Kernel (AAAI 2021 · 7 citations) |
Cora · accuracy (%) (higher is better)
6 papers, 2016–2023 · not reported since 2023
| Year | Best so far | Set by |
|---|---|---|
| 2016 | 91.91 | Group and Graph Joint Sparsity for Linked Data Classification (AAAI 2016 · 4 citations) |
MUTAG · accuracy (higher is better)
6 papers, 2016–2024 · not reported since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2016 | 87.94 | The Multiscale Laplacian Graph Kernel (NeurIPS 2016 · 111 citations) |
Citeseer · accuracy (%) (higher is better)
5 papers, 2020–2023 · not reported since 2023
| Year | Best so far | Set by |
|---|---|---|
| 2020 | 71.1 | GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding (ICLR 2020 · 14 citations) |
| 2021 | 72.7 | Structure-Aware Random Fourier Kernel for Graphs (NeurIPS 2021 · 3 citations) |
| 2022 | 73 | From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers (ICML 2022 · 7 citations) |
Pubmed · accuracy (%) (higher is better)
5 papers, 2020–2023 · not reported since 2023
| Year | Best so far | Set by |
|---|---|---|
| 2020 | 77.8 | GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding (ICLR 2020 · 14 citations) |
| 2021 | 79.6 | Structure-Aware Random Fourier Kernel for Graphs (NeurIPS 2021 · 3 citations) |
What has been tried
110 papers here report 1,012 measured changes (a component added, removed or swapped, compared with a baseline): helped 65%, no clear effect 11%, hurt 17%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use 2 graph layers instead of 1 | COCO retrieval · Text retrieval R@1 | 75.1 -> 76.2 | Helped | GeoMM: On Geodesic Perspective for Multi-modal Learning (CVPR 2025 · 2 citations) |
| add edges connecting consecutive graphcode layers | Point cloud shape dataset · accuracy | 82.8±1.9 -> 86.9±1.4 | Helped | Graphcode: Learning from multiparameter persistent homology using graph neural networks (NeurIPS 2024 · 1 citation) |
| Set S = sD rather than S = sI | MNIST, 1 label/class · accuracy | 97.4 (0.1) -> 97.5 (0.1) | No clear effect | Continuous Partitioning for Graph-Based Semi-Supervised Learning (NeurIPS 2024 · 1 citation) |
| remove the covariance regularizer (β=0) | graph visualization · visualization quality | Hurt | WatE: A Wasserstein t-distributed Embedding Method for Information-enriched Graph Visualization (AAAI 2025 · 0 citations) | |
| Remove the geometry loss | Experiments reported in the paper · experimental results | No clear effect | Cover learning for large-scale topology representation (ICML 2025 · 0 citations) | |
| Add hinge loss to L2 | Cora · exact embedding dimension (D*) | 6 -> 7 | Hurt | How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · 0 citations) |
| Add the metric-distortion validation step after ORC candidate selection | Synthetic manifolds: 1D and 2D pruning benchmarks · good-edge removal (%) | ORC-ManL: 0.0±0.0; ORC Only: 10.9±0.1 to 18.1±0.3 | Helped | Recovering Manifold Structure Using Ollivier Ricci Curvature (ICLR 2025 · 0 citations) |
| double the number of communities | Cora and CiteSeer · accuracy | Cora: 0.49 ± 0.09 -> 0.56 ± 0.09; CiteSeer: 0.56 ± 0.06 -> 0.56 ± 0.05 | Helped | A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs (ICLR 2024 · 0 citations) |
| Add the optimal weighted self-loop | Semi-supervised CSBM · exact recovery probability | I(a_\tau,b_\tau, 0 )>1; I(a_\tau,b_\tau,c_\tau)>1 | Helped | Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks (ICML 2024 · 0 citations) |
| Use the minimal hierarchy-aware negative edge set E_H* instead of the full edge complement | MeSH 2020 · F1 | Helped | Learning Representations for Hierarchies with Minimal Support (NeurIPS 2024 · 0 citations) | |
| replace vanilla attention with curvature-aware attention | Wrinkle manifold, p-Laplacian diffusion · L2 relative error (%) | 8.47±2.82 -> 3.41±0.59 | Helped | Curvature-aware Graph Attention for PDEs on Manifolds (ICML 2025) |
| Vary the mixup graph size r | graph classification datasets · accuracy | ±3% | No clear effect | Graph Mixup on Approximate Gromov–Wasserstein Geodesics (ICML 2024) |
Baseline numbers that disagree
The same baseline on the same benchmark and metric, reported more than 5% apart by different papers here. Training budgets, data splits and reimplementations differ, so state which number you compare with.
| Baseline | Benchmark | Metric | Reported | Papers |
|---|---|---|---|---|
| WL | NCI1 | accuracy | 81.4 – 85.8 | 3 papers, e.g. NeurIPS 2018 and NeurIPS 2016 |
| WL | Proteins | accuracy | 71.4 – 75.6 | 2 papers, e.g. NeurIPS 2018 and NeurIPS 2016 |
What reviewers will expect
Datasets and baselines named in the 14 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- AIDS · 2 of 14 papers
- MNIST · 2 of 14 papers
Baselines
- UMAP · 3 of 14 papers
- Isomap · 2 of 14 papers
- LLE · 2 of 14 papers
- t-SNE · 2 of 14 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 47 papers; from OpenAlex and the papers' affiliations).
- University of Illinois, Urbana Champaign · 4 papers
- Technion - Israel Institute of Technology · 3 papers
- Google · 3 papers
- University of California, San Diego · 3 papers
- IBM · 2 papers
- University of Massachusetts Amherst · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Neural combinatorial optimization on graphs (159 papers)
- Graph comparison and random features (155 papers)
- Continuous DAG structure learning (102 papers)
- Graph distance and retrieval (79 papers)
Elsewhere in the topic
- Neural and local graph clustering (81 papers)
- Deep learning for graph matching (42 papers)
- Optimization algorithms for graph matching (42 papers)
- Anchor-based multi-view clustering (31 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).