Year: 2021

Abstract:
Graph Neural Networks (GNNs) have received extensive affirmation for their promising performance in graph learning problems. Despite their various neural architectures, most are intrinsically graph filters that provide theoretical foundations for model explanations. In particular, low-pass filters show superiority in label prediction in many benchmarks. However, recent empirical research suggests that models with only low-pass filters do not always perform well. Although increasing attempts to understand graph filters, it is unclear how a particular graph affects the performance of different filters. In this paper, we carry out a comprehensive theoretical analysis of the synergy of graph structure and node features on graph filters’ behaviors in node classification, relying on the introduction of interaction probability and frequency distribution. We show that the homophily degree of graphs significantly affects the prediction error of graph filters. Our theory provides a guideline for graph filters design in a data-driven manner. Since it is hard for a single graph filter to live up to this, we propose a general strategy for exploring a data-specified filter bank. Experimental results show that our model achieves consistent and significant performance improvements across all benchmarks. Furthermore, we empirically validate our theoretical analysis and explain the behavior of baselines and our model.

heading: 1 INTRODUCTION
text: 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 on low-pass filters pose a significant problem: Why does a filter work on one dataset but not on another? More precisely, for a given filter, what kinds of structure and features are useful for prediction? This makes it clear to us that in order to solve this problem, it is necessary to take into account graph information, including the graph structure, features, and labels.
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 considering their inconsistency of performance on different graphs. It is clear that structural and feature information lead to the possible inconsistency. However, there has been little explicit analysis of how graph information influences the performance of graph filters. For instance, GNNs have formulated a variety of graph filters in a heuristic manner under a suppressed homophily assumption, i.e., nodes with similar attributes/labels tend to have connections. There remains a paucity of quantitative description of homophily until Pei et al. (2020) designed a rough index to measure it.
In this paper, we establish a comprehensive theoretical analysis of the effect of structure and feature information on node label prediction to fill the gap and provide deep insights into the explanation of graph filters. We first establish a systematic investigation on graphs with an indicator in terms of homophily - the interaction probability and a distributional representation of input information - the
frequency distribution. The interaction probability derived from random walk theory relates node labels with its local topology and quantifies the degree of clustering of nodes in the same/different class. We argue that interaction probability reflects the difficulty in identifying one class from others. In terms of feature information, we draw on spectral analysis representing features as frequency distributions. Furthermore, we consider the moment of frequency and build an explicit relation with graph structure. Interestingly, we find that the moment of label frequency (noting that a one-hot label vector can be regarded as a special node feature) is determined by interaction probability. The aforementioned preparations underpin our deep understanding of graph filters.
We validate the prediction error of a graph filter under two settings: a. fixed graph structure, unravel the influence of input (original or transformed node features); b. given input, show how structure matters, and provide analysis utilizing frequency distribution and interaction probability. The main conclusions are: 1. given structure, the frequency response of an ideal graph filter should be consistent with the main frequency band of label frequency, that is, a matched frequency response is the premise of success; 2. given input, a graph filter essentially tunes the weight of edges - failing to make a homophily degree large enough may cause an unsatisfactory prediction accuracy. These interpretations of graph filters imply a data-driven filter design principle. In addition, we apply these theoretical results to three types of filters - low-pass, high-pass, and band-pass filters with specified form. It shows that a single graph filter is hard to comply with the principle of ideal filters, especially when the homophily degree and label frequency distribution of different classes are very different. For example, when frequency distributions of labels are far from each other, it is hard to find a single filter whose frequency response can cover all the main frequency bands well. In this paper, we leverage a combination of band-pass graph filters to overcome this problem and develop a simple yet effective framework to show how to learn multiple filters depending on datasets. We empirically validate our theoretical analysis and investigate structure and feature information of benchmarks. We verify our model on a variety of datasets and explain the behavior of baselines and our model. Experimental results show that our model achieves a consistent and significant performance improvement across all benchmarks.
Our main contributions are: 1.We develop a theoretical analysis of graph information based on the introduction of interaction probability and frequency distribution; 2.We provide a deep understanding of the performance of graph filters illustrating how graph structure and input information matter; 3.We indicate the weakness of GNNs with a single graph filter and propose a general framework to learn a data-specified filter bank which contributes to significant improvement.

