Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networks

Authors: mitchell keren taraday
almog  david
chaim  baskin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 06:31:01

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/.

Main paper: 
 introduction: 
 Message-passing Graph Neural Networks (MPGNNs) have established themselves as the major workhorses for graph representation learning over the past decade [24] . These models have been proven to be effective in graph-structured problems in a variety of domains, ranging from social networks [18] to natural sciences [14, 23, 4] and having some 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. A typical MPGNN takes graph-structured data containing node and edge features as input. It then iteratively updates node representations by combining their egocentric view with a symmetrized aggregation of their proximate neighbor features. The key insight regarding the expressive power of such models is their equivalence to the Weisfeller-Lehman (WL) graph isomorphism test [47] . Consequently, past research directions were majorly directed toward developing models that surpass the vanilla WL test by tackling the graph learnability problem from various perspectives, including stronger notions of the WL test [31, 35] , spectral graph methods [46, 13, 44] and graph transformers [49, 36] .However, one subtle but often overlooked detail in such expressivity analyses is the existence of a 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 [50] showcased such a 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, 1] , sum-based aggregations seem to lag behind the aggregators used in practice [11] .In this work, we suggest that a possible explanation for this gap is the inability of sum-based aggregators 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 a very simple function requiring neighbor-mixing.With this motivation in mind, we propose a 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 a provably polynomial representation size m = O(n 2 d) (where n is the number of neighbors and d is feature dimensionality). The theoretical construction underlying SSMA provides a positive answer to a lasting mystery regarding DeepSets [50] -"Can the DeepSets polynomial be efficiently generalized to handle vector features?"as depicted in Figure 1 .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 to scale it to larger graphs and how to make it easier to optimize.Finally, we demonstrate that when integrated into a wide range of well established MPGNN architectures, 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-art results in many settings.Contributions. Our contributions may be summarized as follows:1. We define the notion of "neighbor-mixing" and show that sum-based aggregators have limited neighbor-mixing power. We verify this idea by conducting an experiment on a simple and natural synthetic task. 2. We propose Sequential Signal Mixing Aggregation (SSMA) -an aggregation module of dimension m = O(n 2 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 to scale it to larger graphs. 4. Finally, we conduct extensive experiments showing that enriching prominent MPGNN architectures with SSMA yields large improvements on a variety of benchmarks, achieving state-of-the-art results. 
preliminaries and related work: 
 Let X be some domain. We are interested in representing multisets (sets in which repeated elements are allowed) over that domain. We denote multisets by {{x 1 , ..., x n }} where each x i ∈ X , and denote by M n := (X ) n the n-tuple space over X . We seek a (possibly learnable) permutation invariant mapping f : M n → R m separating distinct multisets 2 . When combined with a learnable compression network g θ : R m → X , their composition γ = g θ • f can be utilized as an aggregation module for MPGNNs over the domain X .Particularly, we are interested in continuous features, namely the domains X = R and X = R d . We consider the symmetry group G = S n acting on M n = R n by [σ.x] i = x σ -1 (i) and on M n = R n×d by [σ.X] ij = X σ -1 (i)j correspondingly. It is widely agreed that finding a good representation f : M n → R m for these domains is crucial for building better aggregation modules γ and has a direct influence on the performance of the model on a variety of downstream tasks [47, 12, 27, 40] .DeepSets [50] was the pioneering work introducing a sum-based aggregator with a provably finite representation size m: γ({{x 1 , ..., x n }}) = ρ( n k=1 ϕ(x k )) where ϕ : R d → R m and ρ : R m → R d . 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 ∈ O( n+d d ). This upper bound was later improved to O(n 2 d) and eventually to a tight Θ(nd) [17] . While moment-based features served as a 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, as long as non-polynomial analytic activations are used [1] .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-based aggregators have been proposed to capture the most important signals incoming from the neighborhood [2, 7] . Others suggested using a mixture of symmetric aggregators such as min, max, mean, sum, std as each of these aggregators helps separate different kinds of multisets [47, 41, 12] . Other works focused on aggregations preserving intrinsic properties of the neighborhood data such as variance and fisher-information [38, 30] .Another intriguing type of work deals with the relaxation of the neighbor ordering invariance constraint. Particularly, regularizing recurrent neural network-based aggregations to maintain permutation invariance -either by choosing a random neighbor permutation [20] or by explicit regularization terms [10, 34] has raised some interest. 
on the limited neighbor-mixing of sum-based aggregators: 
 Despite their provable separation power, sum-based aggregators seem to lag behind other aggregators used in practice [11] . We claim that a possible explanation for this phenomenon lies in their inability to "mix" the neighbor's features, in that the mutual effect of perturbing the features of two distinct 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 γ : R n×d → R d be some aggregation function that is continuously twice differentiable. We define the neighbor mixing of the ℓ-th aggregation output with respect to the neighbor pair (i, j):EQUATIONAt an intuitive level, sum-based aggregators have small mix (ℓ)i,j 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 γ({{x 1 , ..., x n }}) = n k=1 ϕ(x k ) we have:∂ 2 ∂x i ∂x j n k=1 ϕ (ℓ) (x k ) = 0 (2)Formally, to account for mixing that may occur in any subsequent (global) transformation we have the following proposition:Proposition 3.2. Let γ({{x 1 , ..., x n }}) = ρ ( n k=1 ϕ(x k ))where ϕ : R d → R m is a local operator and ρ : R m → R d is a pooling operator that is continuously twice differentiable. Then, we have ∀i ̸ = j:EQUATIONWhere J ϕ (.) is the Jacobian matrix of ϕ and H ρ (ℓ) (.) is the Hessian matrix corresponding to ℓ-th output of ρ. Particularly, for typical choices of ϕ and ρ it follows: mixEQUATION2 ) where θ is the concatenation of the parameters in ϕ and ρ.The proof of Proposition 3.2 is given in Appendix A.1. Motivated by the above observation, we propose a new species of aggregation module which is convolution-based rather than sum-based.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) the full set of assumptions and a complete?• 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 or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
ssma-sequential signal mixing aggregation: 
 4.1 Warm-up: DeepSets polynomial from a convolutional point of view Let x = {{x 1 , ..., x n }} be a scalar multiset. We define its DeepSets polynomial by considering a polynomial of variable t having the multiset elements as its roots:EQUATIONIts coefficients, we denote by e k (x), are permutation invariant functions. Moreover, the (e k (x)) m k=0 s form an ensemble of invariant separators 3 .Instead of describing a polynomial by its coefficients, one can represent a polynomial by evaluating it on some fixed set of points. Given a set of n + 1 fixed points, the polynomial may be represented by evaluating its value on these points. One can switch from this representation back to the coefficients by solving a system of linear equations, which always has a unique solution. Now, by allowing the evaluation points to be complex, we can choose them as the roots of unity. By doing so, we get the discrete Fourier transform (DFT) of the polynomial coefficients:EQUATIONNext, we denote the factors in p x (t) = n i=1 p i (t) where p i (t) := t -x i . The (padded) coefficients of each p i (t) are then given by the affine transformation:EQUATIONThe nice thing about representing a polynomial by evaluating its values at a list of fixed points is that polynomial multiplication becomes point-wise. It can be deduced that the coefficients of p x (t) can be computed by transforming the coefficients h(x i ) of each p i (t) to the Fourier domain, performing 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(x i ). We combine the above ideas into the following theorem: Theorem 4.1. Scalar multisets x = {{x 1 , ..., x n }} can be represented by an invariant and separating map f conv :EQUATIONWhere h : R → R m is an affine map, ⊛ is the circular convolution operator, and the number ofseparators is m = n + 1 ∈ O(n).Theorem 4.1 simply states that sequential convolution can be utilized to compute the renowned DeepSets polynomial coefficients. While not particularly surprising, Theorem 4.1 shows that the coefficients of the DeepSets polynomial can be efficiently computed and directly utilized as a multiset representation. Moreover, it paves the way for our construction, as seen in the next section."How does the DeepSets polynomial can be efficiently extended to handle vector features?"The key idea underlying our answer to this question is to encode each feature vector as another polynomial, and then to reduce the problem to the scalar case.We encode each element X i belonging to the multiset X = {{X 1 , ..., X n }} as a polynomial of another variable z:EQUATIONThen, we can perform a reduction to the scalar case by replacing each X i with Enc(X i ):EQUATIONAnd define the generalized DeepSets polynomial:EQUATIONWhere e kℓ (X) is the coefficient oft k z ℓ in p X (t, z). Note 0 ≤ k ≤ n while 0 ≤ ℓ ≤ n(d -1).Opposed to the scalar case, it is not evident why the obtained coefficients (e kℓ (X)) k,ℓ 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 lemma in Appendix A.2.We can now repeat the steps in Section 4.1 to achieve the actual representation. We compute the coefficient matrix of each p i (t, z) and sequentially perform two-dimensional circular convolution.This leads us to an analogous theorem for the d-dimensional case: Theorem 4.2. Vector multisets X = {{X 1 , ..., X n }} can be represented by an invariant and separating map f conv :EQUATIONWhere Φ : R d → R m1×m2 is an affine map, ⊛ is the 2D circular convolution operator and thenumber of separators is m = m 1 × m 2 = (n + 1)(n(d -1) + 1) ∈ O(n 2 d).The full proof of Theorem 4.2 is given in Appendix A.3.∂ 2 h 1 ∂u 0 ∂v 1 = 1 0 1 2 0 1 2 0 0 1 2 2 1 0 0 1 2 2 1 0 0 1 2 2 1 + + + + + + * = u v h ∂ 3 h 0 ∂u 2 ∂v 1 ∂w 0 = 1 0 1 2 0 1 2 0 1 2 0 0 1 2 2 1 + + 0 0 0 + 0 1 + 2 0 0 1 2 2 1 + + 0 + 0 1 + 1 1 1 0 0 1 2 2 1 + + + 0 1 + 2 2 2 1 ... ... ... = * * h u v wFigure 2 : 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 a feature per node, the corresponding n-th order derivative of exactly one entry of h is 1.Let u 1 , ..., u n ∈ R m be discrete signals representing the locally-transformed 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 u j i with j starting from 0. The core factor causing the neighbor mixing bottleneck of sum-based aggregators h = n i=1 u i lies within the fact that no mixing is done in the representation, but only in the MLP compressor that comes afterward:EQUATIONOn the contrary, each element of sequential circular convolution h = u 1 ⊛ ... ⊛ u n is composed of sums of terms of the form u j1 1 u j2 2 • ... • u jn n . Particularly:EQUATION)This implies that the convolutional representation achieves, in fact, a generalized, higher-order notion of the mix values:EQUATIONThis notion of higher-order neighbor mixing is visualized in Figure 2 . We refer the reader to Appendix A.4 for further theoretical discussions on the stability of permutation-invariant representations.Combining Theorem 4.2 with an MLP compressor yields the "vanilla" version of SSMA: it first applies the local affine map, then computes 2D circular convolution across the neighbor axis and finally compresses the result back using MLP as a universal compressor. The circular convolution is implemented by applying FFT, performing product aggregation along the neighbor axis and then transforming the result back using IFFT. As "scatter_mul" 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 up 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 element-wise magnitudes of the product by taking their geometric means. The goal is to create a compressed view of t's incoming neighbors. Right: our proposed aggregation. We convert the neighbor features into two-dimensional discrete signals. We then apply 2D circular convolution by applying 2D FFT, performing pointwise multiplication and transforming back using IFFT. Finally, we compress the result back into a d-dimensional vector using a multi-layer perceptron as a universal compressor.Low-rank compressor. Since the number of parameters in the MLP compressor rapidly increases with the representation dimension m, we opted for a single linear layer as our compressor. To accommodate a higher number of neighbor slots and allow for a larger hidden dimension, we reduced the number of parameters in the linear layer by splitting it into two consecutive linear layers that squeezes the representation to low dimension and than expands it back. This effectively performs a low-rank factorization of the weight matrix of the original single linear layer.Neighbor selection methods. The representation size of the vanilla SSMA m = O(n 2 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 a new set of κ neighbors. The first technique simply draws at 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 : j → i for the k-th slot is expressed as follows:EQUATIONEQUATIONWhere a k , b k ∈ R d are per-slot learnable weight vectors. Thereafter, the k-th slot for the i-th node is produced by considering the weighted average of the incoming neighbors:EQUATION5 Experiments 
