The Generalized Skew Spectrum of Graphs
Authors: Armando Bellante
Martin Plávala
Alessandro Luongo
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning
ICML
graph representation
invariant
permutation
generalized skew spectrum
embedding
group theory
representation theory
fourier transform
finite groups
permutation group
Primary area: general_machine_learning->representation_learning
TL;DR: Generalizing a group-theoretical, permutation-invariant embedding for graphs to handle richer data structures and enhance expressivity.

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.

The Generalized Skew Spectrum of Graphs
Armando Bellante 123
Martin Plávala Alessandro Luongo
Abstract
This paper proposes a family of permutation- invariant graph embeddings, generalizing the Skew Spectrum of graphs of Koondor & Borg. wardt (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 Spec- trum could not handle. Our generalization further defines family of functions that enables a trade- off between computational complexity and ex- pressivity. By applying heuristics to this family, we improve the Skew Spectrum's 's expressivity tional cost. We formally prove the invariance of our generalization, demonstrate its improved expressiveness through experiments, and discuss its efficient computation.
(a) GI.
(b) G2.
G3
G1. G2
(c) G3.
(d) Embedding IR?.
the same computa-
Figure I. Three graphs and permutation invvariant embedding.
such as adjacency matrices, are highly sensitive to the con- ventional node numbering used when acquiring the graph data. For instance, graphs G1 and G2 in [ isomor- phic, 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-sensiiie rep- resentations make learning motivates the need for permutation germutation-iivaiian invariant graph embed- dings, also known as graph invariants.
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 (Net-
images challenging. This
tleton 2013), or fraud detection in banking (Pourhabibi
al.] 2020). However, developing adequate graphs repre-
A permutation-invariie embedding a mapping that rep- resents graphs as vectors while ensuring that isomorphic graphs are assigned the same vector. The expressivity, completeness, of such embedding 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 deter- mining wether two graphs are isomorphic is a paramount example of NP-intermediate problem (Babai 2016).
sentations remains fundamental challenge in graph anal- [Hamilton] 2020). Traditional graph representations,
ysis
Laxx-PPaack-Insttteee für Quantenoptik, Hans- Konns--offrmann- 1. 85748 Garching. Germany 'Munich Center for Quantum Sci- ence and Technology (MCQST), Schellingstr. 4, 80799 München, Germany Dipartimento di Elettronica, Informazione Bioingeg- neria, Politecnico Milano, Milan, Italy "Institute of Thcoretical Physics, Leibiniz Universität Hannover, Appelstraße 2, 30167 Hannover, Germany NNaurwissenschaftichh hatrseenssccatiiccccceechhhhhh Fakultät, Universität Siegen. Siegen, Germany 'Centre for Quantum Tech- nologies, National University of Singapore, Singapore Inveriant Pte. Ltd., Singapore. Correspondence Armando Bellante <ar- mando.bellante polimi.it>.
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 disci- plines (Corso et al. 2024). Modern methods primarily rely on message-passinn neural networks (Gilmer et al. 2017
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Generalized Skew Spectrum of Graphs
or spectral properties of the graph Laplacian (Hammond
2. Background
et al. 2011]. While these approaches have achieved prac- tical success, they often lack theoretical guarantees about their expressivity beyond the Weisfeiler-Lemman test (Mor- ris 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 particu- larly crucial as such complex graph structures increasingly appear in real-world applications, from multi-omics biologi- cal networks to heterogeneous social networks.
Our work extends the seminal paper of Kondor & Borgwardi 2008) on the Skew Spectrum of graphs. In this section, we review the key concepts, laying the ground for our results.
Notation. The symbol + denotes a direct sum. For exam- plc, Di=1 denotes a diagonal matrix with entries I,..., along the diagonal. The symbol X denotes sequence of tensor products. For instance, 8 ;-=1% 2/ 11 @ U2- We use [n] to denote the set of integers {_..... ,n). Similarly, [a, 6] refers to the set of integers between a and b, inclusive.
This leads us to investigate the following research questions:
How can we consiruct commulation-nnvariinn graph embeddings that (i) handle rich graph struc- tures beyond simple graphs, (ii) are mathemati- cally well- well-grounded, and (íã) offer practical com- putational efficiency?
2.1. The Symmetric Group
The symmetric group S, consists of all permutations of elements. A permutation a E S, is bijection of the indices of these elements, where (i) denotes the image of index under a. We use cycle notation, e.g., o = (1,4,3) maps - 4, 4 -> 3, and - 1. For k < n, the subgroup Sy a naturally embeds in S,, by acting on the first k: indices while stabilizing the last
Furthermore, can we develop a theoretical frame- work that enables principled trade-offs between computational efficiency and completeness?
k. This induces natural partition of Sn into right and left cosets, leading to the coset tranversals Se AS, and Sp/Sa.. These right (left) sets contain exactly one representative element per coset: a unique x E &S (Sn (y E S,/Ss),, such that any a E S,, can be decomposed as a = h1 (a = yh2) for some hn E Sy (h2 E &s2). This definition extends double-coset transversals Sy /S, where any a S, can be written as
Group theory offers a principled and complementary frame- work for constructing graph invariants with provable proper- ties (Bronstein et al., 2021 Dehmamy et al., 202T: Batatia cet al., (023). A seminal contribution in this direction was the Skew Spectrum (Kondor & Borgwardi 2008), which introduced rigorous method for constructing graph in- variants through functions on the symmetric group. While theoretically elegant, the original Skew Spectrum could not handle rich graph structures and offered no clear path- way 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.
h32h4 for unique 2 E Sy S,/S and h3, h4 E Sy.- For example, Sn-2\Sn/ Sn/Snn2 consists of the following 7 group elements: {() (n - 1,m), (n - 2, n - 1), (n - 2, n). (n 2, n 1, 1,n), (n- 2, n,n - 1), (n - 3, 100-1)11 1)(n 2, n))-
We denote irreducible representations (irreps) of S,, by p. These are mappings from group elements to unitary matri- ces, 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 Trr(S,,), and we define A,, as the subset of four irreps indexed by the partitions (n2), (n - 1, 1), (n 2, 2), (n - 1,
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 cormutation-invariant graph embed- dings that naturally extend to attributed graphs, multi- layer graphs, and hypergraphs;
We refer the interested reader to Appendix and the back- ground sections (2.6 and 2.7) of Bellante (2024) for more.
2. k- d-Correlation Spectra: We establish a theoretical framework that enables principled trade-offs between computational complexity and expressivity;
2.2. Graph isomorphism and functions on S,
3. Doubly-Reduced k-Spectra: We introduce heuristics that preserve the generalizations and improve the ex- pressivity of the Skew Spectrum without increasing its computational cost, bridging theory and practice.
The adjacency matrix A of a graph encodes its structure, with A specifying the relationship between nodes and j. The construction of A inherently depends the node numbering, and since graphs are often labeled arbitrarily, the same structure can be represented by multiple distinct adjacency matrices, complicating graph comparison tasks.
We illustrate our theoretical contributions with numerical experiments, demonstrating that our generalizations signifi- cantly improve the Skew Spectrum expressivity: distinguish- ing richer graphs, and distinguishing more non non- -oomisomocppic simple graphs at the same computational complexity.
Graph isomorphism is the problem of determining whether two graphs G1 and G2 have the same structure despite
2

---

The Generalized Skew Spectrum of Graphs
2.00
A key factor in this reduction is the projection TS., a (p). which maps p onto the trivial irrep of Sa This projec- tion induces sparsity structure in the Fourier transform, enabling efficient computation. This sparsity also plays critical role the efficient computation of the graph invari- ants. We formalize this sparsity the following lemma.
1.50
13
B
1.5
0.3
0.8
Lemma 2.1 (Fourier sparsity). Let f Sa/Sn-2 - Its Fourier transform using YOR is collection of sparse square matrices indexed by specific partitions of n. The sparsity pattern is independent of f:
(a) Adjacency ma- (b) Function f(g) gg(n),((n11)) 1y- is rep- resented vector where 9i g(i).
trix.
Figure 2. A weighted, directed graph a function on S4.
1. (n); size 1, one scalar entry.
2. (n - 1)); size n 2 non-zero columns.
differences in node numbering. Formally, for adjacency matrices (1) and ( G1 G1 and G2 are isomorphic if there S,, such that A A (2) Here, reorders the node indices of G2 to align with GI, preserving the edge relationships.
3. (n 2): size n(n-3) non-zero columns.
(n (n- (1-1))n2), 1 non-zero columns.
4. (n 2, 1, 1); size
exists permutation
2
We use An to denote this set of partitions.
For a detailed discussion on TBn-2 and its connection the sparsity pattern, Appendix B
To encode adjacency information in a manner that reflects this relationship, we define a function f Sn +
f(g) Ag(n)) for all g E Sn.
2.4. The Skew Spectrum of Graphs
Kondor & Borgwardi (2008) introduced a translation- invariant function Sn the spectrum (the Fourier trans- form) of triple correlation function, which they termed the Skew Spectrum.
This encoding captures information about node adjacency while naturally reflecting the action of permutations on node indices. Indeed, using this formalism, two graphs are iso- morphic if and only their corresponding functions satisfy:
Definition 2.2 (Skew Spectrum). Let f Sn + C. An entry of the Skew Spectrum defined as
3 s.t. (() (og) for all g E Sn.
(2)
In other words, graph isomorphism reduces to verifying whether two functions are related by translation E S.. The Skew Spectrum leverages this formulation to construct graph invariants through translation-invart Sn. using correlation functions and their Fourier transforms.
S)(01, = Σ f(g) S
p(T) p(z)).
(4)
GES,
E2
functions on
A Skew Spectrum entry is a (sparse) matrix. The Skew Spectrum is uniquely determined by a small subset of entries specifically, it indexed by 7 group elements (Sn-2\S,, /s//nn2) and irreps (A,). Moreover, (4) can be expressed as S1(11, 1 p) = p)) f(p), where f(gi.)) f())( p(ō) is the Fourier transform of another Ejes. [... function r(g,, .). This decomposition, Fourier transforms, and sparsity are key efficient computation.
To conclude, note that graph functions [ are sparse: they depend only on the image of the last indices under g (g(n- 1) and (n)). More formally, f(oh) fa) for all h E Sn Thus, f is supported on the coset transversal / As shown in Fig. 2 this sparsity implies that f takes distinct values on at most n elements, rather than n!.
2.3. Fourier transform on Sn
The Skew Spectrum has up to 85 non-zero sealar values (features) across all the entries, and they can be computed in On²²) operations. To improve efficiency, the authors proposed a way to trade expressivity for computational cost, introducing a reduced invariant.
The Fourier transform of a function over S, is defined as
1 Σ f(g)p(g)
(p)
(3)
Definition 2.3 (Reduced Skew Spectrum). Let f S,, C. An entry of the reduced Skew Spectrum is defined as
where p is an irreducible representation of S
Standard FFT algorithms require (mlloolyoog(n!) opera- tions to evaluate fp) for all irreps (Masien 1998). How- ever, for graph-derived functions, taking values on S /S,-1
(G))) S 2
Sy p)
p(0) TB,, (()2))
JES
the complexity reduces to (n)3) ) (or even (n))) opera- tions (Kondor & Borgwardt 2008 Clausen Hühne 2017).
G26S.
where projects & onto the trivial representation of S,
3

