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

Authors: rui  duan
mingjian  guang
junli  wang
chungang  yan
hongda  qi
wenkang  su
haoran  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:01:14

Abstract: Polynomial-based learnable spectral graph neural networks (GNNs) utilize polynomial to approximate graph convolutions and have achieved impressive performance on graphs. Nevertheless, there are three progressive problems to be solved. Some models use polynomials with better approximation for approximating filters, yet perform worse on real-world graphs. Carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints leaded to overfitting, which diminishes the generalization of the models. How to design a model that retains the ability of polynomial-based spectral GNNs to approximate filters while it possesses higher generalization and performance? In this paper, we propose a spectral GNN with triple filter ensemble (TFE-GNN), which extracts homophily and heterophily from graphs with different levels of homophily adaptively while utilizing the initial features. Specifically, the first and second ensembles are combinations of a set of base low-pass and high-pass filters, respectively, after which the third ensemble combines them with two learnable coefficients and yield a graph convolution (TFE-Conv). Theoretical analysis shows that the approximation ability of TFE-GNN is consistent with that of ChebNet under certain conditions, namely it can learn arbitrary filters. TFE-GNN can be viewed as a reasonable combination of two unfolded and integrated excellent spectral GNNs, which motivates it to perform well. Experiments show that TFE-GNN achieves high generalization and new state-of-the-art performance on various real-world datasets.

Main paper: 
 introduction: 
 Graph neural networks (GNNs) are competitive in graph-related tasks (Scarselli et al., 2008; Yang et al., 2023; Shirzad et al., 2023; Duan et al., 2024) and can be divided into two main categories: spatial-based (Xu et al., 2019) and spectral-based (Shirzad et al., 2023; Tao et al., 2023; He et al., 2022; Bo et al., 2023b; Guo et al., 2023) GNNs. Spectral graph convolutions in the spectral domain of the graph Laplace matrix, i.e., the spectral graph filters, are the core component of spectral-based GNNs. We further classify spectral-based GNNs into two categories based on whether their graph convolutions can be learned or not.The first class of spectral-based GNNs' graph convolutions are predetermined, i.e., they filter the graph signals (features) in a fixed way. Graph convolutional networks (GCNs) (Kipf & Welling, 2016) and their variants (Rong et al., 2020; Chen et al., 2020; Yang et al., 2021) utilize only the first two Chebyshev polynomials to simplify ChebNet (Defferrard et al., 2016) , and their graph convolutions are the fixed low-pass filters.The second class of spectral-based GNNs' graph convolutions are learnable, i.e., their filters are variable and they filter the graph signals in learnable way. ChebNet (Defferrard et al., 2016) utilizes Chebyshev polynomials to approximate the graph convolutions and it can learn arbitrary filters in theory (Balcilar et al., 2021; He et al., 2022) . CayleyNet (Levie et al., 2018) utilizes Cayley polynomials to learn the graph convolutions, and ARMA (Bianchi et al., 2021a) learns the rational graph convolutions by using the Auto-Regressive Moving Average filters family (Narang et al., 2013) . GPR-GNN (Chien et al., 2021) and BernNet (He et al., 2021a) use Monomial and Bernstein polynomials to approximate the graph convolutions. ChebNetII (He et al., 2022) revisits ChebNet and makes learned coefficients more legal through Chebyshev interpolation. EvenNet (Lei et al., 2022) ignores odd-hop neighbors and improves the robustness of GNNs by using the even-polynomial graph filter. PCNet (Li et al., 2023) uses the Possion-Charlier polynomials to approximate the graph filter and constrain the coefficients. Just like EvenNet, the heterophilic graph heat kernel provided by PCNet pushes odd-hop neighbors away and aggregates even-hop neighbors. FavardGNN (Guo & Wei, 2023) learns a polynomial basis from the space of possible orthonormal bases and OptBasisGNN (Guo & Wei, 2023) computes the optimal basis for a given graph structure and signal. Specformer (Bo et al., 2023a) encodes the set of eigenvalues and performs self-attention in the spectral domain, which leads to a learnable set-to-set spectral filter.Despite polynomial-based learnable spectral GNNs have achieved impressive performance on graphs, there are three progressive problems to be solved. First, some polynomial-based models use polynomials with better approximation than some other models when approximating filters, but the former's performance is lagging behind that of the latter on real-world graphs. For example, GPR-GNN and BernNet outperform ChebNet, even though they use polynomials that are weaker than Chebyshev polynomials in approximation theory (He et al., 2022) . ChebNetII, an enhanced version of ChebNet, whose performance still lags behind that of PCNet using Possion-Charlier polynomials. The important factors influencing the real-world performance of such GNNs are graph learning methods, polynomial approximation and coefficient constraints, but of course there are others as well, in any case not only the polynomial approximation ability. The following two facts exist: ChebNetII outperforms GPR-GNN and BernNet through refined coefficient constraints; and PCNet outperforms ChebNetII through the carefully crafted graph learning method, i.e., pushing odd-hop neighbors away to match the structural properties of heterophilic graph.The second problem was raised based on the answer to the first problem. Carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints leaded to overfitting while improving models' performance, which diminishes the generalization of the models. FFKSF (Zeng et al., 2023) attributes the degradation of polynomial filters' performance to the overfitting of polynomial coefficients. ChebNetII (He et al., 2022) further constrains the coefficients to enable them easier to be optimized. ARMA (Bianchi et al., 2021b) 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. Desired learnable spectral GNNs can learn various graph convolutions, which motivates them to extract homophily from heterophilic graph and vice versa. Instead of ignoring odd-hop or even-hop neighbors, which makes the model miss important neighbor information.Finally, the third problem was raised. How to design a model that retains the ability of polynomialbased spectral GNNs to approximate filters while it possesses higher generalization and performance? In this paper, inspired by ensemble learning (Schapire, 1990; Hansen & Salamon, 1990; Zhou, 2012) (see in section 3.1), we design triple filter ensemble (TFE) mechanism to adaptively extract homophily and heterophily from graphs with different levels of homophily while utilizing the initial features, where the first and second ensembles combine a set of base low-pass and high-pass graph filter, respectively, and the third ensemble combines them by two learnable coefficients. The third ensemble of TFE will yield a graph convolution (TFE-Conv) used to filter the graph signal. The filtered signal is fed into a fully connected linear neural network (NN), whose output is then passed through a softmax layer to obtain the prediction. TFE-GNN does not impose refined constraints on the coefficients and does not design very complex learning methods, which possesses higher generalization. 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 describe the differences between TFE-GNN and several other recent methods (Li et al., 2024; Huang et al., 2024b,a) in Appendix B.7. TFE-GNN also offers the following three advantages. We theoretically demonstrate that the approximation ability of TFE-GNN agrees with that of ChebNet under certain conditions, as outlined in Theorem 1, i.e., can learn arbitrary filters. Theorem 2 shows that TFE-GNN is a reasonable combination of two excellent polynomial-based spectral GNNs, which motivates it to perform well. TFE extract the initial information, homophily and heterophily from graphs adaptively, which allows TFE-GNN to be applied to various homophily level cases. Experiments show that TFE-GNN achieves new state-of-the-art performance on datasets, and the homophily levels measured by the edge homophily ratio (Zhu et al., 2020) for these datasets is 0.06, 0.21, 0.23, 0.30, 0.57, 0.74, 0.80, 0.81, and 0.93.  
