Graph Information Matters: Understanding Graph Filters from Interaction Probability
Authors: Zhixian Chen
Tengfei Ma
Yang Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: Node classification
graph filters
homophily degree
interaction probability
frequency distribution
filter bank
spectral graph neural networks

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 filter 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.

Under review as a conference paper at ICLR 2022
GRAPH INFORMATION MATTERS: UNDERSTANDING GRAPH FILTERS FROM INTERACTION PROBABILITY
Anonymous authors Paper under double-bling review
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 understand graph filters, it is unclear how particular graph affects the performance of different filters. In this paper, we carry out 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 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 general strategy for exploring 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.
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, c.g. explaining the behavior of various GNNs in node classification. NNt & Machara 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. (22TT) empirically revealed the weakness of GNNs with only low- lo-pass filters in certain datasets. These contradictory views on low-pass filters pose a significant problem: Why does filter work on one dataset but not on another? More precisely, for 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. necessary to take into account graph information, including the graph structure. features, and labels.
Existing theoretical research is mostly restricted 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 tion 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 variety of graph filters in heuristic manner under suppressed homophily assumption, i.c., nodes with similar attributes/labels tend to have connections. There remains a paucity of quantitative description of homophily until Pei al. (2020) designed rough index to measure
clear that structural and feature informa-
In this paper, we establish a comprehensive theoretical analysis of the effect of structure and feature information 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 distributional representation of input information the

---

Under review as a conference paper at ICLR 2022
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 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 graph filter under two settings: a. fixed graph structure, unravel the inftuence 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 data-driven filter design principle. In addition, 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, is hard 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 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.
apply these
Our main contributions are: We develop a theoretical analysis of graph information based on the introduction of interaction probability and frequency distribution; 2. We provide deep understanding of the performance of graph filters illustrating how graph structure and input information matter; 3. We indicate the weakness of GNNs with single graph filter and propose general framework to leam a data- speci-- filter bank which contributes to significant improvement.
2 RELATED WORK
In this paper, we focus on the analysis of graph filters in the context of graph neural networks. Since Bruna et al. (014) defined spectral graph filters and extended convolutional operations to graphs, various spectral graph neural networks have been developed. For example, ChebNet (Defferrard et al.) (016) 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). [ianchi et al. (202T) proposed the rational reto-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) ct al. 2020). By bridging the gap between spatial and spectral graph neural networks, Balcilar Balciaa 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 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 this paper, there are some other heuristic metrics for homophily. Pei et al. (2020) defined node homophily index to characterize their datascts and help explain their experimental results for Geom_ GCN: 3 1 homophily ratio instead and identified set of key designs that can boost learning from the graph
#nodes E. #neighbors of o that have the same label as Zhu et al. (2020) defined edge #neighbors
2

---

