Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networks
Authors: Mitchell Keren Taraday
Almog David
Chaim Baskin
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
message passing neural networks
invariant aggregation
Primary area: graph_neural_networks
TL;DR: We introduce  SSMA, a novel aggregation for MPGNNs which  treats the neighbor features as 2D discrete signals and sequentially convolves them, inherently enhancing the ability to mix features attributed to distinct neighbors.

Abstract: Message Passing Graph Neural Networks (MPGNNs) have emerged as the preferred method for modeling complex interactions across diverse graph entities. While the theory of such models is well understood, their aggregation module has not received sufficient attention. Sum-based aggregators have solid theoretical foundations regarding their separation capabilities. However, practitioners often prefer using more complex aggregations and mixtures of diverse aggregations. In this work, we unveil a possible explanation for this gap. We claim that sum-based aggregators fail to "mix" features belonging to distinct neighbors, preventing them from succeeding at downstream tasks.
To this end, we introduce Sequential Signal Mixing Aggregation (SSMA), a novel plug-and-play aggregation for MPGNNs. SSMA treats the neighbor features as 2D discrete signals and sequentially convolves them, inherently enhancing the ability to mix features attributed to distinct neighbors. By performing extensive experiments, we show that when combining SSMA with well-established MPGNN architectures, we achieve substantial performance gains across various benchmarks, achieving new state-of-the-art results in many settings.
We published our code at https://almogdavid.github.io/SSMA/.

Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networks
Mitchell Keren Taraday*
Almog David" Department of Computer Science Technion
Department of Computer Science Technion Haifa, Israel
Haifa, Israel almogdavid@@maii.coo com
butovsky wwm.mmihhellmmmalli... @gmail. com
Chaim Baskin
School of Electrical and Computer Engineering
Ben-Gurion University of the Negev
Be's er Sheva, Israel
chaimbaskin@bgu.co ac. i1
Abstract
Message Passing Graph Neural Networks (MPGNNs) have emerged as the pre- ferred method for modeling complex interactions across diverse graph entities. While the theory of such models is well understood, their aggregation module has not received sufficient attention. Sum- based aggregators have solid theoretical foun- dations regarding their separation capabilities. However, practitioners often prefer using more complex aggregations and mixtures of diverse aggregations. In this work, we unveil possible explanation for this gap. We claim that sum-based aggre- gators fail to "mix" features belonging to distinct neighbors, preventing them from succeeding at downstream tasks. To this end, we introduce Sequential Signal Mix- ing Aggregation (SSMA), a novel plug-and-play aggregation for MPGNNs. SSMA treats the neighbor features 2D discrete signals and sequentially convolves them, inherently enhancing the ability to mix features attributed to distinct neighbors. By performing extensive experiments, we show that when combining SSMA with well-established MPGNN architectures, we achieve substantial performance gains across various benchmarks, achieving new state-of- state-of-the-as thethhe-rt results in many settings. We published our code at https: /almmoddaaidd wew.dd.gtttt. github. io/iio//S/ Lo/SSMA/
Introduction
basssge--assiigg Graph Neural Networks (MPGNNs) have established themselves as the major workhorses for graph representation learning the past decade (24). These models have been proven to be effective graph-structured problems in a variety of domains, ranging from social
networks (18) natural sciences [14 23 4 and having
non-trivial applications in computer
vision and natural language processing [26]] 33 45 28).
Such renowned models of this nature owe their success to their high efficiency, along with good generalization capabilities and simplicity. typical MPGNN takes graph-structured data containing node and edge features input. It then iteratively updates node representations by combining their egocentric view with a symmetrized aggregation of their proximate neighbor features.
Equul contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The key insight regarding the expressive power of such models is their equivalence to the Weisfeller-Lehmaall (WL.) graph isomorphism test [47] Consequently, past research directions were majorly directed toward developing mod- els that surpass the vanilla WL test by tackling the graph learnability problem from various per- spectives, including stronger notions the WL test| 31 351, spectral graph methods 44 13 44
DeepSets polynomial
w (t-l) (ta)) (t-w)
Generalized DeepSets polynomial
(t- fu- toll o (2l2)))
1F
(l- for oo (t- (wt 4u004
and graph transformers
49 36].
However, one subtle but often overlooked detail in such expressivity analyses is the existence of Hash function, which compresses the neighbor features into a fixed-sized representation. Such Hash function need not only be injective but also differentiable and efficient in terms of memory and computation. The seminal DeepSets paper 150 showcased such sum-based construction for the Hash function. While this construction was very simple and computationally efficient, the theoretical representation size required in this construction is exponential in the node feature dimension. Although the bound on this representation size was improved in later works [17 I sum-based aggregations seem to lag behind the aggregators used in practice [
1
Figure 1: An efficient and provable generalization of the DeepSets polynomial to vector features.
In this work, we suggest that a possible explanation for this gap the inability of sum-based aggrega- tors to "mix" features belonging to distinct neighbors. We formalize the "neighbor-mixing" property and show that sum-based aggregators have limited neighbor-mixing capability. This observation is later verified by conducting an experiment showing that sum-based aggregators struggle with approximating even very simple function requiring neighbor-mixx mixing.
With this motivation in mind, we propose new aggregation module that treats the neighbor features as two-dimensional discrete signals and sequentially convolves them hence coined as Sequential Signal Mixing Aggregation (SSMA). SSMA has provably polynomial representation size m O( d) (where n is the number of neighbors and d is feature dimensionality). The theoretical construction underlying SSMA provides positive answer to lasting mystery regarding DeepSets 50) "Can the DeepSets polynomial be efficiently generalized handle vector features?"'a as depicted in Figure
As later investigated, the convolutional component in SSMA allows it to directly mix features attributed to distinct neighbors, inducing a higher-order notion of neighbor mixing. We then discuss some practical aspects of SSMA. Particularly, we discuss how to implement it in a computationally efficient manner, how scale larger graphs and how to make it casier to optimize.
Finally, we demonstrate that when integrated into a wide range of well established MPGNN architec- tures, SSMA greatly enhances their performance. We observe significant gains across all benchmarks tested, including the TU datasets 32). open graph benchmark (OGB) [21] datasets, long-range graph benchmarks (LRGB) [16] datasets and the ZINC [19] molecular property prediction dataset achieving state-of-the-aat results in many settings.
Contributions. Our contributions may be summarized follows:
1. We define the notion of limited neighbor- nighhor-mixing power. We verify this idea by conducting an experiment simple and natural synthetic task.
and show that sum-based aggregators have
2. We propose Sequential Signal Mixing Aggregation (SSMA) an aggregation module of di- mension m = On? d) which treats the neighbor features as discrete signals and sequentially convolves them. The theoretical construction underlying SSMA builds upon the DeepSets polynomial, efficiently extending it to multidimensional features.
3. We introduce a few practices for stabilizing the optimization process of SSMA and show how scale it to larger graphs.
4. Finally, we conduct extensive experiments showing that enriching prominent MPGNN architectures with SSMA yields large improvements on variety of benchmarks, achieving oftte-of-theaale art results.

---

2 Preliminaries and related work
Let X' be some domain. We interested in representing multisets (sets in which repeated elements are allowed) over that domain. We denote multisets by ((=1...,,T_,] where each x; E X, and denote by M,, = (X)) the n-tuple space over X. We seek (possibly learnable) permutation invariant mapping f Mn + RT separating distinct multisets 2 When combined with a learnable compression network go : I X, their composition - go f can be utilized an aggregation module for MPGNNs over the domain X.
interested in continuous features, namely the domains X' = R and X' R We consider the symmetry group 9 = S,, acting on Mn = R" by [o.x0] = (() and on M, = Rnx by [o.X] = X L(ijj correspondingly. It is widely agreed that finding a good representation f: M, + R for these domains is crucial for building better aggregation modules 7 and has
Particularly,
direct influence on the performance of the model on a variety of downstream tasks 44 12 27 40).
DeepSets [50] was the pioneering work introducing sum- sum-based aggregator with a provably finite representation size m: ((1 Zn B)) = <<== x(xx)) where ø : IR - R and p R + Rd.
Their construction consisted of "hand-crafted" moment-based features. Despite being efficient for scalar-based features, the representation size grew exponentially with the node feature dimensionality, m E (((((t)) ). This upper bound was later improved O(n2d) and eventually to a tight (ndd (I7). While moment-based features served as powerful tool for achieving theoretical separation, learnable neural features are favored over such hand-crafted features in practice. As was unveiled, neural features can achieve theoretical separation as well, long as non-polynomial analytic activations are used M
Despite their clear theoretical advantages, sum-based aggregators seem to have limited performance in practice 12, [27). Consequently, many works focused on different species of permutation invariant aggregators. For instance, attention-basee aggregators have been proposed to capture the most important signals incoming from the neighborhood 2 77. Others suggested using mixture of symmetric aggregators such as min, max, mean, sum, std as each of these aggregators helps separate different kinds of multisets [47 12]. Other works focused on aggregations preserving intrinsic properties of the neighborhood data such variance and fisheriinformation [38] 30)
Another intriguing type of work deals with the relaxation of the neighbor ordering invariance con- straint. Particularly, regularizing recurrent neural setwork-bbsed aggregations to maintain permutation invariance either by choosing a random neighbor permutation (20) or by explicit regularization
terms 100 34 has raised some interest.
3
On the limited neighbor-mixing of sum-based aggregators
Despite their provable separation power, sum-based aggregators seem lag behind other aggregators used in practice [1]. We claim that possible explanation for this phenomenon lies in their inability to "mix" the neighbor's 's features, in that the mutual effect of perturbing the features of two distinet neighbors on each aggregation output is very small. In practice, many downstream tasks require high "mixing" values as the aggregator should mix information from different distinct neighbors to produce a useful representation for tackiling the downstream task.
Definition 3.1. Let 7 Ra + IR be some aggregation function that is continuously twice differentiable. We define the neighbor mixing of the f-th aggregation output with respect to the neighbor pair (i.
82
(6)
(0) (1) LT.)
mix
At an intuitive level, sum-based aggregators have small mix values as the result of the local pooling operation is summed across the neighbors. Namely, without explicitly "mixing" features from distinct neighbors before the summation. Indeed, given r(f(=
T.,,. t. Eh Φ(xx) we have:
"meaning that distinct multisets should be mapped to distinct representations, hereby requiring sufficiently large representation dimension
3

---

0²
(2) (Ix) =
Ōr,du,
Formally, to account for mixing that may occur in any subsequent (global) transformation we have the following proposition:
Proposition 3.2. Let 7 (i. Fnlll p <Ek= ((xx)) where R E local operator and p I IRd is a pooling operator that is continuously twice differentiable. Then, we have Vi +
m [|Jo(z))l2
| Σ (oxe))) [14((1))122
H
Where Jo).) is the Jacobian matrix of & and H (.) is the Hessian matrix corresponding to l-th (i)
output of p. Particularly, for typical choices of & and p it follows: mix;, 0(1001)) where 0 is the concatenation of the parameters in à and p.
The proof of Proposition 3.2 given in Appendix A.I
Motivated by the above observation, we propose a new species of aggregation module which is convolution-based rather than sum-based.
4 SSMA- Sequential Signal Mixing Aggregation
4.1 Warm-up: DeepSets polynomial from convolutional point of view
Let ([=1,... ..., )r be scalar multiset. We define its DeepSets polynomial by considering polynomial of variable t having the multiset elements as its roots:
(t)
Its coefficients, we denote by (x), are permutation invariant functions. Moreover, the (ex (+)) form an ensemble of invariant separators F
Instead of describing polynomial its coefficients, one represent polynomial by evaluating on some fixed set of points. Given set of n + fixed points, the polynomial may represented by evaluating its value these points. One can switch from this representation back to the coefficients by solving system of linear equations, which always has a unique solution. Now, by allowing the evaluation points to be complex. discrete Fourier transform (DFT) of the polynomial coefficients:
choose them the roots of unity. By doing so, we get the
(,(x)
Σ ex(x) k=
2
=;.0...,)))
(5)
Next, we denote the factors in (t( = Ih (t) where pr(t) == Lú. The (padded) coefficients of each pt(t) are then given by the affine transformation:
h(w,) [- v. 1, 0] g=+1
(6)
The nice thing about representing polynomial by evaluating its values at list of fixed points is that polynomial multiplication becomes point- wise. It can be deduced that the coefficients of pz(()) can be computed by transforming the coefficients h (ax) of each pt(t) (t) to the Fourier domain, performing
'If for two multisets we have en (x) = et (y) for all < k < m, then pa(() = (t(t) for all t, and therefore each one of the roots of the left-hand side polynomial corresponds to some root of the right-han hand side polynomial. An inductive argument shows that this implies that both polynomials have the same roots.

---

elementwise multiplication and then transforming back to the coefficients domain. According to the circular convolution theorem, this exactly amounts to sequentially convolving the coefficients h(z,). We combine the above ideas into the following theorem:
Theorem 4.1. Scalar multisets aं map Joon::
((1 ..., Fn HI can be represented by an invariant and separating
Scono
h(x,)
(7)
Where h. R > I is an affine map. separators is m = n + O(n).
+ is the circular convolution operator, and the number of
Theorem simply states that sequential convolution can be utilized to compute the renowned DeepSets polynomial coefficients. While not particularly surprising, Theorem 4.I shows that the coefficients of the DeepSets polynomial can be efficiently computed and directly utilized as multiset representation. Moreover, paves the way for our construction, seen the next section.
4.2 Efficient generalization to multidimennsonal features
"How does the DeepSets polynomial can be efficiently extended to handle vector features?"
The key idea underlying our answer to this question to encode each feature vector as another polynomial, and then to reduce the problem to the scalar case.
Generalized DeepSets Polynomial
We encode each element X; belonging the multiset X ((X1,..., Xn)] a polynomial of another variable 2:
Enc (X)
11-1
(8)
Then, we can perform a reduction to the scalar case by replacing each X, with Enc(X.))
(t 2) == t- Enc(X:) = -t-
Σ
Xij
(9)
3=1
And define the generalized DeepSets polynomial:
= II (t,
Σ
Cke (X) th
(10)
==1
k.l
Where exr(X) is the coefficient of 2f in (x(1, 2). Note S k S while 0 S n(d 1).
Opposed the scalar case, it is evident why the obtained coefficients (x)e(X)):: in the above construction form an ensemble of separators. We prove injectivity by utilizing ideas from ring theory, particularly the notions of unique factorization domains (UFDs) and Gauss's 's lemma in Appendix A.22
We can now repeat the steps in Section 4.1 to achieve actual representation. We compute the coefficient matrix of each (t, z) and sequentially perform two-dimensional circular convolution.
This leads to an analogous theorem for the d-dimensional case:
Theorem 4.2. Vector multisets X ([X1, ... map Jcovvi
1..,. X }} can be represented by an invariant and separating
feom X)
+ (X.)
(1I)
Where T TRd R xm2 is affine map, number of separators is m = m. X m2 = (n + ()(ndd - + +1) O(?
+ is the 2D circular convolution operator and the
The full proof of Theorem 4.2 is given in Appendix A.3

---

74
0% a
Visualization of the higher order notion of neighbor mixing. We visualize the convolution result h for 3-dimensional features, considering 2 neighbors u, v (left) and 3 neighbors u, v, w (right). We demonstrate for each n-tuple matching feature per node, the corresponding n-th order derivative of exactly one entry of h is 1.
Figure 2:
4.3 How does circular convolution impact neighbor Mixing?
Let U1,.... Ub !!' be discrete signals representing the locally- neighbors before being aggregated. For the sake of simplicity, we slightly override the notation in this section, and refer to the j-th element of the i-th signal as ui with j starting from O.
The core factor causing the neighbor mixing bottleneck of sum-based aggregators h Σ i=1 u, lies within the fact that no mixing done in the representation, but only the MLP compressor that comes afterward:
02 @u Jul
(12)
the contrary, each element of sequential circular convolution = 26 ... @ uh is composed of sums of terms of the form u² u
uin Particularly:
h
u
(13)
f1 tr.... mk (mod
This implies that the convolutional representation achieves, in fact, a generalized, higher-order notion of the mix values:
8m
4A ji, S Ek:
h
(14)
Ou Ou Ou.
This notion of bigher-order neighbor mixing is visualized in Figure We refer the reader to Ap- pendix A.4 for further theoretical discussions on the stability of permutation-inee invaariian representations.
2
4.4 Practical considerations
Combining Theorem 4.2 with an MLP compressor yields the "vanilla" version of SSMA: first applies the local affine map, then computes 2D cireular convolution across the neighbor axis and finally compresses the result back using MLP as a universal compressor. The circular convolution implemented by applying FFT, performing product aggregation along the neighbor axis and then transforming the result back using IFFT. As "scatter, saar__mull"" is not implemented for complex numbers in standard libraries, we convert complex values to their polar representation in which multiplication is equivalent to multiplying the magnitudes and summing the arguments. The "vanilla" version of SSMA is presented in Figure 3
We now suggest a few practical adjustments to the "vanilla" version of SSMA:
Normalizing the circular convolution. As SSMA performs a product over the neighbors' axis, the optimization process of the vanilla SSMA might get unstable. To address this instability, we normalize the clement-wiss magnitudes of the product by taking their geometric means.

---

FPR
Figure 3: Visualization of the Sequential Signal Mixing Aggregation. Left: demonstration of the aggregation stage in an off-the-shelf MPGNN layer. The goal is create compressed view of t's incoming neighbors. Right: our proposed aggregation. We convert the neighbor features into woo-dimensional discrete signals. We then apply circular convolution by applying 2D FFT, performing pointwise multiplication and transforming back using IFFT. Finally, we compress the result back into d-dimensional vector using a multi-layer perceptron universal compressor.
Low-rank compressor. Since the number of parameters in the MLP compressor rapidly increases with the representation dimension m, we opted for single linear layer as our compressor. To accommodate higher number of neighbor slots and allow for larger hidden dimension, we reduced the number of parameters the linear layer by splitting into consecutive linear layers that squeezes the representation to low dimension and than expands it back. This effectively performs low-rank factorization of the weight matrix of the original single linear layer.
Neighbor selection methods. The representation size of the vanilla SSMA m = On? d) may become prohibitively high in dense neighborhoods (e.g in transductive settings). To address this issue, we employ two neighbor selection techniques that reduce the original neighborhood to new set of neighbors. The first technique simply draws most random neighbors without replacement. The second technique draws inspiration from Graph Attention Networks (GAT) and attention slots 29 42 and map the neighbors into attention slots. The attention coefficient for the edge e for the k-th slot is expressed as follows:
e (h,, h2) Leaky bb (x,
(15)
(k) softmaxyea EyeN... exp(ex(h,, hy:))
(16)
Where au, by E Rd are per-slot learnable weight vectors. Thereafter, k-th slot for the i-th node produced by considering the weighted average of the incoming neighbors:
aij
hi
(17)
(6)
5
Experiments
5.1 Synthetic task
To empirically demonstrate the success of SSMA in managing tasks characterized by high neighbor mixing (opposed to sum-based aggregators), we introduce synthetic regression task we name SUMOFGRAM. In this task, sample random neighbor features and then generate the labels by considering the sum the Gramian matrix corresponding to the neighbor features.
In some sense, the SUMOFGRAM task is the "simplest" task that involves neighbor mixing:
2
Vi # j mixi,
SUMOFGRAM (1) ...,..
+|
(18)
Ox,Oa,

---

Regression errors SumOfGram task
Activation
ReLl
SLU
101
10A
Regresion
10a 10 10a
10'
Number trainable parameters
Figure 4: SUMOFGRAM train and test regression L1 errors for different activation functions. The sum aggregator (not dashed) performs poorly and fails to scale with the capacity of the aggregation module, even when used in conjunction with analytic activations. On the contrary, SSMA (dashed) consistently achieves low regression errors and scales well with the number of learnable parameters.
We train both the sum aggregator and our proposed Sequential Signal Mixing Aggregation until convergence with varying representation sizes m on the SUMOFGRAM task.
As may be observed in Figure 4 sum aggregators fail at this task, even when used in conjunction with analytic activations, which as claimed previously [1 sufficient achieve separation. This shows that sole separation is insufficient for performing arbitrary downstream tasks. On the contrary, SSMA has low regression errors, consistently along different activation functions.
5.2 Benchmarking SSMA
Experimental Setup. We test the effectiveness of SSMA by incorporating it into popular MPGNN architectures. We evaluate both original and augmented architectures across a wide range of bench- marks. These benchmarks cover learning in both the transductive and inductive settings, node and graph-level prediction tasks, regression and classification problems, feature-oriented as well as purely topological data and tasks that involve challenging neighborhood configurations including dense neighborhoods and distant neighbor dependencies. As SSMA introduces learnable parameters, we ensure fair comparison by maintaining an equal total parameter count to that of the original archi- tectures each experimental setting, adjusting the architecture 's hidden dimension adhere the budget constraints. For a detailed discussion on the parameter budget in each experiment, please refer to Appendix C.4 Given the budget for each experiment, we conduct a hyperparameter search (HPS) on SSMA parameters to find the best configuration. We further perform ablation studies to closely examine the effect of each hyperparameter, as detailed Appendix F
Results. We observe substantial performance gains across all tested combinations of benchmarks and MPGNN architectures. Notably, the most significant relative improvements were observed on the IMDB-B benchmark, which lacks node and edge features. This phenomenon is likely attributed to SSMA'S neighbor mixing capabilities, enabling to learn joint topological relationships among neighbors. The Improvements observed on the LRGB [16] datasets indicate that SSMA better extracts relevant neighborhood information to be propagated to distant parts of the graph. Additionally, the experiments on the OGBN networks (OGBN-Arxiv and (GBN-Products) 21I confirm that SSMA is robust to dense neighborhoods and highlight the efficiency of its attentional neighbor selection mechanism. Another noteworthy observation is that SSMA utilizes the hidden dimension more effectively. Since we use the same parameter budget, experiments with SSMA employ lower hidden dimensionality than those using "sum' aggregation. This is because SSMA allocates learnable parameters, whereas 'sum' aggregation does not. Despite a smaller hidden dimension, SSMA outperforms 'sum' aggregation, indicating efficiency retaining relevant information for downstream tasks. Benchmarks for more common aggregation functions is in Appendix F

---

ZINC [99 using sum aggregation as baseline. We report the TU datasets' accuracy mean and STD of a 10-fold cross cross- validation run. For the ZINC dataset, we report mean MAE and STD on the test set according to 5 distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Table 1: Results for TU datasets [32
Module
ENZYMEST
PTC-MR 1
MUTAG f
PROTEINS
IMDB-B
ZINC +
GCN 24
51.0210.63
59.852404
84.2349.86
75.3924.53
68.8023.49
0.347
GCN SSMA
54,8347.55
62.29:9.33
89.7926.71
76.28#3.19
75.2+2.
0.280=#.02
GAT 4
50.67+492
65.53+8.41
75.51=11.72
73.32=3,08
51.026.07
0,386=00025
GAT
56.67#3.22
66.41=5.99
89.1924.58
80.18=0.1
74.5
0.223+8.028
GATv2
G
44.83+596
56.4727.57
17.26213.15
73.0423.35
47.025.27
0.396:40.06
GATv2 + SSMA
52.5008843
61.6426.80
88.80=11.00 1,80
75.28
72.8+4.92
0.235
GIN 48
49.50+
60,4649.11
06.45+8.17
73.30=5.11
71,343.97
0.252++0007
GIN SSMA
51,692804
61.28+9.22
90,51
75.19
74.1=5.02
0.222
GraphGPS 37
48.33 71
61.4 61.41
79, 10.91
73.76=6.05
69 69.625554
0,251
GraphCiPS SSMA
49.17#3.15
63.024499
86,07=7.95
75.56+4.24
71.1
0.22e00.05
PNA 122
52.50 60
58.41
84, 19=9,
74.86+4.57
71.944.46
0. 0,192+0.00 001
88.29:8.46
ESAN" 8
69. 2dxi5
91.1170
75.9144.3
77.123.0
0. 0.10220.003
ESAN SSMA
77.8945.62
96.3263.37
80.6924.1
80.622.15
0.09628.002
Improvement (%)
7.2
3.7
20.36
Table Test performance on the OGB 22 & LRGB [6] benchmarks using sum aggregation as
baseline. indicates reproduced results while indicates the reported results from the relevant paper.
LRGB
OGB-N
OGB-G
Module
Peptides-f
Peptides-s
Arxiv
Products
molhiv
molpcha
A
MAE
Accuracy +
Accuracy
AUROC f
AP
GCN
24
61. 111.4
0.28an.01
65.62n.55
63.823.. 45
0.77anm1
0.212001
GCN
SSMA
63.321.42
0.2620.02
66.320.0
72.3
0.7920.01
0.2320.01
GAT 45
63.420.68
0.27an.11
62.1
60.617.65
0.75anoz
0.211001
GAT + SSMA
63,620.47
0.2620001
66.620.78
67.3:5.81
0,7920.01
0.2220.01
GATv21
63.121.34
0.2720.01
62.82
56.718.25
0.75anm1
0.1810.01
GATv2 SSMA
63.721.13
0.2620.01
64,720.62
66.42:370
0.7920.01
0.22#t001
GIN 4B
60.42n.96
0.2740.01
$4.12087
54.815.53
0.75an.01
0.212901
GIN SSMA
62,551.37
0,2620.02
66,4#1,52
67.0=5.79
0.7820.01
0.22#2001
GraphGPS 37]
58.81#1.22
0.2820.01
63. 68
48 89.
0. 0.76emaa
0. 1929010
GraphGPS SSMA
60.34:149
0.2720.01
66.7129.73
67.62
0.78e0.01
0.22+0001
PNA 122
57.021.17
0.2820.01
=9.1
45.6s216.52
0.75=n.0
0.1
PNA SSMA
61.1=1.75
0.27=0.03
66.320.81
63,923772
0.78e0.02
0.21=0001
ESAN 3
0.76e0.01
SSMA
0.83an.01
Improvement (%)
3.02
23.86
Conclusion and discussion
In this work, re-examined the field of aggregation functions in MPGNNs and introduced the Sequential Signal Mixing Aggregation, a new plug-and-play aggregation method with solid theo- retical foundation. We demonstrated its effectiveness architectures with different parameter budgets. Each component of our method was systematically examined and its contribution to performance is verified. We hope the observed performance gains will motivate further research into harnessing our aggregation for specific applications and developing more advanced aggregation functions for MPGNNs. Future research could address some limitations of our method, such as the representation size scaling quadratically with the number of neighbors and the need for explicit normalization due the instability of the convolution operation.
various datasets and message-passing

---

References
[1] I. Amir, S. J. Gortler, Avni, R. Ravina, and N. Dym. Neural injective functions for multisets, measures and graphs via finite witness theorem. In Shirty-seventh Conference Neural Information Processing Systems, 2023.
[2] J. Back, M. Kang, and J. Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference Learning Representations, 2021.
[3] B. Bevilaequa, F. Frasca, D. Lim, B. Srinivasan, C. Cai, G. Balamurugan, M. M. Bronstein, and H. Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representationss 2022.
[4] J. Bradshaw, M. J. Kusner, B. Paige, M. H. S. Segler, and J. M. Hemándezz-ooato. generative model for electron paths. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[5] X. Bresson and T. Laurent. Residual gated graph convnets. arXiv preprint arXiv: 2017.
[6] S. Brody, U. Alon, and E. Yahav. How attentive are graph attention networks? In International Conference Learning Representations, 2022.
[7] D. Buterez, J. P. Janet, S. J. Kiddle, D. Oglic, and P. Liò. Graph neural networks with adaptive readouts. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
[8] J. Cahill, J. W. Iverson, and D. G. Mixon. Towards bilipschitz invariant theory, 2024.
[9] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pages 257-266,
2019.
[10] E. Cohen-Karlik, A. B. David, and A. Globerson. Regularizing towards permutation invariance in recurrent models. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc
[11] G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1333 13271, 2020.
[12] G. Corso, Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, 2020.
[13] M. Defferrard, X. Bresson, and P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[14] D. Duvenaud, D. Maclaurin, J. Aguilera-Iparrauuin R. Bombarel, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. CORR, abs/1 599909929,,....... 2015.
[15] V. P. Dwivedi, C. K. Joshi, A. T. Luu, Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 2023.
[16] V. P. Dwivedi, L. Rampášek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, and D. Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22340, 2022.
[17] N. Dym and S. J. Gortler. Low-dimensional invariant embeddings for universal geometric learning. Foundations of Computational Mathematics, pages 1-41, 2024.
[18] W. Fan, Y. Ma, Q. Li, Wang, G. Cai, J. Tang, and D. Yin. A graph neural network framework for social recommendations, IEEE Trans. Knowl. Data Eng., 34(5)2003--047,, 2022.
10

---

[19] R. Hemezz-ombarrlli, J. N. Wei, D. Duvenaud, J. M. Hernández-Lobato, B. Sánchez-Lengelingg T. D. Hirzel, R. Adams, and A. Aspuru- Guzik. Auto-
D. Sheberla, J. matic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-22 276, 2018.
[20] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc.
[21] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:221 18 2223333, 2020.
[22] J. Irwin, T. Sterling, M. Mysinger, E. Bolstad, and R. Coleman. Zine: A free tool discover chemistry for biology. Journal of chemical information and modeling, 52, 05 2012.
[23] W. Jin, K. Yang, R. Barzilay, and T. Jaakkola. Learning multimodal graph-to-graph translation for molecule optimization. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[24] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[25] R. Kortvelesy, S. Morad, and A. Prorok. Generalised f-mean aggregation for graph neural networks. Advances in Neural Information Processing Systems, 36:34439-3440,, 2023.
[26] E. Kosman and D. D. Castro. Graphvid: It only takes a few nodes to understand a video. In
S. Avidan, G. J. Brostow, M. Cissé, G. M. Farinella, and T. Hassner, editors, Computer Vision- ECCV 2022 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXXV, volume 13695 of Lecture Notes in Computer Science, pages 195-212. Springer, 2022.
[27] G. Li, C. Xiong, A. Thabet, and B. Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint w7Xi:2206600779, 2020.
[28] X. Liu, X. You, X. Zhang. J. Wu, and P. Lv. Tensor graph convolutional networks for text classification. In The Thirty-Fourth AAAI Conference on Artificcal Intelligence, AAAI 2020, The Whirty-Secone Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8409-8416 AAAI Press, 2020.
[29] F. Locatello, D. Weissenborn, T. Unterthiner, A. Mahendran, G. Heigold, J. Uszkoreit, A. Doso- vitskiy, and T. Kipf. Object-centric learning with slot attention. Advances in Neural Information Processing Systems, 33:1 1525- 11538, 2020.
[30] L. Makinen, J. Alsing, and B. D. Wandelt, Fishnets: Information-optimal, scalable aggregation for sets and graphs, 2023.
[31] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2153-2164, 2019.
[32] C. Morris, N. M. Kriege, Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.0866:. 2020.
[33] M. Narasimhan, S. Lazebnik, and A. G. Schwing. Out of the box: Reasoning with graph convolution nets for factual visual question answering. CoRR, abs/1811.00553 2018
[34] E. Ong and P. Veličković. Learnable commutative monoids for graph neural networks. In The First Learning Graphs Conference, 2022.

---

[35] O. Puny, D. Lim, B. T. Kiani, H. Maron, and Y. Lipman. Equivariant polynomials for graph neural networks. In A. Krause, Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 28191-28222. PMLR, 2023.
[36] L. Rampásek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini. Recipe for general, powerful, scalable graph transformer. CoRR, abs/2205. 12254, 2022.
[37] L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
[38] L. Schneckenreiter, R. Freinschlag, F. Sestak, J. Brandstetter, G. Klambauer, and A. Mayr. GNN-VPA: A Second Tiny Papers Track at ICLR 2024, 2024.
aggregation strategy for graph neural networks. In The
[39] L. Schneckenreiter, R. Freinschlag, F. Sestak, J. Brandstetter, G. Klambauer, and A. Mayr. Gnn-vpa: A variance-preserving aggregation strategy for graph neural networks. arXiv preprint arXiv:2403.04747, 2024.
[40] S. A. Tailor, F. Opolka, P. Lio, and N. D. Lane. Adaptive filters for low-latency and memory- efficient graph neural networks. In International Conference on Learning Representations. 2022.
[41] S. A. Tailor, F. Opolka, P. Lio, and N. D. Lane. Do we need anistropic graph neural networks? In International Conference on Learning Representations, 2022.
[42] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint arxiv: 1090,,, 2017.
[43] Veličković, G. Cucurull, A. Casanova, A. Romero, Liò, and Y. Bengio. Graph Attention Networks. International Conference on Learning Representations. 2018. accepted as poster.
[44] X. Wang and M. Zhang. How powerful are spectral graph neural networks. ICML, 2022.
[45] Z. Wang, Q. Lv, X. Lan, and Y. Zhang. Cross-lingual knowledge graph alignment via graph convolutional networks. In E. Riloff, D. Chiang, J. Hockenmaier, and J. Tsujii, editors, Pro- ceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 349-357, Brussels, Belgium, Oct.-Nov. 2018. Association for Computational Linguistics.
[46] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pages 1871- PMLR, 2019.
[47] K. Xu, W. Hu. J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint ar Xrv: 1810.00000 2018
[48] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[49] S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim. Graph transformer networks. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc. E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 11960-119700 2019.
[50] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. Smola. Deep sets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
12

---

A Proofs and extended theory discussion
A.1 Proof of Proposition 3.2
Proof. Let us consider a general sum basedased aggregator: FI, = p(En=1 o(Ix)).
Then, have that for * j and for the E-th output:
mix
(19)
82
((x))
(20)
Dz
k=1
0
<((+a))
(21)
dz
dz
0
n
(xx))) [o(x;)
(22)
0ey
k=1
22
= ((WW) (o(x))
(23)
0vg
Jo(x,)" ST Hom
o(xx)) Jo(zz)
(24)
Hppo Σ (pp ((xx)) (s(an))
||,(11))12
(25)
Typically, the local operator é R2 - Ihm is of the form <(x) = [AAx b) where a an activation function applicd element- wise and A E mxd E Rm are learnable parameters. Usually [o'(z) is bounded by some small constant C1. Therefore, have:
Jo (z))l2 = [|diag(o' (Ax + b)) All S ||4
(26)
Moreover, the global pooling operator p R.m + Rd is MLP of the form:
p(z) = W2 o oW, + 31) + 82
(27)
where Wi E Rmxm B1 E Rm W2 E mdxm .2 E Rd.
Therefore:
d
d= 00 = W2 diag(o'(W1e B1)) W1
(28)
Let us denote:
(x) W|( diag(o (Woo B.)) = (W2[C,A) d'W + -114))
(29)
Then,
d²
d
dz2 (0
u (8) (z) Wi
(30)
dz
We compute dz
d (2) for each output dimension 1 < k < separately:
13

---

dz { u' (2)kk) d
d'
dz (W2le, k] o' (WWi +
(31)
W2 k) (", + B1 [k)) Wi :]
(32)
Summarizing this for all dimensions & yields:
d u (2) diaga (W2[e, k)) diag(o"(Wiz + B1)) W1
(33)
dz
So under the assumption |a" |a"()) S 02 we get the following bound on the Hessian norm:
p (=)112 c [WW[[] I|
(34)
(1) And the final bound on mix given by:
mix (2) c2 ot |122 [Wil] ||AIl 0(101))
(35)
14

---

A.2 Ring theory and the factorization lemma
ring is an algebraic structure that generalizes the notion of field. In particular, univariate and multivariate polynomials obey this structure. Formally, ring R is a set associated with two binary operations + (addition) and (multiplication) satisfying the ring axioms:
1. R is an abelian group under the addition operation.
2. R is a monoid under the multiplication operation:
(a) associativity: (a b) c = a (b c) for all a, b, R.
(b) existence of identity: there is an element E R such that: 1 a = a a.
3. Distributivety: a (b + e) = a b+ a. c and (b + c) a = b. a..a00 a.
A ring is said to be commutative if its elements commute under multiplication: b b a for all a, b. E R.
Given a commutative ring R, we can define its corresponding univariate polynomial ring denoted as R[X] by considering a set formal expressions Ei=o a; where n is a non non-negative integer and a;; E R. We consider X a formal variable and define addition and multiplication according to the ordinary rules for manipulating algebraic expressions. Each polynomial p E R[ has a degree defined max; a; o O. For each E R, we can define an evaluation map T, which takes some polynomial as an input and returns an element in the underlying ring by substituting = r. namely: T,(E X;X') Σi= a,r".
Multivariate polynomials can defined similarly by considering multiple formal variables. Alter- natively, note that since the polynomial ring of some commutative ring R is also commutative ring by itself, we can equivalently define multivariate polynomials by considering the ring of polynomials above R R[X], namely: (R(X))(Y) = R(X, Y].
An integral domain is nonzero commutative ring in which the product of any two nonzero elements is nonzero. In particular, any field is an integral domain, and any polynomial ring is an integral domain, given that its underlying ring is itself an integral ring. Am immediate conclusion is that R[x] and R[21..... _n are integral domains.
An irreducible element of an integral domain is non-zero element that is not invertible and is not the product two non-invertible elements. For instance, for every commutative ring R, every polynomial of the form x where R is an irreducible element of R(x))
unique factorization domain (UFD) is an integral domain in which every non-zero element of f can be written as product (an empty product if x is invertible) of irreducible elements p; of and an invertible element u: r = u II. Pt. This representation ought to be unique up to multiplication with invertible elements. The key fact underlying polynomial ring of a UFD is by itself a UFD (known as Gauss's 's lemma). In conjunction with the fact that any field F is a UFD, get that [[F1,,... ...; Zn.] is UFD for any amount of variables.
construction is the fact that
Lemma A.1. Ler p(t, 2) E R(t, 2] be some polynomial that can be factorized as:
p(t,2) = II u((2))
(36)
where uz(z) is some polynomial of Then, such factorization is unique to the order of the terms (1 wz())).
Proof. Gauss's 's lemma implics that [ttt, 2] > (R[)))[t is a unique factorization domain. Since every polynomial of the form t r(z) is an irreducible element in (I[z)))(), it follows that factorization of the form ptt, 2) = ( (=)) is unique up to permutation of the terms.
Corollary A.2. The coefficients of the polynomial px(t, 2) defined in Section 4.2 form an ensemble of sepurating invariants.
15

---

A.3 Proof of Theorem 4.2
Proof. Let (x 2) be the polynomial in the construction. Corollary A.2 implies that its coefficients form an ensemble of separating invariants. Consequently, we repeat the steps in Section 4. to get an analogous result Theorem 4.1 arriving the desired form.
We represent Fx (4, by evaluating its value grid of points (u,, 2b) where S nno
Specifically, we can choose == e ut1 and 26 == e - and to get the two-dimensional DFT of the polynomial coefficients:
72
Px(ue: Ug. 0b)
exe (ub)
Σ k,ł
Cke (X) .e
2nio
2x
(37)
k= 2=0
Again, by setting 4(X:) to be the coefficients matrix of pi(l, 2) = - 9X (z):
X
X :2
Xid
1
0
0
((X.)
(38)
we get that:
Eke (X) = F&D 2 F2D (+
(39)
Where the multiplication elementwise. According to the 2D circular convolution theorem, this exactly amounts convolving the vector coefficients of (t, 2)s:
Che X
xX)))
(40)
16

---

A.4 On the stability of permulation-invariint representations
Ideally, we would like our representation to be numerically stable. That is, to require that two distinct multisets are close to each other, then their representations should also be close to each other. and vice versa. This was formalized previously [ using the notions bi-Lipschitzness and Wasserstein distance as we now recapitulate.
Let X, be two multisets of d dimensional vectors with X
72.
Wasserstein distance. measure the distance between equally sized multisets C Rd using the notion of Wasserstein distance:
(X, Y) min - TES
Σ X T
(41)
Where ||-I| is the La norm over TRd
We are interested the bi-Lipschitzzess property whether there exist constants c, > such that:
Wp (X, Y) < [(x) - im/ C. (,
(42)
Unfortunately, it turns out that this notion of stability is unattainable any differentiable permutation- invariant representation. We prove this by generalizing such results for sum num-based aggregators [.]
Proposition A.3. Let f be some differentiable multiset representation. Then, there exist n, d such that for every >> 0 there exist X., Y. S I2d two multisets of size n such that:
[(x.) ( f(Y.) Se. CX,, Y.)
(43)
An independent proof for general invariant embeddings is given in
Proof. Let f be some permutation-invarree representation. We use the same construction as in and generalize the proof to arbitrary symmetric and differential representations.
We choose π = 2 and some arbitrary E N.
Let Xo, d Rd where d has unit norm, and consider Sn {[x0 hd, hd])-
We note that the Wasserstein distance (y So) is h. Thus, is sufficient to show that:
f(S.)
f(S)) f(Su)
lim
(44)
Since fs ; 2d + R is invariant we have that for every E IR:: fu(u, v) fl)
The differentiabilityy of la at (u, implies that for every sisd d:
fu(ui, ui + l,,,, Uds v) - (u
(u, v) = lim
(45)
h-+0
h us + i...., wa) fu(v, = detifa(v,u)
fu(v, u1,
lim h-+0
(46)
h
Particularly, this implies that fi (xo, xo) Satifa(xo. xo).
Using the differentiability of fa at (xo, xo) we can write:
(xo + 11. + +z)
(47)
fx xo) + >o 0xfx - + Σ
(xt:f((xoXxo) xo) + (1 (2))))))))1)
(48)
mm1
17

---

Plugging in 61 hd and 82 = -hd we get:
fu (xo + hd, xo - -hd) fx(x0,x0) xo)= =
(49)
. -d - Σ
Ostifk Oatifi(Xo,xx0) di + oh) ox(h)
(50)
All in all, we have:
f(Sh) f(So)
Σx (xx + hd, xo - hd) (xxxxxxo)
lim
limn 4-+0
(51)
h-0
h
h
Ek=1 [ox(h]]
[ox(h) 0
lim
lim
(52)
A-00
h
h
Meaning that for every > 0 there exists sufficiently small & such that:
((Sh) f(So)]| h =c c. (S, So)
(53)
18

---

B Complexity analysis
B.1 Theoretical analysis
In this section, we provide a theoretical complexity analysis of SSMA for both its "vanilla" and refined versions. We consider the total cost of the aggregation stage in a single MPGNN layer within a graph G = (V, E). We let d be the hidden dimension and m = my m2 be the total representation size. We let R be the number of slots in the refined version of SSMA. We first analyze the vanilla version of SSMA step-by-step:
1. Local affine layer: locally transforms each node by an affine transformation O([V) mm d).
2. Local FFT: the FFT computed per node yielding a cost of O(IVI m logg)))).
3. Product aggregation: The complex variant of scatter _mml aggregation - O [5| m).
4. Local IFFT: Same as stage
5. MLP compressor: We used linear layer compressor the original dimension O[[VI-m- dd).
All in all we get: O(m(d+ [ compared to the standard VI which is negligible slowdown. In the refined version of SSMA, consider the modifications we applied:
Neighbor selection: If the random neighbor selection used, then the cost is simply O(m - K | +|E) for this stage. Alternatively, if the soft-attentional neighbor selection is picked, the attention weights in Equation (T6) may be computed per edge and attention slot in total running time of Om K |V + K- [El) and the contents of the slots may be implemented using sum aggregation in O(m [E).
). We get total of O(m x- [V|+ El) for the random neighbor selection or O(m k (IVI + [E')) for the soft-attentional neighbor selection for this stage.
Other modifications: the normalization method does not affect the complexity of the ag- gregation. While the complexity of the MLP compressor is slightly reduced, the asymptotic complexity remains the same due the local affine layer bottleneck.
Application of SSMA on the new neighborhood: We consider the complexity obtained in the analysis of the vanilla SSMA and replace the number edges, |E). with & [V]. The complexity of this stage then becomes: O(m(d log(m))[VV + m [V] Omm(d + log(m) + ()))
All all, we get (m((d + log(m) + x) |E]) for the random neighbor selection refined SSMA ((m(d+log(mm + k) + mx El) for the soft neighbor selection refined version of SSMA.
B.2 Runtime measurement
To further show that SSMA scalable we computed the runtime of compared other common networks, we measured the runtime of the layer with our aggregation with and without attention, for each configuration we show the downstream task results. As can be seen in Table SSMA runtime comparable to other methods while achieving higher downstream task performance.
19

---

Table Comparison of the training and inference times in (ms) MPGNN++SSMA against PNA and GraphGPS. rSSMA indicates random neighbor selection while aSSMA indicates attentional neighbor selection.
Method
Train (ms)
Inference (ms)
Arxiv Ace. (%)
Proteins Acc. (%)
GIN rSSMA
2.768
0.988
64.217
73.921
GCN + rSSMA
5,286
1.322
64.834
74.308
GAT + ISSMA
5,996
1,453
64.902
75.197
PNA GPS
6.068
1.218
59.1
74.86
7.178
1.362
63.87
73.76
GIN + aSSMA
8.072
1.504
65.835
72.94
GCN + aSSMA
8.347
1.666
65.368
73.132
GAT + aSSMA
9.236
1.888
60.108
72.677
C Extended experimental setup
C.1 Datasets
TU Datasets (32. We conducted experiments on five widely used datasets, including four bioin- formatics datasets (ENZYMES, PTC-MR, MUTAG, and PROTEINS) and one movie collaboration dataset that relies solely on topological data small, detailed in Table they span diverse range of domains.
While these datasets are all relatively
The ENZYMES dataset consists of 600 enzyme graphs, where the task is classify each enzyme into one of six EC top-level classes. Nodes represent secondary structure elements (SSEs) and are annotated by type. An edge connects two nodes if they are neighbors along the amino acid sequence or among the three nearest spatial neighbors, with edge features indicating their type (structural or sequential).
The PTC-MR dataset contains 344 compounds labeled according to their carcinogenicity male rats. The MUTAG dataset consists of 188 chemical compounds, divided into two classes based on their mutagenic effect on bacteria. The PROTEINS dataset includes 1,113 protein molecules, with the task being multiclass protein function prediction. For all of the above datasets, nodes represent atoms, while edges mean that two atoms are connected.
As these datasets lack official train/validation//et splits, employ random 10-fold cross-vard validation for evaluation. The prediction task for all these datasets is multiclass classification, and we use accuracy as the performance metric.
The IMDB- IMDB-Binary Binary dataset is a movie collaboration dataset comprising 1,000 graphs. In each graph, nodes represent actors/actresses, with edges indicating co-appearance in movies. Collaboration graphs for the Action and Romance genres were generated ego networks for each actor/actress, and each ego network was labeled with the corresponding genre. The task is to identify the genre of an ego-network graph.
We benchmark on the ZINC dataset. Specifically, the subset of 12K graphs as defined in 15 from the full 250K ZINC dataset. The prediction task is to regress molecular property known as constrained solubility, which calculated as "logP SA cycle" " (octanol-vu -water partition coefficients, logP, penalized by the synthetic accessibility score, SA, and the number of long cycles, cycle). this dataset, node features represent the types of heavy atoms, and edge features represent the bonds between them. The ZINC dataset is widely used for research in molecular graph generation. We used the dataset versions available via PYG without any further preprocessing.
ZINC dataset 19
22
We conduct experiments on the commonly used ogbg- molhiv and ogbg-molpcba molecule datasets to assess SSMA on graph-level prediction tasks. In these datasets, each graph represents a molecule, with nodes corresponding to atoms and edges to chemical bonds. The node features are 9-dimensional, encompassing atomic number, chirality, and other atomic attributes such as formal charge and ring membership. We refer the reader code for further details. The prediction task involves accurately predicting molecular properties, represented as
OGB Graph property prediction 21.
20

---

binary labels, such whether molecule inhibits HIV virus replication. The bebg-molpeba dataset includes multiple tasks, some of which may contain 'nan' values indicating that the corresponding label is not assigned to the molecule. These datasets differ in size: ogbg-molhiv is smaller, while ogbg-molpcha medium-sized. The evaluation metries used are ROC-AUC for oghg-molhiv and Average Precision (AP) for ogbg-molpcba. We used the official train/validationttes splits provided by the OGB team.
OGB Node property prediction 211 We benchmark on two dense node-level citation graph datasets from OGB-N: ogbn-products and ogbn-arxiv. The login-products dataset is an undirected and unweighted graph representing Amazon product co-purchasing network. Nodes represent products sold on Amazon, and edges indicate co-purchased products. Node features are generated by extracting bag-of-words features from product descriptions, followed by Principal Component Analysis for dimensionality reduction. The prediction task multiclass classification to predict product's category.
The ogbn-arxiv dataset is smaller directed graph representing the citation network among Computer Science papers indexed by the Microsoft Academic Graph (MAG) Each node represents arXiv paper, and the directed edges indicate citations between papers. Node embeddings are created by averaging the embeddings of words in the paper titles and abstracts, computed using the skip-gram model over the MAG corpus. The task is to predict the 40 subject areas of the arXiv CS papers.
We used the graph obtained from the OGB python package without any preprocessing.
Long Range Graph Benchmark (LRGB) 16]. We benchmark on graph-level datasets from the Long-Rang: Graph Benchmark (LRGB): peptides-func and peptides-struct. Each graph in these datasets represents peptide, short chain amino acids shorter than proteins and abundant in nature. Each amino acid is composed of many heavy atoms, making the molecular graph of peptide much larger than that of small dikgelike molecule. Peptide graphs have low average node degree. Still, they have significantly larger diameters compared to other drug-like molecules, making them ideal for studying onn-range dependencies in Graph Neural Networks (GNNs). Both datasets use the same set of graphs but differ in their prediction tasks. Peptides-fun is multi-label graph classification dataset based on peptide function, while Peptides-struct based the 3D structure of peptides. More details can be found in the LRGB GitHub repository used the versions of the datasets available via PYG without any further preprocessing.
multi-label graph regression dataset
Dataset statistics.
The statistics of the datasets we used in our experiments are shown in Table
Table 4: The statistics of the datasets used in our experiments
Dataset
Avg. Nodes
Avg. Edges
Graphs
Avg. in deg
STD in deg
Median deg
ogbg-molhiv
25.51
54.94 56.22
41127 437929
2.15
0.77
ogbg-molpcba
25.97
2.16
0.71
ogbn-arxiv
169343
1166243
6.89
67.6
ogbn-products
2,449.029
123,718,280
50.52
95.91
mutag
17.93
39.59
188
2.21
0.74
2
enzymes
32.63
124.27
3.81
1.15
proteins
39,06
145.63
1113
3.73
1.15
ptc-mr
14.29
29.38
344
2.06
0.81
indi-binary
19.77
193.06
1000
9.76
7.43
zinc
23.16
49.83
12000
2.15
0.72
peptides-fund
150.94
307.3
15535
2.04
0.79
peptides-struct
150.94
307.3
15535
2.04
0.79
2
21

---

C.2 Preprocessing
We did not modify the features of the graph topology in any of the experiments except the following cases:
For purely topological datasets lacking node features, we assigned the zero vector as the initial node feature.
For the large graphs "arBN-arxiv" and "OGBN-Products. " undirected the graphs and then clustered them following
( We did so we will be able to fit them into memory.
In the ESAN experiments 3 we followed the preprocessing steps outlined by the authors, as these were integral parts of their suggested method. Specifically, we used the configuration that yielded the best empirical results reported the paper, "DSS-GNE -NNN (GIN) (EGO+)."
C.3 Tailoring GNN architectures to different benchmarks
In all our experiments, we used consistent architectures with minor variations tailored to each dataset. The primary difference is in the initial layer, which adapts the specific characteristics of the dataset's node and edge features. This initial layer can be either an embedding layer or linear layer designed to project the input into the network's hidden space. Following the initial layer, the architecture consists of stacked message-passing layers with residual connections and batch normalization layers. For graph-prediction benchmarks, readout function is applied. Finally, two-layer multilayer perceptron (MLP) with ReLU activation produces the output.
C.3.1 GraphGPS configuration
Due to the flexibility of GraphGPS and its numerous configuration options, we selected and focused on specific setup. We utilized the Residual Gated Graph ConvNet from [5] as our convolution operator.For the attention module we used, dropout rate of 0.5 and attention heads. For the experiments that uses Positional Encoding used random walk with length 20. This configuration was taken from graph-gps repository The full initialization details are available in our code.
C.4 Parameter budget
We made our best effort to find the most common parameter budget for each benchmark. Specifically:
For the ZINC 19 dataset, we employed a 100k parameter budget in order to obtain fair comparison to previous works I2
For the TUDatasets (MUTAG, ENZYMES, PROTEINS, IMDB-BINARY BINARY), where there is no consensus on the parameter budget, we used 500,000 parameter budget. An exception was made for ESAN, for which used 100,000-parameter budget to allow fair comparison.
For the OGB-N datasets, we used 500,000 parameter budget. This is reasonable when considering the parameter counts of models on the the/oggb-arxi leaderboard and productroddct leaderboard
For OGB-G datasets, we used 500,000 parameters for ogbg-molhiv and 2,000,000 for ogbg-molpcba since its prediction task is more complex and contains 128 label prediction tasks. These are reasonable numbers can be seen from Dobgg-moliv leaderboard & oghg-molpcha leaderboard
For the LRGB datasets, also used 2,000,000 parameter budget as those datasets require deeper GNNs because they need to embed long-range dependencies in the graph.
summary of the parameter budget can be seen Table 5
22

---

Table 5: Parameter budget used for each dataset. *for the ESAN, we used a 300,000 parameter budget. *or the ESAN we used a 100,000 parameter budget.
Dataset
Parameter budget
ogbg-molhiv
500,000
oghg-molpehe
2,000,000
ogbn-arxiv
500,000
igbn-products
500,000
mutag**
500,000
enzymes
500,000
proteins**
500,000
pic-mr**
500,000
imdb-binary
500,000
zinc
100,000
peptides-fune
2,000,000
peptides-struct
2,000,000
C.5 Implementation details
We conduct experiments using PyTorch Geometric the underlying framework, running them on NVIDIA RTX A5000 GPUs. Detailed information on the selected hyperparameters for each dataset and layer configuration, along with instructions for reproducibility, can be found in our GitHub repository integrated our SSMA directly into the official implementation shared by the authors (ESAN VPA). We performed hyperparameter search only within the space the authors used, without altering the training evaluation protocols.
htlp::///ammmaaiid... www.ogddiiiiggii.u....a i Lo/SSMA/). For ESAN B and VPA [3), we
C.6 Hyper parameter search
We use the Weights & Biases platform to perform hyperparameter searches (HPS), aiming to identify the optimal configuration for each dataset. For each configuration, we determine the maximum hidden dimension that fits within the predetermined parameter budget.
MLP compression strength: We search for the optimal compression rate of the low-rank MI.P compressor rate. We define the compression rate 7 as the ratio between the bottleneck rank and the inner aggregation representation dimension m. We perform simple range search over [0.1, 0.25, 0.5, 0.75, 1.0].
Neighbor selection method: We search for the best neighbor selection method. We perform simple range search over [random, attention, slots].
Effective neighborhood size: search for the optimal neighborhood size We perform a simple range search over [2,3,.... CLLIP (max_ (max_neiggll) meighbrrs, 7)].
23

---

D Additional Experiments
D.1 Comparison variance preserving aggregation
We further evaluate our approach against a recently proposed method [39], we substitute the suggested aggregation technique with our own while retaining the original architecture and training protocol outlined in the work. We refer the reader to the original paper for an overview of architecture and training procedures. As illustrated Table 6 our method demonstrates notable superiority over existing method without additional adjustments. Furthermore, optimizing hyperparameters and architecture selection has the potential for further enhancement.
Table 6: Test accuracy (higher is better). Shown is the mean + STD of 10-fold cross-validation runs, VPA results taken directly from (39] SSMA results are generated by using the code provided in 39 without any architecture or training protocol modifications
Module
IMDB-B
IMDE-M
RDT-B
RDT-M5K
COLLAB
MUTAG
PROTEINS
PTC
NCII
GCN -
71.7
46 46.755.
85.5a2.3
S6.R12.4
73.2a117
1196
73.9s4
61.3a5a
79.0n1
$7,2
44.126-5
78.635
82.6455
50.5418
76.922.1
88,38113
7666:54
65.7e11.9
81.8679
72,0+=11
48.7+53
89.0+14
86-7634
75.2a11
60.1113
51 $1.2=2
SSMA
731=22
49.7218.7
89.4t8.1
57.725.
74.00a2
87.7a1177
739
64.1e120
81.75u
Avg. improwment (3)
3.19
7,80
2,93
6.74
3.88
7.85
2.68
7.32
3,88
D.2
Comparison Generalised f-Mean Aggregation
We conducted a further evaluation of our approach against a recently proposed aggregation function that parameterizes a function space encompassing all standard aggregators [25] This aggregation
was incorporated into our framework, and the experiments were performed using the identical setup
described in Appendix C For the aggregation method, employed the configuration specified by the authors in their experiments, as detailed in their rrepository) As shown in Appendix D.2 SSMA outperforms the proposed method. This demonstrates that even method capable of learning variety of aggregation functions experiences relative decline in performance it cannot effectively mix node features like SSMA. This underscores the critical importance of feature mixing in SSMA.
Table 7: Results for TU datasets [32] & ZINC [9] using the aggregation from 25 aggregation as bascline. We report the TU datasets' accuracy mean and STD of 10-fold cross-validation run. For the ZINC dataset, we report mean MAE and STD on the test set according to distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES
PTC-MR 1
MUTAG 1
PROTEINS
IMDB-B
ZINC J
GCN
2
44,33=5.84
58.61#6.83
14.12222.32
13.13244
69.00e6.51
0.29#0.01
GCN
89.79#6.1
76.28%3.19
GAT 4R
50.17=7.60
99.1647977
83,25=10.53
73.75+4.
68.1046.49
0,39#0.33
GAT SSMA
56.6743.72
66.4125.09
89.19:4.5M
80.18
74.5
0.223
6
51.67=8.05
57.43+7.49
17.05+12275
70.9645 47
71.8+5.09
0.26#4001
GATv2
+ SSMA
52,50a843
61.6426.80
88.8021130
75.284430
72,8s4492
0.235
GIN 48
15.33+3.5
S7. $7.0667.74 74
70.94+10.7
68, 68.2644.6
57.648.4
0.27+0004
GIN SSMA
51.6928.44
61.2829.23
90.51
75.1914.73
74.1
0.2224n.083
GraphGPS
37
211.33+11.35
$9 19.26e110.28
55.73+18.00 04
14.85111.00 63
53,5+6635
01255en.1
GraphGPS
SSMA
49.1743.15
63.02a493
86.0727.95
75.5624.24
71.124799
0.2249.005
Improvement (%)
83.45
19.83
17.13
D.3
Comparison GraphGPS with Positionl-Eneodingg
Given the significant improvement in GraphGPS performance with positional encoding, we conducted additional experiments involving GraphGPS with positional encoding. The experiment details provided in Appendix C As shown in Appendix D.3 SSMA enhances GraphGPS performance even with positional encoding.
24

---

Table Results for GraphGPS with positional encoding, the aggregation used for the baselines is Add. See Appendix for more information.
Dataset
GraphGPS
GraphGPS SSMA
GraphGPS PE
GraphGPSS SSMA
ENZYMES
48.33a6.71
49.17:3.15
57.6612845
58.83a5.35
PTC-MR
61.41=6.91
63.02:4493
59.5825.35
64.7625.72
MUTAG
=1.91
86,07+7.95
90.34=7.76
91.37=5.76
PROTEINS
73.7626.15
75.56124.24
73.57=4.31
76.02:3.37
IMDB-B
69 64:.54
71.1
70,9+4.
72.5:468
ZINC
0.2012
0.22+
0.102=0.004
0.100=a0.003
PEPTIDES-F
58,81
600_34
20.81
59.87=00.2
PEPTIDES-S
0.28+0.01
0.27
0.278=00003
0.265=0.004
AGBN-ARXIV 1
63.87=0.68
66.71#9.73
53.53+1
62.85+2.4
48.8917,77
67.62.15.6
39.01 13.06
61.82+2.9
OGBG-MOLHIY
76,242.72
78.4=1833
74.4+2.309
75.73=1.894
OGBG-MOLPCBAT
0.19#001
0.22#0.01
0.196
0.199:0.006
Improvement (%)
8.2
8.64
E
Ablation studies
E.1
Neighbor selection method
In this experiment, we compare the strategy of selecting random neighbors for each node with our proposed soft-neighbor selection mechanism. There are two main reasons for this comparison. i) To demonstrate that SSMA can establish strong aggregation capabilities independently of the aggregation occurring in the attention slots. ii) To provide empirical justification for the proposed soft-neighbor selection mechanism.
To achieve this, we conducted ablation experiments on two different datasets:
1. "OGBN-Arxiv, citation network where most nodes have very low in-degree, while few nodes have an extremely high in-degree.
2. "Proteins." dataset with an in-degree distribution highly concentrated around the mean.
For each one of these datasets, we compared the test accuracy using both neighbor selection methods for varying number of neighbors and types of MPGNN layers. The results presented in Figure
Accuracy number of neighbors
80.0
Architecture
gat random
77.5
gat sttention
randoa
Accuracy
75.0
gen attention
72.5
ain randon
gin
70.0
67.5
85.0
neighbors
Figure 5: Comparison of the neighbor selection methods across different neighbor counts and MPGNN layer types on the "OGBN-Arxiv" and "Proteins" datasets.
The experiment results confirm that SSMA achieves strong performance even with the random neighbor selection and that the soft-neighbor selection works better in most cases. Interestingly, we observe that inerease in the number of neighbors does not necessarily correlate with improved performance, which was apparent most prominently "OGBN-Arxiv:
Furthermore, we find that the GAT layer does not benefit from the proposed slot attention mechanism. This lack of improvement may attributed to the intrinsic attention mechanism within the GAT architecture, rendering the additional attention mechanism redundant.
25

---

E.2 Performance of SSMA under different budget constraints
In this experiment, we explore the performance of SSMA compared sum- sum-based aggregators across various hidden dimension sizes used by the MPGNN architectures. This investigation is motivated by two key objectives: To assess the relative gain of SSMA over sum-based aggregators in both the low- low-budget and high-budget regimes. ii) To analyze how the scaling behavior of sum-based aggregators compares that of SSMA.
We conducted ablation studies on the "IMDB-B" and "MUTAG" datasets to achieve these goals. For each dataset, we measured the accuracy using both sum-based aggregators and SSMA, varying the hidden dimensions and types of MPGNN layers. The results of these experiments are illustrated in Figure 6
Accuracy vs, hidden dimension
IMDB-8
MUTAG
(original)
85
gen (original)
Accuracy
65
80
(ours)
graphgos (original)
graphges (ours)
10a
10a
10*
10a
Hidden dimension
Figure 6: SSMA achieves peak performance with significantly lower hidden dimensions.
The experimental results clearly indicate that SSMA outperforms sum-based aggregators across all parameter regimes, showcasing its effectiveness in propagating relevant information for downstream tasks. Additionally, SSMA does not always benefit from higher dimensionality, reaching saturation much earlier than its counterpart aggregators. This further demonstrates the efficiency of SSMA.
26

---

E.3
On the effectiveness of low-rank compressors
This experiment investigates the impact of low-rank MLP compression on the test performance of diverse architectures. As detailed in Section 4.4 low-rank compression significantly reduces learnable parameters while maintaining good expressive power. This allows for an intriguing trade- off: fewer parameters for larger number of hidden units or slots. We evaluate this trade-off on the "OGBN-Arxiv and "7INC" datasets to understand its effect on performance.
The experiment results are presented in Figure 7
Performance compression strength
OGBN-Arxiv
ZINC
Architecture
0.400
gat
gon
0.350
63
0.325
0.300
0.225
10 10
100
10-2
10-1
10c
Compression strength
Figure 7: The performance under different compression strengths. SSMA can handle strong compres- sion rates without losing much of its performance.
As demonstrated above, maintaining high performance. Notably, the best results are achieved at compression strengths significantly lower than one, demonstrating the expressive power of the MLP compressor even under significant compression and the efficiency of SSMA in propagating information.
observe that SSMA exhibits resilience strong compression,
27

---

E.4 Learning the affine transformation in SSMA
To validate the selection of our affine transformation, we conducted an ablation study where we ini- tialized the affine transformation with our proposed configuration and allowed the model to optimize it further. We used the ZINC dataset for this study and performed a brief hyperparameter search to identify the optimal configuration. The best results are presented in Table The experiments show slight improvement when the affine transformation learned, but the gain is minimal, supporting the validity of our proposed affine transformation. Additionally, we examined the differences between the learned transformation and our proposed one. The learned transformation was similar to our proposal, with an average absolute difference of 0.023 0.019, while the average norm of the affine weights is 0.026 + 0.057.
Table 9: Learning the affine transformation on the ZINC dataset
Layer
Learnable Affine
Constant Affine
GCN
0.2822 + 0.008
0.2836 = 0.012
GAT
0.2278 0.005
0,2323 0.003
GIN
0.2210 + 0.004
0.2260 + 0.003
28

---

Common aggregation functions benchmarks
In order further show the effectiveness of SSMA perform more benchmarks on other common aggregation functions. The results can be seen in the tables below.
Table 10: Results for TU datasets [32 & ZINC [9] using LSTM module aggregation
baseline. We report the TU datasets' accuracy mean and STD of a 10-fold cross-validation run. For the ZINC dataset, report MAR and STD the test set according to 5 distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES
PTC-MR
MUTAG
PROTEINS
IMDB-B
ZINC +
GCN
37.5a8.21
58.7945.23
78.85&21.38
66.58e7.85
54.247.38
0.32&n-04
GCN
SSMA
54,83#7.55
62,29
89,7926.71
76,28+3.19
75.2#29
0,280=#.02
GAT
43
32.8318220
61.352700
74.27a23.17
64.32a5.89
48. 801666
0.3120.04
GAT SSMA
56,6743722
66.41=5.99
89.19s4,58
80.18
74.5+4.14
0,223+8.028
GATv2! 6
34.3316.54
57.0627.99
16,1622:1.4
65.0728.57
54.9015.22
0.30an.22
52.50+843
72.8s492
0.2355+0.00
GIN! 48
37.8347.16
58.41=7.97
78. 78.72823.88
71.07=5.61
50, 70+801
0.25=0.03
GIN SSMA
51.692804
61,28=9.25
90.51
75.19
74.1
0.222
GraphGPS
37
29.17=10.37
38.17=5.37
73.38+22.01
63.03-14.57
49,90+4408 98
0.32+0.0
GraphCiPS SSMA
49.17
63.028493
86.07
75.5624.24
71.124.99
0.22g0.085
Improvement (%)
55,39
7.09
17.52
16.11
42,53
20.93
Table 11: Results for TU datasets
32 & ZINC [19 using pooling aggregation baseline.
We report the TU datasets' accuracy mean and STD of a 10-fold cross-validation run. For the ZINC dataset, report mean MAE and STD on the test set according distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES
PTC-MR
MUTAG
PROTEINS
IMDB-B
ZINC 4
GCNT
49.334767
56.73+5.91
83.08&10.18
70.764442
66.984.72
0.3240.0
GCN
SSMA
54.8317.55
62.2929.33
89,7926.71
76.28s3.19
75.2s2.
0,28022.02
GAT 48
25.8345.29
58.8747742
80.85
71.4384.23
66.5a6.65
0.27a0.01
GAT SSMA
56.67#3.72
66.4125.09
89.1924.58
80.1820.1
74.5
0.22328.028
GATv21
6
47.174707
60.2618.58
10.44
71.42a6.09
65.614.09
0.28
GATv2 + SSMA
52.50=8.43
61.6426.80
88,80=11.80
75.28=4.80
72.8+-922
0.235#2.003
GINT 48
44.671661
60.7915.85
79.96211.4
70.4422.42
$1.625.02
0.4120.01
GIN SSMA
51.6928.04
61.2829.25
90.5 90.51
75.1924.73
74.115.0
0.222:8.003
GraphGPS 3y
21.33
57.91
57, 57.61
48.01
49.415.25
0.41:
GraphGPS SSMA
49.17#3115
63.022499
86,07=7.95
75.5624.24
71.124.79
0.2220.005
Improvement (%)
38.46
6.26
19.13
17.93
24.58
27.36
29

---

Table 12: Results for TU datasets 32 & ZINC 19 using mean aggregation as baseline. We report the TU datasets' accuracy mean and STD of a 10-fold cross-vare validation run. For the ZINC dataset, we report mean MAE and STD on the test set according to 5 distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES
PTC-MR
MUTAG
PROTEINS
IMDB-B
ZINC 1.
GCN
15.8319909
M.8826607
86.0717.05
73.212407
70.72406
0.3120.11
GCN
SSMA
54.8347.55
62.2929.33
89.7926.71
76.28a3.19
75.2a2.9
0.280
GAT 4B
48.334791
57.6626.96
78.72+14.14
73.12:4.51
70.824.75
0.25+0.01
GAT SSMA
56,6743772
66.4125.09
89.1922.58
80.1820.1
74.5
0.223
GATv2! 6
51.67+875
$7.79+9.00
79.27=13.2
73.11
70.8+3.49
0.25+0001
GATv2 SSMA
52.50:8.43
61.6426680
88.80211.00
75,28
72.8s492
0.235
GINT 48
43.67*885
56.11555.32
72.26 1.06
74.46ea.79
50.0=5.29
11,4+0
GIN SSMA
51,6918.04
61.28a9.25
90.51
75.192473
74.115.02
0.222+0.003
GraphGPS
37
24.8348.48
58,7945.58
61.15#21
18
48.244994
0.39
GraphIPSS
SSMA
49.17
63.0224.93
86,07
75.5624.24
71.12479
0.22g0.005
Improvement (%)
24.43
10.37
19.13
5.75
22.02
22,91
Table 13: Results for TU datasets [32 & ZINC [9 using min pooling aggregation as a baseline. We report the TU datasets' accuracy mean and STD of a 10-fold cross-validation run. For the ZINC dataset, we report mean MAE and STD on test set according to distinct runs. f indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES
PTC-MR 1
MUTAG
PROTEINS
IMDB-B
ZINC +
GCNT 24
45.67=742
56.97+5.01
87.1886.43
73.1225.42
68.924.01
0.35+0.01
GCN
62.2929.35
89.7926.71
76.28
75.2s29
0,280:10.02
GAT 43
46.3349906
56.534895
80.68e9.22
71.60e4.12
65.8=1.99
0.27=0.01
GAT SSMA
56.6743.72
66.4125.69
89.1924.58
80.1820.1
74.5a4.14
0.2231a.028
GATv2
6
$7.7247.09
64,92498
0.27=0.01
GATv2 + SSMA
52,501844
61.642690
88.80
75.282480
72.8
0.235
GINt 48
35.67a4225
58.4115.27
73.03&11.12
69.44
50.0a5.29
0.41
GIN SSMA
51.6928.04
61. 21.2829.23
90,51
75.1924.73
74.1
0.222+8.003
GraphGPS 37
26.172
$7.55.7709
69.27
59,23a5.75
49.625.27
0.41200.44
GraphGPS SSMA
49.17=3.15
63.0244.93
86.07a7.95
75.56+4.24
71.124.9
0.22e0.005
Improvement (%)
40.33
9.59
13.76
11.8
25.21
28.51
Table 14: Results for TU datasets 32 & ZINC 19
using multiplication aggregation baseline. We report the TU datasets' accuracy mean and STD of a 10-fold cross-validation run. For the ZINC dataset, report mean MAE and STD the test set according to 5 distinct runs. indicates reproduced results while indicates the reported results from the relevant paper.
Module
ENZYMES1
PTC-MR
MUTAG
PROTEINS
IMDB-B
ZINC +
29.67+7.11
56.5527.57
77.91210.23
60.57=7.61
65.421.4
GCN
SSMA
54,83+7.55
62.29
89,7926.71
76,28+3.19
75.2+29
0,280=4.02
GAT
+
23. 27.174883
$4.5528.99
76.97=11.12
63.68=5559
64.925.36
0.98=n.02
GAT SSMA
56.6743.72
66.4125.9
89.19s4.58
80.18
74.5s4.14
0.22338.028
GATv2! 6
23.83+6643
56. 15+8.66
75.85=11.2
59,63e7.37
65.0=1159
0.98=0.01
52.50=a.43
61.64a6.00
88.80
75.28
72.8s4922
0.235++.00
GIN! 48
22.67+584
08
73. 12.1444
69.35=5.24
46.822105
1,5+000
GIN SSMA
51.692804
61,28
90.51
75.1924.73
74.145.02
0.22244.00
GraphGPS
37
22.33+763
58,
73.5+12.35
52.33+10.0R
81-889
0.88+142
GraphCiPS
SSMA
49.1743.15
63.0224993
86.0727.95
75.56:4424
71.124.9
0.22g0.085
Improvement (5)
119.58
12.1
17.81
26.18
27.47
82,69
30

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In this paper. we introduce a novel aggregation method that enhances expres- sive power capabilities for various message-passinngg graph neural networks. We provide theoretical justification and conduct extensive experiments on multiple datasets and architec- tures.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provided information method limitations in section 4.4.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) the full set of assumptions and a complete?
31

---

Answer: [Yes]
Justification: In sections and 4, where we discuss the proposed method's theoretical proposition, provide full set of assumptions and complete proof. The appendix references part of the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide fully detailed experiment setup in Section 5 and additional, comprehensive information on evaluations and datasets in the appendix. We also provided the code for our experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
32

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code of our experiments in the Abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
gublic/guidess heaia//ggiiies/ooeeuubbiiseeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips cc/ wttppppllllllppie http://oooooouoaasssooooooloo..e
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All implementation details for experiments have been provided in Section and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in the appendix, or supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We reported the standard deviation error of the mean and all the results in section and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources used presented in Appendix C.5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and ensured our compliance with its guidelines
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As the proposed methods improve the expressive power of existing techniques that operate on datasets with no direct social impact, we believe this work also does not have direct social impact.
Guidelines:
34

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: All the datasets used in this work are known and widely used. We are not aware of any risks involved in these datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: In our code repository we share all the packages we used for our code, and we also specify the version of each package The repository is here serc/nttpss://annddarii gi
github.io/SSMA/ io/SSMA/
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
35

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.paperssii paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We document experiments thoroughly, anonymize the data, and provide the code. The code link is available the Abstract.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
36

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "qQXuwkYT0i", "reviewer": "Reviewer_vJN5", "summary": "This paper introduces Sequential Signal Mixing Aggregation (SSMA), a novel aggregation method for Message Passing Graph Neural Networks (MPGNNs). SSMA addresses the shortcomings of traditional sum-based aggregators, which often struggle to effectively \"mix\" features from distinct neighbors. By treating neighbor features as 2D discrete signals and sequentially convolving them, SSMA significantly enhances feature mixing from distinct neighbors. Experimental results show that integrating SSMA into existing MPGNN architectures markedly improves performance across various benchmarks, achieving state-of-the-art results.", "questions": "Please refer to the weaknesses.", "limitations": "The limitations have been demonstrated in the paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThe explanation of the limitations of sum-based aggregators is compelling and insightful, offering a fresh perspective on the problem and effectively motivating the proposed method.\n2.\tSSMA introduces an innovative approach to feature aggregation in MPGNNs, which can be efficiently implemented and scaled to accommodate larger graphs.\n3.\tThe experimental results on both node and graph-level tasks clearly demonstrate the effectiveness of the proposed method.", "weaknesses": "1.\tOther aggregation methods, such as LSTM[1] and DIFFPOOL[2], also effectively mix neighbors’ features. These methods should be included in the related work and experimental comparisons.\n2.\tThe inductive setting mentioned in the experimental setup section is missing from the experiments section.\n\n[1] Inductive Representation Learning on Large Graphs. NeurIPS 2017. \n[2] Hierarchical Graph Representation Learning with Differentiable Pooling. NeurIPS 2018", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding the discussed limitations of sum-based aggregators compelling and insightful, endorsing SSMA’s innovative approach and appreciating the experimental results which demonstrate the effectiveness of SSMA.\n\n***\n\nWe would like to address your quoted concerns:\n\n> Other aggregation methods, such as LSTM[1] and DIFFPOOL[2], also effectively mix neighbors’ features. These methods should be included in the related work and experimental comparisons.\n\nThank you very much for this feedback which motivated us to broaden the experiments.\n\nFollowing your and reviewer's @QvY7 suggestion, we compared SSMA to more advanced aggregation methods such as LSTM and Generalized f-Mean Aggregation[1], along the comparisons to PNA[2] and VPA[3] which already exist in the paper. Refer to tables 4,5 in the attached PDF for the results.\n\nWhile DiffPool[5] is not an aggregation method per-se but rather a technique to pool the graph nodes’, your input led us to create a dense version of SSMA, allowing it to be incorporated into DiffPool and other methods in this line of work (e.g MinCutPool [4]).\nIn addition, we compared the original version of DiffPool with SSMA-augmented version of DiffPool on the TU datasets using the benchmark code provided by [PyG](https://github.com/pyg-team/pytorch_geometric/tree/master/benchmark/kernel).\nRefer to table 3 in the attached PDF for the results.\n\n***\n\n> The inductive setting mentioned in the experimental setup section is missing from the experiments section.\n\n\nWe point out that the experimental section includes both the inductive and transductive settings.\n To provide further clarity, we present the distinction between the inductive and transductive benchmarks used in our experiments.\n\nInductive benchmarks:\nogbg-molhiv, ogbg-molpcba, mutag, enzymes, proteins, ptc-mr, imdb-binary, zinc, peptides-func, peptides-struct.\n\n\nTransductive benchmarks: ogbn-arxiv and ogbn-products. \n\nTo further eliminate confusions regarding this topic, we refer the reviewer to table 3 in the appendix which contains additional details about the datasets.\n\n***\n\nThanks again for the review!\n\nLet us know if you have any further questions and consider modifying your score if you are satisfied with our response.\n\n***\n\n[1]: Generalised f-Mean Aggregation for Graph Neural Networks. NeurIPS 2023.\n\n[2]: Principal Neighbourhood Aggregation for Graph Nets. NeurIPS 2020.\n\n[3]:  GNN-VPA: A Variance-Preserving Aggregation Strategy for Graph Neural Networks. ICLR 2024 Tiny Paper.\n\n[4]: Spectral Clustering with Graph Neural Networks for Graph Pooling. ICML 2020.\n\n[5]: Hierarchical Graph Representation Learning with Differentiable Pooling. NeurIPS 2018.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "GX85vPyDoV", "reviewer": "Reviewer_QvY7", "summary": "This paper introduces Sequential Signal Mixing Aggregation (SSMA) for Message Passing Graph Neural Networks (MPGNNs), addressing the limitations of traditional sum-based aggregation methods. SSMA enhances the mixing of features from distinct neighbors by treating neighbor features as 2D discrete signals and applying sequential convolution.", "questions": "- The authors conducted extensive tests combining different MPGNN architectures with SSMA in the experiments. However, why is there only a comparison of SSMA with one other aggregator in the appendix? Could the authors provide more experimental results comparing SSMA with other aggregators to demonstrate its advantages better?\n\n- Could the authors provide direct training time comparisons between MPGNNs using SSMA and other aggregators? This would help to illustrate the time cost associated with adding the SSMA module more clearly.\n\n- In Figure 1, SSMA is demonstrated, but the nodes u, v, and w appear more like a set rather than having a sequential relationship. Does \"sequential\" refer to the pipeline being sequential, or is there a sequential relationship among these graph nodes?\n\n- Are there specific types of graphs or tasks where SSMA may not perform as well as other methods?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Treating neighbor features as 2D discrete signals and using sequential convolution is innovative. This approach allows for more effective mixing of features from different neighbors, addressing a significant limitation in traditional sum-based aggregators. By revealing that sum-based aggregators cannot adequately \"mix\" neighbor features, the paper paves the way for more aggregation techniques. Introducing a convolution-based aggregation module is an advancement in the field.\n\nThe theoretical foundation of the proposed SSMA method is robust, with well-detailed mathematical formulations and proofs. The paper derives the key equations and supports them with solid theoretical arguments. \n\nThe practical aspects, including learnable affine transformations, low-rank compression, and normalization, are well thought out and enhance the applicability and stability of SSMA in real-world scenarios.", "weaknesses": "- Limited Comparisons: The paper only compares SSMA with one other aggregation method in the appendix. Including comparisons with more diverse and state-of-the-art aggregation methods would strengthen the evaluation and provide a more comprehensive understanding of SSMA's advantages and limitations. Recent advancements such as Generalized f-Mean Aggregation, Principal Neighbourhood Aggregation (PNA), Hybrid Aggregation for Heterogeneous Graph Neural Networks (HAGNN), Robust Graph Neural Networks via Unbiased Aggregation, and GNN-VPA: A Variance-Preserving Aggregation Strategy for Graph Neural Networks could provide valuable benchmarks for comparison​ (ar5iv)​​ (ar5iv)​​ (ar5iv)​​ (ar5iv)​​ (ar5iv)​​ (ar5iv)​​.\n\n- Computational Complexity: The paper would benefit from discussing SSMA's computational complexity compared to other aggregation method  s. Currently, the paper only addresses SSMA's time complexity. It would be better if it included a comparison with the time complexities of similar aggregation methods from related work. This would provide a clearer context for evaluating SSMA's efficiency and practicality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer's recognition of convolution-based aggregations as an advancement in the field, effectively addressing a major limitation of traditional sum-based aggregators. We thank the reviewer for highlighting the robust theoretical foundation, and appreciating the practical aspects that enhance SSMA's applicability and stability in real-world scenarios.\n\n***\nWe would like to address your questions:\n\n> The authors conducted extensive tests combining different MPGNN architectures with SSMA in the experiments. However, why is there only a comparison of SSMA with one other aggregator in the appendix? Could the authors provide more experimental results comparing SSMA with other aggregators to demonstrate its advantages better?\n\nThank you for this feedback which motivated us to broaden the experiments.\nFollowing your and reviewer's @vJN5 advice, we compared SSMA to a wider spectrum of aggregations including LSTM and Generalized f-Mean Aggregation[1]. Please refer to tables 4,5 in the attached PDF for the results.\n\n\nA comparison to PNA[2] already exists in the main paper (Tables 1 and 2) and a comparison to variance-preserving aggregation[3] (VPA) already exists appendix D.1.\nAlthough comparing our results with those from 'Robust Graph Neural Networks via Unbiased Aggregation' could have broadened our experiments, we were unfortunately unable to find a code base for this paper. \n\n***\n\n> Could the authors provide direct training time comparisons between MPGNNs using SSMA and other aggregators? This would help to illustrate the time cost associated with adding the SSMA module more clearly.\n\nWe appreciate the reviewer’s suggestion and agree that such a comparison would demonstrate the efficiency of SSMA when integrated into MPGNNs. We conducted training and inference time comparisons, evaluating SSMA-augmented MPGNNs against PNA and GraphGPS. To ensure fair assessment we enforce the same hidden-dimension and report the time spent on a single convolutional layer. Please refer to Table 1 in the attached PDF for the results.\n\n\nThe results highlight the impressive trade-off of SSMA between down-stream performance and practical training and inference time complexities.\n\n***\n\n> In Figure 1, SSMA is demonstrated, but the nodes u, v, and w appear more like a set rather than having a sequential relationship. Does \"sequential\" refer to the pipeline being sequential, or is there a sequential relationship among these graph nodes?\n\nThe term 'sequential' in SSMA refers to the sequential convolution of the transformed features of neighboring nodes, as outlined in Theorems 4.1 and 4.4, which underlie the construction of SSMA. Figure 1 demonstrates that this sequential convolution can be practically computed in the Fourier domain.\n\n***\n\n> Are there specific types of graphs or tasks where SSMA may not perform as well as other methods?\n\nWhile the “vanilla” version of SSMA may fail in dense neighborhoods due to the representation size scaling quadratically with the number of neighbors (as pointed out in lines 212-213, 269-270) the proposed neighbor selection mechanism (lines 212-220) accounts for such cases, as later demonstrated in the experimental section (lines 252-255).\nWe haven’t identified other potential failure cases, which we leave for future research.\n\n***\n  \nThanks again for the review!\n\nLet us know if you have any further questions and consider modifying your score if you are satisfied with our response.\n\n***\n\n[1]: Generalised f-Mean Aggregation for Graph Neural Networks. NeurIPS 2023.\n\n[2]: Principal Neighbourhood Aggregation for Graph Nets. NeurIPS 2020.\n\n[3]:  GNN-VPA: A Variance-Preserving Aggregation Strategy for Graph Neural Networks. ICLR 2024 Tiny Paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "g0bLTB5zVq", "reviewer": "Reviewer_aDFM", "summary": "The paper analyzes the discrepancy between the theoretical guarantees of sum-based aggregators and their practical performance, which makes more complex aggregators preferred in practice. They define the notion of neighbor-mixing to explain this gap, and propose a novel aggrgeation module, named SSMA, which builds upon deepsets polynomial.", "questions": "Can you expand on the intuition of sum-based aggregators lacking mixing abilities?", "limitations": "Addressed", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The theoretical analysis is sound and rigorous.\nThe experimental section shows promising performance in practice, and I particularly appreciated that the authors have adjusted the number of parameters in the augmented model to match that of the original, to ensure a fair comparison.", "weaknesses": "The paper is hard to follow, and I think adding some intuition on the results would significantly strengthen the paper. For example, while I would have liked to understand the intuition why sum-based aggregators have small neighbor-mixing (which is very briefly touched in lines 116 to 118, but, in my opinion, not sufficiently to have any intuition, and it seems more like a statement that it is the case).\nSection 4 is generally hard because, while it is supposed to be a way of constructing the model, it ends up being a theoretical digression until 4.3, where then the model becomes clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the theoretical analysis and the experimental section, particularly our methodological approach to ensure fair comparison.\n\n***\n\nWe would like to address your quoted concerns:\n\n> Can you expand on the intuition of sum-based aggregators lacking mixing abilities?\n\nNote that additional intuition on sum-based aggregators lacking mixing abilities is provided in subsection 4.3. Specifically, please refer to lines 185-187 and Eq. (14) which intuitively state that for sum-based aggregators the “mixing” is done only in the MLP.\nRegarding section 4, to further exemplify the construction of the generalized DeepSets polynomial we provide an additional figure illustrating a concrete instantiation of the polynomial for a specific neighbor set. Please refer to Figure 1 in the attached PDF.\n\n***\n\nIf the reviewer remains unsatisfied with the intuitive explanations, we welcome further clarification on what specific aspects need more elaboration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "cTJI1kLNh1", "reviewer": "Reviewer_4Dt8", "summary": "This paper focuses on the aggregation module in Message Passing Graph Neural Networks (MPGNNs). \nIt tackles the problem that sum-based aggregators, even though widely used, fail to 'mix' features belonging to distinct neighbors, preventing them from succeeding at the downstream tasks.\n Accordingly, the authors introduce a novel plug-and-play aggregation for MPGNNs, denoted as Sequential Signal Mixing Aggregation (SSMA).\nSSMA treats the neighbor features as 2D discrete signals and sequentially convolves them with circular convolution by applying 2D Fast Fourier Transform (FFT).\nThe authors also propose several designs to guarantee the practical use of the proposed methods.\nIn the empirical experiments, SSMA successfully improved the performance of several MPGNNs.", "questions": "1. What is the configuration of GraphGPS in the experiment? As in the paper, several configurations are provided.\n2. In eq (8), the number of separators $m=n+1$ depends on the neighbor sizes; $\\mathbf{h}: \\mathbb{R} \\to \\mathbb{R}^m$ is an affine map. How this affine map is determined? Is it learnable? In graph learning, the $n$ is usually assumed unknown and varying. (the same question applies to vector-feature cases as well)\n\n2. Following up on the Weakness 2. The experiment on ZINC follows the 100k parameter setting as ESAN, while other baselines are reproduced. Compared to the 500K parameter setting in GraphGPS, there are interesting points. Regular MPNNs, e.g., GCN, GAT, GIN, PNA, do not show significant improvement on the 500K setting, while GraphGPS is significantly improved. Based on Table 3 and Table B.1 in GraphGPS, GatedGCN ($\\sim 0.090$), GraphGPS($\\sim0.070$), GraphGPS+NoPE ($\\sim0.110$), GINE+RWSE($\\sim0.070$).\n    - I am interested to know the improvement of GRASS on GraphGPS on the 500K setting\n    - Can GRASS improve MPNNs with PE?", "limitations": "The limitation on computational complexity is adequately addressed by the proposed technique.s\nNo potential negative societal impact aware.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work has a good motivation and a solid mathematical foundation driving the proposed methods. \n2. This paper is well-written.\n3. The empirical performance can well support the statement of the paper.\n4. According to the best of my knowledge, this is the first work to enhance the aggregation module via circular convolution.", "weaknesses": "1. Even though with good theoretical computational complexity analysis, it will be good to have the empirical run-time comparison between the MPGNN and MPGNN+SSMA. \n2. According to my knowledge, there are many works using pre-computed PE with conditional aggregation to improve the distinguishability of the neighbors during the 'mixing' of them, (e.g., [1], GraphGPS). They require extra one-time computation on PE but will not increase the complexity of the model inference. There are no comparisons to the line of work. (I am not sure about the exact GraphGPS configuration in the experiments. I have some concerns about it which are listed in \"questions\")\n\n\n\n\n\n\n\n\n\n\n\n- [1] Dwivedi, Vijay Prakash, et al. \"Graph Neural Networks with Learnable Structural and Positional Representations.\" International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are pleased that the reviewer recognized the novelty of our proposed method, its underlying mathematical foundations and the empirical performance supporting the statement of the paper. We thank the reviewer for appreciating the paper’s motivation and writing. \n\n***\n\nWe would like to address some concerns mentioned by the reviewer.\n\n> Even though with good theoretical computational complexity analysis, it will be good to have the empirical run-time comparison between the MPGNN and MPGNN+SSMA.\n\nWe appreciate the reviewer’s suggestion and agree that such a comparison would demonstrate the efficiency of SSMA when integrated into MPGNNs. We conducted training and inference time comparisons, evaluating SSMA-augmented MPGNNs against PNA and GraphGPS. To ensure fair assessment we enforce the same hidden-dimension and report the time spent on a single convolutional layer. Please refer to Table 1 in the attached PDF.\n\nThe results highlight the impressive trade-off of SSMA between down-stream performance and practical training and inference time complexities.\n\n***\n\n> What is the configuration of GraphGPS in the experiment? As in the paper, several configurations are provided.\n\n\nAs several configurations are provided in GraphGPS, we tried to focus on the most standard configuration possible - A GatedGCN as the message-passing network, standard multi-head attention with 8 heads without PE or SE. We used [PyG](https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.nn.conv.GPSConv.html)’s implementation for the layer.\n\n***\n\n> In eq (8), the number of separators $m=n+1$ depends on the neighbor sizes; $\\boldsymbol{h}: \\mathbb{R} \\rightarrow \\mathbb{R}^m$ is an affine map. How this affine map is determined? Is it learnable? In graph learning, the $n$ is usually assumed unknown and varying. (the same question applies to vector-feature cases as well)\n\nThe affine map $\\boldsymbol{h}$ In Eq. (8) is fixed and refers to the padded coefficients of each $p_i$ as given by Eq. (5) (please refer to lines 140-141). The same applies for $\\boldsymbol{\\Phi}$ in the vector case, in which the full form of the affine map is given in Appendix A.3, Eq. (39). While this is the (fixed) affine map which was used in the experiments, Appendix E.4 includes an ablation study that investigates this exact matter.\n\nRegarding the value of $n$, the provided number of separators is satisfactory as long as the number of neighbors is upper bounded by $n$. If there are fewer than $n$ neighbors, the high-power coefficients will vanish. \n\n***\n\n> Following up on the Weakness 2. The experiment on ZINC follows the 100k parameter setting as ESAN, while other baselines are reproduced. Compared to the 500K parameter setting in GraphGPS, there are interesting points. Regular MPNNs, e.g., GCN, GAT, GIN, PNA, do not show significant improvement on the 500K setting, while GraphGPS is significantly improved. Based on Table 3 and Table B.1 in GraphGPS, GatedGCN ($\\sim 0.090$), GraphGPS($\\sim 0.070$), GraphGPS+NoPE ($\\sim 0.110$), GINE+RWSE($\\sim 0.070$). I am interested to know the improvement of GRASS on GraphGPS on the 500K setting. Can GRASS improve MPNNs with PE?\n\nFollowing the reviewer’s suggestion, we perform the following additional experiments on the ZINC regression benchmark:\n* Regarding scaling, we scale up different SSMA augmented architectures (both GCN,GIN and GraphGPS) to the 500K parameter regime.\n* Reagrding positional encoding (PE): we examine the effect of RWSE-20 positional encoding on SSMA-augmented GraphGPS.\n\nFor the GraphGPS experiments in this context we used [PyG](https://github.com/pyg-team/pytorch_geometric/blob/master/examples/graph_gps.py)'s example code, carefully adopting the hyperparameters and optimization parameters used in the ZINC experiments in the GraphGPS paper.\nPlease refer to Table 2 for the results.\n\nThere are several insights:\n* SSMA consistently improves the effectiveness, even at a higher scale and with or without PE.\n* SSMA is well-behaved with positional-encoding, proving to be very effective even with 100K parameters.\n* Scaling does not seem to be valuable when considering classic MPNNs (in contrast to GraphGPS) which strengthens the reviewer's hypothesis.\n\n***\n\nThanks again for the review, let us know if you have any further questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We sincerely appreciate the reviewers for their valuable feedback on our paper.

We were pleased to hear that the reviewers found the explanation of the limitations of sum-based aggregators "compelling and insightful, offering a fresh perspective on the problem and effectively motivating the proposed method" (@vJN5). They also noted that "introducing a convolution-based aggregation module is an advancement in the field" (@QvY7). The significance and rigorous approach of the experimental section were recognized: "The experimental section shows promising performance in practice, and I particularly appreciated that the authors have adjusted the number of parameters in the augmented model to match that of the original, to ensure a fair comparison" (@aDFM). Additionally, the paper was praised for being well-written with solid theoretical foundations: "This work has a good motivation and a solid mathematical foundation driving the proposed methods" and "This paper is well-written" (@4Dt8).

***

The reviewers' suggestions encouraged us to expand our experiments and provide additional illustrations of our method. 

The results of the requested experiments are detailed in the attached PDF file. Specifically:

* Table 1 compares the training and inference times of SSMA against other methods, as requested by reviewers (@QvY7,@4Dt8).
* Table 2 demonstrates the effects of positional encoding (PE) and scale on the effectiveness of SSMA as requested by reviewers (@4Dt8).
* Table 3 demonstrates the benefit of SSMA to DIffPool as requested by the reviewer (@vJN5).
* Figure 1 illustrates a specific realization of the generalized DeepSets polynomial compared to DeepSets motivated by the reviewer's comments (@aDFM).
* Table 4 includes additional experiments for the f-Mean aggregation as requested by the reviewer (@QvY7).
* Table 5 includes additional experiments for the LSTM aggregation, as requested by the reviewer (@vJN5).

***

We thank the reviewers for spending time reviewing our paper and encourage further discussion on any issues that may arise from the rebuttal. If our responses and the additional experiments satisfactorily address the reviewers' concerns, we would be grateful if they could consider modifying our score.

Meta-review: This paper studies the aggregation method in graph neural networks. It founds that the commonly used sum-based aggregators cannot "mix" features of distinct neighbors. The authors then propose SSMA (short for Sequential Signal Mixing Aggregation) to tackle the limitation with respect to neighbor mixing. There are a few minor concerns remained after reading the paper and author-reviewer discussion:
* First, the structure of this paper made some parts hard to understand. For example, the authors claim that the mixing value for sum-based aggregation is small, which is more like a statement at that point. And more detailed explanation is deferred until section 4.3. Restructuring or a better pointer to the explanations would help.

* Second, it  might be helpful to briefly explain the intuition of definition and theorem before or after it, to further enhance the clarity for broad audience. For example, it would be helpful to explain the intuition of equation (1) by expanding "in that the mutual effect of perturbing the features ...". Similar treatments could be done for proposition 3.2 and most theoretical parts in section 4.2.

Despite these minor concerns, I find the paper well-motivated and the method interesting and novel. All reviewers unanimously believe that this paper is above the acceptance threshold. I recommend accepting this work.
Decision: Accept (poster)