preliminaries: 
 Notations. Given a graph G = (E, V ) with node set V and edge set E ⊆ V × V . Let n = |V | denote the size of the node set, i.e., the number of nodes. This paper uses x ∈ R n to denote the graph signals, and x(i) to denote the signal at node i. Y ∈ {0, 1} n×C denotes label matrix of G, and Y i is the label vector of node i, where C is the number of classes. We denote X ∈ R n×d0 as the initial feature matrix of G, denote the adjacency matrix of G as A ∈ {0, 1} n×n , and denotes the degree matrix as D, where D ii = n j=0 A ij , and d 0 is the initial feature dimension. The (combinatorial) graph Laplacian is defined as L = D -A, and its eigendecomposition is L = U ΛU T . The columns u i of U ∈ R n×n are orthonormal eigenvectors, namely the graph Fourier basis, and Λ = diag([λ 1 , ..., λ n ]) is the diagonal matrix of eigenvalues. We also call these eigenvalues frequencies.The homophily metrics are used to define the homophily level of a graph by considering the different relationships between node labels/features and graph structures, including edge homophily (Zhu et al., 2020) , node homophily (Pei et al., 2020) , class homophily (Lim et al., 2021b) , etc. In this paper, we use the edge homophily ratio ehr to measure the ratio of intra-class edges contained in a graph as the homophily level:EQUATIONwhere u, v are nodes, Y u is the label vector of u, and Y v is the label vector of v. The value of ehr close to 1 corresponds to strong homophily, while the value of ehr close to 0 indicates strong heterophily.The graph filters are core components of spectral GNNs. We classify the graph filters into three categories based on the type of signal they filter: low-pass, high-pass and full-pass filters. The high-pass filter H hp are more suitable for extracting high-frequency signals (Bo et al., 2023a; Yang et al., 2022) . Empirically, the commonly used high-pass filters are the symmetric normalized Laplacian L sym = D -1/2 LD -1/2 = I -D -1/2 AD -1/2 and the random walk normalized Laplacian L rw = D -1 L = I -D -1 A.L a sym = I -L sym = D -1/2 AD -1/2 and L a rw = I -L rw = D -1 A.The full-pass filter H f p is the identity matrix I and retains all graph initial signals.Spectral-based GNNs create the spectral graph convolutions (filters) in the domain of Laplacian spectrum and many methods use the polynomial spectral filters to achieve graph convolutions, such as ChebNet Defferrard et al. (2016) , GPR- GNN Chien et al. (2021 ), BernNet He et al. (2021a) , ChebNetII He et al. (2022) , PCNet (Li et al., 2023) , FavardGNN (Guo & Wei, 2023) , etc. We begin by describing how the signal x is filtered by h:EQUATIONwhere y denotes the filtering results of x, and h denotes the spectral filter, which is a function on the eigenvalues of the graph Laplacian matrix L. Existing studies have replaced nonparametric filters with polynomial filters:EQUATIONwhere θ k ∈ R K is a vector of polynomial coefficients. We bring Equation 3 into Equation 2:EQUATIONWe describe polynomial-based spectral GNNs in terms of ChebNet (Defferrard et al., 2016) and its enhanced version ChebNetII (He et al., 2022) , including how they approximate graph convolution with polynomials and how constraining the coefficients. Other related methods are similar, such as EvenNet (Lei et al., 2022) and PCNet (Li et al., 2023) . ChebNet uses Chebyshev polynomial to approximate the filtering operation, which is a remarkable attempt:EQUATIONwhere L = 2L sym /λ max -I denotes the scaled graph Laplacian matrix, λ max is the largest eigenvalue of L and θ is a vector of Chebyshev coefficients. Chebyshev polynomial T k (x) of order k can be recursively defined asT k (x) = 2xT k-1 (x) -T k-2 (x) with T 0 (x) = 1 and T 1 (x) = x.ChebNet's structure is:EQUATIONwhere W k are the trainable weights, which contain the Chebyshev coefficients θ k . ChebNetII (He et al., 2022) proposes ChebBase to determine who is more competitive, Chebyshev basis or other bases.EQUATIONwhere f (X) is a Multi-Layer Perceptron (MLP). ChebNetII believes that ChebNet learns the illegal coefficient by analyzing a series of polynomial filters. Therefore, it then proposes ChebBase/k, which is an improvement on ChebNet and constrains the coefficients with θ k /k (Equation 7). Finally, ChebNetII is proposed.EQUATIONwhere γ j is the learnable coefficient, and it links Equation 7 and Equation 8 with θ k = 2 K+1 K j=0 γ j T k (x j ), i.e., the learnable coefficients constrain.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: we discuss the limitations of TFE-GNN in Appendix A.2.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
