summaries: The paper shows that not all cases of heterophily are harmful for GNNs with aggregation operations. Based on a backpropagation analysis on an SGC-style GNN, it provides a new metric based on similarity matrix which considers the influence of both graph structure and input features. Observing that the diversification operation is able to address some harmful heterophily cases, it proposes the Adaptive Channel Mixing GNN framework which combines a high-pass filter, a low-pass filter and an identity channel.

summaries: In this paper, the authors first analyze the potential drawbacks of existing heterophily metrics, then propose an aggregated heterophily metric aiming to better estimate the "harmful" heterophily and utilize diversification operation to address certain harmful heterophily cases. Based on the analysis, the authors propose an adaptive channel mixing (ACM) framework to improve GNN model performance. Several experiments have also been conducted to evaluate the proposed model.

summaries: This paper proposes a new aggregation-based homophily metric for assessing the homophily of a graph. This metric complements the current metrics by considering unharmful heterophily cases. The second contribution is a new filterbank framework which uses the diversification operation to fight harmful heterophily information.

summaries: The paper starts from studying the question of how heterophily affects the learning effectiveness of Graph Neural Networks on node classification tasks and posits that heterophily may not be always detrimental to the task. Following this observation, it proposes a new architecture, called Adaptive Channel Mixing, which appropriately applies aggregation, diversification and identity channels in each GNN layer in order to tackle harmful heterophily. According to the experimental results, the proposed architecture is successful.

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

authors:
Sami Abu-El-Haija
Bryan Perozzi
Amol Kapoor
Nazanin Alipourfard
Kristina Lerman
Hrayr Harutyunyan
Greg Ver Steeg
Aram Galstyan

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

venue: arXiv preprint arXiv:1409.0473,

authors:
Peter W Battaglia
Jessica B Hamrick
Victor Bapst
Alvaro Sanchez-Gonzalez
Vinicius Zambaldi
Mateusz Malinowski
Andrea Tacchetti
David Raposo
Adam Santoro
Ryan Faulkner

venue: arXiv preprint arXiv:1806.01261,

authors:
Deyu Bo
Xiao Wang
Chuan Shi
Huawei Shen

venue: arXiv preprint arXiv:2101.00797,

authors:
Michael M. Bronstein
Joan Bruna
Yann LeCun
Arthur Szlam
Pierre Vandergheynst

authors:
Ming Chen
Zhewei Wei
Zengfeng Huang
Bolin Ding
Yaliang Li

title: Simple and deep graph convolutional networks

authors:
Eli Chien
Jianhao Peng
Pan Li
Olgica Milenkovic

authors:
Fan RK Chung
Fan Chung Graham

title: Spectral graph theory

venue: Number 92. American Mathematical Soc.,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

venue: University of California,

authors:
Matthias Fey
Jan Eric Lenssen

venue: arXiv preprint arXiv:1903.02428,

authors:
Alex Graves
Abdel-rahman Mohamed
Geoffrey Hinton

title: Graph representation learning

authors:
William L. Hamilton
Rex Ying
Jure Leskovec

title: Inductive representation learning on large

venue: graphs. arXiv,

authors:
Yifan Hou
Jian Zhang
James Cheng
Kaili Ma
Richard TB Ma
Hongzhi Chen
Ming-Chang Yang

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Thomas N. Kipf
Max Welling

venue: URL http://arxiv.org/abs/1609.02907

authors:
Johannes Klicpera
Aleksandar Bojchevski
Stephan Günnemann

venue: arXiv preprint arXiv:1810.05997,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

venue: Proceedings of the IEEE,

authors:
Derek Lim
Xiuyu Li
Felix Hohne
Ser-Nam Lim

venue: arXiv preprint arXiv:2104.01404,

authors:
Vijay Lingam
Rahul Ragesh
Arun Iyer
Sundararajan Sellamanickam

venue: arXiv preprint arXiv:2106.12807,

authors:
Meng Liu
Zhengyang Wang
Shuiwang Ji

title: Non-local graph neural networks

venue: arXiv preprint arXiv:2005.14612,

authors:
Ilya Loshchilov
Frank Hutter

title: Decoupled weight decay regularization

venue: arXiv preprint arXiv:1711.05101,

authors:
Sitao Luan
Mingde Zhao
Xiao-Wen Chang
Doina Precup

venue: arXiv preprint arXiv:2008.08838,

authors:
Sitao Luan
Mingde Zhao
Chenqing Hua
Xiao-Wen Chang
Doina Precup

venue: arXiv preprint arXiv:2008.08844,

venue: arXiv preprint arXiv:1905.09550,

authors:
Miller McPherson
Lynn Smith-Lovin
James M Cook

venue: Annual review of sociology,

authors:
Hongbin Pei
Bingzhe Wei
Kevin Chen-Chuan Chang
Yu Lei
Bo Yang

venue: arXiv preprint arXiv:2002.05287,

authors:
Benedek Rozemberczki
Rik Sarkar

authors:
Benedek Rozemberczki
Carl Allen
Rik Sarkar

title: Multi-Scale Attributed Node Embedding

venue: Journal of Complex Networks,

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE transactions on neural networks,

authors:
Felix Wu
Tianyi Zhang
Amauri Holanda de Souza Jr.
Christopher Fifty
Tao Yu
Kilian Q Weinberger

title: Simplifying graph convolutional networks

authors:
Keyulu Xu
Chengtao Li
Yonglong Tian
Tomohiro Sonobe
Ken-ichi Kawarabayashi
Stefanie Jegelka

authors:
Yujun Yan
Milad Hashemi
Kevin Swersky
Yaoqing Yang
Danai Koutra

venue: arXiv preprint arXiv:2102.06462,

authors:
Jiong Zhu
Ryan A Rossi
Anup Rao
Tung Mai
Nedim Lipka
Nesreen K Ahmed
Danai Koutra

title: Graph neural networks with heterophily

venue: arXiv preprint arXiv:2009.13566,

authors:
Jiong Zhu
Yujun Yan
Lingxiao Zhao
Mark Heimann
Leman Akoglu
Danai Koutra

title: Experimental results: average test accuracy± standard deviation on 10 real-world benchmark

venue: ACMII-GCN

title: 2020). NA means the reported results are not available and OOM means out of memory

title: Geom-GCN, H2GCN and GPRGNN are from Pei et al

