{'fraction_non_alphanumeric': 0.04222150048717116, 'fraction_numerical': 0.013699843514718474, 'mean_word_length': 4.3012991078416025, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
When Does A Spectral Graph Neural Network Fail in Node Classification?

Spectral Graph Neural Networks (GNNs) with various graph filters have received extensive affirmation due to their promising performance in graph learning problems. However, it is known that GNNs do not always perform well. Although graph filters provide theoretical foundations for model explanations, it is unclear when a spectral GNN will fail. In this paper, focusing on node classification problems, we conduct a theoretical analysis of spectral GNNs performance by investigating their prediction error. With the aid of graph indicators including homophily degree and response efficiency we proposed, we establish a comprehensive understanding of complex relationships between graph structure, node labels, and graph filters. We indicate that graph filters with low response efficiency on label difference are prone to fail. To enhance GNNs performance, we provide a provably better strategy for filter design from our theoretical analysis - using data-driven filter banks, and propose simple models for empirical validation. Experimental results show consistency with our theoretical results and support our strategy.


Introduction
Graph Neural Networks (GNNs) have continuously attracted interest as their promising performance in various graph learning problems. It is known that most of GNNs are intrinsically graph filters (Kipf & Welling, 2017;Defferrard et al., 2016;Ortega et al., 2018;Nt & Maehara, 2019). With the theoretical foundation of filters, there is an increasing attempt at model explanation, e.g. explaining the behavior of various GNNs in node classification. (Nt & Maehara, 2019) investigated the superiority of low-pass filters backed up with theoretical arguments while recent research (Balcilar et al., 2020;Chang et al., 2020;Bo et al., 2021) empirically revealed the weakness of GNNs with only low-pass filters in certain datasets. These contradictory views bring us to a question: why does a graph filter work on a dataset but not on another? More general, when does a graph filter fail and what limits its prediction performance?
Existing theoretical research is mostly restricted to the investigation of filters themselves, such as exploring their expressive power (Oono & Suzuki, 2020;Balcilar et al., 2020), without taking their inconsistency of performance on different graphs into account. In this paper, we conduct a theoretical analysis of spectral GNNs performance by investigating their prediction errors on different graphs. Our preliminary result of prediction errors encourages us to have a comprehensive understanding of the complex and ambiguous relationships between graph structure, node labels, and graph filters. In Sect.4, we propose significant graph indicators including interaction probability (as a metric of homophily) and response efficiency. With the aid of them, we perform further analysis on prediction error which underpins deep insights of the failure of graph filters: 1. A graph filter fails when it has low response efficiency on label difference or input difference; 2. A graph filter is a hidden structure-adjustment mechanism and it fails when it is limited to make graph homophilic high enough by strengthening internal connections of classes; 3. Graph filters are prone to fail on graphs with low information label differences. It leads us to another question: how to design filters to improve GNNs performance?
To address this concern, we apply our theoretical results to typical graph filters and investigate their potential behavior on different graphs. We show that low-pass filters are superior to high-pass filters in homophilic graphs and high-order filters have an advantage over low order filters in most cases. In addition, we provide a theoretical demonstration of the superiority of filter banks which have only been empirically used in previous works to enhance GNNs performance (Min et al., 2020;Gao et al., 2021). Based on these explorations, we propose an effective strategy for filter design, that is, learning filter banks in a data-driven manner.
To verify the effectiveness of the strategy we proposed, we develop a simple framework, named DEMUF, to learn dataspecified filter banks efficiently and examine our models on various datasets. Experimental results show that our model achieves a significant performance improvement compared with spectral GNN baselines across most benchmarks and have strong consistency with our theoretical conclusions.
The rest of the paper is organized as follows: we formulate the prediction error of spectral GNNs and obtain a general lower bound in Sect.3. In Sect.4, we propose two groups of graph indicators which underpins our deep insights of graph filters from the spatial and spectral perspectives in Sect.5. Following that, we draw two main conclusions in Sect.5.1 and apply them to three types of filters in Sect.5.2. In Sect.6, we develop a simple framework to implement the strategy we proposed for filter design and empirically validate our theoretical analysis.

Related Work
In this paper, we focus on the analysis of the performance of GNNs from the spectral perspective. Since Bruna et al. (2014) defined spectral graph filters and extended convolutional operations to graphs, various spectral graph neural networks have been developed. For example, ChebNet (Defferrard et al., 2016) defines the Chebyshev polynomial filter which can be exactly localized in the k-hop neighborhood. Kipf & Welling (2017) simplified the Chebyshev filters using a first-order approximation and derived the well-known graph convolutional networks (GCNs). Bianchi et al. (2021) proposed the rational auto-regressive moving average graph filters (ARMA) which are more powerful in modeling the localization and provide more flexible graph frequency response, however more computationally expensive and also more unstable. Recently, Min et al. (2020) augmented conventional GCNs with geometric scattering transforms which enabled second-order filtering of graph signals and alleviated the over-smoothing issue. In addition, most graph neural networks originally defined in the spatial domain are also found essentially connected to the spectral filtering (Balcilar et al., 2020). By bridging the gap between spatial and spectral graph neural networks, Balcilar et al. (2020) further investigated the expressiveness of all graph neural networks from their spectral analysis. However, their analysis is limited to the spectrum coverage of a graph filter itself and lacks deeper insights into the graph-dependent performance of these filters.
Another related topic is the graph homophily/heterophily. One important graph indicator we propose in the paper is the homophily degree which we define through the interaction probability. Beyond that, there have been some other heuristic metrics for homophily/heterophily in previous works. Pei et al. (2020) defined a node homophily index to characterize their datasets and help explain their experimental results for Geom GCN. Zhu et al. (2020) defined edge homophily ratio instead and identified a set of key designs that can boost learning from the graph structure in heterophily. Some recent works analyzed the impact of heterophily on the performance of GNNs Jin et al., 2021;Ma et al., 2021), but they are either limited to empirical study Jin et al., 2021) or just focused on GCNs (Ma et al., 2021). Our work differs from these works in that our homophily degree definition is only used as one of the graph indicators in our theoretical analysis of GNNs performance, and our analysis is also not limited to GCNs but for all spectral GNNs.

Problem Formulation
Notations. Let G n be an undirected graph with additional self-connection, A ∈ R n×n be the adjacency matrix and L = D − A be the Laplacian matrix, where D is a diagonal degree matrix with D ii = j A ij . We denoteÃ = D − 1 2 AD − 1 2 andL = I −Ã as the symmetric normalized Laplacian. Let (λ i , u i ) be a pair of eigenvalue and unit eigenvector ofL, where 0 = λ 0 ≤ · · · ≤ λ n−1 ≤ 2. In graph signal processing (GSP), {λ i } and {u i } are called frequencies and frequency components of graph G n .
In this paper, we are mainly interested in multi-class node classification problems on G n with labels T = {0, . . . , K − 1}.
For ∀k ∈ T , we denote C k as the set of nodes with label k and introduce a label matrix Y ∈ R n×K = (y 0 , . . . , y K−1 ), where y k is the indicator vector of C k . Let R = Y Y , then Y 1 = diag(R) and R k = |C k |. The general formulation of the l + 1-th layer of spectral GNNs is X (l+1) = σ(g(L)X (l) W (l+1) ), here g(L) is so-called the graph filter, σ(·) is an activation function and W (l+1) is a learnable matrix. In multi-class classification problems, σ(·) = softmax(·). In this paper, we say X (l) W (l+1) is the input of g(L) in l + 1-th layer.

Prediction Error
Definition 3.1 (Prediction error). For a graph G n withL, let X = (x 0 , . . . , x K−1 ) be the learnable input of g(L) in the last layer and Y = (y 0 , . . . , y K−1 ) be the label matrix, the prediction error is formulated as: Since Er(X, Y ) = l∈T Er(x l , y l ), estimating the entire prediction error equals to estimate that of any single label. Without loss of generality, in the following discussion, we focus on label y 0 and investigate Er(x 0 , y 0 ). By denoting y 0 = y 0 and y 1 = K−1 l=1 y l , we obtain a corresponding binary classification problem where Er(x 0 , y 0 ) is an approximation of Er(x 0 , y 0 ). For simplicity, in the rest of paper, we investigate Er(x 0 , y 0 ) in a binary classification. The theorem below provides a lower bound of it.
The proof is in Appendix B.1. The first inequality holds when x 0 = x 1 where Er(x 0 , y 0 ) = n 4 . This theorem indicates that prediction errors of binary classification are dependent on graph filter g(L), ∆y = y 0 − y 1 and ∆x = x 0 − x 1 , what we refer to as label difference and input difference in this paper, respectively. Then we have It makes us aware of the need to fully understand their impact on the performance of spectral GNNs.

