Shape-aware Graph Spectral Learning

Dear Reviewer 7Vz6,

We are grateful to the reviewers for his/her time and thoughtful evaluation of our paper. Here are our responses and answers.

W1: In the presented theorem, the two compared graph filters have the same response norm, which is reasonable but not the case for many existing spectral GNNs. My concern is that, although the theorem is correct, some existing spectral GNNs can still fit the desired shape by further increasing the overall norms of their responses. This is not a technical flaw but needs to be further discussed.

RW1:

1. In Theorem 1, the reason why we assume two filters have the same response norm is to avoid the trivial solution. To be more specific, we made two assumptions. (1) before a certain point $m$, $g_1(\lambda_i)<g_2\left(\lambda_i\right)$; after the point $m$, $g_1\left(\lambda_i\right) > g_2\left(\lambda_i\right)$. (2) $g_1$ and $g_2$ have the same output norm.
   If we don’t assume they have the same norm, consider the following scenario: $g_1(\lambda_1) = g_2(\lambda_1) - e < g_2(\lambda_1)$, and $g_1(\lambda_i) = g_2(\lambda_i) + E >> g_2(\lambda_i)$, for $i \ge 2$, where $e$ is a very small value ($10^{-5}$) and $E$ is a very large value ($10^{5}$). In this case, assumption 1 is still satisfied. However, because $E$ is an extremely large value, almost all of the frequencies are involved in the final representations, which are meaningless and contain no information. Therefore, we only compare two filters with the same norm.

2. Increasing the overall norm of the output values does not mean that the filter can fit better because what really matters is the relative difference between high and low frequencies, not their absolute values. Consider we have a certain filter $g$, and then we multiply its output values by 2 to get $g’ = 2g$. Obviously, $||g’||_2^2 = 4||g||_2^2$. However, they have the same expressive power because the output results are just multiplied by a constant.

3. We adopted these assumptions solely for the purpose of understanding which types of filters are favored by a graph with a specific homophily ratio. However, in practical applications, we do not impose any restrictions on the norm of the spectral filter. A filter that incorporates beneficial frequencies and discards harmful frequencies is likely to yield good results. This is proved by our experiments.

W2: In the experimental setup, GCN is regarded as a spatial GNN method, which is not that necessary, in my opinion. To my knowledge, GCN is often analyzed as a simplification of the Chebyshev polynomial approximator.

RW2: Thanks for pointing this out! Yes, you are totally correct. GCN can be considered as both spatial and spectral methods. Actually, according to [1], most GNNs can be explained as both spatial and spectral. And this does not affect our analysis and results.

Q1: I am wondering how you calculate the homophilic level ($h$) when there is just a tiny fraction of nodes are labeled. Actually, this is a crucial factor for the explicit shape-aware regularization to work well, according to my understanding of this work.

RQ1: In the initial epoch, we compute the homophily ratio using the given training labels. Then, in every subsequent epoch, we update this ratio by considering both the original and the predicted labels. Table 6 compares the actual homophily ratios with estimated homophily ratios by our method. The similarity between these two sets of ratios indicates that our method can estimate the homophily ratio accurately.

Q2: I tried your code. There are some questions that need to be answered so that I can reproduce your reported results...

RQ2:

1. Yes, you are correct, the weight_decay is chosen from {0, 0.0005}. And we tune the dropout and dprate among {0, 0.1, 0.3, 0.5, 0.7, 0.9}. If you use Optuna, the code would be.

dropout = trial.suggest_categorical("dropout", [0.0, 0.1, 0.3, 0.5, 0.7, 0.9])
dprate = trial.suggest_categorical("dprate", [0.0, 0.1, 0.3, 0.5, 0.7, 0.9])

We have revised the paper accordingly and submitted the new version.

2. Thanks for noticing this. Except that, the "dropout" and "dprate" should also be tuned, other parts are correct. You may increase the number of trials to get better results. To ensure better reproductivity, we have updated the code and done the following things:
   (1) We provide our virtual environment and optimal hyperparameters in scripts.sh to reproduce results in Table 1.
   (2) We give the code to search optimal hyperparameters using Optuna.
   (3) We provide the code to reproduce the results in the case study in Section 3.
   All of these are in the instructions in README.md (https://anonymous.4open.science/r/NewtonNet-8115/README.md).

  Hope this will help! Shall you have any other questions, please feel free to let us know, we will be happy to answer. If there’s no further concern, we sincerely hope that you will increase your rating.

Reference:
[1] Revisiting Graph Neural Networks: All We Have is Low-Pass Filters.

Dear Reviewer LpUg,

Thank you for your dedication to reviewing our paper. We would like to kindly remind the reviewer that many of the questions/comments are irrelevant to our paper. For example, your comments state interpretability, outliers, and noisy data in Weaknesses 4-5 and Questions 5-6, which have nothing to do with our paper. Our paper works on graph spectral learning, rather than the above areas.
There are also paradoxical sentences and expressions. For example, Question 2 both acknowledges and denies our comparison with other SOTA baselines.
The remaining comments/questions are general for most graph mining papers. For example, scalability, and comparison with other baselines. We highly suspect that you submitted a wrong review of our paper. We sincerely hope that you could double-check our paper and your review. Nevertheless, the following are our responses to your comments and questions:

W1: The effectiveness of the suggested approach might not be universally applicable, as its performance is contingent on the specific characteristics of the dataset, making it less versatile.

RW1: In Table 1, we demonstrate that our method achieves state-of-the-art performance across 11 diverse datasets. These datasets span various domains (Citation, WebKB, Wikipedia, Social networks) and range from small to large scales. We believe this variety and the consistent performance across these datasets substantiate the effectiveness of our method beyond mere coincidence.

W2: The process of fine-tuning hyperparameters could be a resource-intensive and time-consuming endeavor, potentially impeding the scalability of the proposed approach.

RW2:

1. We detail the experimental settings and the process for hyperparameter tuning in Section 6.1 and Appendix D.4. Once the search space is determined, methods like grid search or hyperparameter optimization tools such as Optuna can be utilized to identify the optimal hyperparameters.
2. The time and space complexity of NewtonNet is analyzed in Appendix B.1, where we demonstrate the excellent scalability of our method. NewtonNet has a better scalability than GCN.

W3: The foundation of our approach hinges on the presumption that the graph Laplacian matrix adequately encapsulates the graph's inherent structure; however, this assumption may not hold true in all instances.

RW3: As we discuss in Section 2, the graph Laplacian matrix $\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1 / 2} \mathbf{A} \mathbf{D}^{-1 / 2}$ encapsulates all information from the adjacency matrix $\mathbf{A}$. This is the same across all graphs.

W4: Interpretability poses a concern, as the proposed approach lacks a straightforward means of explanation. This could curtail its utility in domains where interpretability is a paramount consideration.

RW4: The focus of our paper is not on interpretability, but rather on exploring the relationship between homophily/heterophily and graph spectral learning.

W5: The susceptibility of the proposed approach to data noise and outliers may undermine its performance when confronted with real-world datasets.

RW5: As mentioned in response to RW1, our experiments are conducted on 11 varied real-world datasets. Our research does not specifically address noisy data or outlier detection; instead, it concentrates on examining the relationship between homophily/heterophily and graph spectral learning.

W6: A significant limitation arises from the substantial volume of labeled data that the proposed approach necessitates to attain satisfactory performance, which can be impractical in situations where acquiring labeled data is a challenging and expensive endeavor.

RW6: Our proposed method does not require a substantial volume of labeled data. The experiments illustrated in Figure 3 reveal that NewtonNet demonstrates a higher percentage of improvements under conditions of limited labels compared to scenarios with higher training ratios. This indicates that NewtonNet performs effectively even with a limited number of labels available.

Q1: Could the proposed approach be adapted to accommodate directed graphs? While the paper focuses on undirected graphs, considering the prevalence of directed graphs in real-world applications, it would be intriguing to explore the adaptability of this approach to handle directed graphs.

RQ1: Currently, the Laplacian matrix definition in all spectral GNNs is based on undirected graphs, as this ensures the matrix is positive semidefinite with eigenvalues between [0, 2]. However, we acknowledge the prevalence of directed graphs in many real-world scenarios and are keen to investigate this problem in our future work.

