An Effective Universal Polynomial Basis for Spectral Graph Neural Networks

Dear Reviewer bWo5,

We sincerely thank you for your valuable feedback on our paper. We address your comments and questions below. In the revised draft, we have updated the paper according to the reviewer's points. We mark our revision in $\textcolor{blue}{blue}$.

W1: The design of heterophilic bases relies on the dataset's homophily rate ... but I think this process might affect the model's performance.

A1: Please kindly refer to our global response. As demonstrated, a high-quality estimation of the homophily ratio is accessible by the training set without compromising the performance of our model. As advised, we have added a discussion related to the homophily ratio and updated the experimental results in our revision.

Additionally, we have conducted an experiment to investigate the sensitivity of our proposed UniFilter to the estimated homophily ratio. Since UniFilter only utilizes the homophily basis on Cora ($\tau=1$ for Cora as shown in Table 5 in the Appendix in submission) and does not rely on the homophily ratio, we thus test UniFilter on Pubmed and Squirrel. To this end, we vary the estimated homophily ratio $\hat{h} \in \\{0.78, 0.79, 0.80, 0.81, 0.82\\}$ on Pubmed and $\hat{h} \in\\{0.19,0.20,0.21,0.22,0.23\\}$ on Squirrel based on the results in Table C (in global response). The achieved accuracy scores are presented in Table H.

Table H: Accuracy (%) for varying estimated homophily ratio $\hat{h}$ on Pubmed and Squirrel.

In Table H, UniFilter demonstrates consistent accuracy scores across different homophily ratios for both Pubmed and Squirrel. Notably, the accuracy variations remain minor, staying within a 1% range from the scores under the true homophily ratio, particularly on the Pubmed dataset.

Based on the experimental results, we observe that i) the homophily ratio can be effectively estimated using training data, and ii) our proposed UniFilter is robust towards the variance of estimated homophily ratios.

W2: There are not enough datasets for heterophilic graphs ... more extensive heterophilic graph datasets, such as the latest benchmarks available [1] and [2].

A2: As advised, we have tested our model on the new heterophily dataset amazon-ratings from [1]. Our UniFilter is tested on amazon-ratings by following the settings in [1] in a fixed dataset splits of 50%/25%/25% for training/validation/test for a quick comparison.

Specifically, UniFilter achieves an accuracy score of 53.28% $\pm$ 0.71% on amazon-ratings, slightly lower than the highest score 53.63% $\pm$ 0.39% achieved by GaphSage, as reported in [1]. However, UniFilter beats all heterophily-specific models tested in [1]. This observation confirms the effectiveness of our method as a spectral filter.

[1] Platonov, Oleg, et al. "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?." The Eleventh International Conference on Learning Representations. 2022.

[2] Lim, Derek, et al. "Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods." Advances in Neural Information Processing Systems 34 (2021): 20887-20902.

Minor Comments:

C1: The writing in this paper requires further refinement. For example, the notations used are somewhat confusing, such as using bold uppercase letters $\mathbf{G}$ for a graph and calligraphic fonts $\mathcal{L}$ for the Laplacian matrix.

A1: We thank the reviewer for the comments. As advised, we have replaced the calligraphic fonts $\mathcal{L}$ with bold uppercase letter $\mathbf{L}$ in our revision.

C2: No available code for reproducing the results has been provided.

A2: As advised, we have uploaded the code with instructions to reproduce our experimental results.

Thank you again for your valuable time and effort spent reviewing.

We thank the reviewer for the replies.

As suggested, we estimate the homophily ratio when only utilizing 2.5% of nodes for training. Table I below presents the estimated homophily ratio $\hat{h}$ for all the tested datasets.

Table I: Estimated homophily ratio $\hat{h}$ using 2.5% of nodes for training

The estimated homophily ratio $\hat{h}$ is close to the true $h$ across all datasets except for Citeseer. By further testing, we find that it requires 6% nodes as training for an accurate estimation of $0.732 \pm 0.12$ on Citeseer. In such a case for the sparse setting, we can take the homophily ratio as a hyperparameter and tune it within the vicinity of the estimated $\hat{h}$ until we achieve the best possible performance.

As required, we test our model UniFilter on one new heterophily dataset Texas from the suggested ChebNetII paper (due to time constraints, only one new dataset is considered). By following the full-supervised setting, our model UniFilter achieves an accuracy score of 93.44% $\pm$ 3.59% on Texas, higher than the best result of 93.28% $\pm$ 1.47% presented in Table 6 in ChebNetII paper. We believe this result provides further confirmation of the effectiveness of our proposed model.

