The Generalized Skew Spectrum of Graphs

This paper proposes a family of permutationinvariant 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 isomorphisminvariant 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 tradeoff 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.