Spatio-Spectral Graph Neural Networks

We thank the reviewer for the valuable points and positive feedback. We will use the extra space in the camera-ready version to address the reviewer's points.

---

High-resolution filters for low frequencies

We truncate the spectral filter for efficiency reasons mainly, whereas the special choice of a low-pass window is required by neither our theoretical analysis nor by any specifics of its implementation (we state this in ll. 192-193, now moved out of §3.2 directly into §3 for clarity). While we intended ll. 149-167 to provide supplementary intuition as for why low-pass windows might be a sensible default, we do agree that this might distract the reader from initially understanding the essentials of our method. We intend to keep points (1) and (2) as main arguments (except for the point on "as graph problems discretize continuous phenomena [...]") and move the remainder (ll. 158-167) to the appendix.

---

Parametrizing spectral filters

To improve readability, we have rewritten the second sentence (ll. 240-241), explaining our use of the term "Gaussian smearing":

As depicted in Fig. 7, we learn a channel-wise linear combination of translated Gaussian basis functions (similar to the "Gaussian smearing" used by Schütt et al., 2017).

Moreover, we have overhauled the window discussion (ll. 247-253) to explain, first, how the Gibbs phenomenon adversely affects learning, and, second, how we alleviate it by overlaying the filters with a window function:

We multiply the learned combinations of Gaussians by an envelope function (we choose a Tukey window) that decays smoothly to zero outside the cutoff $\lambda_{\text{cut}}$. This counteracts the so-called "Gibbs phenomenon" (also known as "ringing"): as visualized for a path graph/sequence of 100 nodes in Fig. 8, trying to approximate a spatially-discontinuous target signal using a low-pass range of frequency components results in an overshooting oscillatory behavior near the spatial discontinuity. Dampening the frequencies near $\lambda_{\text{cut}}$ by a smooth envelope function alleviates this behavior. We note that the learned filter may, in principle, overrule the windowing at the cost of an increased weight decay penalty.

---

Additional structure to enhance presentation

To streamline the presentation and reading flow, we will use the extra space to introduce additional structure. Specifically, we have revised the paper to make sure that the overall "story arc" implied by Fig. 2 (core theory in §3.1-3.2, design space considerations in §3.3-3.6) is more closely aligned with the section structure: §3 of the revised manuscript will instead feature two subsections, §3.1 (Theoretical Analysis) and §3.2 (Design Space) that form the umbrella for the previous §3.1-3.2 and §3.3-3.7. This extra structure will allow for better guidance through the considerations around S$^2$GNNs. Naturally, we greatly welcome any additional suggestions on how to improve the presentation.

---

Positional encodings

We thank the reviewer for the helpful suggestions and we have extended the related work section accordingly. We would like to note that LapPE [2] (and accordingly LSPE [1]) breaks permutation equivariance (sign invariance is approximately enforced through augmentations; repeated eigenvalues are ignored). We will use the extra page to explicitly discuss this aspect in the revised manuscript instead of only referring to background literature. Experimentally, we have so far (implicitly) addressed LapPE, e.g., through our evaluations of GPS.

---

Further related work

We thank the reviewer for pointing out additional related work, and we have included them in our manuscript accordingly. Thus, we will implement the requested changes in the camera-ready version.

---

Runtime comparison of message passing and spectral filters

Great suggestion! Of course, the runtime comparison depends severely on the used hardware since it essentially compares a sparse matrix multiplication (adjacency matrix) with matrix multiplications on dense "tall and skinny" matrices (GFT). With OGB-arXiv (170k nodes) as the graph for comparison, we find that one GCN-layer here is as costly as a spectral filter with approx. 2,500 eigenvectors. We provide the detailed plot in the global PDF.

---

Additional dataset: PCQM

Since the primary download of PCQM-contact is currently not available, we report results on PCQM4Mv2 instead (also 3.4 million graphs etc.). Due to the time and resource constraints during the rebuttal phase, we were not able to tune the hyperparameters. Instead, here we manually merged the configuration from S$^2$GNN with the configuration from the Long Range Graph Benchmark. This yields a much smaller yet very effective model for PCQM4Mv2. For the camera-ready version, we intend to scale the model up and also follow the pretraining procedure of TGT-At (without using RDKit coordinates at test time).

