Revisiting Heterophily For Graph Neural Networks
Authors: Sitao Luan
Chenqing Hua
Qincheng Lu
Jiaqi Zhu
Harry Zhao
Shuyuan Zhang
Xiao-Wen Chang
Doina Precup
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Homophily Metrics
Heterophily
Non-Homophilous
Heterophilic Graphs
High-pass filter
Filterbank
Adaptive Channel Mixing

Abstract: Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using graph structures based on the relational inductive bias (homophily assumption). While GNNs have been commonly believed to outperform NNs in real-world tasks, recent work has identified a non-trivial set of datasets where their performance compared to NNs is not satisfactory. Heterophily has been considered the main cause of this empirical observation and numerous works have been put forward to address it. In this paper, we first revisit the widely used homophily metrics and point out that their consideration of only graph-label consistency is a shortcoming. Then, we study heterophily from the  perspective of post-aggregation node similarity and define new homophily metrics, which are potentially advantageous compared to existing ones. Based on this investigation, we prove that some harmful cases of heterophily can be effectively addressed by local diversification operation. Then, we propose the Adaptive Channel Mixing (ACM), a framework to adaptively exploit aggregation, diversification and identity channels to extract richer localized information in each baseline GNN layer. ACM is more powerful than the commonly used uni-channel framework for node classification tasks on heterophilic graphs. When evaluated on 10 benchmark node classification tasks, ACM-augmented baselines consistently achieve significant performance gain, exceeding state-of-the-art GNNs on most  tasks without incurring significant computational burden. (Code: https://github.com/SitaoLuan/ACM-GNN)

Revisiting Heterophily For Graph Neural Networks
Sitao Luan 12, Chenqing Hual.2
Qincheng Lu', Jiaqi Zhu', Mingde Zhao 1.2, Shuyuan Zhang!
Xiao-Wer Chang', Doina Precup 1,2,3
(uan @ mail, chenqing. hua @ mail, qincheng.lue @ mail, Zhagi.zhuuunn mail, mingde zhao mail, shuyuan. shuyuan.zhang zhang @ mail, chang cs, dprecup@es) mmmcill.ca
McGill University; MMlaa "DeepMind
Abstract
Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using graph structures based on the relational inductive bias (homophily assumption). While GNNs have been commonly believed to outperform NNs in real-world tasks, recent work has identified non-trivial set of datasets where their performance compared to NNs is not satisfactory. Heterophily has been considered as the main cause of this empirical observation and numerous works have been put forward address it. In this paper, we first revisit the widely used homophily metrics and point out that their consideration of only graph-label consistency Then, we study heterophily from the perspective of post-aggregation node similarity and define new homophily metrics, which are verified to he advantageous compared to existing ones. Based on this investigation, we prove that some harmful cases of heterophily can be effectively addressed by local diversification operation. Then, we propose the Adaptive Channel Mixing (ACM), a framework to adaptively exploit aggregation, diversification and identity channels node-wisely extract richer localized information for diverse node heterophily situations. ACM is more powerful than the commonly used uni-channel framework for node classification tasks on heterophilic graphs and is easy to be implemented in baseline GNN layers. When evaluated on 10 benchmark node classification tasks, ACM-augmented baselines consistently achieve significant performance gain, exceeding state-of-the- art GNNs on most tasks without incurring significant computational burden. Code: httts:///githu.... wtwptttwb...omiittttttsaaee Stt//SStttttnnntteeeeeeea ACM GNN
shortcoming.
Introduction
Deep Neural Networks (NNs)
2 have revolutionized many machine learning areas, including
image recognition 21, speech recognition [33 and natural language processing (2), due to their
effectiveness in learning latent representations from Fuclidean data. Recent research has shifted focus on non-Fuclidean data (6)
e.g., relational data or graphs. Combining graph signal processing and numerous Graph Neural Network (GNN) architectures have been 30 which empirically outperform traditional NNs on graph-based machine learning tasks such as node classification, graph classification, link prediction and graph generation, etc. GNNs are built on the homophily assumption
convolutional neural networks 23
proposed 39 IC
[5
35 connected nodes tend to share similar attributes with each other [4], which offers additional information besides node features. This relational inductive bias 3 is believed to be a key factor leading to GNNs' superior performance over NNs in many tasks.
However, growing empirical evidence suggests that GNNs are not always advantageous compared to traditional NNs. In some cases, even simple Multi-Layer Perceptrons (MIPss) can outperform GNNs by a large margin on relational data 44 29
An important reason for this is believed to be the heterophily problem: the homophily assumption does not always hold, so connected nodes may in fact have different attributes. Heterophily has received lots of attention recently and an increasing number of models have been put forward to address this problem
32
20
24 In
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

this paper, we first show that by only considering graph-label consistency, existing homophily metries are not able to describe the effect of some cases of heterophily on aggregation- based GNNs. We propose a post-aggregation node similarity matrix, and based on it, we derive new homophily metrics, whose advantages are illustrated on synthetic graphs (Sec. ( Then, we prove that diversification operation can help to address some harmful cases of heterophily (Sec. Ap. Based on this, we propose the Adaptive Channel Mixing (ACM) GNN framework which augments uni-channel baseline GNNs, allowing them to exploit aggregation, diversification and identity channels adaptively, node-wisely and locally in each layer. ACM significantly boosts the performance of 3 uni-channel baseline GNNs by 2.04% 27.5% for node classification tasks on 7 widely used benchmark heterophilic graphs, exceeding SOTA models (Sec. O on all of them. For 3 homophilic graphs, ACM ACM-augmented GNNs can perform at least as well as the uni-channel baselines and are competitive compared with SOTA.
Contributions 1. To our knowledge, we are the first to analyze heterophily from post-aggregation node similarity perspective. 2. The proposed ACM framework is highly different from adaptive filterbank with multiple channels and existing GNNs for heterophily: 1) the traditional adaptive filterbank channels (00) uses a scalar weight for each filter and this weight is shared by all nodes. In contrast, ACM provides a mechanism so that different nodes can learn different weights to utilize information from different channels to account for diverse local heterophily; 2) Unlike existing methods that leverage the high-order filters and global property of high high-frequency signals 46 129 S [6] which require more computational resources, ACM successfully addresses heterophily by considering only the nodewise local information adaptively. 3. Unlike existing methods that try to facilitate learning filters with high expressive power 46
g 16. ACM aims that, when given a filter with certain expressive power, we can extract richer information from additional channels in certain way to address heterophily. This makes ACM more flexible and easier to be implemented.
45
2 Preliminaries
In this section, we introduce notation and background knowledge. We use bold font for vectors (e.g., v). Suppose we have an undirected connected graph
EV.E, A), where V is the node set with |/| = N; E is the edge set without self-loops; A E IR NxN is the symmetric adjacency matrix with A., = if Gij E E, otherwise A, = 0. Let D denote the diagonal degree matrix of G. i.e. Da.; = d; Σ, Aiz. Let Nr denote the neighborhood set of node i, i.e., No [j eij E E). A graph signal a vector x E INN defined on V, where x; is associated with node i. We also have a feature matrix X E IR N whose columns are graph signals and whose i-th row Xt,: is feature vector of node i. We use Z E Nx to denote the label encoding matrix, whose i-th row Z,, is the one-hot encoding of the label of node
2.1 Graph Laplacian, Affinity Matrix and Variants
The (combinatorial) graph Laplacian is defined as L = D A, which is Symmetric Positive Semi- Semi-Definite (SPSD) 9 Its eigendecomposition is UAUT, where the columns u, of U E R Nx are orthonormal eigenvectors, namely the graph Fourier basis, A = diag(Ai..... AN) with \ S ... S AN. These eigenvalues are also called frequencies.
In additional to L, some variants are also commonly used, egg., the symmetric normalized Laplacian Laym = D LD = I - D-1/2 D-1/2AD--1 AD11 and the random walk normalized Laplacian Liw = D- = - D-1A. The graph Laplacian and its variants can be considered as high-pass filters for graph signals. The affinity (transition) matrices can be derived from the Laplacians, e.g., Arw I L = DD' A, Aym = I- Lyym D A-1/2 1/2 and are considered to be low-pass filters 1 - (Tyym) = \r( E (-1,
34 Their eigenvalues satisfy (Aw = (A
Applying the renormalization trick [19 to affinity and Laplacian matrices respectively leads to
Aym A- and Leym -- Asmm where À = A + and Ó = D + I. The renormalized affinity matrix essentially adds self-loop to each node in the graph, and is widely used in Graph
Convolutional Network (GCN) 19 as follows:
Y softmax ReLU(Asm Wi)
(1)
where Wi E FXA and W1 E R x0 are learnable parameter matrices. GCNs can be trained by minimizing the following cross entropy loss
L = tracee " log Y)
(2)
2

---

where log(.) is component-wise logarithm operation. The random walk renormalized matrix Aw D- which shares the same eigenvalues as Asm. can also be applied in GCN. The corresponding Laplacian is defined as L.w I A. The matrix An is essentially a random walk matrix and behaves as mean aggregator that is applied in spatial-based GNNs [15 14. To bridge spectral and spatial methods, we use Arw in this paper.
2.2 Metrics of Homophily
The homophily metrics are defined by considering different relations between node labels and graph structures. There are three commonly used homophily metrics: edge homophily M 46]. node homophily 36 and class homophily 26 defined follows:
Hodge (G)
|eev Cuv
EE, Zu.: Z
Hnode (G) = VV
Σ DEV
H
1
{u u E No. Zu.: Zu.i
[81
1V]
dp
NEV
Zu,
Even [ul Zu,k = -1, No, Zu,: = Zu
Helass (9)= C-1
hk
h2 h==
N
Eve Zu, (vl,01Z
de
(3)
where Hiode is the local homophily value for node v; [a]+ = max(a, 0); by the class-wise homophily metric 126. All metrics are in the range of [0, 1]: value close corresponds to strong homophily, while a value close to indicates strong heterophily. Hotge(G) measures the proportion of edges that connect two nodes in the same class; Hnoee (G) evaluates the average proportion of edge-label consistency of all nodes; Helus(9) tries to avoid sensitivity to imbalanced classes, which all based on the linear feature- independent graph-label consistency. The inconsistency relation is implied to have a negative effect to the performance of GNNs. With this in mind, in the following section, we give example to illustrate the shortcomings of the above metrics and propose new reature-independen metrics that defined from post-aggregation node similarity perspective, which is novel.
make (edge()) (9) misleadingly large. The above definitions
3 Analysis of Heterophily
3.1 Motivation and Aggregation Homophily
Heterophily is widely believed to be harmful for message-passing based GNNs 46 36 & be- cause, intuitively, features of nodes in different classes will be falsely mixed, leading nodes to be indistinguishable [46]. Nevertheless, is not always the case, e.g., the bipartite grapt shown in Figure iss highly heterophilic according to the existing homophily metries in equation 3 but after mean aggregation, the nodes in classes 1 and 2 just exchange colors and are still distin- g This example tells us that, besides graph-label consistency, we need study the relation between nodes after aggregation step.
Class
Class 2
Metries:
Hedg= 0
Aggregation
Hnnde(G) -0
Hatass (G)
Hagg (G) =1
Hägg (6)
Figure 1: Example of harmless heterophily
To this end, we first define the aggs-aggregttion node similarity matrix as follows:
S(Á, x) = Áx(Âx)" E NxW
(4)
where Á NxN denotes a general aggregation operator. S(,, X) is essentially the gram matrix that measures the similarity between each pair of aggregated node features.
Relationship Between S(A, X) and Gradient of SGC SGC is one of the most simple but representative GNN models and its output can be written as:
Y = softmax Aattmax(Axra (AXW) softmax(YY)
(S)
26 did not name this homophily metric. We named it class homophily based on its definition.
33 use same example but not to demonstrate the deficiency of homophily metrics.
8 also point out the insufficiency of Hass by examples to show that different graph typologies with the same H (9) carry different label information.
3

---

With the loss function in equation after each gradient descent step, we have AW =Y "dW where the learning rate. The update of Y is (see Appendix for derivation):
dc
AY' = ÁxAw = -åx dc dW o Ax dc dW
-)
(6)
where - Y is the prediction error matrix. The update direction of the prediction for node is
essentially a weighted sum of the prediction error, i.e., A(Y"),, = Eev [S(A, X)] (.j (Z Y);s and [s(Á,)]] can be considered as the weights. Intuitively, high similarity value [S(A, i.j means node i tends to be updated to the same class node j. This indicates that S(A, X) is closely related to a single layer GNN model.
Based on the above definition and observation, we define the aggregation similarity score as follows.
Definition 1. The aggregation similarity score is:
Sage (S(A,
- -Mv -MV M (I5(A, ou. Zo.:)) 2 (eS(A( + Zn:
(7)
where Meana (1-3) lakes the average over u of a given multiset of values or variables.
Sage (S, X)) measures the proportion of nodes nodes in the same class (including v) is larger than that in other classes. In practice, we observe that in most datasets, we will have ( X)) > 0.5 To make the metric range in [0,1], like existing metries, we rescale equation to the following modified aggregation similarity.
as which the average weights on the set of
S.M. (((A
(00s, - -1]+
(8)
In order to measure the consistency between labels and graph structures without considering node features and to make fair comparison with the existing homophily metrics in equation we define the graph (9) aggregation (Å) homophily and its modified version as:
Hage (G) Sage (S(A, H.M (9) S.M (S(Á,
As the example shown in Figure I when A Áww is easy to see that Hagg (9) H (9) uge and other metrics are O. Thus, this new metric reflects the fact that nodes in classes and are still highly distinguishable after aggregation, while other metrics mentioned before fail to capture such information and misleadingly give value O. This shows the advantage of H (g) and H (9), which
additionally exploit information from aggregation operator Å and the similarity matrix.
To comprehensively compare H,M (G) with the existing metrics on their ability to elucidate the influence of graph structure on GNN performance, we generate synthetic graphs with different homophily levels and evaluate SGC 42 and GCN [9 on them in the next subsection.
Test Accuracy
1..
syne-cora .oon
syne-chameleon, gen
0.8
syne-tora, _sgc]
sync-chameleon Lsycl
sync-citesor__g _ecseerrrgccco_e
sync-squirei_ee
0.6
syne citeseer sgrl
sync sucirrulrrel sgel
0.4
syne-pubmed._
sync-fimm
sync-pubmed sgc1
sync-flim sgcl
0.2
0.0
0.8 Edge Homophily
0.0 0.4
0.0 0.2 0.8 Class Homophily
0.2 0.4 0.6 0.8 1.0 Modified Agg Homophily
Node Homophily
(a) Halge (9)
(b) mmaa(())
(c) Ham (g)
(d) H M (9)
Figure 2: Comparison of baseline performance under different homophily metrics.
'See Appendix for an intuitive explanation under certain conditions.
In practice, we will only check H9gr9) when H. (G) 0.

---

Class 1
Class 2
AXXTA A
(I A) Xx (I
A)
50
50
.50
.50
.50
.50
50
.00
67
-20
22
-20
.25
X Z
50
33
.3
56
.20
.60
.25
.58
.20
.60
.25
.58
000 .00
.00
89
.00
27
.00
-33
.00
+27
.00
.00
1: [1.0]
50
20
60
68
.65
.68
.65
.0
00
-27
08
.08
.10
2: [1.0]
.88
63
25
00
-33
.10
113
10
.13
[1,0]
50
25
60
68
.65
688
.65
.20
00
-27
00
.08
.10
[010,1]
50
.25
.58
65 .6
.5
63
25
.0
-33
.10
.13
.10
5: 5:10,1]
Large positive weighs in inter-class block for node 1,3.
Positive weights intra-class blocks, Non-negative weights blocks.
6: [0
cross-class
7: [:
Figure 3: Example of how diversification can address harmful heterophily
3.2 Empirical Evaluation and Comparison on Synthetic Graphs
In this subsection, we conduct experiments on synthetic graphs generated with different levels of Hegg(()) (9) to assess the output of Hagg (G) in comparison with existing metries.
Data Generation & Experimental Setup We first generated 10 graphs for each of 28 edge ho- mophily levels, from 0.005 to 0.95, for total of 280 graphs. In every generated graph, we had 5 classes, with 400 nodes in each class. For nodes in each class, we randomly generated 800 intra-class edges and [ (9) 800] inter-class edges. The features of nodes in each class sampled from node features the corresponding class of base datasets (Cora, CiteSeer, PubMed, Chameleon, Squirrel, Film). Nodes were randomly split into cain/validation/test sets, in proportion of 60%%/20%/2004 We trained 1-hop SGC (sge-/) - and GCN 19] on the synthetic graphs [ For each value of Hedge (g). we take the average test accuracy and standard deviation of runs over the 10 generated graphs with that value. For each generated graph, we also calculate (9) Helass and agg (9). Model performance with respect to different homophily values is shown in Figure
800
Comparison of Homophily Metrics The performance of SGC-1 and GCN is expected to be monotonically increasing if the homophily metric is informative. However, Figure 2 (a)()(c) show that the performance curves under Hedge (9), (G) and Helnss are U-shaped while Figure d) reveals nearly monotonic curve with little numerical perturbation around 1. This indicates that H HM (G) provides better indication of the way in which the graph structure affects the performance of SGC-1 and GCN than existing metrics. (See more discussion on aggregation homophily and
theoretical results for regular graphs in Appendix D
4 Adaptive Channel Mixing (ACM)
8 4 it has been shown that high-frequency graph signals, which can be extracted by high-pass filter (HP), is empirically useful for addressing heterophily. In this section, based on the similarity matrix in equation 6 we theoretically prove that diversification operation, i.e., HP filter, can address some cases of harmful heterophily locally. Besides, a node-wise analysis shows that different nodes may need different filters to process their neighborhood information. Based on the above analysis, in Sec. 4.2 we propose Adaptive Channel Mixing (ACM), a 3-channel architecture which can adaptively exploit local and node-wise information from aggregation, diversification and identity channels.
In prior work 32
4.1 Diversification Helps with Harmful Heterophily
We first consider the example shown in Figure From S(Á, relatively large positive weights to nodes in class 2 after aggregation, which will make nodes {1,3) hard be distinguished from nodes in class 2. However,
that nodes {1,3} assign
still distinguish nodes (1,3) and
(4. 5, 6, 7} by considering their neighhorhood differences: nodes (1,3} 3 are different from most of their neighbors while nodes (4, 5, 7} are similar to most of their neighbors. This indicates that
"See Appendix C.I for description of the hyperparameter searching range and Appendix D for more detailed description of the data generation process A similar J- J-shaped curve for Hotye (9) is found in 46). though using different data generation processes. The authors do not mention the insufficiency of edge homophily.
5

---

although some nodes become similar after aggregation, they are still distinguishable through their local surrounding dissimilarities.
This observation leads us introduce the diversification operation, i.e., HP filter - Á to extract information regarding neighborhood differences, thereby addressing harmful heterophily. As X) in Fig. 3 shows, nodes {1, 3/ will assign negative weights to nodes {4, 5, 6, 7) after the diversification operation, i.e, nodes 1,3 treat nodes 4,5,6,7 as negative samples and will move away from them during backpropagation. This example reveals that there are cases in which the diversification operation is helpful handle heterophily, while the aggregation operation is not. Based on this observation, we first define the diversification distinguishability of node and the graph diversification distinguishability value, which measures the proportion of nodes for which the diversification operation is potentially helpful.
Definition 2 (Diversification Distinguishability (DD) based on S(I Å, X)). Given S(T A, X), node is diversification distingusishable the following two conditions satisfied at the same time,
1. Mean., (
V VAZu: Zu: Zu: 0:
(10)
2. Mean. (I)(T-,,)),sa EVA Zui # kn 50
Then, graph diversification distinguishability value is defined as
DD x (G)
M {ule E VA is diversification distinguishablee
(11)
We can see that DD x.x (9) E [0, 1]. Based on Def. 2. the effectiveness of diversification in addressing heterophily can be theoretically proved under certain conditions:
Theorem 1. (See Appendix G for proof). For = 2, suppose X = Z, Å = A Then for any
I- -- A... all nodes are diversification distinguishable and DD (g) = 1.
With the above results for HP filters, we will now introduce the concept of filterbank which combines both LP (aggregation) and HP (diversification) filters and can potentially handle various local heterophily cases. We then develop ACM framework in the following subsection.
4.2 Filterbank and Adaptive Channel Mixing (ACM) Framework
Filterbank For the graph signal defined G, 2-channel linear (analysis) filterbank (II R includes a pair of filters HLP. Hup, which retain the low-frequee low-frequency and fighfrequency content of respec- tively. Most existing GNNs use a uni-channel filtering architecture with either LP or HP channel, which only partially pre- serves the input information. Unlike the uni-channel architecture, filterbanks with HLP + HμP = / do not lose any information from the input signal, which is called the perfect reconstruction property m1 Generally, the Laplacian matrices (Taym. Iiw, Iuym: l.rw) can be regarded as HP filters [T] and affinity matrices (Asym, Arw. Asym. A,w)) can be treated as LP filters 3E [.l. Moreover, we extend the concept of filterbank and view MLPs using the identity (full- pass) filterbank with HLP = I and HμP = O, which also satisfies HLP + HEp I 0 = I.
Local Homophily Distributions
texas film squiinel
19 [
0.0
0.8
Hi
Figure 4: H bode distributions
Node-wise Channel Mixing for Diverse Local Homophily The example in Figure 3 also shows that different nodes may need the local information extracted from different channels, e.g., nodes {1,3) demand information from the HP channel while node 2 only needs information from the LP channel. Figure 4 reveals that nodes have diverse distributions of node local homophily W across different datasets. In order to adaptively leverage the LP, HP and identity channels in GNNs to deal with the diverse local heterophily situations, we will now describe our proposed Adaptive Channel Mixing (ACM) framework.
'I graph signal processing, additional synthesis filter But synthesis filter is not needed in our framework.
is required to form the 2-channel filterbank.

---

Adaptive Channel Mixing (ACM) We will use GCN as an example to introduce the ACM framework in matrix form, but the framework can be combined in a similar manner to many different GNNs. The ACM framework includes the following steps:
Step 1. Feature Extraction for Each Channel:
Option 1: H ReI.U (HupHt-'W2 H ReL.U (IppH H ReLU (1H"-
Option 2: Hi HLP (H'-1 Hty HHRRLLU (H Hj / ReLU (H'
HD = X E NNF, W W w/-1 E E I 1,..., L;
Step 2. Row-wise Feature-based Weight Learning:
a4 Sigmoid (H) a'y = Sigmoid (HlgWH) ot. Sigmoid (n/ Wt W w R [a a at] = Softmax (([a), (aN) E RNNK3, xT,TT TE R temperature, Whin E 1
Step Node-wise Adaptive Channel Mixing:
H' ReLU (diag(a',) + diag(d')) + diag(a))H
We will refer to the instantiation which uses option in step as ACM and to the one using option as ACMII 10 In step 1, ACM(II)-GNN implement different feature extractions for 3 channels using a set of filterbanks. Three filtered components, HL H Hy, are obtained. To adaptively exploit information from each channel, ACM(II)GCN first extract nonlinear information from the filtered signals, then use W Mix to learn which channel is important for each node, leading to the row-wise weight vectors a1z, d' a1 E Nx whose i-th elements are the weights for node These three vectors are then used as weights in defining the updated H in step 3.
Complexity The number of learnable parameters in layer / of ACM(II-GCN 3F (F +9, compared to Fi-1 Fj in GCN, The computation of steps 1-3 takes N (nz(HHr) )) + 18N flops, while the GCN layer takes 2N 1 + (n HLP)) flops. where mnz(.) is the number of non- zerz elements. An ablation study and a detailed comparison on running time are conducted in Sec. 6
Limitations of Diversification Like any other method, there exists some cases of harmful het- erophily that diversification operation cannot work well. For example, suppose we have 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 mainly come from their connections to the same large cluster, and this can lead to the diversification operation failing to discriminate them. See Appendix H for more detailed discussion.
5 Related Work
We now discuss relevant work on addressing heterophily in GNNs. I|] acknowledges the difficulty of learning graphs with weak homophily and propose MixHop to extract features from multi-hop neighborhoods to get more information. [17 propose measurements based on feature smoothness and label smoothness that are potentially helpful to guide GNNs when dealing with heterophilic graphs. (Geom-GCy 36 precomputes unsupervised node embeddings and uses the graph structure defined by geometric relationships in the embedding space to define the bi-level aggregation process to handle heterophily. H2GCN 46 combines 3 key designs to address heterophily: (1) ego- and neighbor-embedding separation; (2) higher-order neighborhoods; (3) combination of intermediate representations. CPGNN A5 models label correlations through a compatibility matrix, which is beneficial for heterophilic graphs, and propagates prior belief estimation into the GNN by using the compatibility matrix. Non-local GNNs [X]] propose a simple and effective non-local aggregation framework with an efficient attention-guided sorting for GNNs. FAGCN 4 learns edge-level
aggregation weights as GAT 41 but allows the weights to be negative, which enables the network
to capture high-frequency components in the graph signals. GPRGNN N uses learnable weights that can be both positive and negative for feature propagation. This allows GPRGNN to adapt to heterophilic graphs and to handle both high- and low-frequency parts of the graph signals (See Appendix D for more comprehensive comparison between ACM-GNNs, ACMII-GNNs and FAGCN,
Sec more variants in Appendix B
10See Appendix B. for the reasons of having 2 options for ACM-GNNs.
See Appendix A.4 and A.S for more discussion of the components in ACM architecture.
7

---

GPRGNN). BernNet [16] designs scheme to learn arbitrary graph spectral filters with Bernstein polynomial address heterophily. [3 points out that homophily is not necessary for GNNs and characterizes conditions that GNNs can perform well on heterophilic graphs.
Empirical Evaluation
In this section, we evaluate the proposed ACM and ACMII framework on real-world datasets (see Appendix D.2 for performance comparison with basline models on synthetic datasets). We first conduct ablation studies in Sec. 6. to validate the effectiveness and efficiency of different components of ACM and ACMII. Then, we compare with state-of-the-an (SOTA) models in Sec. 6.2
The hyperparameter searching range and computing resources are described in Appendix
(a) Input Feature
(b) GCN Outpul
(c) ACM-GCN Output
Alpha values aL
Density
0.25
0.50
Alpha values
(d) Low-pass Channel
(e) High-pass Channel
(I) Identity Channel
Learned Weights
Figure 5: t-SNE visualization of the output layer of ACM-GCN and GCN trained on Squirrel
6.1 Ablation Study & Efficiency
We will now investigate the effectiveness and efficiency of adding HP, identity channels and the adaptive mixing mechanism in the proposed framework by performing ablation study. Specifically, we apply the components ACM to SGC-1 42 and the components of ACM and ACMII to GCN I9 separately. We run 10 times each of the 9 benchmark datatsets, Cornell, Wisconsin, Texas, Film. Chameleon, Squirrel, Cora, Citeseer and Pubmed used
37 [6), with the same 60%% random splits for train/validation/test used in [X] and report the average test accuracy as well as the standard deviation. We also record the average running time per epoch (in milliseconds) compare the computational efficiency. We the temperature 7 in equation 4.2 be which is the number of channels.
The results in Table show that most datasets, the additional HP and identity channels are helpful, even for strong homophily datasets such as Cora, CiteSeer and PubMed. The adaptive mixing mechanism also has advantage over directly adding the three channels together. This illustrates the necessity of learning to customize the chanmel usage adaptively for different nodes. The t-SNE visualization in Figure 5 demonstrates that the high-pass channel(e) and identity channel(f) can extract meaningful patterns, which the low-pass channel(d) is not able to capture. The output of ACM-
We only test ACM-SGCM SGC-I I because SGC-1 does not contain any non tineaiiyrttyy which makes ACM- and ACMII-SGC- exactly the same.

---

Ablation Study on Diffecent Components in ACM SGC and ACM GCN (16)
Baseline
Model Components
Comeell
Wisconsin
Texas
Film
Chameleon
Squirel
Cora
CieeSeer
PahMed
Models
LP Idearny Mixing]
Ace +
Acc
+ Sid
Sed
70.38
53.28
79.66
83.28
581
91.88
161
90.98
36.76
1,01
65.27
57.27
1.7
56.8
108
80.98
1.88
87:21
0.42
10:44
93.93
+ 366
95:25
+ 134
90.93
2,4
28,38
1.13 63.83
+
240
46.79
0.75
96.3
1.28
80.57
0.99
87.8
+ 0.58
9.44
88.2 1: 4.39
93.5
91.55
2994
27.19
0.57
62.82
1M
44.94
093
85
1.35
80.75
88.11
0.21
11.00
93.77
93.25
93.61
1,55
39.33
1,25
63,68
1/2
1:13
86.63
80.9
87.75
0.85
182446 3.11
75.5
35.51
260
44.76
88.9
11.44
82.13
2:59
96.62
1.61
89.19
3.04
38.06
1,35
69
1AS
572
1.0
53.93
1,55
81.96
0.91
90.01
0.8
7.22
ACM-GON wf
94.26 2:23
96.10
2:2
91.1-:995
11.51
0
67
1
2
53.97
1
1:39
88.95
1
0,9
S1.72
1.22
90.88
1: 0..5
4.44
91 2
95.37
2:31
95.25 -
40.47
93
1 2.04
54.78
277
89.13
1.77
81.96
2,03
91.01
0.7
3.11
55.55
$1.80
90.69
1: 300
91.00
90.33
0.75
2.14
0.39
ACM
3
94.26
91 + 1.43
2.57
96.25
96.00
+ 2.09
2.15
93.77
2.91
40.27
40.96
1.07
1.2. 66.
66.52
+ 2.65
1.76
50.78
52.0
+ 1.64
2.07
58.83
80.00
1.16
81.54
0.95
1.22
98.71
90.6
= 0.47
0.67
4.67
6.67
95.9
1.83
96.62
2.44 95 3,15
41.84
1,15 68.38
1,36 $4.53 +: 2.09
89
0.72
$1.79
0.95
90.74
+: 0.5
2.78
Compazison of Average Kunning Time Per Epochtins)
2.53
2,83
2.5
3.18
3.48
4.65
3.47
3.43
4.04
4,01
4.57
4.24
4.55
4.76
5.09
5.39
4.69
4.75
ACM-SG..
4.04
06
4.38
16
3,49
3.18
3,92
3.87
5.53
5,96
5.43
5.21
5.41
6.96
6
59
6.04
3.67
3.74
3.59
4.56
4,96
6.41
4.24
4.18
5.08
6.63
8.06
7.89
8.11
7.
9.39
7.82
7.38
8.74
ACM-GCN of
5,93
6.65
6.8
5.2
5.73
5.65
8.25
8.11
7.89
7.97
8.41
11.9
8.84
8.38
8.63
6.62
7,35
7.39
7.62
7.33
9.69
7.49
7.58
7.97
6.1
6.05
6.26
6.87
6.44
6.5
6.14
7.21
6.6
ACMI-GON w/
5.24
5.27
5:46
5.72
5.65
7.87
5.48
5.65
6.33
Table 1: Ablation study 9 real-world datasets (36. Cell with v means the component is applied to the baseline model. The best test results are highlighted.
GCN(C) shows clearer boundaries among classes than GCN(b). The running time is approximately doubled in the ACM and ACMII framework compared to the original models.
6.2 Comparison with Baseline and SOTA Models
Datasets & Experimental Setup In this section, we evaluate SGC with hop and 2 hops (SGC-I, SGC-2), GCNII 7 GCNII" 77) GCN 1+ and snowball networks
30 with and 3 layers We use A,w as Both filters are deterministic. We compare these approaches with several baselines and SOTA GNN models: MLP with layers (MLP-2),
(snowball-2,, snowball-3) and combine them with the ACM or ACMII framework 13
the LP filter and the corresponding HP filter is / - Arw
14
GAT 41, APPNP 20, GPRGNN R, G.G 4o..
MixHop [I] GCN+JK [19 43 26 GAT+JK
41 + 26
FAGCN GraphSAGE 15 Geom-GCN 36 and BernNet [o.. addition to the
benchmark datasets used in section Deezer-Europe
6.1
we further test the above models on a new benchmark dataset,
we test the models 10 times following the same early stopping strategy, the same 60%/20%//0% random data split and Adam []] optimizer used in GPRGNN [8. For Deezer-Europe, we test the above models 5 times with the same early stopping strategy, the same fixed splits and Adam used in [26].
On each dataset used in 37 36
Structure information channel and residual connection Besides the filtered features, some recent SOTA models additionally use graph structure information, i.e., MLPa A). and residual
connection to address heterophily problem, e.g., LINKX (25) and GloGNN 14). MLPx((A) and residual connection can be directly incorporated into ACM and ACMII framework, which leads us to
ACM(II)GCN+ and ACM(II-GCN++: See the details of implementation in Appendix B
PGCNII and GCNII are hard to implement with the ACMII framework. See Appendix B for explanation.
"See Appendix A.3 for the comparison of Årx and Agm.
We choose Deezer-Europe because MLP outperforms GCN on it 26
Seee table in Appendix A.2 for the performance comparison with several SOTA models, egg. LINKX 25
and GloGNN 24 the fixed 48%/32%//20 splits provided by (36

---

Coreel (SOTA- BerNNet)
Wisconsin (SOTA-MLP22
(SOTA BermNet)
95
95
SOTA
(%)
baseline
ACM GNNss
90
85
accurary
90
ACM-GCN+
85
80
75
85
ACMII-GCN+
GCN++
ACMII-GCN++
80
65
GCN
snowball-22 snowbali
GCN
snowball-2
GCN
snawball Snowball
(a) 10.16 % 13.44 %
(b) 20.25 % 27.50 %
(c) 11.64 % 13.45 %
Chameleon (SOTA-Bern) BernNet)
Film (SOTA- BernNet)
Squirrel (SOTA-GCN++K)
70
75
42
Aecuraty (8)
40
65
Accuracy
Accuracy
70
38
55
36
63
50
34
45
32
60
40
snowball-2snowbball.
anowball-2snowballa
snowball-ssowoaall.
(d) 1 2.04 % ~ 11.90 %
(c) f 4.31 6.35
(f) 1 4.06 25.22 %
Figure Comparison of baseline GNNs (red), ACM-GNNs (green), ACMII-GNNs (blue) with SOTA (magenta line) models symbol "1" shows the range of performance improvement (%) of ACM-GNNs and ACMII-GNNs over baseline GNNs. See Appendix I for detailed discussion of the relation between H and GNN performance.
selected datasets. The black lines indicate the standard deviation. The
agg
To visualize the performance, in Fig- plot the bar charts of the test accuracy of SOTA models, three selected baselines (GCN, snowball-2. snowball-3), their ACM(II) augmented models, ACM(II)- the most commonly used benchmark heterophily datasets (See Table 2 in Appendix A. for the full results, comparison and ranking). From Fig. 6 we can see that (1) after being combined with the ACM ACMII framework, the performance of the three baseline models is significantly boosted, by 2.04 ~~7.50 on all the 6 tasks. The ACM and ACMII in fact achieve SOTA performance. (2) On Cornell, Wisconsin, Texas, Chameleon and Squirrel, the augmented bascline models significantly outperform the current SOTA models. Overall, these results suggest that the proposed approach can help GNNs to generalize better on node classification tasks on heterophilic graphs, without adding too much computational cost.
GCN+ and ACM(II)-CN++
7 Conclusions and Limitations
We have presented an analysis of existing homophily metrics and proposed new metrics which are more informative in terms of correlating with GNN performance. To our knowledge, this is the first work analyzing heterophily from the perspective of post-aggregation node similarity. The similarity matrix and the new metrics we defined mainly capture linear feature-independent relationships of each node. This might be insufficient when nonlinearity and feature- dependent information is important for classification. the future, it would be useful to investigate if a similarity matrix could be defined which is capable of capturing nonlinear and feature- feature-dependent relations between aggregated node.
We have also proposed multi-channel mixing mechanism which leverages the intuitions gained in the first part of the paper and can be combined with different GNN architectures, enabling adaptive filtering (high-pass, pass, low-pass or identity) different nodes. Empirically, this approach shows very promising results, improving the performance of the base GNNs with which it is combined and achieving SOTA results at the cost of a reasonable increase computation time. As discussed in Sec. however, the filterbank method cannot properly handle all cases of harmful heterophily, and alternative ideas should be explored as well the future.
8 Acknowledge
The authors would like to give very special thanks to William L.. Hamilton for valuable discussion and advice. The project was partially supported by DeepMind and NSERC.
10

---

References
[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 21-29. PMLR, 2019.
[2] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprini arXiv: (00:::4449044400 0473, 2014.
[3] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. -Gonzalzz. V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint /806.0/61, 2018.
[4] D. Bo, X. Wang, C. Shi, and H. Shen. Beyond low- wwwffreuency information in graph convolutional networks. arXiv preprint arXiv:2101.00997, 2021.
[5] C. Bodnar, F. Di Giovanni, B. P. Chamberlain, P. Liò, and M. M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. arXiv preprint arXiv:2202.04579, 2022.
[6] M. M. Bronstein, Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: going beyond euclidean data. arXiv, abs/161 1. .08097, 2016.
[7] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
[8] 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.
[9] F. R. Chung and F. C. Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[10] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv, abs/ 2016.
[11] V. N. Ekambaram. Graph structured data viewed through a fourier lens. University of California, Berkeley, 2014.
[12] M. Fey and J. Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:/903. 024028,, 2019.
[13] A. Graves, A.r. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pages 6645-6649, Ieee, 2013.
[14] W. L. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-19,, 2020.
[15] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. 2017.
arXiv, abs//170.002/
[16] M. He, Z. Wei, H. Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 2021.
[17] Y. Hou, J. Zhang. J. 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.
[18) D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[19] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv, abs//609.02990 0099070 2016.
[20] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
[21] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances neural information processing systems, pages 1097-1 105, 2012.
11

---

[22] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. nature, 521((553)):36,, 2015.
[23] Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, et al. Bradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11):2278-2 2324,, 1998.
[24] X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian. Finding global homophily in graph neural networks when meeting heterophily. arXiv preprint arXiv:2205.0 07308 2022.
[25] D. Lim, F. Hohne, X. Li, S. L. Huang, V. Gupta, O. Bhalerao, and S. N. Lim. Large scale learning on non non-hoooph graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20901 2021.
[26] D. Lim, X. Li, F. Hohne, and S.-N. Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv: 04. 01 0040, 2021.
[27] V. Lingam, R. Ragesh, A. Iyer, and S. Sellamanickam. Simple truncated svd based model for node classification on heterophilic graphs. arXiv preprint arXiv:2 12807, 2021.
[28] M. Liu, Z. Wang, and S. Ji. Non-local graph neural networks. arXiv preprint arXiv:2005.1461 2020.
[29] M. Liu, Z. Wang, and S. Ji. Non-local graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[30] S. Luan, M. Zhao, X.-W. Chang, and D. Precup. Break the ceiling: Stronger multi-scale deep
graph convolutional networks. arXiv preprint orXiv:/906.02/ 07,4, 2019.
[31] S. Luan, M. Zhao, X.WW. Chang, and D. Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. arXiv preprint arXiv:2008.08833, 2020.
[32] Luan, M. Zhao, C. Hua, X.-W. Chang, and D. Precup. Complete the missing half: Augmenting
aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008. 08844, 2020.
[33] Y. Ma, X. Liu, Shah, and J. Tang. Is homophily necessity for graph neural networks? arXiv preprint arXiv:2/06.060 106.06644,,4 34, 2021.
[34] T. Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint (905.00900 2019.
[35] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, (7(1))415-44) 444,,,44422 2001.
[36] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint
:et:20002.52877 2020.
[37] B. Rozemberezki, C. Allen, and R. Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
[38] B. Rozemberezki and Sarkar. Characteristic Functions on Graphs: Birds of Feather, from Statistical Descriptors to Parametric Models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20), page 1325-1334. ACM, 2020.
[39] F. Scarselli, M. Gori, A. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
[40] P. Vary. An adaptive filter-bank equalizer for speech enhancement. Signal Processing, 1666)1 2006.
[41] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXivv, abs/1710. 10990,,,,, 2017.
[42] Wu, T. Zhang. A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: /902.0/022.3333 2019.
[43] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. 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 5453-5462. PMLR, 10-15 Jul 2018.
[44] 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.06466, 2021.
12

---

[45] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009. 2020.
[46] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "vWFdN9AHFED", "reviewer": "Reviewer_9hm2", "summary": "This paper presents an analysis of existing homophily metrics, and proposes a new metric more informative for the performance. Based on the analysis, they design a 3-way filterbank, enabling adaptive filtering (high-pass, low-pass or identity) at different nodes. Experiments validate the effectiveness of the proposed method.", "questions": "1. More comparisons with FAGCN.\n2. There is a gap between the proposed metric and method.\n3. The improvement in Table 4 does not seem statistically significant because of high variance.\n", "limitations": "In addition to the limitations mentioned in the paper, the intrinsic relationship between the proposed metric and method should be taken into consideration. No potential negative societal impact.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1.\tThis paper is the first to analyze heterophily from post-aggregation node similarity.\n2.\tThe proposed filterbank is plug-and-play for backbone GNNs, which extracts richer information from additional channels.\nWeakness:\n1.\tContribution is not convincing. They argue that the traditional adaptive filterbank uses a scalar weight shared by all nodes, and their proposed method learns different weights for different nodes. However, in my opinion, FAGCN can do the same thing.\n2.\tThere is a gap between the proposed metric and method. Based on post-aggregation node similarity, they propose an aggregation similarity metric. However, the final 3-channel filterbank has nothing to do with the above metric.\n3.\tThe novelty of the idea is not enough. In addition to the limitations pointed out above, both new metric and method are relatively straightforward.\n4.\tThe improvement in Table 4 does not seem statistically significant because of high variance.\n5.\tThere is a problem with the typesetting of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GggAs0KKnv2", "reviewer": "Reviewer_icHY", "summary": "This paper first points out that existing homophily metrics cannot precisely reflect the performance of GNN in some cases, and develops a new one based on the similarity comparison between the local neighbors in the same and different class. Next, based on the proposed metric, the paper shows the case that a high-pass filter can address the harmful heterophily, and further propose a node-wise mixing filter that combines low-pass and high-pass filters. ", "questions": "What's the correlation between the high-pass filter and diversification? It would be better to define diversification and describe how a high-pass filter can extract such information. A synthetic example is not clear enough.", "limitations": "1. Some experiments are missing: (1) The comparison between the existing homophily metrics and the proposed one on real-world datasets. (2) The case study of \\alpha score on different nodes. These analysis could better help readers understand the effect of architecture and hyper-parameters of the architecture.\n\n2. The theoretical analysis is based on the random walk Laplacian. It would be better if the authors can extend it to the widely used symmetric Laplacian.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n1. The motivation for the proposed homophily metric is clear and theoretically guaranteed, although the analysis of one-layer SGC is relatively simplistic. The observations from Table 8 show that the metric can accurately determine whether the additional graph information is harmful.\n2. Node-wise aggregation is reasonable since the local structure differs between different nodes.\n3. The experimental results on many different GNNs shown in the Appendix are complete and convincing.\n​\nCons\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DbZnBG5YmPX", "reviewer": "Reviewer_vQE7", "summary": "This paper first addresses the limitation of the previously proposed metrics in analyzing the performance of GNNs on heterophilic graph datasets. To solve the limitation, a new metric based on the post-aggregation node similarity is proposed. The newly proposed metric better reflects the performances of GNNs on node classification tasks. To further improve the GNNs, the authors propose an adaptive channel mixing mechanism that uses both high and low-frequency graph signals. The adaptive channel mixing mechanism is employed in existing GNN models and shows improved performances on various node classification datasets.", "questions": "- Two variants of the adaptive channel mixing mechanism are proposed. From a practical point of view, which model should be used?\n- The new metric can be extended to the multi-hop aggregation setting. Was there any further finding when the authors consider the multi-hop aggregation matrix?\n- The intuition behind the mixing matrix is unclear. Could authors elaborate more on the necessity of the mixing matrix W_Mix? Why the attention is insufficient to mix the channel outputs?", "limitations": "Although the limitation of the proposed approach is addressed in the appendix, the limitations are shown based on a curated example and fail to show general conditions where the model fails.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The paper addresses the limitation of previously suggested metrics well and proposes a new metric that can better reflect the behaviors of GNN models.\n- The adaptive channel mixing mechanism is intuitive and can be applied to many existing GNN models without adding too much computational complexity.\n- Extensive experimental results are shown on various datasets to show the performance of the proposed framework.\n\nWeaknesses\n\n- Although the metric shows a strong correlation with many existing GNN models, the analysis of post-aggregation is based on SGC and cannot be generalized to the other models directly.\n- Representation of some parts can further be improved. For example, the connection between the diversification distinguishability and the adaptive channel mixing framework seems vague.  The definition of diversification distinguishability and the following theorem seem not necessary to introduce the necessity of the proposed framework. Also, the connection between the metric part and the model part seems not very clear although both parts are inspired by the post-aggregation similarity.\n- The proposed metric seems to be correlated with model performances. However, the correlation between the performances of real-world datasets and the proposed metric hasn’t been shown.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6zOWqKyMDIE", "reviewer": "Reviewer_S2KT", "summary": "This paper considers heterophily in GNN for node classification. It has two major contributions to the community. First, it pointed out that mainstream homophily measures (i.e. edge, node, class) does not align with GCN/SGC classification accuracy, since those measures does not distinguish harmless/harmful heterophilty. It proposes a new mesaure that inspired by SGC gradient updates, which shows good alignment between homophily and classification accuracy on synthetic datasets. Second, this paper propose ACM which uses low pass high pass and identity channels, combine together with softmax operation, ACM is based on the intuition that high pass filter would help distinguish nodes with harmful heterophily. ACM is empirically verified to be good.", "questions": "N/A", "limitations": "Suggestions\n  - in abstract, make clear this paper is about node classification, (real-world tasks -> nodeclassification)\n  - line 137, i assume you meant to write [-1, 1]\n  - line 142, I am not sure what you mean here\n  - line 554, i assume you meant to write 1_{N}^{T}\n  - my experience is that graphsage typically works well for heterophily graphs, adding that as a baseline to acm would be useful\n  - add citations\n    - (gnn heterophily) Residual correlation in graph neural network regression\n    - (gnn heterophily) Beyond Homophily in Graph Neural Networks\n    - (gnn heterophily) New benchmarks for learning on non-homophilous graphs\n  ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n  - the new homophily is novel and practical connection with SGC gradient is very intuitive\n    - this is a very notable contribution to the community, although homophily and SGC performance has been discussed in the past by many, it is a known issue that the edge homophily is not fully correlated with SGC performance. the analysis and new hopophily measure solved this problem\n  - ACM is novel effective and intuitive\n\nWeakness\n  - writing could improve", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4XVcI25MMH", "reviewer": "Reviewer_Y2Du", "summary": "This paper investigates the relationship between heterophily and the performance of current GNNs. First, the paper proposes a novel homophily metric that specifics harmful heterophily. The metric is shown to be more correlated with the GNNs’ performances than traditional metrics. To handle with harmful heterophily, based on the metric, the paper proposes Adaptive Channel Mixing (ACM) Framework. Extensive experiments are conducted on real-world datasets that verify the superiority of ACM framework. ", "questions": "refer to \"limitations\"", "limitations": "1.\tThe proposed diversification operation is not novel since many previous works have utilized high- frequency components directly or indirectly. The authors have emphasized the difference between ACM and GPRGNN/FAGCN in node-wise channel mixing, but GPRGNN also contains node- wise feature transformation before the propagation step, which could cause γ_k to be different for each node. And the attention mechanism in FAGCN could be seen as a node-wise mixing as well. While the superiority of ACM over other mixing mechanisms is revealed in the experiment, I would be glad to see a more intuitive explanation or example of why ACM is better. \n2.\tThe homophily metric on real-world datasets are indistinguishable. In table 8, homophily metrics on most datasets are above 0.8, and seem not correlated with GNNs’ performances. (e.g. chameleon, film, squirrel) I wonder if the proposed metric is still instructive in real-world datasets. \n3.\tWhy are there some bumps in figure 2(c), 2(d) when h(G)=1.0 and h(g)=0.0 ? \n4.\tThere seems to be too many overfull lines. \n5.\tIn Fig.2, please explain the performance drop in the interval [0.0, 0.2] and why (d) does not include this interval.\n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1.\tThe proposed homophily metric is interesting and makes sense. The given example in Fig. 1 and comparison with other metrics in Fig.2 nicely illustrate the advantages of this new metric. \n2.\tThe experiments including detailed ablation study are clear and comprehensive. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept