Unifying Homophily and Heterophily for Spectral Graph Neural Networks via Triple Filter Ensembles

We are grateful for your comments and suggestions, and we will explain and answer your concerns point by point!.

Weakness 1: The potential computational overhead introduced by the triple filter ensemble.

W-A1: Thanks for pointing out what we need to strengthen. The triple filter ensemble (TFE) is the core component of our proposed TFE-GNN, which combines filters to form a graph convolution. Similarly to ChebNetII [4] and PCNet [5], the time complexity of TFE-GNN is linear to $K_{lp}$+$K_{hp}$ when $EM_1$, $EM_2$, and $EM_3$ take summation. This shows that TFE does not influence the time complexity magnitude of the model.

Weakness 2: The descriptions of the theorems are too lengthy and not concise.

W-A2: Thanks for your valuable and helpful comment. We simplify condition (2) of Theorem 1 as "$EM_1$, $EM_2$, and $EM_3$ take summation, $H_{hp}$ take $L_{sym}$ and $H_{lp}$ take $L_{sym}^a$". We simplify condition (2) of Theorem 2 as "$EM_1$, $EM_2$ takes summation and $EM_3$ takes ensemble method capable of preserving the model's properties, $H_{hp}$ takes $\bar{H}^2_{gf}$ and $H_{lp}$ takes $\bar{H}^1_{gf}$".

Question 1: Can the ensemble methods be further optimized or replaced?

Q-A1: This is a insightful question that helps us analyze the TFE-GNN. There exist some other ensemble methods or alternative techniques to replace $EM_1$, $EM_2$, and $EM_3$, such as mean, maximization, pooling, etc., however, these methods do not perform as good as summation according to our experimental results.

Question 2: What is the computational overhead of the triple filter ensemble? How does the model scale with larger graphs and higher-dimensional feature spaces?

Q-A2: Thanks for your insightful questions. Similar to most spectral GNNs [4, 5], the triple filter ensemble mechanism does not influence the time complexity magnitude of the TFE-GNN, i.e., the time complexity of TFE-GNN is linear to $K_{lp}$+$K_{hp}$ when $EM_1$, $EM_2$, and $EM_3$ take summation. Specifically, the time complexity of message propagation is $O((K_{lp}+K_{hp})|E|C)$, the time complexity of the combination of $H_{gf}$ with respectively $\omega$ and $\omega'$ (Equations 9 and 10) is $O((K_{lp}+K_{hp})nC)$, and the time complexity of the coefficient calculation is not greater than $O(K_{lp}+K_{hp})$, where $C$ denote the number of classes and $n$ denotes the number of nodes. We report the training time overhead of the different spectral GNNs in Table 6 of Appendix B.5.

For graphs with higher dimensional features, we scale TFE-GNN by exchanging the order of message propagation and feature dimensionality reduction: $\widetilde{Z}=EM_3\lbrace\vartheta_1Z_{lp}, \vartheta_2Z_{hp}\rbrace = EM_3\lbrace \vartheta_1TFE_1f_{mlp}(X), \vartheta_2TFE_2f_{mlp}(X) \rbrace$. We use a sparse form of the adjacency matrix of large graphs, which greatly reduces the space required for TFE-GNN. Therefore, TFE-GNN scales well to large graphs and high-dimensional feature spaces.

We chose two large graphs [6] --fb100-Penn94 and genius-- to verify the scalability of TFE-GNN, and the experimental results are 84.76% and 89.32%, respectively. The performance of TFE-GNN on fb100-Penn94 exceeds that of all models mentioned in the article [6]. TFE-GNN tops the performance on genius dataset, which demonstrates its high competitiveness. All dataset statistics and experimental parameters are reported in Tables 1 and 2, respectively, of the author rebuttal’s one-page PDF. We will add a new section 3.5 to analyze and study the scalability of TFE-GNN in the final version.

Question 3: Why TFE-GNN has higher generalization.

Q-A3: Thanks for your valuable and meaningful questions. TFE-GNN is free from polynomial computation, coefficient constraints, and specific scenarios. These factors, especially the coefficient constraints, are responsible for model overfitting [7]. We illustrate the generalization ability of TFE-GNN with more intuitive experiments. In addition to the two large graphs --fb100-Penn94 and genius--, we add two additional datasets [9] --roman-empire and amazon-rating-- whose edge homophily are 0.05 and 0.38 respectively, to verify the generalization of TFE-GNN. Experimental results on the two datasets are 75.87%, and 52.21%, respectively. These additional experimental results further validate the generalization ability of TFE-GNN on both homophilic and heterophilic datasets: TFE-GNN can generalize well on graphs with different edge homophily levels. We will follow up with sufficient experiments and report the experimental results and parameters in the final version.

We sincerely appreciate your valuable comments and suggestions and we answer your concerns point to point!

Weakness 1: More theoretical and empirical results are expected to explain why TFE-GNN has better generalization.

W-A1: Thanks for your meaningful comments. We further explain why TFE-GNN has better generalization by introducing two new references [5, 6]. FFKSF [5] and ARMA [6] attribute the model overfitting to the overfitting of polynomial coefficients and the aggregation of high-order neighborhood information. TFE-GNN does not impose refined constraints on the coefficients and achieves better performance with a smaller order, whcih possesses higher generalization.

We select four new datasets [2, 3] and conduct relevant experiments to further explain why TFE-GNN has better generalization, including roman-empire, amazon-rating, and two large graphs [3] fb100-Penn94 and genius, whose edge homophily are 0.05, 0.38, 0.47, and 0.62, respectively. Experimental results show that TFE-GNN achieves competitive performance on these datasets with results of 75.87%, 52.21%, 84.76% and 89.32%, respectively. TFE-GNN achieves competitive rankings on all datasets, with the best performance on fb100-Penn94, outperforming most spectral GNNs on roman-empire, and topping the rest of the datasets. These additional experimental results further validate the generalization ability of TFE-GNN on both homophilic and heterophilic datasets: TFE-GNN can generalize well on graphs with different edge homophily levels. We will add the above relevant content to Section 4.3 and Appendix B.3 in the final version.

Weakness 2: The relevance of the abstract and introduction and the later sections can be enhanced.

W-A2: Thanks for pointing out our current shortcomings. To stress the expressiveness of TFE-GNN, we add the following sentences from line 83 of the paper: Theorem 2 show that TFE-GNN is a reasonable combination of two excellent polynomial-based spectral GNNs, which motivates it to perform well. TFE-GNN preserves the ability of the different filters while reducing overfitting problem.

Question 1: Could you provide some references for the second problem?

Q-A1: We appreciate your valuable question and find that the second problem, which builds on the first, is really not sufficiently described. We add the following sentences to clarify it from line 67 of the introduction: FFKSF [5] attributes the degradation of polynomial filters’ performance to the overfitting of polynomial coefficients. ChebNetII [4] further constrains the coefficients to enable them easier to be optimized. ARMA [6] suggests that the filter will overfit the training data when aggregating high-order neighbor information. Whereas the order of polynomial-based spectral GNNs is usually large to increase the approximation of the polynomials, which directs them to obtain high-order neighborhood information, and then leads to overfitting. Therefore, it is reasonable to assume that carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints lead to overfitting of the models, which diminishes generalization of the models. TFE-GNN discards these factors to improve generalization, while retaining the approximation ability.

Question 2: In Table 5 in Appendix A.2, is there a typo (93.13±0.62) in the last row of the second column?

Q-A2: Thanks for your responsible, careful and valuable comment! We are sorry for our carelessness. Actually, its correct value should be 83.13±0.62, we will revise it in the final version.

Question 3: Could you account for this oscillation in Figure 5 in Appendix B.3?

Q-A3: Thanks for your valuable comment. The learning rate controls the step size which in turn affects the loss optimization. The large learning rate (= 0.1) is responsible for the oscillations of the validation loss in Figure 5 in Appendix B.3. Figure 1 in the one-page PDF in the author rebuttal shows that the loss is stable when the learning rate is 0.001. The early stopping mechanism allows TFE-GNN to carry less stable losses and losses do not fall into unacceptable local maximum.

Suggestion 1: It would be interesting to explore the generalization ability between this class of two-fold filters versus general polynomial filters.

S-A1: Thanks for your valuable ideas. We will add the following to Section 5: We are eager to explore different types of combinations of low-pass and high-pass filters, as well as global combining methods such as pooling.

Suggestion 2: The statement of the second problem needs clarification or references.

S-A2: Thank you for your helpful suggestion. In addition to PCNet [1] pointing out that carefully crafted graph learning methods lead to low model generalization, we add two new references [5, 6] to state the second problem of this paper. FFKSF [5] and ARMA [6] attribute the overfitting to the overfitting of polynomial coefficients and the aggregation of high-order neighborhood information. We add the relevant analysis to the introduction starting at line 67 of the introduction

We appreciate the advice! We will gladly answer any additional questions you may have.

References

[1] Li, B et al. Pc-conv: Unifying homophily and heterophily with two-fold filtering. AAAI 2024.

[2] Oleg Platonov et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. ICLR 2022.

[3] Derek Lim et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. NeurIPS 2021.

[4] He, M et al. Convolutional neural networks on graphs with chebyshev approximation, revisited. NeurIPS 2022.

[5] Z. Zeng et al. Graph Neural Networks With High-Order Polynomial Spectral Filters. IEEE TNNLS, 2023.

[6] F. M. Bianchi et al.. Alippi, Graph Neural Networks With Convolutional ARMA Filters. IEEE TPAMI, 2022.

Thanks for the recognition and insightful comments. We will answer your concerns below.

more in-depth explanation on role of the key innovation – ensemble and the origin of the effectiveness.

We explain in depth "the ensemble and the origins of effectiveness" in terms of the problems solved by TFE-GNN. Then, we explain how TFE-GNN accomplishes our purpose and explain what the generalization and performance of TFE-GNN stems from. Finally, we elaborate on the key differences between TFE-GNN and filter combinations [4, 5], filter banks [6] and other similar methods [7. 8].

• We describe the core problem in this paper as follows: Carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints leaded to overfitting, which diminishes GNNs’ generalization. We are inspired by the properties of ensemble learning [1, 2, 3] and use ensemble ideas to solve this problem. First, the strong classifier determined by the base classifiers can be more accurate than any of them if the base classifiers are accurate and diverse. And then, this strong classifier retains the characteristics of the base classifier to some extent.

• Our TFE-GNN utilizes the above properties of ensemble to achieve the following effects: improves generalization and hence classification performance while retaining approximation ability. Specifically, we combine a set of weak base low-pass filter to determine a strong low-pass filter that can extract homophily from graphs. We combine a set of weak base high-pass filter to determine a strong high-pass filter that can extract heterophily from graphs. Learnable coefficients of low-pass/high-pass filters can enhance the adaptivity of TFE-GNNs. Finally, TFE-Conv is generated by combining the above two strong filters with two learnable coefficients, which retains the characteristics of both two strong filters, i.e., it can extract homophily and heterophily from graphs adaptively. Furthermore, Theorems 1 and 2 prove the approximation ability and expressive power of TFE-GNN, and experimental results verify that TFE-GNN achieves our purpose. Therefore, the high generalization and state-of-the-art classification performance of TFE-GNN stems from the aptness of the base classifiers and the advantages of the ensemble idea.

• The key difference between TFE-GNN and other GNNs with similar aggregation paradigms [4-8] is that TFE-GNN retains the ability of polynomial-based spectral GNNs while getting rid of polynomial computations, coefficient constraints, and specific scenarios. Specifically, Equation 13 and its predecessors in our paper show that TFE-GNN is free from polynomial computations, unlike ChebNetII and PCNet which require the computation of Chebyshev polynomials $T_k(x)$(Eq. 8 in [9]) and Possion-Charlier polynomials $C_n(k, t)$ (Eq. 15 in [4]), respectively. TFE-GNN does not impose refined constraints on the coefficients and does not design very complex learning methods, which helps it avoid overfitting as much as possible. TFE-GNN extracts homophily and heterophily from graphs with different levels of homophily adaptively while utilizing the initial features, which helps it not be limited to specific scenarios. In summary, TFE-GNN achieves a better trade-off in approximation ability and classification performance.

We will add relevant content to the Introduction and 3.1 Motivation of the final version and cite relevant references, including suggested relevant references. Thanks again for your valuable and insightful comments.

References

[1] Schapire, R. E. The strength of weak learnability. Machine learning, 5(2):197–227, 1990.

[2] Hansen, L. K. and Salamon, P. Neural network ensembles. IEEE transactions on pattern analysis and machine intelligence, 12(10):993–1001, 1990.

[3] Zhou, Z.-H. Ensemble methods: foundations and algorithms. 2012.

[4] Li, B et al. Pc-conv: Unifying homophily and heterophily with two-fold filtering. AAAI 2024.

[5] Du, Lun, et al. Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. Proceedings of the ACM Web Conference 2022. 2022.

[6] Sitao Luan, et al. Revisiting heterophily for graph neural networks. NeurIPS 2022.

[7] Keke Huang et al. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. ICML, 2024.

[8] Changqin Huang et al. Flow2GNN: Flexible two-way flow message passing for enhancing GNNs beyond homophily. IEEE TRANSACTIONS ON CYBERNETICS, 2024.

[9] He, M et al. Convolutional neural networks on graphs with chebyshev approximation, revisited. NeurIPS 2022.

We appreciate your valuable suggestions and we will explain them line by line.

Question 1: I recommend the authors to run additional experiments on two more up-to-date heterophilous datasets, such as those introduced in the papers [1, 2].

A1: Thank you for your valuable comment. We think that adding relevant experiments is necessary to make our paper more complete after discussing it. We validate our model with additional experiments on two large graphs [2] --fb100-Penn94 and genius-- whose edge homophily are 0.47 and 0.62, respectively. Experimental results on these two datasets were 84.76% and 89.32% for node classification. The performance of TFE-GNN on fb100-Penn94 dataset exceeds that of all models mentioned in the article [2]. TFE-GNN tops the performance on genius dataset, which demonstrates its high competitiveness. All dataset statistics and preliminary experimental parameters are reported in Tables 1 and 2, respectively, of the author rebuttal’s one-page PDF. Note that we use the same dataset splits as in the article [2].

We will add relevant experiments and their results analysis to the final version. We will modify our publicly available code accordingly and follow up with sufficient experiments and report the experimental results and parameters in the final version.

Question 2: It remains unclear to me in a high-level, what are the key differences between TFE-GNN compared to prior models which make TFE-GNN able to achieve a better trade-off here?

A2: Thanks for your constructive feedback. The key difference between TFE-GNN and prior models is that TFE-GNN retains the ability of polynomial-based spectral GNNs while getting rid of polynomial computations, coefficient constraints, and specific scenarios. The first problem we describe in line 52 of the introduction shows that it is not only the approximation ability of the polynomials affects the performance of GNNs, but also coefficient constraints and graph learning methods influence the performance. For example, ChebNetII [3], a prior model, constrains learnable coefficients by Chebyshev interpolation to boost ChebNet’s performance, which brings overfitting [6] for it. EvenNet [4] and PCNet [5] elaborate graph learning methods, namely even-polynomials and heterophilic graph heat kernel to ignore odd-hop neighbors, whcih makes them to accommodate the structure nature of heterophilic graph. This elaborate design is similar to the heterophily-specific models [7]. These models achieve great node classification performance for specific problems or scenarios through specific tricks.

In this paper, our proposed model is free from polynomial computations, coefficient constraints, and specific scenarios. Specifically, Equation 13 and its predecessors in our paper show that TFE-GNN is free from polynomial computations, unlike ChebNetII and PCNet which require the computation of Chebyshev polynomials $T_k(x)$(Eq. 8 in [3]) and Possion-Charlier polynomials $C_n(k, t)$ (Eq. 15 in [5]), respectively. TFE-GNN does not impose refined constraints on the coefficients and does not design very complex learning methods, which helps it avoid overfitting as much as possible. TFE-GNN extracts homophily and heterophily from graphs with different levels of homophily adaptively while utilizing the initial features, which helps it not be limited to specific scenarios. Furthermore, Theorems 1 and 2 prove the approximation ability and expressive power of TFE-GNN, and experimental results verify that TFE-GNN achieves our purpose. In summary, TFE-GNN achieves a better trade-off in approximation ability and classification performance.

We will add the following sentences from line 80 of the introduction: The key difference between TFE-GNN and prior models is that TFE-GNN retains the ability of polynomial-based spectral GNNs while getting rid of polynomial computations, coefficient constraints, and specific scenarios.

We appreciate the advice! We will gladly answer any additional questions you may have.

References

[1] Oleg Platonov et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. ICLR 2022.

[2] Derek Lim et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. NeurIPS 2021.

[3] He, M et al. Convolutional neural networks on graphs with chebyshev approximation, revisited. NeurIPS 2022.

[4] Lei, R et al. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. NeurIPS 2021.

[5] Li, B et al. Pc-conv: Unifying homophily and heterophily with two-fold filtering. AAAI 2024.

[6] Z. Zeng et al. Graph Neural Networks With High-Order Polynomial Spectral Filters. IEEE Transactions on Neural Networks and Learning Systems, 2023.

[7] Oleg Platonov et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2022.

I appreciate the authors detailed response to my comments. After reading authors' response, I decide to keep my original rating.

Thank you for the detailed rebuttal. I am satisfied with the responses provided. However, I recommend that the authors properly cite the suggested references on heterophilous graph learning in the final version. Based on this, I will raise my score to 6.