methodology: 
 We propose a spectral GNN with triple filter ensemble (TFE-GNN) to solve three progressive problems in polynomial-based learnable spectral GNNs. In this section, we describe the methodology of TFE-GNN in detail and theoretically prove its approximation capabilities, including motivations, TFE-Conv, TFE-GNN, time complexity and scalability and theoretical analysis.Polynomial-based learnable spectral GNNs (He et al., 2022; Li et al., 2023; Guo & Wei, 2023) performs well on homophilic and heterophilic graphs, because their graph convolutions are flexible and variable. However, carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints leaded to overfitting, which diminishes GNNs' generalization.Inspired by the following properties of ensemble learning (Schapire, 1990; Hansen & Salamon, 1990; Zhou, 2012) : 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 this strong classifier retains the characteristics of the base classifier to some extent. First, we combine a set of weak base low-pass filter to determine a strong low-pass filter that can extract homophily. Then, we use the same method to extract heterophily. 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. TFE-Conv and TFE-GNN are shown in Figure 1 .We design triple filter ensemble (TFE) mechanism for combining low-pass and high-pass filters to yield a graph convolution (TFE-Conv), which can match various graph structures adaptively without carefully crafted graph learning methods, i.e., can extract homophily and heterophily adaptively from graphs with different homophily level. The first ensemble of TFE is formalized as follows:EQUATIONwhere T F E 1 denotes the result of combining a set of base low-pass filters, which is a graph convolution that can extract homophily while utilizing the initial signals, EM 1 denotes the ensemble method of the first ensemble,EM 1 {h 0 , h 1 , • • • , h K } denotes the combination of elements h 0 , h 1 , • • • , h K with EM 1, ω are the learnable coefficients, and K lp is the order of the first ensemble. The second ensemble is similar to the first ensemble and is formalized as follows:TEQUATIONwhere T F E 2 denotes the result of the second ensemble, which can extract heterophily while utilizing the initial signals, EM 2 denotes the ensemble method of the second ensemble, ω ′ are the learnable coefficients, and K lp is the order of the second ensemble. The third ensemble combines T F E 1 and T F E 2 with two learnable coefficients ϑ 1 and ϑ 2 :EQUATIONwhere T F E 3 denotes the result of the third ensemble, i.e., TFE-Conv, and EM 3 denotes the ensemble method of the third ensemble. The learnable coefficients ϑ 1 and ϑ 2 used to combine the two strong graph convolutions T F E 1 and T F E 2 guarantee T F E 3 's adaptivity.TFE-Conv matches various graph structures adaptively, which facilitates the filtering of the graph signals (features) X. The filtered signal is fed into an MLP, whose output is then passed through a softmax layer for obtaining the prediction. This is the forward propagation of TFE-GNN and is coupled with the cross-entropy loss and the backpropagation mechanism to form the complete TFE-GNN. The formalization of X being filtered by TFE-Conv is:Z = T F E 3 • X = EM 3 {ϑ 1 T F E 1 , ϑ 2 T F E 2 } • X = EM 3 {ϑ 1 T F E 1 • X, ϑ 2 T F E 2 • X}, (12)where T F E 1 and T F E 2 are the graph convolutions obtained from the first and second ensembles, respectively, which are similar to T F E 3 in that they filter the graphical signal as follows: Z lp = T F E 1 • X and Z hp = T F E 2 • X. Thus, Equation 12 can be rewritten in the following form:EQUATION)We decouple transformation/prediction and feature propagation (Rong et al., 2020; He et al., 2022) for TFE-GNN and formalize TFE-GNN used for node classification:EQUATIONwhere L denotes the cross-entropy loss, Y L denotes the training set with labels, and ⊤ denotes the vector transpose.Similar to some spectral GNNs (He et al., 2022; Li et al., 2023) , 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 ω and ω ′ (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 ). We report the training time overhead of the different spectral GNNs in Appendix B.6.We scale TFE-GNN by exchanging the order of message propagation and feature dimensionality reduction:Z = EM 3 {ϑ 1 Z lp , ϑ 2 Z hp } = EM 3 {ϑ 1 T F E 1 f mlp (X), ϑ 2 T F E 2 f mlp (X)}.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.ChebNet has been shown to learn arbitrary filters in theory (Balcilar et al., 2021; He et al., 2022) . We find a connection between TFE-GNN and ChebNet and then analyze the conditions under which they transform into each other. We prove that TFE-GNN is equal to ChebNet under certain conditions, i.e., they have the same approximation ability, so TFE-GNN can also learn arbitrary filters.Theorem 1. TFE-GNN and ChebNet can be transformed into each other under the following conditions, (1) learning the proper coefficients ω, ω ′ , ϑ and ChebNet' coefficient θ, (2) the ensemble methods EM 1 , EM 2 and EM 3 take summation, the base high-pass filter H hp takes the symmetric normalized Laplacian L sym and the base low-pass filter H lp takes the affinity (transition) matrix of L sym , and (3) K hp = K lp = K -1. Thus, TFE-GNN can also learn arbitrary filters.Theorem 1 (proof in Appendix A.1) shows that TFE-GNN matches various graph structures adaptively while learning arbitrary filters under certain conditions. The proof of Theorem 1 shows that ChebNet can be unfolded into a combination of high-pass or low-pass filters, or a combination of high-pass and low-pass. TFE-GNN, on the other hand, is a combination of two different unfoldings of ChebNet.Condition (1) of Theorem 1 is shown in its proof, the EM 1 and EM 2 in condition ( 2) are taken to summation to correspond to the expansion of the Chebyshev polynomials, while EM 3 is an ensemble method capable of preserving the properties of the model, such as summation and concatenation, and condition (3) motivates the agreement between the orders of TFE-GNN and ChebNet.Polynomial-based spectral graph GNNs can all be unfolded into combinations of filters, which is similar to the idea of filter ensemble in TFE-GNN. TFE-GNN is a combination of two polynomialbased GNNs under certain conditions by displacing its base filters and setting K lp and K hp .Theorem 2. TFE-GNN can be rewritten in the following form, with certain conditions to be satisfied, which is a combination of two polynomial-based learnable spectral GNNs:Z * = sof tmax(f mlp (ϑ 1 K ′ k=0 θ1 k P 1 k ( H1 gf ) k X ϑ 2 K ′′ k=0 θ2 k P 2 k ( H2 gf ) k X)), where P k denote polynomials used for approximation, θ are the learnable coefficients, Hgf denote graph filters, and denotes EM 3 . Conditions are (1) learning the proper coefficients ω, ω ′ , ϑ, θ1 , and θ2 , (2) the ensemble methods EM 1 , EM 2 take summation and EM 3 takes ensemble method capable of preserving the properties of the model, such as summation and concatenation, the base high-pass filter H hp takes H2gf and the base low-pass filter H lp takes H1 gf , and (3) K lp = K ′ and K hp = K ′′ . Thus, TFE-GNN can match various graph structures adaptively.The proof of Theorem 2 is reported in Appendix A.1. Theorems 1 and 2 show that polynomial-based learnable spectral GNNs are able to learn different filters, and thus perform well on both homophilic and heterophilic graphs. In contrast, fixed-filter GNNs can only filter graph signals based on their filter forms. TFE-GNN combines different filters directly, preserving the ability of the different filters while reducing overfitting problem. Theorem 2 also shows that TFE-GNN will perform well on real-world datasets: it is a reasonable combination of two excellent polynomial-based spectral GNNs. We discuss the limitations of TFE-GNN in Appendix A.2.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [Yes] Justification: we provide detailed code in the supplemental material, which can be run directly after installing the required packages.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In this section, we conduct experiments to evaluate the proposed TFE-GNN against the state-of-theart (SOTA) GNNs on real-world datasets and conduct ablation study, generalization, visualization (Appendix B.3), hyper-parameters (Appendix B.5), and time efficiency (Appendix B.6) analysis to verify TFE-GNN's excellent.Datasets and experimental setup. We evaluate TFE-GNN on several real-world datasets for supervised node classification and chose 11 graphs with various levels of homophily, including 4 citation graphs (Kipf & Welling, 2016) Cora, Citeseer, Pubmed, and Cora-Full (Bojchevski & Günnemann, 2017) , 2 Co-authorship graphs (Shchur et al., 2018) Coauthor CS and Coauthor Physics, 2 Wikipedia graphs (Rozemberczki et al., 2021) Chameleon and Squirrel, and 3 WebKB graphs (Pei et al., 2020) Texas, Cornell, and Wisconsin. The dataset statistics are summarized in Table 1 . In addition, we choose four additional datasets, i.e. roman-empire (Platonov et al., 2023) , amazon-rating (Platonov et al., 2023) , fb100-Penn94 (Lim et al., 2021a) and genius (Lim et al., 2021a) , to further validate the classification performance, generalization and scalability of TFEGNN. Detailed dataset statistics and experimental results are reported in the Appendix B.1. All experiments are carried out on the machine with Linux system, two NVIDIA Tesla V100 and twelve Intel(R) Xeon(R) Gold 5220 CPU @2.20GHz. There are many options available for H lp , H hp , EM 1 , EM 2 , and EM 3 in TFE-GNN, and we choose common and frequently used options for them to make a broad and fair comparison between TFE-GNN and other SOTA GNNs. H hp and H lp take the symmetric normalized Laplacian L sym and L a sym respectively. We add self-loops to the graph in practice, soL sym = I -D-1/2 Ã D-1/2 and L a sym = D-1/2 Ã D-1/2, where Ã = A + I, and Dii = n j=0 Ãij . We use generalized normalization about L sym to alleviate the overcorrelation issue in spectral GNNs (Yang et al., 2022; Li et al., 2023) and keep L a sym unchanged, namely L sym = I -D-η Ã D-η . EM 1 and EM 2 take summation, and EM 3 takes summation or concatenation. Thus, TFE-Conv filters the graph signal X in the following way:EQUATIONwhere ∥ denotes concatenation and has lower arithmetic priority than addition, subtraction, multiplication and division.Setting and baselines. We compare TFE-GNN to a series of SOTA models for full-supervised node classification on datasets with random splits, including 11 polynomial approximation filter methods GCNs (Kipf & Welling, 2016) , ARMA (Bianchi et al., 2021a) , APPNP (Klicpera et al., 2018) , ChebNet (Defferrard et al., 2016) , GPR-GNN (Chien et al., 2021) , BernNet (He et al., 2021a) , ChebNetII (He et al., 2022) , SPECFORMER (Bo et al., 2023a) , EvenNet (Lei et al., 2022) , FavardGNN/OptBasisGNN (Guo & Wei, 2023) , and PCNet (Li et al., 2023) . We also add 5 competitive SOTA models Half-Hop (Azabou et al., 2023) , GCNII (Chen et al., 2020) , TWIRLS (Yang et al., 2021) , PDE-GCN (Eliasof et al., 2021) , and EGNN (Zhou et al., 2021) . We randomly split each class of nodes into 60%, 20%, and 20% as training, validation, and testing sets for full-supervised node classification and all models share the same ten random splits for a fair comparison.For TFE-GNN, we set the hidden units to be 64 or 512 (Squirrel, Chaneleon, roman-empire, and amazon-rating), the number of early stoppings is 200 and the number of epochs is 1000 for all datasets. We employ the ReLu as an activation function for f mlp . We use the officially released code for GCNII, GPR-GNN, BernNet, etc and use the Deep Graph Library implementations for other models, such as GCNs, APPNP, ChebNet, etc. More experimental details of hyper-parameters and code URLs are listed in Appendix C.Results. Tables 2 and 3 report the results of the different models on all datasets and gives mean classification accuracy and standard deviation over ten random splits, where the bolded numbers indicate the best results, "Favard" denotes FavardGNN/OptBasisGNN, TFE-GNN sum denote that EM 3 of TFE-GNN is summation, and TFE-GNN con denote that EM 3 of TFE-GNN is concatenation.The experimental results are taken from ChebNetII, Half-Hop, SPECFORMER, EvenNet, and avardGNN/OptBasisGNN, when they report relevant results, and the remaining results are reproduced by us. Tables 2 and 3 illustrate that ChebNet starts to outperform GCNs when there is more training data available, which suggests the validity of the Chebyshev approximation. TFE-GNN achieves new state-of-the-art results on all datasets. TFE-GNN outperforms some SOTA models with similar results on Cora and Citeseer, including GPR-GNN (Chien et al., 2021) , BernNet (He et al., 2021a) , ChebNetII (He et al., 2022) and Half-Hop (Azabou et al., 2023) . Notably, TFE-GNN outperforms ChebNetII on Chameleon and Squirrel by 5.79% and 14.85%, respectively, which amounts to performance improvements of 8% and 26%. TFE-GNN achieves exciting results on Physics (strong homophily) and Wisconsin (strong heterophily) for full-supervised node classification, already close to 100% accuracy. We put the relevant settings and results of TFE-GNN for semi-supervised node classification in Appendix B.2, due to space limitations.We conduct experiments to investigate the (joint) contributions of TFE-GNN's components. The last three rows of Tables 2 and 3 report the results of the ablation experiments. The symbol "TFE-GNN\T F E 1 " means ϑ 1 = 0 or K lp = 0, "TFE-GNN\T F E 2 " means ϑ 2 = 0 or K hp = 0, and "TFE-GNN rw+sum " indicates that TFE-GNN sum uses the random walk normalized LaplacianL rw = D -1 L = I -D -1A as the high-pass graph filter H hp . Partial ablation experiments yielded the same results due to the choice of hyperparameters K lp and K hp . We observe that TFE-GNN\T F E 1 performs worse under strong homophily, while TFE-GNN\T F E 2 performs worse under strong heterophily. TFE-GNN with all graph filters achieves the best results, which suggests that it can match various graph structure.We verify the generalization of TFE-GNN by analyzing its cross-entropy loss in the training and validation sets on Cora, and a smaller gap between the two losses indicates a better generalization of the model (Feng et al., 2020) . Figure 2 shows the significant gap between the training and validation losses for ChebNet, ChebNetII, and PCNet, which indicates a possible overfitting and diminishes their generalization. The validation loss of TFE-GNN is much closer to its training loss and the early stopping mechanism allows the model to carry less stable losses. More generalization analyses are reported in Appendix B.4. We try to explain the reason for the oscillation in TFE-GNN's losses in Figure 2 . 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 2 . Figure 3 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 minimum.  
conclusions: 
 We propose TFE-GNN with triple filter ensembles (TFE) to solve three progressive problems. TFE-GNN extracts homophily and heterophily from graphs with different homophily levels adaptively while utilizing the initial features, which motivates it to match various graph structure. We theoretically prove that TFE-GNN can learn arbitrary filters and is a combination of two polynomial-based spectral GNNs. Experiments show that TFE-GNN achieves new state-of-the-art performance on various real-world datasets. In the future, we will dig deeper into ensemble methods of triple filter ensembles and expect to further improve the performance of TFE-GNN. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: all details are in section 4 and Appendix C.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: all information is in section 4 and Appendix C.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: all information is in section 4.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: full paper.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: our articles are fundamental research.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: we cite the papers covered in the public datasets in the experimental section 4.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Proofs of Theorems 1 and 2 Theorem 1. TFE-GNN and ChebNet can be transformed into each other under the following conditions, (1) learning the proper coefficients ω, ω ′ , ϑ and ChebNet' coefficient θ, (2) the ensemble methods EM 1 , EM 2 and EM 3 take summation, the base high-pass filter H hp takes the symmetric normalized Laplacian L sym and the base low-pass filter H lp takes the affinity (transition) matrix of L sym , and (3) K hp = K lp = K -1. Thus, TFE-GNN can also learn arbitrary filters.proof: We first prove that ChebNet can be transformed into TFE-GNN under conditions (1), (2), and (3). Instead of ChebNet, we use its excellent version Chebyshev basis (Equation 7). We change Equation 7 to the following form that does not affect approximation ability:EQUATION)Equation 16 can be rewritten in the form of equal approximation ability using the learnable parameters (constants) ϑ 1 and ϑ 2 :Ŷ = sof tmax(f mlp (ϑ 1 K k=0 θ k T k ( L)X + ϑ 2 K k=0 θ k T k ( L)X)) = sof tmax(f mlp (ϑ 1 Ỹ + ϑ 2 Ỹ )).(17) We parse and reconstruct the key parts of Equation 17 by unfolding and integrating technologies, i.e., analyzing K k=0 θ k T k ( L)X = Ỹ . We get the follow equation by unfolding the summation and Chebyshev polynomialEQUATIONwhere T 0 ( L) = I, T 1 ( L) = L, T 2 ( L) = 2 L2 -I, and so on. Equation 18 can be viewed as a (K -1)-th order polynomial of Ỹ with respect to L. We then integrate the coefficients of different orders L in Equation 18:EQUATIONwhere the first coefficient of the polynomial 19, the coefficient of the highest order θ ′ K-1 = θ K-1 2 K-2 , and so on. We can calculate the relationship between coefficients θ ′ k and θ k (0 < k < K -1) based on the generalized form of the Chebyshev polynomials.θ ′ 0 = (θ 0 -θ 2 + θ 4 -θ 6 + • • • ) in EquationEQUATIONwhere ⌊n/2⌋ denotes downward rounding, and n 2j denotes combinatorial numbers. We get the connection between Ŷ1 and Z hp according to the given conditions (1), (2), and (3):EQUATIONwhere the conversion of the coefficients θ ′ to ω ′ are realized through equation L = 2L sym /λ max -I.We continue to unfold Equation 19:EQUATIONwhereθ ′′ 0 = θ ′ 0 + 2-λmax λmax θ ′ 1 • • • + ( 2-λmax λmax ) K-1 θ ′ K-1 , and θ ′′ K-1 = ( 2 λmax ) K-1 θ ′ K-1 .We get the connection between Ỹ and Z lp according to the given conditions (1), (2), and (3):EQUATIONwhere ω = θ ′′ . We get a new conclusion about Ŷ :EQUATION)ChebNet and its excellent version Chebyshev basis are essentially the same (Defferrard et al., 2016) , except that Chebyshev basis implements the decoupling (He et al., 2022) . Therefore, we proved that ChebNet can be transformed into TFE-GNN under conditions (1), (2), and (3), and vice versa.Theorem 2. TFE-GNN can be rewritten in the following form, with certain conditions to be satisfied, which is a combination of two polynomial-based learnable spectral GNNs:Z * = sof tmax(f mlp (ϑ 1 K ′ k=0 θ1 k P 1 k ( H1 gf ) k X ϑ 2 K ′′ k=0 θ2 k P 2 k ( H2 gf ) k X)), where P k denote polynomials used for approximation, θ are the learnable coefficients, Hgf denote graph filters, and denotes EM 3 . Conditions are (1) learning the proper coefficients ω, ω ′ , ϑ, θ1 , and θ2 , (2) the ensemble methods EM 1 , EM 2 take summation and EM 3 takes ensemble method capable of preserving the properties of the model, such as summation and concatenation, the base high-pass filter H hp takes H2gf and the base low-pass filter H lp takes H1 gf , and (3) K lp = K ′ and K hp = K ′′ . Thus, TFE-GNN can match various graph structures adaptively.proof : The proof of Theorem 2 is similar to that of Theorem 1. First, we unfold the polynomials P 1 k and P 2 k in Z * to get a combination of K ′ -th order polynomial with respect to H1 gf and K ′′ -th order polynomial with respect to H2 gf , which is similar to Equation 18. P k can be the Chebyshev, Bernstein, even, Possion-Charlier polynomials in ChebNet (Defferrard et al., 2016) , BernNet (He et al., 2021a) , EvenNet (Lei et al., 2022) , PCNet (Li et al., 2023) , and so on. We then sum their coefficients using ( H1gf ) k (k ∈ [0, K ′ ]) and ( H2 gf ) k (k ∈ [0, K ′′ ])as variables respectively, which is similar to Equations 19 and 22. Finally, we replace θ1 and θ2 with ω and ω ′ , which is similar to Equations 21 and 23. Therefore, TFE-GNN is a combination of two polynomial-based learnable spectral GNNs. Theorems 1 and 2 state that TFE-GNN can learn any filter and matches various graph structure and extracts homophily and heterophily from graphs adaptively. We design triple filter ensembles to generate a TFE-Conv, which can match various graph structures and extract the initial information, homophily and heterophily adaptively. The learnable coefficients ϑ 1 and ϑ 2 and customized hyperparameters K lp and K hp enhance the performance of TFE-GNN while creating some limitations. In particular, K lp and K hp rely on one's experience, and it is solved by selecting the appropriate K lp and K hp according to the homophily level of datasets. For example, we choose a larger K lp for datasets with strong homophily while choosing a larger K hp for datasets with strong heterophily. However, the real-world dataset cannot determine its homophily level due to the presence of unlabeled nodes. We are able to determine its approximate homophily level based on training set labels or dataset knowledge, which may be in error.It is conceivable that there are other limitations of the TFE-GNN, such as the choice of the base filter, which affect the performance of the model. In fact, none of K lp , K hp , H lp and H hp is fatally weakening the performance of TFE-GNN, as long as we make a suitable choice based on the general phenomenon of polynomial-based spectral GNNs. For example, H hp taking the symmetric normalized Laplacian L sym or the random walk normalized Laplacian L rw , H hp taking their affinity (transition) matrix L a sym or L a rw , K lp and K hp the interval [1, 10] . Datasets and Setting. We illustrate the generalization and scalability of TFE-GNN with more intuitive experiments. We select four new datasets (Platonov et al., 2023; Lim et al., 2021a) and conduct relevant experiments to further explain why TFE-GNN has better generalization, including roman-empire, amazon-rating, and two large graphs (Lim et al., 2021a) 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. Dataset statistics are reported in Table 6 and the hyperparameters are reported in Table 7 . Note that we use the same dataset splits as in the article (Platonov et al., 2023; Lim et al., 2021a) .Setting and baselines. We compare TFE-GNN to a series of SOTA models for semi-supervised node classification on real-world datasets, including GCNs (Kipf & Welling, 2016) , ARMA (Bianchi et al., 2021a) , APPNP (Klicpera et al., 2018) , ChebNet (Defferrard et al., 2016) , GPR-GNN (Chien et al., 2021) , BernNet (He et al., 2021a) , ChebNetII (He et al., 2022) , EvenNet (Lei et al., 2022) , and FavardGNN/OptBasisGNN (Guo & Wei, 2023) . We employ the standard and popular training/validation/testing split method (Kipf & Welling, 2016; Klicpera et al., 2018) on three citation networks for semi-supervised node classification, i.e., Cora, Citeseer, and Pubemd, with 20 nodes per class for training, 500 and 1,000 nodes for validation and testing. We split each class of nodes into 2.5%, 2.5%, and 95% as training, validation, and testing sets for other datasets and all models share the same ten random splits for a fair comparison. The seed used for dataset splitting is 42 or 1941488137 (He et al., 2022) .Results. Table 5 reports the results of the different models on all datasets for semi-supervised node classification and gives mean classification accuracy and standard deviation over ten foxed splits. Table 5 shows that TFE-GNN achieves state-of-the-art performance on 6 datasets, where TFE-GNN con and TFE-GNN rw+sum also show strong competitiveness, which is similar to the experimental results of full-supervised node classification. TFE-GNN outperforms FavardGNN/OptBasisGNN (Guo & Wei, 2023) on Wisconsin, Texas, and Corenell (strong heterophily) by 8.99%, 12.01%, and 6.78%, respectively, which amounts to performance improvements of 17%, 22%, and 13%. The t-SNE visualization in Figure 4 demonstrates that the graph convolution T F E 1 (b) can extract meaningful patterns on Citeseer (strong homophily), which the graph convolution T F E 2 (c) is not able to capture. The t-SNE visualization in Figure 5 demonstrates that T F E 2 is better than T F E 1 at extracting the information used for categorization on Squirrel (strong heterophily). The output of TFE-GNN(d) shows clearer boundaries among classes (colors) than that of T F E 1 and T F E 2 . These visualization findings validate the competitiveness of TFE-GNN and echo its leading performance on node classification. We add some experiments to analyze TFE-GNN's generalization. These newly designed generalization experiments use the early stopping mechanism, i.e., no longer train for 1000 epochs as fixed as in Figure 2 . of TFE-GNN(f) is much closer to its training loss in the six subplots of Figure 6 , although its losses are more volatile. This observation demonstrates that TFE-GNN's generalization is best when it achieves state-of-the-art classification performance because the early stopping mechanism allows TFE-GNN to carry less stable losses. TFE-GNN yields two hyper-parameters K lp and K hp in addition to those associated with the neural network, since we parameterize ω, ω ′ , and ϑ as learnable coefficients. We conduct 200 experiments to obtain the interactions between K lp and K hp and the objective values corresponding to model accuracy. We draw their contour plots on Cora and Chameleon. Figure 7 shows parametric contour, where the horizontal coordinate "hop1" denotes the hyper-parameter K lp and the vertical coordinate "hop2" denotes the hyper-parameter K hp . The parametric contour in Figure 7 demonstrates that there is a difference in the distributions of the objective values (model accuracy) on Cora(a) and Chameleon(b), i.e., there is a large difference in the influence of "hop1" and "hop2" on homophily and heterophily graphs.We conduct time efficiency experiments to count training times for ChebNet (Defferrard et al., 2016) , BernNet (He et al., 2021a) , ChebNetII (He et al., 2022) and TFE-GNN. All experiments are carried out on the machine with Linux system, two NVIDIA Tesla V100 and twelve Intel(R) Xeon(R) Gold 5220 CPU @2.20GHz. Table 8 shows the results of time efficient experiments on Cora, where TFE-GNN_zero indicates that K lp or K hp has and only a value of 0, TFE-GNN_ten indicates that hyper-parameter K lp or K hp has and only a value of 10, the other hyper-parameter has the value K and TFE-GNN_all indicates that K lp and K hp have the same value K. We take the average of the times of ten training (100 epochs each) as time overheads (unit: second).The columns in Table 8 imply the change in model-invariant training time as K increases, and the rows imply the change in K-invariant training time as the model varies. Table 8 shows the variation in training time and the comparison between the different models. We observe that the training time of TFE-GNN is significantly smaller than that of ChebNetII when the value of K is relatively large.Although BernNet and ChebNetII start with a low training time, they quickly catch up and surpass the other models as K increases. Therefore, TFE-GNN has a clear advantage when a larger receptive field (K) is required. TFE-GNN is more suitable for full-supervised node classification than semi-supervised node classification. The key technical differences: TFE-GNN is free from polynomial computation, coefficient constraints, and specific scenarios, compared to polynomial-based spectral GNNs and heterophilyspecific Models (Platonov et al., 2023) , such as ChebNetII (He et al., 2022) and PCNet (Li et al., 2023) . We also describe the differences between TFE-GNN and several other methods (Li et al., 2024; Huang et al., 2024b,a) .PEGFAN (Li et al., 2024) sets up three optional feature matrices for the homophilic and heterophilic graphs, respectively, and performs a concatenation operation for the selected feature matrices. PEG-FAN performs row normalization on the feature matrices that message passing and dimensionalityreducing outputs, and adds a new linear layer before sof tmax after the activation function ReLU . These components increase network complexity of PEGFAN, whereas TFE-GNN is more concise and requires less space.UniFilter (Huang et al., 2024b) establishes a link between the estimated graph homophily rate ĥ and the propagation matrix P by θ = π/2(1 -ĥ), and forms heterophily bases u 0 , u 1 , . . . , u K and the rotation matrix P θ , in which learn coefficient w discloses the significance of each frequency component in graph. The performance of UniFilter is affected by the ĥ estimated from the training data labels, which seems to require that the training data label distribution is similar to the graph true global label distribution. The difference between TFE-GNN and UniFilter is that TFE-GNN rarely relies on such priori knowledge and conditions, which ensures its better adaptability and classification performance.Flow2GNN (Huang et al., 2024a ) is an interesting and novel attempt, which decomposes the original adjacency matrix into two matrices via a random binary matrix G (l) with elements that follow the Bernoulli distribution. Information flows within the nodes in two respective disentangled graphs with reduced heterophily, and then adaptively aggregates them with the strength estimation vector p (l) i of information flow. TFE-GNN combines the well-performing and well-tested graph filters, while Flow2GNN is highly dependent on G (l) and p (l)i .Hyper-parameters. We provide more experimental details for reproducing the experiments. Table 9 shows the hyper-parameters of TFE-GNN on datasets for full-supervised node classification. Table 10 shows the hyper-parameters of TFE-GNN on datasets for semi-supervised node classification. The symbol optim denotes the optimizer, K lp denotes the order of the low-pass graph filter, K hp denotes the order of the high-pass graph filter, drop pro denotes the dropout rate of input features, drop lin denotes the dropout rate of intermediate features, lr ada denotes the learning rate of the learnable coefficients ω and ω ′ , wd ada denotes the weight decay of ω and ω ′ , lr adae denotes the learning rate of ϑ, wd adae denotes the weight decay of ϑ, lr lin denotes the learning rate of MLP f mlp , and wd lin denotes the weight decay of f mlp .Note that different DGL and PyTorch versions can affect model performance, and that fine-tuning of parameters, including but not limited to hyperparameters and seeds, may be required in order to reproduce the effect in this paper. For datasets roman-empire, amazon-rating, fb100-Penn94 and genius, this paper uses DGL 0.5.2 and PyTorch 1.5.1, and for other datasets, this paper uses DGL 0.9.0 and PyTorch 1.12.1.Baseline implementations. We use the officially released code for GCNII, TWIRLS, GPR-GNN, BernNet, ChebNetII, H 2 GCN, Haf-Hop, ARMA, EGNN, PDE-GCN, SPECFORMER, EvenNet, FavardGNN/OptBasisGNN,and PCNet. And we use the Deep Graph Library implementations for other models, such as GCNs, APPNP, ChebNet, etc. We did not spend a lot of time tuning parameters for these models. The code URLs are as follows. Justification: abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: In this paper, the authors proposed a new GNN model based on a triple filter ensemble mechanism (TFE-GNN), which aims to learn a spectral GNN with theoretically guaranteed filter approximation power and strong generalizability in practical node classification tasks. In theory, the authors demonstrated that the proposed TFE-GNN is equivalent to ChebNet under some specific settings, so they have the same filter approximation power. Moreover, this model leads to the combination of two spectral GNNs that correspond to heterophilic and homophilic graphs, respectively, which provides a unified GNN framework. Experiments show that the proposed method achieves promising performance in various node classification tasks. 

