Joint Graph Rewiring and Feature Denoising via Spectral Resonance

Reply to Reviewer Fauu (Part 1/2)

We thank the reviewer for their constructive comments and detailed feedback, particularly for drawing our attention to the topic of GNNs vs MLPs. In the following, we want to address the individual concerns mentioned by the reviewer. We will upload a revised paper soon. **Weaknesses:** > 1. The paper should better discuss previous works on GNN versus MLP, and the connection between heterophily and graph noise. [1-4] investigated the phenomena that MLP sometimes perform better than GNN (especially GCN) for heterophilic graphs. In particular, [4] proposed a metric that well correlates with empirical GNN performance, and also discussed the connection between heterophily and graph noise. A better discussion (acknowledgement?) of [4] is needed due to its high relevance to this paper. Thank you for bringing these works to our attention. We actually already cite the work of Dong and Kluger (2023) in our related work section, but we will highlight it more in the revised version in the context of graph denoising. As you suggest, MLPs indeed outperform GNNs in the weak graph regime; we have acknowledged that in the main text (line 354 ff.). But we emphasize that even in that regime, after applying JDR, GNN outperforms the MLP (cf. the discussion below on W.2). This suggests that in real-world datasets the graphs really do contain information that is complementary to features, and JDR can help tease it out. It means that GNNs can still perform strongly in this situation, provided that we first use this complementarity to denoise the graph. > 2. The comparison between JDR and graph rewiring methods seems not perfectly fair as the authors also mention themselves. You are right. We do state this since we aim to disclose the limitations of our method as transparently as possible. At the same time, since JDR is the first method to jointly denoise the graph and the features, there are no more direct comparisons that we can do. This is why we very explicitly state this under limitations. That is why many of our experiments focus on showing what advantage features bring to rewiring. We acknowledge that our wording may not reflect this clearly and will articulate it accordingly. The comparison is fair insofar as there is no restriction for other methods to use feature information---it's only that JDR is the only method that does. The real limitation of JDR is that it cannot be applied without node features. We will emphasize this in the revised manuscript. > Moreover, if JDR indeed achieves optimal denoising, then the graph may no longer be needed in later training. We do not think that JDR achieves optimal denoising (that does not even seem possible for real graphs). We will make this explicit in the revision. We do claim that it improves alignment between leading spectral spaces and consequently with the labels (as per Proposition 1 and numerical experiments). But even if denoising was in some sense optimal, due to the different inductive biases of different deep net architectures, it may still be favorable to provide different views of label information (as a graph and as features), since even optimal denoising cannot result in zero noise. As mentioned before, we consider cases where the graph and features contain complementary information. In this case, even an optimal, though graph-agnostic denoising, cannot restore the full information about the labels in the features (and vice versa). So we assume that by "optimal denoising" you refer to the case, where we also transfer information from graph to features (and vice versa). JDR is indeed designed such that it is able to perform this transfer due to it alternating joint denoising scheme. The experiments on cSBM verify this in the corner cases were either the graph or the features do not contain any information about the labels. In this case, the only way to improve is by transferring label information from one source to the other. However, this does not mean that the graph does not help for node classification anymore, which is visible for cSBM where GNN+JDR clearly outperforms the MLP in the very weak graph regime.

Reply to Reviewer Fauu (Part 2/2)