Q2: How does the performance of the proposed approach compare to other state-of-the-art methods on the same datasets? The paper presents comparisons with baseline methods, but a comprehensive evaluation against other contemporary approaches on the same datasets would offer valuable insights into its relative effectiveness.

RQ2: In Table 1, we compare our NewtonNet with 10 other representative and state-of-the-art methods, encompassing both spatial (such as MLP, Mixhop, GCN, APPNP, GloGNN++) and spectral (like ChebNet, GPRGNN, ChebNetII, BernNet, JacobiConv) approaches. We believe this comprehensive comparison strongly validates the effectiveness of our method.

Q3: Could the authors offer additional insights into the hyperparameter tuning process? While the paper briefly mentions hyperparameter tuning, more extensive details on the selection process and an assessment of the sensitivity of results to hyperparameter choices would enhance clarity.

RQ3:

1. Yes, we determined the optimal hyperparameters through grid search, detailed in Section 6.1 and Appendix D.4. Hyperparameter optimization tools like Optuna can also be employed for this purpose.
2. Sensitivity analysis conducted in Appendix E.1 examines the impact of parameters $\gamma_1, \gamma_2, \gamma_3$, and $K$ on our model.

Q4: What is the scalability of the proposed approach to larger graphs? The current evaluation primarily focuses on relatively small graphs. Understanding its performance and computational complexity as graph size scales would be beneficial, particularly for applications involving larger graphs.

RQ4:

1. The time and space complexity of NewtonNet, analyzed in Appendix B.1, underscores our method's superior scalability, outperforming GCN in this regard.
2. Our experiments included several large-scale datasets. For instance, Penn94, Twitch-gamer, and Genius[1] have 41554, 421961, and 168114 nodes, respectively. Table 5 provides detailed statistics of these datasets.

Q5: Can the authors provide a deeper understanding of the interpretability challenges associated with the proposed approach? The paper notes potential interpretability issues, but additional insights into the specific challenges and potential pathways to improve interpretability would be valuable.

RQ5: Please refer to RW4.

Q6: How does the proposed approach handle noisy or incomplete data? The paper does not explicitly address the approach's handling of noisy or incomplete data, which can be a limitation in real-world scenarios. It would be advantageous to gain insights into potential adaptations of the proposed approach to accommodate such data scenarios.

RQ6: Please refer to RW5.

 
We hope these responses clarify your queries. Should you have any further questions, please do not hesitate to let us know.

Reference:
[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods

Thank you for your contributions and feedback. As the author-reviewer discussion period is ending soon, we'd appreciate it if you could re-evaluate our submission with the new experiments and clarifications in mind. If you have additional insights, we're open to continued discussion until the deadline.

Q1. Can the regularization be used for other polynomial filtering functions?

Q2. The authors explain in Appendix E.1 that the reason for their choice of K to be 5 (typically set as 10 or tuned in a range in other polynomial filters) is that when K is larger, the polynomial becomes susceptible to the Runge phenomenon according to He et al., (2022). Since the Runge phenomenon is caused by the selection of equal-paced interpolation points, why not use Chebyshev nodes for interpolation?

RQ1 & RQ2: Questions 1 and 2 raise similar issues, so I will address them together.

1. We would like to kindly remind the reviewer that we discussed this on page 7, under the section “Compared with other approximation and interpolation methods,” and in Appendix C. To make it more clear, shape-aware regularization is applicable exclusively to interpolation methods, as it necessitates direct control over the output values of interpolated points (specifically, $\mathbf{t}$ in Equation 7). Only interpolation methods directly reflect the output values of the polynomial. Methods like GPRGNN, ChebNet, and BernNet, which use approximation methods, are not compatible with shape-aware regularization.

2. While ChebNetII employs interpolation methods, its interpolated points are fixed, limiting our ability to tailor any interpolated points to fit various shapes of spectral filters. This limitation led us to propose Newton interpolation for learning the spectral filter, which is not only an interpolation method but also allows for the random selection of interpolated points.

3. NewtonNet can choose any points as interpolated points, including Chebyshev nodes. However, when conducting experiments, we found that Chebyshev nodes with regularization did not yield as satisfactory results as equispaced points. In fact, the performance was similar to ChebNetII. Consequently, we opted for equispaced points in our experiments.

4. Additionally, the concern of Runge's phenomenon primarily arises with high polynomial powers. According to Wikipedia[1], “Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree …” Our experiments demonstrate that NewtonNet with K=5 delivers good performance across various datasets. Opting for a lower polynomial degree not only mitigates the Runge phenomenon but also enhances the speed and efficiency of our method.

Please let us know if you have further questions!

Reference:

1. https://en.wikipedia.org/wiki/Runge%27s_phenomenon

Dear Reviewer zWto,

Thank you for your comments on improving our work. Here are our responses and answers.

W1. On the choice of K. First, In the second line under Eq.7, the authors write that they set K=4 in this paper. According to Fig.2 and the description of experimental settings in Appendix D.4, you want to write K=5, right? Then, in Appendix E.1, the authors conduct a sensitivity analysis on K, and find that NewtonNet's performances on the Cora and Chameleon datasets peak at K=5. Such an analysis is weird since the accuracies on test datasets are in fact used as prior knowledge. A valid way is to set K as a hyperparameter.

RW1:

1. Thanks for your careful reading. Yes, it’s a typo. We have revised the paper accordingly and submitted the new version.
2. We appreciate your question and realize our explanation might not have been as clear as intended:
   (1) We assure you that we did not use any prior knowledge from the test sets in our experiments. We strictly follow the common practice of training the model on the training set, selecting the best model (hyperparameters) based on the validation set, and then evaluating and reporting the results on the test set.
   (2) $K$ is indeed a hyperparameter. Regarding the hyperparameter $K$, to simplify our approach and reduce the search space, we initially did not tune $K$ and chose $K=5$ for the results presented in Table 1. However, to analyze the impact of $K$, we varied it over the set {2, 5, 8, 11, 14} as shown in Fig. 8. This investigation revealed that $K=5$ yields the best outcomes for the Cora and Chameleon datasets. However, it doesn’t mean that $K=5$ is the best choice for other datasets. Additionally, we conducted further experiments on amazon-ratings, which shows that $K=8$ provides better results. Generally, as $K$ increases from a small number the performance will first increase and then drop when $K$ is too large. A number of $K$ between 5 to 8 works well.

(3) To give more facts, if you refer to our code (Line 13 of https://anonymous.4open.science/r/NewtonNet-8115/config.py), it can be seen that $K$ is set as a hyperparameter.

W2. On the weak-supervised experiments. According to Ref.1, the Chameleon and Squirrel datasets are problematic in that they use duplicated nodes. This would be problematic, especially in weak-supervised settings. I am curious how this experiment would perform on other datasets.

RW2: We run experiments on your suggested datasets and show the results here. We will add this table and reference in the camera-ready version.

Thanks for your reply.

Q1: Thank you for your explanation. I'm still a bit puzzled because although ... I presume the process might not be overly time-consuming.

A1. We do define $K$ as a hyperparameter. The only thing is that we fixed $K=5$ to reduce the search space and simplify the settings. However, according to your suggestions, we re-ran the experiments with $K$ varying among [2, 5, 8, 11, 14] and found some improved results. Due to limited time, we only conducted experiments on Cora, Citeseer, Pubmed, Chameleon, Squirrel, and Crocodile. The results show that on Cora, Citeseer, and Chameleon, the best results are still achieved with $K=5$ and are the same as Table 1. However, on Pubmed, Squirrel, and Crocodile, better results were observed since we expanded the search space. These are summarized in the following table.

Due to time constraints, we conducted only a limited number of trials with Optuna. We believe to achieve better results with more trials. We intend to complete all the experiments and update the results in the next version of our work. Thank you for your valuable suggestions.

Q2: I mean, can your shape-aware regularization be used for approximation-based filters once you substitute $t_i$ with $f(q_i)$ ?

A2. I’m not sure if I understand your question correctly. I guess $f$ here is the function that we want to approximate, i.e. the spectral filter.
Since there are no interpolated points $q_i$ in approximation-based filters, we cannot apply shape-aware regularization by substituting $f(q_i)$ directly. But we can also define a series of points $q_i$ on approximation methods.
Then, let us clarify some concepts. In NewtonNet, $t_k$’s are function values, while $\hat{g}_{t}[q_0, \cdots, q_k]$ are coefficients.

Consider an approximation-based filter, for example, the one used in GPRGNN $f(q_i) = \sum_{k=0}^K w_k q_i^k$, where $w_k$’s are coefficients and $f(q_i)$’s are function values.

In interpolation methods, our parameters to be learned are the function values. These function values are then utilized to compute the coefficients. We directly regularize and learn these function values.

In contrast, approximation methods are designed to learn coefficients first. These coefficients are used to calculate function values. Then we regularize the function values. This process requires additional computational steps. Moreover, the regularization in this case is not applied directly to the parameters we aim to learn.

In conclusion, based on your description, while shape-aware regularization might be applicable to approximation methods, its application is relatively indirect and less efficient. We believe that exploring this further would be a suitable topic for future research.

Q3: More critical discussion on Runge's Phenomenon.

A3.

1. We didn’t mean $K=10$ is a large value that suffers from Runge's phenomenon. We mean that the reason why we chose $K=5$ is to mitigate Runge's phenomenon and make the method more efficient.
2. Figure 8 shows that $K=5$ is preferable by Cora and Chameleon. However, this doesn’t mean “ $K=5$ is preferable over higher orders ” on all datasets. The added experiments above indicate that Pubmed shows better results with $K=2$, while Crocodile performs better with $K=8$ compared to $K=5$.

  We hope this addresses your questions.

Dear Reviewer UTx2,

Thank you for your valuable comments on our work. Below are our responses.
 

W1: In practice, incorporating homophily information might offer the most significant benefits when the datasets are of limited size. For sufficiently large datasets, the graph filters will be fine-tuned automatically according to the graph homophily level.

RW1:

1. Our approach does not explicitly incorporate homophily information. We rely solely on the graph structure and predicted labels to estimate the homophily ratio.
2. Could you kindly point out that is there any reference for the claim “For sufficiently large datasets, the graph filters will be fine-tuned automatically according to the graph homophily level”? To our understanding, there is no clear evidence that graph filters adapt more effectively to larger graphs. Even if the graph is large, if there are not sufficient labels, we still do not know much about the homophily/heterophily information. In such scenarios, the graph filter's fine-tuning is hindered by insufficient information. Our experiments, illustrated in Figure 3, demonstrate that under conditions of scarce labels, NewtonNet shows a more significant improvement compared to situations with higher training ratios on both large and small datasets. For instance, in the Chameleon dataset, NewtonNet shows a notable improvement over BernNet by 28.2% when the training ratio is 0.1; however, this improvement is 3.2% when the training ratio is 0.6.
   However, if we do not provide guidance to the spectral filter, it will learn some undesired information on both small and large graphs. Actually, letting the graph filter be fine-tuned automatically on any graph is exactly what we aim to achieve by proposing shape-aware regularization. The experiments in Table 1 and Figure 3 validate that NewtonNet successfully learns beneficial frequencies autonomously on both small and large datasets, supporting our approach.

Q1: I recommend that the complexity analysis in Appendix B.1 be included in the main body of the paper.

RQ1: Thanks for your suggestion. In the new version submitted, we added a complexity analysis part in Section 4.

Q2: Are the high frequencies completely irrelevant for graphs with homophily and vice-versa? Currently, the paper discusses the relative importance of high and low frequencies for different homophily levels. However, it is not clear to me whether certain frequencies can be completely ignored in the extremities of graph homophily level.

RQ2:

1. We explore the relationship between the homophily ratio and frequency importance in Fig. 1(b). This figure demonstrates that even in extreme cases (homophily ratio = 0.0 or 1.0), the importance of low, middle, and high frequencies is not negligible. Therefore, we cannot conclusively state that “high frequencies are completely irrelevant for entirely homophilous graphs or the reverse.”

2. In fact, it's not necessary to correlate specific homophily ratios with particular frequencies. NewtonNet, enhanced by shape-aware regularization, is designed to automatically learn the significance of each frequency and adapt to the optimal spectral filter.

3. In completely homophilous graphs (homophily ratio = 1.0), the graph essentially reduces to several disconnected components/subgraphs, with each subgraph having nodes of the same label. In such scenarios, the node classification task becomes redundant as the class of each node can be easily determined.

Should you have any further questions or require additional information, please feel free to contact us. If we have addressed your concerns, we sincerely hope you can raise your score.