Research map / Graph learning / GNN architectures
The Generalized Skew Spectrum of Graphs
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 a generalized Skew Spectrum for graphs (multi-orbit, k-correlation, and doubly-reduced k-spectra) that is permutation-invariant and handles attributed, multilayer, and hypergraph structures, with complexity bounds and small experiments on synthetic graphs, QM7, and graph atlases.
Problem
Permutation-invariant graph embeddings (graph invariants) that are complete, handle richer structures such as attributed, multilayer graphs and hypergraphs, and remain computationally efficient; the original Skew Spectrum cannot handle these and lacks a complexity-expressivity trade-off.
Approach
Generalizes the Skew Spectrum by replacing scalar functions on S_n with vector-valued (multi-orbit) functions combining tensor products, and by defining k-correlations and their Fourier transforms (k-Spectra), then makes them tractable via reduction to four irreps and a double reduction over double-coset representatives with dynamic-programming precomputation.
Key results
- On a synthetic 4-family dataset, a random forest reaches 100% accuracy with the 2-Orbit Skew Spectrum versus 50% with the concatenated single-orbit spectra.
- On QM7 atomization energy, XGB with the 2-Orbit Skew Spectrum achieves MAE 18.28 versus 29.15 for the single-orbit representation.
- For n=7 graphs, the concatenated doubly-reduced k-spectra yield no collisions among non-isomorphic graphs, while 1-WL does not.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine adjacency and node-label orbits in a 2-Orbit Skew Spectrum instead of concatenating separate single-orbit spectra | Random Forest classification of synthetic graph families · Synthetic graph families | accuracy: 50% -> 100% | Helped |
| combine off-diagonal and diagonal information in a 2-Orbit Skew Spectrum instead of using the off-diagonal Single-Orbit spectrum | QM7 atomization energy regression · QM7 | MAE: 29.15 -> 18.28 | Helped |
| increase the correlation order k beyond k=3 | Doubly-Reduced k-Spectra · Graph Atlas, 7 nodes | non-isomorphic graph collisions | Helped |
| concatenate k-Spectra across k | Doubly-Reduced k-Spectra · Graph Atlas, 7 nodes | non-isomorphic graph collisions | Helped |
| use concatenated k-Spectra instead of 1-WL | Graph invariant comparison · Graph Atlas, 7 nodes | non-isomorphic graph collisions | Helped |
| use concatenated k-Spectra instead of 1-WL | Graph invariant comparison · Connected chordal graphs, 8 nodes | non-isomorphic graph collisions | Hurt |
Surprising findings
- On QM9 and ZINC, Laplacian eigenvalues achieved the best accuracy, outperforming the multi-orbit spectrum in the rebuttal experiments.
- On chordal graphs with n=8, 1-WL yields fewer collisions than the concatenated k-spectra, so the two are complementary rather than ordered.
Limitations
- Completeness for finite k is only conjectured; the k_max question is open.
- Hypergraph extension beyond small arity is left as future work; the paper provides only a proof-of-concept implementation.
- Experiments are small-scale and preliminary; no open-source implementation with thorough benchmarking is released.
Experimental setup
Datasets: synthetic labeled directed weighted graph families (15A, 15B, 6A, 6B) QM7 QM9 ZINC Graph Atlas 7-node graphs connected chordal graphs with 8 nodes
Benchmarks: QM7 QM9 ZINC Graph Atlas (7 nodes) chordal graphs (8 nodes)
Metrics: classification accuracy mean absolute error number of collisions among non-isomorphic graphs
Baselines: Single-Orbit Skew Spectrum Laplacian eigenvalues adjacency eigenvalues 1-WL Coulomb matrix eigenvalues
Builds on: Skew Spectrum (Kondor & Borgwardt, 2008) reduced Skew Spectrum (Kondor & Borgwardt) Young Orthogonal Representation
Closest papers by meaning
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · similarity 0.87)
- REVISITING MULTI-PERMUTATION EQUIVARIANCE THROUGH THE LENS OF IRREDUCIBLE REPRESENTATIONS (ICLR 2025 · similarity 0.85)
- Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (NeurIPS 2025 · similarity 0.85)
- Schur Nets: exploiting local structure for equivariance in higher order graph neural networks (NeurIPS 2024 · similarity 0.85)
- Learning Representations for Hierarchies with Minimal Support (NeurIPS 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.