> This (JDR(X) + MLP) seems uncovered by the ablation settings. You are right. We ran new experiments corresponding to this ablation. Based on your W.2 we also became interested in how well an MLP with JDR can perform. The MLP+JDR experiments show to which extend JDR can transfer information from graph to features. These new results on the cSBM and real-world datasets can be found in Appendix A.5.3. We think they provide really interesting insight (so thanks again for suggesting them!), which we briefly present here. As you pointed out in the question and as we have seen in the main text, an MLP outperforms the GNNs in the weak graph regime. Now combining the MLP with JDR clearly outperforms GCN (especially in the heterophilic regime) and performs very similar to GPRGNN. However, if GPRGNN is combined with JDR, it again provides superior performance compared to MLP+JDR, **even in the heterophilic regime** which you highlighted. This supports our claim that GNNs can be the method of choice when the graph and the features contain valuable information, since they do use both. The described behaviors can be observed both on synthetic data from the cSBM and real-world datasets. > 3. The authors should check if the rewired graph structures degenerate, which may be a natural consequence of combining matrix factorization scheme and thresholding. Could you please elaborate what you mean by degenerate here? If you refer to the cases where the rewired graph splits into disconnected components or the corresponding matrices become low rank, we did not observe this with JDR. We do not threshold the spectrum (rather interpolate), but we do (hard) threshold the synthesized interpolated adjacency matrices: we retain the top-$k$ entries per node, resulting in the new, rewired edges. We should mention that we did observe one degenerate case on the Cornell and Texas graphs when we treated $k$ as a hyperparameter. The best choice for $k$ using a GCN as a downstream model ended up being close to $0$. This, however, did not happen with GPRGNN. This is compatible with our findings about the relative merits of GNNs and MLPs (also of W.1 and W.2) and with what we observed for DIGL on these datasets (l.426 ff.). Since these graphs are very noisy, removing edges is a good approach if the downstream algorithm is too weak to handle the high noise, which is the case for GCN. With better downstream algorithms which can handle the high noise, such as GPRGNN, the edge removal strategy is not optimal. We hope this speaks to your question, otherwise we'd be happy to discuss further. > 4. The hyperparameter tuning was not performed for the GNN backbone. This is questionable as the optimal backbone hyperparameter is anticipated to vary across different rewired graphs (and potentially different denoised features). This may matter because the performance gap between JDR and other methods seems small in most cases. We agree with the reviewer that we could achieve better results by also tuning the hyperparameters of the GNNs for each rewired graph. One could even go one step further and iteratively tune the parameters of JDR and the downstream GNN multiple times. We did not do it because it would **massively** increase the required GPU time and associated energy but it would not qualitatively change the findings. We agree with you that the results could only improve. Since we are not tuning the hyperparameters of the GNNs for all rewiring methods, we still achieve a fair comparison across methods. > 5. Some paragraphs are unclear and not readable. In particular, it is unclear what “findings” in the sentence “The Gaussian adjacency equivalence conjecture (Shi et al., 2024) suggests a generalization of the findings to the true binary adjacency case.” is referring to. The whole section (as well as the proof) needs to be polished. Thank you for pointing this out, we will rework these sections for clarity in the revision. The statement you quote in your question refers to an analytic technique used in the study of the cSBM (Deshpande et al., 2018). Random matrix theory gives us strong guarantees for Gaussian matrices, e.g., for Gaussian Orthogonal Ensembles (GOEs), but there are much fewer results for the actual binary adjacency matrices. The Gaussian adjacency equivalence conjecture (Shi et al., 2024) states that one can analyze a graph using a Gaussian adjacency matrix and then this analysis generalizes to the true binary adjacency. We use this reasoning to show that JDR improves alignment under the cSBM. We hope that this make our statement clearer; please do let us know if that is not the case.

Reply to Reviewer Pd13 (Part 1/2)