heading: 2 RELATED WORK
text: In this paper, we focus on the analysis of graph filters in the context of graph neural networks. 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. Very recently, Min et al. (2020) augmented conventional GCNs with geometric scattering transforms which enabled band-pass filtering of graph signals and alleviated the oversmoothing 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 measurement of graph homophily. Beyond the interaction probability that we define in this paper, there are some other heuristic metrics for homophily. Pei et al. (2020) defined a node homophily index to characterize their datasets and help explain their experimental results for Geom_GCN: β = 1#nodes ∑ v #neighbors of v that have the same label as v #neighbors of v . 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: h = #edges whose end nodes have same labels#edge . This edge homophily definition is sensitive to the number of classes and size of each class, and Lim et al. (2021) made a modification to alleviate this problem. Our work differentiates from these works in that we not only use our definition to characterize the graph but also directly relate it to the performance of graph filters (or GNNs).

heading: 3 THEORETICAL ANALYSIS OF GRAPH INFORMATION

heading: 3.1 NOTATION
text: Let Gn = (Vn, En) be an undirected graph with additional self-connection, where Vn = {v0, . . . , vn−1} is the set of nodes and En ⊂ Vn × Vn is the set of edges. Let A ∈ Rn×n be the adjacency matrix and L = D − A be the Laplacian matrix, where D is a diagonal degree matrix with Dii = ∑ j Aij . we denote Ã = D − 12AD− 1 2 , then L̃ = D− 1 2LD− 1 2 = I − Ã is the
symmetric normalized Laplacian. Let (λi,ui) be a pair of eigenvalue and unit eigenvector of L̃, where 0 = λ0 ≤ · · · ≤ λn−1 ≤ 2.

heading: 3.2 PROBLEM SETTING
text: In this paper, we are mainly interested in node classification problems on undirected graphs. Given Gn = (Vn, En), we consider T = {0, . . . ,K−1} as the set of all node labels. For ∀k ∈ T , we denote Ck as the set of nodes with label k and R ∈ RK×K as a size matrix which is a diagonal matrix with Rk = |Ck|. Considering single-label problems in which classes are mutually exclusive, we use onehot encoding to indicate the class label and introduce a label matrix Y ∈ Rn×K = (y0, . . . ,yK−1) to represent the labels of Vn, where yk is the indicator vector of Ck. Obviously, R = Y ⊤Y , Y ⊤1 = diag(R) and Y 1 = 1. A signal x on Gn can be arranged the signal values in a vector form x = (x0, . . . , xn−1) ⊤. Particularly, labels {yk|k ∈ T } are also graph signals.

heading: 3.3 A STRUCTURE INDICATOR - INTERACTION PROBABILITY
text: Homophily of graphs is an implicit assumption widely leveraged in graph learning methods including GNNs. It is considered an indisputable common property of most graphs, despite its descriptive and unquantifiable definition, which introduces a variety of uncertainties. In this section, starting with the random walk, we introduce interaction probability to overcome this challenge.
For a random walk on Gn, we denote P = D−1A as its transition matrix which is also a row Markov matrix. From the random walk theory, P k is the k-step transition matrix, and P kij is the probability that a random walker starting from node vi arrives at vj after k steps. For a node v and a class Cl, we denote πki (Cl) as the probability that a random walker starting from vi stays in Cl at the k-th step. It is trivial that πki (Cl) = ∑ j∈Cl P k ij with ∑ l∈T π k i (Cl) = 1. πki (Cl) demonstrates the relative preference/closeness of node vi for Cl with k-scale. To meet the homophily assumption, for vi in Cl, πki (Cl) is expected to gap away from others. Since πki (Cl)− ∑ m ̸=l π k i (Cm) = 2πki (Cl)− 1, πki (Cl) can be regarded as a measure of the k-scale homophily degree of node vi. Particularly, for ∀k ∈ N and vi ∈ Cl, πki (Cl) = 1 means that Cl is a community and will never communicate with other classes. However, this case is rare in real graphs. Below, we investigate the homophily of a class and propose a method to measure the communication strength between two classes. Definition 3.1 (k-step interaction probability). For l,m ∈ T , we define Πk as the k-step interaction probability matrix formulated as follows:
Πklm = 1
Rl ∑ vi∈Cl πki (Cm) = 1 Rl ∑ vi∈Cl,vj∈Cm P kij = y⊤l P kym y⊤l yl
(1)
Πk = (Y ⊤Y )−1Y ⊤P kY = R−1Y ⊤P kY. (2)
Πklm is the probability that a random walker from Cl arrives at Cm after k steps. Remark 1. Obviously, Πk1 = 1. Πklm is the mean proportion of Cm in the k-hop neighbors of nodes from Cl. Noting that rank(Y ) = K, when K ̸= n, Y R−1Y ⊤ ̸= I , thus (R−1Y ⊤PY )k ̸= R−1Y ⊤P kY , i.e. (Π)m ̸= Πm. More generally, for an arbitrary polynomial function g, R−1Y ⊤g(P )Y is likely not equal to g(R−1Y ⊤P kY ). In the rest of paper, we
write g̃(Π) = R−1Y ⊤g(P )Y and g(Π) = g(R−1Y ⊤P kY ). For instance, if g(·) = (·)m, then g̃(Π) = Πm and g(Π) = (Π)m. Also, we denote Πkll, the self-interaction probability, as π k l for short.
1-step interaction probability intuitively reflects the degree of clustering of two classes and ∑k
i=1 Π i
measures the strength of interaction between classes in the scale of k steps. Since P is not symmetric, Πklm ̸= Πkml. To facilitate analysis, here we propose a symmetric variant of interaction probability to identify the interactions between two classes. We denote this symmetric k-step interaction probability matrix as Π̃k, by replacing P with Ã = D− 1 2AD− 1 2 , we obtain Π̃k = R− 1 2Y ⊤ÃkY R− 1 2 . Below, we investigate the important properties of Πk and Π̃k. Proposition 3.1. For l,m ∈ T and an arbitrary polynomial function g(·), we have: a. RlΠklm +RmΠ k ml ≥ 2 √ RlRmΠ̃ k lm, where Rl is the l-th diagonal element of R; b. (g̃2(Π̃))ll ≥ (g̃(Π̃)ll)2, where g̃k(Π̃) = R− 1 2Y ⊤gk(Ã)Y R− 1 2 .
The proof can be found in Appendix B. Since Π̃k1 ̸= 1, that is, the measure is no longer a probability measure. However, according to Prop.3.1.a ( let m = l ), π̃kl is the lower bound of π k l , and π̃ k l = π k l when Gn is a regular graph. In the rest of theoretical analysis, we use π̃kl to measure the degree of Cl’s clustering. Let g(·) = (·)k, from Prop.3.1.b, we have π̃2kl ≥ (π̃kl )2. In Section.4.2, we leverage this inequality to derive a lower bound of our prediction error and further illustrate how structure influences the performance of a given filter.

