Is Heterophily A Real Nightmare For Graph Neural Networks Performing Node Classification?
Authors: Sitao Luan
Chenqing Hua
Qincheng Lu
Jiaqi Zhu
Harry Zhao
Shuyuan Zhang
Xiao-Wen Chang
Doina Precup
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Graph Neural Networks
Homophily
Heterophily
Filterbank

Abstract: Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based on the relational inductive bias (homophily assumption). Though GNNs are believed to outperform NNs in real-world tasks, performance advantages of GNNs over graph-agnostic NNs seem not generally satisfactory. Heterophily has been considered as a main cause and numerous works have been put forward to address it. In this paper, we first show that not all cases of heterophily are harmful for GNNs with aggregation operation. Then, we propose new metrics based on a similarity matrix which considers the influence of graph structure and input features on GNNs. The metrics demonstrate advantages over the commonly used homophily metrics by tests on synthetic graphs. From the metrics and the observations, we find some cases of harmful heterophily can be addressed by diversification operation. With this fact and knowledge of filterbanks, we propose the Adaptive Channel Mixing (ACM) framework to adaptively exploit aggregation, diversification and identity operations in each GNN layer to address harmful heterophily. We validate the ACM-augmented baselines with 11 real-world node classification tasks. They consistently achieve significant performance gain and exceed the state-of-the-art GNNs on most of the tasks without incurring significant computational burden.

Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
Anonymous Author(s)
Affiliation
Address
email
Abstract
Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based on the relational inductive bias (homophily assumption). Though GNNs are believed to outperform NNs in real-world tasks, performance advantages of GNNs over graph-agnostic NNs seem not generally satisfactory. Heterophily has been considered put forward to address it. In this paper, we first show that not all cases of heterophily are harmful for GNNs with aggregation operation. Then, we propose new metrics based on a similarity matrix which considers the influence of graph structure and input features on GNNs. The metries demonstrate advantages over the commonly used homophily metrics by tests on synthetic graphs. From the metrics and the observations, we find some cases of harmful heterophily can be addressed by diversification operation. With this fact and knowledge of filterbanks, we propose the Adaptive Channel Mixing (ACM) framework to adaptively exploit aggregation, diversification and identity operations in each GNN layer to address harmful heterophily. We validate the ACM-augmented baselines with 11 real-world node classification tasks. They consistently achieve significant performance gain and exceed the trate-of-the-art GNNs on most of the tasks without incurring significant computational burden.
main cause and numerous works have been
11
13
15
17
Introduction
19
20 Deep Neural Networks (NNs) 18 have revolutionized many machine learning areas, including image recognition I7 speech recognition [TO] and natural language processing 2 etc.One major strength is their capacity and effectiveness of learning latent representation from Euclidean data. Recently, the focus has been put on its applications
22
23
-on-Euclidean data 4 e.g., relational data
24
or graphs. Combining graph signal processing and convolutional neural networks [19] numerous Graph Neural Networks (GNNs) 20 perform traditional neural networks on graph- machine learning tasks, e.g., node classification,
25
! have been proposed which empirically out-
26
27
graph classification, link prediction and graph generation, etc. GNNs are built on the homophily assumption 26). i.e., connected nodes tend to share similar attributes with each other [. which offers additional information besides node features. Such relational inductive bias is believed to be a key factor leading to GNNs' superior performance over NNs' in many tasks.
28
29
30
31 Nevertheless, growing evidence shows that GNNs do not always gain advantages over traditional NNs 32 when dealing with relational data. In some cases, even simple Multi-Layer Perceptrons (MLPs) can
33 outperform GNNs by large margin 55 22 J. An important reason for the performance degradation
34 is believed to be the heterophily problem. i.e,, connected nodes tend to have different labels which
35 makes the homophily assumption fail. Heterophily challenge has received attention recently and
38 there are increasing number of models being put forward to address this problem 45
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 Contributions
In this paper, we first demonstrate that not all heterophilous graphs are harmful for aggregation-bast GNNs and the existing metrics of homophily are insufficient decide whether the aggregation operation will make nodes less distinguishable or not. By constructing a similarity matrix from backpropagation analysis, we derive new metrics depict how much GNNs are influenced by the graph structure and node features. We show the advantage of our metrics over the existing metrics
38
39
40
41
42 by comparing the ability of characterizing the performance of two baseline GNNs on synthetic graphs of different levels of homophily, From the similarity matrix, we find that diversification operation able to address some harmful heterophily cases, and then based on which we propose Adaptive Channel Mixing (ACM) GNN framework. The experiments the synthetic datasets, real-world datasets and the ablation studies consistently show that baseline GNN augmented by ACM framework is able to obtain significant performance boost node classification tasks on heterophilous graphs
43
44
46
48
The rest of this paper is mainly organized as follows: section we introduce the notation and the background knowledge. In section B] we conduct node-wise heterophily analysis, derive new metrics based on a similarity matrix and conduct experiments to show their advantage. section 4.3] we propose the ACM-GNN framework to adaptively utilize the information from different filterbank channels to address heterophily problem. In section 5 we discuss the related works and clarify the differences to our method. In section 6 we provide empirical evaluations on ACM framework, including ablation study and tests on 11 real-world node classification tasks.
49
50
51
52
59
54
Preliminaries
55
We introduce the related notation and background knowledge. We use bold fonts for vectors (e.g., 57 v). Suppose we have an undirected connected graph 9 = AV), where V is the node set with
58 IV N: & is the edge set without self-loop: E R RRNX is the symmetric adjacency matrix with
59
A.j = iff eij E E, otherwise A.j = O. We use D to denote the diagonal degree matrix of G. i.e.
60 D = d, = Σj Aig and use Nr to denote the neighhorhood set of node i, i.e., Nr = [j Jj:00 Eij E)
61 A graph signal is a vector I E RV defined on V, where x; is defined on the node i. We also have a graph signals and whose i-th row X is feature vector of node i. We use Z E NxC to denote the label encoding matrix, whose i-th row Zı is the oot encoding of the label of node i. The i-th column of the identity matrix T is denoted by ez-
62 feature matrix X E RR-XF, whose columns
64
65
2.1
Graph Laplacian, Affinity Matrix and Their Variants
66
The (combinatorial) graph Laplacian is defined as L D A, which is Symmetric Positive Semi- (SPSD) (6. Its eigendecomposition gives T. UAU", where the columns u, of U E NNN are orthonormal eigenvectors, namely the graph Fourier basis, A diag(Ai..... Ax) with A S .... S. AN. and these cigenvalues are also called frequencies. The graph Fourier transform u//x u
67
69
of the graph signal æ is defined as æ --- U xxx= x
where u² x is the
71
component of x in the direction of ui.
72
In additional to L, some variants are also commonly used, e.g., the symmetric normalized Laplacian Lyym = D 112 1122 = 1- 1-1 10-12/2----0 AD-1 and the random walk normalized Laplacian L,w = D T, = 1 D- A. The affinity (transition) matrices can be derived from the Laplacians, e.g.,
73
74
Anw = 1- Lyw = D-1 A, Asym = Laym = AD AD- 11/2 and are considered to be low-pass filters 25. Their eigenvalues satisfy A₂ (Arw) = (A4m)) = 1 Ac 1 >z ) E (-1, 1].
75
76
77
Applying the renormalization trick [15 to affinity and Laplacian matrices respectively leads to
Agm = D-1/2 A521 and Taym = [ Asm. where = A + / and ò = D + T. The renormalized affinity matrix essentially adds self-loop to each node in the graph, and is widely used in Graph Convolutional Network (GCN) 15] as follows,
78
79
80
= softmax (Amm ReI.U(Aym XWo) Wi)
where Wo E RF and Wi E R x0 are learnable parameter matrices. GCN can be trained by minimizing the following cross entropy loss
81
82
C= ---trace(23 Ld log Y)
(2)
83 where log(:) is component-wise logarithm operation. The random walk renormalized matrix 84 Aw D-1 which shares the same eigenvalues as Ayms can also be applied in GCN. The
2

---

corresponding Laplacian is defined as L.w = Aww- Arw is essentially random walk matrix and 86 behaves as a mean aggregator that is applied in spatial-based GNNs [2] To bridge the spectral
85
87 and spatial methods, we use Arw in the paper.
2.2
Metrics of Homophily
89
The metrics of homophily are defined by considering different relations between node labels and graph structures defined by adjacency matrix. There are three commonly used homophilies: edge
91
homophily [ 351. node homophily [28], and class homophily [2I] defined as follows:
(g) { (uw Cue E Eu.
Zu.i W = [V]
{u u E Zu. = Zu
Hedge
[3]
du
NEV
{2 Zo.k = 1H
hg E Yu
Zu = 1, No. Zu: = Zu
Helass (9)
hg
C
Eee(w/Zo,=11) dp
(3)
where [a]+ = ma 0); hg is the class-wise homophily metric [21] They are all in the range of (0, 1] and value close to 1 corresponds strong homophily while value close to 0 indicates strong heterophily. Hadge measures the proportion of edges that connect two nodes in the same class; Hodee (9) evaluates the average proportion of edge-label consistency of all nodes; H9las( tries to avoid the sensitivity to imbalanced class, which can cause Hodge misleadingly large. The above definitions are all based on the graph-label consistency and imply that the inconsistency will cause harmful effect to GNNs. With this in mind, we will show a counter example to illustrate the insufficiency of the above metries and propose new metrics.
92
94
95
96
97
98
99
3
Analysis of Heterophily
100
101
3.1
Motivation and Aggregation Homophily
Heterophily is believed to be harmful for message-passing based GNNs 335 28 5 be-
103
cause intuitively features of nodes in different classes will be falsely mixed and this will lead nodes indistinguishable (35]. Nevertheless. it is not always the case, e.g., the bipartite graph shown in Figure iis is highly heterophilous ac- cording to the homophily metrics G). but after mean aggregation, the nodes in classes and 2 only exchange colors and are still dis- the insufficiency of Hoode by examples to show that different graph typologies with the same Hoodo can carry different label information.
Class
105
Class
Metries:
After
107
Hedgs
Aggregation
HGoda(G
Hatass (G)
109
Magg
Hagge (G) -1
111
112
tinguishable. Authors in [5] also point
Figure 1: Example of harmless heterophily
113
115
To analyze to what extent the graph structure can affect the output of GNN, we first simplify the GCN by removing its non-linearity [II. Let Å E I NxN denote general aggregation operator. Then, equation can be simplified as,
118
Y softmax softmax(AXX) (AXW) softmax(Y")
(4)
0C After each gradient decent step AW = ow, where is the learning rate, and the update of Y' will be (see Appendix for derivation).
119
120
dc & Ax
ac OW
AY' AXAW = Ax
(5)
where S(,,x) AX(ÁX) is node similarity matrix after aggregation, Z Y is the prediction error matrix. The update direction of node is essentially a weighted sum of the prediction error, i.e.,
122
A(Y").. r.. =EEv (((AA)) i.j
123
'The authors in 21 did not name this homophily metric. We name it class homophily based its definition.
3

---

124
To study the effect of heterophily, we define the aggregation similarity score.
125
Definition 1. Aggregation similarity score
Sags (S(),x)) K Mean. ((S(A, | v).u Zn: Zo.)) }) 2 Mean, (IS(A, X) Bua + Zoo (o.)))
M
(6)
126
where Meana (f-)) takes the average over u of a given multiset of values or variables.
Sugg (S) is the proportion of nodes V that will put relatively larger similarity weights nodes in the same class than in other classes after aggregation. is easy to see that Sage (S(,, X)) e
128
[0, 1]. But in practice, we observe that in most datasets, we will have Sagg (S(,, X)) 2 0.5. Based on the following modified aggregation similarity for practical usage, Sag
129
130
this observation, we rescale 6
(A(,)))
2S (S(A,))
131
In order to measure the consistency between labels and graph structures without considering node features and make a fair comparison with the existing homophily metrics in Gb. we define the graph (g) aggregation (A) homophily and its modified version
132
Hage = Sage (S(A. Hig (9) Sags
((A,
(8)
134
In practice, we will only check (9) when H (G) =
As Figure shows, when À = A (9) H (g) Thus, this new metric reflects the fact that nodes in classes and 2 are still highly distinguishable after aggregation, while other metrics mentioned before fail capture the information and misleadingly give value O. This shows the advantage of Hagg()) and Hage (9) by
agg
135
136
137
138
additionally considering information from aggregation operator and the similarity matrix.
To comprehensively compare H dug (9) and the metrics in in terms of how they reveal the influence of graph structure on the GNN performance, we generate synthetic graphs and evaluate SGC 31 and GCN 15 on them in the next subsection.
139
140
142
3.2
Evaluation and Comparison on Synthetic Graphs
Data Generation & Experimental Setup For one dataset, generate 95 graphs in total with 19 edge homophily levels varied from 0.05 to 0.95, each corresponding to graphs. For every generated graph, we have 5 classes with 400 nodes in each class. In each class, there are randomly generated 800 intra-class edges and [(800- - (edge()))) Hooee inter--lasss edges. The features of nodes each class are sampled from node features in the corresponding class of the base dataset. Nodes are randomly split into 60%//0%%/20 for train/validate siliia/lllaaiio/eestt.. We train 1-hop SGC (sge-/ 31 and
144
145
146
147
148
149
GCN [S] on synthetic data (see appendix [A.]] for hyperparameter searching range). For each value of H edgge (9), we take the average test accuracy and standard deviation of runs over 5 generated graphs.
150
For each generated graph, we also calculate its ( Helss (G) and H. (G). Model performance with respect to different homophily values are shown Figure
Test Accuracy
1.0
0.8
0.6
0.4
0.2
0.0 0.2 0.6 0.8
0.0 0.6 Node Homophily
0.2 0.6 0.8 Class Homophily
Edge Homophily
Modified Agg Homophily
(a) Hadge
(b) Hmnde())
(c) Ham. (9)
(d) H (G)
Figure 2: Comparison of baseline performance under different homophily metrics.
152
According
B) Hedge (g) #intra-class adges/(#intree) /ee///Wiinntaaaneeee edges #inter-class edges)

---

153
Comparison of Homophily Metrics The performance of SGC-1 and GCN are expected to be
monotonically increasing with a proper and informative homophily metric. However, Figure 2 ()) ()) show that the performance curves under (G) mode (g) and clluss are U-shaped while Figure d) reveals nearly monotonic curve with a little perturbation around This indicates that
154
155
156
H M (9) can describe how the graph structure affects the performance of SGC-1 and GCN.
157
158
In addition, we notice that in Figure aa) both SGC-1 and GCN get the worst performance on all datasets when Hedge (G) is around somewhere between 0.1 and 0.2. This interesting phenomenon can be explained by the following theorem.
159
180
161
Theorem 1. (See Appendix C for proof). Suppose there are C' classes in the graph G, edges for each node are i...l. such that each edge of any node has probability h of connecting with nodes in the same class and probability 1 - h of connecting with nodes in different classes, and B(d,.) = d for
162
all nodes. Let the aggregation operator À = Áiw- Then, for nodes v, 01 and u2, where Zun Zo: and Zug + Zu we have
185
-(1
(C-
1) + +1) - h)dd 2 (C - 1)(d 1)
g(h) = E (S(A, 2e...) - -E (S(A,))o.u)
(9)
and the minimum of g(h) is reached at
d + 1 C
distra/ + 1-C
diuttr
Cd
O(diata/h) h)
Cdlint + C C-1
186
where dintra = dh, which is the expectation of the number of neighbors of a node that have the same label as the node.
167
188
The value of (h)) in D is the expected differences of the similarity values between nodes in the same class and nodes in other classes. g(h) is strongly related to the definition of aggregation homophily and its minimum potentially implies the worst value of Hagg (9). In the synthetic experi- ments, we have diuaa 2, 5 and the minimum of g(h) is reached at h = 1/7 0.14, which corresponds to the lowest point in the performance curve in Figure aa). In other words, the h where
169
170
171
172
173
SGC-1 and GCN perform worst is where g(h) gets the smallest value, instead of the point with the smallest edge homophily value. This again shows the advantage of (9) over Hedge (G) by taking
175
use of the similarity matrix.
Class 1
Class 2
Axx AT
(I
A)
XXX
(I
A)
50
50
.50
.50
.00 .00
.67
.20
-25
-20
-25
X = Z
.50
33
.25
.20
.25
.00 .00
.00
.00
.00
.00
.00
1: [1,0]
50
50
20
33
56
60
.60
68
.58
65
.60
.68
.58
.65
20
.67
_00
.0
-27
.89
-27
.00
-33
.10
-27
.08
-33
.10
2: [1,0]
50
558
65
66
.65
.63
25
00
-33
10
.13
.10
.13
3: [1,0]
.00
25
60
68
65
.68 .65
-0
00
-27
08
.10
.08
4: [0,1]
50
25
558
65 .63 .65
.63
25 .0
.33
.10
.13
.10
.13
5: [0,1]
Large positive weighs in inter-class block for node 1,3.
Positive weights in intra-class blocks,
6: [0,1]
negutive weights in cross-class blocks.
7: [0,1]
Figure 3: Example of how HP filter addresses harmful heterophily
176
4
Adaptive Channel Mixing (ACM) Framework
177
4.1 How Diversification Operation Helps with Harmful Heterophily
We first consider the example shown in Figure 3. From S(Å, X), nodes 1,3 assign relatively large positive weights to nodes in class 2, which will negatively affect information aggregation. Despite the fact, we can still distinguish between nodes 1,3 and 4,5,6,7 by considering their neighborhood
178
179
180
A similar J- J-shaped curve is found in 35 though using different data generation processes, It does not mention the insufficiency of edge homophily.
5