Under review as a conference paper at ICLR 2022
structure in heterophily: h #edges whose end nodes have sume labels This edge homophily definition is #edge sensitive the number of classes and size of each class, and Lim al. (202T) made modification to alleviate this problem. Our work differentiates from these works in that we not only use our definition characterize the graph but also directly relate the performance of graph filters (or GNNs).
3 THEORETICAL ANALYSIS OF GRAPH INFORMATION
3.1 NOTATION
Let Gn = (Vn: En) be an undirected graph with additional self-connection, where V2 {Uo...., vn-1) is the set of nodes and en C Vn Vn is the set of edges. Let A E Raxx be the adjacency matrix and matrix with D3 = E, Ai. we denote Ā = D AD- then i. Dー = Ā is the symmetric normalized Laplacian. Let (Ag, u,) be pair of eigenvalue and unit eigenvector of L, where 0 = X S ... S An-1 2.
D - A be the Laplacian matrix, where D is a diagonal degree
3.2 PROBLEM SETTING
In this paper, we are mainly interested in node classification problems on undirected graphs. Given Gn (Vn, E,), we consider T [(O.... K - as the set of all node labels. For A4 E T. we denote C& as the set nodes with label and R E KxXK as a size matrix which a diagonal matrix with R2= |C&l. Considering single-label problems in which classes
mutually exclusive, hot encoding to indicate the class label and introduce a label matrix Y E R=*K = (K-1) to represent the labels of Vn. where yk is the indicator vector of C.. Obviously, R Y
one-
Y 1 diag( R) and Y1 = 1. signal x on Gn can be arranged the signal values in a vector form Particularly, labels {yulk E T are also graph signals.
(zo,... (Zo.-..;;a
In-1) (...))..
3.3 A STRUCTURE INDICATOR INTERACTION PROBABILITY
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 random walk on Gn. we denote P = D-'A as its transition matrix which is also row Markov matrix. From the random walk theory, p& is the k-step transition matrix, and pk the probability that a random walker starting from node v; arrives at U after k steps. For node and class C, we denote o (Ct) as the probability that random walker starting from stays in Ct at the k-th step. It is trivial that ग (C.) Ejec, pk with ΣieT (Ct) = 1. T (C:) demonstrates the relative prefereence/loseeness of node u; for Cj with k-scale. To meet the homophily assumption, for v; in C,, T (C.) is expected gap away from others. Since (C,) - Emptt म (Cm) 2n (C,) - 1, o (C,) can be regarded as a measure of the k-scale homophily degree of node v;. Particularly, for vk E N and v; E Ci, ア. (C,) = means that C is a community and will never communicate with other classes. However, this case is rare in real graphs. Below, we investigate the homophily of class and propose method to measure the communication strength between two classes.
Definition 3.1 (k-step interaction probability). For I, m T, we define II as the k-step interaction probability matrix formulated as follows:
yJ Pkym
I
Σ
k (Cm)
Σ
pk
lm
R
R
y1 Y1
V.EC:
v.ECI CCm
& -Y phy R Ry pky.
(2)
1h is the probability that a random walker from C₁ arrives at Cn after k steps.
Remark 1. Obviously, I 1. H is the mean proportion of C. in the k-hop neigh- bors of nodes from C.. Noting that rank(Y)
K, when K A YR- 'y # I, thus (R-lyT) * * R y Thy,, ie. (II) * II.h. More generally, for an arbitrary polyno- mial function g. R- ((P) is likely not equal gR-1lyT TPk)). In the rest of paper,
3

---

Under review as a conference paper at ICLR 2022
write ((II) (PlYg((P)) and g(II) g(R-lYTphy) For instance, if g(-) (.)m. then g -1"h and (II) = (II).. Also, we denote Iīf the self- probability, as of for short.
1 ststep interaction probability intuitively reflects the degree of clustering of two classes and Σ i=1 IIo measures the strength of interaction between classes in the scale of ic steps. Since P is not symmetric, I1 * u 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 Ii by replacing P with Á = D- 3, we obtain I1 = R Y T A 2, Below, we investigate the important properties of 11 and ii
Proposition 3.1. For I, E T and an arbitrary polynomial function 9-). we have: R in + Rm ml 2 2 Rm I7A, Img where R₁ the 1-th diagonal element of R: b. (TT) 2 (((T) where g (TT) = R R g (A)YR=
The proof can be found in Appendix B Since 1 * 1. that is, the measure is no longer a probability measure. However, according to Prop 3.1 a let m 1) af is the lower bound of n/. and af n when G. is regular graph. In the rest of theoretical analysis, we use मे measure the degree of Ci's clustering. Let g(+) = (.)² from Prop 3.1 1.1g b, we have # 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 given filter.
3.4 A FEATURE INDICATOR FREQUENCY DISTRIBUTION
Following the graph signal processing (GSP) concepts, Ao.... Ap-1 are graph frequencies and ....., 11-1 are the corresponding frequency components which are invariant of graph filters. Through Fourier transform, we obtain {a, = (u, x).x O...................... 1-1] 1} the spectral representation of graph signal x, called graph signal spectrum. Moreover, graph signal can be represented as a linear combination of frequency components, i.e., Σ a, For label vector y, which is also graph signal, we denote : } 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, ///E: 7 reflects how much the frequency component u₃ contributes to the distinctiveness of C₁, without considering the positivity and negativity of effects. Interestingly, 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, random variable taking values in the set of graph frequencies with prohability Pr(f = Ax) = of Σ, of The probability describes the frequency distribution of signal
With this definition, we derive distributional representations of signals from their spectral representa- tions/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 show how graph structure influences signal frequency.
(1-AX)x
Proposition 3.2. For G = E),E), let f be the frequency of signal x, then E[f"]
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 's frequency.
Corollary 3.3. For label frequency f of yı. we have E[T]] = (g(1 - (i)) with g = (.)a.
Recall that ii) R (1 A we have = म.. E = 1 2 + of =
and the variance of f/: Var(f:) = #7 2 It can be seen that both the mean and variance of label frequency are close to when म, approaches 1, which reflects high homophily degree (as ग. S कı < 1). In Section [.]] we conduct a more detailed analysis of feature information of spectral space with frequency distribution.
ANALYSIS OF GRAPH FILTERS
graph filter is defined a function y with applied Laplacian matrix or adjacency matrix. Denote R Á) as polynomial ring in Á over IR, here we mainly interested in g E RR(A). In this section,
4

---

Under review as a conference paper at ICLR 2022
provide 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 concern:: with fixed graph structure, how does the input impact the performance of 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 + 1-th layer of spectral GNNs is X(++)) (
here a is an activation function, (1) is the output of the I-th layer, X is feature matrix and W(+ is learnable transformation matrix. We call X x(++1) the imput of g()) in I + 1-th layer and denote X as the input of (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, (()) is directly used for prediction.
Definition 4.1 (Prediction error). Let X E RT*K
K be the input of graph filter g(A), Y E Raak is the label matrix, the prediction error is formulated by:
Br(g, x) =I1 g(A)x Y 1 tr(X T (A)x)) 2tr(X T
9 (
(3)
Remark 2. For label vector yı, we denote Er(g, x1) -I1 I ((A)x Yt 11% as the error of g(A) predicting class l. Obviously, Er(g, X) = EieT Er(g, xI). where X/ is the 1-th column of X.
In particular, we will apply our conclusion to specified filters and make concrete analysis. Definition 4.2. With e [0, ea] and é' E [-1, 1]. eo is a small constant, we define low-pass filters (i(e) (A), high-pass filters ( and band-pass filters go(e') as:
(((e(() = =el + A, Iicee (A) = el - A, Dole)) (A) = 1 - (1+ (1+161)2('11 A)?.
For X, an eigenvalue of i., we have mi(e) (A) E [e - 1, + c). (A) E 1,1 1, + c) and Do(e)) (A) E
[0, 1] since À E [0, 2]. Particularly, Pu()) is the GCN filter.
4.1 How INPUT MATTERS
Denote X U = (xx))...xX.)) and Ý UTY (To. ........y. 5K-1),,, where U is a matrix
with unit eigenvectors of L. (recall that eigenvectors of Á are consistent with that of L), revisiting Er(g, x)) and Er(g, yi) in spectral domain, we have:
Er(g, x = 11 g -A) Yr 11 Σ(0(1 -1)aa, - 7;)²
(4)
Fr(g, = E - -1) R2 En<t pi -g(1- -xa))=== R 9(1 - [i)] (5)
where A the eigenvalue matrix of i., as and 7s are the spectra of x; and y, respectively, p: = Pr(fi A.). fi is the frequency of yı. For better comparison, normalize the input x/: x 113--1 y: 1/
i.., Σa² = Ena is re-scaled function with g(00, 2]) concentrating in [-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 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 y:) the lower bound of Er(g, x:) 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. y1) of three types of filters:
Gr(gu))yr)/BB = Var(fi - e) + Effi - e]² = Var(f) + (E[f) 2)²
(6)
Er(gh(e) Var(2 - fi E) E/2 fi c|² Var(f)) + (L][G) + E 2)²
5