heading: 3.4 A FEATURE INDICATOR - FREQUENCY DISTRIBUTION
text: Following the graph signal processing (GSP) concepts, λ0, . . . , λn−1 are graph frequencies and u0 . . . ,un−1 are the corresponding frequency components which are invariant of graph filters. Through Fourier transform, we obtain {αi = ⟨ui,x⟩|i = 0, . . . , n− 1} the spectral representation of a graph signal x, called graph signal spectrum. Moreover, a graph signal can be represented as a linear combination of frequency components, i.e., x = ∑ αiui. For a label vector yl which is also a graph signal, we denote {γ0, . . . , γn−1} as its spectrum. There is an intuitive assumption: information of label vectors is all we need for classification - we will validate this assumption in Section 4.1. Under this context, γ2i / ∑ i γ 2 i reflects how much the frequency component uk contributes to the distinctiveness of Cl, without considering the positivity and negativity of effects. Interestingly, we find that the normalized signal spectrum is a histogram/discrete distribution defined below. Definition 3.2 (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) = α2k /∑ i α 2 i . The probability describes the frequency distribution of signal x.
With this definition, we derive distributional representations of signals from their spectral representations/spectra. One can evaluate the signal effect by comparing frequency distributions of signals and label vectors under a specified distribution metric, such as Wasserstein distance. Below, we consider the moment of frequency distribution to show how graph structure influences signal frequency.
Proposition 3.2. For G = {V, E}, let f be the frequency of signal x, then E[fn] = x ⊤(I−Ã)nx
x⊤x .
The proof of this proposition can be found in Appendix B. With the definition of interaction probability, we further represent the moment of the label vector’s frequency.
Corollary 3.3. For label frequency fl of yl, we have E[fnl ] = ( g̃(I − Π̃) ) ll with g = (·)n.
Recall that g̃(I − Π̃) = R− 12Y ⊤(I − Ã)nY R− 12 , we have E[fl] = 1 − π̃l, E[f2l ] = 1 − 2π̃l + π̃2l and the variance of fl: Var(fl) = π̃2l − (π̃l)2. It can be seen that both the mean and variance of label frequency are close to 0 when π̃l approaches 1, which reflects a high homophily degree (as π̃l ≤ πl ≤ 1). In Section 4.1, we conduct a more detailed analysis of feature information of spectral space with frequency distribution.