We thank the reviewer for thoughtful comments, positive review and the interesting questions, especially for drawing our attention to the derivation of JDR via the cSBM and its implications. In the following, we address the reviewer's concerns one by one. **Weaknesses:** > 1. The theoretical framework seems convincing to me, while how the real data sets fit the parametric model needs further investigation, otherwise the heuristic of denoising features might not be applicable. This is indeed an important topic and we discuss it in Appendix A.2, where we demonstrate the significance of the cSBM in GNN research. We wish to highlight two points: First, our extensive experiments clearly confirm that the reasoning for cSBM does transfer to real-world datasets to a large extent. Second, there is substantial evidence in the literature that the cSBM is a useful model in the analysis of GNNs and graph datasets. Important works include the theoretical studies of node-level GNN problems based on the cSBM, e.g., on double descent (Shi et al., 2024), neural collapse (Kothapalli et al., 2023), OOD generalization (Baranwal et al., 2021), or oversmoothing (Wu et al., 2023). Beyond being a standard synthetic benchmark, the cSBM is also used to verify hypotheses about GNNs (Ma et al., 2022; Luan et al., 2023). This does not mean that all the work is done. Like any model, the cSBM idealizes certain aspects of graph data which in some cases is a limitation; we discuss this as well in Appendix A.2. But there is overwhelming evidence (in particular experimental) that it is a very useful model to reason about graph data. > 2. More explanation is needed on the insights of where the rationale of denoising comes from, e.g. lines 159-190. Thank you for bringing this lack of clarity to our attention. We will improve these explanations in the revised manuscript along the following lines: Due to the quadratic and bilinear forms in (2), the optimal $\mathbf{v}^*$ is related to the leading singular vector in $X$ and second leading eigenvector in $A$. The reason for this is that each of the two subproblems would lead exactly to the corresponding eigen/singular vectors, so the overall formulation leads to a compromise between the two. Too see this, for simplicity, let us only consider $A$. In a balanced two-class SBM, we can write the adjacency as $$ A = \mathbb{E}(A) + (A - \mathbb{E}(A)) $$ where $\mathbb{E}(A)$ captures the expected structure of $A$ and $(A - \mathbb{E}(A))$ the fluctuations around its mean. Now consider without loss of generality that the nodes are sorted such that the first half belongs to class $1$ and the second half to class $2$. Then $\mathbb{E}(A)$ is a block matrix with structure $$ \mathbb{E}(A) = \begin{bmatrix} p \mathbf{1}\mathbf{1}^T & q\mathbf{1}\mathbf{1}^T \newline q\mathbf{1}\mathbf{1}^T & p\mathbf{1}\mathbf{1}^T \end{bmatrix} $$ where $p$ is the probability of links between nodes of the same class and $q$ between nodes of different classes. Let the vector of class labels be $\mathbf{y} = [1, \ldots, 1, -1, \ldots, -1]^T$. Then we can write $$ \mathbb{E}(A)=\frac{p+q}{2}\mathbf{1}\mathbf{1}^T+\frac{p-q}{2}\mathbf{y}\mathbf{y}^T. $$ For small fluctuations (high SNR, $|\lambda| \gg 1$), $A \approx \mathbb{E}(A)$. Then $A$ is approximately a rank-$2$ matrix and we can directly see that $\mathbf{y}$ is the second leading eigenvector. Even for lower SNRs there will be substantial alignment between $\mathbf{y}$ and the label vector. A similar reasoning can be applied for the leading left singular vector in $X$. Together this shows that the optimal $\mathbf{v}^*$ is related to the labels $\mathbf{y}$. We hope that this provides more clarity; if not we would be happy to answer further questions. > 3. Since the eigendecomposition is applied on adjacency, the comparison of training and inference time costs between the vanilla GNN and with the add-on of the proposal is needed. We thank the reviewer for the suggestion (together with FthW who made similar remarks). We agree that this comparison would strengthen the paper. We ran the requested experiments and added them to the revised paper. We also discuss implications and limitations of such an analysis. The results do not show a clear "winner"; JDR generally requires a comparable or shorter time compared to baselines. The reasons for these ambiguities are, among others, that results depend on many hardware and framework-related factors. In our particular case we should add that different hyperparameter choices of the rewiring methods lead to dramatically different run times (even when applying the same method on the same dataset). For example, FoSR is quite fast on the large Twitch-gamers dataset as it only runs for $5$ iterations, while it is slow on the smaller Questions dataset, where it runs for $700$ iterations.

Reply to Reviewer PNCZ