---

Under review as a conference paper at ICLR 2022
Br(ghte).31)// [E]f.) 1)s + 6Va (F) + d 1)2 + 8(1 c')
Var Var E(]
(8)
(1+ |e')4
where we use Var(ff) 4 [ Var(ft) 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 [[ = 1- and Var(f:) = म. ) It demonstrates that higher homophily means lower Effi]. lower Var(fi), and also lower prediction error for low-pass filters. On the other hand, we indicate that, in most cases, band-pase pass filters are more powerful than low-pass filters, let alone high-pas pass filters. However, the prediction capacity of signal filter is very limited when the means of spectra vary widely.
4.2 How STRUCTURE MATTERS
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. yi) using symmetric interaction matrix and propose a lower bound er(g. v1) leveraging Proposition 3.1
Fr(g. vi) = yi (T (T- (()) Ri(T 20((T) + (2((1)) 2 er(g, R2 - g(T)))² (9)
How structural information matters? We indicate that, in the spatial point of view, graph filters can be interpreted as reight-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(a(c) v1) = (1 ग - -)) Ra; er(an()) y1) = + मं - =) er( y1) (1
(10)
- 2e + m)) 2 (1 + 1e'l) 1e'))=+R((e - #T)
(11)
Discussion. These error bounds indicate that: 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 graph whose classes have consistent homophily degree (their self-interaction probabilities concentrate around a constant E) Io(2) would work better than others. However, it is predictable that any single filters would fail graphs with diverse self-interaction probabilities.
5 MODEL AND EMPIRICAL STUDY
Our theoretical analysis of graph information demonstrates that: when node classes have inconsis- tent homophily degree their label frequency distribution are far from each other, a single graph filter is prone to fail; 2. in most cases, sand-pass filters would perform better than low-pass and high-pass filters; 3. feature may contribute 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 be applied 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.
5.1 ARCHITECTURE OF TWO FRAMEWORKS DEMUF
Our framework includes feature disentanglement and frequency filtering. As we have emphasized the limitations single filters, it is natural to leverage multi graph filters. Theoretically, piling up sufficient numbers of graph filters capture all the frequency components can improve prediction performance. However, it is very expensive. To avoid this problem, we consider feature disentan- glement- 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 have overlap their main frequency bands. Then for each family, we apply

---

Under review as a conference paper at ICLR 2022
DE
F2
D.
FM
DE,
stufll
Mggff
MLP
MLP
DISENTANGLE BLOCK & FILTER BLOCK
Plain-DEMUF
DEMUF
Figure Illustration of Plain-DEMUF and Tree-DEMUF. There are two main model blocks of DEMUF frameworks: disentangle block and filter block. In parallel as their disentangled input are generated through single disentangle block at the same time. Differently, each Tree-DEMUF layer contains two branches will be disentangled into two branches of the next layer after going through a filter.
all filter blocks run in
is early stopped while the other
band-pass pass graph filter to capture their main frequency components, We propose two frameworks with different structures of filters: Plain-DEMUF and Tree-DEMUS (depicted in Fig. 1
band
The DISENTANGLE block and FILTER block are formulated as follows:
X₁ DISENTANGLE(X. 2x) 4xx H₃ FILTER (xx, Ek, Exg (gb(ea)) )he Xx. (12)
In our implementation, we provide two samples of DISENTANGLE functions 4g one is linear transformations, the other is GUMBEL SOFTMAX (Jang et al. (017) used to generate learnable masks for feature selection. In terms of the FILTER block, we use band-pass filter defined in Definition 4.2 i.e., 9b(e) = (1 + [c) - cJ)² as the identical filter form. Here, c is the parameter of filter constrained in [-1, 1] noting that 1 e is the center of frequency response Pb(e). In each FILTER block, h is the number of layers. The framework of Main-DEMUU with N graph filters is:
H MIL.(ONNCAC
FILTER (DISENTANGLE (x, 0x) ck. N1s we
x)))
Based on this, we implement simple model called P-DEMUF. Precisely, we leverage GUM- HEL_SOFTMAX to generate N learnable masks [M1....,MN Mr) for feature sampling at once followed by different MLP. That is, (X) = (X @ MR).
Similarly, we develop a model, T-DEMUF, under the framework of Tree-DEMUF formulated by:
H1, X1 FILTER
DISENTANGLE X (1, (DISENTANGLE X, X,, ..)).EL,.) 11),
H&41, Xk+1 (DISENTANGLE Xk. (ILLE))FILTER DISENTANGLE (KR, V/s Wx).ckk hx
= W...M (Wr (WiH k -I,..,,,,,, =l,...,N))).
In each T-DEMUF layer, we use GUMBEL GUMBEI_SOFTMAX SOFTMAX with different parameters to generate two masks Mj and My and (Xx) further disentangling of the branch of H4 by utilizing an additional constraint L(Xx-1, Hy) =Il Xk-1 C Mi. Hx 1 Noting that Hs (Ab(c)))* X Mt. this constraint make the main frequency bands of H2 consistent with frequency response of (M
X2 Mr and (Xx)))) = Xx C My. In each layer, stop
Model discussion. Compared with filter-bank learning methods which directly apply array of filters to features, our models use subsets of features. It can greatly reduce the amount 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 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. validate this statement.

