Node-oriented Spectral Filtering for Graph Neural Networks
Authors: Shuai Zheng
Zhizhe Liu
Zhenfeng Zhu
Youru Li
Yao Zhao
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Graph Neural Networks
Node-oriented Spectral Filtering
Homophily Assumption

Abstract: Graph neural networks (GNNs) have shown remarkable performance on homophilic graph data while being far less impressive when handling non-homophilic graph data due to the inherent low-pass filtering property of GNNs. In general, since the real-world graphs are often a complex mixture of diverse subgraph patterns, learning a universal spectral filter on the graph from the global perspective as in most current works may still be difficult to adapt to the variation of local patterns. On the basis of the theoretical analysis of local patterns, we rethink the existing spectral filtering methods and propose the \underline{N}ode-oriented spectral \underline{F}iltering for Graph Neural Network (namely NFGNN). By estimating the node-oriented spectral filter for each node, NFGNN is provided with the capability of precise local node positioning via the generalized translated operator, thus adaptive discriminating the variations of local homophily patterns. Furthermore, the utilization of re-parameterization brings a trade-off between global consistency and local sensibility for learning the node-oriented spectral filters. Meanwhile, we theoretically analyze the localization property of NFGNN, demonstrating that the signal after adaptive filtering is still positioned around the corresponding node. Extensive experimental results demonstrate that the proposed NFGNN achieves more favorable performance.