text:
1 INTRODUCTION Deep Neural Networks (NNs) (LeCun et al., 2015) have revolutionized many machine learning areas, including image recognition (Krizhevsky et al., 2012), speech recognition (Graves et al., 2013) and natural language processing (Bahdanau et al., 2014), etc.One major strength is their capacity and effectiveness of learning latent representation from Euclidean data. Recently, the focus has been put on its applications on non-Euclidean data (Bronstein et al., 2016), e.g., relational data or graphs. Combining graph signal processing and convolutional neural networks (LeCun et al., 1998), numerous Graph Neural Networks (GNNs) (Scarselli et al., 2008; Defferrard et al., 2016; Hamilton et al., 2017; Velickovic et al., 2017; Kipf & Welling, 2016; Luan et al., 2019) have been proposed which empirically outperform traditional neural networks on graph-based machine learning tasks, e.g., node classification, graph classification, link prediction and graph generation, etc.GNNs are built on the homophily assumption (McPherson et al., 2001), i.e., connected nodes tend to share similar attributes with each other (Hamilton, 2020), which offers additional information besides node features. Such relational inductive bias (Battaglia et al., 2018) is believed to be a key factor leading to GNNs’ superior performance over NNs’ in many tasks.
Nevertheless, growing evidence shows that GNNs do not always gain advantages over traditional NNs when dealing with relational data. In some cases, even simple Multi-Layer Perceptrons (MLPs) can outperform GNNs by a large margin (Zhu et al., 2020b; Liu et al., 2020; Luan et al., 2020b; Chien et al., 2021). An important reason for the performance degradation is believed to be the heterophily problem, i.e., connected nodes tend to have different labels which makes the homophily assumption fail. Heterophily challenge has received lots of attention recently and there are increasing number of models being put forward to address this problem (Zhu et al., 2020b; Liu et al., 2020; Chien et al., 2021; Zhu et al., 2020a; Yan et al., 2021).
1In general, harmful heterophily means the heterophilous structure that will make a graph-aware model underperform its corresponding graph-agnostic model.
Contributions In this paper, we first demonstrate that not all heterophilous graphs are harmful for aggregation-based GNNs and the existing metrics of homophily are insufficient to decide whether the aggregation operation will make nodes less distinguishable or not. By constructing a similarity matrix from backpropagation analysis, we derive new homophily metrics to depict how much GNNs are influenced by the graph structure and node features. We show the advantage of our metrics over the existing metrics by comparing the ability of characterizing the performance of two baseline GNNs on synthetic graphs of different levels of homophily. According to the similarity matrix, we observe that diversification operation is able to address some harmful heterophily cases, and based on which we propose Adaptive Channel Mixing (ACM) GNN framework. The experiments on the synthetic datasets, ablation studies and real-world datasets consistently show that the baseline GNNs augmented by ACM framework are able to obtain significant performance boost on node classification tasks on heterophilous graphs.
The rest of this paper is mainly organized as follows: In section 2, we introduce the notation and the background knowledge. In section 3, we conduct node-wise analysis on heterophily, derive new homophily metrics based on a similarity matrix and conduct experiments to show their advantages over the existing homophily metrics. In section 4, we demonstrate the capability of diversification operation on addressing some cases of harmful heterophily and propose the ACM-GNN framework to adaptively utilize the information from different filterbank channels for each node to address heterophily problem. In section 5, we discuss the related works and clarify the differences with our method. In section 6, we provide empirical evaluations on ACM framework, including ablation study and tests on real-world node classification tasks.
2 PRELIMINARIES We will introduce the related notation and background knowledge in this section. We use bold fonts for vectors (e.g., v). Suppose we have an undirected connected graph G = (V, E , A), where V is the node set with |V| = N ; E is the edge set without self-loop; A ∈ RN×N is the symmetric adjacency matrix with Ai,j = 1 iff eij ∈ E , otherwise Ai,j = 0. We use D to denote the diagonal degree matrix of G, i.e., Di,i = di = ∑ j Ai,j and use Ni to denote the neighborhood set of node i, i.e., Ni = {j : eij ∈ E}. A graph signal is a vector x ∈ RN defined on V , where xi is defined on the node i. We also have a feature matrix X ∈ RN×F , whose columns are graph signals and whose i-th row Xi,: is a feature vector of node i. We use Z ∈ RN×C to denote the label encoding matrix, whose i-th row Zi,: is the one-hot encoding of the label of node i.
2.1 GRAPH LAPLACIAN, AFFINITY MATRIX AND THEIR VARIANTS
The (combinatorial) graph Laplacian is defined as L = D −A, which is Symmetric Positive SemiDefinite (SPSD) (Chung & Graham, 1997). Its eigendecomposition gives L = UΛUT , where the columns ui of U ∈ RN×N are orthonormal eigenvectors, namely the graph Fourier basis, Λ = diag(λ1, . . . , λN ) with λ1 ≤ · · · ≤ λN , and these eigenvalues are also called frequencies. The graph Fourier transform of the graph signal x is defined as xF = U−1x = UTx = [uT1 x, . . . ,u T Nx]
T , where uTi x is the component of x in the direction of ui.
In additional to L, some variants are also commonly used, e.g., the symmetric normalized Laplacian Lsym = D
−1/2LD−1/2 = I −D−1/2AD−1/2 and the random walk normalized Laplacian Lrw = D−1L = I −D−1A. The graph Laplacian and its variants can be considered as high-pass filters. The affinity (transition) matrices can be derived from the Laplacians, e.g., Arw = I − Lrw = D−1A, Asym = I − Lsym = D−1/2AD−1/2 and are considered to be low-pass (LP) filters (Maehara, 2019). Their eigenvalues satisfy λi(Arw) = λi(Asym) = 1− λi(Lsym) = 1− λi(Lrw) ∈ (−1, 1]. Applying the renormalization trick (Kipf & Welling, 2016) to affinity and Laplacian matrices respectively leads to Âsym = D̃−1/2ÃD̃−1/2 and L̂sym = I − Âsym, where Ã ≡ A + I and D̃ ≡ D + I . The renormalized affinity matrix essentially adds a self-loop to each node in the graph, and is widely used in Graph Convolutional Network (GCN) (Kipf & Welling, 2016) as follows,
Y = softmax(Âsym ReLU(ÂsymXW0) W1) (1)
where W0 ∈ RF×F1 and W1 ∈ RF1×O are learnable parameter matrices. GCN can be trained by minimizing the following cross entropy loss
L = −trace(ZT log Y ) (2)
where log(·) is a component-wise logarithm operation. The random walk renormalized matrix Ârw = D̃
−1Ã, which shares the same eigenvalues as Âsym, can also be applied in GCN. The corresponding Laplacian is defined as L̂rw = I − Ârw. The matrix Ârw is essentially a random walk matrix and behaves as a mean aggregator that is applied in spatial-based GNNs (Hamilton et al., 2017; Hamilton, 2020). To bridge the spectral and spatial methods, we use Ârw in the paper.
2.2 METRICS OF HOMOPHILY
The metrics of homophily are defined by considering different relations between node labels and graph structures defined by adjacency matrix. There are three commonly used homophily metrics: edge homophily (Abu-El-Haija et al., 2019; Zhu et al., 2020b), node homophily (Pei et al., 2020), and class homophily (Lim et al., 2021) 2 defined as follows:
Hedge(G) = ∣∣{euv | euv ∈ E , Zu,: = Zv,:}∣∣
|E| , Hnode(G) =
1 |V| ∑ v∈V ∣∣{u | u ∈ Nv, Zu,: = Zv,:}∣∣ dv ,
Hclass(G) = 1
C − 1 C∑ k=1
[ hk − ∣∣{v | Zv,k = 1}∣∣ N ] + , hk = ∑ v∈V ∣∣{u | Zv,k = 1, u ∈ Nv, Zu,: = Zv,:}∣∣∑ v∈{v|Zv,k=1} dv
(3) where [a]+ = max(a, 0); hk is the class-wise homophily metric (Lim et al., 2021). They are all in the range of [0, 1] and a value close to 1 corresponds to strong homophily while a value close to 0 indicates strong heterophily. Hedge(G) measures the proportion of edges that connect two nodes in the same class; Hnode(G) evaluates the average proportion of edge-label consistency of all nodes; Hclass(G) tries to avoid the sensitivity to imbalanced class, which can cause Hedge(G) misleadingly large. The above definitions are all based on the graph-label consistency and imply that the inconsistency will cause negative effect to the performance of GNNs. With this in mind, we will show a counter example to illustrate the insufficiency of the above metrics and propose new metrics in the following section.
3 ANALYSIS OF HETEROPHILY
3.1 MOTIVATION AND AGGREGATION HOMOPHILY
Heterophily is believed to be harmful for message-passing based GNNs (Zhu et al., 2020b; Pei et al., 2020; Chien et al., 2021) because intuitively features of nodes in different classes will be falsely mixed and this will lead nodes indistinguishable (Zhu et al., 2020b). Nevertheless, it is not always the case, e.g., the bipartite graph shown in Figure 1 is highly heterophilous according to the existing homophily metrics in equation 3, but after mean aggregation (operated by mean aggregator), the nodes in classes 1 and 2 only exchange colors and are still distinguishable. Authors in (Chien et al.,
2021) also point out the insufficiency of Hnode by examples to show that different graph typologies with the same Hnode(G) can carry different label information. To analyze to what extent the graph structure can affect the output of a GNN, we first simplify GCN by removing its nonlinearity as (Wu et al., 2019). Let Â ∈ RN×N denote a general aggregation operator. Then, equation 1 can be simplified as,
Y = softmax(ÂXW ) = softmax(Y ′) (4)
2The authors in (Lim et al., 2021) did not name this homophily metric. We name it class homophily based on its definition.
After each gradient decent step ∆W = γ dLdW , where γ is the learning rate, the update of Y ′ will be (see Appendix C for derivation),
∆Y ′ = ÂX∆W = γÂX dL dW ∝ ÂX dL dW = ÂXXT ÂT (Z − Y ) = S(Â,X)(Z − Y ) (5)
where S(Â,X) ≡ ÂX(ÂX)T is a post-aggregation node similarity matrix, Z − Y is the prediction error matrix. The update direction of node i is essentially a weighted sum of the prediction error, i.e., ∆(Y ′)i,: = ∑ j∈V [ S(Â,X) ] i,j (Z − Y )j,:.
Instead of measuring the graph-label consistency, we study the effect of heterophily by considering the post-aggregation node similarity. To this end, we first define the aggregation similarity score as follows. Definition 1. Aggregation similarity score
Sagg
( S(Â,X) ) = ∣∣∣{v ∣∣Meanu({S(Â,X)v,u|Zu,: = Zv,:}) ≥ Meanu({S(Â,X)v,u|Zu,: 6= Zv,:})}∣∣∣ |V|
(6) where Meanu ({·}) takes the average over u of a given multiset of values or variables.
Sagg(S(Â,X)) measures the proportion of nodes v ∈ V that will put relatively larger similarity weights on nodes in the same class than in other classes after aggregation. It is easy to see that Sagg(S(Â,X)) ∈ [0, 1]. But in practice, we observe that in most datasets, we will have Sagg(S(Â,X)) ≥ 0.5. Based on this observation, we rescale equation 6 to the following modified aggregation similarity for practical usage,
SMagg
( S(Â,X) ) = [ 2Sagg ( S(Â,X) ) − 1 ] +
(7)
In order to measure the consistency between labels and graph structures without considering node features and make a fair comparison with the existing homophily metrics in equation 3, we define the graph (G) aggregation (Â) homophily and its modified version as
Hagg(G) = Sagg ( S(Â, Z) ) , HMagg(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, Hagg(G) = HMagg(G) = 1. Thus, this new metric reflects the fact that nodes in classes 1 and 2 are still highly distinguishable after aggregation, while other metrics mentioned before fail to capture such information and misleadingly give value 0. This shows the advantage of Hagg(G) and HMagg(G) by additionally exploiting information from aggregation operator Â and the similarity matrix.
To comprehensively compare HMagg(G) with the metrics in equation 3 on how they can reveal the influence of graph structure on GNN performance, we generate synthetic graphs with different homophily levels and evaluate SGC (Wu et al., 2019) and GCN (Kipf & Welling, 2016) on them in the next subsection.
3.2 EMPIRICAL EVALUATION AND COMPARISON ON SYNTHETIC GRAPHS
In this subsection, we conduct experiments on synthetic graphs with different HMedge(G) to empirically verify the effectiveness of HMagg(G) and compare it with the existing metrics.
Data Generation & Experimental Setup We first generate 280 graphs in total with 28 edge homophily levels varied from 0.005 to 0.95, each corresponding to 10 graphs. For every generated graph, we have 5 classes with 400 nodes in each class. For nodes in each class, we randomly generate 800 intra-class edges and [ 800Hedge(G) − 800] inter-class edges. The features of nodes in each class are sampled from node features in the corresponding class of 6 base datasets (Cora, CiteSeer, PubMed, Chameleon, Squirrel, Film). Nodes are randomly splitted into 60%/20%/20% for train/validation/test. We train 1-hop SGC (sgc-1) (Wu et al., 2019) and GCN (Kipf & Welling, 2016) on the synthetic graphs 3. For each value of Hedge(G), we take the average test accuracy and standard deviation of
3See Appendix A.1 for hyperparameter searching range and Appendix B for more detailed description of the data generation process
runs over 10 generated graphs. For each generated graph, we also calculate its Hnode(G), Hclass(G) and HMagg(G). Model performance with respect to different homophily values are shown in Figure 2.
Comparison of Homophily Metrics The performance of SGC-1 and GCN are expected to be monotonically increasing with a proper and informative homophily metric. However, Figure 2(a)(b)(c) show that the performance curves under Hedge(G), Hnode(G) and Hclass(G) are U -shaped 4, while Figure 2(d) reveals a nearly monotonic curve with a little perturbation around 1. This indicates that HMagg(G) can describe how the graph structure affects the performance of SGC-1 and GCN more appropriately and adequately than the existing metrics. (See more discussion on aggregation homophily and theoretical results for regular graphs in Appendix B.)
4 ADAPTIVE CHANNEL MIXING (ACM) FRAMEWORK
High-frequency graph signal, which can be extracted by high-pass filter, is empirically shown to be useful for addressing heterophily problem (Luan et al., 2020b; Chien et al., 2021; Bo et al., 2021). In this section, based on the similarity matrix proposed in equation 5, we will figure out how diversification operation i.e., highpass (HP) filter, is potentially capable to address
some cases of harmful heterophily. From the node-wise analysis, we argue that aggregation (LP filter) and diversification (HP filter) should be combined together as a filterbank (Ekambaram, 2014) for feature extraction and different nodes may have different needs for the information processed by different filters. Based on the above argument, we generalize filterbank method and propose Adaptive Channel Mixing framework in subsection 4.2 to address heterophily challenge.
4.1 HOW DIVERSIFICATION OPERATION HELPS WITH HARMFUL HETEROPHILY
We first consider the example shown in Figure 3. From S(Â,X), we can see that nodes 1,3 assign relatively large positive weights to nodes in class 2 after aggregation, which will make node 1,3 hard to be distinguished from nodes in class 2. Despite the fact, we can still distinguish nodes 1,3 and 4,5,6,7 by considering their neighborhood differences: nodes 1,3 are different from most of their neighbors while nodes 4,5,6,7 are similar to most of their neighbors. This indicates, in some cases, although some nodes become similar after aggregation, they are still distinguishable via their surrounding dissimilarities. This leads us to use diversification operation, i.e., HP filter I − Â (Ekambaram, 2014) to extract the information of neighborhood differences and address harmful heterophily. As S(I − Â,X) in Figure 3 shows, nodes 1,3 will assign negative weights to nodes
4A similar J-shaped curve for Hedge(G) is found in (Zhu et al., 2020b), though using different data generation processes. The authors do not mention the insufficiency of edge homophily.
4,5,6,7 after 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 exist some cases that diversification operation is helpful while aggregation operation is not. Based on this observation, we first define diversification distinguishability of a node and graph diversification distinguishability value as follows to measure the proportion of nodes that diversification operation is potentially helpful for.
Definition 2. Diversification Distinguishability (DD) based on S(I − Â,X).
Given S(I − Â,X), a node v is diversification distinguishable if the following two conditions are satisfied at the same time,
1. Meanu ( {S(I − Â,X)v,u|u ∈ V ∧ Zu,: = Zv,:} ) ≥ 0;
2. Meanu ( {S(I − Â,X)v,u|u ∈ V ∧ Zu,: 6= Zv,:} ) ≤ 0
(9)
Then, graph diversification distinguishability value is defined as
DDÂ,X(G) = 1
|V| ∣∣∣{v|v ∈ V ∧ v is diversification distinguishable}∣∣∣ (10) We can see that DDÂ,X(G) ∈ [0, 1]. Based on definition 2, the effectiveness of diversification operation on addressing heterophily can be proved for binary classification problems under certain conditions, leading us to:
Theorem 1. (See Appendix E for proof). For a binary classification problem, i.e., C = 2, suppose X = Z, Â = Ârw. Then for any I − Ârw, all nodes are diversification distinguishable and DDÂ,Z(G) = 1.
Theorem 1 theoretically demonstrates the importance of diversification operation on handling heterophily. Combined with aggregation operation, we can get a filterbank which uses both LP and HP filters to distinctively extract the low- and high-frequency information from graph signals. We will introduce filterbank in the next subsection.
4.2 FILTERBANK AND ADAPTIVE CHANNEL MIXING (ACM) FRAMEWORK
Filterbank For the graph signal x defined on G, a 2-channel linear (analysis) filterbank (Ekambaram, 2014) 5 includes a pair of low-pass (LP) and high-pass (HP) filters HLP, HHP, where HLP and HHP retain the low-frequency and high-frequency content of x, respectively.
Most existing GNNs are under uni-channel filtering architecture (Kipf & Welling, 2016; Velickovic et al., 2017; Hamilton et al., 2017) with either HLP or HHP channel that only partially preserves the input information. Unlike the uni-channel architecture, filterbanks with HLP + HHP = I will not lose any information of the input signal, i.e., perfect reconstruction property (Ekambaram, 2014). Generally, the Laplacian matrices (Lsym, Lrw, L̂sym, L̂rw) can be regarded as HP filters (Ekambaram, 2014) and affinity matrices (Asym, Arw, Âsym, Ârw) can be treated as LP filters (Maehara, 2019; Hamilton, 2020). Moreover, it can be interpreted that MLPs uses the identity filterbank with HLP = I and HHP = 0 that satisfy HLP +HHP = I + 0 = I .
From Figure 3, we also observe that different nodes may have different needs for the information from different channels, e.g., nodes 1,3 demand information from HP channel while node 2 only needs information from LP channel. To adaptively leverage the LP, HP and identity channels in GNNs, we propose the Adaptive Channel Mixing (ACM) architecture in the following part.
Adaptive Channel Mixing (ACM) Framework ACM framework can be applied to lots of baseline GNNs and in this part, we use GCN as an example to introduce ACM framework in matrix form. We use HLP and HHP to represent general LP and HP filters. The ACM framework includes 3 steps as
5In graph signal processing, an additional synthesis filter (Ekambaram, 2014) 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.
follows, Step 1. Feature Extraction for Each Channel:
Option 1: H lL = ReLU ( HLPH l−1W l−1L ) , H lH = ReLU ( HHPH l−1W l−1H ) , H lI = ReLU ( IH l−1W l−1I ) ;
Option 2: H lL = HLPReLU ( H l−1W l−1L ) , H lH = HHPReLU ( H l−1W l−1H ) , H lI = I ReLU ( H l−1W l−1I ) ; H0 = X ∈ RN×F0 , W l−1L , W l−1 H , W l−1 I ∈ R Fl−1×Fl ; Step 2. Row-wise Feature-based Weight Learning
α̃lL = σ ( H lLW̃ l L ) , α̃lH = σ ( H lHW̃ l H ) , α̃lI = σ ( H lIW̃ l I ) , W̃ l−1L , W̃ l−1 H , W̃ l−1 I ∈ R
Fl×1[ αlL, α l H , α l I ] = Softmax ( ( [ α̃lL, α̃ l H , α̃ l I ] /T )W lMix ) ∈ RN×3, T ∈ R temperature, W lMix ∈ R3×3;
Step 3. Node-wise Adaptive Channel Mixing:
H l = diag(αlL)H l L + diag(α l H)H l H + diag(α l I)H l I (11) The framework with option 1 in step 1 is called ACM framework and with option 2 is named ACMII framework. In step 1, ACM-GCN and ACMII-GCN implement distinct feature extraction for 3 channels by a set of filterbank and 3 filtered components H lL, H l H , H l I are obtained. To adaptively exploit information from each channel, ACM-GCN and ACMII-GCN first extract nonlinear information from the filtered signals, then use W lMix to learn which channel is important or not for each node, leading to the row-wise weight vectors αlL, α l H , α l I ∈ RN×1 whose i-th elements are the weights for the i-th node. These three vectors are then used as weights in defining the updated H l in step 3. See Appendix F for the performance comparison with basline models on synthetic datasets.
Complexity Number of learnable parameters in layer l of ACM-GCN and ACMII-GCN is 3Fl−1(Fl + 1) + 9, while it is Fl−1Fl in GCN. The computation of step 1-3 takes NFl(8 + 6Fl−1) + 2Fl(nnz(HLP) + nnz(HHP)) + 18N flops, while GCN layer takes 2NFl−1Fl + 2Fl(nnz(HLP)) flops, where nnz(·) is the number of non-zero elements. An ablation study and a detailed comparison on running time is conducted in section 6.1. Limitations of Diversification Operation Just like any other method, Diversification operation may not work well in all harmful heterophily cases. For example, when we have more than 2 classes and consider an imbalanced dataset where several small clusters with distinctive labels are densely connected to a large cluster. In this case, the surrounding differences of nodes in small clusters are similar, i.e., the neighborhood differences are mainly from their connection to the same large cluster, and this possibly makes diversification operation fail to discriminate them. See a more detailed demonstration and discussion in Appendix G.
5 PRIOR WORK We discuss relevant work of GNNs on addressing heterophily challenge in this part. Authors in (Abu-El-Haija et al., 2019) acknowledge the difficulty of learning on graphs with weak homophily and propose MixHop to extract features from multi-hop neighborhood to get more information. Authors in (Hou et al., 2019) propose measurements based on feature smoothness and label smoothness that are potentially helpful to guide GNNs on dealing with heterophilous graphs. Geom-GCN (Pei et al., 2020) precomputes unsupervised node embeddings and uses graph structure defined by geometric relationships in the embedding space to define the bi-level aggregation process to handle heterophily. H2GCN (Zhu et al., 2020b) combines 3 key designs to address heterophily: (1) ego- and neighbor-embedding separation; (2) higher-order neighborhoods; (3) combination of intermediate representations. CPGNN (Zhu et al., 2020a) models label correlations by the compatibility matrix, which is beneficial for heterophily settings, and propagates a prior belief estimation into GNNs by the compatibility matrix. FBGNN (Luan et al., 2020b) first proposes to use filterbank to address heterophily problem, but it does not fully explain the insights behind HP filters and does not contain identity channel and node-wise channel mixing mechanism. FAGCN (Bo et al., 2021) learns edgelevel aggregation weights as GAT (Velickovic et al., 2017) but allows the weights to be negative which enables the network to capture the high-frequency components in graph signals. GPRGNN (Chien et al., 2021) uses learnable weights that can be both positive and negative for feature propagation, it allows GPRGNN to adapt heterophily structure of graph and is able to handle both high- and low-frequency parts of the graph signals. (See Appendix J for a more comprehensive comparison between ACM-GNNs, ACMII-GNNs and FAGCN, GPRGNN.)
6 EXPERIMENTS ON REAL-WORLD DATASETS
In this section, we evaluate ACM and ACMII framework on real-world datasets. We first conduct ablation studies in subsection 6.1 to validate the effectiveness of different components. Then, we compare with the state-of-the-arts (SOTA) models in subsection 6.2. The hyperparameter searching range and computing resources for all experiments are attached in Appendix A.
6.1 ABLATION STUDY & EFFICIENCY
We investigate the effectiveness and efficiency of adding HP, identity channels and the adaptive mixing mechanism in the proposed framework by ablation study. Specifically, we apply the components of ACM to SGC-1 (Wu et al., 2019) 6 and the components of ACM and ACMII to GCN (Kipf & Welling, 2016) separately. We run 10 times on each dataset with the same 60%/20%/20% random splits for train/validation/test used in (Chien et al., 2021) and report the average test accuracy as well as the standard deviation. We also record the average running time per epoch (in milliseconds) to compare the efficiency. We set the temperature T in equation 11 to be 3.
From the results we can see that on most datasets, the additional HP and identity channels are helpful, even on strong homophily datasets, such as Cora, CiteSeer and PubMed. The adaptive mixing mechanism also shows its advantage over the method that directly adds the three channels together. This illustrates the necessity of learning to customize the channel usage adaptively for different nodes. As for efficiency, we can see that the running time is approximately doubled under ACM and ACMII framework than the original model. 6.2 COMPARISON WITH STATE-OF-THE-ART MODELS
Datasets & Experimental Setup In this section, we implement SGC (Wu et al., 2019) with 1 hop and 2 hops (SGC-1, SGC-2), GCNII (Chen et al., 2020), GCNII∗ (Chen et al., 2020), GCN (Kipf & Welling, 2016) and snowball networks with 2 and 3 layers (snowball-2, snowball-3) and apply them
6We only test ACM-SGC-1 because SGC-1 does not contrain any non-linearity and ACM-SGC-1 and ACMII-SGC-1 are the same.
GCN snowball-2 snowball-3
80 90 Te st A cc ur
ac y
(% )
Cornell (SOTA=APPNP)
(a) HMagg(G) = 0.8032, ↑ 4.1 % GCN snowball-2 snowball-360
70
80
90
100
Te st
A cc
ur ac
y (%
)
Wisconsin (SOTA=MLP-2)
(b) HMagg(G) = 0.7768, ↑3.13 % GCN snowball-2 snowball-3
80
90
Te st
A cc
ur ac
y (%
)
Texas (SOTA=GPRGNN) SOTA baseline GNNs ACM-baseline ACMII-baseline
(c) HMagg(G) = 0.694, ↑2.82 %
in ACM or ACMII framework7: we use Ârw as LP filter and the corresponding HP filter is I − Ârw and they are deterministic. We compare them with several baseline and SOTA GNN models: MLP with 2 layers (MLP-2), GAT (Velickovic et al., 2017), APPNP (Klicpera et al., 2018), GPRGNN (Chien et al., 2021), H2GCN (Zhu et al., 2020b), MixHop (Abu-El-Haija et al., 2019), GCN+JK (Kipf & Welling, 2016; Xu et al., 2018; Lim et al., 2021), GAT+JK (Velickovic et al., 2017; Xu et al., 2018; Lim et al., 2021), FAGCN (Bo et al., 2021) GraphSAGE (Hamilton et al., 2017) and Geom-GCN (Pei et al., 2020). Besides the 9 benchmark datasets Cornell, Wisconsin, Texas, Film, Chameleon, Squirrel, Cora, Citeseer and Pubmed used in (Rozemberczki et al., 2021; Pei et al., 2020), we further test the above models on a new benchmark dataset, Deezer-Europe, that is proposed in (Rozemberczki & Sarkar, 2020). On each dataset used in (Rozemberczki et al., 2021; Pei et al., 2020), we test the models 10 times following the same early stopping strategy, the same random data splitting method 8 and Adam (Kingma & Ba, 2014) optimizer as used in GPRGNN (Chien et al., 2021). For Deezer-Europe, we test the above models 5 times with the same early stopping strategy, the same fixed splits and AdamW (Loshchilov & Hutter, 2017) used in (Lim et al., 2021).
To better visualize the performance boost and the comparison with SOTA models, in Figure 4, we plot the bar charts of the test accuracy of SOTA models, 3 selected baselines (GCN, snowball-2, snowball-3) and their ACM and ACMII augmented models on 6 most commonly used benchmark heterophily datasets (See table 4 in Appendix A.3 for the full results and comparison). We can see that after being applied in ACM or ACMII framework, the performance of the 3 baseline models are significantly boosted on all tasks and can achieve SOTA performance. Especially on Cornell, Texas, Film and Squirrel, the augmented models significantly outperform the current SOTA models. Overall, It suggests that ACM or ACMII framework can help GNNs to generalize better on node classification tasks on heterophilous graphs.
7GCNII and GCNII∗ are hard to be implemented under ACMII framework. See Appendix A.6 for explanation. 8See table 9 in Appendix I for the performance comparison with several SOTA models on the fixed
48%/32%/20% splits provided by (Pei et al., 2020).
REFERENCES Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr
Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21–29. PMLR, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00797, 2021.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. arXiv, abs/1611.08097, 2016. URL http:// arxiv.org/abs/1611.08097.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725–1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. https://openreview. net/forum, 2021.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv, abs/1606.09375, 2016. URL http: //arxiv.org/abs/1606.09375.
Venkatesan Nallampatti Ekambaram. Graph structured data viewed through a fourier lens. University of California, Berkeley, 2014.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02428, 2019.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645–6649. Ieee, 2013.
William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1–159, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv, abs/1706.02216, 2017. URL http://arxiv.org/abs/1706.02216.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference on Learning Representations, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv, abs/1609.02907, 2016. URL http://arxiv.org/abs/1609.02907.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097–1105, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on nonhomophilous graphs. arXiv preprint arXiv:2104.01404, 2021.
Vijay Lingam, Rahul Ragesh, Arun Iyer, and Sundararajan Sellamanickam. Simple truncated svd based model for node classification on heterophilic graphs. arXiv preprint arXiv:2106.12807, 2021.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint arXiv:2005.14612, 2020.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multiscale deep graph convolutional networks. arXiv preprint arXiv:1906.02174, 2019.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. arXiv preprint arXiv:2008.08838, 2020a.
Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao-Wen Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008.08844, 2020b.
Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550, 2019.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415–444, 2001.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Benedek Rozemberczki and Rik Sarkar. Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM ’20), pp. 1325–1334. ACM, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv, abs/1710.10903, 2017.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv:1902.07153, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453–5462. PMLR, 10–15 Jul 2018. URL http://proceedings.mlr.press/v80/xu18c.html.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009.13566, 2020a.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020b.
A HYPERPARAMETERS & DETAILS OF THE EXPERIMENTS
A.1 HYPERPARAMETER SEARCHING RANGE FOR SYNTHETIC EXPERIMENTS
A.2 HYPERPARAMETER SEARCHING RANGE FOR ABLATION STUDY
A.3 FULL RESULTS OF THE COMPARISON WITH SOTA MODELS
The main results of the full sets of experiments 9 with statistics of datasets are summarized in Table 4, where we report the mean accuracy and standard deviation. We can see that after applied in ACM or ACMII framework, the performance of baseline models are boosted on almost all tasks and achieve SOTA performance on 8 out of 10 datasets. Especially, ACMII-GCN performs the best in terms of average rank (3.40) across all datasets. Overall, It suggests that ACM or ACMII framework can significantly increase the performance of GNNs on node classification tasks on heterophilous graphs.
A.4 HYPERPARAMETER SEARCHING RANGE FOR GNNS ON REAL-WORLD DATASETS
See table 5 for the hyperparameter seaching range of baseline GNNs, ACM-GNNs, ACMII-GNNs and several SOTA models.
A.5 OPTIMAL HYPERPARAMETERS FOR BASELINES AND ACM(II)-GNNS ON REAL-WORLD TASKS
See the reported optimal hyperparameters for baseline GNNs in table 6 and for ACM-GNNs and ACMII-GNNs in table 7.
9The splits for all these experiments are random 60%/20%/20% splits for train/valid/test. The open source code we use is from https://github.com/jianhao2016/GPRGNN/blob/ f4aaad6ca28c83d3121338a4c4fe5d162edfa9a2/src/utils.py#L16. See table 9 in Appendix I for the performance comparison with several SOTA models on the fixed 48%/32%/20% splits provided by (Pei et al., 2020).
A.6 DETAILS OF THE IMPLEMENTATION OF ACM AND ACMII FRAMEWORKS
Unlike some baseline GNN models, in ACM(II) framework, we first use dropout operation over the input data. The implementation of ACM(II)-GCN and ACM(II)-snowball is straightforward, but SGC-1, SGC-2, GCNII and GCNII* are not able to be applied under ACM(II) framework and we will make an explanation as follows.
• SGC-1 and SGC-2: SGC does not contain nonlinearity, so the option 1 and option 2 in step 1 of equation 11 is the same for ACM-SGC and ACMII-SGC. Thus, we only implement ACM-SGC.
• GCNII and GCNII*: GCNII: H(`+1) = σ (( (1− α`) ÂH(`) + α`H(0) )( (1− β`) In + β`W(`) ))
GCNII*: H(`+1) = σ ( (1− α`) ÂH(`) ( (1− β`) In + β`W(`)1 ) + +α`H (0) ( (1− β`) In + β`W(`)2 ))
From the above architecture of GCNII and GCNII∗ we cam see that, without major modification, GCNII and GCNII* are hard to be put into ACMII framework. In ACMII framework, before apply Â, we first implement a nonlinear feature extractor σ(H`W(`)). But in GCNII and GCNII*, before multiplyingW `(or W `1 ,W ` 2 ) to extract features, we need to add another term including H(0), which are not filtered by Â. This makes the order of aggregator Â and nonlinear extractor unexchangable and thus, incompatible with ACMII framework. So we did not implement GCNII and GCNII* in ACMII framework.
The open source code is attached in the supplementary material.
A.7 COMPUTING RESOURCES
For all experiments on synthetic datasets and real-world datasets, we use NVidia V100 GPUs with 16/32GB GPU memory, 8-core CPU, 16G Memory. The software implementation is based on PyTorch and PyTorch Geometric (Fey & Lenssen, 2019).
B EXPERIMENTAL SETUP AND FURTHER DISCUSSION ON SYNTHETIC GRAPHS
B.1 DETAILED DESCRIPTION OF DATA GENERATION PROCESS
• For each node v, we first randomly generate its degree dv . • Given dv , we sample hdv intra-class edges and (1− h)dv inter-class edges.
More specifically in our synthetic experiments, for a given h,
• we generate node degree dv for nodes in each class from multinomial distribution with numpy.random.multinomial(800/h, numpy.ones(400)/400, size=1)[0].
• For a sampled dv, we generate intra-class edges from (does not include self-loop) numpy.random.multinomial(hdv, numpy.ones(399)/399, size=1)[0] and inter-class edges from numpy.random.multinomial((1-h) dv, numpy.ones(1600)/1600, size=1)[0].
We will release the code and the generated data later.
B.2 FURTHER DISCUSSION OF AGGREGATION HOMOPHILY ON REGULAR GRAPHS
We notice that in Figure 2(a), the performance of SGC-1 and GCN both have a turning point, i.e., whenHedge(G) is smaller than a certain value, the performance will get better instead of getting worse. With some extra restriction on node degree in data generation process, we find that this interesting phenomenon can be theoretically explained by the following proposition 1 based on our proposed similarity matrix which can verify the usefulness of HMagg(G). We first generate regular graphs ,i.e., each node has the same degree, as follows,
Generate Synthetic Regular Graphs We first generate 180 graphs in total with 18 edge homophily levels varied from 0.05 to 0.9, each corresponding to 10 graphs. For every generated graph, we have 5 classes with 400 nodes in each class. For each node, we randomly generate 10 intra-class edges and [ 10Hedge(G) − 10] inter-class edges. The features of nodes in each class are sampled from node features in the corresponding class of the base dataset. Nodes are randomly split into 60%/20%/20% for train/validation/test. We train 1-hop SGC (sgc-1) Wu et al. (2019) and GCN Kipf & Welling (2016) on synthetic data (see Appendix A.1 for hyperparameter searching range). For each value of Hedge(G), we take the average test accuracy and standard deviation of runs over 10 generated graphs. We plot the performance curves in Figure 5.
From Figure 5 we can see that the turning point is a bit less than 0.2. We derive the following proposition for d-regular graph to explain and predict it.
Proposition 1. (See Appendix D for proof). Suppose there are C classes in the graph G and G is a d-regular graph (each node has d neighbors). Given d, edges for each node are i.i.d.generated, such
that each edge of any node has probability h to connect with nodes in the same class and probability 1− h to connect with nodes in different classes. Let the aggregation operator Â = Ârw. Then, for nodes v, u1 and u2, where Zu1,: = Zv,: and Zu2,: 6= Zv,:, we have
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 (12)
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 expected number of neighbors of a node that have the same label as the node.
The value of g(h) in equation 12 is the expected differences of the similarity values between nodes in the same class as v and nodes in other classes. g(h) is strongly related to the definition of aggregation homophily and its minimum potentially implies the turning point of performance curves. In the synthetic experiments, we have dintra = 10, C = 5 and the minimum of g(h) is reached at h = 5/27 ≈ 0.1852, which corresponds to the lowest point in the performance curve in Figure 5. In other words, the Hedge(G) where SGC-1 and GCN perform worst is where g(h) gets the smallest value, instead of the point with the smallest edge homophily value Hedge(G) = 0. This reveals the advantage of Hagg(G) over Hedge(G) by taking use of the similarity matrix.
C DETAILS OF GRADIENT CALCULATION IN EQUATION 5
C.1 DERIVATION IN MATRIX FORM
This derivation is similar to (Luan et al., 2020a).
In output layer, we have
Y = softmax(ÂXW ) ≡ softmax(Y ′) = ( exp(Y ′)1C1 T C )−1 exp(Y ′) > 0 L = −trace(ZT log Y )
where 1C ∈ RC×1, (·)−1 is point-wise inverse function and each element of Y is positive. Then
dL = −trace ( ZT ((Y )−1 dY ) ) = −trace ( ZT ( (softmax(Y ′))−1 d softmax(Y ′) ))
Note that
d softmax(Y ′) =− ( exp(Y ′)1C1 T C )−2 [(exp(Y ′) dY ′)1C1TC ] exp(Y ′) + ( exp(Y ′)1C1 T C
)−1 (exp(Y ′) dY ′) =− softmax(Y ′) ( exp(Y ′)1C1 T C
)−1 [(exp(Y ′) dY ′)1C1TC ] + softmax(Y ′) dY ′
= softmax(Y ′) ( − ( exp(Y ′)1C1 T C )−1 [(exp(Y ′) dY ′)1C1TC]+ dY ′)
Then,
dL = − trace ( ZT ( (softmax(Y ′))−1 [ softmax(Y ′) ( − ( exp(Y ′)1C1 T C
)−1 [ (exp(Y ′) dY ′)1C1TC ] + dY ′
)])) = − trace ( ZT ( − ( exp(Y ′)1C1 T C
)−1 [(exp(Y ′) dY ′)1C1TC]+ dY ′)) = trace ((( Z ( exp(Y ′)1C1 T C )−1) 1C1 T C )T [exp(Y ′) dY ′]− ZT dY ′
) = trace (( exp(Y ′) (( Z ( exp(Y ′)1C1 T C )−1) 1C1 T C ))T dY ′ − ZT dY ′
) = trace (( exp(Y ′) ( exp(Y ′)1C1 T C )−1)T dY ′ − ZT dY ′
) = trace ( (softmax(Y ′)− Z)T dY ′
) where the 4-th equation holds due to ( Z ( exp(Y ′)1C1 T C )−1) 1C1 T C = ( exp(Y ′)1C1 T C )−1 . Thus,
we have dL dY ′ = softmax(Y ′)− Z = Y − Z For Y ′ and W , we have
dY ′ = ÂXdW and dL = trace ( dL dY ′ T dY ′ ) = trace ( dL dY ′ T ÂX dW ) = trace ( dL dW T dW )
To get dLdW we have, dL dW = XT ÂT dL dY ′ = XT ÂT (Y − Z) (13)
C.2 COMPONENT-WISE DERIVATION
Denote X̃ = XW . We rewrite L as follows: L = −trace ( ZT log ( (exp(Y ′)1C1 T C) −1 exp(Y ′) )) = −trace ( ZT ( − log(exp(Y ′)1C1TC) + Y ′
)) = −trace ( ZTY ′ ) + trace ( ZT log ( exp(Y ′)1C1 T C
)) = −trace ( ZT ÂXW ) + trace ( ZT log ( exp(Y ′)1C1 T C
)) = −trace ( ZT ÂXW ) + trace ( 1TC log (exp(Y ′)1C) ) = − N∑ i=1 ∑ j∈Ni Âi,jZi,:X̃ T j: + N∑ i=1 log  C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
 = −
N∑ i=1 log
exp  C∑
c=1 ∑ j∈Ni Âi,jZi,cX̃j,c + N∑ i=1 log  C∑ c=1 exp ∑ j∈Ni Âi,jX̃j,c
= − N∑ i=1 log exp
( C∑
c=1 ∑ j∈Ni Âi,jZi,cX̃j,c ) (
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
)
Note that C∑
c=1 Zj,c = 1 for any j. Consider the derivation of L over X̃j′,c′ :
dL dX̃j′,c′
=− N∑ i=1
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
exp
( C∑
c=1 ∑ j∈Ni Âi,jZi,cX̃j,c
)
×  ( Âi,j′Zi,c′ ) exp ( C∑ c=1 ∑ j∈Ni Âi,jZi,cX̃j,c )( C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c) ) (
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
)2
−
( Âi,j′ ) exp
( C∑
c=1 ∑ j∈Ni Âi,jZi,cX̃j,c
)( exp(
∑ j∈Ni Âi,jX̃j,c′) ) (
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
)2
=− N∑ i=1  ( Âi,j′Zi,c′ )( C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c) ) − ( Âi,j′ )( exp( ∑ j∈Ni Âi,jX̃j,c′) ) (
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
)
=− N∑ i=1 Âi,j′ ( C∑ c=1,c 6=c′ (Zi,c′) exp( ∑ j∈Ni Âi,jX̃j,c) ) + (Zi,c′ − 1) ( exp( ∑ j∈Ni Âi,jX̃j,c′) ) (
C∑ c=1 exp( ∑ j∈Ni Âi,jX̃j,c)
)
=− N∑ i=1 Âi,j′ ( Zi,c′ P̂ (Yi 6= c′) + (Zi,c′ − 1)P̂ (Yi = c′) ) =−
N∑ i=1 Âi,j′ ( Zi,c′ − P̂ (Yi = c′) ) Writing the above in matrix form, we have
dL dX̃ = Â(Z − Y ), dL dW̃ = XT ÂT (Z − Y ), ∆Y ′ ∝ ÂXXT ÂT (Z − Y ) (14)
D PROOF OF PROPOSITION 1
Proof. According to the given assumptions, for node v, we have Âv,k = 1d+1 , the expected number of intra-class edges is dh (here the self-loop edge introduced by Â is not counted based on the definition of edge homophily and data generation process) and inter-class edges is (1− h)d. Suppose there are C ≥ 2 classes. Consider matrix ÂZ,
Then, we have E [ (ÂZ)v,c ] = E [ ∑ k∈V Âv,k1{Zk,:=eTc } ] = ∑ k∈V E [ 1{Zk,:=eTc } ] d+1 , where 1 is the indicator function.
When v is in class c, we have ∑ k∈V E [ 1{Zk,:=eTc } ] d+1 = hd+1 d+1 (hd+1 = hd intra-class edges + 1 self-loop
introduced by Â). When v is not in class c, we have ∑ k∈V E [ 1{Zk,:=eTc } ] d+1 = (1−h)d (C−1)(d+1) ((1 − h)d inter-class edges uniformly distributed in the other C − 1 classes).
For nodes v, u, we have (ÂZ)v,:, (ÂZ)u,: ∈ RC and since elements in Âv,k and Âu,k′ are independently generated for all k, k′ ∈ V , we have
E [ (ÂZ)v,c(ÂZ)u,c ] = E [ ( ∑ k∈V Âv,k1{Zk,:=eTc })( ∑ k′∈V Âu,k′1{Zk′,:=eTc }) ]
= E [ ( ∑ k∈V Âv,k1{Zk,:=eTc }) ] E [ ( ∑ k′∈V Âu,k′1{Zk′,:=eTc }) ] Thus,
E [ S(Â, Z)v,u ] = E [ < (ÂZ)v,:, (ÂZ)u,: > ] = ∑ c E [ ( ∑ k∈V Âv,k1{Zk,:=eTc }) ] E [ ( ∑ k′∈V Âu,k′1{Zk′,:=eTc }) ]
=  ( hd+1 d+1 )2 + ((1−h)d) 2
(C−1)(d+1)2 , u, v are in the same class 2(hd+1)(1−h)d (C−1)(d+1)2 + (C−2)(1−h)2d2 (C−1)2(d+1)2 , u, v are in different classes
For nodes u1, u2, and v, where Zu1,: = Zv,: and Zu2,: 6= Zv,:, g(h) ≡ E [ S(Â, Z)v,u1 ] − E [ S(Â, Z)v,u2 ] (15)
= (C − 1)2(hd+ 1)2 + (C − 1) [(1− h)d]2 − (C − 1) (2(hd+ 1)(1− h)d)− (C − 2) [(1− h)d]2
(C − 1)2(d+ 1)2
=
( (C − 1)(hd+ 1)− (1− h)d
(C − 1)(d+ 1) )2 Setting g(h) = 0, we obtain the optimal h:
h = d+ 1− C
Cd (16)
For the data generation process in the synthetic experiments, we fix dintra, then d = dintra/h, which is a function of h. We change d in equation 16 to dintra/h, leading to
h = dintra/h+ 1− C
Cdintra/h (17)
It is easy to observe that h satisfying equation 17 still makes g(h) = 0, when d in g(h) is replaced by dintra/h. From equation 17 we obtain the optimal h in terms of dintra:
h = dintra
Cdintra + C − 1
D.1 AN EXTENSION OF PROPOSITION 1
Base on the definition of aggregation similarity, we have
Sagg
( S(Â, Z) ) = ∣∣∣{v ∣∣Meanu({S(Â, Z)v,u|Zu,: = Zv,:}) ≥ Meanu({S(Â, Z)v,u|Zu,: 6= Zv,:})}∣∣∣ |V|
=
∑ v∈V 1{ Meanu ( {S(Â,Z)v,u|Zu,:=Zv,:} ) ≥Meanu ( {S(Â,Z)v,u|Zu,: 6=Zv,:} )} |V|
Then, E ( Sagg ( S(Â, Z) )) = E  ∑ v∈V 1{ Meanu ( {S(Â,Z)v,u|Zu,:=Zv,:} ) ≥Meanu ( {S(Â,Z)v,u|Zu,: 6=Zv,:} )} |V|
=
∑ v∈V P ( Meanu ( {S(Â, Z)v,u|Zu,: = Zv,:} ) ≥ Meanu ( {S(Â, Z)v,u|Zu,: 6= Zv,:} )) |V|
= P ( Meanu ( {S(Â, Z)v,u|Zu,: = Zv,:} ) −Meanu ( {S(Â, Z)v,u|Zu,: 6= Zv,:} ) ≥ 0 )
Consider the random variable RV = Meanu ( {S(Â, Z)v,u|Zu,: = Zv,:} ) −Meanu ( {S(Â, Z)v,u|Zu,: 6= Zv,:} ) Since RV is symmetrically distributed and under the conditions in proposition 1, its expectation is E[RV ] = g(h) as showed in equation 15. Since the minimum of g(h) is 0 and RV is symmetrically distributed, we have P(RV ≥ 0) ≥ 0.5 and this can explain why Hagg(G) is always greater than 0.5 in many real-world tasks.
E PROOF OF THEOREM 1
Proof. Define W cv = (ÂZ)v,c. Then,
W cv = ∑ k∈V Âv,k1{Zk,:=eTc } ∈ [0, 1], C∑ c=1 W cv = 1
Note that
S(I − Â, Z) = (I − Â)ZZT (I − Â)T = ZZT + ÂZZT ÂT − ÂZZT − ZZT ÂT (18)
For any node v, let the class v belongs to be denoted by cv. For two nodes v, u, if Zv,: 6= Zu,:, we have
(ZZT )v,u = 0
(ÂZZT ÂT )v,u = C∑ c=1 W cvW c u
(ÂZZT )v,u = W cu v
(ZZT ÂT )v,u = (ÂZZ T )u,v = W cv u
Then, from equation 18 it follows that
(S(I − Â, Z))v,u = C∑
c=1
W cvW c u −W cuv −W cvu
When C = 2,
S(I − Â, Z)v,u = W cuv (W cuu − 1) +W cvu (W cvv − 1) ≤ 0
If Zv,: = Zu,:, i.e., cv = cu, we have
(ZZT )v,u = 1
(ÂZZT ÂT )v,u = C∑ c=1 W cvW c u
(ÂZZT )v,u = W cv v
(ZZT ÂT )v,u = (ÂZZ T )u,v = W cu u = W cv u
Then, from equation 18 it follows that
S(I − Â, Z)v,u = 1 + C∑
c=1
W cvW c u −W cvv −W cvu
= C∑ c=1,c 6=cv W cvW c u + 1 +W cv v W cv u −W cvv −W cvu
= C∑ c=1,c 6=cv W cvW c u + (1−W cvv )(1−W cvu ) ≥ 0
Thus, if C = 2, for any v ∈ V , if Zu,: 6= Zv,:, we have S(I − Â, Z)v,u ≤ 0; if Zu,: = Zv,:, we have S(I − Â, Z)v,u ≥ 0. Apparently, the two conditions in equation 9 are satisfied. Thus v is diversification distinguishable and DDÂ,X(G) = 1. The theorem is proved.
F MODEL COMPARISON ON SYNTHETIC GRAPHS
In order to separate the effects of nonlinearity and graph structure, we compare sgc with 1 hop (sgc-1) with MLP-1 (linear model). For GCN which includes nonlinearity, we use MLP-2 as its corresponding graph-agnostic baseline model. We train the above GNN models, graph-agnostic baseline models and ACM-GNN models on all synthetic datasets and plot the mean test accuracy with standard deviation on each dataset. From Figure 6 and Figure 7, we can see that on each HMagg(G) level, ACM-GNNs will not underperform baseline GNNs and the graph-agnostic models. But when HMagg(G) is small, baseline GNNs will be outperformed by graph-agnostic models by a large margin. This demonstrate the advantage of the ACM framework. The curves will almost be the same for ACMII framework.
G DISCUSSION OF THE LIMITATIONS OF DIVERSIFICATION OPERATION
From the black box area of S(I − Â,X) in the example in Figure 8 we can see that nodes in class 1 and 4 assign non-negative weights to each other although there is no edge between them; nodes in class 2 and 3 assign non-negative weights to each other as well. This is because the surrounding differences of class 1 are similar as class 4, so are class 2 and 3. In real-world applications, when
nodes in several small clusters connect to a large cluster, the surrounding differences of the nodes in the small clusters will become similar. In such case, HP filter are not able to distinguish the nodes from different small clusters.
H THE SIMILARITY, HOMOPHILY AND DDÂ,X(G) METRICS AND THEIR ESTIMATIONS
Additional Metrics There are three key factors that influence the performance of GNNs in realworld tasks: labels, features and graph structure. The (modified) aggregation homophily tries to investigate how the consistency of graph structure and labels will influence the performance of GNNs with features being fixed. And their correlation is verified through the synthetic experiments.
Besides graph-label consistency, we need to consider feature-label consistency and aggregatedfeature-label consistency as well to fully investigate the performance of NNs and GNNs. With aggregation similarity score of the features Sagg (S(I,X)) and aggregated features Sagg ( S(Â,X) ) listed in table 8, our methods open up a new perspective on analyzing and comparing the performance of graph-agnostic models and graph-aware models in real-world tasks. Here are 2 examples.
Example 1: People observe that GCN (graph-aware model) underperforms MLP-2 (graph-agnostic model) on Cornell, Wisconsin, Texas, Film. Based on the aggregation homophily, the graph structure is not the main cause of the performance degradation. And from Table 6 we can see that the Sagg ( S(Â,X) ) for the above 4 datasets are lower than their corresponding Sagg (S(I,X)), which
implies that it is the aggregated-feature-label inconsistency that causes the performance degradation.
Example 2: According to the widely used analysis based on node or edge homophily, the graph structure of Chameleon, and Squirrel are heterophilous and bad for GNNs. But in practice, GCN outperforms MLP-2 on those 2 datasets which means the additional graph information is helpful for node classification instead of being harmful. Traditional homophily metrics fail to explain such phenomenon but our method can give an explanation from different angles: For Chameleon, its modified aggregation homophily is not low and its Sagg ( S(Â,X) ) is higher than its Sagg (S(I,X))
which means its graph-label consistency and aggregated-feature-label consistency help the graphaware model obtain the performance gain; for Squirrel, its modified aggregation homophily is low but its Sagg ( S(Â,X) ) is higher than its Sagg (S(I,X)) which means although its graph-label consistency
is bad but the aggregated-feature-label consistency is the key factor to help the graph-aware model perform better.
We also need to point out that (modified) aggregation similarity score, Sagg ( S(Â,X) ) and
Sagg (S(I,X)) are not deciding or threshold values because they do not consider the nonlinear structure in the features. In practice, a low score does not tell us the GNN models will definitely perform bad.
Furthermore, in most real-world applications, not all labels are available to calculate the dataset statistics. In this section, We randomly split the data into 60%/20%/20% for training/validation/test, and only use the training labels for the estimation of the statistics. We repeat each estimation for 10 times and report the mean with standard deviation. The results are shown in table 8.
Analysis From the reported results we can see that the estimations are accurate and the errors are within the acceptable range, which means the proposed metrics and similarity scores can be accurately estimated with a subset of labels and this is important for real-world applications.
I EXPERIMENTS ON FIXED SPLITS PROVIDED BY (PEI ET AL., 2020)
See table 9 for the results and table 10 the optimal searched hyperparameters.
J A DETAILED EXPLANATION OF THE DIFFERENCES BETWEEN ACM-GNNS, ACM(II)-GNNS AND GPRGNN, FAGCN
• Difference with GPRGNN (Chien et al., 2021): To explain how the channel mixing mechanism makes ACM-GNNs and ACMII-GNNs different from the learning mecha-
nism in GPRGNN, we first rewrite GPRGNN as Z = K∑
k=0
γkH (k) = K∑ k=0 γkIH (k) =
K∑ k=0 diag(γk, γk, . . . , γk)H (k). The node-wise channel mixing mechanism in GPRGNN
form is Z = K∑
k=0
diag(γ1k, γ 2 k, . . . , γ N k )H (k), where N is the number of nodes and
γik, i = 1, . . . , N are learnable parametric mixing weights for different channels. ACM and ACMII allow GNNs to learn more diverse parameters in diagonal than GPRGNN and thus, have stronger expressive power than GPRGNN.
• Difference with FAGCN (Bo et al., 2021): instead of using a fixed Â, FAGCN learns a new filter Â′ based on Â in a similar way as GAT (Velickovic et al., 2017). Some people may take Â′ as a mixing matrix and think it is similar to our channel mixing mechanism, but Â′ is essentially a learnable aggregator or LP filter for LP channel, which is far different from channel mixing. And Â′ can be decomposed into Â′ = Â′1 − Â′2, where Â′1 and −Â′2 represents positive and negative edge (propagation) information respectively. In our paper, we are not discussing the advantages of using the learned filter Â′ over the fixed filter Â, we are comparing the models with and without channel mixing mechanism. We believe the empirical results on real-world tasks in table 4 and table 9 is the best way to compare the models with fixed filter and node-wise channel mixing and the models with learned filter but without channel mixing

title: IS HETEROPHILY A REAL NIGHTMARE FOR GRAPH NEURAL NETWORKS ON PERFORMING NODE CLASSI-