All three reviewers scored this paper positively, and their concerns about this work's motivation, complexity, and solidness were resolved in the rebuttal phase. In addition, although both SAC and I agree that the merits of this paper seem to outweigh the issues, we believe that more generalizability tests are required, e.g., testing model performance with increased data noise or in some OOD scenarios, and that comparisons with baselines like ChebNet in such scenarios are necessary. Otherwise, the claims in the abstract and introduction are not convincing to some extent.

In summary, I decided to accept this work and strongly suggest the authors polish this paper according to the reviewers' comments.

Reviews: review: paper_summary: paper_summary: This paper proposed a spectral GNN with triple filter ensemble (TFE-GNN) that aims to retain both the ability of polynomial based spectral GNNs to approximate filters and the higher generalization and performance on graph learning tasks, when most existing GNNs can only retain one of the two capabilities. Theoretical analysis shows that the approximation ability of TFE-GNN is consistent with that of ChebNet under certain conditions, namely it can learn arbitrary filters. Experiments show that TFE-GNN achieves high generalization and best performance on various homophilous and heterophilous real-world datasets.
strength_weakness: strength_weakness: - My main concern is that the heterophilous datasets that are used in the experiments are not up-to-date. Specifically, the five heterophilous datasets in the experiments are a subset of those first adopted by Pei et al. 2020 (Geom-gcn).  However, recent works like Platonov et al. 2022 has identified several drawbacks of these datasets, including leakage of test nodes in the training set in squirrel and chameleon, which can render the results obtained on these datasets unreliable. I recommend the authors to run additional experiments on two more up-to-date heterophilous datasets, such as those introduced in the papers below:
    - Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2022. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. In The Eleventh International Conference on Learning Representations.
    - Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao,
    and Ser Nam Lim. 2021. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems 34 (2021), 20887–20902.
- The authors discussed that for existing GNN models, “some polynomial-based models use polynomials with better approximation than some other models when approximating filters, but the former’s performance is lagging behind that of the latter on real-world graphs.” The proposed TFE-GNN models seem to have overcome that limitation, but 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?
questions: questions: It would be great if the authors can address the points discussed in weakness during the rebuttal.
limitations: limitations: The paper includes discussion regarding the limitations in Appendix A.2, most notably the reliance on setting hyperparameters $K_{lp}$ and $K_{hp}$ that are suitable for the homophily level of datasets.
paper_summary: paper_summary: This paper proposes a spectral GNN with triple filter ensemble (TFE-GNN). As the ensemble of two diverse and simple low-pass and high-pass graph filters, TFE-GNN achieves good generalization ability and SOTA performance on both homophilic and heterophilic datasets.
strength_weakness: strength_weakness: W1. One major statement that TFE-GNN has better generalization then other adaptive filter GNNs is not fully explained - only empirical results on the loss curves are shown. As a major contribution emphasized in the abstract, more theoretical and empirical results are usually expected. 

W2. The relevance of the abstract and introduction and the later sections can be enhanced. For example, most theoretical analyses are about the expressiveness of TFE-GNN, which is not stressed in the introduction.
questions: questions: Questions: 

Q1. In the introduction section, could you provide some references for the second problem, that the existing methods for solving problem one reduce the generalization ability of GNNs? 

Q2. In Table 5 in Appendix A.2, is there a typo (93.13±0.62) in the last row of the second column? It significantly outperforms all other settings but is not marked in bold as the best result. 

Q3. In Figure 5 in Appendix B.3, there is a large oscillation of the validation loss of the TFE-GNN, compared to other models. Could you account for this oscillation?  

 

Suggestions: 

S1. The idea of combining low-pass and high-pass filters is explored by many works (PCNet[1], GBK-GNN[2]). It would be interesting to explore the generalization ability between this class of two-fold filters versus general polynomial filters. 

S2. The statement of the second problem (starting from line 64) that “Carefully crafted graph learning methods, sophisticated polynomial approximations, and refined coefficient constraints led to overfitting” needs clarification or references. 


[1] Li, Bingheng, Erlin Pan, and Zhao Kang. "Pc-conv: Unifying homophily and heterophily with two-fold filtering." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 12. 2024. 

[2] 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.
limitations: limitations: -
paper_summary: paper_summary: This paper proposes a novel spectral GNN architecture, the TFE-GNN, which integrates homophily and heterophily using a triple filter ensemble (TFE) mechanism. The model aims to overcome the limitations of existing polynomial-based learnable spectral GNNs by adaptively extracting features from graphs with varying levels of homophily. The TFE-GNN combines low-pass and high-pass filters through three ensembles, enhancing the generalization and performance of the model. Theoretical analysis and experiments on real-world datasets demonstrate the effectiveness and state-of-the-art performance of TFE-GNN.
strength_weakness: strength_weakness: * The paper does not address potential computational overhead introduced by the triple filter ensemble mechanism;
* The descriptions of the theorems are too lengthy and not concise.
questions: questions: * Can the ensemble methods (EM1, EM2, EM3) be further optimized or replaced with alternative techniques to improve performance?
* What is the computational overhead of the triple filter ensemble mechanism compared to traditional spectral GNNs? How does the model scale with larger graphs and higher-dimensional feature spaces?
* The authors mention that TFE-GNN has higher generalization. Why? Any theoretical results for charactering the generalization ability of TFE-GNN?
* (I am quite curious about it) Are there specific scenarios or types of graphs where TFE-GNN might not perform as well?
*Authors may consider discussing the key technical differences between the proposed work and recent methods on heterophilous graph learning, such as: [1] Permutaion equivariant graph framelets for heterophilous graph learning; [2] How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing; [3] Flow2GNN: Flexible two-way flow message passing for enhancing GNNs beyond homophily
limitations: limitations: The authors have discussed the limitations of their work adequately.