We hope that these additional responses help clarify your concerns. Please do not hesitate to let us know if there are any additional questions and we also appreciate your suggestions to further improve this submission. Thank you.

Dear Reviewer SYRx,

We sincerely thank you for your positive and valuable feedback on our paper. We address your comments and questions below. In the revised draft, we have updated the paper according to the reviewer's points. We mark our revision in $\textcolor{blue}{blue}$

W1: The motivation for the choice of $\theta=\tfrac{\pi}{2}(1-h)$ from theorem 3, is not very straightforward and clear.

A1: We would like to clarify that this setting is derived based on the insights from both Theorem 1 and Theorem 3.

As we prove in Theorem 1, the frequency of desired signals is proportional to $1-h$. Therefore, the basis with its spectrum aligned with homophily ratios ($1-h$ in this case) enhances the capture of desired signals, leading to improved adaptability to the underlying graphs.

As we prove in Theorem 3, the expected signal frequency is monotonically increasing with $\theta$ for $\theta\in [0,\tfrac{\pi}{2})$. Combining with the conclusion in Theorem 1 and leveraging the monotonicity property, we thus empirically set $\theta=\tfrac{\pi}{2}(1-h)$. Consequently, setting $\theta=\tfrac{\pi}{2}(1-h)$ takes advantage of insights from both Theorem 1 and Theorem 3.

As advised, we have updated the explanation in the revised version. Specifically, we revised Theorem 3 slight by explicitly pointing out frequency $f(\phi)=0$ for all-ones vector $\phi$ which is therefore served as the pivot vector. Then we have revised the explanation as follows, marked in $\textcolor{blue}{blue}$ in the updated version.

"Theorem 3 reveals the correlation between the expected frequency of the signal basis and its relative position to the $0$-frequency vector $\phi$ on regular graphs. This fact implicitly suggests that we may take the angles (relative position) between two basis vectors into consideration when aiming to achieve the desired basis spectrum on general graphs. Meanwhile, Theorem 2 discloses the growing similarity and asymptotic convergence phenomenon within the homophily basis. To mitigate this over-smoothing issue, we can intuitively enforce all pairs of basis vectors to form an appropriate angle of $\theta \in [0,\tfrac{\pi}{2}]$. Pertaining to this, Theorem 1 proves the spectral frequency of ideal signals proportional to $1-h$, aligning with the homophily ratios of the underlying graphs. By leveraging the monotonicity property proved in Theorem 2, we empirically set the $\theta:=\frac{\pi}{2}(1-h)$."

W2: For this method, the knowledge of the homophily ratio seems to be important. In many practical scenarios, this may not be possible to be estimated accurately and even approximations could be difficult. No ablation study is presented showing the sensitivity of this model to the accurate knowledge of the homophily ratio.

A2: Please kindly refer to our global response to the homophily ratio issue. As demonstrated, this issue can be trivially resolved without compromising the performance of our model. As advised, we have added a discussion related to the homophily ratio and updated the experimental results in our revision.

As suggested, we added an ablation study on the sensitivity of our proposed UniFilter to the estimated homophily ratio. Since UniFilter only utilizes the homophily basis on Cora ($\tau=1$ for Cora as shown in Table 5 in the Appendix in submission) and does not rely on the homophily ratio, we thus test UniFilter on Pubmed and Squirrel. To this end, we vary the estimated homophily ratio $\hat{h} \in \\{0.78, 0.79, 0.80, 0.81, 0.82\\}$ on Pubmed and $\hat{h} \in\\{0.19,0.20,0.21,0.22,0.23\\}$ on Squirrel based on the results in Table C (in the global response). The achieved accuracy scores are presented in Table G.

Table G: Accuracy (%) for varying estimated homophily ratio $\hat{h}$ on Pubmed and Squirrel.

In Table G, UniFilter demonstrates consistent accuracy scores across different homophily ratios for both Pubmed and Squirrel. Notably, the accuracy variations remain minor, staying within a 1% range from the scores under the true homophily ratio, particularly on the Pubmed dataset.

Therefore, we observe that i) the homophily ratio can be effectively estimated using training sets, and ii) our proposed UniFilter is robust towards the variance of estimated homophily ratios.