---

Under review as a conference paper at ICLR 2022
5.2 EXPERIMENTS
To validate DEMUF, we compare the performances of P-DEMUF and T-DEMUF with that of spectral GNNs, spatial GNNs and MI.P on extensive datasets.
5.2.1 EXPERIMENT SETTINGS
Datasets. We use four types of real datasets- Citation network, WebKB, Actor co-occurtence 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. 202I) are two Wikipedia networks with web pages nodes and links between pages as edges. The nodes originally have five classes while [B et al. (2021) proposed new classification criteria which divides nodes into three main categories. In this paper, the relabeled networks are called Chameleon2 and Squirre12. Actor (Tang et al. 2009) is a subgraph of the wwt---diieccoo-ctooo-wweee
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 dataset, we calculate the mean of self-interaction probability (diagonal of interaction probability matrix) and show it in Table [ This metric is similar the node homophily (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 201
ChebNet (Defferrard et al.) (016)). GIN (Xu 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 a well-known low-pass filter. The filter shape of GIN depends on its parameter 6. In this paper, we fix 0.3 and thus it is also a low-pass filter. ChebNet and ARMA are high-ordet polynomial filters. In addition, we also add three spatial GNNs (whose spectral forms are hardly analyzed): GAT (Veličković et al.) 2018), FAGCN (Bo 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 novel aggregation method based 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, 3 and 4, respectively. P- P-DEMUF uses: 3 filters with 8 layers for Citation networks; 5 filters for Cornell, filters for Wisconsin and 3 filters for Texas all of them are 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).
5.3 RESULT AND ANALYSIS
The experimental results are summarized in Table 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, 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 hwmophlyyhl 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
8

---

Under review as a conference paper at ICLR 2022
Table 1: Node classification accuracy. The first row the mean of self-interaction probability.
Cora
Cite.
Coreell
Texas
Wisc.
Cham.
Squi.
Cham.2
Squi.2
Actor
#mean-n,
0.861
0.809
0.436
0.356
0.413
0.338
0.290
0.516
0.425
0.393
GCN
88.5
76.2
54.05
57.84
51.37
41.23
27.95
66.93
57.12
28.05
Spectral
Cheb.
88.21
76.26
80.00
78.38
78.43
51.71
36.52
75.44
66.11
35.76
GIN
87.06
74.1
55.68
52.97
49.02
36.58
23.73
44.74
52.22
26.30
ARMA
87.56
74.86
71.35
75.68
73.29
52.54
36.56
76.14
66.78
35.27
Spatial
GAT
88.32
76.85
55.14
61.08
54.51
47.46
32.66
70.92
61.42
29.32
FAGCN
89.19
77.15
73.51
65,41
76.86
49.82
33.68
74.47
65.86
34.61
Geom GCN
85.27
77.9
60.81
67.57
64.12
60.90
38.14
73.20
63.30
31.63
MLP
75.33
71.4
80.00
80.00
84.31
49.56
34.89
77.28
63.19
36.38
T-DEMUF
86.72
74.57
86.15
87.83
85.31
69.52
56.47
81.89
70.66
37.53
Ours
P-DEMUF
87.85
75.69
86.49
89.73
89.68
69.46
56.45
79.17
68.87
37.68
11.34
12.21
16.49
19.73
14.37
18.62
118.33
14.61
13.88
11.30
Cora
Wis.com
Squiimal
Squirmel2
Actio
6:21
7:34
0:24
0.6
3.03
2-32
0-32
0.30
0.00
1420
0.54
0.00
3.0
1,38
1.50
300
0.5
1.00
3.50
800
0500
1.00
1.5
8.00
336
1.6
3.50
0.08
0.53
3.00
3.0
Visualizations of interaction probability matrix and frequency distribution five datasets here and filters (b(1-)) learnt by P-DEMUF and T-DEMUF, where the thickness of curve reflects its weight w. It shows that frequency responses of our filters are consistent with labels frequency.
Figure 2:
reason might be that the high complexity their filters makes 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, select some typical datasets and show the frequency distribution these graphs in Fig. [ 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 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 those components (as shown in the last two rows of Fig. 2 T- DEMUF uses fewer number of (more dispersed) filters achieves comparable or better performance.
CONCLUSION
In this paper, we propose a theoretical analysis of graph information with the introduction of interaction probability and frequency distribution. We develop deep understanding of how different structures and input influence the performance of graph filters. We also design simple framework to learn filter bank. Empirical results extensive datasets validate the power of our model.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power graph neural networks in spectral perspective. In International Conference on Learning Representations, 2020.
Filippo Maria Bianchi, Danicle Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Thirty-Fifthh AAAI Conference on Artificial Intelligence, pp. 3950-3957, 2021.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks graphs. In International Conference on Learning Representations, 2014.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network. arXiv preprint WwXiv:2003.07450 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL [RRLitttts:///perreeet
het/fee fooummiddn66117220
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp.
2016.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In International Conference on Learning Representations, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. arXiv preprint arXiv:2 104.04400 2021.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. In Advances Neural Information Processing Systems, 2020.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint htt.::99500095555 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Antonio Ortega, Pascal Frossard, Jelena Kovacevie, José M. F. Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 106(5):808-828, 2018. doi: 1..109//PROC..20122222200 URL https::/dci. org /10 wtt.g///1111110/PP.. 2018 2820126
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Newworks, 9(2), 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad. Collective classification in network data. A/ Magazine, 29(3):93-93, 2008.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 807-816, 2009.
10

---

Under review as a conference paper at ICLR 2022
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference Learning Representations. 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
A BENCHMARKS AND MODEL. DISCUSSION
A.1
STATISTICS INFORMATION BENCHMARKS.
We provide statistics information of our benchmarks in Table. A.1
Table 2: Datasets statistics.
Dataset
Cora
Cite.
Cornell
Texas
Wisc.
Cham.
Squi.
Cham.2
Squi.2
Actor
Nodes
2708
3327
183
183
251
2277
5201
2277
5201
7600
Edges
5429
4732
309
499
36101
217073
36101
217073
33544
Features
1433
3703
1703
1703
1703
2325
2089
2325
2089
931
Classes
7
6
5
5
5
5
5
3
3
5
A.2 SPECTRAL FILTERS.
In our paper, we use four spectral GNN as baselines whose spectral filters are listed as Table A.2 and define band-pass filter Ib(c) as a quadratic function with respect the adjacency matrix.
Table 3: Spectral filters.
Model
Filter
GCN
Ā A (T +
GIN
C(s) 20(2) -(()))) ((o-2);
ChebNet
( 2L/Amar - 11 =1
ARMA Ours
(I Ex -
km-0 Pk L.
I- (1 (e)) 22 ell=
Since ( (A) = 1-1 AA² -1--01000000 -A))
exactly an overlap between low-pass filter (I+}c]-e)[+A) and high-pass filter (ett|e(+e//AAA That is why (e) is band-pass filter.
A.3 MODEL DISCUSSION.
A.3.1 MOTIVATION OF DISENTANGLEMENT
Overlap not disentangled. Without disentanglement, it is highly possible that the learned filters have large overlaps if we do not induce any constraints 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 Therefore, it is natural to assume that if the input of filters is different, filters are less likely to overlap. Disentanglement make the "input" different and more adaptable to each filter.
how much they contribute to label prediction.
11

---

Under review as a conference paper at ICLR 2022
Disentanglement reduces the model complexity. With disentanglement, 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.
A.3.2 MOTIVATION OF T-DEMUF.
As we clarified in Section 5.1, our implementation of disentanglement learnabee masking leveraging GUMBEL-SOFTMAX, These learnable maskings disentangle node features into several subsets of features. With a constraint c( H&) =|| x ④ M Hs ll.. for each subset of features we train band-pas pass filter to through their main frequency. As shown in Figure 2] this constraint guides the process 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 higher weight; those useless captured feature information will be assigned a lower weight. Weights are also learnable.
random masking but
A.3.3 How CAN OUR FILTER BANK SELECTION BE DATA DRIVEN.
In our algorithm, although the form of our band pass filter gc(c) is predefined, its parameters including c and weight w 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 MORE EXPERIMENTAL RESULTS.
A.4.1 ADDITIONAL. BASELINE GPRGNN.
Here we compare our models with related baseline GPRGNN(Chien et al. 2021). It is worth noting that the splitting in our paper different from that GPRGNN. In GPRGNN, 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: Coreell and Texas: 33/1/18/ 8/101/30 Wisconsin: 10/70/118/32/21 Although GPRGNN's splitting is likely better for model training, our model still outperforms 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 much better than MIPs'.. - We also test T-DEMUF Actor, Cornell, and Texas following the splitting of GPRGNN, As shown in Table A.4.] in most of the benchmarks, our model performs better than GPRGNN.
Table 4: Node classification accuracy of P-DEMUF and GPRGNN.
Different Splitting
GPRGNN Splitting
Dataset
Cham.
Squi.
Cornell
texas
actor
GPRGNN
69.52
49.93
91.36
92.92
39.30
T-DEMUF
67.48
56.47
91.26
92.79
41.11
12.04
6.54
10.1
10.13
1..1
A.4.2 ABLATION STUDY.
To show the advantage of using disentanglement, we provide 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, simply fix the number of filters 2. The results shown Table A.4.2] validate that if we take off the disentanglement blocks of P-DEMUF, the results become worse in most of benchmarks.
12

---

Under review as a conference paper at ICLR 2022
Table 5: Node classification accuracy of P-DEMUF and its ablation models. We fix the number of band-pass filters as 2.
Dataset P-DEMUF
Cornell
Texas
Cham.
Squi.
Actor
81.08
85.14
68.46
55.45
36.95
P-DEMUF (w/o masking
80.00
84.86
67.20
53.54
37.20
P-DEMUF (w/o masking & linear)
77.30
86.49
62.5
44.19
36.71
B
PROOF OF PROPOSITION
Here, we provide the proof of Proposition 3.2
Proof. Since x
auu; u, the i-th unit eigenvector of i. and X" uu i,"u, then we have
P(f = 1AA Σ(auu)) ( (aa(u)))
x xLxx
x T A)
B
Σ
(13)
x
0=0
Below is the proof Proposition 3.1
Proof. For P D-1A and À = D AD- 1 and II, defined by Definition 3.1 the inequality
can be represented as (RIT* + (TT*) R)mm 2 2 + R$ )t which is equivalent to prove y (P&
(PK)TT Jyi 2 Ty Noting that, (Pk)T =DP*D* D- and A p D 3, with B pk (P+)T, we have Bij PH + di
J, Ph 2 / p+ 2 Therefore, y (B 2d* yyr 2 0.
Let m then get क. #
To prove proposition b, we utilize lemma B.1
Since g(A) is symmetric, then we have
(g ii y (o(())) yTy 2 (y y A(A)))² (g(TT))
Lemma B.1. Let B Raxn is symmetric matrix, Vij. y R", we have
y Bay
By 2
2
y
y yTy
Proof. Since B is symmetric, then we have B = UAUT, T here U matrix unit eigenvectors
of B. From the proof of Proposition 3.2 we obtain that
y B²y y Σaf and y By
( Ea? aa)) From Hölder's inequality, we have (E(a:A))) af) V E { Therefore, we
have (o,A)) 2 ( (
13


Reviews:
[{"review_id": "lXBAq_LgjFx", "reviewer": "Reviewer_nP66", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and clear to understand.\n\n## Strengths:\n1. The theoretical analysis looks clean and simple. Equation 6, 7, 8, 9 and 10 provide a good indication of how the prediction error is dependent on pi_l. It also gives insight into the homophily requirements for good performance.\n2. The proposed model is simple and gives good performance on datasets of varying homophily scores.\n\n## Weaknesses:\n1. The error analysis is done on MSE rather than Softmax (which I suspect is what is used in the experiments). However, this doesn't take away much from the presented work and the analysis still feels insightful enough.\n2. The motivation for disentanglement block is unclear. The paper states *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.* While it is clear that it will be difficult to have large number of band-pass filters, it is unclear how disentanglement of features work to avoid this scenario.\n3. Implementation of disentanglement seems to be just random masking. How does it satisfy the statement made *Features in the same family are expected to have similar spectral properties* ?\n4. The motivation for P-DEMUF is pretty clear, but the T-DEMUF architecture motivation is not clear and there is no mention of it anywhere. Also, the equations of T-DEMUF are somewhat confusing. It feels like there might be a typo there, at least by looking at Figure 1.\n5. GPRGNN by [Chien et. al] is missing from baseline comparison.\n\nIn light of the above, I am inclined to rate this paper marginally below threshold. \n\nThere are few typos in the paper:\n1. Var(f_l) in Section 3.4 and in other places it appears has a mistake.\n2. Equations for T-DEMUF likely have a typo in there.\n\n**References:**\n\nEli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. ICLR, 2021.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is well-written and clear to understand. Theoretical analysis is clean, simple and gives interesting insights. The results are also very strong with good improvements on several datasets. However, there are several weaknesses in the paper A] the motivation for the disentanglement block is unclear B] it is also unclear how simple random masking achieves disentaglement C] The motivation for T-DEMUF is unclear as well and D] a very related baseline by [Chien et. al] is missing from comparison.\n\nIn light of the above, I am inclined to rate this paper marginally below threshold. \n\n**References:**\n\nEli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. ICLR, 2021.\n\n---\n\nUpdate post response phase:\nHaving gone through other reviews, it seems that there maybe a lack of clarity in the paper, particularly on the theoretical aspects. I admit it was a bit of an effort to keep up with all the notations and the paper will definitely strengthen by bringing in lot more clarity in notations. \n\nHaving said that, I would like to add that although the conclusion of the work may not be new, but new perspectives for the same conclusion should not be discouraged. In mathematics, we have multiple proofs for a single statement like \"There are infinite number of primes\" [A], each of them brings a new perspective and has something to offer. I believe that we would be doing a disservice if we rejected papers simply on the basis that conclusion is not new, without really analyzing if the paper is offering a newer fresh perspective or not.\n\nHowever, beyond these issues, I believe it is important to assess the actual model strengths as well. This is mostly where I find many things not so clear, for example, the feature disentanglement aspect is not clearly explained. Also, how does T-DEMUF work is not very well explained and what is the exact motivation for T-DEMUF is also quite lacking. \n\nIn light of these, I am inclined to retain my current assessment of marginally below acceptance threshold.\n\n[A] https://primes.utm.edu/notes/proofs/infinite/\n\n---\n\nUpdate post second response phase:\n\nThe authors have addressed all my issues. However, the outcome is the following:\n1. The notations have to be improved in the paper\n2. Explanation and motivation for disentanglement has to be added to the paper\n3. Explanation and motivation for T-DEMUF has to be added to the paper.\n\nHowever, I believe these should not be difficult changes to make and hence I am willing to change my rating to marginally above acceptance threshold, under the assumption that the authors would make these changes in the final revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "VO2NNu2pRxR", "reviewer": "Reviewer_kKsu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper suffers on many fronts.\nI wish I could give a more thorough review of this work, but the writing is so poor that assessing the merits of this work would be quite difficult.\nThe authors make many statements with very little explanation.\nFor instance, Proposition 3.1 is largely a jumble of symbols with very little surrounding discussion: it is not explained why I should remotely care about this result.\nSection 3.4 states things that are largely obvious from a graph signal processing perspective.\nDefinition 4.1 is a strange way to look at prediction error: why are you using a Frobenius norm to evaluate the error of a node classificiation problem?\nThe conclusions reached in Section 4.1 are quite obvious and well-understood in the broad literature.\nOf course filters should \"match the true signal,\" this is the most basic fact from signal processing!\n\nThe conclusion that graph neural networks should use a filter bank rather than a single filter is nothing new.\nSee, for instance, the work \"Stability Properties of Graph Neural Networks\" from Gama et. al. (2020).\n\nOverall, the contributions of this paper are extremely lacking.\nAnd even if there was a notable contribution of this work, the writing quality obscures it so much for it to be at all useful.\nI would also like to point out that the authors failed to cite even the most widely-known introductory papers for graph signal processing, such as that of Ortega et. al. (2018).\nThe failure of the authors to do so indicates a severe lack of familiarity with the graph signal processing literature, which this paper claims to contribute to.", "summary_of_the_paper": "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.\nThe authors introduce \"interaction probability\" as a metric for understanding homophily and its relationship to random walk transition matrices.\nIn 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.", "summary_of_the_review": "This paper does not live up to its claims, and is extremely poorly written.\nThe authors spent most of their effort on this work stating obvious things in convoluted ways, amounting to very limited statements regarding graph filters.\nDespite their claims of reaching \"deep understanding\" of graph filters, this paper achieves very little.\nDue to the poor writing and shallow application of this work, I strongly recommend this paper be rejected.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7cXxhmAHPBU", "reviewer": "Reviewer_RH1y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here are the detailed comments:\n\n[Problem] Very nice introduction and literature review. The problem is novel and interesting.\n\n[Notation] The notation set shall be largely simplified. For example, y_i, c_m, r_i all refer to the node labels. \n\n[Typos] There are typos throughout this paper. For example, missing space in the 9th line of Sec 3.3; in Sec 3.4, graph frequency -> graph frequencies? For {\\alpha_i = <u_i, x>}_i, why does the index i appear in both the inside and the outside of the parentheses?\n\n[Theoretical Analysis] In sec 3.3, the authors claimed that \\phi_i^k = \\sum P_{i,j}^k is the probability that a random walker starting from v_i and stays in C_l. Based on my understanding, \\phi_i^k does not exclude the case that the random walk traverse outside of C_l. Same in the Def. of interaction probability. Does the interaction probability also consider the case that random walk traverse to some other communities (different from l and m)? If so, please provide the justifications - what is the motivation and rationale of these formulations. \n\n[Proposition 3.1] There lack of insightful discussions about Proposition 3.1. What are the physical meanings of g(\\Phi) and g[\\Phi]? What does Proposition 3.1 tell us? And, what is the connection between Proposition 3.1 to the proposed algorithms?\n\n[Confusiong Notions] In Def. 3.2, what do you mean about the distributional representation? The authors may want to provide further explanation. In Proposition 3.2, \"f be the frequency of signal x\" --> \"f be the frequency distribution of signal x\"?\n\n[Over-calimed Contribution] (1) The low-pass/high-pass filters seem very similar to \"Beyond Low-frequency Information in Graph Convolutional Networks\". Moreover, the authors shall provide theoretical proofs to show why the g_b is a band-pass filter. (2) The authors claimed that this paper provides a \"data-driven\" mechanism for filter bank selection, which is not well described in the algorithm description. (3) the theoretical analysis and algorithm feel disconnected. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "The studied problem of this paper is interesting, while there may exist some issues in the theoretical foundation of the proposed algorithm. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, in order to theoretically investigate the relationship between graph structure and labels in GNNs, interaction probabity and frequency indicators are introduced and analyzed, and a new family of GNNs with multiple filters is proposed based on the insights from the theoretical analysis,
In the discussion, there was an opinion that the theoretical analysis is interesting, but its novelty and clarity are limited. Although certain contributions are acknowledged, the impact is marginal and the audience for which this paper will matter is rather limited.
Decision: Reject