Node-oriented Spectral Filtering for Graph Neural Networks
Anonymous Author(s)
Affiliation Address email
Abstract
Graph neural networks (GNNs) have shown remarkable performance on homophilic graph data while being far less impressive when handling non non-homen non-homophilic graph data due to the inherent low-pass filtering property of GNNs. In general, since the real-world graphs are often a complex mixture of diverse subgraph patterns, learning universal spectral filter on the graph from the global perspective in most current works may still be difficult to adapt to the variation of local patterns. On the basis of the theoretical analysis of local patterns, rethink the existing spectral filtering methods and propose the Node-oriented spectral Filtering for Graph Neural Network (namely NFGNN). By estimating the node- oriented spectral filter for each node, NEGNN is provided with the capability of precise local node positioning via the generalized translated operator, thus adaptive discriminating the variations of local homophily patterns. Furthermore, the utilization of re-parameterizatioon brings trade-off between global consistency and local sensibility for learning the node-oriented spectral filters. Meanwhile, theoretically analyze the localization property of NEGNN, demonstrating that the signal after adaptive filtering is still positioned around the corresponding node. Extensive experimental results demonstrate that the proposed NEGNN achieves more favorable performance.
2
6
10
12
14
18
17
18
Introduction
19
20 As powerful tool for analyzing graph data, GNNs are attracting considerable attention from both
21 academia and industry. Meanwhile, GNNs have also demonstrated remarkable capabilities in
22 number of graph-related applications, including but limited recommendation system [14] 40).
23 disease prediction (27 17], drug discovery 36 9], and action recognition 42 33
In the field of graph machine learning, homophily has always remained common assumption 25 39), i.e., nodes within the same class tend to connect with each other. However, behind the great critical limitation doesn't hold true in many 27 graph-related scenario, which inhibits severely the further extension of GNNs to more general graph
25
success of the previous efforts, such assumption
28 data. As mater of fact, it is hard argue that homophily is inherent characteristic of graph
29 data [55 and there are also a considerable number of non-homophilic graphs in real-world, where the
30 links usually exist between nodes from different classes. For example, protein structural networks,
31 connections between different types of amino acids are casier to form [8]; in addition, for an air
32 traffic network, the establishment of the air routes is more for commercial reasons and has little to do
33 with the activities of airports (29
As far the existing GNNs concerned, most of them usually adopt message passing architecture in
35 the spatial domain to aggregate the node feature from neighbors over the given topology structure [3 Obviously, the practice that all neighbor nodes considered contribute positively to
36
10 20
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

300
PM
2122
Hararrty Adds
(a) Cora
(b) Citeseer
(c) Cornell
(d) Actor
Figure 1: The statistical histogram of hN, (v) and 2N (v) of four real-world graphs, where Cora
and Citeseer are known as the graphs with strong homophily, Cornell and Actor are known as the graphs with strong heterophily.
37 node aggregation without distinction does not apply to heterogeneous graphs. Besides, the commonly adopted message passing architectures have been proven to exhibit significant low-pass filtering properties 2 41]. which is quite contrary to the non-low-pase properties of non-homophilic graphs. In order to break the homophily limitation, several recent studies have made some exploratory efforts 40
38
39
41 to solve the GNN modeling problem with non-homophily graphs. such as exploring some new aggregation schemes 445
42
12 44 and high-pass spectral filtering 4 46). However, these methods are still designed for specific heterophilic graph and lack of good scalability to homophilic graph. Actually, whether a graph homophilic or heterophilic depends on the relatedness of the downstream
43
44
45
task to the graph construction. It means that for fixed topology structure, when combined with different downstream tasks, the identification of its graph property will be very different. Taking the dating network as example, people are more likely to date someone who are opposite sex and about the same age. this case, the graph is likely to be heterophilic if we use the gender of the node as the label, while it may be homophilic if we the age group of the node as the label. Therefore, from the perspective of practical application, a simple yet effective GNN model that can be adaptively applied to graphs with mixed structural properties should be more preferred.
46
47
48
50
51
52 Moreover, GNN also confronts with another follow-on challenge, i.e., the homophily property is in general not consistent across the whole graph. In a real-world graph, there are always diverse subgraph patterns among different regions [37]. As shown in Fig [ a network seems like homophily may also contain a small amount of randomness or heterophily. Although the universality of GNNs has been taken into consideration in 6 [3 through adaptive spectral filter learning, the global filter modeling without focus on the variation of local structural pattern may still be suboptimal for the graph that is mixed up of more complex homophilic and heterophilic property. Besides, the relation re-imtimation based methods [24. 37 16 28 have shown some advance addressing the issue of the mixing pattern to a certain extent. In these approaches, different measures of node similarity are defined to perform potential neighborhood discovery, whereas the design of similarity measure and the high complexity that comes with it makes them less concise and flexible.
53
54
56
57
58
60
61
62
63
In this paper, we first analyze the local mixing patterns in the graph via the label consistency of the node neighborhoods. A theoretical justification is also given to analyze why the existing near-neighborhhood aggregation mechanisms fail to work for the non-homophily graphs. Further, inspired by the generalized translated operator in graph signal processing (GSP), we propose a novel GNN (namely NFGNN) from the perspective of spectral filtering to achieve adaptive localized graph spectral filter learning. The key idea is to estimate the node-oriented filter for cach node to solve the issue of varied local patterns in the graph. To be specific, we first apply the translated operator to center the spectral filter at each node, and then the K-order polynomial is used to approximate the optimal filter to be learned at each node. In addition, low-rank approximation based re- parameterization is used to decompose the filter weight matrix to node-agnostic and node-
64
65
66
68
70
71
72
73 dependent matrices, improving the fiexibility of the model. It also brings trade-off between global
74 and local perspectives. Meanwhile, we theoretically prove that the filtered signal is localized around
75 the corresponding node, demonstrating that NFGNN achieves the adaptive localized filtering. Finally,
76 an extensive group of experiments on various real-world datasets with different scales verifies that the proposed NFGNN achieves more favorable performance.
77
78 2 Preliminaries
79 Notations. An undirected graph is denoted as G = (V,E), where V {m:) denotes the set of nodes with |V] and E is the set of edges among nodes. The topology structure of graph G
2

---

81
could be described by the adjacency matrix A E R with At, = 1 1f (1,j) E E or O otherwise, and D the diagonal degree matrix D with its i-th diagonal entry D,, En=E; Acj. Besides, we use Σ,
82
L I- D-1/2AD-177 to denote the symmetric normalized Laplacian matrix of G and I is the
89
84
identity matrix.
85
For each node E V. we denote its neighborhood by using N(v), and further, the i-hop neighbors (v) and the neighbors within i-hops Nv((v) of node v by Nu(v) {m m E V dg (v. m) i} and [e( = {m m E V A dg(v, m) S i}, respectively, where dg(i.)) is the shortest path distance between two nodes and j on graph G. Besides, let x = [x11.... ".,," _nn'' E TK" denote the n-dimensional signal defined on the given graph G, where 2; denotes the signal response (feature) at the i-th node V/- Generally, when each node receives f channels of signals, we will have 90
86
87
86
89
91
X,]" E Rnxs with each column of it being a graph signal 92 x and its i-th row X, E R representing f- dimensional feature vector associated with node 2
a feature matrix X [
Furthermore, for the node classification task, each node E V has class label yo 3 = {1, -1. C}. where y is the set of class labels with [ = C, and C' is the number of classes. In addition, we use
94
95 Yo E RC denote the one-hot vector corresponding ye-
96
Graph Fourier Transform. According to graph signal processing theory, the graph Laplacian provides an effective way of spectral analysis on graphs. Given the Laplacian matrix L, it can be eigendecomposed into UAU",, where U = [ui, ... Ut .... un] E Rnxa is the graph Fourier basis formed by orthonormal eigenvectors {w and A diag/(A,."
96
99
An] E B is the diagonal matrix of the ordered eigenvalues {Ar) A E 2). Notice that {Mr]==1 is also identified as the frequencies of the graph. Thus, the graph Fourier transform of the signal is defined as
....... A
100
x = U" x, and (Ax) indicates the response of x at the frequency Ar. The inverse graph Fourier
102
transform is defined as x UR (34). Thus, on the basis of the graph Fourier transform, the signal filtered by g can be given as follows:
104
Σ (01) UgUxx
105
where g (A) diaglg(A)). ((x)...... [Am,)] is the spectral filter and we have g = Ug.
108
Since the spectral filtering is equivalent to convolution in the spatial domain (26). Eq. c also
107
be defined as the spectral graph convolution z = x &g g, where #g denotes the graph convolution operator.
108
3
Motivations
110
3.1 Adaptability to Mixing Local Structural Patterns
To measure the homophily of a graph, both edge homophily ratio 45 and node homophily ratio [28] are two widely used metrics. In addition, (23) proposed a more comprehensive homophily metric that mitigates homogeneity bias from class imbalance. It is less sensitive to the number of classes and size of each class than edge homophily ratio and node homophily ratio. Since we aim to analyze the local patterns of the graph via the label consistency of the node neighborhoods, the node homophily ratio 116 is adopted in this work. It should be noticed that the edge homophily ratio and the node homophily ratio have similar qualitative behavior (II] In particular, the node homophily ratio Hg of the graph
112
114
118
G is defined as the average of the homophilic 1-hop neighbor ratio of each node e in G and given by:
Hg
1 Σ (N) M
(v) = MV
Σ PEV
Im E NN) Vm = yn
[v)
NEV
119 where f (v) denotes the homophilic 1- 1-hop neighbor ratio of node e centered at node v.
120 In essence, Hg provides an overall evaluation criterion for homophily of graph. Instead, we should also cast more insight into the variation of local structural pattern. Particularly, we first give vi- sualization of the statistical histogram of hx, (v) and hwea (c). As shown in Fig [ even in Cora
121
122
Unless otherwise stated, only x E IR" is considered as the input of GNNs for convenience of presentation. the following discussions of this work still apply to X E xf with f channels of signals (i.e., f -imennsional features).
3

---

123
and Citeseer network, which are usually considered as homophilic graphs, there still exist small number of completely 1-hop heterophilic subgraphs. Similarly, there are some subgraphs with a high homophily ratio in Cornell and Actor network. Obviously, these ohservations mean that, for graph with complex topological structure, it is definitely a mixture of homophilic and heterophilic local subgraphs. Furthermore, for the two heterophily graphs, we can find that the statistical histogram of hN (v) is much different from that of hN, (v), demonstrating that the associated local subgraph patterns for each node varied generally with the change of neighborhood range.
124
125
126
127
128
130
Based on the above analysis on the variation of local structural pattern, it motivates us to consider that it is conducting adaptive modeling for the graph nodes with different degree of homophily is a necessity, and further, we should improve the effectiveness of GNNs for the nodes with various local structural patterns.
131
132
133
134
3.2
Aggregatability of Near-neighbors
To facilitate the discussion of the aggregatability of near-neighbors, we first give two definitions about the neighborhood. i.e., heterophily-
136
and homophily-preferred,
137
Definition 3.1. For node with label Yo. (u)) is expected to be heterophily- if P(ym =
Ye Vo) S P(ym # YolWo), Vm E (N)).. Conversely, N(v) is expected be comophily-prefereee
138
139
Intuitively, the near-neighbor aggregation is definitely effective when the near near-neighbor subgraph is completely homophilic, while it may not capture adequate homophilic information when the neighborhood is expectedly eeterophily-preferrdd that the aggregation of expectedly comophhlyy-prfferee neighborhoods is also beneficial to the node representation. Classical GNNs [19 38 10] commonly suffer from the over- smoothing problem and
141
According to Definition 3.1 it can be inferred
143
144
are thus limited to shallow networks, which means that each node just aggregates the information about its neighbors within 2 or 3-hops. Thus, whether the near-neighborhhod is homophily-preffcee or hhteerohiiy-preffemm
145
148
will be of great importance for them. To empirically analyze the preference of near-neighborhood, we first propose a label entropy SN₂ (v) to measure the neighbor label distribution of node u, which is defined as:
147
148
|N! (v)
(V (o)
(v) E(
DEY [N:(O] + e)og(
[N(O +s)
(3)
where N.()(()) {m: Ne(1) ym = v) and 10- is a constant to avoid overflow. Clearly, the larger the label entropy SN, (v) is, the more random the neighbor label distribution of o will most nodes in the homophily graphs have low Sv, (v) and most nodes in the heterophily graphs have high SN₂ (v). Besides, for all four graphs, the statistical histogram of
149
150
be. As shown in Fig 2
151
152
153
SN is shifted to the right overall compared to SN, (v). These observations suggest that the
154
neighbor label distribution of each node tends to be uniform as the neighborhood range increases.
155
Combined with the definition 3.1 we can conclude that the neighbor based aggregation is not the optimal solution for heterophily graphs
156
1760
2105
2500
N.M
10
2%
00 04
63
54 10
(a) Cora
(b) Citescer
(c) Cornell
(d) Actor
Figure 2: The statistical histogram of SN, (v) and (wzz(o) of four real-world graphs.
157 Theoretically, we explore the preference of the 2-hop neighborhood N2(v) for multi-class node classification and have the following proposition:
158
159
Proposition 3.1. For each node v in graph G, let's assume the class labels of its neighbors (ym m E [(w) are conditionally independent when given you and P(ym = yo (y) = o, Vy + yv- Then, the 2-hop neighborhood (y) of node will always be P(um vluv) b.
160
162
expectedly heterophily-preferred if S 151-
2

---

163
For the proof of the above proposition 3.1 please refer to the supplemental materials.
Different from the statement that 2-hop neighbor aggregation could help GNNs to learn more effective node representation [45] 1. proposition 3.1 shows that the aggregation of N2 is hard to be beneficial for GNNs when the neighborhood label distribution tends to be uniform. This finding is also consistent with our empirical analysis mentioned above.
165
166
187
The Proposed NFGNN
168
189
The observations in Sect. Elpoints out that the real-world graph is often made up of a mixture of various local patterns, while the near-neighbor aggregation mechanism does not handle the heterophilic local patterns well. Various elaborately designed aggregation mechanisms in the spatial domain have been proposed to tackle these issues. Different from these methods based on spatial domain, spectral graph convolution aims to learn a specific spectral filter for a given graph structure and node labels, thus
170
171
172
178
174
preserving the appropriate frequency components for the downsteam tasks. Therefore, spectral graph convolution also possesses a strong expressive power [2] and can work well for both heterophily and homophily graphs. However, existing spectral-based methods are still not flexible enough. They usually estimate globally consistent filter from the perspective of the whole graph (20] 13 7 EJ, which may be inappropriate for some local patterns. In this section, we rethink the globally consistent spectral graph convolutions, and propose localized spectral filter learning method to break the limitation.
176
178
180
181
4.1
Polynomial Filter
182
directly eigendecompose the normalized Laplaciann matrix L obtain the Fourier basis U and treat the ğ as the trainable parameters. However, the expensive eigenvalue decomposition restricts the availability of these methods greatly. To circumvent the eigendecompooition, K-order polynomial approximation is adopted parameterize the spectral
Based on Eq [
early spectral GNNs 55 [5|
183
184
185
186
filter:
9(x))
A
(4)
k=
where "ik denotes the learnable fitting coefficient. By plugging Eq. can be rewritten as:
into [ the spectral filtering
188
K Σ 1==0
UgU x R
Σ **
U'x= =
x
(5)
189
Except for the reduced complexity, another advantage of the localization property. When the filter g centers at node vy, the value at node vy after filtering by g is
filter is the
190
equal to A== 7x (L*)a.)) Meanwhile, (L*) will be 0 if (i, > K M. The above facts show that the Koorder polynomial spectral filter is exactly localized in NeK(1)
191
192
193
Due to the high efficiency, various polynomial kernels are used for spectral filter parameterization, such as Chebyshev basis (7] and Bernstein basis (13. Interestingly, many spatial aggregation spectral convolution 20 3
194
185
methods can also be essentially attributed to
196
Nevertheless, such polynomial filters are still globally consistent, or node independent In other words, the filter is applied for all nodes with the fixed fitting coefficients {> that are trained on the whole graph, and makes no specific discrimination for each node when performing filtering. Thus, even it is localized, the polynomial-parameteriie parameterized spectral filters are still unable to effectively
2
197
198
199
200
model the complex local structural patterns with mixture of homophily and heterophily. Intuitively,
201
compared to learning a globally shared filter g(Ar) as a trade-off solution for different local patterns
202
across the whole graph, learning an appropriate node-specific filter ga for node i to fit the local
203
pattern where it is located seems to be a better choice.
K
9c(Ai)
(6)
R=0
For such practice, what needs to be figured out is how to learn å and ensure it is still positioned around node i. To this end, we introduce the node-oriented filtering.
205
2 The analysis of existing GNNs from spectral filtering perspective is provided in the supplemental materials.
5

---

208
4.2
Translated Filter for Node-oriented Filtering
207
Inspired by the generalized translation operator, we develop an adaptive localized spectral filtering
208
on graph G using the polynomial-paramml parameterized spectral convolution. It takes full into account the specific effect of the node where the filter is positioned.
209
210
Definition 4.1. Generalized translation operator) [34] For any signal g E I defined on a given
graph G and any i {0, 1,..... ,n m1-1, 1}, we define generalized translation operator T; .R" + R via generalized convolution with a Kronecker delta function ó; centered at the i-th node UA
212
Ta(g) = V=Tg)==N(g<+ 6,) = VV
Hnu (1)((A)
1=1
where uf (1) denotes the i-th element of uT.
213
214
Definition 4.1 shows that a signal could be centered at specific node through a kernelized operator
acting on g [44 Then, can perform the spectral convolution of signal with the filter signal g when g is centered at a specific node Uy:
216
X & T:(g) - VN (((())
(8)
):)r) VNu (1)( Eq.
becomes:
x & Tg
Σ (A)uuux Ug,
(9)
218
Recall the inverse graph Fourier transform, it can be derived that x; = U, where Ug indicates the i-th row of U. Hence, U; could also approximated from x; according to U, = Z;q, where (inv(X) E R is the pseudoinverse of x. Then, note that (1) = uz (i). it can be derived that 9e (Ar) ~ (A) (N(zzg) ((Ar))(AA), where qi denotes the (-th element of q. Therefore, gi can be approximated by a specific filter gi corresponding to node v; which also considers the impact from the feature x; associated with node ;; in estimating the filter weight.
219
220
222
224
Without loss of generality, the K-order polynomial approximation can be used to directly parameterize g: As traditionally used approximate kernel in GSP (7), the Chebyshev polynomial T& (-) are adopted to parameterize g. that is, g. = => x (A), where Á 2A/Amaz I. Meanwhile, for each node, we focus only on the convolution result of the filter positioned at that node, i.c.,
228
227
228 2. 8, (Ug, U x). here 6; [0, ... ...... O] R denotes row vector with only the i-th
229
element being and the remains being zeros. Thus, the node-oriented localized filtering can be as:
K
2, = o 6: 5,U EmmTTh(A) U
Σ A=
V S (L)x
(10)
where V = [m E m2x((+11 is the trainable coefficient matrix, L UÄUT Meanwhile, similar to the above discussion localized filter, have the following Propositior4.1 claim that the adaptively filtered signal z is also approximately positioned around the node i.
230
232
Proposition 4.1. Given signal defined on a graph G and filter T:(g) that translated to a given center node vú in G, the filtered signal z = x (g) is approximately localized around the node i.
234
235
To prove the proposition 4.1 let's first introduce the following Lemma 4.1
236
Lemma 4.1 (35)). Let PK be the polynomial approximation with degree K to the spectrum of graph
signal s,, i.e., ((Ac) Rs px = Ek N If dg (i, n) > K, then Te(T)n & T.(KK) = 0,
237
238
where рк denotes the signal corresponding to PK.
239
Proof. According to Definition
4.1 and the properties of convolution, we notice that z can he rewritten
z = x v [g * d.) v VN(( g) 6.) (x [[xx]]
(11)
241
Furthermore, let o x * g and Px be the polynomial approximation with degree K to G. From
242
Lemma 4.1 T2(p), R T.(KK),
will hold if di(i, > K. Then, have Zn TT(2),
243
()) K.
This completes the proof.

---

Algorithm 1 Node-oriented Spectral Filtering for GNNs
Input: X SER" R=xx R K
Output: Z
Learnable Parameters: W.T. W.T.C. W.T.O.
I: (0) (X),
X()) LX.
1at Feature Transformation
for = K
( <- 2LX (k-1)
X (k-2) i
for
= 1 to n do
Th.k H.1
H" oxx
Z: n (k)
ZZ
end for end for
245
4.3
The Implementation of NEGNN
According to the proposed adaptive localized filtering in Eg 10 we will further formalize the
247
20). the entanglement of feature transformation and filtering may be harmful to the performance and robustness of the GNN model. Hence, we adopt the similar way by first applying a MLP to perform the non-linear transformation for the raw feature matrix X. Then, the spectral filtering operation can be implemented by recursive way due to the stable recurrence relation of Tx):):
architecture of the proposed NFGNN. As pointed out in |4
249
251
(L) = 2LTx-1(L) -Tx-2(L)
(12)
252 Accordingly, given the input X, we will have ( = Tx (L)
253
Notice that, the scale of the trainable coefficient matrix V positive proportional to the number n of nodes. With the increase of n, this will inevitably involve learning large number of parameters. At the same time, the model also needs to learn K parameters for a single node, which is intractable to be optimized. In addition, learning such large number of parameters can also lead overfitting, especially in the case of small number of labels. To achieve parameter lightweight for V we use separable low-rank approximation to re- re-parameterize it. Specifically, decomposed into two trainable parameter matrices V = HI with 1i, = H, where H E Raxd
254
255
256
257
258
is assumed to be
259
and r E (xx(K11) are the node-dependent matrix and node-agnostic matrix, respectively. 260
261 As I' seen as node-agnostic, it can be directly trained as general parameters, which is very similar to the learning of the polynomial coefficients in [7]. But for H, since we treat it as node dependent, a simple yet effective nonlinear transformation (MLP) is applied, i.e., H oX ()), where W E /x xd
282
263
264
and (-) are the learnable weight matrix and activation function, respectively. is worthy of note that, through low-rank approximation based re- parameterizzaiin,, the parameter complexity of v is reduced from Onn x (K + 1)) to O((K + 1) x d f x d), and we can flexibly adjust the model capacity by changing d. Particularly, we set 1 in this work, and thus the node-agnostic matrix I [k is closely related to { in Eq. 6 We summarize the proposed node-oriented
265
286
267
268
269
filtering in Algorithm
5
Experimental Results and Analysis
270
271
5.1
Experimental Settings
272
Datasets.
To provide a comprehensive evaluation of our method, several graphs from various
domains with different homophily ratios are used, including 5 homophilic graphs: citation graphs Cora, CiteSeer, PubMed [31], and co-purchase graphs Computers and Photo [32] 5 heterophilic
273
274
graphs: Wikipedia graphs Chameleon and Squirrel [30] the Actor cooceurrence graph, and webpage graphs Texas and Cornell from WebKB 28
276
The statistics of these datasets are summarized in
supplemental materials.
278
Baselines. Several baselines have been selected for comparison, including methods that can be seen as spectral filtering based, GCN 19] SGC 41) ChebNet [7]. APPNP 20). GPRGNN [).
279
TTe source code for the implementation of NFGNN be seen in supplemental materials.
7

---

Table 1: Results real-world graphs: Mean accuracy (%) - 95% confidence interval. Boldface letters mark the best result, while underlined letters denote the second best result.
Cora
Ciesseer
PubMed
Computers
Photo
Chameleon
Actor
Squirel
Texas
Cornell
NEGNN
77.69:191
67.74:10.52
85,07:10.13
84.18:1040
92.16-082
72.5210.59
40.62:10.8
58 08.90
94.03:1082
01
BernNet
76.37-4036
65.83-40.61
62.57-4-0.17
79.57:40.8
91350-035
68.73+-0.7
40.01
50.75-0007
92.30+122
91.96=1077
GPRGNN
79.51:1.36
03.33
85.07:10.09
32
01293-026
67.48:1::00
39.30.10.7
49.93:2.55
92.92.101
91.36:10.0
APPNP
79.41-4038
68.59
85.02
81,99:0026
91.11=0226
51.9110056
38.86-1024
34.77
91.1810.00
90.80-0033
ChebNet
71.39:0.51
65.67400.8
83.83400.12
82,41
90.09=0.28
59,96::051
38.0240225
40.67=0.31
86.08
1..33=
SGC
70.81:0677
58.98:0447
82.09::0.11
76.27:2066
83.80=046
63.02::043
29.79::0:0
43.14=0.28
18.1111117
1.55
GCN
75.21
07.30
84,27:1:0001
82,52:20.32
90.54_0.21
00,96:1:0.7
30,59:10.33
45.66620.39
75.
16:19.99
66.72:11.7
LINKX
6..40:11.37
55.94:10.96
84.3331:000
73.64:1..7
1..84-1.21
69.971:0.1
39.22:10.22
58.31
90.33
8..36:11.00
BMOCN
74.07+00.25
64.34-00.22
84.71+00334
NA
NA
69.69+1121
NA
53.16::0.74
93.00--0.57
NA
FAGUN
78.10=00.11
66.77=0.18
84.09+40002
12. NA
90.39-1.54 NA
61.59+198
39.08:0.65
40.61
19.611152
88.52
GoomGCN
20.37
20. 0.090
18.20:11:23
61.06:2449
31.81
38 38.28:0027
58.56:11
15.59
GAT
76.70:10:2
67. 0.
83,28:10:1
81.95:10:8
90.09-0.21
63.9:0.66
35,9810233
42.72:10.33
18.87
76.00:1100
MLP
50,34440.48
$2.88 08-50.0155
80.574-0.12
70.48+0.28
78.69
46.72+0046
38.58+0025
31.28-0.27
92.26+00711
91,36+0,70
LINK
42.94:1..02
1.99
54.7811966
10.05:1131
18584-145
71.09:1.16
26.2511.43
19.77
19.61
44.91
639
645
107
$5000
Axtn?
(a) Cora
(b) Citeseer
(c) Cornell
(d) Actor
Figure 3: Mean classification accuracy of nodes range by homophily ratio Ni (v) on four datasets.
280
BernNet [3]. and 3 spatial aggregation based methods, GAT 338. G..Geeo-GGe GCN 28 BMGCN [I]
281
and non-GNN baselines, MLP, LINK (4), and LINKX (22. For GPRGNN, BernNet, and BMGCN,
we directly use the open-source codes released by the original paper. For the others, we use the models that are provided by (6).
283
284
Experimental Setup. For the node classification task, we follow the random split ratio in 6 to split sets. Specifically, The sparse splitting ratio (2.5% is used for homophilic graphs, and the dense splitting ratio (60%/2006/20%) is used for heterophilic graphs. We run each experiment 50 times with random initialization, and random data splits. Finally, we report the average results with a 95% confidence interval. We set the degree of the polynomial 10 for all datasets. The Adam [8] is employed as the optimizer for the NEGNN training. For GPRGNN, BernNet, and BMGCN, we use the best combination of hyperparameters provided in the
285
the dataset into vraining/valiaationn/
286
287
288
209
K-
291
original paper to report the results for each dataset
292
5.2
Performance Comparison
293
The average results of running 50 times on the node classification task are reported in Table where accuracy is used as the evaluation metric with 95% confidence interval. NFGNN outperforms all the baselines on datasets and achieves comparable results on the other 4 datasets. In particular, on Chameleon and Squirrel graphs, NFGNN outperforms the SOTA method BMGCN by large margin,
294
295
296
297
i... 2.83% and 5.03%, demonstrating the superiority of our method.
298
Meanwhile, it can be observed several interesting phenomena in Table T i) GCN and GAT are even inferior to MLP on some heterophilic graphs, which shows that positive near-neighbor aggregation is indeed out of power in some cases. Besides, the performance of MLP also shows that the utilization of node features is also very important for GNNs. ii) The filter-learing based methods generally have good performance on both the homophilic and heterophilic graphs, indicating that adaptive filter learning has better transferability than filter pre-designing.
299
300
301
352
303
304
5.3
Node-level Analysis
A motivation of the proposed NEGNN is to solve the mixed local patterns discussed in Sect. 3 Therefore, we divide the test nodes into 5 different intervals according to the homophilic 1-hop neighbor ratio hx, (1) and report the mean accuracy of each interval. The results of GCN, NEGNN
306
307
More detailed experimental settings are discussed in the supplementary material.
8

---

Table 2: Accuracy (%) improvement of the node-oriented filtering (NF).
Basis
Citeseer
Pubmed
Chameleon
Texas
w/a NF
78.15
66.60
82.28
61.79
38.88
91.80
Monomial
w/ NF
79.16
68.42
84.79
63.36
39.53
91.47
Improv.
(1.01)
(1.82)
(2,51)
(1.57)
(0.66)
(-0,33)
w/o NF
76.32
65.61
82.10
67.82
39.31
92.29
Bermstein
w/ NF
78.41
66.22
83.09
69.93
40.77
93,37
Improv.
(2.09)
(0.61)
(0.99)
12.11)
(1.46)
(1.08)
w/o
76.07
65.11
84.02
39.11
92.47
Chebyshev
w/ NF
77.69
67.74
85.07
72.52
40.62
94.03
Improv.
(0.62)
(2.63)
(1.05)
(4,04)
(1.51)
(1.56)
308
with only 7 (marked as NEGNN w/o NF) and NFGNN are shown in Fig 3 It should be noticed that the
NFGNN w/o NF is equivalent to learning a globally consistent filter using the Chebyshev polynomial. can be seen from Fig. ( and (d) that NFGNN has promising and similar performance on all five intervals, which shows that NFGNN can effectively capture the various local patterns under the condition as long as the amount of trainable data is sufficient. Besides, both NFGNN and NFGNN w/o NF perform better than GCN on the supervised node classification task, as shown in Fig. B a) and (b). It suggests that adaptive learning filters are no less expressive than pre-designed filters, even in the semi-supervised case.
310
312
314
316
5.4
Effectiveness of the Node-oriented Filtering
317
To evaluate the effectiveness of the proposed node-oriented filtering more comprehensively, we first compare the performance of NFGNN and NEGNN w/o NE. Further, since the node-oriented filtering is independent of the polynomial basis, the Chebyshev basis is replaced by the Monomial basis and Bernstein basis, respectively, and we check the improvement bring by the node-oriented filtering
318
319
320
mechanism for them. For the Bernstein basis, we refer to the implementation form given in [I3
321
322
The results on six graphs are summarized in in55.] Firstly, it can be seen that the globally consistent filters learned using three different bases have leading performance on different datasets, respectively, illustrating the effectiveness of using a polynomial approximation to learn filters. Furthermore,
323
324
325
except for the Monomial basis on Texas graph, the node-oriented filtering mechanism has different enhancements for each basis. The improvements not only validate the effectiveness of the proposed node-oriented filtering, but also demonstrate that the polynomial filter and the node-oriented filtering can each other to some extent.
326
328
329
6
Conclusion and Discussion
330
In this paper, we first analyze in depth the local patterns in graph data and the aggregatability of Near-neighbors. Motivated by these observations, we rethink the spectral-based GNNs and propose NFGNN for node-oriented spectral filtering via the generalized translated operator. Compared to previous methods that learn a global filter, NFGNN performs spectral filtering through filters translated on specific nodes to address the issue of local patterns. Through recursive form and re- parameterization trick, the oriented- filtteriggiiiigggg is implemented in a simple way. The experimental results on several real-world graph datasets verify that our NEGNN achieves more remarkable performance over currently available alternatives.
331
332
333
334
335
337
338
Studying spectral-basse -based GNNs in accordance with the idea of graph signal processing theory is one of the origins of GNNs. With different starting points, the spatial-designed GNNs aim to design the neighborhood aggregation mechanism based on the topological characteristics of the graph, focusing more on the local relationship between nodes and their neighbors. In contrast, spectral-based GNNs are dedicated to the design of the filtering of the graph signal in the spectral domain, analyzing the graph more from a global perspective. The proposed NFGNN in this paper provides a new form of trade-off off between global and local perspectives in the spectral domain. Particularly, NFGNN can be seen as a extension of the existing methods for estimating global filters. For spectral- -base GNNs, the scalability of spectral convolution and inductive learning setting are still key issues to be solved at present, and it still one of the directions of graph neural networks that can be expected because of the great transfcrability it exhibits.
339
340
341
342
343
344
345
347
9

---

References
349
350
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
352
354
[2] Muhammet Balcilar. Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In International Conference on Learning Representations, 2020.
355
356
357
[3] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE transactions on pattern analysis and machine intelligence, 2021.
359
360
[4] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, 2021.
362
383
[5] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1206303..2..... 2013.
384
365
[6] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
77] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
388
389
370
[8] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
371
372
[9] Thomas Gaudelet, Ben Day, Arian R Jamasb. Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al. Utilizing graph machine learning within drug discovery and development. Briefings in bioinformatics, bbbb)bbbb,, 2021.
373
375
376
[10] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proc. Adv. Neural Inf. Process. Syst., pages 1024-1034, 2017.
377
[1I] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(l::sss,0((::1))))))) 120 2011.
378
[12] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng. Block modeling 2021.
modeling-guided guided graph convolutional neural networks. arXiv preprint arXiv:2112.13500
381
383
[13] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 2021.
384
385
[14] Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pages 039-648,777 2020.
386
388
389
[15] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint 1506.050000000 2015.
390
391
[16] Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 34, 2021.
392
[17] Anees Kazi, Shayan Shekarforoush, S Arvind Krishna, Hendrik Burwinkel, et al. Inceptiongen: receptive field aware graph convolutional network for disease prediction. In Int, Conf. on Inf. Process. in Medical Imaging (IPMI), pages 73-85, 2019.
394
10

---

396
[18] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
397
398
[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 2016.
400
[00]
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997,, 2018.
401
402
[21] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.
403
[22] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non- con-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20901 2021.
406
408
[23] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2 2021.
[24] Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
411
412
[25] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
413
414
[26] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-828, 2018.
416
417
[27] Sarah Parisot, Sofia Ira Ktena, Enzo Ferrante, Matthew Lee, et al. Spectral graph convolutions for population-based disease prediction. In Proc. Ins. Conf. Med. Image Comput. -osputt-Assist. Intervent. (MICCAI), pages 177-185, 2017.
419
420
[28] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
421
422
[29] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figuciredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 385-394, 2017.
424
425
[30] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())xenab014, 2021.
426
427
[31]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
[32] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint /rXiv:1811.05886. 2018
430
431
[33] Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Two-stream adaptive graph convolutional networks for skeleton- based action recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 22026-1203. 2019.
432
433
[34] David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-99) 98, 2013.
435
437
[35] David I Shuman, Benjamin Ricaud, and Pierre Vandergheynst. Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis, 20(2):260-291, 2016.
438
[36] Mengying Sun, Sendong Zhao, Coryandar Gilvary, Olivier Elemento, Jiayu Zhou, and Fei Wang. Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics, 21(3):919-99 2020.
440

---

442
[37] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1541-1551, 2021.
443
444
445
446
[38] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proc. Ins. Conf. Learn. Represent. 2018.
448
[39] Ulrike Von Luxburg. A tutorial on spectral clustering, Statistics and computing, (7(4):395-416 2007.
449
[40] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pages 165-174, 2019.
451
453
[41] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
454
455
456
[42] Sijie Yan, Yuajjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In Thirty-second AAAI conference artificial intelligence. 2018.
458
459
[43] Elena Zheleva and Lise Getoor. To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles. In Proceedings of the 18th international conference on World wide web, pages 531-540, 2009.
460
461
462
[44] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily.
463
484
[45] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804 2020.
485
466
467
[46] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226, 2021.
468
469
Checklist
470
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
473
contributions and scope? [Yes] See Sect. [ our contribution is in the last paragraph.
474
(b) Did you describe the limitations of your work? [Yes] See in Sect. ??.
475
(c) Did you discuss any potential negative societal impacts of your work? [Yes] The broader impact is discussed in supplemental materials.
476
477
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
480
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
482
3. If you ran experiments..
483
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and instructions related to the experiment are in the supplementary materials.
484
485
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the experimental setup in Sect. and more detail in supplemental materials.
487
12

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] The confidence interval reported.
490
491
(d) Did you include the total amount of compute and the type of resources used (c.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] See in the supplemental materials.
4. If you are using existing assets (e.g., code, data, models) or curating/releasngg new assets...
494
(a) If your work uses existing assets, did you cite the creators? [Yes]
495
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
497
488
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
500
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
502
5. If you used crowdsourcing or conducted research with human subjects...
503
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
505
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
506
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
508
13


Reviews:
[{"review_id": "vq7ip3M49W", "reviewer": "Reviewer_WEKa", "summary": "This paper discusses node oriented spectral filtering as an extension to Chebyshev polynomial of normalized adjacency matrix. As motivation the paper argues on the aggregation of neighbors of labeled nodes. The paper argues on superiority on non-homophilic graphs through experiments.   ", "questions": "The argument of 2-hops and 3-hops aggregation is a bit confusing. It is mainly based on experiments using a few set of datasets. To my knowledge, methods such as the GPRGNN and Mixhop which uses higher-order convolutions (acting as convolution from multiple hops) do not impose such limits. Can authors elaborate on this?  \n\n\nThis paper only contain experiments with graph data by [Pei et al]. Further, the homophily measure described in the paper is a bit dated.\nThere is a new homophily measure and new non-homophilic benchmark datasets introduced by [Lim et al., 2021a, Lim et al., 2021b].\nIt would be interesting know how the proposed method perform with some of the new non-homophilic data. Can the authors provide few more experiment with the new dataset?\n\nTwo important non-GCN/GNN bechmark method that are important for comparison are the MLP and LINK [Zheleva and Getoor, 2009]. MLP would allow us to know about learning ability of node features itself and LINK tells us about direct learning from graph data only (adjacency matrix). Can the authors add these two benchmark methods in the paper? Another benchmark method that is useful for comparison is LINKX [Lim et al., 2021a].\n\n\nReference\n   \n[Zheleva and Getoor, 2009] Zheleva, E. and Getoor, L. (2009). To join or not to join: The illusion of privacy in  social networks with mixed public and private user profiles. WWW ’09.\n \n [Lim et al., 2021a] Lim, D., Hohne, F. M., Li, X., Huang, S. L., Gupta, V., Bhalerao, O. P., and Lim, S.-N.  (2021a). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In  NeurIPS.\n \n [Lim et al., 2021b] Lim, D., Li, X., Hohne, F., and Lim, S.-N. (2021b). New benchmarks for learning on  non-homophilous graphs. Workshop on Graph Learning Benchmarks, WWW 2021.", "limitations": "Limitations are not well discussed. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.) Experimental results are promising\n\nWeaknesses:\n1.) Highly Incremental work. Very closely related to ChebNet and related method.\n2.) Homophily definition is not up to date and experiments are not adequate.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ccbc0uLqqW", "reviewer": "Reviewer_LUHK", "summary": "The paper proposes a method called NFGNN which utilizes generalized translation operator to learn local patterns contributing to homophily/heterophily.\n", "questions": "Please see the section above.", "limitations": "n/a", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. A new GNN method with ability to capture the local patterns.\n2. Well organized and easy to follow (in general).\n\n\nWeaknesses/Questions:\n\n1. My main concern is the performance of the proposed method as compared to existing baselines. \nAlso, FAGCN adresses heterophily by considering low as well as high frequency information. \nThe numbers reported in FAGCN are superior to the proposed method. \nTherefore it is difficult to establish the usefulness of the proposed method.\n\n2. The evaluation on only node classification task seems limited to me. \nAdditional experiments on graph classification tasks will further strengthen the paper. \n\n3. Even though Section 6 is well motivated, the content does not justify it to be a separate section.\n\n4. Citation method is not proper. (please use \\citep{} or \\citet{} accordingly)\n\n5. The purpose of reparameterization with low-rank approximation against first (or higher) order polynomial is not clear to me. \n\n6. How does generalized translated operator help in adapting to local patterns? It is defined through spectral domain. \nWhat is the intuition of this translation operator in spatial domain when a filter is translated to a node?\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UzrZf0pywO4", "reviewer": "Reviewer_YZ7W", "summary": "This work proposes a new graph neural network by designing a node-oriented spectral filtering method. The developed algorithm is motivated by the observation that the subgraphs centered at different nodes have different properties. Experimental results demonstrate superior performance compared to baseline models.", "questions": "See weakness section", "limitations": "see weakness section", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. This paper indicates the fact that real-world graphs are often a mixture of diverse subgraph patterns.\n2. This paper shows that the standard near-neighborhood aggregation mechanisms fail to work for the non-homophily graph.\n3. This paper proposes a novel node-oriented graph spectral filtering method, which gives rise to a more powerful GNN model.\n\nWeakness:\n\nOverall, I am satisfied with the experimental findings and observations. The proposed model seems to be novel and useful. Some minor issues are as follows:\n\n1. What if using 3 or more hop neighborhood aggregation methods? Standard multi-layer GNN models implicitly perform multi-hop neighbor aggregation. A discussion on this point is needed.\n\n2. Will using learnable node-oriented graph spectral filtering involve more trainable parameters? Will this incur more severe overfitting?\n\n3. It would be better to give a more clear comparison between the proposed filtering method and the prior methods in Section 4.1 (i.e., give more equations) to better highlight the difference and novelty of the proposed method.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HqPnXEnOh3", "reviewer": "Reviewer_TWyA", "summary": "In this work the authors address the problem of local structure variation and non-homophily by introducing a generalized translation operator in order to implement a node centered spectral filter for graph neural networks. They demonstrate the empirical effectiveness of their method by confirming the realization of the filter localization in practice and showing performance gains on datasets with different homophily ratios.", "questions": "1. I'm a little confused by the wording of line 224 - it's stated as if $\\Psi$ should be included in Eq. 9 somewhere? \n2. It is somewhat out of scope I'm sure, but as a convincing sanity check, it would be nice to have the _complement_ to the demonstration that the NF method indeed improves node oriented predictions, the complement being how it effects the full graph classification task. Would your hypothesis be that it doesn't improve/alter global representations much in that setting? (this would be a meta ablation of sorts)", "limitations": "1. Barely a limitation, more a comment, that Table 1 is not as interesting/relevant to me as Fig 3 and Table 2. The direct analysis on the ability of the NF method to address heterophily should be the focus of the empirical section, even extended if possible.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**Quality/Clarity**: The preliminaries and technical details of their proposed method are sound. The motivations section is particularly in depth as it provides not only theoretical but also empirical analysis of the homophily versus heterophily characteristics of the datasets to be used in the evaluation.\n\n**Significance**: Though the modification is small, it fundamentally increases the adaptiveness of the family of spectral GNN approaches that, while having some nice theoretical properties, in their standard formulation, lack fine grained expressiveness or the ability to scale to large scale graphs where global filters are likely not as meaningful. Figure 3 and Table 2 provide targeted evidence of the effectiveness of the translation operator/NF modification.\n\n### Weaknesses\n\n**Significance**: The margins of improvement in Table 1 are not very significant except in Squirrel and Texas \n\n**Clarity**: There is not adequate discussion devoted prior to Section 5 in the preliminaries or the other theoretical prose on how exactly the localized filter is expected to better address variations in homophily characteristics. This is somewhat borne out by the results anyway, but it should be motivated earlier on.\n\n**Originality**: Also relating to the significance, the fact that the core modification itself is quite compact, is noted, and thus the likelihood that the approach is completely novel is potentially low. But this isn't a focus of this review.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject