The Generalized Skew Spectrum of Graphs
This work addresses the need for more expressive graph embeddings in machine learning, though it is incremental as it builds directly on prior work.
The paper tackles the problem of embedding complex graph structures like attributed, multilayer, and hypergraphs by generalizing the Skew Spectrum, resulting in improved expressivity at the same computational cost as the original method.
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.