We thank the reviewer for the careful and constructive review.

Additional Comparison with Spectral GNNs:

Thank you for the comment.

Following the reviewer's request, we included JacobiConv, BernNet, Specformer, and OptBasisGNN in our node classification experiment.

Moreover, motivated by other comments about heterophilic graphs, we extended NLSFs to include an additional filter capturing the band that contains the remaining non-leading eigenvectors, which we call rem-NLSFs. For Index NLSFs, we incorporate $\mathbf{I} - \sum_ {j=1}^J \mathbf{P}_ j$, and for Value NLSFs, we add the $\mathbf{I} - \sum_ {j=1}^K g_ j(\mathbf{\Delta})$. This alleviates the loss of information due to projecting to the low-frequency bands. All of our proofs are trivially extended to rem-NLSFs. If the reviewer would like to see the new proofs, which are almost identical to the old ones, we can send an anonymous PDF file to the AC according to the regulations of NeurIPS.

Table 2 of the global response PDF presents the node classification accuracy for these methods and rem-NLSFs. We see that rem-NLSFs outperform the other models on the Cora, Citeseer, and Chameleon datasets. For the Pubmed and Actor datasets, rem-NLSFs achieve the second-best results. Adding the orthogonal component alleviates the loss of information due to projecting to the low-frequency bands and, therefore, further improves the empirical results. The new experiments will be included in the camera-ready version if accepted.

Additional Discussion on Equivariant GNNs:

Thank you for this feedback.

While Section 2 already shortly discusses the background of Equivariant GNNs, we add an extended review in the appendix to include more works:

In recent developments on equivariant GNN model design, Satorras et al. (2021) introduced a new model for learning graph neural networks (GNNs) that are equivariant to rotations, translations, reflections, and permutations, Huang et al. (2023) developed an approach for designing GNNs that respect approximate automorphism symmetries. Additionally, Lim et al. (2023) presented SignNet and BasisNet, which process eigenvectors invariant to sign and eigenspaces. Different from these methods, Kofinas et al. (2024) proposed representing neural networks as computational graphs of parameters. In a more theoretically oriented work, Keriven et al. (2019) extended the Stone-Weierstrass theorem for the algebra of real-valued functions to the equivariant case, and Karczewski et al. (2024) established a generalization bound for E(n)-Equivariant GNNs. Azizian et al. (2021) explored the expressive power of message-passing GNNs, linear GNNs, and folklore GNNs, for both their invariant and equivariant versions. Additionally, Puny et al. (2023) introduced an alternative expressive power hierarchy to evaluate GNNs based on their ability to approximate equivariant graph polynomials.

We will also include a more detailed comparison to methods that consider graph automorphisms as symmetries, like Huang et al. (2023). Let us explain the main idea of the comparison. The goal is to illustrate that functional translations are more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Automorphisms are another analog to translations on general graphs, which competes with our notion of functional shifts. Consider as an example the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we claim that functional shifts are not so sensitive. To visualize this, we conducted a toy experiment that illustrates that graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 presents the performance of the NLSF, which is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).