We thank the reviewer for their feedback and for acknowledging the theoretical justification along with the ubiquitous possibilities of lifting GNNs to S$^2$GNNs. Furthermore, we thank the reviewer for highlighting that the paper contains a lot of intuitive analysis with examples.

---

W1: Pseudocode and notation table

We provide pseudo-code and a table covering the notations in the global response. If this does not fully address the reviewer's comment, we ask for clarification.

---

W2: Baselines

We include task-specific state-of-the-art baselines for each task/experiment (see Table 1 for peptides tasks, Table 2 for associative recall, in Table 10 for CLUSTER, and Table 12 for arXiv-year). In total, we compare to the following 21 baselines (see paper for full references): (1) GAT (Velickovic et al., 2018), (2) GCN (Kipf & Welling 2017; Tönshoff et al., 2023), (3) GatedGCN (Bresson & Laurent, 2018), (4) DirGCN (Rossi et al., 2023), (5) FaberNet (Koke & Cremers, 2024), (6) TIGT (Choi et al., 2024), (7) MGT+WPE (Ngo et al., 2023), (8) GraphMLPMixer (He et al., 2023), Graph ViT (He et al., 2023), (9) GRIT (Ma et al., 2023), (10) DRew-GCN (Gutteridge et al., 2023), (11) PathNN (Michel et al., 2023), (12) CIN++ (Giusti et al., 2023), (13) ARGNP (Cai et al., 2022), (14) GPS (Rampášek et al., 2022), (15) GPTrans-Nano (Chen et al., 2023), (16) Exphormer (Shirzad et al., 2023), (17) EGT (Hussain et al., 2022), (18) Transformer (Vaswani et al., 2017), (19) Transformer w/ FlashAttention (Dao et al., 2022), (20) H3 (Fu et al., 2023), (21) Hyena (Poli et al., 2023).

Following the suggestion, in the revised version of the manuscript, we will also include a comparison to further baselines on OGB Products (Table 3). It should be noted that the largest dataset considered by the suggested SpecFormer is arXiv (170k nodes). Scaling by >10x (Products, 2.5M nodes) would be prohibitively expensive due to SpecFormer's large required fraction of eigenvalues. Furthermore, SpecFormer does not discuss directed graphs and, thus, is not directly applicable to TPUGraphs (Table 4).

---

Q2: Scaling the eigendecomposition

There is no clear scalability limit for the eigendecomposition as calculating $k$ eigenvectors scales linearly in the number of edges $m$. However, it should be noted that the EVD of such large graphs will come at considerable computational cost and one should consider approximate methods. For example, there are open-source implementations for an approximate partial SVD (equivalent to EVD for PSD matrices) that support a hundred million rows and columns: https://github.com/criteo/Spark-RSVD.

---

Q3: Performance vs. number of eigenvectors on real tasks

We plot the influence of the number of eigenvectors in the global response (Figure 2) on the real-world dataset peptides-func. Since we here limit the number of eigenvalues by cut-off frequency $\lambda_{\text{cut}}$ (Figure 2a), we report the average number of eigenvectors in Figure 2b.

We thank the reviewer for their feedback and for acknowledging the theoretical justification along with the ubiquitous possibilities of lifting GNNs to S$^2$GNNs.

---

W1: Ablation on the combination of spatial and spectral filter

We agree with the reviewer that different combinations may yield beneficiary properties. In the camera-ready version, we will highlight that we focus on the simplest options, showing that the combination is very effective (Eq. 1 & 2). From an approximation-theoretic standpoint, choosing addition moreover recovers the analysis in §3.2 most naturally. Nevertheless, we value the suggestion and present the following comparison of concatenation, addition (Eq. 1), a Mamba-like composition, and arbitrary sequence of filters (Eq. 2), on peptides-func.

