Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
Year: 2021

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

Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using1 the graph structures based on the relational inductive bias (homophily assumption).2 Though GNNs are believed to outperform NNs in real-world tasks, performance3 advantages of GNNs over graph-agnostic NNs seem not generally satisfactory.4 Heterophily has been considered as a main cause and numerous works have been5 put forward to address it. In this paper, we first show that not all cases of heterophily6 are harmful for GNNs with aggregation operation. Then, we propose new metrics7 based on a similarity matrix which considers the influence of graph structure and8 input features on GNNs. The metrics demonstrate advantages over the commonly9 used homophily metrics by tests on synthetic graphs. From the metrics and the10 observations, we find some cases of harmful heterophily can be addressed by11 diversification operation. With this fact and knowledge of filterbanks, we propose12 the Adaptive Channel Mixing (ACM) framework to adaptively exploit aggregation,13 diversification and identity operations in each GNN layer to address harmful14 heterophily. We validate the ACM-augmented baselines with 11 real-world node15 classification tasks. They consistently achieve significant performance gain and16 exceed the state-of-the-art GNNs on most of the tasks without incurring significant17 computational burden.18
1 Introduction19
Deep Neural Networks (NNs) [18] have revolutionized many machine learning areas, including20 image recognition [17], speech recognition [10] and natural language processing [2], etc.One major21 strength is their capacity and effectiveness of learning latent representation from Euclidean data.22 Recently, the focus has been put on its applications on non-Euclidean data [4], e.g., relational data23 or graphs. Combining graph signal processing and convolutional neural networks [19], numerous24 Graph Neural Networks (GNNs) [29, 7, 12, 30, 15, 24] have been proposed which empirically out-25 perform traditional neural networks on graph-based machine learning tasks, e.g., node classification,26 graph classification, link prediction and graph generation, etc.GNNs are built on the homophily27 assumption[26], i.e., connected nodes tend to share similar attributes with each other [11], which28 offers additional information besides node features. Such relational inductive bias [3] is believed to29 be a key factor leading to GNNs’ superior performance over NNs’ in many tasks.30
Nevertheless, growing evidence shows that GNNs do not always gain advantages over traditional NNs31 when dealing with relational data. In some cases, even simple Multi-Layer Perceptrons (MLPs) can32 outperform GNNs by a large margin [35, 22, 5]. An important reason for the performance degradation33 is believed to be the heterophily problem, i.e., connected nodes tend to have different labels which34 makes the homophily assumption fail. Heterophily challenge has received attention recently and35 there are increasing number of models being put forward to address this problem [35, 22, 5, 34, 33].36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Contributions In this paper, we first demonstrate that not all heterophilous graphs are harmful for37 aggregation-based GNNs and the existing metrics of homophily are insufficient to decide whether the38 aggregation operation will make nodes less distinguishable or not. By constructing a similarity matrix39 from backpropagation analysis, we derive new metrics to depict how much GNNs are influenced by40 the graph structure and node features. We show the advantage of our metrics over the existing metrics41 by comparing the ability of characterizing the performance of two baseline GNNs on synthetic graphs42 of different levels of homophily. From the similarity matrix, we find that diversification operation43 is able to address some harmful heterophily cases, and then based on which we propose Adaptive44 Channel Mixing (ACM) GNN framework. The experiments on the synthetic datasets, real-world45 datasets and the ablation studies consistently show that baseline GNN augmented by ACM framework46 is able to obtain significant performance boost on node classification tasks on heterophilous graphs.47
The rest of this paper is mainly organized as follows: In section 2, we introduce the notation and the48 background knowledge. In section 3, we conduct node-wise heterophily analysis, derive new metrics49 based on a similarity matrix and conduct experiments to show their advantage. In section 4.3, we50 propose the ACM-GNN framework to adaptively utilize the information from different filterbank51 channels to address heterophily problem. In section 5, we discuss the related works and clarify52 the differences to our method. In section 6, we provide empirical evaluations on ACM framework,53 including ablation study and tests on 11 real-world node classification tasks.54
2 Preliminaries55
We introduce the related notation and background knowledge. We use bold fonts for vectors (e.g.,56 v). Suppose we have an undirected connected graph G = (V, E , A), where V is the node set with57 |V| = N ; E is the edge set without self-loop; A 2 RN⇥N is the symmetric adjacency matrix with58 Ai,j = 1 iff eij 2 E , otherwise Ai,j = 0. We use D to denote the diagonal degree matrix of G, i.e.,59 Di,i = di = P j Ai,j and use Ni to denote the neighborhood set of node i, i.e., Ni = {j : eij 2 E}.60 A graph signal is a vector x 2 RN defined on V , where xi is defined on the node i. We also have a61 feature matrix X 2 RN⇥F , whose columns are graph signals and whose i-th row Xi,: is a feature62 vector of node i. We use Z 2 RN⇥C to denote the label encoding matrix, whose i-th row Zi,: is the63 one-hot encoding of the label of node i. The i-th column of the identity matrix I is denoted by ei.64
2.1 Graph Laplacian, Affinity Matrix and Their Variants65
The (combinatorial) graph Laplacian is defined as L = D A, which is Symmetric Positive66 Semi-Definite (SPSD) [6]. Its eigendecomposition gives L = U⇤UT , where the columns ui of67 U 2 RN⇥N are orthonormal eigenvectors, namely the graph Fourier basis, ⇤ = diag( 1, . . . , N )68 with 1  · · ·  N , and these eigenvalues are also called frequencies. The graph Fourier transform69 of the graph signal x is defined as xF = U 1x = UTx = [uT1 x, . . . ,uTNx]
T , where uTi x is the70 component of x in the direction of ui.71
In additional to L, some variants are also commonly used, e.g., the symmetric normalized Laplacian72 Lsym = D 1/2LD 1/2 = I D 1/2AD 1/2 and the random walk normalized Laplacian Lrw =73 D 1 L = I D 1A. The affinity (transition) matrices can be derived from the Laplacians, e.g.,74 Arw = I Lrw = D 1A, Asym = I Lsym = D 1/2AD 1/2 and are considered to be low-pass75 filters [25]. Their eigenvalues satisfy i(Arw) = i(Asym) = 1 i(Lsym) = 1 i(Lrw) 2 ( 1, 1].76 Applying the renormalization trick [15] to affinity and Laplacian matrices respectively leads to77 Âsym = D̃ 1/2ÃD̃ 1/2 and L̂sym = I Âsym, where Ã ⌘ A+ I and D̃ ⌘ D+ I . The renormalized78 affinity matrix essentially adds a self-loop to each node in the graph, and is widely used in Graph79 Convolutional Network (GCN) [15] as follows,80
Y = softmax(Âsym ReLU(ÂsymXW0) W1) (1)
where W0 2 RF⇥F1 and W1 2 RF1⇥O are learnable parameter matrices. GCN can be trained by81 minimizing the following cross entropy loss82
L = trace(ZT log Y ) (2)
where log(·) is a component-wise logarithm operation. The random walk renormalized matrix83 Ârw = D̃ 1Ã, which shares the same eigenvalues as Âsym, can also be applied in GCN. The84
corresponding Laplacian is defined as L̂rw = I Ârw. Ârw is essentially a random walk matrix and85 behaves as a mean aggregator that is applied in spatial-based GNNs [12, 11]. To bridge the spectral86 and spatial methods, we use Ârw in the paper.87
2.2 Metrics of Homophily88
The metrics of homophily are defined by considering different relations between node labels and89 graph structures defined by adjacency matrix. There are three commonly used homophilies: edge90 homophily [1, 35], node homophily [28], and class homophily [21] 1 defined as follows:91
Hedge(G) = {euv | euv 2 E , Zu,: = Zv,:}
|E| , Hnode(G) =
1 |V| X
v2V
{u | u 2 Nv, Zu,: = Zv,:}
dv ,
Hclass(G) = 1
C 1
CX
k=1
" hk
{v | Zv,k = 1}
N
#
+
, hk =
P v2V {u | Zv,k = 1, u 2 Nv, Zu,: = Zv,:}
P v2{v|Zv,k=1} dv
(3) where [a]+ = max(a, 0); hk is the class-wise homophily metric [21]. They are all in the range92 of [0, 1] and a value close to 1 corresponds to strong homophily while a value close to 0 indicates93 strong heterophily. Hedge(G) measures the proportion of edges that connect two nodes in the same94 class; Hnode(G) evaluates the average proportion of edge-label consistency of all nodes; Hclass(G)95 tries to avoid the sensitivity to imbalanced class, which can cause Hedge misleadingly large. The96 above definitions are all based on the graph-label consistency and imply that the inconsistency will97 cause harmful effect to GNNs. With this in mind, we will show a counter example to illustrate the98 insufficiency of the above metrics and propose new metrics.99
3 Analysis of Heterophily100
3.1 Motivation and Aggregation Homophily101
Heterophily is believed to be harmful for102 message-passing based GNNs [35, 28, 5] be-103 cause intuitively features of nodes in different104 classes will be falsely mixed and this will lead105 nodes indistinguishable [35]. Nevertheless, it106 is not always the case, e.g., the bipartite graph107 shown in Figure 1 is highly heterophilous ac-108 cording to the homophily metrics in (3), but109 after mean aggregation, the nodes in classes 1110 and 2 only exchange colors and are still dis-111 tinguishable. Authors in [5] also point out the112 insufficiency of Hnode by examples to show that113 different graph typologies with the same Hnode114 can carry different label information.115
To analyze to what extent the graph structure can affect the output of a GNN, we first simplify the116 GCN by removing its non-linearity as [31]. Let Â 2 RN⇥N denote a general aggregation operator.117 Then, equation (1) can be simplified as,118
Y = softmax(ÂXW ) = softmax(Y 0) (4)
After each gradient decent step W = @L@W , where is the learning rate, and the update of Y 0 will119 be (see Appendix B for derivation),120
Y 0 = ÂX W = ÂX @L @W / ÂX @L @W = ÂXXT ÂT (Z Y ) = S(Â,X)(Z Y ) (5)
where S(Â,X) ⌘ ÂX(ÂX)T is a node similarity matrix after aggregation, Z Y is the prediction121 error matrix. The update direction of node i is essentially a weighted sum of the prediction error, i.e.,122 (Y 0)i,: = P j2V h S(Â,X) i
i,j (Z Y )j,:.123
1The authors in [21] did not name this homophily metric. We name it class homophily based on its definition.
To study the effect of heterophily, we define the aggregation similarity score.124 Definition 1. Aggregation similarity score125
Sagg
⇣ S(Â,X) ⌘ =
n v Meanu {S(Â,X)v,u|Zu,: = Zv,:}
Meanu {S(Â,X)v,u|Zu,: 6= Zv,:} o |V|
(6) where Meanu ({·}) takes the average over u of a given multiset of values or variables.126
Sagg(S(Â,X)) is the proportion of nodes v 2 V that will put relatively larger similarity weights on127 nodes in the same class than in other classes after aggregation. It is easy to see that Sagg(S(Â,X)) 2128 [0, 1]. But in practice, we observe that in most datasets, we will have Sagg(S(Â,X)) 0.5. Based on129 this observation, we rescale (6) to the following modified aggregation similarity for practical usage,130
S M agg
⇣ S(Â,X) ⌘ = h 2Sagg ⇣ S(Â,X) ⌘ 1 i
+ (7)
In order to measure the consistency between labels and graph structures without considering node131 features and make a fair comparison with the existing homophily metrics in (3), we define the graph132 (G) aggregation (Â) homophily and its modified version as133
Hagg(G) = Sagg ⇣ S(Â, Z) ⌘ , H M agg(G) = SMagg ⇣ S(Â, Z) ⌘ (8)
In practice, we will only check Hagg(G) when HMagg(G) = 0. As Figure 1 shows, when Â = Ârw,134 Hagg(G) = HMagg(G) = 1. Thus, this new metric reflects the fact that nodes in classes 1 and 2 are still135 highly distinguishable after aggregation, while other metrics mentioned before fail to capture the136 information and misleadingly give value 0. This shows the advantage of Hagg(G) and HMagg(G) by137 additionally considering information from aggregation operator Â and the similarity matrix.138
To comprehensively compare HMagg(G) and the metrics in (3) in terms of how they reveal the influence139 of graph structure on the GNN performance, we generate synthetic graphs and evaluate SGC [31]140 and GCN [15] on them in the next subsection.141
3.2 Evaluation and Comparison on Synthetic Graphs142
Data Generation & Experimental Setup For one dataset, we generate 95 graphs in total with 19143 edge homophily levels varied from 0.05 to 0.95, each corresponding to 5 graphs. For every generated144 graph, we have 5 classes with 400 nodes in each class. In each class, there are randomly generated145 800 intra-class edges and [(800 800Hedge(G)) /Hedge(G)]2 inter-class edges. The features of nodes146 in each class are sampled from node features in the corresponding class of the base dataset. Nodes147 are randomly split into 60%/20%/20% for train/validation/test. We train 1-hop SGC (sgc-1 [31] and148 GCN [15] on synthetic data (see appendix A.1 for hyperparameter searching range). For each value149 of Hedge(G), we take the average test accuracy and standard deviation of runs over 5 generated graphs.150 For each generated graph, we also calculate its Hnode(G), Hclass(G) and HMagg(G). Model performance151 with respect to different homophily values are shown in Figure 2.
152
2According to (3), Hedge(G) = #intra-class edges/(#intra-class edges +#inter-class edges)
Comparison of Homophily Metrics The performance of SGC-1 and GCN are expected to be153 monotonically increasing with a proper and informative homophily metric. However, Figure 2(a)(b)(c)154 show that the performance curves under Hedge(G), Hnode(G) and Hclass(G) are U -shaped 3, while155 Figure 2(d) reveals a nearly monotonic curve with a little perturbation around 1. This indicates that156 H
M agg(G) can describe how the graph structure affects the performance of SGC-1 and GCN.157
In addition, we notice that in Figure 2(a), both SGC-1 and GCN get the worst performance on all158 datasets when Hedge(G) is around somewhere between 0.1 and 0.2. This interesting phenomenon can159 be explained by the following theorem.160
Theorem 1. (See Appendix C for proof). Suppose there are C classes in the graph G, edges for each161 node are i.i.d.generated such that each edge of any node has probability h of connecting with nodes in162 the same class and probability 1 h of connecting with nodes in different classes, and E(dv) = d for163 all nodes. Let the aggregation operator Â = Ârw. Then, for nodes v, u1 and u2, where Zu1,: = Zv,:164 and Zu2,: 6= Zv,:, we have165
g(h) ⌘ E ⇣ S(Â, Z)v,u1 ⌘ E ⇣ S(Â, Z)v,u2 ⌘ =
✓ (C 1)(hd+ 1) (1 h)d
(C 1)(d+ 1)
◆2 (9)
and the minimum of g(h) is reached at
h = d+ 1 C
Cd = dintra/h+ 1 C C(dintra/h) ) h = dintra Cdintra + C 1
where dintra = dh, which is the expectation of the number of neighbors of a node that have the same166 label as the node.167
The value of g(h) in (9) is the expected differences of the similarity values between nodes in the168 same class as v and nodes in other classes. g(h) is strongly related to the definition of aggregation169 homophily and its minimum potentially implies the worst value of Hagg(G). In the synthetic experi-170 ments, we have dintra = 2, C = 5 and the minimum of g(h) is reached at h = 1/7 ⇡ 0.14, which171 corresponds to the lowest point in the performance curve in Figure 2(a). In other words, the h where172 SGC-1 and GCN perform worst is where g(h) gets the smallest value, instead of the point with the173 smallest edge homophily value. This again shows the advantage of Hagg(G) over Hedge(G) by taking174 use of the similarity matrix.175
4 Adaptive Channel Mixing (ACM) Framework176
4.1 How Diversification Operation Helps with Harmful Heterophily177
We first consider the example shown in Figure 3. From S(Â,X), nodes 1,3 assign relatively large178 positive weights to nodes in class 2, which will negatively affect information aggregation. Despite179 the fact, we can still distinguish between nodes 1,3 and 4,5,6,7 by considering their neighborhood180
3A similar J-shaped curve is found in [35], though using different data generation processes. It does not mention the insufficiency of edge homophily.
difference: nodes 1,3 are distinguishable from their neighbors while nodes 4,5,6,7 are homogeneous to181 their neighbors. This indicates, in some cases, although some nodes become similar after aggregation,182 they are still distinguishable via surrounding dissimilarities. This suggests the possibility of using183 diversification operation to address harmful heterophily i.e., high-pass (HP) filter I Â [8] (will be184 introduced in next subsection). As S(I Â, Z) in Figure 3 shows, nodes 1,3 assign negative weights185 to nodes 4,5,6,7, i.e., nodes 1,3 treat nodes 4,5,6,7 as negative samples and will move away from186 them. Base on this example, we propose diversification distinguishability as follows,187
Definition 2. Diversification Distinguishability (DD) based on S(I Â,X).188
Given S(I Â,X), a node v is diversification distinguishable if the following two conditions are189 satisfied at the same time,190
1. Meanu ⇣ {S(I Â,X)v,u|u 2 V ^ Zu,: = Zv,:} ⌘ 0;
2. Meanu ⇣ {S(I Â,X)v,u|u 2 V ^ Zu,: 6= Zv,:} ⌘  0
(10)
Then, graph diversification distinguishability value is defined as191
DDÂ,X(G) = 1
|V|
{v|v is diversification distinguishable} (11)
DDÂ,X(G) 2 [0, 1] measures the proportion of nodes that HP filter is helpful for. Its effectiveness192 can be proved for binary classification problems under certain conditions, leading us to:193
Theorem 2. (See Appendix E for proof). Suppose X = Z, Â = Ârw. Then, for a binary classifica-194 tion problem, i.e., C = 2, all nodes are diversification distinguishable and DDÂ,Z(G) = 1.195
Conducting both aggregation and diversification operations to distinctively extract the low- and high-196 frequency information from graph signals is the same as using filterbanks in graph signal processing.197 We introduce filterbanks in next subsection.198
4.2 Filterbank in Spectral and Spatial Forms199
Filterbank For the graph signal x defined on G, a 2-channel linear (analysis) filterbank [8] 4200 includes a pair of filters HLP, HHP, where HLP and HHP retain the low-frequency and high-frequency201 content of x, respectively.202
Most existing GNNs are under uni-channel filtering architecture [15, 30, 12] with either HLP or203 HHP channel that only partially preserves the input information. Unlike the uni-channel architecture,204 filterbanks with HLP + HHP = I will not lose any information of the input signal, i.e., perfect205 reconstruction property [8, 27].206
Generally, the Laplacian matrices (Lsym, Lrw, L̂sym, L̂rw) can be regarded as HP filters [8] and affinity207 matrices (Asym, Arw, Âsym, Ârw) can be treated as LP filters [25, 11]. Moreover, MLPs can be208 considered as owing a special identity filterbank with matrix I that satisfies HLP +HHP = I +0 = I .209
Filterbank in Spatial Form Filterbank methods can also be extended to spatial GNNs. Formally,210 on the node level, left multiplying HLP and HHP on x performs as aggregation and diversification211 operations, respectively. For example, suppose HLP = Â and HHP = I Â, then for node i we have212
(HLPx)i = X
j2{Ni[i}
Âi,jxj , (HHPx)i = xi X
j2{Ni[i}
Âi,jxj (12)
where Âi,j is the connection weight between two nodes. To leverage HP and identity channels in213 GNNs, we propose the Adaptive Channel Mixing (ACM) architecture in the following subsection.214
4In graph signal processing, an additional synthesis filter [8] is required to form the 2-channel filterbank. But synthesis filter is not needed in our framework, so we do not introduce it in our paper.
4.3 Adaptive Channel Mixing(ACM) GNN Framework215
ACM framework can be applied in lots of baseline GNNs and in this subsection, we use GCN as an216 example and introduce ACM framework in matrix form. We use HLP and HHP to represent general217 LP and HP filters. The ACM framework includes 3 steps as follows,218 Step 1. Feature Extraction for Each Channel: H
l L = HLPReLU H l 1 W l 1 L , H l H = HHPReLU H l 1 W l 1 H , H l I = I ReLU H l 1 W l 1 I ,
W l 1 L , W l 1 H , W l 1 I 2 R Fl 1⇥Fl ; Step 2. Feature-based Weight Learning with Row Normalization (RN): H̃
l I = RN H l I , H̃ l L = RN H l L , H̃ l H = RN H l H ;
↵ l L =
⇣ ELU ⇣ H̃
l LW̃ l L
⌘⌘ , ↵
l H =
⇣ ELU ⇣ H̃
l HW̃ l H
⌘⌘ ,↵
l I =
⇣ ELU ⇣ H̃
l IW̃ l I
⌘⌘ ,
W̃ l 1 L , W̃ l 1 H , W̃ l 1 I 2 R Fl⇥1; Step 3. Channel Mixing: H
l = diag(↵lL)H l L + diag(↵ l H)H l H + diag(↵ l I)H l I .
(13) ACM-GCN first implements distinct non-linear feature extractions for 3 channels, respectively. After219 processed by a set of filterbanks, 3 filtered components H lL, H l H , H l I are obtained. Different nodes220 may have different needs for the information in the 3 channels, e.g., in Figure 3, nodes 1,3 demand221 high-frequency information while node 2 only needs low-frequency information. To adaptively exploit222 information from different channels, ACM-GCN learns rowwise (nodewise) feature-conditioned223 (un-normalized) weights to combine the 3 channels. ACM can be easily plugged into spatial GNNs by224 replacing HLP and HHP by aggregation and diversification operations as shown in (12). See Appendix225 F for a detailed discussion of model comparison on synthetic datasets.226
Complexity Number of learnable parameters in layer l of ACM-GCN is 3Fl 1(Fl + 1), while it is227 Fl 1Fl in GCN. The computation of step 1-3 takes NFl(20 + Fl 1) + 2Fl(nnz(HLP) + nnz(HHP))228 flops, while GCN layer takes 2NFl 1Fl + 2Fl(nnz(HLP)) flops, where nnz(·) is the number of229 non-zero elements. A detailed experiments on running time is conducted in section 6.1.230
Limitations Diversification operation does not work well in all harmful heterophily cases. For231 example, consider an imbalanced dataset where several small clusters with distinctive labels are232 densely connected to a large cluster. In this case, the surrounding differences of nodes in small233 clusters are similar, i.e., the neighborhood differences are mainly from their connection to the same234 large cluster, and this possibly makes diversification operation fail to discriminate them. See a more235 detailed demonstration and discussion in Appendix G.236
5 Prior Work237
GNNs on Addressing Heterophily We discuss relevant work of GNNs on addressing heterophily238 challenge in this part. [1] acknowledges the difficulty of learning on graphs with weak homophily239 and propose MixHop to extract features from multi-hop neighborhood to get more information.240 Geom-GCN [28] precomputes unsupervised node embeddings and uses graph structure defined by241 geometric relationships in the embedding space to define the bi-level aggregation process. [13]242 proposes measurements based on feature smoothness and label smoothness that are potentially243 helpful to guide GNNs on dealing with heterophilous graphs. H2GCN [35] combines 3 key designs244 to address heterophily: (1) ego- and neighbor-embedding separation; (2) higher-order neighborhoods;245 (3) combination of intermediate representations. CPGNN [34] models label correlations by the246 compatibility matrix, which is beneficial for heterophily settings, and propagates a prior belief247 estimation into GNNs by the compatibility matrix. GPRGNN [5] uses learnable weights that can be248 both positive and negative for feature propagation, it allows GRPGNN to adapt heterophily structure249 of graph and is able to handle both high and low frequency parts of the graph signals.250
GNNs with Filterbanks Previously, there are geometric scattering networks [9, 27] that apply251 filterbanks to address over-smoothing [20] problem. The scattering construction captures different252 channels of variation from node features or labels. In geometric learning and graph signal processing,253 the band-pass filtering operations extract geometric information beyond smooth signals, thus it is254 believed that filterbanks can alleviate over-smoothing in GNNs. In ACM framework, we aim to255
design a framework with the help of filterbanks to adaptively utilize different channels to address the256 challenge of learning on heterophilous graph. We deal with different problem as in [9, 27].257
6 Experiments on Real-World Datasets258
In this section, we evaluate ACM framework on real-world datasets. We first conduct ablation studies259 in subsection 6.1 to validate different components. Then, we compare with the state-of-the-arts260 models in subsection 6.2.261
6.1 Ablation Study & Efficiency262
We investigate the effectiveness and efficiency of adding HP, identity channels and the adaptive mixing263 mechanism in ACM framework by ablation study. Specifically, we apply the above components to264 SGC-1 and GCN separately, run 10 times on each dataset used in [28] with 60%/20%/20% random265 splits for train/validation/test and report the average test accuracy as well as the standard deviation.266 We also record the average running time per epoch(in milliseconds)/average total running time(in267 seconds) to compare the efficiency. (See Appendix A for hyperparameter searching space.)268
From the results we can see that on most datasets, the additional HP and identity channels are helpful,269 even on strong homophily datasets, such as Cora, CiteSeer and PubMed. The adaptive mixing270 mechanism also shows its advantage over the method that directly adds the three channels together.271 This illustrates the necessity of learning to customize the channel usage adaptively for different nodes.272 As for efficiency, we can see that the running time is approximately doubled in ACM framework than273 the original model.274
6.2 Comparison with State-of-the-art Models275
Datasets & Experimental Setup In this section, we implement SGC [31] with 1 hop and 2 hop276 (SGC-1, SGC-2), GCN [15] and GraphSAGE and apply them [12] in ACM framework: we use277 Ârw and mean aggregator as LP filter and the corresponding HP filter can be derived from (12).278 We compare them with several baselines and state-of-the-art models: MLP with 2 layers (MLP-2),279 GAT [30], APPNP [16], GPRGNN [5], H2GCN [35], MixHop [1], GCN+JK [15, 32, 21], GAT+JK280 [30, 32, 21] and Geom-GCN [28]. Besides the 9 benchmark datasets used in [28], we further tests281 the above models on 2 new benchmark datasets, Deezer-Europe and YelpChi, that are proposed in282
[21]5. We test these models 10 times on Cornell, Wisconsin, Texas, Film, Chameleon, Squirrel, Cora,283 Citeseer and Pubmed following the same early stopping strategy, the same data splitting and Adam284 [14] optimizer used in GPRGNN [5]. For Deezer-Europe and YelpChi, we test the above models285 5 times with the same early stopping strategy, the same splits and AdamW [23] used in [21]. The286 details of hyperparameter search are reported in appendix A.287
The main results of this set of experiments with statistics of datasets are summarized in Table 2, where288 we report the mean accuracy and standard deviation. We can see that after applied in ACM framework,289 the performance of baseline models are boosted on almost all tasks. Especially, ACM-GCN performs290 the best in terms of average rank (1.73) across all datasets and achieves SOTA performance on 6 out291 of 11 datasets. Overall, It suggests that ACM framework can help GNNs to generalize better on node292 classification tasks on heterophilous graphs.293
7 Future Work294
The similarity matrix and the new metrics defined in this paper mainly capture the linear relations295 of the aggregated nodes. But this might be insufficient sometimes when nonlinearity information in296 feature vectors are important for classification. In the future, similarity matrix that is able to capture297 nonlinear relations between nodes can be proposed to define new homophily metrics.298
From experimental results, the standard deviation of ACM-GNNs are relatively higher than GNNs on299 some tasks and this is suspiciously caused by the feature-based weight learning mechanism. In the300 future, a stabilizer or a more robust weight learning method can be proposed to reduce the variance.301
8 Social Impact302
We do not find any direct path of this work to any negative social impact.303
5The 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 we choose them.
References304 [1] S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan,305 G. Ver Steeg, and A. Galstyan. Mixhop: Higher-order graph convolutional architectures306 via sparsified neighborhood mixing. In international conference on machine learning, pages307 21–29. PMLR, 2019.308
[2] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align309 and translate. arXiv preprint arXiv:1409.0473, 2014.310
[3] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski,311 A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep312 learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.313
[4] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning:314 going beyond euclidean data. arXiv, abs/1611.08097, 2016.315
[5] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph316 neural network. In International Conference on Learning Representations. https://openreview.317 net/forum, 2021.318
[6] F. R. Chung and F. C. Graham. Spectral graph theory. Number 92. American Mathematical319 Soc., 1997.320
[7] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs321 with fast localized spectral filtering. arXiv, abs/1606.09375, 2016.322
[8] V. N. Ekambaram. Graph structured data viewed through a fourier lens. University of California,323 Berkeley, 2014.324
[9] F. Gao, G. Wolf, and M. Hirn. Geometric scattering for graph data analysis. In International325 Conference on Machine Learning, pages 2122–2131. PMLR, 2019.326
[10] A. Graves, A.-r. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural327 networks. In 2013 IEEE international conference on acoustics, speech and signal processing,328 pages 6645–6649. Ieee, 2013.329
[11] W. L. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and330 Machine Learning, 14(3):1–159, 2020.331
[12] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs.332 arXiv, abs/1706.02216, 2017.333
[13] Y. Hou, J. Zhang, J. Cheng, K. Ma, R. T. Ma, H. Chen, and M.-C. Yang. Measuring and334 improving the use of graph information in graph neural networks. In International Conference335 on Learning Representations, 2019.336
[14] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint337 arXiv:1412.6980, 2014.338
[15] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks.339 arXiv, abs/1609.02907, 2016.340
[16] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks341 meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.342
[17] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional343 neural networks. In Advances in neural information processing systems, pages 1097–1105,344 2012.345
[18] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. nature, 521(7553):436, 2015.346
[19] Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, et al. Gradient-based learning applied to document347 recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.348
[20] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi-supervised349 learning. arXiv, abs/1801.07606, 2018.350
[21] D. Lim, X. Li, F. Hohne, and S.-N. Lim. New benchmarks for learning on non-homophilous351 graphs. arXiv preprint arXiv:2104.01404, 2021.352
[22] M. Liu, Z. Wang, and S. Ji. Non-local graph neural networks. arXiv preprint arXiv:2005.14612,353 2020.354
[23] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint355 arXiv:1711.05101, 2017.356
[24] S. Luan, M. Zhao, X.-W. Chang, and D. Precup. Break the ceiling: Stronger multi-scale deep357 graph convolutional networks. arXiv preprint arXiv:1906.02174, 2019.358
[25] T. Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint359 arXiv:1905.09550, 2019.360
[26] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social361 networks. Annual review of sociology, 27(1):415–444, 2001.362
[27] Y. Min, F. Wenkel, and G. Wolf. Scattering gcn: Overcoming oversmoothness in graph363 convolutional networks. arXiv preprint arXiv:2003.08414, 2020.364
[28] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gcn: Geometric graph convolutional365 networks. arXiv preprint arXiv:2002.05287, 2020.366
[29] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural367 network model. IEEE transactions on neural networks, 20(1):61–80, 2008.368
[30] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention369 networks. arXiv, abs/1710.10903, 2017.370
[31] F. Wu, T. Zhang, A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph371 convolutional networks. arXiv preprint arXiv:1902.07153, 2019.372
[32] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning373 on graphs with jumping knowledge networks. In J. Dy and A. Krause, editors, Proceedings of374 the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine375 Learning Research, pages 5453–5462. PMLR, 10–15 Jul 2018.376
[33] Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra. Two sides of the same coin:377 Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint378 arXiv:2102.06462, 2021.379
[34] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph neural380 networks with heterophily. arXiv preprint arXiv:2009.13566, 2020.381
[35] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph382 neural networks: Current limitations and effective designs. Advances in Neural Information383 Processing Systems, 33, 2020.384
Checklist385 1. For all authors...386
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s387 contributions and scope? [Yes]388
(b) Did you describe the limitations of your work? [Yes] In the Appendix G, we discussion389 cases that high-pass filter cannot tackle.390
(c) Did you discuss any potential negative societal impacts of your work? [No] It is in391 Section 8, we have not come up with significant social negative impact.392
(d) Have you read the ethics review guidelines and ensured that your paper conforms to393 them? [Yes]394
2. If you are including theoretical results...395 (a) Did you state the full set of assumptions of all theoretical results? [Yes] In Section396 3&4, we mainly define a new homophily metric and it is followed by two theorems.397 (b) Did you include complete proofs of all theoretical results? [Yes] In Appendix B&C&398 E, we justify the new metric and two theorems.399 3. If you ran experiments...400
(a) Did you include the code, data, and instructions needed to reproduce the main experi-401 mental results (either in the supplemental material or as a URL)? [Yes] The settings are402 provided in details and the source code is submitted in the supplemental material.403
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they404 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-406 iments multiple times)? [Yes] We include average test accuracy of times of running407 with standard deviation.408
(d) Did you include the total amount of compute and the type of resources used (e.g., type409 of GPUs, internal cluster, or cloud provider)? [Yes] We include hardware details in410 Appendix, which is not computationally expensive.411
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...412 (a) If your work uses existing assets, did you cite the creators? [Yes] In Section 6, we413 specify the datasets with their data split sources in footnotes.414 (b) Did you mention the license of the assets? [No]415 (c) Did you include any new assets either in the supplemental material or as a URL? [No]416 (d) Did you discuss whether and how consent was obtained from people whose data you’re417 using/curating? [No]418 (e) Did you discuss whether the data you are using/curating contains personally identifiable419 information or offensive content? [No] None included.420 5. If you used crowdsourcing or conducted research with human subjects...421
(a) Did you include the full text of instructions given to participants and screenshots, if422 applicable? [No] None included.423
(b) Did you describe any potential participant risks, with links to Institutional Review424 Board (IRB) approvals, if applicable? [No] None included.425
(c) Did you include the estimated hourly wage paid to participants and the total amount426 spent on participant compensation? [No] None included.427

Review summaries:
The paper makes two specific points: 1. 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. 2. 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.

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. 

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.  

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.