[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.

[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.

[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.

Experiments Highlighting the Benefits of Equivariant Learning:

Thanks for this comment.

It is important to note that the connection between graph isomorphism testing and GNNs is primarily theoretical. In practical applications, spectral GNNs are not commonly utilized for direct isomorphism testing to the best of our knowledge. We would appreciate it if the reviewer could provide any specific work they are referring to for further clarification.

Following the reviewer's suggestion, as explained above, we added a new toy example demonstrating how a standard translation can be estimated by a graph functional shift on a perturbed grid, which shows the robustness of functional shift symmetries. We then train an NLSF MNIST classifier, which illustrates that NLSFs can roughly implement CNN-like architectures, also on a perturbed grid.

Thank you again for your valuable feedback. We will include these examples in the camera-ready version if accepted.

Thank you for your comment.

Please note that in Section 4.1, we discussed the complexity of our method. We elaborated on the efficiency of the Lanczos algorithm, which is well-known for its computational efficiency. For estimating the leading $J$ eigenvectors, the Lanczos algorithm takes $O(JE)$ operations per iteration and converges very fast, where $E$ is the number of edges. Hence, the Lanczos algorithm is as efficient as a message-passing neural network that operates on features of dimension $J$.

Section 4.1 already discusses the efficiency of the Lanczos algorithm, but we will extend the text and make this clearer. We will clarify that the Lanczos algorithm (for sparse graphs) can be seen as a message-passing algorithm, as it only uses the nonzero entries of the matrix, which are interpreted as edges in our context of graph machine learning.

Additionally, we reported the runtime analysis in Appendix C, where the average running time per epoch(ms)/average total running time(s) of our method is 18.22/4.5 for Cora, 18.51/4.4 for Citeseer, 20.23/6.1 for Pubmed, 28.51/17.1 for Chameleon, 25.56/5.1 for Squirrel, and 17.09/4.6 for Actor. In comparison, for example, the runtime for ChebNetII is 20.53/5.9 for Cora 20.61/5.7, for Citeseer, 33.57/12.9 for Pubmed, 39.03/17.3 for Chameleon, 37.29/38.04 for Squirrel, and 40.05/9.1 for Actor. Our method is efficient and comparable with competing baselines.

We appreciate the reviewer's feedback and will make sure that these points are more explicitly detailed in the camera-ready versions if accepted.

We thank the reviewer for the positive and encouraging comments.

Enhancing Accessibility of Theoretical Contributions:

Thank you for your comment.

We recognize the importance of making our manuscript accessible to a broader audience. To improve accessibility, we will provide more details on the mathematical concepts in the appendix. For instance, we will write and explain Schur’s lemma, extend the discussion on random geometric graphs, and elaborate on the background of the cut norm and Hoeffding's inequality.

Clarifying the Concept of Functional Translation on Graphs for Enhanced Accessibility:

We will extend the text in Section 3.1 to further clarify the link between graph functional shifts and standard domain translations. We will start by showing that on the standard grid (on the 2D torus) with central difference GSO, the standard Fourier basis is the eigenbasis of the Laplacian. We will then show that any domain shift on the grid, when applied on signals, is equivalent to modulation in the frequency domain. Hence, domain shifts commute with the Laplacian (both of them are diagonal matrices in the frequency domain). Functional shifts are defined by adopting this property as a definition. We call any unitary operator that commutes with Laplacian a graph functional shift. For the grid, these include exactly the operators that multiply each frequency by a complex number of unit modulus.

Fig. 1 (in the global response PDF) presents a comparison of a classical and a functional translation of a Gaussian signal. The classical translation $f(t-T)$ is a specific case of functional translation, which is equivalent to modulation in the frequency domain $e^{-i\omega T}\hat{f}(\omega)$. Our example of a graph functional shift is an operator that modulates low frequencies by a given rate and modulates high frequencies by another rate. This is interpreted as shifting the low-frequency content and the high-frequency content of the signal at different speeds. This illustrates that functional symmetries are more rich than domain symmetries.

In addition, we add another experiment showing that functional translations are much more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Autonorpisms are another analogue to translations on general graphs, which competes with our notion of functional shifts. Consider again the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we propose a toy experiment that illustrates the graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 shows that the performance of the NLSF is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).

These examples will be incorporated into the camera-ready version if accepted, including the discussion about automorphism symmetries vs functional shifts.

[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.

[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.

[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.

We thank the reviewer for the positive feedback.

Enhancing Writing Quality for Improved Readability and Clarity:

Thank you for your valuable feedback.

In response to the reviewer’s suggestions, we will make the following revisions:

• Introduction Section: We will reorder the paragraphs in the introduction. Specifically, we will highlight the research gap earlier in the section.
• Method Section:
  • We will emphasize that $\rho$ is any non-linear activation function (such as ReLU, Sigmoid, etc.). We will include the following explanation of why non-linear activation functions break the functional symmetry. We offer a construction for complex-valued signals, which is easy to extend to the real case. Consider a 1D grid with $100$ nodes and the central difference Laplacian. Here, the Laplacian eigenvectors are the standard Fourier modes. In this case, one can see that a graph functional shift is any operator that is diagonal in the frequency domain and multiplies each frequency by any complex number with the unit norm. Consider the nonlinearity that takes the real part of the signal and then applies ReLU, which we denote in short by ReLU. Consider a graph signal $x=(e^{i\pi 10n/100} + e^{i\pi 20n/100})_{n=0}^{99}$. We consider a graph functional shift $S$ that shifts frequencies 10 and 20 at a distance of 5, and every other frequency is not shifted. Namely, frequency 10 is multiplied by $e^{-i\pi 50/100}=-i$, frequency 20 by $e^{ -i\pi = -i\pi 100/100}=-1$, and every other freequency is multiplied by 1. Consider also the classical shift $D$ that translates the whole signal by $5$ uniformly. Since $x$ consists only of the frequencies 10 and 20, it is easy to see that $Sx=Dx$. Hence, $ReLU(Sx)=ReLU(Dx)=D(ReLU(x))$. Conversely, if we apply $ReLU(x)$ and only then shift, note that $ReLU(x)$ consists of many frequencies in addition to 10 and 20. For example, by nonnegativity of ReLU, $ReLU(x)$ has a nonzero DC component (zeroth frequency). Now, $S(ReLU(x))$ only translates the 10 and 20 frequencies, so we have $S(ReLU(x))\neq D(ReLU(x))=ReLU(S(x))$. We will add this example to an appendix.
  • We will revise the sentence, "Instead, functional shifts are related to the notion of functional maps..." into "Instead, functional shifts are general unitary operators that are not permutation matrices in general. The value of the functionally translated signal at a given node can be a mixture of the content of the original signal at many different nodes. For example, the functional shift can be a combination of shifts of different frequencies at different speeds."
  • We will also explain in detail why spectral filters commute with graph functional shifts. This is easily seen from the fact that both spectral filters and functional shifts are diagonal operators in the graph Fourier domain.

Visualizing Learned Features and Demonstrating Relaxed Symmetry:

Visualizing the learned filter directly is not feasible due to its high-dimensional nature: the filter is a general MLP, which makes it challenging to visualize in a meaningful way (as is typically the case in deep learning). However, to illustrate the concepts of relaxed symmetry and functional translation, we will add a new toy example. Similarly to the above construction, one example of a functional translation on the grid, which is not a classical translation, is an operator that translates different frequency bands at different speeds. In the example, we compare the translation of a Gaussian signal on a 2D grid by a classical uniform translation and by different speeds for different frequencies. See the experiments in the rebuttal PDF.

In addition, we add another experiment showing that functional translations are much more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Autonorpisms are another analogue to translations on general graphs, which competes with our notion of functional shifts. Consider again the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we propose a toy experiment that illustrates the graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 shows that the performance of the NLSF is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).

These examples will be incorporated into the camera-ready version if accepted, including the discussion about automorphism symmetries vs functional shifts.

[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.

[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.

[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.

We thank the reviewer for the insightful comments and questions.

Complexity, Efficiency, and Runtime Analysis:

In Section 4.1, we discussed our method's complexity and efficiency, highlighting the efficiency of the Lanczos algorithm. This algorithm estimates the leading $J$ eigenvectors in $O(JE)$ operations per iteration and converges quickly, making it as efficient as a message-passing neural network with $J$-dimensional features.

We will extend Section 4.1 to clarify that the Lanczos algorithm can be viewed as a message-passing algorithm for sparse graphs, using only the matrix's nonzero entries, interpreted as edges in graph machine learning. In addition, we reported the runtime analysis in Appendix C, where the average running time per epoch(ms)/average total running time(s) of our method is 18.22/4.5 for Cora, 18.51/4.4 for Citeseer, 20.23/6.1 for Pubmed, 28.51/17.1 for Chameleon, 25.56/5.1 for Squirrel, and 17.09/4.6 for Actor. In comparison, for example, the runtime for ChebNetII is 20.53/5.9 for Cora 20.61/5.7, for Citeseer, 33.57/12.9 for Pubmed, 39.03/17.3 for Chameleon, 37.29/38.04 for Squirrel, and 40.05/9.1 for Actor. Our method is efficient and comparable with competing baselines. Furthermore, we will include the space overhead (MB) of our method: 79 for Cora, 163 for Citeseer, 2054 for Pubmed, 85 for Chameleon, 263 for Squirrel, and 319 for Actor. In comparison, the space overhead for ChebNetII is 67 for Cora, 159 for Citeseer, 1821 for Pubmed, 79 for Chameleon, 259 for Squirrel, and 316 for Actor.

We also explain below how we addressed the limitation of computing only the leading eigenvectors. We slightly extended the NLSF method (the extension is called rem-NLSF), which now allows capturing all of the frequency contant of the graph. See the details below.

Theoretical Analysis on Heterophilic Graphs and Large-Scale Datasets:

Thank you for your comment.

We would like to clarify that in our first submission, we used three heterophilic graphs (Chameleon, Squirrel, and Actor) among the six datasets for the node classification task. We will emphasize this point more clearly in our revised version.

Motivated by the reviewer's question, we extend our approach to include an additional filter in both Index and Value NLSFs. For Index NLSFs, we incorporate the $(J+1)$-th filter as $\mathbf{I} - \sum_ {j=1}^J \mathbf{P}_ j$, and for Value NLSFs, we add the $(K+1)$-th filter $\mathbf{I} - \sum_ {j=1}^K g_ j(\mathbf{\Delta})$. This alleviates the loss of information due to projecting to the low-frequency bands. Now, the full spectral range of the signal is captured by the NLSF.

We denote these NLSFs with orthogonal complement as rem-NLSFs. This setup is particularly relevant for heterophilous graphs, which require high-frequency components to accurately represent the labels. Table 2 presents the classification performance, and we see that rem-NLSFs improve performance for heterophilic graphs. We will motivate this construction in our paper from the perspective of heterogeneous components of the target.

The theory, and all of our proofs, trivially extend to rem-NLSF. If the reviewer would like to see the new version of the proofs, which are almost identical to the old proofs, we would be more than happy to send an anonymous PDF file to the AC according to NeurIPS regulations.

In addition, following the reviewer's questions, we conduct additional tests on five large heterophilic graphs: Penn94, Pokec, Genius, Twitch-Gamers, and Wiki datasets from Lim et al. (2021). The experimental setup is in line with previous work by Chien et al. (2021), Lim et al. (2021), and He et al. (2022). We use the same setup for our NLSFs as reported in Appendix B. Table 1 (in the global response PDF) presents the classification accuracy. We see that rem-NLSFs outperform the competing methods on the Penn94, Pokec, Genius, and Wiki datasets. For the Twitch-Gamers dataset, rem-NLSFs yield the second-best results. Our additional experiments show that our method could indeed scale to handle large-scale graphs effectively.

Thank you again for the valuable comment.

Expressivity:

We note that graph-level NLSFs are bounded by the expressive power of MPNNs with random positional encodings. For example, in [1], the authors showed that random features improve GNN expressivity, distinguishing certain structures that deterministic GNNs cannot. The Lanczos algorithm for computing the leading $J$ eigenvectors can be viewed as a message-passing algorithm with a randomly initialized $J$-channel signal.

In Section 4.3, we discuss the expressivity in the context of a single fixed graph with variable signals. This setting is unrelated to the traditional graph isomorphism test hierarchy of expressivity.

At the graph-level, our example in Appendix A.2.4 can be used to show that graph-level NLSFs (without synthesis and pooling) are not more expressive than spectral GNNs. We also have an approach for showing that spectral GNNs are more expressive than graph level NLSF (without synthesis and pooling), but it requires very high dimensional features and unstable filters. If the reviewer would like to see the analysis, we can write you a comment in OpenReview or send an anonymous PDF to the AC according to the NeurIPS regulations.

Regarding pooling-NLSFs, we do not have an answer to whether standard spectral GNNs are more powerful than pooling-NLSFs with unlimited resources. A more practically useful question is comparing their expressivity within the same parameter budget. This is a theoretically challenging question. However, in practice, NLSFs typically perform better than standard spectral GNNs with equal budgets, or equivalent architecture. This comparison is also valid for graph-level NLSF (without synthesis and pooling).

We will add a discussion on these points in the camera-ready version if accepted.

[1] Sato et al. (2021). Random features strengthen graph neural networks.