Research map / Graph learning / GNN architectures
Graph Persistence goes Spectral
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 SpectRe, a persistent-homology descriptor that adds graph Laplacian spectra to RePHINE diagrams, proving it is strictly more expressive than RePHINE and the Laplacian spectrum, introducing bottleneck-type metrics, and showing SpectRe is locally (not globally) stable.
Problem
Existing color-based persistent homology descriptors for graphs (PH, RePHINE) cannot separate simple non-isomorphic graphs, e.g., monochromatic ones, and lack a suitable stability theory.
Approach
Augment each RePHINE persistence tuple with the non-zero Laplacian eigenvalues of the connected component at its death (vertices) or birth (cycles), giving a descriptor strictly more expressive than both RePHINE and the Laplacian spectrum; define bottleneck-type metrics and prove global stability for RePHINE and local stability for SpectRe.
Key results
- SpectRe separates all minimal Cayley graphs (accuracy 1.00 on c-12 to c-63), while RePHINE reaches at most 0.95.
- On BREC, SpectRe reaches 1.00 on Basic, Regular and Extension subsets and 0.54 overall versus 0.41 for RePHINE.
- With GCN on real data, SpectRe achieves the best mean accuracy on 8 of 9 datasets, e.g., MUTAG 91.2 vs 87.7 for RePHINE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · Cayley graphs c-12 through c-63 | accuracy: RePHINE: 0.95, 0.83, 0.61, 0.86, 0.76, 0.84, 0.78, 0.73 -> SpectRe: 1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00, 1.00 | Helped |
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · BREC E (100) | accuracy: 0.55 -> 1.00 | Helped |
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · BREC All (400) | accuracy: 0.41 -> 0.54 | Helped |
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · BREC C (100) | accuracy: 0.03 -> 0.04 | Helped |
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · BREC D (20) | accuracy: 0.00 -> 0.05 | Helped |
| Add evolving graph-Laplacian spectra to RePHINE to form SpectRe | RePHINE · BREC B (60), R (50), E (100), C (100), D (20), and All (400) | accuracy: 0.98 -> 1.00; 0.94 -> 1.00; 0.55 -> 1.00; 0.03 -> 0.04; 0.00 -> 0.05; 0.41 -> 0.54 | Helped |
| Add SpectRe diagrams to GCN | GCN · MUTAG | accuracy: GCN: 63.2{\color{gray} $\pm$4.7}; RePHINE: 87.7{\color{gray} $\pm$3.0}; SpectRe: 91.2{\color{gray} $\pm$3.0} | Helped |
| Replace RePHINE diagrams with SpectRe diagrams | GCN · PTC-MM | accuracy: 57.8{\color{gray} $\pm$1.6} -> 61.7{\color{gray} $\pm$2.9} | Helped |
| Replace RePHINE diagrams with SpectRe diagrams | GCN · PTC-MR | accuracy: 58.1{\color{gray} $\pm$11.9} -> 59.1{\color{gray} $\pm$5.9} | Mixed |
| Replace RePHINE diagrams with SpectRe diagrams | GCN · PTC-FR | accuracy: 68.5{\color{gray} $\pm$6.4} -> 69.4{\color{gray} $\pm$2.8} | Mixed |
| Replace RePHINE diagrams with SpectRe diagrams | GCN · NCI1 | accuracy: 80.66{\color{gray} $\pm$1.55} -> 80.90{\color{gray} $\pm$0.17} | Mixed |
| Replace RePHINE diagrams with SpectRe diagrams | GCN · NCI109 | accuracy: 76.51{\color{gray} $\pm$1.03} -> 76.63{\color{gray} $\pm$0.86} | Mixed |
Surprising findings
- SpectRe is not globally stable even under injectivity assumptions; only local stability holds.
Limitations
- Eigendecomposition overhead is non-negligible and can bottleneck large datasets.
- Only color-based (degree and curvature) filtrations studied; Vietoris-Rips and biparameter filtrations left open.
- SpectRe is not globally stable; only local stability under injectivity holds.
Experimental setup
Datasets: Minimal Cayley graphs BREC MUTAG PTC-MM PTC-MR PTC-FR NCI1 NCI109 IMDB-B ZINC MOLHIV
Benchmarks: Minimal Cayley graphs BREC MUTAG PTC-MM PTC-MR PTC-FR NCI1 NCI109 IMDB-B ZINC MOLHIV
Metrics: accuracy MAE AUROC
Baselines: PH^0 PH^1 RePHINE Laplacian spectrum GCN
Builds on: RePHINE persistent homology on graphs DeepSets GCN
Closest papers by meaning
- On topological descriptors for graph products (NeurIPS 2025 · similarity 0.90)
- Boosting Graph Pooling with Persistent Homology (NeurIPS 2024 · similarity 0.88)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.88)
- TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration (ICML 2025 · similarity 0.87)
- TopoGCL: Topological Graph Contrastive Learning (AAAI 2024 · similarity 0.87)
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.