# The Generalized Skew Spectrum of Graphs

arXiv: https://arxiv.org/abs/2505.23609 · HTML: https://mlsanity.com/paper/2505.23609/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 9 of 9)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Automatic Symmetry Discovery with Lie Algebra Convolutional Network](https://mlsanity.com/paper/2109.07103/) (2021)
- [Hierarchical Graph Pooling with Structure Learning](https://mlsanity.com/paper/1911.05954/) (2019)
- [Ewald-based Long-Range Message Passing for Molecular Graphs](https://mlsanity.com/paper/2303.04791/) (2023)
- [From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks](https://mlsanity.com/paper/2305.04963/) (2023)
- [A General Framework for Equivariant Neural Networks on Reductive Lie Groups](https://mlsanity.com/paper/2306.00091/) (2023)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)

## Abstract (arXiv)

This paper proposes a family of permutation-invariant graph embeddings, generalizing the Skew Spectrum of graphs of Kondor & Borgwardt (2008). Grounded in group theory and harmonic analysis, our method introduces a new class of graph invariants that are isomorphism-invariant and capable of embedding richer graph structures - including attributed graphs, multilayer graphs, and hypergraphs - which the Skew Spectrum could not handle. Our generalization further defines a family of functions that enables a trade-off between computational complexity and expressivity. By applying generalization-preserving heuristics to this family, we improve the Skew Spectrum's expressivity at the same computational cost. We formally prove the invariance of our generalization, demonstrate its improved expressiveness through experiments, and discuss its efficient computation.