Proposed Graph Indicators
In this section, we explore the relationships between graph structure, graph signals including node labels, and graph filters and define related graph indicators which underpins our further investigation on prediction error in Sect.5.

Spatial Graph Indicators
Homophily of graphs is considered an indisputable common property of most graphs. In this section, we derive a measure of homophily degree from interaction probability.
For a random walk on G n , P k = (D −1 A) k is the k-step transition matrix where P k ij is the probability that a random walker starting from node v i arrives at v j after k steps. j∈C l P k ij is the probability that a random walker starting from v i stays in C l at the k-th step, demonstrating the relative preference/closeness of node v i for C l at k-th scale. Based on this, we define interaction probability to reflect the strength of interaction between two classes.
Definition 4.1 (k-step interaction probability). For l, m ∈ T , denote P k = (D −1 A) k , the k-step interaction probability matrix is formulated as: Π k lm is the probability that a random walker from C l arrives at C m after k steps and m∈T Π k lm = 1.
Since P is not symmetric, then Π k lm = Π k ml . Below we propose a symmetric variant of interaction probability, which plays a key role in our theoretical analysis. Definition 4.2 (k-step symmetric interaction probability). For l, m ∈ T , denoteÃ k = (D − 1 2 AD − 1 2 ) k , the k-step symmetric interaction probability matrix is formulated as:Π That is, k-step (symmetric) interaction probability is not the k-th power of 1-step (symmetric) interaction probability.
Notations. In the rest of paper, we takeπ k l as the shorthand forΠ k ll . We denoteg(Π Noting thatΠ k 1 = 1,Π k is not a probability measure in the strict sense. However, it is a bridge to other graph indicators, as we will show in the rest of this section. Below, we show the relationship betweenΠ k and Π k . Proposition 4.4 (Interaction probability). For l, m ∈ T ,π 2k l ≥ (π k l ) 2 and π k l ≥π k l . More generally, The proof can be found in Appendix B.2. It indicates thatπ k l is the lower bound of π k l . Recall the descriptive definition of graph homophily -nodes with the same labels are more likely to cluster together, for a homophilic graph with symmetric interaction probabilityΠ, self-interaction probabilityπ k l is expected to gap away from {Π k lm |m ∈ T , m = l}. Definition 4.5 (k-homophily degree). For a graph G n with symmetric interaction probabilityΠ, the k-homophily degree of G n is defined as In binary classification problems, . Larger H k (Π|C l ) means C l have denser internal connections and sparser connections between other classes. Then intuitively, H k (Π|G n ) reflects the possibility to obtain a node's label directly from its neighbors. As we illustrate in Sect.5.1.2, one of the keys to the success of graph filters is to increase the possibility by strengthening internal connections of classes, that is, make graph more homophilic.

Spectral Graph Indicators
In this section, we develop another indicator -repsonse efficiency, to measure the effect of graph filters g(L) applied to different graph signals. Recall that {λ i } and {u i } are graph frequencies and frequency components. For a graph signal x with spectrum α = {α i = u i , x }, we are able to represent it as x = α i u i . Noting that α 2 k i α 2 i shows the percentage of occurrences in x for each u k , we introduce a distributional representation of x. Definition 4.7 (Frequency distribution). We define f , the frequency of signal x, as a random variable taking values in the set of graph frequencies with probability Pr(f = λ k ) = α 2 k i α 2 i . The probability describes the frequency distribution of signal x.
Since probability Pr(f = λ k ) = α 2 k i α 2 i is the weight of u k in x and g(λ k ) reflects how filter g(L) acts on u k , then we claim that k g(λ k ) Pr(f = λ k ) is the effect of g(L) acting on x. Although an all-pass filter can pass all frequencies, we appreciate a filter with a high magnitude response for important frequencies so that we can capture the main frequency information of a signal x efficiently. Definition 4.8 (Response Efficiency). For a graph filter g(L) and a signal x with spectrum α, the response efficiency of g(L) on x is defined as It can also be denoted as µ g (α).
We obtain a high response efficiency when the magnitude response of g(L) is positively associated with the frequency distribution of x. In Sect.5.1.1, we have further discussion of the relationship between graph response efficiency and its prediction performance. Before that, we investigate the consistency of proposed graph indicators.
Proposition 4.9. Let f l be the frequency of label y l , for a graph filter g(·), we have µ g (y l ) = The proof of this proposition can be found in Appendix B.2. Recall thatg( According to Proposition 4.4,π l ≤ π l ≤ 1 andπ 2 l ≥ (π l ) 2 . Therefore, whenπ l approaches 1, which reflects a high homophily degree of C l , both the mean and variance of label frequency are close to 0. It implies that, for a highly homophilic graph, the main information of labels is low-frequency so it should be assigned to low-pass filters. Rigorous support for this argument can be found in Sect.5.2.

Analysis of Graph Filters
In this section, we aim to figure out two major concerns: what causes the failure of a graph filter and how to design filters to improve GNNs performance? Precisely, we first provide a deep understanding of the performance of graph filters concerning label prediction with the aid of graph indicators we proposed above, then apply our theoretical conclusion to typical filters. From this, we have obtained insights into filter design.

FROM FILTER RESPONSE EFFICIENCY
Let δ, η be the spectra of ∆y, ∆x, respectively, it is trivial to revisit the inequality (3) of Er(x 0 , y 0 ) as: We attempt to establish an analysis of i ψ g(λ i )δ i η i which is the critical term of this lower bound in the spectral domain.
Before that, we introduce information content proposed by information theory to measure the informativeness of signal frequency.
The theorem indicates that the prediction error of a given graph filter is bounded by its response efficiency on labels and inputs difference. In GNNs, inputs are learnable. Ideally, a GNN with filter g can learn appropriate inputs with large enough µ g (η). In this way, the prediction error will be restricted only by the graph structure, node labels, and the filter itself, that is what Corollary 5.3 illustrates.
Corollary 5.3 (Spectral lower bound). For a binary classification problem, with the same settings and notations in Theorem 5.2, we have For a given classification problem, we claim that a graph filter fails if the lower bound of its prediction error is large. Corollary 5.3 (proof is provided in Appendix B.5) impels us toward deep insights of graph filters in terms of response efficiency: 1. A graph filter fails when it has low response efficiency on label difference, i.e., small µ g (δ), which means that it can't capture the main information used for label identification efficiently; 2. Most filters fail on graphs with low information label difference, i.e., small I(δ), which means that a closed difference of labels' probability on different frequency components would have been difficult to distinguish.

FROM GRAPH HOMOPHILY DEGREE
Recall the attempt we made to explore the relation between filter response efficiency on labels and graph homophily degree at the end of Sect.4, it inspires us to explain graph filters from a perspective of graph homophily.
Theorem 5.4 (Spatial lower bound). Given a binary classification problem on a graph G n whose label difference is ∆y with spectrum δ, for a graph filter g(·) ∈ S g and arbitrary input X, we have where m g = min The proof of Theorem 5.4 provided in Appendix B shows that for any function g(·) which is nonnegative on the closed This theorem brings us an explanation of graph filters in terms of homophily: a graph filter is a hidden structure-adjustment mechanism which transforms graph structure to g(I −Ã). It obtains poor prediction performance when it fails to make the high homophily degree H 1 (g(I −Π)|G n ) of transformed graph high enough. From this, we are able to glimpse the prediction capacity of filters on a given graph through the modified homophily degree.

Applied to Specific Graph Filters
In this section, we apply the above observations to specific graph filters and provide practical strategies to enhance GNNs performance. Here, we consider typical filters including first/second-order low/high-pass filters and investigate their advantage/disadvantage on different graphs by comparing their H 1 (g(I −Π)|G n ).
This theorem rigorously validates our inference of Proposition 4.9: low-pass filters are superior to high-pass filters on homophilic graphs. Compared with first-order filters, second-order filters involve 2-homophily degrees so that they can identify more different graphs. Actually, we show that second-order filters are easier to have better performance than first-order filters. Theorem 5.6 (First/second-order). Given a graph G n with interaction probabilityΠ and a = 2( , for g 1 ∈ S 1 g , there exists a g 2 ∈ S 2 g such that It shows the superiority of second-order filters on most graphs apart from those with a high 2-homophily degree and gives a guarantee to narrow the disadvantage. There is an intuitive hyperthesis to be inferred from this theorem: high-order filters have an advantage over low order filters in most cases. However, high-order filters would bring high computation costs. In practice, to enhance the GNNs performance, filter banks are empirically used in previous works. Below, we provide a rigorous demonstration of the advantage of filter banks. Theorem 5.7 (Filter bank). Given a graph G n with normalized Laplacian matrixL with eigenvalues {λ i }, ∀g 1 (·) in S 1 g , there exists a single filter g 2 (·) ∈ S 1 g and positive l 1 , l 2 s.t. for g = l 1 g 1 + l 2 g 2 we have m g1 m g log , and l 1 + l 2 = 1, here m g = min i∈Ig g(λ i ).
This theorem can be generalized to the family of second-order graph filters S 2 g .

A Strategy for Filter Design
According to our theoretical framework and conclusion on prediction error of a specific label, a graph filter that has a high response efficiency on this label difference or which can strengthen the internal connection of this class is the key to the success of GNNs. Considering a K-class classification problem, as we showed in Sect.3.1, we will obtain K related binary classification problems with K label differences. When these label differences have a high diversity of frequency distributions, a low order single filter is prone to fail since it can barely have high response efficiencies on all of them. In these cases, it is necessary to leverage a filter bank to handle different frequency distributions.
How to design a powerful filter bank efficiently? Theoretically, piling up sufficient numbers of graph filters to capture all the frequency components can improve prediction performance while it is very expensive. On the other hand, following our theoretical results, it is not difficult to design an ideal filter bank with the frequency distributions of label differences or graph interaction probability on hand. However, such graph indicators are usually unknown. Nevertheless, node features are accessible in attribute graphs and provide valid information for classification. As illustrated in Theorem 5.2, an ideal filter should have a high response frequency on both input difference and label difference. Here we assume that for each label there is some information provided by (partial) features useful for identification. Also, target frequency components and features may differ for different labels. When we classify labels with different target components having the same frequency, we need to separate objects with different target components before filtering. Otherwise, it is likely to bring noise and hurt the performance. Therefore, feature disentanglement is necessary. On the other hand, since a filter bank is applied to features to capture valid information, filter design should be targeted at specific graphs and features.

Model and Empirical Study
As already emphasized, one practical strategy for improving prediction performance is to learn a filter bank in a data-driven manner. In this section, to verify this theoretical strategy, we propose a simple framework -disentangled multi-filter framework ( There are two main model blocks of DEMUF frameworks: disentangle block and filter block. In Plain-DEMUF, all filter blocks run in parallel as their disentangled input are generated through a single disentangle block at the same time. Differently, each Tree-DEMUF layer contains two branches -one is early stopped while the other will be disentangled into two branches of the next layer after going through a filter.

Architecture of Two Frameworks of DEMUF
Following the conclusions in Sect.5.3, i.e., different features should be assigned to different filters, we assemble feature disentanglement and frequency filtering blocks to our framework. The block of feature disentanglement is to divide features into different families in a learnable way. Then in the frequency filtering block, learnable graph filters are applied to targeted families of features. We provide two frameworks with different structures: Plain-DEMUF and Tree-DEMUF (depicted in Fig. 1).
The DISENTANGLE block and FILTER block are formulated as follows: In our implementation, we provide two samples of DISENTANGLE functions Φ k : one is linear transformations, the other is GUMBEL SOFTMAX (Jang et al., 2017) used to generate learnable masks for feature selection. In terms of the FILTER block, we use the normalized second order filter g (L) = I − ((1− )I−L) 2 (1+| |) 2 with learnable parameter ∈ (−1, 1). In each FILTER block, h is the number of layers. The framework of Plain-DEMUF with N filters is: Based on this, we implement a simple model called P-DEMUF. Precisely, we leverage a GUMBEL SOFTMAX to generate N learnable masks {M 1 , . . . , M N } for feature sampling at once followed by different MLP. That is, Φ k (X) = MLP k (X M k ).
Similarly, we develop a model, T-DEMUF, under the framework of Tree-DEMUF formulated by: In each T-DEMUF layer, we use GUMBEL SOFTMAX with different parameters to generate two masks M k and M k and Φ k (X k ) = X k M k and Ψ k (X k ) = X k M k . In each layer, we stop further disentangling of the branch of H k by utilizing an additional constraint Noting that H k = (g k (L)) h k X k−1 M k , this constraint is to make (g k (L)) h k has high response efficiency on H k .
Model discussion. Compared with filter-bank learning methods which directly apply an array of filters to features, our models use subsets of features. It can greatly reduce the amount of computation and parameters and help learning filters more effectively. T-DEMUF uses an additional constraint to guide the filter learning process while filters in P-DEMUF do not interfere with each other. We provide further discussion and ablation study in Appendix A.

Experiments
To validate DEMUF, we compare the performances of P-DEMUF and T-DEMUF with that of spectral GNNs, spatial GNNs and MLP on extensive datasets. Baselines. We compare our models with four spectral GNNs: GCN (Kipf & Welling, 2017), ChebNet (Defferrard et al., 2016), GIN (Xu et al., 2019), ARMA (Bianchi et al., 2021). We list their spectral filter forms in Appendix A. In addition, we also add four spatial GNNs: GAT (Veličković et al., 2018), FAGCN (Bo et al., 2021), Geom GCN (Pei et al., 2020) and GPRGNN (Chien et al., 2020). Both GAT and FAGCN utilize attention mechanism, Geom GCN is a novel aggregation method based on the geometry of graph, GPRGNN can handle both homophilic and heterophilic graphs through learning GPR weights. Finally, we also compare with MLP which is an all-pass filter.

Result and Analysis
We summarize the experimental results in Table 1 and visualize the interaction probability and label frequency distribution of some typical graphs in Fig. 2.
Our models show consistent superiority on most benchmarks and outperform all spectral GNN baselines. These promising results strongly suggest that our strategy of filter design proposed in Sect.5.3 is effective to improve spectral GNNs' prediction performance. Precisely, T-DEMUF yields over 7.49% higher accuracy than the best baselines (ARMA) on Squirrel. Compared with baselines with first-order filters (GCN and GIN), our models and other baselines with high-order filters (Cheby and ARMA) have a huge lead on most of datasets apart from Cora and Citeseer. It empirically validates our argument about the superiority of high-order filters proposed in Theorem 5.6. On the other hand, the poor performance of GCN and GIN we implemented which are low-pass filters on graphs with low homophily degree verify our analysis on low-pass filters provided by Theorem 5.5. In addition, the visualization of Cora's indicators confirms our deduction in Sect.4.2 -high interaction probability brings high homophily degree and high concentration of label frequency distribution on low-frequency.
Interestingly, all models have poor performance on Actor (less than 42%) while partial models including T-DEMUF, P-DEMUF obtain over 90% prediction accuracy on WebKB networks and all have good results on Cora. We indicate that these observations strongly support our theoretical analysis on prediction error in terms of graph indicators in Sect.5.1.1 and 5.1.2. For example: 1. high homophily degree makes Cora easy to be classified; 2. highly diverse label frequency distributions which imply high label difference information content give a guarantee of good performance of appropriate filters on Wisconsin; 3. low homophily degree and similar label frequency distributions of Actor make all models fail.

Conclusion
In this paper, we conduct a theoretical analysis on the prediction error of spectral GNNs and develop a deep analysis of graph filters' performance based on the introduction of significant graph indicators. We also propose an effective and practical strategy for filter design which has been empirically validated by a simple framework we developed.

A. Benchmarks and Model Discussion
A.1. Statistics information of benchmarks.
We use four types of real datasets -Citation network, WebKB, Actor co-occurrence network and Wikipedia network, to validate our proposed models. Cora and Citeseer (Sen et al., 2008) are widely used citation benchmarks which represent paper as nodes and citation between two papers as edges. Cornell, Texas, and Wisconsin (Pei et al., 2020) are three subgraphs of WebKB which is a webpage network with web pages as nodes and hyperlinks between them as edges. Chameleon and Squirrel (Rozemberczki et al., 2021) are two Wikipedia networks with web pages as nodes and links between pages as edges. The nodes originally have five classes while Bo et al. (2021) proposed a new classification criteria which divides nodes into three main categories. In this paper, the relabeled networks are called Chameleon2 and Squirrel2. Actor (Tang et al., 2009) is a subgraph of the fillm-director-actor-writer network whose nodes only represent actors and edges represent their collaborations.
We provide statistics information of our benchmarks in Table. A.1. A.2. Spectral filters.
In our paper, we use four spectral GNNs as baselines whose spectral filters are listed as Table.A.2 and define a normalized second order filter g (L) with ∈ [−1, 1]. Model , it is exactly an overlap between a low-pass filter (2 + | | − )I −L and a high-pass filter (| | + )I +L.
For a given graph G n with interaction probabilityΠ, we investigate H 1 (g(I −Π)|G n ) for our second-order filter and the filter of GCN. We first normalize GCN's filter as g gcn (L) = I −L 2 , then we have How can our filter bank selection be data-driven.
As we clarified in Sect.6, our implementation of disentanglement is not random masking but learnable masking leveraging GUMBEL-SOFTMAX. These learnable maskings disentangle node features into several subsets of features. In our algorithm, although the form of our second order filter g (L) is predefined, its parameters including and weight ω are learned from specified graphs. Moreover, the parameters of our feature disentanglement blocks (the linear transformations and learnable masking) are also learned from data which will affect the learning of the filter bank. Therefore, our filter bank selection is data-driven.

A.4. Experimental Setup and Additional Results
Experimental Setup.
For all data, we use 60% nodes for training, 20% for validation and 20% for testing. For all experiments, we report the mean prediction accuracy on the testing data for 10 runs. We search learning rate, hidden unit, weight decay and dropout for all models in the same search space. Finally, we choose learning rate of 0.01, dropout rate of 0.5, and hidden unit of 64 over all datasets. The number of filters are searched between 2 to 10, and the final setting is: both T-DEMUF and P-DEMUF use 2 filters with 1 layer and 3-layer MLP on WebKB; 2 filters with 18 layers and 3-layer MLP on Wikipedia and 5 filters with 1 layer and 4-layer MLP on Actor. For Citation networks, T-DEMUF uses 4 filters with 7 layers while P-DEMUF uses 3 filters with 8 layers. In addition, as the setting of benchmarks are the same as that in Geom GCN, we refer to the results reported in (Pei et al., 2020).

Ablation Study.
To show the advantage of using disentanglement, we provide an ablation study on five benchmarks. Here, we propose two ablation models based on P-DEMUF. Recall that the disentanglement block of P-DEMUF consists of learnable masking and linear transformations, we design our ablation models by taking off the component of masking and linear transformation. Also, for fair and intuitive comparison, we simply fix the number of filters as 2. The results shown as Table.A.4 validate that if we take off the disentanglement blocks of P-DEMUF, the results become worse in most of benchmarks. Before presenting the proof of Theorem 3.2, we start with a useful lemma.

B.2. Proof of Proposition 4.4 and 4.9
We first introduce two useful lemma. Proof. Since x = n−1 i=0 α i u i , u i is the i-th unit eigenvector ofL and λ n = u iL n u i then we have Lemma B.3. Let B ∈ R n×n is a symmetric matrix, ∀ij, y ∈ R n , we have y B 2 y y y ≥ y By y y 2 .
Proof. Since B is symmetric, then we have B = U ΛU , here U is matrix of unit eigenvectors of B. From the proof of Lemma B.2, we obtain that y B 2 y y y = (αiλi) 2 α 2 i and y By Therefore, we have (αiλi) 2 Below is the proof of Proposition 4.4.
Let m = l, then we get π k l ≥π k l . According to Lemma B.3, let g(·) = (·) n , since g(Ã) is symmetric, then we have Proof of Proposition 4.9.
Proposition 4.9 can be directly derived from Lemma B.2.
Below is the proof of Theorem 5.2 and 5.4.
Proof of Theorem 5.2.
Proof. To prove this theorem is equivalent to prove that for g 1 (L) = 1 I + 2L ∈ S 1 g and g 2 (L) = 1 I + 2L + 3L 2 ∈ S 2 g , then for homophilic graphs with H 1 (Π|G n ) > 0, we can always find a low-pass filter work better than a high-pass filter; otherwise, we can always find a high-pass filter work better than a low-pass filter.
Proof of Theorem 5.7 Proof. Here we assume that I γ−ω = ∅, that is for any g, I g,γ−ω = I g . Below, we assume that R 0 = R 1 .
If 2 > 0, g is a high-pass filter and m g = 1 ; if 2 < 0, g is a low-pass filter and m g = 1 + 2 λ n−1 where λ n−1 is the maximal eigenvalue.