We thank the reviewer for their positive comments and thoughts and suggestions on computational aspects of JDR. In the following, we address the reviewer's concerns. A revised manuscript will be uploaded soon. We look forward to further feedback. **Weaknesses:** > The proposed method involves graph structure matrix and graph feature matrix decomposition, which can be computationally challenging on extremely large real-world graph data, limiting the practicability of the proposed method. As you suggest, it may be challenging to apply JDR out of the box to *extremely* large graphs. But this is true for any method, and in particular for all preprocessing rewiring methods. We specifically discuss the issue of scalability in Section 3.2 of the main paper. While scalability is a general limitation of preprocessing rewiring methods (if one wants to work with huge graphs), JDR is at least as good and in many cases more scalable than the baselines. We show in the accompanying experiments that we can still use JDR on graphs up to size of $168$k nodes and millions of edges and outperform the baseline methods. The strongest baselines like BORF are not applicable in this regime. JDR handles these cases without specific optimization for very large graphs. By carefully engineering a more efficient implementation, we are confident that JDR can be extended to graphs with millions of nodes (as for the ogbn-products mentioned below), but that entails substantial new research which is outside the focus of this paper. > As the SVD decomposition can have time complexity of $O(N^3)$, it may be not accurate to say the proposed JDR has time complexity of $O(N)$ Thank you for pointing this out; we should state it more clearly in the revised version. Our estimate is based on the following reasoning: 1) real graphs are more or less sparse, and 2) we only need the top-$k$ spectral spaces, not the full eigen/singular value decompositions. We discuss this in Appendix A.1.3: The complexity to obtain the top-$k$ eigenvectors (using variants of the power method) scales as $\mathcal{O}(N^2k)$. For sparse matrices this further reduces to $\mathcal{O}(\text{nnz}(A)k)$ where $\text{nnz}(A)$ is the number of non-zero elements in $A$. If the average degree $d$ does not scale with $N$, the complexity becomes $\mathcal{O}(N)$. As mentioned above, we will state these estimates much more explicitly in the revised manuscript. **Questions:** > As the computation overhead of the proposed method seems large, can it be applied to large graphs, e.g. ogbn-products? Please refer to our response to W.1. In a nutshell: graphs with more than $200$k nodes would present a challenge for our current code, but we believe a careful implementation of sparsity-aware power method would be able to handle them.

Reply to Reviewer VArZ