As advised, this ablation study is added in the Appendix in our revised version.

W3: [Theoretical] Theorem 3 shows the relationship ... would be invalid for capturing signals with extreme eigenvalue.

A3: First, we would like to clarify that (i) the expectation considered in Theorem 3 aims to explore a general relationship between signal frequency and its position by abstracting away the randomness of graphs, providing guidance to the design of our polynomial basis, and (ii) signals with extreme eigenvalue, i.e., high frequency or low frequency can be captured by our constructed basis. Specifically, the variance of the spectral frequency distribution for a random signal is the result of the randomness of graph structures. It affects how easily a signal is captured but does not affect if the graph signal is captured.

Subsequently, we explain from both theoretical and practical perspectives. Theoretically, signals associated with eigenvalues are from a $n$-dimensional vector space where $n$ is the number of nodes in $G$. To capture any signals with any eigenvalues, our UniBasis can be constructed to contain $n$ basis vectors. Meanwhile, note that these basis vectors are linear independent since any two of them form the fixed $\theta$ angle in our design. In such a case, these $n$ linear-independent vector bases form a space basis, able to capture any signal vectors from that space with properly trained weights $w_k$, as well as the signals with extreme eigenvalue.

Practically, as proved in Theorem 1, the frequency of desired signals is proportional to $1-h$ where $h$ is the homophily ratio. The signals with extreme eigenvalues (signals in either high frequency or low frequency) would be captured or enhanced if they approach the desired signal of graphs. As shown in Figure 2 in our experiments, signals in both high frequency and low frequency are captured on corresponding datasets. Moreover, our UniFilter based on the UniBasis achieves SOTA performance on graphs with homophily ratios from $0.22$ to $0.81$.

Q1: Please refer to weaknesses. especially weaknesses 3.

A1: Please kindly refer to our response to weakness 3.

Q2: In Proof 3. authors claim that: "The negative value $\sum \tfrac{\lambda^{2k+1}_i(v^T_i x_i)^2}{c1c2}$ decreases and the positive value $\sum \tfrac{\lambda^{2k+1}_i(v^T_id_i)^2}{c1c2}$" increases as the exponent k increases". How is this result derived? value range of $\lambda$ is [−1,1], so the results should be the negative value decreases and the positive value decreases instead.

A2: We thank the reviewer for the careful checking. First, we would like to clarify that the value range of $\lambda$ is in ${\bf(-1,1]}$ ($\lambda=-1$ corresponds to bipartite graphs which are not considered in our paper) as stated in the proof, which is critical to deriving the result.

Second, notice that for normalized vectors $\tfrac{P^k x}{\|P^k x\|}$ and $\tfrac{P^{k+1} x}{\|P^{k+1} x\|}$, $\sum (\tfrac{\lambda^k_iv^T_ix}{c_1} )^2$ = $\sum (\tfrac{\lambda_i^{k+1} v^T_ix}{c_2} )^2$ =1 holds for all $k$ where $c_1=\|P^k x\|$ and $c_2=\|P^{k+1} x\|$. Since $v^T_i$ and $x$ remain unchanged, values $(v^T_i x)^2$ are constant for all eigenvectors $v_i$, $i\in \\{1,2,\cdots,n \\}$. In the equation $\tfrac{P^k x \cdot P^{k+1} x}{\|P^k x\| \|P^{k+1} x\|}=\sum^n_{i=1} \tfrac{\lambda^{2k+1}_i(v^T_i x)^2}{c_1c_2}$, the exponent $2k+1$ of $\lambda_i$ keeps being odd integer. Therefore, $\tfrac{\lambda^{2k+1}_i(v^T_i x)^2}{c_1c_2}$ with $\lambda_i \in (-1,0)$ contributes the the negative part. $\tfrac{\lambda^{2k+1}_i(v^T_i x)^2}{c_1c_2}$ with $\lambda_i \in (0,1]$ corresponds the positive part.

Notice that $c_1$ and $c_2$ are normalization factors, exerting equal scaling effects to both the negative part and the positive part. Their values also change accordingly along the increase of $k$ to ensure $\sum^n_{i=1} (\tfrac{\lambda^k_iv^\top_ix}{c_1} )^2 =\sum^n_{i=1} (\tfrac{\lambda^{k+1}_iv^\top_ix}{c_2} )^2=1$ for all $k$. As a consequence, we can infer that negative part $\tfrac{\lambda^{2k+1}_i(v^T_i x)^2}{c_1c_2}$ with $\lambda_i \in (-1,0)$ decreases while the positive part $\tfrac{\lambda^{2k+1}_i(v^T_i x)^2}{c_1c_2}$ with $\lambda_i \in (0,1]$ would increase along the increase of $k$.