---

The Generalized Skew Spectrum of Graphs
This projection reduces the domain of r(g1, a) to Sn/S,,2 ensuring the same sparsity pattern as in f()) and further simplifying the computation. The reduced Skew Spectrum's efficiency is summarized in the following result.
then replaced by the tensor product.
Definition 3.1 (Multi- Orbii Skew Spectrum). Let f S, + C4. A Multi-Orbit Skew Spectrum entry is defined as
( 60 [úg 6 [(22)
Py
Theorem 2.4 (Reduced Skew Spectrum computation). Let f :.S//nn- + C. We can compute its reduced Skew Spectrum in Onn²) operations. The reduced Skew Spectrum has up to 49 non-zero entries.
Sm 1
ges
92
Expanding the direct sums in fg), we obtain:
The reduced Skew Spectrum is the key contribution of Kon dor & Borgwardr (2008), validated experimentally effective and efficient tool for representing graphs. In the next sections, we will present our generalization.
Sy(91,0) = θ
(9 fc, (6)
(a)
where (2 p) = Eges. Sn (r, (09.)
p(ğ). This for- mulation introduces terms ( for i j. which capture correlations between orbits and enhance the spec- trum's ability distinguish between graphs. Our intuition comes from a quantum theory perspective, where these terms can be viewed as interference terms. In quantum theory interference terms capture superposition-relate phe- nomena where the whole can be greater than sum of the parts. Similarly, the Multi-Orbit Skew Spectrum is more expressive than the concatenation of individual spectra.
[S..
3. Richer graph structures and multiple orbits
While the Skew Spectrum is a powerful invariant for weighted and directed graphs, it does not fully capture richer graph structures such as graphs with node edge features, multilayer graphs, or hypergraphs. To address these limi- tations, we introduce the Multi-Orbit Skew Spectrum, en- abling the analysis of these complex structures.
Richer graph structures are typically represented by a col- lection of data structures (e-g., adjacency matrices, node fea- ture vectors, etc.) indexed by the graph nodes. Under node renumbering, the elements within these structures permute independently without mixing (e.g., node features remain distinct from edge weights). These distinct subsets of data are referred to as orbits, and two such graph structures are isomorphic if there exists a single permutation that aligns all their orbits.
We formally prove the invariance of the Multi-Orbit Skew Spectrum in Section 4 where it emerges special case of the broader framework we propose. Its reduced version is akin to the one of the original Skew Spectrum: each term of the direct sum in (6) is computed as a reduced Skew Spectrum (Def. 2.3 Its computation is detailed in Section and has the following complexity.
Theorem 3.2 (Reduced Multi-Orbit Skew Spectrum). Let f Sn/SSn2 + C². Computing its reduced Mubti Skew Spectrum takes OdP + ddn²) operations. The resulting embedding has up to 49d non-zero entries.
To illustrate, consider graphs G1 and G2 in Figure Treat- ing node numbers as labels, the two graphs are not isomor- phic; e.g., node 5 has high degree in G1 but lower degree in G2. For isomorphism, both the adjacency matrix and the node labels must align under the same permutation.
In the remainder of this section, we demonstrate how to construct Multi-Orbit functions for various graph structures. These examples illustrate the spectrum's 's versatility in cap- turing complex data representations.
natural extension of the invariant is to define separate func- tions for each orbit (e.g., one for the adjacency matrix and one for node labels) and concatenate their respective Skew Spectra. However, this approach fails to account for correla- tions between orbits. For example, the individual spectra of G1 and G2 would coincide, even though the permutations linking the adjacency matrix and node labels differ. This information loss limits the invariant's completeness.
Self-loops. Graphs with self-loops naturally split into two orbits: diagonal and off-diagonal entries, which do not mix under permutations. Define fi Ao(n), for off- diagonal entries and f2 (o(n),,(x)) for diagonal entries.
Node features. If each node has a vector x; of p features, the Multi-Orbit function f spans d = p + orbits. Specifi- cally, fe(a) = Ts)o(n) for E [p] capturing the features, and fa(o) ((e)) encoding the adjacency.
To overcome this, we replace scalar functions with vector- valued functions, enabling unified representation of multiple orbits. Specifically, we define a function f S, /, + Cd as the direct sum of single-orbit functions:
Edge features. When each edge has up to d features, the graph can be represented as a tensor A E Cdxuxa where A encodes the hth feature of the edge between nodes i and j. The function fa(a) = (x)(()))((n1)) captures these features, with the number of orbits scaling with the features.
f(g) = + fi(g)
(5)
EE[4
The pointwise product required for the Skew Spectrum is

---

The Generalized Skew Spectrum of Graphs
Multilayer graphs. Graphs with multiple edge layers, each representing distinct relationships (e.g., friendship or work connections in social networks), can be represented using separate adjacency matrices. For layer i, define fi(o)= = (n-1)- where indexes the layers.
Here I = (f1,..., ik) E [d] is list of indices, and
fi. (9) I fú, (991)
(!0) (G)-2:P) =
Σ BES
p(.). (9)
Sm
The invariance of the k-Spectrum follows directly from the one the k-correlation functions, holding for both the Skew Spectrum (k- = 3) and our Multi-Orbit extension.
Hypergraphs. In hypergraphs, edges connect multiple nodes. A simple representation uses A Cd with rows corresponds edges and fi(or) Ai,((n) specifies node- edge relationships. Although f is defined over S./Sn,1,, potentially reducing the computation, the number of orbits matches the number of edges, which can be large.
Theorem 4.3 (Invariance). Let f1. Sn - C² be equiva- lent to up left-translation, such that fi(o) f2(3a) for some fixed σ E Sn and every a E Sn. Then, the Orbii k-Spectra of fi and f2 are identical. In other words, for each Gk-2 E (8,)²=3, E IIr(Sn), we have ((K)
Alternatively, for hypergraphs with edges connecting up to q nodes, an adjacency tensor Afa.... can encode whether an edge exists between nodes ; A fictitious node + 1 handles edges with fewer than nodes. This defines f(r) on on /n/Sn-q While beyond the scope of this paper, Clausen & Hühne (0177) provide efficient Fourier transforms on S,,/S,, which could be used to extend our invariant.
5(k) 5(1) (Gx-2.P) f1 (G)-2: S
iq.
Proef. Because of the bijection, we show the translation invariance of k-correlations. By substituting g ag.
we obtain 5/111 (Gx-1) Ejes. (2(3g) X f2(F89))
Ege Sala') 1 fa(d'
f2 (G=-1).
(k)
Sm
4. Spectra of higher correlations
Intuition. There are reasons believe that computing higher correlations will increase the expressivity of the invariant. First, k-correlations are group-invariant poly- nomials of f of order k. The Seiie-Weissss theorem (Stone 1948) tell us that polynomials are dense in con- tinuous functions. Thus one can hope that the set of all k-correlations for arbitrary high k will span a dense sub- set of the space of all invariants. In other words, one can hope that if complete invariant exist, then it can be ar- bitrary well approximated by the k-correlations. Indeed, Adler & Konheim (1962) observed that correlation func- tions for k = 1, form a complete translation invari- ant for realevalued, Haar-integrable functions on locally compact abelian groups. While (Chazan & Weiss 1970) showed that in that general case the invariants are com- plete only for an infinite k. Kakarala (1992) references and shows settings for which 3-correlations plete. We conjecture that, for any finite n, there exists finite kinax for which the collection of k-correlations, for all k: < kmax. forms a complete translation invariant for func- tions on S,,/Sn-2. In Section 4.1 we provide arguments to believe that kmax E O
The Skew Spectrum and our Multi-Orbit generalization are Fourier transforms over the last function entry of triple correlation s (01, .2) Eees, (())(((r)((ãa))
[5.]]
In signal analysis, is well-known that correlation functions constitute translation invariants, because summing over the entire domain effectively averages out translations. Our idea for the second generalization is to compute higher correlations, aiming to increase the completeness of the invariant at the expense of higher computation complexity. Formally, we define a (Multi-Orbit) k-correlation as follows.
Definition 4.1 (k-correlation). Let f : S,, -> Cd. An entry of the k-correlation function is defined as
already com-
8/ (k) (Gu-1)
f(g)
fāgr)
Sm
gea.
where Gk-1 1) E (-
Our family of invariants the k-Spectrum entries- is given by Fourier transforms over the last entry of k-correlation function. This establishes a bijection with the correlation functions, while helping the computation.
Another confirmation arises from the study of higher cor- relations undirected, unweighted graphs, in which case Aij E {0, 1} and A = 0. Here, higher correlation entries count increasingly larger graph substructures. For instance, Agtni.stn counts the number of edges in [3ml
s = Σjes,
Definition 4.2 (k-Spectrum). Let ʃ S.. - Cd. An entry of the k-Spectrum is defined as
the graph. Going on with similar calculations, sy²) (g1) re-
covers the results of S(1) for 91 = () and g2 = (n - n), (8) counts the number of pairs of edges that share a common ver- tex for g E {(n 10o-2, n 1),( (n 2, n), (n -0-2 2, n 1, n), (n-
8 (Gk-2, p)= ① (k) It
(Gk f fin(
5

---

The Generalized Skew Spectrum of Graphs
2, n,n 1)}. and counts the number of pairs of edges that do not share vertex for 9 (n -3, n () n) Both the first and second correlations are sufficient to distinguish all graphs with up to three vertices. Finally, one can deduce that sy (n1 2, n - 1), (n 3, n2 1)) is proportional to the number of triples of edges that all share one vertex,
possible values of l maximum of 9, with the spectrum reaching its peak number of entries in the range [4, 6). While this heuristics heavily sacrifices expressivity, we will show that it still adds completeness to the reduced Skew Spectrum, without increasing its computational complexity.
The reasons that motivate these heuristics are two. First, the Skew Spectrum and the Multi- Orbit version only need to be evaluated on the 7 double cosets representatives Sn-2\Sm/Sn-22 We extend this to k-Spectra by analogy.
while / (nn - 2, n)), (n - 2, n - 1)) is proportional to the number of triples of edges that form a triangle, allowing the invariant to distinguish graphs with more nodes.
Second, we note that repeated elements do not increase expressivity when representing unweighted graphs, and that the order of the elements in Gk-2 does not matter.
4.1. Sparsity and double reduction
The increased expressivity of higher correlations comes with higher computational complexity. Indeed, (8) needs to be evaluated on k group clements, each one taking up to n! values. Here we prove a result that reduces the number of k-Spectrum entries to compute.
Theorem 4.5 (Element distinctness). Let f: S,, + {0. and let Gk-2 the list obtained by adding one element to Gk-3- Then, Sj (Gx p) adds information over o (( (Gk-3: P) only if the added element in Gk-2 is not already in Gk-3-
((R)
Theorem 4.4. Let| f :..//n-2- + Cd. The Multi-Orbit k- Spectrum of f is uniquely determined by its subset of compo- (k) nents { (Gx-2,P)lp E An; Gk-2 E (Sn/8n-21 k-2))
Proof. Because of the Fourier bijection, we consider k- correlations (see Def. 4.1).. Define Gk-1 by taking Gk-2 and adding one element a, and then G2-2 by taking Gk-3
Proof. Observe Def. 4.2 To restrict Gk-2, suffices to see that for any H E 2 k-2 II
fú, (ōgil))
and adding the same o. Using f(g) = f() and 7 one
k-2 (ōgi). To restrict p, use Lemma 2.1 I
can verify (Gx-)) sf s/- (G implying that ((k) Sj 2G = =Sg ((
While the Skew Spectrum and its Multi-Orbit general- ization only need to be evaluated on 7 group elements (5.-2\,,/S,,-- and 4 irreps (A,)), the k-Spectrum re- quires ((n2(k-2) group entries and 4 irreps.
Theorem 4.6 (Element ordering). Let f : Sn C. (kt) (Gk-2, adds information over Si (Gk-2: only Gk and Gk-z contain distinct sets of elements.
To reduce the computational complexity, while maintaining the generalization, we employ two heuristics: the reduction of Kondor & Borgwardi (2008), and a double reduction that further limits the entries evaluate.
Proof. Consider the k-Spectrum (Def. 4.2 Let Gh con- tain permuted elements of Gk-2- Since the terms (99)) commute, we have p(k) (Gx-2,P) = p()) (G') (Gk_2)))
Reduction. Analogously to the approach of Theorem 2.4
5. Relationship to WL hierarchy and GNNs
we define the reduced k-Spectrum
Understanding the expressive power of Graph Neural Net- works has become a central theme in graph learning research. A key result in this area establishes that message-passing neural networks- broad class of GNNs are most as expressive as the 1-dimensional Weisfeiler-Lehman (1-WL) graph isomorphism test (Xu et al. | Morris et al. 2019). Recent work has extended this line of analysis to alternative architectures, including those based on relational pooling and spectral features, relating them to the broader Weisfeiler-
8/ (Gk-2.P) =
(10)
In
where $/4_, (G) = 1 (Gk- 2, Ts. (p) and
(k)
- (p) is the projection of p onto the trivial irrep of Sn-2-
78.-2 makes the rows of (()) 8/ (G o)t match the sparsity patterns of the Fourier transform columns (Lemma 2.J and Appendix B), making ((k) easier to compute and restricting the non-zero elements of each the direct sum term to 49.
Lehman hierarchy (Zhou et al. 2023 Zhang et al. 2024).
Within this landscape, exploring the relationship between our proposed k-Spectra (or k-correlations) framework and the WL hierarchy offers a promising avenue for both the- oretical insight and practical application. Understanding this connection can shed light on the representational capa- bilities of kSSpectra and suggests ways it may enhance the
Double reduction. The Doubly-reduced k-Spectrum is given by the entries of the reduced k-Spectrum evaluated on without repeti- tions or order. This heuristic reduces the number of possible entries from n (k=-2) to (g (x This effectively restricts the
-k-2 taking values in
6

---

The Generalized Skew Spectrum of Graphs
Algorithm 1 Doubly-Reduced k-Spectrum
Algorithm 2 Precomputing ((c)
Input: Functions ft S - C, for [d]
Input: Functions ft Sn/Sn - C, for [d]
Precompute s(k)
for i E [d] do
for E {(n), - 1,),, 2,2), (n 2, do
for j E [n 2] do
for i E [d] do
F( = -ngg))/)) fi((n - 1,
Compute (p) end for
for a E Sn/Snn200 do
P, = [i(0)
for Gk-2 E comb(Snn2)0nn /Sn 2) do
0, = fi(o (n- 1,n))
for 1--1 E [d|=11 do
P, ((0-(n-1..j)
Compute 8/21 (Gk-2;
end for
fi(0 "jo.(j,n- 1,n))
Sf (GB=2, p) = ① (eeet +
((k)
8/z, ()) fi (p)
(R)
Pi 0,J
T(a--jjm)
end for
F((((j)) -Ee{(,,) Pi
P9(0,,0,5)
end for Output 5g
n-3
end for end for end for for Jk-2 E [d]k- do
expressivity of graph learning models, such GNNs.
for Gk-2 E c - 2) do
for a E Sn/Sn-2 do
Theoretically, k- WL and k-correlation spectra capture dis- tinct structural properties: while k-WL. iteratively refines node representations based on patterns over k-tuples of node neighborhoods, k-correlations count edge-level substruc- tures (see Intuition in the previous section). This distinction positions k-Spectra as complementary framework for eval- uating and augmenting expressivity.
Qn (Gk-2, أj= nn for E [d] do
11 P. o,
T--1 append 22 (k)
1 (Gk-2, 0) = liz-1 (0)
n-2 Qua (Gk-
end for
end for
end for
As an illustrative example, Gai et al. (2025 Corollary 3.14) show that spectral-invariant GNNs can count paths and cy- cles of up to 7 vertices. In contrast, non-reduced k-Spectra with sufficiently large l can capture longer paths and larger cycles, suggesting path for practical advantage.
end for Output (A)
promising opportunities for future work at the intersection of spectral methods and GNN design.
To empirically examine the relationship with WL tests, in Section 7.2 we demonstrate that features derived from the doubly-reduced k-Spectra are neither strictly less expressive nor strictly more expressive than those derived from 1-WL. This supports the intuition that k-Spectra offer orthogonal structural insights not captured by WL-based approaches.
6. Computation and complexity
We proceed to detail the computation of the Doubly- Reduced k-Spectrum (10). which is the generalization of the Skew Spectrum with the lowest computational complexity.
Beyond theoretical comparisons with WL tests, we highlight three potential integration approaches into GNN pipelines:
The main idea is summarized in Algorithm [ We can treat g(k) as the Fourier transform of function (T ES,/S
Post concatenation: Precompute k-Spectra whole- graph embedding and concatenate it with the output of the GNN embedding, just before the prediction layers.
Sim, (a)
k-2
(k) 1--1 (Gk-2,
Σ II (ahgi) (11) SS 2 MER
k-Spectra aggregation: Incorporate k-Spectra sub- graph invariants during the node aggregation step. k-Spectra pooling: Replace standard pooling fune- tions (e.g., summation, max) with k- Spectra-based in- variants to aggregate node features.
1=1
After precomputing s(k), we can compute its transform and that of one single orbit function, for all the input. Then, multiplying them produces one entry of the Spectrum.
Each of these strategies supports the incorporation of leam- able parameters, such as orbit-specific weights (terms of Eq. B). allowing the model to adaptively emphasize the most relevant graph information, We see these directions as
Precomputing g!k) efficiently requires some creativity. Al- gorithm 2 does so, using a divide-and-conguee strategy, coupled with dynamic programming. The procedure breaks the computation of (*) into the computation of partial sums

---

The Generalized Skew Spectrum of Graphs
7. Numerical experiments
We implemented proof-of-concepl for the Doubly-reduced k- k-Spectrum validate our theoretical insights. We report experiments that illustrate our contributions and show how the new results add expressivity to the original embedding.
(a) 15A.
(b) 15B.
(c) 6A
(d) 6B.
Figure 3. Synthetic dataset with four graphs families. Each family contains 1000 isomorphic graphs. Families are isomorphic.
7.1. Multiple orbits
First, we illustrate the potential of Multi- Piblit embeddings.
that can be efficiently recombined when fixing the input parameters. We summarize this intermediate result in the following Lemma, discussing its correctness Appendix C
Eigenvalue collision. first demonstration considers graphs with node labels, represented by adjacency matri- ces with labels encoded in the diagonal. While eigenvalues and singular values also form valid permutation invaarian embeddings (permutations act as similarity transformations through orthogonal matrices, preserving the spectrum), they fail to distinguish such structures.
Lemma 6.1 (Precomputing s(k)). Algorithm 2 precom- (k)
putes 81x-1 (G) for for all the choices of the input pa- rameters I&-1 E |d]-1, Gk-2 E (5n=2\a/8nn-2/) 2-2 E Sp/Sn-2 It requires Od dn2= operations and (dn + n2² space.
Combining this lemma with the efficient computation of Fourier transforms on S, we arrive the following.
Theorem 6.2 (Doubly-reduced t-Sppetrum). Let f Sn/Sn-2 + Cd. We can compute its doubly-reduced k- spectrum in O(dh-ln² 3 + d " operations. The doubly- reduced k-spectrum has up 7dt non-zero entries.
This result recovers the complexity of the reduced Multi- Orbit Skew Spectrum (Theorem 3.2) for the reduced Skew Spectrum (Theorem 2.4) for d 1. The double reduction limits the scaling with n. On a single orbit, this enables the computation of more expressive invariants at the same computational cost of the Skew Spectrum.
(a) Graph
(b) Graph 2.
and that of
Figure 4. Two directed, weighted, labeled non-isomorphic graphs
For example, the two graphs in Fig. 4 are non-isomorphic, as for instance the path from to has different weights.
[ 1
2
Their adjacency matrices, A 2 2 and A₂
2 1
6.1. Complexity analysis
{3,0] and singular values (3.16, 0}. However, the reduced 2-Orbit
share eigenvalues Eigs(A1) = Eigs(A)
We briefly prove Theorem 6.2. discussing the complexity of the algorithm and the number of non-zero entries.
Skew Spectrum, using fi = An(n). and f2(0) = A (n)) correctly distinguishes them.
Main algorithm. Algorithm I precomputes (kk)
(Lemma 6.1 and then proceeds to compute the entries of ((k). The for loops compute d Fourier transforms (A) and on fi, each of which takes ((n²) operations, since both are functions on Sn Finally, the direct sum performs d matrix multiplication that cost O(??) each (see the sparsity patterns of Lemma 2.1). The overall complexity is indeed 01 d"
Synthetic graphs. We evaluated the Multi-Orbit gener- alization on synthetic dataset of labeled, directed, and weighted graphs. The dataset consists of four families: (15A, 15B, 6A, 6B) (Fig. 3). Graphs within a family are isomorphic under edge- and label-preserving permutations, but graphs across different families are not. Specifically, in 15.4 and 15B (and similarly in 6.4 and 6B), there is a permutation that links the edges and separate permutation that links the labels, but these permutations are not the same. The task is to correctly classify the four families.
Non-zero entries. For each the 4 irreps, there are (e22) lists Gk-2 which evaluate the spectrum. Each spectrum entry has d terms in the direct sum, with non-zero entries determined by the irrep. Using (10p and the column sparsity of the Fourier transform (Lemma 2. we observe that each E {(n), (n - 1, (n - 2, 1)} produces non-zero entry, while p = (n 2) produces 4: (7 113 4).
We processed the graphs using two representations: (1) the concatenation of Single-Orbi Skew Spectra computed on graph structure and labels, and (2) the 2-Orbit Skew Spec- trum. Random Forest classifier (60 estimators, no max depth) trained on 80% of the data achieves 50% accuracy
8

---

The Generalized Skew Spectrum of Graphs
1044
Table 1. Atomization energy regression on QM7, for different rep-
107
:332
303329
10
2295
200
resentations and models. Results in Mean Average Error (MAE).
Coltsions
10?
Collisions
29
22
201
10
REPRESENTATION
XGB
GBR
EN
LINEAR
10%
HINGLE-ORBIT
29.15
36.55
114.68
61.15
2-ORBIT
18.28
27.12
58.60
49,45
C's EIGS
38.04
37.92
47.83
Representation
Repr esentation
LAPL.'S EIGS
23.52
26.93
47.62
47.80
(a) Craph Atlas, 7 nodes.
(b) Chordal graphs nodes.
Figure 5. Shattering non-isomorphic graphs with SSSpectra (k E [3, 9), their concatenation (C), Laplacian's 's eigenvalues (L), and 1-WL tests with different iterations (I-WL-ITER).
with the Single-Orbit representation and 100% with the 2- Orbit representation. This is because the concatenation of Single-Orbit Skew Spectra cannot distinguish the couples 15A4-15B and 6,--B, whose labels and edges are linked by different permutations, while the 2- 2-Orbit Skew Spectra capture interactions between edges and labels (6)
k-S S-Spectra offer greater expressivity in that setting. On the other hand, for the chordal graphs with n 8, 1-WI. re- sults in fewer collisions than the concatenated spectra. This outcome supports the perspective discussed in Section 3 re- inforcing the idea that k-correlations and WL tests measure different structural properties and can serve as complemen- tary expressivity metrics.
QM7. We tested the Multi-Orbit generalization on the QM7 dataset, which contains Coulomb matrices of 7,165 molecules with up to 23 atoms (Rupp et al. 2012 Blum & Reymond 2009). The Coulomb matrix C' E RR 1223x23 is defined as C = z 2 and Cij- = TR, RRT. where 2; is the nuclear charge of the i-th atom of the molecule, and R; is its position. The task is to predict molecular atomization energies (kcal/mol), renormalized from -1 to 1.
2.2,
8. Conclusion
This work generalizes the Skew Spectrum (Kondor & Borgwardi 2008), advancing group-theoretic methods for permutation-invariant graph embeddings. We introduced Multi- Spectra for complex graph structures, k-Spectra to trade-off expressivity and complexity, and Doubly- Reduced k-Spectra to enhance expressivity of the original Skew Spectrum without added cost. We support our the- oretical insights with numerical experiments. This study complements modern approaches and opens new avenues for research in graph representation.
We compare different representations: the Single-Orbin Skew Spectrum on the off- off-diagnnsls, the 2-Orbit Skew Spec- trum, and eigenvalues of adjacency and Laplacian matrices. We train several models dient Boosting (XGB), Gradient Boosting Regressor (GBR), Elastic Net (EN), Linear Regression (Linear) (Pedregosa et al. 10 Table reports the results, with XGB and the 2-Orbit Skew Spectrum achieving the best performance.
80%-20% split: Extreme Gra-
7.2. Higher correlations
Future directions. On the theoretical side, (1) key open question is whether there exists a finite kmax such that the collection of all k-correlations up to kmax forms a complete invariant, which remains to be proven. (2) Our framework, focused S,,/,,,, could naturally be extended to func- tions on G H for arbitrary groups/subgroups, broadening its scope beyond graphs to invariants for other structured data domains. (3) Another avenue is exploring other families of translation-invariant polynomials beyond k-correlations.
We study how higher-order correlations affect expressivity using two datasets of non-isomorphic, unweighted, undi- rected graphs: the Atlas of all graphs with 7 nodes, and set of connected chordal graphs with 8 nodes (McKay). For each dataset, we computed the Doubly-Reducee k-Spectra for k E [3.9]. their concatenation, the eigenvalues of the graph Laplacian, and the 1- 1-WL test for multiple iterations. We then measured the number of collisions, i.e., cases where non-isomorphic graphs could not be distinguished by each method. Figure 5 summarizes the results.
On the practical side, (1) developing a scalable, optimized open-source implementation with thorough benchmarking is crucial step toward real-world adoption. (2) Integrating our methods with modern deep learning frameworks offers further opportunities: (2. introducing trainable parameters, such as learning the relative importance of correlations be- tween orbits, or (2.2) using the generalized Skew Spectrum as a positional encoding, aggregation, or pooling function to enhance neural representations.
Increasing A significantly improves the expressivity of the Skew Spectrum (k- 3), reducing the number of collisions. For n = 7,the concatenated k-Spectra form a complete invariant no collisions remain outperforming both the Laplacian eigenvalues and 1-WL in distinguishing graph structures. Interestingly, 1-WL does not achieve a com- plete invariant for the n graphs, and the concatenated

---

The Generalized Skew Spectrum of Graphs
Impact Statement
10.2307/2034551.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Babai, L. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 684-697, 2016.
Batatia, I., Geiger, M., Munoz, J., Smidt, T., Silberman, L., and Ortner, C. A general framework for equivariant neural networks reductive lie groups. Advances in Neural Information Processing Systems, 16:55260-55288 2023,
Acknowledgements
First and foremost, we would like to thank Ramakrishna Kakarala for providing us with a soft copy of his thesis. We also extend our sincere thanks the Quantum Open Source Foundation (QOSF), through which the authors met and this project started.
Bellante, A. Quantum Algorithms for Sparse Recovery and Machine Learning. Phd thesis, Politecnco di Milano, Milan, Italy, 2024.
A.B. gratefully acknowledges Stefano Gogioso and Erick- son Tjoa for insightful discussions that helped improve the mathematical notation; Filippo Guerranti for providing ref- erences, background material, and assistance in revising the manuscript and supporting the submission process; and Alessandro Palma for valuable feedback experiments and the submission process. He also thanks Professors Ste- fano Zanero. Donatella Sciuto, and Ferruccio Resta for their support during his Ph.D., Patrick Rebentrost for hosting him at CQT during part of this research, and Professor Ig- nacio Cirac for his support during his postdoctoral work. A.B.'s research was partially funded by THEQUCO as part of the Munich Quantum Valley, supported by the Bavarian State Government through the Hightech Agenda Bayern Plus. Additional financial support was provided by ICSC "National Research Centre in High Performance Comput- ing, Big Data and Quantum Computing," " Spoke 10, funded by the European Union NextGenerationUU, under grant PNRR- WWRRR-CN0000013-HHPG
Blum, L. C. and Reymond, J.-L. 970 million druglike small molecules for virtual screening in the chemical universe database GDB-13. J. Am. Chem. Soc., 131:8732, 2009.
Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2 10n.:24044347 2021.
Chazan, D. and Weiss, B. Higher order autocorrelation func- tions translation invariants. Information and Control, 16(4))378-383, 1970.
Clausen, M. and Hühne, P. Linear time fourier transforms of innviinvariant functions on the symmetric group sn. In Proceedings of the 2017 ACM on International Sympo- sium on Symbolic and Algebricc Computation, pp. 101- 108, 2017.
Corso, G., Stark, H., Jegelka, S., Jaakkola, T., and Barzilay, R. Graph neural networks. Nature Reviews Methods Primers, 4(1):17, 2024.
M.P. acknowledges support from the Deutsche Forschungs- gemeinschaft (DFG, German Research Foundation, project numbers 447948357 and 440958198; the Sino-German Center for Research Promotion (Project M-0294), the Ger- man Ministry of Education and Research (Project QuKuK, BMBF Grant No. 16KIS1618K), the DAAD, the Alexan- der von Humboldt Foundation, and the Niedersächsisches Ministerium für Wissenschaft und Kultur.
Dehmamy, N., Walters, R., Liu, Y., Wang, D., and Yu, R. Automatic symmetry discovery with lie algebra convolu- tional network. Advances in Neural Information Process- ing Systems, 34:2503-2515, 2021.
Gai, J., Du, Y., Zhang, B., Maron, H., and Wang, L. Homo- morphism expressivity spectral invariant graph neural networks. In 13th International Conference on Learning Representations, ICLR 2025, 2025.
A.L. acknowledges the support of the National Research Foundation, Singapore, and STAR under its Centre for Quantum Technologies Funding Initiative ($24Q200009), and the Quantum Engineering Programme (QEP 2.0) under grants NRF20221-9EP2-02-P05 and NRF202 NRF2021-QEPP-02- POI.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning, pp. 1663-127. PMLR, 2017.
References
Grillet, P. A. Abstract algebra, volume 242. Springer
Science & Business Media, 2007.
Adler, and Konheim, A. A note on translation invariants. Proceedings of The American Mathematical Society
Hamilton, W. L. Graph representation learning. Morgan & Claypool Publishers, 2020.
PROC AMER MATH SOC, 13:425-425, 03 1962. doi:
10

---

The Generalized Skew Spectrum of Graphs
Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):29-1500 2011.
Rupp, M., Tkatchenko, A., Müller, K.-R., and von Lilien- feld, O. A. Fast and accurate modeling of molecular atomization energies with machine learning. Physical Review Letters, 108:058301, 2012.
Kakarala, R. Triple correlation on groups. Phd thesis,
Sagan, B. E. The symmetric group: representations, com- binatorial algorithms, and symmetric functions, volume 203. Springer Science & Business Media, 2013.
University of California, Irvine, 1992.
Kondor, R. Group theoretical methods in machine learn- ing. Phd thesis, Columbia University, 2008
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
Kondor, R.
The skew spectrum of functions on finite groups and their homogeneous spaces. arXiv preprint arXiv:0712.4254) 2007.
Stone, M. The generalized weierstrass approximation theorem. Mathematics Magazine, 21(5):237-254, 1948.
Kondor, R. and Borgwardt, K. M. The skew spectrum of graphs. Proceedings of the 25th international confer- ence on Muchine learning, pp. 496-503, 2008
Xu, K., Hu, W., Leskovec. J., and Jegelka, S. How powerful are graph neural networks? In 7th International Con- ference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Kosmala, A., Gasteiger, J., Gao, N., and Günnemann, S. Ewald-based long-range message passing for molecular graphs. In International Conference on Machine Learn- ing. pp. 17544 17563. PMLR, 2023.
Zee, A. Group Theory in Nutshell for Physicists. In a Nutshell. Princeton University Press, 2016. ISBN 9780691 162690.
Maslen, D. The efficient computation of fourier transforms on the symmetric group. Mathematics of Computation, 1998.
Zhang, B., Zhao, L., and Maron, H. On the expressive power of spectral invariant graph neural networks. In Proceed- ings of the 41st International Conference on Machine Learning, pp. 60496-60526, 2024.
McKay, B.
Combinatorial graphs. https://web
a arch wtchive..gg/web///eoo 0000224411111188//11111111
//users. cecs www.ccaaauu................ www. aa/ data/
Zhang, Z., Bu, J., Ester, M., Zhang, J.. Yao. C., Yu, Z., and Wang, C. Hierarchical graph pooling with structure learning. arXiv preprint arXiv: 1.05954, 2019.
graphs html Accessed: 2024-12-31.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. Pro- ceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Zhao, Y. Young tableaux and the representations of the symmetric group. dimension, 3(1):3, 2008.
Zhou, C., Wang, X., and Zhang, M. From relational pool- ing to subgraph gnns: A universal framework for more expressive graph neural networks. International Con- ference Machine Learning, pp. 42742 42768. PMLR, 2023.
Nettleton, D. F. Data mining of social networks represented as graphs. Computer Science Review, 7:1-34, 2013.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Pourhabibi, T., Ong. K.-L., Kam, B. H., and Boo, Y. L. Fraud detection: systematic literature review of graph- based anomaly detection approaches. Decision Support Systems, 133: 13303, 2020.
Raczka, R. and Barut, A. O. Theory of group representations and applications. World Scientific Publishing Company, 1986.
Rotman, J. An introduction to the theory of groups, vol- ume 148. Springer Science & Business Media, 1999.

---

The Generalized Skew Spectrum of Graphs
A. The Symmetric Group Sn
We review key concepts related to the symmetric group S,, to support our discussion. For a more in-depth treatment, see Grillet 2007), Rotman 1999). Raczka Barut (986),, and the background sections /fllante (2024).
The Symmetric Group S, is the group of all permutations of n objects. Each permuation g S, acts by mapping the indices of objects in an ordered set to new positions, effectively defining bijective function [ra] + [nt. The group has [s,, n! elements, corresponding to all possible rearrangements of indices.
Besides the cycle notation used in the main text, permutations can be conveniently represented as arrays:
2 g [1(), g(2).
π
"
g
1),
g(n)]
(12)
where gii denotes the image of index i under g. For instance, the transposition swapping the first two elements in S4
2
3
4
= [2, 1, 3,
This notation makes it easy to identify left coset transversal for Sh/Snn> 1n-22 containing one representative for each
1
n 1
group element that fixes the last two positions g = [_..,
i j] Since i, E [n] and + j. there are
nn 1) such representatives, giving /S./Sn 2/ n(n 1).
Functions on graphs, such as f(o) (n depend only on the image of the last two indices. This makes it clear that
f(ah) = f(o), for all a E Sn h E Sn-2,
(13)
1
1 n n 1, n
since elements h E Sn-2 preserve the last two indices: h [...,
A.1. Irreducible representations
We introduce the concepts that are most relevant to our work. For a more comprehensive treatment of the irreducible representations of Sn,, see Sagan 2013) Zhao (008), and the background sections Bellante 2024).
For our focus, representation of S, mapping p Sn - (p)im(p)) that assigns each permutation S,, unitary matrix of size dpm(p) dim(p). This mapping satisfies the following properties:
1. p(e) I, where is the identity permutation and / the identity matrix.
2. 0(0102)) (((2)) for all 02 e Sn.
3. =(()))
Since the direct sum of two representations is also representation. we say that a representation is irreducible (irrep) if it cannot be decomposed into a direct sum of smaller representations. That is, if p(a) = (1(a) ① p2(a) for all a E S,, then either dim) = or dim(p2) = 0.
Irreducible representations of S, are classified by partitions of n, up to equivalence under invertible linear transformations. A partition of is sequence À= (A1,22,... ......,,.. of weakly decreasing positive integers (A; 2 >;-1) that sum n. We denote this by À + and often use p interchangeably for both the partition and the corresponding representation. The trivial partition of is (n), which corresponds to the trivial representation p S, C given by p(a) = 1 for all a.
,,) At)
convenient way to visualize partitions is through Ferres diagrams (or Young diagrams), which consist of rows of boxes, where the i-th row contains >; boxes. Because is weakly decreasing, each row contains at most as many boxes as the row above. For example, the partition (7, 4,3, 1) H 15 is represented as:
12

---

The Generalized Skew Spectrum of Graphs
Figure Young lattice S4.
Young tableau is Young diagram filled with the numbers through n without repetition. standard Young tableau has strictly increasing numbers along each row and each column. The dimension of irrep labeled by À is given by the number of standard Young tableaux of shape X. This number can be computed through the hook lenght formula. Table lists the dimensions of irreps relevant to our work.
Table 2. Dimensions of irreducible representations of S.. indexed by partitions À + The dimension is given by the hook-length formula f which counts the number standard tableaux shape X. These values are from Kondor 2008 Table 1.1).
l or dim(px)
(n)
(n 1,
72
(n 2,2)
min 3)
(n 2,1,
(7L 1mn
In this work, use the Young Orthogonal Representation (YOR), a specific irrep S, with real-valued, sparse matrices. This representation is adapted to the subgroup chain S, S -> S1, meaning that any } k, when restricted to Sa-1, decomposes as:
1s._, (h)
n(h), mンक
h he h
(14)
Here p k. H 1, and the notation 7) < p means that 1) can be obtained by removing one box from the Young diagram of p. This structure provides efficient way decompose irreps of S, when acting on elements of subgroup S, S.-k- Figure fillustratss this decomposition for Sy. Such diagrams are often termed Bratteli diagrams Young diagrams.
Finally, a useful result in representation theory, sometimes referred to as the Great Orthogonality Theorem Zee 2016
Section II3)), states that for any two irreps P1,P2:
|Sp 8p 6r,10
Σ (pll)sp(l)a. = dim(p)
(15)
ge
13

---

The Generalized Skew Spectrum of Graphs
(n 22,,1,1
- 22,)
(n - 1,1)
(n)
2, 1)
(n- 1)
(n 2)
Figure 7. Partial Young lattice the partitions reaching (n 2).
Here, 6p..p2 is the Kronecker delta, which is if f1 and are equivalent (i.e., represent the same irrep) and otherwise. A direct consequence of (15) that summing over all elements of S, in given irrep of p yields:
Sn p = (n) p(0)
p(o)
(16)
otherwise.
This follows from the fact that the trivial representation (n) has dimension 1 and consists entirely of ones.
B. Fourier sparsity and projecting on the trivial irrep
In this appendix, we examine the role of T8.-.()), which represents the projection of an irrep p E Irr(S,,) onto the trivial representation of Sn
(p) = hES,
p(h)
(17)
This projection naturally arises in the Fourier transform of functions Sn, /n/Sn-2 + C Kondor 2007 )
f(0)
Σ
f(a)plo)
Σ Σ
f(yh)
(18)
Spp
yES., /Sn REB.-2
Sn 2|
Σ
f(y)p())
p(h)
(19)
S
S hES
yEan /Sn-//nn2
S
fl))P())TS...o)))
(20)
S
yES../S.. /Sp-2
Moreover, 7h, (p) is responsible for the sparsity patterns described Lemma
2.1
Using the fact that YOR adapted 14
along with a special case of the Great Orthogonality Theorem (16), we obtain:
{
if (n (n-2) 2)
TB (p)
+ Σ
(1b)
+
(21)
otherwise.
p<pheS.-
n<p
This shows that Ts.. 2 (p) is diagonal matrix containing mostly Os, except for few 1s corresponding to the positions where (n 2) appears in the decomposition of p.
From the structure of the Young lattice we see that there are exactly four partitions of that contain (n 10-22 2):
(n), - 1, 1), (n 2,2), (n- (0),nn1,11)
(22)
This set of partitions is refereed to as An in the main text. Figure provides a visualization of a partial Young lattice, illustrating these decompositions.
14

---

The Generalized Skew Spectrum of Graphs
Since all other irreps do not contain (n 2), their projection 7B,, 2 (p) is the zero matrix, implying that their Fourier transform also vanishes.
Further observation reveals that three of these partitions - (n). (n 1,, (n - 2, 1) contain (n 2) exactly once, while
(n 2, 2) contains it twice. The number of paths from p to (n - 2) in the Young lattice determines how many diagonal entries of (p) are
Combining this observation with the dimensions of the irreps (see Table 2 completes the proof of Lemma 2.1
Finally, note that, since (p) a diagonal matrix, follows that TB., (p) 78n-2 (p)
C. Precomputing s(k) with Dynamic Programming
In this Appendix, we prove the correctness of Lemma 6.1 and Algorithm begin by proving the following theorem. Theorem C.1. The Fourier transform of
(o)
k-2
(k) 8 I--1 (Gk-2, = nn
Σ
II (ohgg
(23)
hESm-2 1=1
over the last entry produces f1 (Gk-2, k-
(b)
2G 2 (P), where T (GB-
(k)
2. Eges, Su, ( IT (19)))() and ve,, (0) is the projection of onto the trivial irrep (n 2).
Proof. We compute g(k) using the expressions from 23 and
3D:
8/-1 (Gk-
fiz-1
Σ
II E=1
Lu (ghg))pl))
(use 5 = gh) (24)
Sml
gE
hE3m-2
Jia (@h
II
fy (0o1)
(25)
Sml
S
1=1
2-2
fucm (0)
II fy (09))(())
Σ p(h)2
(use Ts. = = (p)))
(26)
Sm
Sn-2 RER.
SE
(k)
p)
(27)
It is also important to observe that (1)) (Gk-2, = (k) 8/2_, (Gk-2, oh) for any h E Sn-2. This implies that
fast Fourier transform on S,/SS,- obtain (A) (Gk-2.P). P).
Now, we address the task of efficiently precomputing 23 for i1 f1,..., 11 E [d]. ...... 9k-2 taking values in the double
coset transversal -, /S./S.n.. = (0, (n - n), (n 2, n 1), (n - n, (n 2,n 1,m), (n 2, n, n - 1), (n n (n 2, n,), and a E Sn
Naively computing (23) for all the possible entries would be prohibitively expensive. Specifically, the sum over S, contains (n- 2)! terms, making this computation infeasible even for small n. To circumvent this, we employ a divide-and-conquer strategy plus dynamic programming.
The main idea is to decompose
as
(o) Qr (G
8
81 (Gk-2,0)
(K)
(28)
n
where Qin-2 Σド= M P. (gt, J. and we have functions P, one per element in the double coset
15

---

The Generalized Skew Spectrum of Graphs
1. o, [ı
2. P,(g fi(a 1, n)).
3. Pilgs, a.j)
4. o. = fi(o-(n,j)),
5. Pa(gs,a,1 = fi(a.(j.n p..njjjn... 1.n))
6. Polgs, J. = T 1)).
7. P,(0),0,5) = Fi(o(f)) Lie(3,6] 0,)
n n-
with P(()) Eielnl fi((n n,),
Here, a. represents the group operation combining two elements, while ajj denotes the image of j under ø.
By utilizing dynamic programming, we can compute these P P-functions efficiently and precompute (k)) without resorting to naive approach.
We break Lemma 6.1 into two propositions, proving its complexity and correctness separately.
C.1. Complexity
Proposition C.2. Algorithm requires O
223 2 + d d operations and O(dn3 + d space.
Proof. We analyze the complexity of each step in Algorithm 2
Computing F)): Each function F.()) requires (n) operations. Since we need to compute ((d)) such functions,
the total time and space complexity for this step (dd²).
Computing Pg ji):: Each function Pc(g, jj can be evaluated in constant time, O(1). We need evaluate Odd))
such functions, leading to total time and space complexity of (dd")).
Computing Q1 (Gk-2, For fixed constant & E [3, 9), each Qı,_, (Gk-2, o) can be evaluated in O(n) operations.
There are d (1_2) n(n entries, the total time complexity of computing all the functions is 223) and
the space complexity is Oddh-2n3) (kc)
(k) Computing $1 (G o): Each s $1--1 (Gk-2, be evaluated in constant time, 0(1). There 1 n)
such entries, requiring (dd time and space.
Summing up the asymptotic complexities for time and space we obtain 0 2n2 dk=2)n² operations and O(dn + d=1nn
n²) space.
C.2. Correctness
(k) Proposition C.3. Algorithm 2 precomputes six (Gk-2, for all the choices of the input parameters Ig-1 E [d
Gk-2 E (S.-2VS./S,.. 2 E /n/Sn-2
Proof. The core idea behind the correctness of Algorithm lies in breaking down the over Sn-2. In particular, the crucial fact is that the sum over S
k-2
II 1=1
fu (ahgi)
(29)
Sn-2
heS
can be broken as sum 2 partial sums
1 Σ
II
Pu (gr,
(30)
2 1=1
To illustrate this, we study the term
Σ
fi(ahg)
(31)
S
KEB
16

---

The Generalized Skew Spectrum of Graphs
for all g _n and show how it naturally breaks into 2 partial sums indexed by j E [n 2]. Specifically, show that each corresponds to the (n 3)! elements h E Sn such that h(n 2) With this additional fact,
analyzing 31 suffices to prove the equivalence of (29 and 31
In the following, for each of the 7 group elements, we consider the action of ohg on n and n 1 and simplify the expression. For an ease of notation, we rewrite each fi as fi(a) = fn(((n - 1), (n)), with f [n]² + C.
91 = 0
ahg(n) (n o(n) ahg(n- 1) oh(n 1) a(n 1).
(32)
(33)
Hence,
Σ f.(ohg(n-1)),tt 1), (1, fi(o)
(34)
Bn-2l 2|
hES 2
So the term breaks in n Di=i o, The choice of how divides Sn is arbitrary here, so can satisfy
hinn 2) j- 2. 92 = (n 1,
ahg(n) = ah(n - 1) = o(n 1)
(35)
ahg(n - 1) ah(n) = (()
(36)
Therefore,
M(chhg(n-11 - o))())))) = f'(o(n) 1)) = f(a (n 1, n,))
(37)
S KEBn-2
So the term breaks in 1. mn-
n- 2i=1 (, Similarly to the previous case, the choice of how j divides Sn-2 is arbitrary,
so we satisfy hnn - 2) j.
93 = (n 2, 1)
abg(n) = ah(n) = (nn) ahg(n- 1) ah(n 2) o(j) for j [n -
(38)
(39)
There are (n 3)! elements h Sn-2 that can produce a certain j. and there are possible j. Grouping these terms, we can write
n-2
n-2
Σ Mahhg(n ohg(()) hESn-2
Σ (n (m-3))(((()))) (n 2)1
1
- n Σ ((a (n 1,5)). (40)
So the term breaks 1 n-2 ΣØ= P.(gs.
4. 94 (n n)
ohg(n) oh(n - 2) = o(j) for E In 2]
(41)
ahg(n 1) ah(n 1) on 1)
(42)
Similarly to the case above,
n-2
n-2
Σ
fllohgnn o))())()) (n - 2)!
Σ
(n - 30 1),o())
Σ
f(a (n, (43)
S
n-2 1=1
hEB
j=1
17

---

The Generalized Skew Spectrum of Graphs
So the term breaks in nー EØ=1 o,
5. 95 (n 2, n n.)
ohg(n) = oh(n - = o(j) for E [
(44)
abi(n 1) aah(n) = a(n)
(45)
Hence,
Σ f'(ahg(n - 1), ohg(n)) (n 2)
n-
1
R-
Σ 1=1
flo (j,n 1,))). (46)
n
hESn-2
1=1
So the term breaks in
n-2 1.
Dÿ=1 Pi(gs,
9o - (n- 2, n, n 12--1 1)
ahg(n) oh(n 1) = onn-n
(47)
oli(nn 1) ah(n 2) =o( for j [n -2
(48)
Therefore,
n-2
Σ
fl(ohg(n - (achg(nn-)),ohhgn))) 1).gng(()) = (n 2)
(n ()) 1))
(49)
Sn-21 hEB
j=1
n-2
Σ
f(a (j,,n 1)).
(50)
3=1
So the term breaks in n-2 -リ Pi o,j). (n - 3, 1)(n n,
ahg(n) oh(n - 2) = o for (n 22
(51)
ahg(n- -1 1) ah(n 3) o(1) for E [m [m-21,1++] #1
(52)
Then, obtain
n- 2 n-
Σ
flahggn -, ohg(n)) = (n 2)
(n (())
(53)
hES.-2
f=1
n-2
n-2
Σ
((d(i),((1))
(54)
n 2 j=1
n-3
So the term breaks - n Ej= o.j)) Here, P. - د. f((o(i)
To further optimize the computation of P: j), compute partial sums F()) = =mh
f(G.1) and write
P, Fi(((i)) - 11) -()))))
(55)
11 n-3
Using the cyclic notation, obtain P. o.j) F(((j)) ElE P((gi
and F(()) Σi=
fe( n. n,
n n
$41
18

---

The Generalized Skew Spectrum of Graphs
Table Regression on QM9 and ZINC with different representations. We tested the following machine learning models: Extreme
Gradient Boosting (Xgboost). Gradient Boosting Regressor (GBR), Elastic Net (EN), Linear Regression (Linear) using the default parameters of sk-leam. The error measured as Mean Absolute Error.
Dataset
Representation
Xgboost
GBR
EN
Linear
Single-orbit
1,1560
1.1552
1,1571
1.1558
3-orbits
1.1570
1.1528
1.1559
1.1540
QM9
C's cigs
0.9602
0,9640
1.1571
0.9899
Laplacian's 's eigs
0.9245
0.9377
1.0773
0.9704
Single-orbit 1.5442
1.5432
1.5422
1.5423
3-orbits
1,5500
1.5441
1.5422
1.5423
ZINC
C's eigs
1.3208
1.3876
1.5297
1.4249
Laplacian's 's eigs
1.3350
1.3933
1,5353
1.4324
D. Further experiments
In this section, report further experiments carried during the conference rebuttal period. These results are preliminary and intended to provide further insight, though they merit deeper future analysis.
D.I. Scalability and other real-world datasets
To further evaluate the scalability and practical relevance of the multi-orbit k-Spectra, we extended the multi-orbit experi- ments on QM7 presented in Section 7.1 (Table to two larger molecular datasets: QM9 and ZINC.
Both datasets were loaded through torch.geometric. QM9 consists of 130,831 molecules, each with up to 9 heavy atoms (maximum 29 nodes). We used the first 100,000 molecules for training and the remaining 30,831 for testing. ZINC contains 449 molecules with up to 38 nodes. We used the default train/tes//validation split from torch. geomet training on 220,011 molecules and testing 5,000, ignoring the validation set for simplicity. Both tasks regression problems. For QM9, the goal is to predict the dipole moment (target label 0 in torch. gww.etricm. for ZINC, the task is to predict penalized logP, also referred to constrained solubility.
Following the setup used for QM7, we compare different graph representations: the Single-Orbit Skew Spectrum on the off-diagonals, a 3-Orbit Skew Spectrum, and eigenvalues of adjacency and Laplacian matrices. For QM9, the three orbits are defined as follows: (1) the Coulomb matrix C: (2) an edge attribute obtained by summing the four edge attributes available in the dataset; and (3) the sixth node feature. For ZINC, the orbits correspond to: (1) the G matrix; (2) the single edge attribute; and (3) the single node feature. We trained multiple regression models these representations: Extreme Gradient Boosting (XGB), Gradient Boosting Regressor (GBR), Elastic Net (EN), Linear Regression (Linear) (Pedregosa
et al. 2011
Results are presented in Table 3 For QM9, the 3-orbit representation consistently outperforms the single-orbit skew spectrum and is competitive with Laplacian and adjacency- based features, with the Laplacian eigenvalues achieving the best accuracy. In ZINC, the 3-orbit representation again comparable other methods, although the eigenvalues of the Coulomb matrix C yield the best performance. We imagine that more thoughtful use of the k-Spectra could yield better results.
D.2. Integration with GNNS
To evaluate the practical impact of incorporating our graph representation into deep learning pipelines, integrate the k-Spectra features into standard Graph Neural Network. Specifically, integrated our k-Spectra with the HGP-SL model (Hierarchical Graph Pooling with Structure Learning) (Zhang et al. 2019).
We follow straightforward integration strategy: after computing a whole-graph embedding using our Doubly-Reduce k-Spectra, we concatenate this vector with the graph embedding produced by the final convolutional layer of HGP-SL. The concatenated representation is then passed to a fully connected layer that produces the final prediction. This design corresponds to the "post-concatenation" approach discussed in Section
19

---

The Generalized Skew Spectrum of Graphs
Table Test accuracy on PROTEINS dataset. Average standard deviation (Max) over six splits. K-Spectra features are concatenated to the HGP-SL embeddings, before the prediction layer.
Baseline
PR=0.3 0.508 0.004 (0.615)
PR=0.2 0.518 0.004 (0.615)
k=S
k=4
Single-O
0.609 0.020 (0.769)
0.622
0.011 (0.769)
0.612 + 0.010 (0.692)
0.642 = 0.016 (0. (0.738)
0.625 0.001 (0.662)
0.588
0.009 (0.662)
Multi-O 0.695 0.002 (0.754)
0.683
0.000 (0.708)
0,582 + 0.023 (0.738)
0.665 + 0.003 (0.723)
0.680 - 0.003 (0.738)
0.665 0.010 (0.815)
The model is trained and evaluated the PROTEINS dataset, which contains protein structures represented as graphs, filtered to contain only graphs with 3 to 30 nodes. We use the same training protocol and hyperparameters in the original HGP-SL work, including a learning rate of 0.001, a batch size of 32, and a maximum of 1000 training epochs. Early stopping applied based on validation loss. We experiment with two dropout rates: the original 0.5 and a lower value of 0.2.
We test both single-orbit and multi-orbit variants of DRkSP, using k E (3,4, 4,J. For each configuration, we report the average accuracy, standard deviation, and maximum accuracy across six random train/test splits. Table 4 summarizes the results. The baseline HGP-SL model achieves average accuracy of 0.508 (dropout 0.5) and 0.518 (dropout 0.2). Augmenting HGP-SL with the spectra consistently improves accuracy across all settings. Notably, moving from k = 3 to A: = 4 generally improves performance. Multi-orbit variants, built using the adjacency matrix and one orbit per node feature, outperform single-orbit variants most cases. These results support the hypothesis that k-Spectra features provide complementary information that enhances learning capacity GNNs.
20


Reviews:
[{"review_id": "tu2XyPKRXM", "reviewer": "Reviewer_hv4C", "summary": "In this paper, authors extend the Skew Spectrum-based graph representation method to handle rich graph structures and achieve preferable computational efficiency. The idea is interesting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Message-Passing Neural Networks:** We stress that our main claim is not to improve message-passing neural networks (MPNN), but rather the Skew Spectrum of graphs. However, we think these methods can improve MPNNs and report evidence in the answers. Most MPNNs architectures aren’t more powerful Weisfeiler-Lehman (WL) tests, specifically 1-WL [1, 2]. We start from this and include two other experiments:\n- We investigate the relationship between k-Spectra (kSP) and WL tests. On a theoretical level, the two appear to be different: k-WL tests look at nodes and distinguish them based on having certain neighbors; k-correlations count different edge structures (see Intuition in Sec. 4). This suggests that kSP provides an alternative expressivity evaluation framework. We extended the experiments in Fig. 5 to show that Doubly-Reduced kSP (DRkSP) can be more and/or less expressive than 1-WL: DRkSP is complete on graph of 7 vertices, while 1-WL is not, but perform slightly worse on Chordal graphs. New Fig: https://anonfile.io/f/LRH87kqC\n- Since DRkSP can be more expressive than 1-WL it can be combined with GNNs to enhance their expressivity. We integrate DRkSP by concatenating the embedding with the GNN output, before a fully connected prediction layer. We use the HGP-SL model of [1], trained on PROTEIN with molecules between 3 and 30 nodes. The results show that the DRkSP improves the learning capability and that both higher correlations and multiple orbits help: https://anonfile.io/f/yqPzRNyf\n\n**Theoretical Guarantees:** We are unsure of what you mean by “giving each node of the graph an index”. We extend the Skew Spectrum in two ways: enabling more complex graph structures through multi-orbits; increasing the expressivity with higher correlations. An explanation of why the extensions improve expressivity is in both Section 3 and 4.\n\nThe theoretical guarantees and the mathematical structure of the invariant guarantee interpretability. The invariant is not a black box. Having an explicit mathematical representation of the model allows determining why an algorithm made a specific choice, which is crucial, for instance, in cyberphysical and medical applications. The theoretical guarantees set expectations on the framework. For instance the embedding invariance (Theorem 4.3) implies that the invariant will not assign distinct representations to isomorphic graphs. Theorems 4.5 and 4.6 clarify which input adds information about graph isomorphism to the embedding. The intuitions in Sec. 3 and 4 explain how the kSP extends expressivity and help reasoning about WL tests and GNNs before experimenting. Other theorems detail the running time, guaranteeing a bounded execution time and setting expectations on the scalability of this method. If you consider it necessary, we can clarify this further in the revised manuscript.\n\n**Other algorithms:** Most of the modern approaches are either based on MPNNs [1] or on Spectral invariant GNNs [2]. We already discussed the relationship between MPNNs, WL and kSP above. About Spectral invariant GNNs, Corollary 3.14 of Reviewer 3’s second reference states that Spectral invariant GNNs can count cycles and paths up to 7 vertices, but non-reduced kSP, for high enough k, can count paths and cycles on more than 7 vertices, see Intuition in Sec. 4. This suggests that DRkSP and further heuristics on kSP could be used to improve the expressivity of such alternative methods.\n\nWe can come up with three ways of integrating the kSP with GNNs:\n- Precompute the kSP and concatenate it to the GNN layer that outputs the graph embedding, just before the fully connected layer that computes the prediction (see our HGP-SL experiment).\n- Compute subgraph invariants in the GNN node aggregation step using kSP.\n- Compute subgraph invariants in the GNN pooling layer using kSP, instead of other invariants like sums or max of all node labels.  \n\nIn all the three cases, we could introduce some learnable parameters, such as weights in the direct sum terms of our Eq. 8 to tune the relevance of the orbits. We will include this discussion in the manuscript.\n\nWe thank the reviewer for their kind feedback and hope that our answer addresses their concern. We remain available for further questions.\n\n[1] Morris, Christopher, et al. \"Weisfeiler and leman go neural: Higher-order graph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.  \n[2] Xu, Keyulu, et al. \"How Powerful are Graph Neural Networks?.\" International Conference on Learning Representations.  \n[3] Zhang, Zhen, et al. \"Hierarchical graph pooling with structure learning.\" arXiv preprint arXiv:1911.05954 (2019).  \n[4] Lu, Q., Zhou, Z., & Wang, Q. (2024). Multi-layer graph attention neural networks for accurate drug-target interaction mapping. Scientific Reports, 14(1), 26119.  \n[5] Feng, Yifan, et al. \"Hypergraph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.", "claims_and_evidence": "A lot of theoretical analysis are made. The expression of the paper is easy to follow.", "methods_and_evaluation_criteria": "The setting is rational to me.", "theoretical_claims": "I am not familiar with the theoretical analysis in the paper, so I am sorry that I am not able to appreciate the analysis in this part.", "experimental_designs_or_analyses": "In this experiment, authors prove the effectiveness of the Multi-Orbit Embeddings, the Higher-Order Correlations and its advantage over the classic Skew Spectrum. More experimental results are encouraged to be conducted to illustrate the advantage of the proposed algorithm against the message-passing neural networks", "relation_to_broader_scientific_literature": "See summary.", "essential_references_not_discussed": "See summary.", "other_strengths_and_weaknesses": "I have some concern over the advantage of giving each node in a graph an index. In this paper, authors claim that they have the advantage of “expressivity theoretical guarantees” and better generalization ability to richer graph structures like attributed graphs, multilayer graphs, and hypergraphs.\n\nWhat can the theoretical guarantee be used for?\n\nAlso, there are many advanced algorithms that are proposed to handle attributed graphs, multilayer graphs, and hypergraphs, can you discuss more about the proposed method with those kinds of algorithms?", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rcjlcVEiDP", "reviewer": "Reviewer_JxLA", "summary": "This paper proposes a family of permutation-invariant graph embeddings, which generalizes the Skew Spectrum of graphs introduced by Kondor & Borgwardt (2008).  Grounded in group theory and harmonic analysis, the method introduces a new class of isomorphism-invariant graph invariants that can embed more complex graph structures, including attributed graphs, multilayer graphs, and hypergraphs, which the original Skew Spectrum could not accommodate.  The paper further defines a family of functions offering a tradeoff between computational complexity and expressivity, and demonstrates an improvement in expressiveness without additional computational cost through generalization-preserving heuristics.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Computational cost:** Benchmarking the k-Spectra (kSP) and their Doubly-Reduced (DRkSP) version would be extremely interesting. However, a fair comparison requires a substantial amount of work, which has to be covered in future research. Fair benchmarking requires using the same programming language, amount of preprocessing, and hardware. While many existing algorithms leverage C implementations and GPUs or TPUs, our current implementation of kSP is in Python, deserves further optimization, and does not fully leverage the high parallelization opportunities of kSP, given by matrix sums, products and tensors. To perform the benchmarking, one would need to optimize for proper scaling and performance.  \n\nWhile a full benchmarking is beyond the scope of this paper, our claim that the single-orbit DRkSP fully generalizes the Skew Spectrum (SkSP) without increasing its asymptotic computational cost is supported by an extremely detailed analysis and proof, which continues in Appendix C. The algorithm’s complexity is O(n^3). To get an idea of the scaling, this is the same as a full eigenvalue decomposition of an nxn adjacency matrix. More concretely, in the rebuttal period, even with a non-optimized implementation, we computed 3-orbit kSP of QM9 (130,831 molecules) and ZINC (249,456 molecules) on a desktop PC, confirming scalability.\n\n**Paper structure:** We appreciate the feedback on structure and we are sorry it can seem confusing. We structured our paper this way: Introduction + SkSP Background (3 pages), Multi-orbit + Higher correlations + heuristics (2.5), Computation and complexity (1 + Appendix), Experiments and Conclusions (1.5).  \n\nWe want to stress that from page 3 onwards, the article only presents our own contributions. Sec. 2 Background discusses the minimum group theoretic background to understand the original SkSP [1]. We believed that introducing these concepts was necessary for a broader audience, who might not necessarily be familiar with graph invariants, harmonic analysis on the symmetric group, and the Skew Spectrum. Indeed, Reviewer 3 (VVhY), suggests expanding the introductory material even further.  \n\nAbout self-loops, node features, and edge features, we believe there is a misunderstanding. We assume that the reader is familiar with these concepts and never introduce them. The homonymous paragraphs in Section 3 describe, extremely concisely, how to encode these structures in our multi-orbit extension, which is part of the contribution.  \n\nOur understanding is that the reviewer expected more pages for the experimental evaluation, as it is common in many ML papers. However, our structure is the one of a theoretical paper, with several formal statements, analysis, proofs, and experiments that showcase the theoretical results. We believe that similar papers are usually welcome at ICML. In any case, upon acceptance, we could expand the experimental section.\n\n**Experiments:** We acknowledge that the experiments can be improved (and we are currently working on this), but respectfully disagree on characterizing them extremely insufficient for our purpose. The current experiments confirm and illustrate our theoretical findings:\n- Eigenvalue collision shows the problem of multiple orbits and how simple eigenvalue invariants fail to address them.\n- Synthetic graphs shows how multi-orbit improves over the previous SKSP.\n- Table 1 shows that multi-orbits can offer more expressive representations than eigenvalue invariants and the SkSP on real-world datasets like QM7.\n- Figure 5 shows the expressive power of DRkSP, illustrating advantages over SkSP and graph spectral-eigenvalue methods.  \n\nWe further improved our experiments in response to feedback. In particular, we investigated the relationship between DRkSP and 1-WL tests, showing that DRkSP is not less powerful nor strictly more powerful than 1-WL (see https://anonfile.io/f/LRH87kqC). This suggests that kSP could improve the expressibility of standard GNNs, which are known to be less powerful than 1-WL [1, 2]. Indeed, a preliminary experiment on PROTEINS shows this is the case https://anonfile.io/f/yqPzRNyf\nFurther experiments on QM9 and ZINC in the setting of Table 1 validate the scalability of the proposed method, with the multi-orbit representation offering comparable results to other representations https://anonfile.io/f/Y7HOKwqq\nMore thoughtful experimental settings could show further advantage of multi-orbits on real-world datasets. Please check the replies to other reviewers for more information.  \n\nWe hope this rebuttal addresses the reviewer’s concerns and are happy to contribute with further information otherwise.\n\n[1] Morris, Christopher, et al. \"Weisfeiler and leman go neural: Higher-order graph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.  \n[2] Xu, Keyulu, et al. \"How Powerful are Graph Neural Networks?.\" International Conference on Learning Representations.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "yes", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "1. The author claims that there is no increase in computational cost and has conducted an analysis on computation and complexity. However, there is no visualization comparing the complexity with existing algorithms.\n\n2. The structure of the article is confusing. It spends a large amount of space introducing basic concepts, such as self-loops, node features, and edge features et al. However, the experiments are extremely insufficient, with almost no experimental results presented except for Figure 5.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. The author claims that there is no increase in computational cost and has conducted an analysis on computation and complexity. However, there is no visualization comparing the complexity with existing algorithms.\n\n2. The structure of the article is confusing. It spends a large amount of space introducing basic concepts, such as self-loops, node features, and edge features et al. However, the experiments are extremely insufficient, with almost no experimental results presented except for Figure 5.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "10KpD7dPS4", "reviewer": "Reviewer_VVhY", "summary": "The paper generalizes the Skew Spectrum to obtain permutation invariant and isomorphism-invariant to graph embeddings. In detail, the authors propose multi-orbit spectra that can handle attributed graphs, multi-layer graphs and hypergraphs. Then $k$-Correlation Spectra is introduced to theoretically characterize the trade-off between complexity and expressivity, which is further extended to Doubly-Reduced $k$-Spectra. The theoretical results are supported by simulation and experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**References:** Thank you for the references, we will include them in our manuscript.\n\n**Introduction:** More introductory material would help reach a broader audience, but the page limits presents a substantial challenge. Upon acceptance, we will consider both leveraging the extra page to revise the introductory material and extending the appendices to include a broader discussion on graph invariants, GNNs expressivity, and group theory.\n\n**WL hierarchy:** We thank the reviewer for the great suggestion. Relating our (general non-reduced) k-Spectra (kSP) to the WL hierarchy is very interesting, since understanding this relationship helps clarify the use of kSP in more advanced learning algorithms like GNNs. Preliminary analysis shows that kSP provides an alternative expressivity framework, since k-WL tests look at nodes and distinguish them based on having certain neighbors; kSP count different edge structures (see Intuition in Sec. 4). To investigate the relationship further, we extended our experiments on Doubly-reduced k-Spectra (DRkSP) to show that they are neither strictly less powerful than 1-WL nor strictly more powerful. Indeed, for undirected graphs of 7 nodes, we have that the concatenation of DRkSP for different values of k forms a complete invariant, while 1-WL tests, even with 50 iterations, report 22 collisions. On the other hand, on a dataset made of chordal graphs, 1-WL tests make 2 collisions and DRkSP 10. We updated our Figure 5 to report these results: https://anonfile.io/f/LRH87kqC\n\n**GNNs:** Most Message Passing Neural Networks (MPNN) architectures are at most as expressive as 1-WL tests [1, 2], while our previous experiment shows that DRkSP can be more powerful than 1-WL test. Corollary 3.14 of your second reference states that Spectral invariant GNNs can count cycles and paths up to 7 vertices, but non-reduced kSP, for high enough k, also counts paths and cycles on more than 7 vertices, see Intuition in Sec. 4. This suggests that DRkSP and further heuristics on kSP could be used to improve the expressivity of GNNs.\n\nWe came up with three ways how to embed kSP into GNNs:\n- Precompute the whole-graph embedding with kSP and concatenate it to the GNN layer that outputs the graph embedding, just before the fully connected layer that computes the prediction.\n- Compute subgraph invariants in the node aggregation step using kSP.\n- Compute subgraph invariants in the pooling layer using kSP, instead of other invariants like sums or max of all node labels.  \n\nIn all the three cases, we could introduce some learnable parameters, such as weights in the direct sum terms of our Eq. 8 to tune the relevance of the orbits. We will include this discussion in the manuscript.  \n\nTo prove the point, we extend our experiments and report preliminary results. Following the first approach, we extend the HGP-SL architecture [3] and test on PROTEINS, using their code and filtering for graphs having between 3 and 30 vertices. We try a dropout rate of 0.5 and 0.2, use a learning rate of 0.001 and a batch size of 32, training the model for a maximum of 1000 epochs and using early stopping on validation loss. The results show that the DRkSP improves the learning capability and that both higher correlations and multiple orbits help: https://anonfile.io/f/yqPzRNyf\n\n**Real-world datasets and scalability:** To address the concern on scalability and practicality, in addition to our previous experiment on QM7, we added some preliminary experiments on two suggested real-world datasets: QM9 and ZINC. These two datasets contain 130,831 and 249,456 molecules, respectively. We processed these datasets on a desktop, using our non-optimized python implementation. This experiment extends Table 1 to the two datasets:https://anonfile.io/f/Y7HOKwqq\n\nFor QM9 we used the first 100,000 molecules for training and the remaining 30,831 for testing. The 3-orbits include the adjacency matrix, the sum of the 4 edge attributes, and the 6th node feature. For ZINC, we used 220,011 molecules for training and 5000 for testing. The 3-orbits include the adj. matrix, the edge attributes, and the node features. The multi-orbit 3SP reports comparable results to the baselines, improving over the single-orbit on QM9. These experiments help prove the scalability of the approach. We are positive that a more thoughtful use of our kSP (including higher correlations, non-reduced versions, and further tuning) will lead to more competitive results.  \n\nWe remain available for further discussions/clarification.\n\n[1] Morris, Christopher, et al. \"Weisfeiler and leman go neural: Higher-order graph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.  \n[2] Xu, Keyulu, et al. \"How Powerful are Graph Neural Networks?.\" International Conference on Learning Representations.  \n[3] Zhang, Zhen, et al. \"Hierarchical graph pooling with structure learning.\" arXiv preprint arXiv:1911.05954 (2019).", "claims_and_evidence": "The claims are well supported by evidence including theoretical analysis and experiments.", "methods_and_evaluation_criteria": "The simulation part is convincing.\n\nHowever, experiments on the real-world benchmarks can be strengthened. Particularly, the only real-world dataset is QM7, and more standard benchmarks including Zinc, QM9, ogbg-molhiv/molpcba, and Long Range Graph Benchmark, is strongly encouraged to validate the practical performance and scalability of the method. Moreover, the base models (e.g., XGB and Linear) do not include state-of-the-art GNNs, which is questionable. How to integrate (doubly-reduced) $k$-spectra into existing GNNs, and what is the effectiveness?", "theoretical_claims": "I check the correctness and did not find major flaws.", "experimental_designs_or_analyses": "See Methods And Evaluation Criteria part.", "relation_to_broader_scientific_literature": "The paper is related to literature in mathematics, including group theory, harmonic analysis, and graph isomorphism problem.", "essential_references_not_discussed": "The paper lacks discussions on established work for graph invariants/expressivity [1, 2, 3]. It would also be better (but not necessary) to include some machine learning papers based on group theory [4, 5]. \n\n\n[1] Zhang, B., Zhao, L., & Maron, H. (2024). On the expressive power of spectral invariant graph neural networks. *arXiv preprint arXiv:2406.04336*.\n\n[2] Gai, J., Du, Y., Zhang, B., Maron, H., & Wang, L. (2025). Homomorphism Expressivity of Spectral Invariant Graph Neural Networks. *arXiv preprint arXiv:2503.00485*.\n\n[3] Zhou, C., Wang, X., & Zhang, M. (2023, July). From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks. In *International Conference on Machine Learning* (pp. 42742-42768). PMLR.\n\n[4] Batatia, I., Geiger, M., Munoz, J., Smidt, T., Silberman, L., & Ortner, C. (2023). A general framework for equivariant neural networks on reductive Lie groups. *Advances in Neural Information Processing Systems*, *36*, 55260-55284.\n\n[5] Dehmamy, N., Walters, R., Liu, Y., Wang, D., & Yu, R. (2021). Automatic symmetry discovery with lie algebra convolutional network. *Advances in Neural Information Processing Systems*, *34*, 2503-2515.", "other_strengths_and_weaknesses": "This paper is valid in theory and is well written. It might be better for the authors to include more detailed introduction in group theory/graph invariants etc. to improve the readability for those readers not so familiar with this specific topic.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* Can you connect the framework with some existing GNN expressivity framework, such as the WL hierarchy?\n\n* Can you elaborate on more large-scale/real-world datasets and more state-of-the-art models?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Generalization of the spectra to attributed graphs is a valuable contribution that can be utilized across the field; the theoretical ground is solid. Empirical results on 1WL expressivity as a results of the rebuttal to VVhY showcase the practical importance of the method. I suggest to accept the paper, it presents valuable new ideas to ICML, and is presented quite clearly.
Decision: Accept (poster)