**Weaknesses:** 1. We disagree with this statement. Can you elaborate in what sense or relative to what earlier work is our manuscript somewhat incremental or of low novelty? We don't know of other methods that rewire the graph with feature information (and even less so of methods that jointly denoise both). We believe that our contribution is rather original. We also think that our approach to analysis is original (certainly not incremental) and we are confident that it will inspire new theoretical work. We have not seen anything related in the literature. 2. It would indeed be great to have a guarantee for downstream performance on node classification problems, but showing something like this is extremely challenging as it depends on the downstream GNNs and unknown data distributions. Such guarantees are also not available for any other rewiring method. In Proposition 1, we proved that JDR increases alignment of graph and node features with the labels under the cSBM assumption. We agree that there is still a gap between this and quantifying the degree of improvement, but at the same time we emphasize that the proof we have provided is the first of its kind and a step in this direction. We are working on a broader quantitative theory, but this will be a contribution on its own as it is non-trivial even under the assumption of synthetic data and a single-layer linear GCN. We do provide extensive numerical experiments and ablations which demonstrate effectiveness of JDR with overwhelming statistical significance. 3. We strongly disagree with the reviewer on this statement. The amount of experimental evaluation in our work is almost excessive. We have evaluated the effectiveness of JDR on numerous datasets and in numerous experiments and combinations. This was explicitly pointed out by reviewer Fauu end implied by others. Here are concrete numbers: In the main text we provide results on **17 synthetic** and **13 real-world** datasets with different sizes, properties and homophily levels. This results in **214 distinct experiments**. In the appendix, we further extend these with three additional real-world datasets, additional splits, ablations on JDR(X) and JDR(A), ablations on the parameters of JDR and experiments with spectral clustering **resulting in additional 300+ experiments**. Comparing this to related papers on FoSR or BORF, we not only consider many more datasets, but also provide much more diverse experiments. We respectfully ask the reviewer to reconsider their judgment in the light of these facts. **Questions:** > My main concern with this work is [...] there is really no theorectical ground on its effectiveness in general when applied to a wider range of datasets. Please refer to our response to W.2 and W.3. > Also, the datasets used are very small and I'm not sure how useful and how scalable the method is in practice. We specifically discuss scalability in Section 3.2 of the main paper. While scalability is a general limitation of preprocessing rewiring methods (if one wants to work with huge graphs), JDR is at least as good and in many cases more scalable than the baselines. We show in the accompanying experiments that we can still use JDR on graphs up to size of 168k nodes and millions of edges and outperform the baseline methods. The strongest baseline methods like BORF are not applicable in this regime. JDR handles these cases without specific optimization for very large graphs. By carefully engineering a more efficient implementation, we are confident that JDR can be extended to graphs with millions of nodes, but that entails substantial new research which is outside the focus of this paper. The original theoretical guarantees we give are a good indication of SNR regimes where JDR can be effective regardless of graph size. Most real graphs from biology and medicine that we deal with on a daily basis have numbers of vertices in the thousands, occasionally tens of thousands, suggesting that these sizes are relevant for applications. > [...] if the authors can either theoretically show how much improvement can be obtained using their method Please see our response to W.2. > or empirically demonstration the effectiveness on a wide range of datasets, not just on common datasets [...] Some of the datasets we used are indeed established benchmarks. This is the norm in the community and it enables rigorous comparison with baselines which is invaluable for fair evaluation. That said, as we explained above, we used an enormous diversity of datasets, including some that are rarely seen in the rewiring literature (e.g. Platonov et al., 2023 and Lim et al., 2021.) To our knowledge, the datasets we compiled for this paper never appeared together in a single publication in the field. Again, we respectfully ask that you reconsider your judgment in the light of the diversity of experiments we performed.

Reply to Reviewer FthW

We thank the reviewer for their positive comments and feedback. In the following we address the concerns mentioned by the reviewer. We will upload an accordingly revised version of the paper very soon. **Weaknesses:** > JDR depends on the availability of informative node features for effective rewiring and denoising, which restricts its applicability to settings with substantial node feature information; this reliance could limit its effectiveness in networks that primarily encode structural data. This is indeed true. We point it out in the paper and discuss it as an intrinsic limitation of our approach. At the same time, we emphasize that it is also an advantage of our method over others that it can leverage the information contained in the node features if they are available. > The algorithm’s design is also tailored to node-level tasks, making it less suited for graph-level tasks like graph classification, where global structure matters more than node-specific features We agree with this as well. (We discuss it as well in the paper.) The reason for this is that the derivation of JDR is closely related to the cSBM and thus also adopts some of its limitations. How to extend the cSBM idea to graph-level problems is an interesting fundamental research question. **Questions:** > could timing comparisons of the proposed methods, more explicitly and beyond just complexity comparison, be provided to observe computational benefits/limitations? This is indeed possible (reviewer Pd13 made a similar remark). We ran the requested experiments and added them to the revised paper. We also discuss implications and limitations of such an analysis. The results do not show a clear "winner"; JDR generally requires a comparable or shorter time compared to baselines. The reasons for these ambiguities are, among others, that results depend on many hardware and framework-related factors. In our particular case we should add that different hyperparameter choices of the rewiring methods lead to dramatically different run times (even when applying the same method on the same dataset). For example, FoSR is quite fast on the large Twitch-gamers dataset as it only runs for $5$ iterations, while it is slow on the smaller Questions dataset, where it runs for $700$ iterations.