synthetic task: 
 To empirically demonstrate the success of SSMA in managing tasks characterized by high neighbor mixing (opposed to sum-based aggregators), we introduce a synthetic regression task we name SUMOFGRAM. In this task, we sample random neighbor features and then generate the labels by considering the sum of the Gramian matrix corresponding to the neighbor features.In some sense, the SUMOFGRAM task is the "simplest" task that involves neighbor mixing: 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.EQUATIONWe 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] , is sufficient to 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.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 benchmarks. 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 a fair comparison by maintaining an equal total parameter count to that of the original architectures in each experimental setting, adjusting the architecture's hidden dimension to adhere to 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 in Appendix E.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 it 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 OGBN-Products) [21] 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 a 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 its efficiency in retaining relevant information for downstream tasks. Benchmarks for more common aggregation functions is in Appendix F Table 1 : Results for TU datasets [32] & ZINC [19] using sum 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 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 † [ 
conclusion and discussion: 
 In this work, we re-examined the field of aggregation functions in MPGNNs and introduced the Sequential Signal Mixing Aggregation, a new plug-and-play aggregation method with a solid theoretical foundation. We demonstrated its effectiveness across various datasets and message-passing 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 to the instability of the convolution operation. 
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 a direct social impact.Guidelines:• 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or 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 no such risks.• Released models that have a 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 to 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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:https://almogdavid. github.io/SSMA/ Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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 our experiments thoroughly, anonymize the data, and provide the code. The code link is available in the Abstract.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing 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 we expect authors to adhere to 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. 
 
 Appendix: A.1 Proof of Proposition 3.2Proof. Let us consider a general sum-based aggregator:F (x 1 , ..., x n ) = ρ( n k=1 ϕ(x k )). Then, we have that for i ̸ = j and for the ℓ-th output:EQUATIONEQUATION)EQUATION)EQUATIONTypically, the local operator ϕ : R d → R m is of the form ϕ(x) = σ(Ax + b) where σ is an activation function applied element-wise and A ∈ R m×d , b ∈ R m are learnable parameters.Usually |σ ′ (z)| is bounded by some small constant c 1 .Therefore, we have:EQUATIONMoreover, the global pooling operator ρ : R m → R d is an MLP of the form:EQUATIONwhereW 1 ∈ R m×m , β 1 ∈ R m , W 2 ∈ R d×m , β 2 ∈ R d .Therefore:EQUATIONLet us denote:EQUATIONThen,EQUATIONWe compute d dz u (ℓ) (z) for each output dimension 1 ≤ k ≤ m separately:EQUATIONSummarizing this for all dimensions k yields:EQUATIONSo under the assumption |σ ′′ (z)| ≤ c 2 we get the following bound on the Hessian norm:EQUATIONAnd the final bound on mix(ℓ)i,j is given by:EQUATIONA ring is an algebraic structure that generalizes the notion of a field. In particular, univariate and multivariate polynomials obey this structure. Formally, a 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, c ∈ R. (b) existence of identity: there is an element 1 ∈ R such that: 1 • a = a • 1 = a. 3. Distributivety: a • (b + c) = a • b + a • c and (b + c) • a = b • a + c • a.A ring is said to be commutative if its elements commute under multiplication:a • b = b • a for all a, b ∈ R.Given a commutative ring R, we can define its corresponding univariate polynomial ring denoted as R[X] by considering a set of formal expressions n i=0 α i X i where n is a non-negative integer and α i ∈ R. We consider X a formal variable and define addition and multiplication according to the ordinary rules for manipulating algebraic expressions. Each polynomial p ∈ R[X] has a degree defined as max i α i ̸ = 0. For each r ∈ R, we can define an evaluation map T r which takes some polynomial as an input and returns an element in the underlying ring by substituting X = r, namely:T r ( n i=0 α i X i ) = n i=0 α i r i .Multivariate polynomials can be defined similarly by considering multiple formal variables. Alternatively, note that since the polynomial ring of some commutative ring R is also a commutative ring by itself, we can equivalently define multivariate polynomials by considering the ring of polynomials above R[X], namely: (R[X])[Y ] ∼ = R[X, Y ].An integral domain is a 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[x 1 , ..., x n ] are integral domains.An irreducible element of an integral domain is a non-zero element that is not invertible and is not the product of two non-invertible elements. For instance, for every commutative ring R, every polynomial of the form x -r where r ∈ R is an irreducible element of R[x].A unique factorization domain (UFD) is an integral domain R in which every non-zero element r of R can be written as a product (an empty product if x is invertible) of irreducible elements p i of R and an invertible element u: r = u • n i=1 p i . This representation ought to be unique up to multiplication with invertible elements. The key fact underlying our construction is the fact that a polynomial ring of a UFD is by itself a UFD (known as Gauss's lemma). In conjunction with the fact that any field F is a UFD, we get that R[x 1 , ..., x n ] is a UFD for any amount of variables. Lemma A.1. Let p(t, z) ∈ R[t, z] be some polynomial that can be factorized as:EQUATIONwhere u i (z) is some polynomial of z.Then, such factorization is unique to the order of the terms (t -u i (z)).Proof.Gauss's lemma implies that R[t, z] ∼ = (R[z])[t] is a unique factorization domain. Since every polynomial of the form t -r(z) is an irreducible element in (R[z])[t], it follows that a factorization of the form p(t, z) = i (t -q i (z)) is unique up to permutation of the terms.Corollary A.2. The coefficients of the polynomial p X (t, z) defined in Section 4.2 form an ensemble of separating invariants.A.3 Proof of Theorem 4.2Proof. Let p X (t, z) 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.1 to get an analogous result to Theorem 4.1, arriving at the desired form.We represent p X (t, z) by evaluating its value on a grid of points (u s , v b ) where 0 ≤ s ≤ n, 0 ≤ b ≤ τ . Specifically, we can choose u s := e -2πi n+1 s and v b := e -2πi τ +1 b and to get the two-dimensional DFT of the polynomial coefficients:EQUATIONAgain, by setting Φ(X i ) to be the coefficients matrix of p i (t, z) = t -q Xi (z):EQUATIONwe get that:EQUATIONWhere the multiplication is elementwise. According to the 2D circular convolution theorem, this exactly amounts to convolving the vector coefficients of p i (t, z)s:EQUATIONA.4 On the stability of permutation-invariant representationsIdeally, we would like our representation to be numerically stable. That is, to require that if 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 [1] using the notions of bi-Lipschitzness and Wasserstein distance as we now recapitulate.Let X, Y be two multisets of d dimensional vectors with |X| = |Y| = n.Wasserstein distance. we measure the distance between equally sized multisets ⊆ R d using the notion of Wasserstein distance:EQUATIONWhere ∥.∥ is the L 1 norm over R d .We are interested in the bi-Lipschitzness property -whether there exist constants c, C > 0 such that:EQUATIONUnfortunately, it turns out that this notion of stability is unattainable by any differentiable permutationinvariant representation. We prove this by generalizing such results for sum-based aggregators [1] . Proposition A.3. Let f be some differentiable multiset representation. Then, there exist n, d such that for every ϵ > 0 there exist X ϵ , Y ϵ ⊆ R d two multisets of size n such that:EQUATIONAn independent proof for general invariant embeddings is given in [8] .Proof. Let f be some permutation-invariant representation. We use the same construction as in [1] and generalize the proof to arbitrary symmetric and differential representations.We choose n = 2 and some arbitrary d ∈ N.Let x 0 , d ∈ R d where d has a unit norm, and consider S h = {{x 0 + hd, x 0 -hd}}.We note that the Wasserstein distance W p (S h , S 0 ) is h. Thus, it is sufficient to show that:EQUATIONSince fk : R 2d → R is invariant we have that for every u, v ∈ R d : fk (u, v) = fk (v, u).The differentiability of fk at (u, v) implies that for every 1 ≤ i ≤ d:EQUATION)EQUATIONParticularly, this implies that ∂ i fk (x 0 , x 0 ) = ∂ d+i fk (x 0 , x 0 ).Using the differentiability of fk at (x 0 , x 0 ) we can write:EQUATIONPlugging in δ 1 = hd and δ 2 = -hd we get:EQUATIONEQUATIONAll in all, we have:EQUATIONMeaning that for every ϵ > 0 there exists sufficiently small h such that:EQUATIONIn 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 = m 1 • m 2 be the total representation size. We let κ be the number of slots in the refined version of SSMA. We first analyze the vanilla version of SSMA step-by-step: To further show that SSMA is scalable we computed the runtime of it compared to 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 3 SSMA runtime is comparable to other methods while achieving higher downstream task performance. TU Datasets [32] . We conducted experiments on five widely used datasets, including four bioinformatics datasets (ENZYMES, PTC-MR, MUTAG, and PROTEINS) and one movie collaboration dataset that relies solely on topological data (IMDB-Binary). While these datasets are all relatively small, as detailed in Table 4 , they span a diverse range of domains.The ENZYMES dataset consists of 600 enzyme graphs, where the task is to 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 in 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 a 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/test splits, we employ random 10-fold cross-validation for evaluation. The prediction task for all these datasets is multiclass classification, and we use accuracy as the performance metric.The IMDB-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 as 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.ZINC dataset [19, 22] . 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 a molecular property known as constrained solubility, which is calculated as "logP -SA -cycle" (octanol-water partition coefficients, logP, penalized by the synthetic accessibility score, SA, and the number of long cycles, cycle). In 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.OGB -Graph property prediction [21] . We conduct experiments on the commonly used ogbgmolhiv 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 to code for further details. The prediction task involves accurately predicting molecular properties, represented as binary labels, such as whether a molecule inhibits HIV virus replication. The ogbg-molpcba 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-molpcba is medium-sized. The evaluation metrics used are ROC-AUC for ogbg-molhiv and Average Precision (AP) for ogbg-molpcba. We used the official train/validation/test splits provided by the OGB team.OGB -Node property prediction [21] . 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 an 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 is multiclass classification to predict a product's category.The ogbn-arxiv dataset is a smaller directed graph representing the citation network among Computer Science papers indexed by the Microsoft Academic Graph (MAG). Each node represents an 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 two graph-level datasets from the Long-Range Graph Benchmark (LRGB): peptides-func and peptides-struct. Each graph in these datasets represents a peptide, a short chain of amino acids shorter than proteins and abundant in nature. Each amino acid is composed of many heavy atoms, making the molecular graph of a peptide much larger than that of a small drug-like molecule. Peptide graphs have a low average node degree. Still, they have significantly larger diameters compared to other drug-like molecules, making them ideal for studying long-range dependencies in Graph Neural Networks (GNNs). Both datasets use the same set of graphs but differ in their prediction tasks. Peptides-func is a multi-label graph classification dataset based on peptide function, while Peptides-struct is a multi-label graph regression dataset based on the 3D structure of peptides. More details can be found in the LRGB GitHub repository. We used the versions of the datasets available via PYG without any further preprocessing.Dataset statistics. The statistics of the datasets we used in our experiments are shown in Table 4 . We did not modify the features of the graph topology in any of the experiments except in the following cases:• For purely topological datasets lacking node features, we assigned the zero vector as the initial node feature. • For the large graphs "OGBN-arxiv" and "OGBN-Products," we undirected the graphs and then clustered them following [9] . We did it 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 in the paper, "DSS-GNN (GIN) (EGO+)."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 to the specific characteristics of the dataset's node and edge features. This initial layer can be either an embedding layer or a 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, a readout function is applied. Finally, a two-layer multilayer perceptron (MLP) with ReLU activation produces the output.Due to the flexibility of GraphGPS and its numerous configuration options, we selected and focused on a 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 4 attention heads. For the experiments that uses Positional Encoding we used random walk with length 20. This configuration was taken from graph-gps repository. The full initialization details are available in our code.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 a fair comparison to previous works [12, 38, 3, 15] . • For the TUDatasets (MUTAG, ENZYMES, PROTEINS, IMDB-BINARY), where there is no consensus on the parameter budget, we used a 500,000 parameter budget. An exception was made for ESAN, for which we used a 100,000-parameter budget to allow fair comparison. • For the OGB-N datasets, we used a 500,000 parameter budget. This is reasonable when considering the parameter counts of models on the ogbn-arxiv leaderboard and ogbn-products 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 as can be seen from ogbg-molhiv leaderboard & ogbg-molpcba leaderboard • For the LRGB datasets, we also used a 2,000,000 parameter budget as those datasets require deeper GNNs because they need to embed long-range dependencies in the graph.A summary of the parameter budget can be seen in Table 5 Table 5 : Parameter budget used for each dataset. *for the ESAN, we used a 300,000 parameter budget. **for the ESAN we used a 100,000 parameter budget.Parameter budget ogbg-molhiv* 500,000 ogbg-molpcba 2,000,000 ogbn-arxiv 500,000 ogbn-products 500,000 mutag** 500,000 enzymes 500,000 proteins** 500,000 ptc-mr** 500,000 imdb-binary** 500,000 zinc 100,000 peptides-func 2,000,000 peptides-struct 2,000,000We conduct our experiments using PyTorch Geometric as 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 (https://almogdavid.github.io/SSMA/ ). For ESAN [3] and VPA [38] , we 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 or evaluation protocols.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 MLP compressor rate. We define the compression rate γ as the ratio between the bottleneck rank and the inner aggregation representation dimension m. We perform a 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 a simple range search over [random, attention_slots]. • Effective neighborhood size: we search for the optimal neighborhood size κ. We perform a simple range search over [2,3,...,CLIP(max_neighbors,7)].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 in 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 are taken directly from [39] , SSMA results are generated by us using the code provided in [39] 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 new aggregation method, we employed the configuration specified by the authors in their experiments, as detailed in their repository). As shown in Appendix D.2, SSMA outperforms the proposed method. This demonstrates that even a method capable of learning a variety of aggregation functions experiences a relative decline in performance if 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 [19] using the aggregation from [25] 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 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 † [Given the significant improvement in GraphGPS performance with positional encoding, we conducted additional experiments involving GraphGPS with positional encoding. The experiment details are provided in Appendix C. As shown in Appendix D.3, SSMA enhances GraphGPS performance even with positional encoding. To achieve this, we conducted ablation experiments on two different datasets:1. "OGBN-Arxiv," a citation network where most nodes have a very low in-degree, while a few nodes have an extremely high in-degree. 2. "Proteins," a 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 a varying number of neighbors and types of MPGNN layers. The results are presented in Figure 5 . 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 an increase in the number of neighbors does not necessarily correlate with improved performance, which was apparent most prominently in "OGBN-Arxiv."Furthermore, we find that the GAT layer does not benefit from the proposed slot attention mechanism. This lack of improvement may be attributed to the intrinsic attention mechanism within the GAT architecture, rendering the additional attention mechanism redundant.In this experiment, we explore the performance of SSMA compared to sum-based aggregators across various hidden dimension sizes used by the MPGNN architectures. This investigation is motivated by two key objectives: i) To assess the relative gain of SSMA over sum-based aggregators in both the low-budget and high-budget regimes. ii) To analyze how the scaling behavior of sum-based aggregators compares to that of SSMA.We conducted ablation studies on the "IMDB-B" and "MUTAG" datasets to achieve these goals. For each dataset, we measured the test 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 . 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.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 tradeoff: fewer parameters for a larger number of hidden units or slots. We evaluate this trade-off on the "OGBN-Arxiv" and "ZINC" datasets to understand its effect on performance.The experiment results are presented in Figure 7 . As demonstrated above, we can observe that SSMA exhibits resilience to strong compression, 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.To validate the selection of our affine transformation, we conducted an ablation study where we initialized 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 9 . The experiments show a slight improvement when the affine transformation is 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. Justification: We provided information on method limitations in section 4.4. Guidelines:• The answer NA means that the paper has no 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 a separate "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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.meaning that distinct multisets should be mapped to distinct representations, hereby requiring a sufficiently large representation dimension m.If for two multisets we have e k (x) = e k (y) for all 0 ≤ k ≤ m, then p x (t) = p y (t) for all t, and therefore each one of the roots of the left-hand side polynomial corresponds to some root of the right-hand side polynomial. An inductive argument shows that this implies that both polynomials have the same roots. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	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.
2.	The inductive setting mentioned in the experimental setup section is missing from the experiments section.

[1] Inductive Representation Learning on Large Graphs. NeurIPS 2017. 
[2] Hierarchical Graph Representation Learning with Differentiable Pooling. NeurIPS 2018
questions: questions: Please refer to the weaknesses.
limitations: limitations: The limitations have been demonstrated in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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)​​.

- 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.
questions: 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?

- 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.

- 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?

- Are there specific types of graphs or tasks where SSMA may not perform as well as other methods?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).
Section 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.
questions: questions: Can you expand on the intuition of sum-based aggregators lacking mixing abilities?
limitations: limitations: Addressed
paper_summary: paper_summary: This paper focuses on the aggregation module in Message Passing Graph Neural Networks (MPGNNs). 
It 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.
 Accordingly, the authors introduce a novel plug-and-play aggregation for MPGNNs, denoted as Sequential Signal Mixing Aggregation (SSMA).
SSMA treats the neighbor features as 2D discrete signals and sequentially convolves them with circular convolution by applying 2D Fast Fourier Transform (FFT).
The authors also propose several designs to guarantee the practical use of the proposed methods.
In the empirical experiments, SSMA successfully improved the performance of several MPGNNs.
strength_weakness: strength_weakness: 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. 
2. 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")











- [1] Dwivedi, Vijay Prakash, et al. "Graph Neural Networks with Learnable Structural and Positional Representations." International Conference on Learning Representations.
questions: questions: 1. What is the configuration of GraphGPS in the experiment? As in the paper, several configurations are provided.
2. 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)

2. 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$).
    - I am interested to know the improvement of GRASS on GraphGPS on the 500K setting
    - Can GRASS improve MPNNs with PE?
limitations: limitations: The limitation on computational complexity is adequately addressed by the proposed technique.s
No potential negative societal impact aware.

Comments: title: Thank you
Official Comment by Reviewer QvY7
comment: Dear Reviewers,

We are extremely grateful to you for reviewing our responses. We deeply appreciate your positive feedback and the scores you raised. We promise to include all additional clarifications, experiments, and figures in the camera-ready version.
Thank you for the clarification and additional experimental proof to address my concerns. I raise my score to 5.
Thank you for the detailed response. I raise my score to 6.
Thank you for the rebuttal.

It well addresses my concerns and questions.

I will raise the score.
I would like to thank the authors for the rebuttal. I will keep my score since it was already positive. I also encourage the authors to include Figure 1 in the appendix, and refer to it in the main paper.
Dear Reviewers,

We hope this message finds you well. In the most respectful way possible, we would greatly appreciate your acknowledgment of the responses we have provided. We understand that the concerns raised are grounded in important factual matters, and we believe that we have addressed each one directly with clear additional results and thorough, non-evasive discussions.

Thank you very much for your time and consideration.