For the normalization, we add the factor $\sqrt{1/2}$ if aggregating two values and $\sqrt{1/3}$ for three values. We use the same hyperparameters as before and solely alter the aggregations. In a different set of experiments, we also tried BatchNorm and GraphNorm, which did not yield significant improvements.

We agree that there are many important aspects, including robustness like in [1]. However, it is not clear how to transfer their approach to our setting since we do not have the option to tie the weights of the spectral and spatial filters. We may try this option if the reviewer can provide more details on the specifics.

---

W2: Comparative Analysis

We do not state that S$^2$GNNs provide the only solution to over-squashing, but we would like to note that we did compare our method to a wide range of popular methods that overcome over-squashing, such as various graph transformer models and rewiring approaches. Our theoretical analysis can be extended to the mentioned GCNII [2] with similar conclusions. However, we want to highlight that although GCNII vanquishes over-smoothing, the information propagation through the graph is similarly constrained by the graph structure as in many other standard MPGNN architectures like GCN. This implies that GCNII does not effectively alleviate all potential over-squashing issues (i.e., information still needs to pass bottlenecks in the graph). We conducted additional experiments with GCNII on the peptides-func benchmark, using similar hyperparameters as GCN-tuned (Tönshoff et al., 2023) and varying the number of layers from 6 up to 64. While results in the standard 6-layer setting approach performance of GCN-tuned (AP of 0.6860±0.0050 with GCN, 0.6656±0.0004 with GCNII), performance starts to deteriorate after ~16 layers, which we conjecture to be caused by over-squashing.

We will include GCNII in the camera-ready version and appreciate further pointers if the point is not fully addressed.

We thank the reviewer for their critical thoughts about our work! We are convinced that we conclusively resolved all points brought up by the reviewer. We would highly appreciate a major reevaluation of our submission.

Before going into detail, we want to highlight that our empirical results yield conclusive evidence for the validity of the advocated GNN construction. For example, S$^2$GNNs outperform all prior message passing schemes, transformers, and graph rewirings on the long-range benchmark task peptides-func by a comfortable margin using substantially fewer parameters.

---

W1: Well known results repeated

Chief among our contributions is the exploration of novel GNN design spaces, given that a part of the model is parametrized explicitly on the spectrum. There indeed are reasonable parametrizations of such filters that would break permutation equivariance – e.g., truncating after a fixed number of eigenvectors, specifically if the last considered eigenspace is degenerate. As we show, each eigenspace must be either left out or included entirely to preserve equivariance. As our treatment substantially extends the traditional parametrization of spectral filters as Laplacian polynomials, proving that equivariance still holds is essential to the formal completeness of our work. Additionally, we capture a more general case than usual, considering complex-valued eigenvectors. We detail this in §F.1 and will highlight these differences in the method section as well.

We decided to include the fact that "locality relates to spectral smoothness" in the main part for readability reasons and because it is a vital insight for our method.

In case we missed important references etc., we would be glad to include them upon the reviewer's request.

---

W2: Connecting the dots

Since the reviewer focuses in their critique on the introduction, we want to briefly point out that the technical arguments can be found in the method section (§3, §3.1, and §3.2). From this technical viewpoint, combining both filters is a fundamental prerequisite for the approximation-theoretic guarantees derived in §3.2.

In the introduction, starting with Figure 1, we illustrate the complimentary limitations of each parametrization on its own. We state in lines 38-39 that a spectrally parametrized convolution should operate on a truncated frequency spectrum for efficiency reasons. This implies a limitation of a purely spectral parametrization. Finally, in lines 61-62, we state explicitly that the combination of both approaches alleviates over-squashing, providing a forward pointer to the technical argument.

In the camera-ready version, we plan to change

Conversely, spectral filters act globally (p_\max), even with truncation of the frequency spectrum ($\lambda_\text{cut}$) that is required for efficiency.

to

Conversely, spectral filters act globally (p_\max), even with truncation of the frequency spectrum ($\lambda_\text{cut}$). The truncation of the frequency spectrum is required for efficiency. Yet, the combination of spatial and spectral filters provably leverages the strengths of each parametrization.

We appreciate further suggestions and more details on potentially missing connections.

---

Q1: GNNs aim to learn data driven filters. Ideal filters may NOT be a “good” choice.

We empirically demonstrate that our parametrization can substantially improve over the prior state of the art, providing strong evidence that the capability of approximating ideal filters is useful! Perhaps we misunderstand a part of the reviewer's concern. However, it is common practice in deep learning to strive for a maximally general hypothesis class s.t. training can decide for a good parametrization in a data-driven manner. Popular examples include Graph Isomorphism Networks (GIN) [1] or even the well-known works on universal approximation. These works also show how to overcome certain limitations or how to obtain full generality. While we make a connection to universal approximation of idealized GNNs [2] explicit in lines 195-197, in the camera-ready version, we will elaborate more on the motivation in Section 3.2. We should also mention that the discontinuity is solely a worst-case example (lines 204-206) and that our approximation-theoretic discussion implies that S$^2$GNNs are strictly more powerful than Message-Passing GNNs (MPGNNs).

If this answer does not fully address the reviewer's questions, we kindly ask for clarification.

[1] Xu et al. How Powerful are Graph Neural Networks? ICLR 2019.

[2] Wang and Zhang. How Powerful are Spectral Graph Neural Networks. ICML 2022.

---

Q2 & W3: Directionality

The ability to support directed graphs shows the general applicability of S$^2$GNNs. For graph machine learning to generalize, e.g., sequence models, directedness is required. This is why we show that S$^2$GNNs are also exceptional sequence models in the associative recall task.

We are the first to use the Magnetic Laplacian for a spectrally parametrized filter. We provide the important and unique (e.g., for potential $q$) design decisions in lines 298-303 and §H.5. It should be noted that only very few MPGNNs, including MagNet (Zhang et al., 2021), also use the Magnetic Laplacian, out of the thousands of papers that work with graph neural networks.

We present results on directed graphs in Figure 12 (distance regression) and Figure 15 (associative recall), Table 2 (associative recall), Table 4 (TPU Graphs), Table 11 (distance regression), Figure 24 (distance regression), Table 12 (arXiv-year). We ablate the importance of directed graphs, e.g., in Figure 15 and Table 11. In both cases, directionality improves performance.

We will use the extra space in the camera-ready version to make these points more explicit and appreciate further suggestions.

Dear AC, dear Reviewers,

We greatly appreciate the discussion of our work and we cherish the feedback! In our view, the presented paper makes profound technical contributions and accordingly contains an above-average amount of content (see next paragraph). We made the conscious decision not to withhold any significant contribution from the main body and thus make sure that our work is reviewed in its entirety. While this enforces a more compact writing style, we would like to highlight that, indeed, none of the presented aspects was deemed unnecessary by the reviewers. Instead, reviewers EZD5, H69b, and rAa9 uniformly acknowledged our theoretical foundations/analysis of our Spatio-Spectral Graph Neural Networks (S$^2$GNNs), along with our method's general applicability and strong empirical results. We are moreover certain that the 11% extra space in the camera-ready version will suffice for the discussed adjustments to increase explicitness and, hence, address all the changes suggested by the reviewers.

Arguably, in comparison to impactful works like ChebNet [1] or GCN [2], our technical contributions are of much greater scope. In essence, ChebNet [1] made the Chebyshev-polynomial coefficients of [4] learnable, GCN [2] uses a fixed parametrization again but stacks multiple layers interleaved with non-linearities. Instead, we provide a new modeling paradigm rooted in approximation theory and signal processing that goes beyond pure recursive neighborhood aggregations and unlocks new design spaces.

We appreciate further feedback that would benefit our work.

[1] Defferrard et al. "Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering" (2016)

[2] Kipf & Welling "Semi-Supervised Classification with Graph Convolutional Networks" (2017)

[3] Veličković et al. "Graph Attention Networks" (2017)

[4] Hammond et al. "Wavelets on Graphs via Spectral Graph Theory" (2009)