---

difference: nodes 1.3 are distinguishable from their neighbors while nodes 4,5,6,7 are homogeneous to their neighbors. This indicates, some cases, although some nodes become similar after aggregation. they are still distinguishable via surrounding dissimilarities. This suggests the possibility of using diversification operation to address harmful heterophity i.e. high-pass (HP) filter / Á B (will be introduced in next subsection). As S(I A, Z) in Figure B shows, nodes 1.3 assign negative weights to nodes 4,5,6,7, i.e,, nodes 1,3 treat nodes 4,5,6,7 as negative samples and will move away from them. Base this example, propose diversification distinguishability as follows,
182
186
Definition 2. Diversification Distinguishability (DD) based on S(1 - (()-A
188
Given S(T - A, X), node v is diversification distinguishable if the following two conditions are satisfied at the same time,
189
190
X) EVA Zuu; -Zvs)) 2 0; 1. Meana ((S(T A,
(10)
2. Mean.. (15(1- VVA Zu: & Zuii)) S
Then, graph diversification distinguishubillty value is defined as
191
1 DD x = | fulv is diversification distinguishable)
(11)
DD x.x (9) E [0, 1] measures the proportion of nodes that HP filter is helpful for. Its effectiveness be proved for binary classification problems under certain conditions, leading
Theorem 2. (See Appendix for proof). Suppose X 2, = Anw Then, for binary classifica- tion problem, Le., C = 2, all nodes are diversification distinguishable and DD (g) 1.
194
196
Conducting both aggregation and diversification operations to distinctively extract the low- and high- frequency information from graph signals is the same as using filterbanks in graph signal processing. We introduce filterbanks in next subsection.
198
4.2
Filterbank in Spectral and Spatial Forms
For the graph signal æ defined on G. a 2-channel linear (analysis) filterbank includes pair of filters HLP, Hup, where H.r and HiP retain the low-frequency and high-frequency content of respectively.
Filterbank
g
201
203
Most existing GNNs are under uni-channel filtering architecture 15
30
with either Hip or
204
HEP channel that only partially preserves the input information. Unlike the uni-channel architecture, filterbanks with HLP + HHP will not lose any information of the input signal, i.e., perfect
205
206
reconstruction property
Generally, the Laplacian matrices (Lsym- Laws Loyms L can be regarded as HP filters S and affinity matrices (Asym. Arw Asm- Arw) can be treated as LP filters 25 [_ Moreover, MLPs can be considered as owing a special identity filterbank with matrix I that satisfies HLP + НμP = 1 +
207
209
210
Filterbank in Spatial Form Filterbank methods can also be extended to spatial GNNs. Formally, on the node level, left multiplying HLP and ННР on æ performs as aggregation and diversification operations, respectively. For example, suppose HLP A and Hup
211
Å, then for node we have
212
Aijzj, (HIPz); = Iz (HIr = (E(U)))
Ai,
(12)
jE (E
213 where A. is the connection weight between two nodes. To leverage HP and identity channels in
214 GNNs, we propose the Adaptive Channel Mixing (ACM) architecture in the following subsection.
'In graph signal processing, an additional synthesis filter g is required to form the 2-channel filterbank. But synthesis filter is not needed in our framework, do not introduce in our paper.

---

215
4.3
Adaptive Channel Mixing(ACM) GNN Framework
216
ACM framework can be applied in lots of baseline GNNs and in this subsection, we use GCN as an example and introduce ACM framework in matrix form. We use Hip and HμP to represent general LP and HP filters. The ACM framework includes steps as follows, Step 1. Feature Extraction for Each Channel:
217
218
H = HLLReLU (HI- H = HeL (H' H = ReLU W
W W w Fi
Step 2. Feature-based Weight Learning with Row Normalization (RN):
H = RN (H)), H1 = RN (H²). H' RN (Ha):
a2 (BLU (MA d'H = (ELU ( (# . (ELU (HAW;))
W/-1 WH w/-! Fix
Step 3. Channel Mixing:
H' (diag(a')) + diag(a')) diag(a))(ti).
(13)
219
ACM-GCN first implements distinct non-linear feature extractions for 3 channels, respectively. After processed by a set of filterbanks, filtered components Hi, H H) are obtained. Different nodes may have different needs for the information in the 3 channels, e-g., in Figure 3 nodes 1,3 demand high-frequent information while node 2 only needs low-frequency information. To adaptively exploit information from different channels, ACM-GCN learns rowwise (nodewise) feature-conditioned
220
222
223
224
(nn-normllieed) weights to combine the 3 channels. ACM can be easily plugged into spatial GNNs by
225
replacing HLP and Hur by aggregation and diversification operations as shown in (2.. See Appendix for detailed discussion of model comparison on synthetic datasets.
226
Complexity Number of learnable parameters in layer I of ACM-GCN is 3F- 1 while it is Fi- Ft in GCN. The computation of step 1-3 takes F2 + + 2 HIp) + nnz( Hyp) )) flops, while GCN layer takes 2 + (Fi(nnz(HH,
228
flops, where nnz(-) is the number of
230
non-zero elements. A detailed experiments on running time is conducted in section 6.1
231
Limitations Diversification operation does not work well in all harmful heterophily cases. For example, consider an imbalanced dataset where several small clusters with distinctive labels are densely connected to a large cluster. In this case, the surrounding differences of nodes in small clusters are similar, i.e., the neighborhood differences are mainly from their connection to the same large cluster, and this possibly makes diversification operation fail to discriminate them. See a more detailed demonstration and discussion in Appendix G
232
233
234
235
236
5
Prior Work
238
GNNS on Addressing Heterophily We discuss relevant work of GNNs on addressing heterophily challenge in this part. M1 acknowledges the difficulty of learning on graphs with weak homophily and propose MixHop to extract features from multi-hop neighborhood to get more information.
240
28 precomputes unsupervised node embeddings and uses graph structure defined by geometric relationships in the embedding space to define the bi-level aggregation process. [T3 proposes measurements based feature smoothness and label smoothness that potentially helpful to guide GNNs on dealing with heterophilous graphs. H₂GCN 35 combines 3 key designs address heterophily: (1) ego- and neighhor-emmeddae separation; (2) higher-order neighborhoods; (3) combination of intermediate representations. CPGNN (34 models label correlations by the compatibility matrix, which is beneficial for heterophily settings, and propagates prior belief estimation into GNNs by the compatibility matrix. GPRGNN (5) uses learnable weights that can be both positive and negative for feature propagation, it allows GRPGNN to adapt heterophily structure of graph and is able to handle both high and low frequency parts of the graph signals.
242
244
245
246
248
249
250
251
GNNs with Filterbanks Previously, there are geometric scattering networks 9 27 that apply filterbanks to address over-smoothing [20) problem. The scattering construction captures different channels of variation from node features or labels. In geometric learning and graph signal processing, the hand-pass filtering operations extract geometric information beyond smooth signals, thus believed that filterbanks can alleviate over-smoothing in GNNs. In ACM framework, we aim to
252
254
7

---

256 design a framework with the help of filterbanks to adaptively utilize different channels to address the challenge of learning on heterophilous graph. We deal with different problem as in
257
258
6
Experiments on Real-World Datasets
259
In this section, we evaluate ACM framework on real-world datasets. We first conduct ablation studies in subsection 6. validate different components, Then, we compare with the state-of-the-arts
280
261
models in subsection 6.2
262
6.1
Ablation Study & Efficiency
Ablation Study Different Compancnts ACM-SGU and ACM-GIN (16
Basaline
Model Components
Comell
Wisconsin
Toxas
Film
Chameloon
Squireel
Com
ChueSerr
PakMMel
Models
LPP HP Identity Mosing|
Are d: Std
Ace di Stl
Acc
d:
Std
Acc
d:
Sid
Apc
Sid
Aec
di Std
Acc d: Sid
Aec d: Sid
Acc :: Std
14.45
6.01
69.75
84.1
+ 2332
25.34
241
64.55
+ 1,38
42.8
1.1
185
79.85
104
84,45
0.58
84.92 = 4.59
91.75
+ 4.05
80
34
+ 3.67
36.94
+ 1.07
63.11
= 1.64
44.8
+ 1.35
85.6
1.51
50:33
+ 1.25
84,5
= 0.42
SUCC-1 w/
92.3 = 38
93 + 2.11
91.64
+ 3665
38.25
+ 166
57
1993
40.2
+ 2
85.98
+ 0.84
50.2
2001
84.37
0.44
+ 3.88
36.58
61.4
252
41.59
8AM8
1.2
79.1
92.46 = 2.10
93.38
+ 2.68
91
38.1
1.22
62.39
2,45
45.65
86552
1.55
70.79
1665
87.69
0.6
81.31
70.25
62.13
34:55
1,55
0.82
$2,95 + 5.17
88.63
2.51 83.03
267
40
1,06
68.12
1.73
$2.08
1.47
83
162
$5
0,9
90.09
0.29
GCN w/
92.13 + 2,65
94.37
+ 3:27
93.11
2.48
40.3
163
06.67
2.15
49.45
0.8
88.46
1.31
51
+
1.15
91.21
1.17
88.52
4,51
1: 225
92.3
221
40.25
1.78
65.97
2.24
51.02
1.64
88.7
6868
50.93
1,53
90.66
0.32
3.0
67.79
1.79
0.87
90.72
Averaee Running Time Per Epoch/Awerage Total Running Time Comparisun
2.70ms00.59 2.5 2.53ms00:51s 2. 6.6mm11..55 3.62mn//1 13s 4, 4.900ms/3 99s
4,05mo80.87%
5.34m/ 22s 4.79mm/44 55% 5 5.58ms/7.700
4.92mm/11.044 04ss
5.03ms/L.00
6.67ms/1.55 .58 6.68me/1.33%
6.42ma//1996
96s
7.41ms/1.99s
6.68mm/2243s
6.69ms/
196 7.20ms/22 48s
4.99ms/1 4.7
4.79mc/1
5.53ms/1
5.80
6.48mm/1
6.500me2.00%
6.25mm/1 7.76s
6.73em/22
4.30ms00088
4.31ms0)91s
4.58ms00.95
95%
3.86mee1
19%
5.999ms/1.43
6.84ms/1
&is
3.40me/1.57
1.5%%
5.72m//1
6.30mms/2 04s
5.15mmi11.08 5.82m//
3.55ms/L.18
6.28ms/1
1,50s
6.60ms/11966
7,27ms/1 15s
7.05ms/2.60s
6.99ms/11.0
1.94s 7:28ma/2.07s
3. 3.78ms00 78s 3.91 79, 3.80ms00.7ss 4.42me00 89s
4.4ms00.59 6, 6.85me'l (8s
4.19me/th.8 87s 5 5.22me/1 113 4.8 4.81m/00995
7.63m/1 54s 7 9.99m// 924 7.26me/1 (48 8.42m</1
73s
9.74mm/ 76s
11, 11.19m22 383 7.74mu/1 61x 9.98ms'3 ..6 9. 9.10mm/1 85s
OCN
7.755s/21 83m/s/
6.99mef1
7.62me/1
54h 7.80mw11 67s
9.76m
7.50mel11
7.4mm/11
8.78mm/1
7.33ma/1 49s 6 8.80m/1 .3. 6.99ms/1 Als 8.76ms/2 19 7.81m//1
1I, 11.25mm2222
29, 7.77mu/1.
59s 7.66mm/1
.6. 8.36m//1 70s
8.0lmw/1.63 63s 8 98mml1 88s 8.17m 66% 9.29me2.000 9.33m/11 96s 12. 15155.2555 53s 9. 16mmll 85s 9.48me11 95% 9. 9.54ml/ 92s
Table 1: Ablation study on 9 real-worke datasets 28 Cell with means the component is applied to the baseline model. The best test results are highlighted.
263 We investigate the effectiveness and efficiency of adding HP, identity channels and the adaptive mixing mechanism in ACM framework by ablation study. Specifically, we apply the above components to SGC-1 and GCN separately, run 10 times on each dataset used in [X]] with 60%/20%/20%% random splits for train/validationn/ess and report the average test accuracy well the standard deviation. total running time(in
285
267
We also record the average running time per epoch(in milliseconds) seconds) to compare the efficiency. (See Appendix A for hyperparameter searching space.)
269
From the results we can see that on most datasets, the additional HP and identity channels are helpful, even on strong homophily datasets, such as Cora, CiteSeer and PubMed. The adaptive mixing mechanism also shows its advantage over the method that directly adds the three channels together. This illustrates the necessity of learning to customize the channel usage adaptively for different nodes. As for efficiency, we can see that the running time approximately doubled ACM framework than the original model.
270
271
273
275
6.2
Comparison with State-of-the-art Models
276
Datasets & Experimental Setup In this section, we implement SGC 33 with I hop and 2 hop (SGC-1, SGC-2), GCN [5] and GraphSAGE and apply them 112 in ACM framework: we use
277
An and mean aggregator as LP filter and the corresponding HP filter can be derived from T2).
278
279
We compare them with several baselines and state-of-the-an models: MLP with 2 layers M),.2),
GAT 30J. APPNP [16, GPRGNN (5) H₂GCN 35 MixHop MI. GCN+JK [15] 32 21, GAT+JK
281
52 21 and Geom-GCN 28 Besides the 9 benchmark datasets used in (28, we further tests
the above models on 2 new benchmark datasets, Deezer-Europe and YelpChi, that are proposed in
8

---

Comell
Wiscensin
Texas
Film
Chamelcon
Squireel
Deezer Europe
YelpChi
Cora
CheeSerr
PubMed
Moodes
251
7,600
2,277
5,201
28,281
45,954
2,708
3,327
19.217
Pedges
295
2093
309
33,544
36,101
217,073
92,752
3,866,599
5.429
4,752
44,538
#fcamures
1,703
1,703
1,703
931
2,325
2,089
31,241
32
1,433
3,703
500
#classes
5
6
Mldgee (2)
0.5669
0,4480
0.4066
0.3750
0.2795
0.2416
0.9251
0,7730
0.8100
0.7363
0.8024
Husts
0,3855
0,1698
0.0968
0,2210
0,2470
0.2156
0.5299
0.7698
0.8252
0.7175
0.7924
H Haya (9)
0.0168
0.094]
0.0013
0,0110
0,0620
0.0254
0.0304
0,0520
0.7657
0.6270
0.6641
15 (9)
0.8032
0,7768
0.094
0,6822
0.61
0.3566
0.5790
0.7206
0.9904
0.9826
0.9432
(p))
60/20/20
60/2020
640220/20
60V2020
60/20/20
60V20200
50025/25
50/25/25
60/20/20
60V20020
60/20/20
Test Accamey (96) State-of the am Model, Baseline GNN Models and ACM-GNN models
|Rank
MLP-2*
91.30
1:
0,70
93.87
3.33
92.26
1: 0.71
38, 58 d 0.25
46.7
73
1
0:46
31.28
0.27
66.
1: 0.72
87
94
= 0.52
76.44
0.30
76,
0.28
$6.43
1 0.
9,000
GAT
76.00
1.01
71.01
4.66
78.57
0.36
35
0.23
63.9
0.46
42.72
0.33
61.09
+: 0.77
$1.42
2.12
16.70
0.42
61.20
0.46
83.28
0.12
APPNP
91.80
+ 0.63
92.00
3.59
11
0.70
58 86
0.24
51.91
+ 0.56
34,77
+0.34
67.21
+ 0.56
75 60
0.48
79.4
+0 08
08.59
0.30
85.02 + 0.09
9.09
GPRGNN
91.36
0.70
93.75
0.61
0.27
49.93
0.50
71
67.63
0.05
6.64
H2GCN
86.23
87.5
1.77
3.53
38.85
1.17
30.39
1.22
07.22
0.90
58
021
87.52
0.61
79.97
87.78
0.29
MixHop
60.33
+ 28.53
77.25
+ 7.80
76.39
+ 7.66 33
2.40
36
10:22
24.55
2,60
66.80
+ 0.5%
57.02
0.5065565
+ 11.51
49:52
= 13.35
4.10
13.09
GUN-JK
66.56
13.82
62.50
+ 15.75
+ 1.91 32.72
2.62
64.08
+ 2.35
53.40
1,90
60.99
+ 0.34
64.35
+ 0.86
86.90
1.51
73.77
1,85
90.09
+ 0.00
10.09
GAT+JK
74,43
10.24
69.50
3.12
75.41
4: 7.1435.41
0.97
08.14
1.18
52.28
59.66
4: 0.92
90.04
89.52
0.43
74,49
2.76
89.15
0.87
8:27
Gomm-GCN
60.81
64.12
67,57
31,63
60,9
38.14
NA
NA
85.27
77.99
90.05
12.33
SGC-1
14.43 +: 6.01
69:15
5.02
84.1
242
25.34
3.41
62.34
192
42.8
1.1
59.73
4: 0.12
58.62
0.85
85.16
0.52
79.93
1,03
80.97
4 1..11
SGC-2
77.7 2: 4,47
72.75
1 3.91
$1
1
3.58
39
1
0.20
63.02
1
0:43
37,41
1
61.56
1: 0.51
57.18
1
0.75
86.58
0.26
76.23
0.29
B1.14
1 0.71
11.73
GCN
81.31
+ 3.13
4.05 34,45
0.85
45.11
62:23
0.53
0362
87.47
0.82
81.3
0.95
87.85
0..4
GmppSAGE
71.41
1.24
64.85
79.03
1.206.337
41.26
0.48
62.57
86.58
0.26
78.24
0.11
11:00
ACM-SGC-1
91.31 + 2:54
93.38
2.68
5.23 58
1.22
2.45
45.65
1.44
66.42
+ 0.96
85.83
1.34
86,52
1.55
80.79
1.65
87.00
0.6
6.27
ACM-SOC-2
90.66
3,36
92.13 5.06
90.66
1: 2.84
1.24
51.51
2.42
39:37
1.41
66.98
0.88
84
1.17
87,44
0.8
80.03
1.26
88.01
0.993
6.73
ACM-GCN
92.62
: 3,04
95.37
= 2.1
95.08
1.8 41.48
=
0.78
67
79
+
1.79
$2. 86
1.96
66.85
1 0.05
80.01
+ 1.02
89.11
= 0.87
N2.16
0.84
90.72
0.7
1.73
ACM-SAGE
91.31 1: 2.94 90.13
1 2.67
91.97
1: 3.15 36.68
2.46
61.81
1 2.71 44.63
3,02
66.21
1 0.59 55.73
1.45
86.24
1.25
50.87
1,36
88.51
0.9
6.45
Table 2: Experimental results: average test accuracy + standard deviation on II real-world benchmark datasets. The best results are highlighted. The "i" results are from 22 and NA means the reported results are not available. Results "*" are from
283
21
We test these models 10 times on Cornell, Wisconsin, Texas, Film, Chameleon, Squirrel, Cora, Citeseer and Pubmed following the same early stopping strategy, the same data splitting and Adam
285
IE!
optimizer used in GPRGNN [5]. For Eueroee-Europe and YelpChi, we test the above models
286
5 times with the same early stopping strategy, the same splits and AdamW [3] used in 21. The
287
details of hyperparameter search are reported in appendix A
288
The main results of this set of experiments with statistics of datasets are summarized in Table 2 where
289
we report the mean accuracy and standard deviation. We can see that after applied in ACM framework, the performance of baseline models are boosted on almost all tasks. Especially, ACM-GCN performs the best in terms of average rank (1.73) across all datasets and achieves SOTA performance on 6 out of 11 datasets. Overall, It suggests that ACM framework can help GNNs generalize better node classification tasks on heterophilous graphs.
291
293
7 Future Work
294
285
The similarity matrix and the new metrics defined in this paper mainly capture the linear relations of the aggregated nodes. But this might be insufficient sometimes when nonlinearity information in feature vectors are important for classification. In the future, similarity matrix that able to capture nonlinear relations between nodes can be proposed to define new homophily metrics.
296
297
298
From experimental results, the standard deviation of ACM-GNNs are relatively higher than GNNs on some tasks and this is suspiciously caused by the feature- based weight learning mechanism. In the future, stabilizer or more robust weight learning method can be proposed to reduce the variance.
300
302
8
Social Impact
303
We do not find any direct path of this work to any negative social impact.
'The authors proposed 8 new datasets. From the reported results, GCN only underperform MLP-2 on Deezer-Europe and YelpChi, which demonstrates the heterophily of these 2 datasets, therefore choose them.

---

References
304
305
[1] S. Abu-EI-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages
307
21-29. PMLR, 2019.
309
[2] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: MXXxv:440900477 2014.
310
[3] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzales V. Zambaldi, M. Malinowski,
312
A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1806::8800001661 2018.
313
314
[4] M. M. Bronstein, Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: going beyond euclidean data. arXiv, abs/1611.08097 2016.
316
[5] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. https://openreview. net/forum, 2021.
317
318
[6] R. Chung and F. C. Graham. Spectral graph theory. Number 92, American Mathematical 319
Soc., 1997.
[7] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering, arXiv, abs/ 100.09975, 2016.
322
[8] V. N. Ekambaram. Graph structured data viewed through a fourier lens. University of California, Berkeley, 2014.
324
325 [9] F. Gao, G. Wolf, and M. Hirn. Geometric scattering for graph data analysis. In International Conference on Machine Learning, pages 1122-2133 PMLR, 2019.
326
327 [10] A. Graves, A.-I. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pages 6649. Ieee, 2013.
329
330
[11] W. L. Hamilton. Graph representation learning, Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1 2020.
331
332
[12] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs arXiv, 02///2066222266 2017.
333
334
[13] Y. Hou, J. Zhang. Cheng. K. Ma, R. T. Ma. H. Chen, and M.-C. Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference on Learning Representations, 2019.
396
337
[14] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 112 2014.
338
339
[15] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv,, hass/1609.029099 2016.
[16] J. Klicpera, A. Bojehevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 18X.v:1810.05997, 2018.
342
343
[17] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
344
346
[18] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning, nature, 52 521((553))436, 2015,
347
[19] Y. LeCun, Bottou, Bengio, Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 11:227822324 1998.
10

---

349
[20] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi semi-supervised learning. arXiv, abs/1801.07666 2018.
350
351
[21] D. Lim, X. Li, F. Hohne, and S.-N. Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104.01404, 2021.
[22]
M. Liu, Z. Wang, and S. Ji. Non-local graph neural networks. arXiv preprint 1Xiv:2005.14612 2020.
354
355
[23] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint
358
17Xiv:1711.05101, 2017.
357
[24] S. Luan, M. Zhao, X.-W. Chang, and D. Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. arXiv preprint 3xXiv:/906.02174, 2019.
358
[25] T. Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 1rivv:1955.09550 2019.
360
361
[26] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1))415 444, 2001.
27 Y. Min, F. Wenkel, and G. Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. arXiv preprint arXiv:2003.08414, 2020.
384
385 [28] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.0S5 052087 2020.
386
367
[29] Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE transactions neural networky, 20 20(1):61-80 2008
[30] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv, 2ts/1710.10903 2017.
370
371
[31] F. Wu, T. Zhang, A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinherger. Simplifying graph
372
convolutional networks. arXiv preprint
2019.
373
[32] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and Jegelka. Representation learning on graphs with jumping knowledge networks. In J. Dy and A. Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages
374
375
376
PMLR, 10-15 Jul 2018.
[33] Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
378
380
[34] Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph neural networks with heterophily. arXiv preprini arXiv:2009. 13566, 2020.
381
382
[35] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph
383
neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
384

---

Checklist
385
386
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
388
389
(b) Did you describe the limitations of your work? [Yes] In the Appendix G we discussion
390
cases that high-pass filter cannot tackle.
391
(c) Did you discuss any potential negative societal impacts of your work? [No] It is in Section 8, we have not come up with significant social negative impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
394
395
2. If you are including theoretical results...
396
(a) Did you state the full set of assumptions of all theoretical results? [Yes] In Section 3&4, we mainly define new homophily metric and it is followed by two theorems.
387
(b) Did you include complete proofs of all theoretical results? [Yes] In Appendix C
399
we justify the new metric and two theorems.
400
3. If you ran experiments..
(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 settings are provided in details and the source code is submitted in the supplemental material.
402
404
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] In Section 6, we specify model details.
405
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We include average test accuracy of times of running with standard deviation.
407
409
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We include hardware details in Appendix, which is not computationally expensive.
410
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets....
413
(a) If your work uses existing assets, did you cite the creators? [Yes] In Section 6, we specify the datasets with their data split sources in footnotes.
414
415
(b) Did you mention the license of the assets? [No]
416
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
417
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
418
419
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] None included.
5. If you used crowdsourcing conducted research with human subjects...
422
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] None included.
423
424
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No] None included.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] None included.
427
12


Reviews:
[{"review_id": "gkR_sPiKgCf", "reviewer": "Reviewer_v2mj", "summary": "In this paper, the authors investigate how heterophily affects the performance of GNNs. Specifically, they first show that not all cases of heterophily are harmful. Then, they propose some new metrics to better characterize the graph properties and their relations to GNNs’ performance. Finally, the authors propose a framework named Adaptive Channel Mixing to address some kinds of harmful heterophily. This paper provides some new perspectives on understanding and addressing heterophily.  ", "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": "Strong points\n+ This paper provides new perspectives on the relation between heterophily and the performance of GNNs. \n+ A new method named Adaptive Channel Mixing is proposed, which is demonstrated to address some kinds of harmful heterophily. \n\nWeak points:\n-\tOverall, the connection between the investigation part (heterophily; new metrics) and the methodology part (new model) seems not strong. It would be better if the authors could describe their connection more clearly. \n-\tIn section 3.2, it would be better if the authors could provide more details of the data generation process. Furthermore, it would be helpful if the authors could provide some explanations of the U-shape of these curves. \n\n-\t In section 4, the authors claim that “diversification operation to address harmful heterophily”. However, it is not clear what is “harmful heterophily”. It would be helpful if the authors could provide a more detailed characterization of “harmful heterophily”. The case stays true for the proposed ACM framework. What kinds of “harmful heterophily” can it address? How does ACM address it? \n\n-\tIt is not clear what Theorem 2 indicates. It would be better if the authors could provide more explanation about this theorem and what it demonstrates.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "8YQt14U-Wy3", "reviewer": "Reviewer_H6yV", "summary": "Graph homophily and heterophily recently gain a lot of attention from the community. First, this paper proposes an interesting metric, which considers the general structure of graph convolutional networks, to measure the potential performance of GCNs on a certain type of graph. The metric shows a strong correlation with the accuracy of graph convolutional networks. They further analyze the characteristics of nodes where the GCN may not work properly that also match the synthetic results. Based on these observations, the adaptive channel mixing framework is proposed. The proposed framework utilizes the high/low-frequency filterbanks and shows strong performance on real-world datasets.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I liked reading this paper. The paper is easy to follow, and the analysis is intuitive and non-trivial, although the configuration is relatively simple. The proposed method with the high/low-frequency filter bank is not new, but the theoretical analysis makes the framework convincing. Some questions and limitations are addressed below:\n\n- What is the correlation between the proposed metric and test accuracy with the 11 real-world datasets? Does it match the observation from synthetic datasets?\n- The main analysis is based on the random walk Laplacian, which is not widely used than the symmetric Laplacian. Will it be impossible to draw a similar definition and theorem from the symmetric one?\n- Although Theorem 1 shows the situation where the message passing architecture may fail to achieve a good performance, the analysis does not take into account the existence of a learnable weight matrix. What would be the role of the weight matrix, and why can it not overcome these situations?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the main review.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7iFskby5hi1", "reviewer": "Reviewer_7tx9", "summary": "The paper makes two specific points:\n1. First the current reliance on homophily scores to distinguish which graphs are likely to perform well for a particular task is not precise. The paper proposes an alternative metric which seems to correlate better with performance.\n2. The paper takes inspiration from their proposed metric to define filter banks that separate high pass and low pass information separately and mixes them for the final desired task.", "questions": "", "limitations": "", "rating": 5, "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": "First of all, I would like to state the paper is well written and easy to understand, however, there are some gaps in the write up that makes it difficult to logically parse the whole paper.\n\n1. The proof for Theorem 1 is not very detailed and misses steps that are not very clear to me. For example, when computing E[\\hat{A}Z], it seems to me that the authors are assuming E[X/Y] = E[X]/E[Y] which is not true, or they are using taylor approximation in which case, the approximation holds only if Cov(X, Y) ~ 0 and Var(Y) ~ 0, both of which I am not sure are true. It would be good for the authors to elaborate on the steps involved to verify the correctness of the stated theorems. (Not only that step, but also how E[S(\\hat{A}, Z)] is computed as well, In general, it would be good if all proofs are given in sufficient detail)\n2. The authors define Diversification Distinguishability based on their proposed metric. However, later on they state that it is the same as low and high frequency information from graph signals. This part is not very clear at all.\n3. In experiments, the authors have used datasets from Geom-GCN paper but it is known that the authors of Geom-GCN misquoted the train/val/test split in their paper, it is not 60/20/20, but rather 48/32/20. So, did the authors use the 60/20/20 split in their experiment or the 48/32/20 split?\n4. The GPR-GNN model also attempts combine various frequencies in an amiable fashion for the task. It is unclear as to why this method achieves higher performance than GPR-GNN model. In fact, there is another work which attempts to do something similar [A]. However, this method is compared with in the paper. It would be good to have some reasoning for why models like GPR-GNN fall behind the proposed approach.\n\n[A] Beyond Low-frequency Information in Graph Convolutional Networks, Deyu Bo, Xiao Wang, Chuan Shi, Huawei Shen, https://arxiv.org/abs/2101.00797", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitation of the proposed Channel Mixing model through the limitations of Diversification Distinguishability metric. However, as said earlier, the connection between Diversification Distinguishability and Channel Mixing model is not very clear and hence it is unclear how the said limitations. For example, they calculate DD_{A,X}(G) for Pubmed to be 0.1889 which is lower DD_{A,X}(G) for other datasets (Appendix G), but in the experimental section, we see that ACM-GCN performs better than other models on Pubmed. This discrepancy in results is not very clear.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "41OHEcPSO3", "reviewer": "Reviewer_bgkm", "summary": "This paper investigates the influence of heterophily on the node classification task of GNNs. They found that not all heterophily cases are baneful for GNNs and propose a similarity matrix to provide a more accurate description of the heterophily degree of graphs. Compared with existing matrices, the proposed matrix can provide more reasonable insights. After, they propose an Adaptive Channel Mixing (ACM) framework to unleash the power of vanilla GNNs on heterophily graphs.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 can be split into several parts: introducing new metric for measuring heterophily, proposing adaptive channel mixing framework, and experimental comparison.  \n\nThe new metric is nicely explained with a motivational example. It's clear that the value of the new metric is different from the commonly used ones. However, I'm not certain how theorem 1 explains the performance of the models on low-homphily regime and how it supports the aforementioned claim. \n\nThe proposed model is based on adaptive channel mixing, which introduces low-pass and high-pass filters. This is very similar to the work [1] in which the model FAGCN combines two signals in the same model. However, this model is not discussed and compared in the experiments. Adding the discuss and comparison with this model is essential for this work. \n\nExperiments thoroughly demonstrate that the proposed ACM-GNN model achieves SOTA performance on many datasets. \n\nOther questions to the authors: \n* Why there is a little bump in Figure 2d at the high values of H_agg? \n\n[1] Beyond Low-frequency Information in Graph Convolutional Networks. Bo et al. 2021-AAAI", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The ways GNNs handle graph data with variations on homophily/heterophily has received a great deal of attention in the recent literature, and the submissions aims to provide new tools (metrics) for studying this question. The paper did not strike any reviewer as a critical addition to the literature, and concerning issues were surfaced regarding a main proof (Thm 1). After several exchanges between the authors and a reviewer, the authors acknowledged that their proof needed repair, and presented a new set of assumptions that revised the theorem statement and proved the revised statement. After a discussion between the AC and SAC, it was agreed that this sort of a revision is beyond the scope of what can reasonably be handled within the NeurIPS response period. Handling it properly requires a full R&R loop akin to a journal review cycle, where the full set of reviewers are re-activated to consider how the change in assumptions change their interpretation of the significance of the result, not to mention checking the new proof. This is simply beyond what the NeurIPS response period can handle. I therefore encourage the authors to resubmit a revised manuscript to a future venue for a full review, as the work was generally well received. 

Decision: Reject