As advised, we have enhanced the proof in our revision.

We sincerely thank you for your positive and valuable feedback on our paper. We address your comments and questions below. In the revised draft, we have updated the paper according to the reviewer's points. We mark our revision in $\textcolor{blue}{blue}$.

W1: [Related works] The paper loses investigations of the works also concentrating on heterophilous graphs [1-5].

A1: We appreciate the reviewer's suggestions. However, we would like to stress that the mentioned model in [4] i.e., the ACM-GNN, is one of our baselines compared in Table 3 in our submission. Furthermore, we indeed conceptually discussed ACM-GNN [4] and the model WRGAT [5] in related work in our original submission.

In this paper, we specifically focus on graph neural networks in the spectral perspective, therefore omitting the other three papers. By following your advice, we have added discussion on other missing papers in related works in our revised version. In Particular, HOG-GNN [1] designs a new propagation mechanism and considers the heterophily degrees between node pairs during neighbor aggregation, which is optimized from a spatial perspective. DualGR [2] focuses on the multi-view graph clustering problem and proposes dual label-guided graph refinement to handle heterophily graphs, which is a graph-level classification task. ASGC[3] simplifies the graph convolution operation by calculating a trainable Krylov matrix so as to adapt various heterophily graphs, which, however, is suboptimal as demonstrated in our experiments.

Furthermore, we have included the model ASGC [3] and WRGAT [5] to compare with our method UniFilter by following their settings. The results are presented in Table D and Table E respectively as advised.

Table D: Accuracy (%) compared with ASGC [3] in the 60%/20%/20% data splits (settings in [3])

Table E: Accuracy (%) compared with WRGAT [5] in the 48%/32%/20% data splits (settings in [5])

As shown, our UniFilter outperforms the two baseline models across all datasets, with notable advantages on some datasets. This observation further confirms the effectiveness of our proposed model.

As advised, we have included those experimental results in Table 2 and Table 3 in our revision.

[1] Wang, T, et al. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. AAAI (2022)

[2] Ling. Y, et al. Dual Label-Guided Graph Refinement for Multi-View Graph Clustering. AAAI (2023).

[3] Chanpuriya, S.; and Musco, C. 2022. Simplified graph convolution with heterophily. NeurIPS 2022.

[4] Revisiting heterophily for graph neural networks. NIPS, 2022, 35: 1362-1375.

[5] Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021: 1541-1551.

W2: [Completeness] This method will be effective under some assumptions, but the authors do not discuss the limitations.

A2: We thank the reviewer for the suggestion. Please kindly refer to our global response. As demonstrated in our global response, the assumption on heterophily ratios can be trivially avoided without compromising the performance of our proposed model. As advised, we have added a discussion related to the homophily ratio in our revision.

Dear reviewer vpd8,

We hope that you will find our responses satisfactory and that they help clarify your concerns. We appreciate the opportunity to engage with you. As today is the last day of our discussion, please don't hesitate to share with us if you have any remaining questions or concerns; we will be happy to respond. Thank you.

Dear Reviewer NCEm,

We sincerely thank you for your valuable feedback on our paper. We address your comments and questions below. In the revised draft, we have updated the paper according to the reviewer's points. We mark our revision in $\textcolor{blue}{blue}$.

W1: The flow (as sketched in summary) lacks soundness.

A1: We would like to clarify that this setting is derived based on the insights from Theorem 1, Theorem 2, and Theorem 3 combined together.

We explain in detail as follows. First, Theorem 3 proves that the expected signal frequency is monotonically increased with the angle $\theta$ formed by the random signal $x$ and the all-ones vector $\phi$. Notice that the frequency of $\phi$ is $0$, i.e., $f(\phi)=0$, which thus is served as the pivot vector. This fact suggests us that we could take the angles (relative position) between two basis vectors into consideration when aiming to calibrate the basis spectrum on general graphs. Also, Theorem 2, the basis vectors in homophily basis exhibit growing similarity and would asymptotically converge (illustrated in Figure 1(a)), which means the angle formed by two consecutive homophily basis vectors becomes smaller until zero, resulting in the over-smoothing phenomenon. To mitigate this issue, it is a natural solution to fix the angle $\theta \in [0,\tfrac{\pi}{2})]$ between all pairs of basis vectors. Meanwhile, Theorem 1 proves the spectral frequency of ideal signals proportional to $1-h$. Inspired from the monotonicity relation disclosed in Theorem 3 and all the analyses above, we thus set $\theta=\tfrac{\pi}{2}(1-h)$ empirically.

As advised, we have updated the explanation in the revised version. Specifically, we revised Theorem 3 slight by explicitly pointing out frequency $f(\phi)=0$ for all-ones vector $\phi$ which is therefore served as the pivot vector. Then we have revised the explanation as follows, marked in $\textcolor{blue}{blue}$ in the updated version.

"Theorem 3 reveals the correlation between the expected frequency of the signal basis and its relative position to the $0$-frequency vector $\phi$ on regular graphs. This fact implicitly suggests that we may take the angles (relative position) between two basis vectors into consideration when aiming to achieve the desired basis spectrum on general graphs. Meanwhile, Theorem 2 discloses the growing similarity and asymptotic convergence phenomenon within the homophily basis. To mitigate this over-smoothing issue, we can intuitively enforce all pairs of basis vectors to form an appropriate angle of $\theta \in [0,\tfrac{\pi}{2}]$. Pertaining to this, Theorem 1 proves the spectral frequency of ideal signals proportional to $1-h$, aligning with the homophily ratios of the underlying graphs. By leveraging the monotonicity property proved in Theorem 2, we empirically set the $\theta:=\frac{\pi}{2}(1-h)$."

W2: $h$ is used as a prior knowledge to adjust the angles among basis vectors. However, the direct calculation of $h$ relies on labels on test sets. This issue is important since it is related to label leakage.

A2: Please kindly refer to our global response. As demonstrated, this issue can be trivially resolved without compromising the performance of our model. As advised, we have added a discussion related to the homophily ratio and updated the experimental results in our revision.

W3: The claim "signals with negative weights are suppressed or eliminated as harmful information" lacks critical thinking. This assertion is related to the overall structure of the neural network, i.e., is there an neural layer after filtering?

A3: We thank the reviewer for pointing it out. We would like to clarify that by following the convention in polynomial graph filters, the signals after filtering are fed into MLP in our model for weight learning. Therefore, the absolute values of learned weights signify the importance of the corresponding signal basis. Signals with negative weights in large absolute values are enhanced in the reverse direction. As advised, we have revised this sentence in our updated version as "signals with weights in large absolute values are enhanced while signals with small weights are suppressed".

Thank you again for your valuable time and effort spent reviewing.

Dear reviewer NCEm,

We hope that our additional responses clarify your concerns. We appreciate the opportunity to engage with you. As today is the last day of our discussion, please don't hesitate to share with us if you have any remaining questions or concerns; we will be happy to respond. Thank you.

To verify the estimation difficulty, we vary the percentages of the training set in {10%, 20%, 30%, 40%, 50%, 60%} on Cora and Squirrel, and then average the estimated homophily ratios $\hat{h}$ over 10 random splits. The results are presented in Table C.

Table C: Homophily ratio estimation $\hat{h}$ over varying training percentages on Cora and Squirrel

As shown in Table A, the estimated values $\hat{h}_1$ and $\hat{h}_2$ derived from training datasets closely align with the actual homophily ratio $h$. There is a difference within a 2% range across all datasets, except for Citeseer. As shown in Table C, the estimated homophily ratio $\hat{h}$ is approaching the true homophily ratio $h$ across varying percentages of training data. This observation verifies that a high-quality estimation of the homophily ratio is accessible by the training set.

We would like to emphasize that the accuracy scores based on estimated homophily ratios in Table B closely match those from the original submission, with a negligible difference of less than 1%. As a consequence, our model UniFilter consistently outperforms all polynomial filters on the $6$ datasets except Actor and beats all model-optimized methods. This observation is consistent with the conclusion in the original submission. Therefore, the effectiveness of UniFilter is justified and the conclusions in the original paper still hold.

As advised, we have clarified this homophily ratio issue and updated the experimental results based on the estimated homophily ratios in Table 2 and Table 3 in our revised version, marked in $\textcolor{blue}{blue}$.