Comments: title: Response to Reviewer pzPy
Response to the rebuttal
Response to Reviewer zzRJ
Response to Reviewer eCxX
Response to Authors' Rebuttal
Explanation of Question 4 on Reviewer zzRJ
comment: 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.
Thank you for your detailed explanations to address the concerns and questions. Most of my questions are properly explained. The experiments are also extended to provide more solid proof of generalization: The authors introduced datasets of different edge homophily levels to explain how TFE-GNN generalize on diverse datasets. A theoretical explanation is also provided based on some references. I am expecting a more in-depth explanation on role of the key innovation - ensembleod nonetheless. 

This paper introduces a spectral GNN with triple filter ensemble. Through experiment results are theoretical explanations, the authors proved that TFE-GNN has strong approximation ability and generalization ability. This work provides an interesting combination of the graph filters and ensemble methods to produce a robust graph learning method. 

Based on the contributions and results of the work, I consider it acceptable to the conference. I hope the authors can delve into the origin of the effectiveness for a better understanding of the GNN community.
Thanks for your helpful feedback! We will cite the suggested references in the final version because of the addition of a new section entitled "TFE-GNN Versus Other GNNs with Similar Aggregation Paradigms" and add the relevant parts of the response to the final version.
We thank the reviewer for reading and agreeing with our responses, and we appreciate that the reviewer agreed with our paper and kept the original rating. We will add the relevant parts of the response to the final version.
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.
> **Question 4:** (I am quite curious about it) Are there specific scenarios or types of graphs where TFE-GNN might not perform as well? The key technical differences between the proposed work and recent methods on heterophilous graph learning.

**Q-A4:** Thanks for your valuable and constructive questions. TFE-GNN is more suitable for full-supervised node classification than semi-supervised node classification. **The key technical differences: TFE-GNN is free from polynomial computation, coefficient constraints, and specific scenarios,** compared to polynomial-based spectral GNNs and heterophily-specific Models [8], such as ChebNetII [4] and PCNet [5]. The key differences between TFE-GNN and the models mentioned in this question are the following.

+ Flow2GNN [3] is an interesting and novel attempt, which decomposes the original adjacency matrix into two matrices via a random binary matrix $G^{(l)}$ with elements that follow the Bernoulli distribution. Information flows within the nodes in two respective disentangled graphs with reduced heterophily, and then adaptively aggregates them with the strength estimation vector $p_i^{(l)}$ of information flow. **TFE-GNN combines the well-performing and well-tested graph filters, while Flow2GNN is highly dependent on $G^{(l)}$ and $p_i^{(l)}$.**

+ UniFilter [2] establishes a link between the estimated graph homophily rate $\hat{h}$ and the propagation matrix $P$ by $\theta =\pi /2(1-\hat{h})$, and forms heterophily bases $\lbrace u_0,u_1,…,u_K \rbrace$ according to Algorithm1 and then obtain the rotation matrix $P_{\theta}$. UniFilter combines $P$ and $P_{\theta}$ using the coefficient $\tau$ and its weight vector $w$ 
discloses the significance of each frequency component in graph. The performance of UniFilter is affected by the $\hat{h}$ estimated from the training data labels, which seems to require that the training data label distribution is similar to the graph true global label distribution. **The difference between TFE-GNN and UniFilter is that TFE-GNN rarely relies on such priori knowledge and conditions, which ensures its better adaptability and classification performance.**

+ PEGFAN [1] sets up three optional feature matrices for the homophilic and heterophilic graphs, respectively, and performs a concatenation operation for the selected feature matrices. PEGFAN performs row normalization on the feature matrices that message passing and dimensionality-reducing outputs, and adds a new linear layer before $softmax$ after the activation function $ReLU$. **These components increase network complexity of PEGFAN, whereas TFE-GNN is more concise and requires less space.** 

+ We will add a new section "TFE-GNN Versus Other GNNs with Similar Aggregation Paradigms", named B.6, to analyze these models and add the above related content to the appendix of the final version.

**References**

[1] Jianfei Li et al. Permutaion equivariant graph framelets for heterophilous graph learning. TNNLS, 2024.

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

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

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

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

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

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

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