heading: 4 ANALYSIS OF GRAPH FILTERS
text: A graph filter is defined as a function g with applied Laplacian matrix or adjacency matrix. Denote R[Ã] as a polynomial ring in Ã over R, here we are mainly interested in g ∈ R[Ã]. In this section, we
provide a deep understanding of the performance of graph filters concerning label prediction based on the above theoretical analysis of graph information. In general, there are two major concerns: with fixed graph structure, how does the input impact the performance of a given filter? and with fixed input, how does graph structure impact the performance of a given filter?. In this section, we provide the theoretical analysis of these two questions in Sections 4.1 and 4.2, respectively.
The general formulation of the l + 1-th layer of spectral GNNs is X(l+1) = σ(g(Ã)X(l)W (l+1)), here σ is an activation function, X(l) is the output of the l-th layer, X(0) is a feature matrix and W (l+1) is a learnable transformation matrix. We call X(l)W (l+1) the input of g(Ã) in l + 1-th layer and denote X as the input of g(Ã) in the last layer. In the following sections, we discuss the prediction error of spectral GNNs with a given graph filter without activation function before prediction. That is, in the last layer with X as input, g(Ã)X is directly used for prediction. Definition 4.1 (Prediction error). Let X ∈ Rn×K be the input of graph filter g(Ã), Y ∈ Rn×K is the label matrix, the prediction error is formulated by:
Er(g,X) =∥ g(Ã)X − Y ∥2F= tr(X⊤g2(Ã)X)− 2tr(X⊤g(Ã)Y )+ ∥ Y ∥2F (3) Remark 2. For a label vector yl, we denote Er(g,xl) =∥ g(Ã)xl − yl ∥2F as the error of g(Ã) predicting class l. Obviously, Er(g,X) = ∑ l∈T Er(g,xl), where xl is the l-th column of X .
In particular, we will apply our conclusion to specified filters and make concrete analysis. Definition 4.2. With ϵ ∈ [0, ϵ0] and ϵ′ ∈ [−1, 1], ϵ0 is a small constant, we define low-pass filters gl(ϵ)(Ã), high-pass filters gh(ϵ)(Ã) and band-pass filters gb(ϵ′)(Ã) as:
gl(ϵ)(Ã) = ϵI + Ã, gh(ϵ)(Ã) = ϵI − Ã, gb(ϵ′)(Ã) = I − (1 + |ϵ′|)−2(ϵ′I − Ã)2.
For λ, an eigenvalue of L̃, we have gl(ϵ)(λ) ∈ [ϵ− 1, 1+ ϵ], gh(ϵ)(λ) ∈ [ϵ− 1, 1+ ϵ] and gb(ϵ′)(λ) ∈ [0, 1] since λ ∈ [0, 2]. Particularly, gl(0) is the GCN filter.

heading: 4.1 HOW INPUT MATTERS
text: Denote X̃ = U⊤X = (x̃0, . . . , x̃K−1) and Ỹ = U⊤Y = (ỹ0, . . . , ỹK−1), where U is a matrix with unit eigenvectors of L̃ (recall that eigenvectors of Ã are consistent with that of L̃), revisiting Er(g,xl) and Er(g,yl) in spectral domain, we have:
Er(g,xl) = ∥ g(I − Λ)x̃l − ỹl ∥2F= ∑ i (g(1− λi)αi − γi)2 (4)
Er(g,yl) = ∑ i γ2(1− g(1− λi))2 = Rl ∑ i pi(1− g(1− λi))2 = RlE[1− g(1− fl)]2 (5)
where Λ is the eigenvalue matrix of L̃, αi and γi are the spectra of xl and yl respectively, pi = Pr(fl = λi), fl is the frequency of yl. For better comparison, we normalize the input xl: ∥ xl ∥2F=∥ yl ∥2F , i.e., ∑ α2i = ∑ γ2i . g is re-scaled function with g([0, 2]) concentrating in [−1, 1].
How input information matter? With normalized feature and graph filters, it indicates that the performance of graph filters greatly depends on label spectra. Particularly, when the frequency response of a graph filter does not fit the label frequency, it might be inferior to all-pass filters, such as MLP. On the other hand, it poses a principle of filter design: make feature response of filters be consistent with the main frequency band of label frequency as much as possible. In terms of input information, it determines the performance of a filter - if the frequency distribution of input vector is far from that of label vector, even an ideal filter would fail. This observation is identical to our assumption in Section 3.4 - information of label vector is all we need and the distance between frequency distribution of input and label vectors reflects its usefulness. Therefore, Er(g,yl) is the lower bound of Er(g,xl) when g(Ã) are given. While an input vector may be useful for distinguishing one class, it may be helpless for another. In most GNNs, they tune the frequency distribution of features with a learnable linear transformation to generate a more informative input.
Here, we discuss the Er(g,yl) of three types of filters: Er(gl(ϵ),yl)/Rl = Var(fl − ϵ) + E[fl − ϵ]2 = Var(fl) + (E[fl]− ϵ)2 (6) Er(gh(ϵ),yl)/Rl = Var(2− fl − ϵ) + E[2− fl − ϵ]2 = Var(fl) + (E[fl] + ϵ− 2)2 (7)
Er(gb(ϵ′),yl)/Rl ≈ (E[fl] + ϵ′ − 1)4 + 6Var(fl)(E[fl] + ϵ′ − 1)2 + 8(1− ϵ′)Var(fl)E[fl]
(1 + |ϵ′|)4 . (8)
where we use Var(f2l ) ≈ 4E[fl]2Var(fl) derived from the delta method. Discussion. An interesting observation is that for a class with high dispersive spectrum, efforts of any single filters are to no avail. From Corollary 3.3, we know that E[fl] = 1−π̃l and Var(fl) = π̃2l −(π̃l)2. It demonstrates that higher homophily means lower E[fl], lower Var(fl), and also lower prediction error for low-pass filters. On the other hand, we indicate that, in most cases, band-pass filters are more powerful than low-pass filters, let alone high-pass filters. However, the prediction capacity of a signal filter is very limited when the means of spectra vary widely.

heading: 4.2 HOW STRUCTURE MATTERS
text: Above, we catch a glimpse of spectral explanation of the behavior of graph filters. Below, we expand more understanding of graph filters. Assume that with learnable transformation, GNNs enable to generate an informative input. Here we discuss the prediction error of different graph filters under the optimal input Y . We revisit Er(g,yl) using symmetric interaction matrix and propose a lower bound er(g,yl) leveraging Proposition 3.1:
Er(g,yl) = y ⊤ l (I − g(Ã))2yl = Rl(I − 2g̃(Π̃) + g̃2(Π̃))ll ≥ er(g,yl) = Rl(I − g̃(Π̃)ll)2. (9)
How structural information matters? We indicate that, in the spatial point of view, graph filters can be interpreted as weight-tuning mechanisms on edges. The lower bound clearly demonstrates that a graph filter would have unsatisfactory prediction accuracy if it fails to make the homophily degree of the tuned graph large enough (g[Π̃]ll are far from 1).
Applying the prediction error lower bound to aforementioned specified filters, we have:
er(gl(ϵ),yl) = (1− π̃l − ϵ)2Rl; er(gh(ϵ),yl) = (1 + π̃l − ϵ)2Rl (10) er(gb(ϵ′),yl) = (1 + |ϵ′|)−4Rl(ϵ′2 − 2ϵ′π̃l + π̃2l )2 ≥ (1 + |ϵ′|)−4Rl(ϵ′ − π̃l)4. (11)
Discussion. These error bounds indicate that: 1. a low-pass filter would fail on classes with low homophily degree - in turn, it confirms that the importance of homophily assumption for low-pass filters like GCN - it is identical with our spectral point of view; 2. high-pass filters have poor performances particularly on the high homophily graphs; 3. for a graph whose classes have consistent homophily degree (their self-interaction probabilities concentrate around a constant ϵ̄), gb(ϵ̄) would work better than others. However, it is predictable that any single filters would fail on graphs with diverse self-interaction probabilities.

heading: 5 MODEL AND EMPIRICAL STUDY
text: Our theoretical analysis of graph information demonstrates that: 1. when node classes have inconsistent homophily degree or their label frequency distribution are far from each other, a single graph filter is prone to fail; 2. in most cases, band-pass filters would perform better than low-pass and high-pass filters; 3. a feature may contribute to the classification of one class but hinder the discrimination of another. Inspired by these, we propose a disentangled multi band-pass filter framework (DEMUF) which can be applied to any type of graphs no matter what kinds of graph information they have. The key point of our model is to learn multi band-pass filters which are used to capture different disentangled feature information respectively.

heading: 5.1 ARCHITECTURE OF TWO FRAMEWORKS OF DEMUF
text: Our framework includes feature disentanglement and frequency filtering. As we have emphasized the limitations of single filters, it is natural to leverage multi graph filters. Theoretically, piling up sufficient numbers of graph filters to capture all the frequency components can improve prediction performance. However, it is very expensive. To avoid this problem, we consider feature disentanglement - essentially, it is to disentangle frequency distributions of features into different families. Features in the same family are expected to have similar spectral properties, that is, they have similar frequency distributions or have overlap on their main frequency bands. Then for each family, we apply
a band-pass graph filter to capture their main frequency components. We propose two frameworks with different structures of filters: Plain-DEMUF and Tree-DEMUF (depicted in Fig. 1).
The DISENTANGLE block and FILTER block are formulated as follows: Xk = DISENTANGLE(X,Φk) = Φk(X), Hk = FILTER ( Xk, ϵk, hk ) = (gb(ϵk)) hkXk. (12)
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 band-pass filter defined in Definition 4.2, i.e., gb(ϵ) = I − (1 + |ϵ|)−2(Ã − ϵI)2 as the identical filter form. Here, ϵ is the parameter of filter constrained in [−1, 1] noting that 1− ϵ is the center of frequency response gb(ϵ). In each FILTER block, h is the number of layers. The framework of Plain-DEMUF with N graph filters is:
H = MLP ( CONCAT ({ FILTER ( DISENTANGLE ( X,Φk ) , ϵk, hk ) , ωk ∣∣∣k = 1, . . . , N})). Based on this, we implement a simple model called P-DEMUF. Precisely, we leverage a GUMBEL_SOFTMAX to generate N learnable masks {M1, . . . ,MN} for feature sampling at once followed by different MLP. That is, Φk(X) = MLPk(X ⊙Mk). Similarly, we develop a model, T-DEMUF, under the framework of Tree-DEMUF formulated by:
H1, X1 = FILTER {( DISENTANGLE ( X,Φ1 ) , ϵ, h ) , ( DISENTANGLE ( X,Ψ1 ) , ϵ1, h1 )} Hk+1, Xk+1 = {( DISENTANGLE ( Xk,Φk ) ,FILTER ( DISENTANGLE ( Xk,Ψk ) , ϵk, hk
)} H = MLP ( CONCAT ({ ωkHk, k = 1, . . . , N })) .
In each T-DEMUF layer, we use GUMBEL_SOFTMAX with different parameters to generate two masks Mk and M ′k and Φk(Xk) = Xk ⊙ Mk and Ψk(Xk) = Xk ⊙ M ′k. In each layer, we stop further disentangling of the branch of Hk by utilizing an additional constraint L(Xk−1, Hk) =∥ Xk−1 ⊙M ′k −Hk ∥22. Noting that Hk = (gb(ϵk))hkXk−1 ⊙M ′k, this constraint is to make the main frequency bands of Hk be consistent with frequency response of (gb(ϵk)) hk .
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 efficiently and effectively. In addition, T-DEMUF uses an additional constraint to guide the filter learning process while P-DEMUF is a combination of multi graph neural networks which would not interfere with each other. Therefore, P-DEMUF is likely to obtain similar filters and require more filters to improve performance than T-DEMUF. The model visualization results in Fig. 2 validate this statement.

heading: 5.2 EXPERIMENTS
text: 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.

heading: 5.2.1 EXPERIMENT SETTINGS
text: Datasets. 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. For all data, we use 60% nodes for training, 20% for validation and 20% for testing. To intuitively show the homophily degree of a dataset, we calculate the mean of self-interaction probability (diagonal of interaction probability matrix) and show it in Table 1. This metric is similar to the node homophily in (Pei et al., 2020). More statistics of datasets can be found in Appendix A.
Baselines. We compare our models with four spectral GNNs: GCN (Kipf & Welling, 2017), ChebNet (Defferrard et al., 2016), GIN (Xu et al., 2019) (despite a spatial GNN, we can easily get its spectral form), ARMA (Bianchi et al., 2021). We list their spectral filter forms in Appendix A. In short, GCN is a well-known low-pass filter. The filter shape of GIN depends on its parameter ϵ. In this paper, we fix ϵ = 0.3 and thus it is also a low-pass filter. ChebNet and ARMA are high-order polynomial filters. In addition, we also add three spatial GNNs (whose spectral forms are hardly analyzed): GAT (Veličković et al., 2018), FAGCN (Bo et al., 2021), Geom_GCN (Pei et al., 2020). Both GAT and FAGCN utilize attention mechanism and FAGCN takes high frequency information into account. Geom_GCN is a novel aggregation method based on the geometry of graph (it is related because it was also empirically studied on graphs with different levels of homophily (Pei et al., 2020)). Finally, we also compare with MLP, a baseline without using any graph information.
Experimental Setup. 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 32 over all datasets. The number of filters are searched between 2 to 10, and the final setting is: for T-DEMUF, we use 4 filters with 7 layers for Citation networks, 2 filters with 15 layers for all WebKB and Wikipedia networks, 5 filters with 1 layer for Actor. The numbers of MLP layers are 2, 2, 3 and 4, respectively. P-DEMUF uses: 3 filters with 8 layers for Citation networks; 5 filters for Cornell, 4 filters for Wisconsin and 3 filters for Texas - all of them are 1 layer; 7 filters with 9 layers for WebKB; 5 filters with 2 layers for Actor. P-DEMUF applies 2-layer MLP to all benchmarks. 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).

heading: 5.3 RESULT AND ANALYSIS
text: The experimental results are summarized in Table 1. Our models consistently outperform baselines over most benchmarks with significant improvement. On Cora and Citeseer, the datasets with a high level of homophily, our models are only comparable to GCN and other baselines. However, on all other datasets with a lower level of homophily, our models both obtained great performance gain.
To understand the impact of graph homophily on different types of graph filters, let us analyze the performance of all spectral GNNs. On high-homophily datasets, all GNNs perform similarly and the accuracy is much higher than MLP. That means the graph structure information is extremely useful in this case. However, on low-homophily datasets, many of them are even worse than MLP. GCN and GIN, the two low-pass filter based models, perform worst. The two GNNs with high-order graph filters, ChebNet and ARMA, are clearly superior to other models due to their higher spectrum coverage. However, they cannot beat our models with specially designed multiple filters. The
reason might be that the high complexity of their filters makes it more difficult to learn one optimal single filter. Finally, our model T-DEMUF yields over 18% higher accuracy than the best baselines (Geom_GCN) on Squirrel; and P-DEMUF yields almost 10% higher accuracy than MLP on Texas
In addition, we select some typical datasets and show the frequency distribution on these graphs in Fig. 2. We can obviously see that on Cora the spectrum is focused on low frequency components. This can explain why the low-pass filter based models can also perform well on it. On other datasets, the frequency distribution is more diverse, so the low-pass filters can not match with the important frequency components anymore. In contrast, both of our models, T-DEMUF and P-DEMUF, learn graph filters corresponding well to those components (as shown in the last two rows of Fig. 2). TDEMUF uses fewer number of (more dispersed) filters but achieves comparable or better performance.

heading: 6 CONCLUSION
text: In this paper, we propose a theoretical analysis of graph information with the introduction of interaction probability and frequency distribution. We develop a deep understanding of how different structures and input influence the performance of graph filters. We also design a simple framework to learn a filter bank. Empirical results on extensive datasets validate the power of our model.

heading: A BENCHMARKS AND MODEL DISCUSSION

heading: A.1 STATISTICS INFORMATION OF BENCHMARKS.
text: We provide statistics information of our benchmarks in Table. A.1.

heading: A.2 SPECTRAL FILTERS.
text: In our paper, we use four spectral GNN as baselines whose spectral filters are listed as Table.A.2 and define a band-pass filter gb(ϵ) as a quadratic function with respect to the adjacency matrix.
Since gb(ϵ)(Ã) = I−(1+ |ϵ′|)−2(ϵI−Ã)2 = (1+ |ϵ|)−2((1+ |ϵ|−ϵ)I+A)((1+ |ϵ|+ϵ)I−A), it is exactly an overlap between a low-pass filter (1+|ϵ|−ϵ)I+A) and a high-pass filter ((1+|ϵ|+ϵ)I−A). That is why gb(ϵ) is a band-pass filter.

heading: A.3 MODEL DISCUSSION.

heading: A.3.1 MOTIVATION OF DISENTANGLEMENT.
text: Overlap if not disentangled. Without disentanglement, it is highly possible that the learned filters have large overlaps if we do not induce any constraints on them. In our algorithm, we aim to train filters to capture the main frequency information of their input and assign different weights to that captured information depending on how much they contribute to label prediction. Therefore, it is natural to assume that if the input of filters is different, filters are less likely to overlap. Disentanglement can make the “input” different and more adaptable to each filter.
Disentanglement reduces the model complexity. With disentanglement, we divide node features into several subsets by learnable masking or map them into several low-dimensional spaces through linear transformations which lowers the dimension of corresponding features for each filter and meanwhile makes the input feature fits better to each filter.

heading: A.3.2 MOTIVATION OF T-DEMUF.
text: As we clarified in Section 5.1, 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. With a constraint L(Xk−1, Hk) =∥ Xk−1 ⊙M ′k −Hk ∥22, for each subset of features we train a band-pass filter to through their main frequency. As shown in Figure.2, this constraint guides the process of filter learning which can help reduce the overlap of filters’ frequency responses such that can reduce the number of graph filters. At the same time, to minimize the supervised loss, maskings are trained to disentangle features whose frequency distribution are similar to those of labels and assign a higher weight; those useless captured feature information will be assigned a lower weight. Weights are also learnable.

heading: A.3.3 HOW CAN OUR FILTER BANK SELECTION BE DATA-DRIVEN.
text: In our algorithm, although the form of our band-pass filter gb(ϵ) 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.

heading: A.4 MORE EXPERIMENTAL RESULTS.

heading: A.4.1 ADDITIONAL BASELINE - GPRGNN.
text: Here we compare our models with a related baseline GPRGNN(Chien et al., 2021). It is worth noting that the splitting in our paper is different from that in GPRGNN. In GPRGNN, its training set consists of the same number of nodes from each class while we just randomly choose our training data. We find that WebKB datasets are sensitive to the way of splitting due to their uneven distribution of labels ( the numbers of classes are: Cornell and Texas: 33/1/18/101/30, Wisconsin: 10/70/118/32/21). Although GPRGNN’s splitting is likely better for model training, our model still outperforms it in the Wikipedia datasets, i.e., Chameleon and Squirrel. In GPRGNN’s setting, the performances of MLP on WebKB are comparable to GPRGNNs’ while in our setting, our proposed models’ performances are much better than MLPs’. We also test T-DEMUF on Actor, Cornell, and Texas following the splitting of GPRGNN. As shown in Table.A.4.1, in most of the benchmarks, our model performs better than GPRGNN.

heading: A.4.2 ABLATION STUDY.
text: 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.2 validate that if we take off the disentanglement blocks of P-DEMUF, the results become worse in most of benchmarks.

heading: B PROOF OF PROPOSITION
text: Here, we provide the proof of Proposition 3.2. Proof. Since x = n−1∑ i=0 αiui, ui is the i-th unit eigenvector of L̃ and λn = u⊤i L̃ nui then we have
E[fn] = n−1∑ i=0 P (f = λi)λ n i = ∑ (αiui) ⊤L̃n(αiui)∑ α2i = x⊤L̃nx x⊤x = x⊤(I − Ã)nx x⊤x . (13)
Below is the proof of Proposition 3.1.
Proof. For P = D−1A and Ã = D− 1 2AD− 1 2 , and Π, Π̃ defined by Definition 3.1, the inequality can be represented as (RΠk +(Πk)⊤R)lm ≥ 2(R 1 2 Π̃kR 1 2 )lm which is equivalent to prove y⊤m(P k + (P k)⊤)yl ≥ 2y⊤mÃkyl. Noting that, (P k)⊤ = DP kD−1 and Ãk = D 1 2P kD− 1 2 , with B = P k + (P k)⊤, we have Bij = P kij + di dj P kij ≥ 2 √ di dj P kij = 2Ã k ij . Therefore, y ⊤ m(B − 2Ãk)yl ≥ 0. Let m = l, then we get πkl ≥ π̃kl .
To prove proposition b, we utilize lemma B.1. Since g(Ã) is symmetric, then we have
(g2[Π̃])ll = y⊤(g(Ã))2y
y⊤y ≥ (y⊤g(Ã)y y⊤y )2 = (g[Π̃]ll) 2.
Lemma B.1. Let B ∈ Rn×n is a symmetric matrix, ∀ij, y ∈ Rn, we have
y⊤B2y
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 Proposition 3.2, we obtain that y ⊤B2y y⊤y
= ∑ (αiλi) 2∑
α2i and
( y⊤By y⊤y )2 =
( ∑
α2iλi) 2 ( ∑ α2i ) 2 . From Hölder’s inequality, we have (
∑ (αiλi) 2)( ∑ α2i ) ≥ ( ∑ α2iλi) 2. Therefore, we
have ∑ (αiλi) 2∑
α2i ≥ (
∑ α2iλi) 2
( ∑ α2i ) 2 .

Review summaries:
This paper studies the applications of graph filters in graph neural networks, and attempts to understand the links between graph spectral analysis, random walks, and homophily. The authors introduce "interaction probability" as a metric for understanding homophily and its relationship to random walk transition matrices. In this framework, the authors claim to understand a notion of graph information, as well as an understanding of how the performance of graph filters depends on both graph structure and input signals, with applications to graph neural networks.

It is observed that for Graph Neural Networks (GNNs), the correlation between the labels and the graph structure matters. The paper gives a theoretical analysis of this behavior via interaction probability and frequency distribution. The analysis shows why homophily is favorable for GNNs. Additionally, they are also able to identify some conditions when GNNs can do well. But the key point made is that it is not possible to cater to all possible scenarios with a single filter. The paper further goes to propose a model that builds multiple band-pass filters over the range of [-1, 1] and then aggregates information over these filters to give improved performance.

The paper presents an insightful analysis of the induced graph filters in GNNs. To accommodate the heterogeneity of graphs, the authors provide a family of novel GNNs for learning data-specific filter banks. Overall, the introduction part is well written, and the studied problem is novel and interesting. However, the technical part of this paper has some issues: (1) the contributions of this paper are over-claimed, (2) the theoretical analysis and algorithm are disconnected, (3) mistakes in the theoretical results.