The Generalized Skew Spectrum of Graphs

Armando Bellante, Martin Plávala, Alessandro Luongo · 2025

Read The Generalized Skew Spectrum of Graphs by Armando Bellante, Martin Plávala, Alessandro Luongo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23609.txt.

Introduction

Armando Bellante, Martin Plavala, and Alessandro Luongo proposed this 2025 family of graph fingerprints for machine learning. A fingerprint must ignore how a graph's nodes are labeled while keeping its structure. An older method, the Skew Spectrum, did this for plain graphs but could not handle labels, layers, or group links. The new family extends it on group theory and harmonic analysis.

The authors prove their fingerprints stay unchanged under relabeling. Settings within the family trade computing cost against richness of detail. Clever shortcuts raise richness at the same cost as the old method. Experiments show the gain in practice. The work serves analysts who compare complex networks, from molecules to social webs.

Catalog record

CREATORArmando Bellante, Martin Plávala, Alessandro Luongo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23609

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Generalized Skew Spectrum of Graphs Armando Bellante, Martin Plávala, Alessandro Luongo Abstract 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. (a) G1. (b) G2. (c) G3. (d) Embedding in \mathbb{R}^{2} . Figure 1 : Three graphs and a permutation-invariant embedding. 1 Introduction Graph-structured data is ubiquitous across domains, from molecular structures in chemistry ( Kosmala et al., 2023 ) to social networks in computational social science ( Nettleton, 2013 ) , or fraud detection in banking ( Pourhabibi et al., 2020 ) . However, developing adequate graphs representations remains a fundamental challenge in graph analysis ( Hamilton, 2020 ) . Traditional graph representations, such as adjacency matrices, are highly sensitive to the conventional node numbering used when acquiring the graph data. For instance, graphs G1 and G2 in Figure 1 are isomorphic, but their different node numbering would yield distinct adjacency matrices. Graph representations that are sensitive to initial node numbering make learning on graphs a harder task, similarly to how rotation- and translation-sensitive representations make learning on images challenging. This motivates the need for permutation-invariant graph embeddings , also known as graph invariants . A permutation-invariant embedding is a mapping that represents graphs as vectors while ensuring that isomorphic graphs are assigned the same vector. The expressivity , or completeness , of such an embedding is determined by its ability to distinguish non-isomorphic graphs. An embedding is complete if it maps all non-isomorphic graphs to different vectors. However, as of today, achieving both computational efficiency and completeness requires a trade-off, as determining wether two graphs are isomorphic is a paramount example of an NP-intermediate problem ( Babai, 2016 ) . Various approaches have been proposed to construct graph invariants, and the challenge has gained renewed importance with the rise of graph neural networks (GNNs) ( Scarselli et al., 2008 ) and their applications across scientific disciplines ( Corso et al., 2024 ) . Modern methods primarily rely on message-passing neural networks ( Gilmer et al., 2017 ) or spectral properties of the graph Laplacian ( Hammond et al., 2011 ) . While these approaches have achieved practical success, they often lack theoretical guarantees about their expressivity beyond the Weisfeiler-Lehman test ( Morris et al., 2019 ; Xu et al., 2019 ) or do not generalize naturally to richer graph structures like attributed graphs, multilayer graphs, and hypergraphs. This limitation becomes particularly crucial as such complex graph structures increasingly appear in real-world applications, from multi-omics biological networks to heterogeneous social networks. This leads us to investigate the following research questions: How can we construct permutation-invariant graph embeddings that (i) handle rich graph structures beyond simple graphs, (ii) are mathematically well-grounded, and (iii) offer practical computational efficiency? Furthermore, can we develop a theoretical framework that enables principled trade-offs between computational efficiency and completeness? Group theory offers a principled and complementary framework for constructing graph invariants with provable properties ( Bronstein et al., 2021 ; Dehmamy et al., 2021 ; Batatia et al., 2023 ) . A seminal contribution in this direction was the Skew Spectrum ( Kondor & Borgwardt, 2008 ) , which introduced a rigorous method for constructing graph invariants through functions on the symmetric group. While theoretically elegant, the original Skew Spectrum could not handle rich graph structures and offered no clear pathway to trade off between computational complexity and expressivity. Our work revisits and improves these older group-theoretic foundations to address modern challenges in graph representation, opening new research directions. In this work, we introduce a generalization of the Skew Spectrum. Our contributions are threefold: 1. Multi-Orbit Spectra : We develop a mathematically rigorous family of permutation-invariant graph embeddings that naturally extend to attributed graphs, multilayer graphs, and hypergraphs; 2. k -Correlation Spectra : We establish a theoretical framework that enables principled trade-offs between computational complexity and expressivity; 3. Doubly-Reduced k -Spectra : We introduce heuristics that preserve the generalizations and improve the expressivity of the Skew Spectrum without increasing its computational cost, bridging theory and practice. We illustrate our theoretical contributions with numerical experiments, demonstrating that our generalizations significantly improve the Skew Spectrum expressivity: distinguishing richer graphs, and distinguishing more non-isomorphic simple graphs at the same computational complexity. 2 Background Our work extends the seminal paper of Kondor & Borgwardt (2008) on the Skew Spectrum of graphs. In this section, we review the key concepts, laying the ground for our results. Notation. The symbol \bigoplus denotes a direct sum. For example, \bigoplus_{i=1}^{n}i denotes a diagonal matrix with entries 1,\dots,n along the diagonal. The symbol \bigotimes denotes a sequence of tensor products. For instance, \bigotimes_{i=1}^{2}v_{i}=v_{1}\otimes v_{2} . We use [n] to denote the set of integers \{1,\dots,n\} . Similarly, [a,b] refers to the set of integers between a and b , inclusive. 2.1 The Symmetric Group The symmetric group \mathbb{S}_{n} consists of all permutations of n elements. A permutation \sigma\in\mathbb{S}_{n} is a bijection of the indices of these elements, where \sigma(i) denotes the image of index i under \sigma . We use cycle notation, e.g., \sigma=(1,4,3) maps 1\rightarrow 4 , 4\rightarrow 3 , and 3\rightarrow 1 . For k<n , the subgroup \mathbb{S}_{k} a naturally embeds in \mathbb{S}_{n} , by acting on the first k indices while stabilizing the last n-k . This induces a natural partition of \mathbb{S}_{n} into right and left cosets, leading to the coset tranversals \mathbb{S}_{k}\backslash\mathbb{S}_{n} and \mathbb{S}_{n}/\mathbb{S}_{k} . These right (left) sets contain exactly one representative element per coset: a unique x\in\mathbb{S}_{k}\backslash\mathbb{S}_{n} ( y\in\mathbb{S}_{n}/\mathbb{S}_{k} ), such that any \sigma\in\mathbb{S}_{n} can be decomposed as \sigma=h_{1}x ( \sigma=yh_{2} ) for some h_{1}\in\mathbb{S}_{k} ( h_{2}\in\mathbb{S}_{k} ). This definition extends to double-coset transversals \mathbb{S}_{k}\backslash\mathbb{S}_{n}/\mathbb{S}_{k} , where any \sigma\in\mathbb{S}_{n} can be written as \sigma=h_{3}zh_{4} for a unique z\in\mathbb{S}_{k}\backslash\mathbb{S}_{n}/\mathbb{S}_{k} and h_{3},h_{4}\in\mathbb{S}_{k} . For example, \mathbb{S}_{n-2}\backslash\mathbb{S}_{n}/\mathbb{S}_{n-2} consists of the following 7 group elements: \{(),(n-1,n),(n-2,n-1),(n-2,n),(n-2,n-1,n),(n-2,n,n-1),(n-3,n-1)(n-2,n)\} . We denote irreducible representations (irreps) of \mathbb{S}_{n} by \rho . These are mappings from group elements to unitary matrices, and can be labeled by partitions of n . Specifically, we use the Young Orthogonal Representation (YOR), which has real-valued entries. The set of YORs is denoted by \mathrm{Irr}(\mathbb{S}_{n}) , and we define \Lambda_{n} as the subset of four irreps indexed by the partitions (n),(n-1,1),(n-2,2),(n-2,1,1) . We refer the interested reader to Appendix A and the background sections (2.6 and 2.7) of Bellante (2024) for more. 2.2 Graph isomorphism and functions on \mathbb{S}_{n} The adjacency matrix A of a graph encodes its structure, with A_{i,j} specifying the relationship between nodes i and j . The construction of A inherently depends on the node numbering, and since graphs are often labeled arbitrarily, the same structure can be

Read the complete text