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

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

Under review as a conference paper at ICLR 2022
Is HETEROPHILY A REAL NIGHTMARE FOR GRAPH NEURAL NETWORKS ON PERFORMING NODE CLASSI- FICATION?
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based 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 het- erophily are harmfu for GNNs with aggregation operation. Then, we propose new metries based on similarity matrix which considers the influence of both graph structure and input features on GNNs. The metrics demonstrate advantages over the commonly used homophily metries 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 real- world node classification tasks. They consistently achieve significant performance gain and exceed the state-of- ofate-of-the-ar the-art GNNs on most of the tasks without incurring significant computational burden.
INTRODUCTION
Deep Neural Networks (NNs) (LeCun et al. 2015) have revolutionized many machine learning areas, including image recognition (Krizhessky et al. 2012). speech recognition (Graves et al. 2013)
and natural language processing (Bahdanau et al. 2014). etc. One major strength 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 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 [016]] Luan et 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 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- Perceptrons (MLPs) can outperform GNNs by a large margin (Zhu et al.) |020b] Liu et al. 2020 Luan et al. 2020b Chien al. 202T). An important reason for the performance degradation 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. (02T).
In general, harmful heterophily means the heterophilous lous structure that will make graph-aware model underperform corresponding graph-agnostic model.

---

Under review as a conference paper at ICLR 2022
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 similarity matrix from backpropagation analysis, we derive new homophily metrics to depict how much GNNs 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 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 obtaín significant performance boost on node classification tasks on heterophilous graphs.
The rest of this paper mainly organized as follows: In section 2 we introduce the notation and the background knowledge. In section we conduct node-wise analysis on heterophily, derive new homophily metries based on a similarity matrix and conduct experiments to show their advantages over the existing homophily metries. 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 = EV,E, A), where V is the node set with |V| N; E is the edge set without self- A IR NxN the symmetric adjacency matrix with Ar, = 1 iff Eij E E, otherwise A., = O. We use D to denote the diagonal degree matrix of 9, Le., D d, = Ej Arg and use A₁ denote the neighborhood set of node i, i.e.
N₁ = {j Eij E E}. A graph signal is a vector x E R-V defined on V. where I; is defined on the node i. We also have a feature matrix X E RNN xF, whose columns are graph signals and whose i-th row X4, is feature vector of node i. We use Z E R- to denote the label encoding matrix, whose i-th row Z 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 Semi- Definite (SPSD) (Chung & Graham 1997). Its eigendecomposition gives L = UAUT, where the columns u, of U XMV are orthonormal eigenvectors, namely the graph Fourier basis, A diag(A),.... AN) with X1 f ... S AN. and these eigenvalues are also called frequencies. The graph Fourier transform of the graph signal where u.! a: is the component of in the direction of ug-
defined as FF --t U |uf x ... u N
In additional to L, some variants are also commonly used, e.g. the symmetric normalized Laplacian Laym = D- 1/2 LD- 1/2
D-1/2 10/2ADD-32 AD-1/2 and the random walk normalized Laplacian Liw D- = - A. 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 T I. D A. Asm = -Lyym = D D-11 AD 1/2 and are considered to be low-pass (LP) filters (Machara 2019).
Their eigenvalues satisfy X₂ (A = Xx (Aym) = (I
\x(( E 1.. Applying the renormalization trick (Kipf & Welling 2016) to affinity and Laplacian matrices respectively
leads to A.ym D-1/2 11/1 and Toym = T Asm. where Á = A + / and か = D + J. 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 (eftmax(Aggm ReLU (eLLUAAsmmXWW Wi)
(I)
where Wo E FF and W1 E R xo are learnable parameter matrices. GCN can be trained by minimizing the following cross entropy loss
L = trace 27 log Y)
2

---

Under review as a conference paper at ICLR 2022
where log(-) is component wise logarithm operation. The random walk renormalized matrix An カ-1A, A, which shares the same eigenvalues as Asm- can also be applied in GCN. The corresponding Laplacian is defined as Liw = A.w. The matrix Aew is essentially a random walk matrix and behaves mean aggregator that is applied in spatial-based GNNs (Hamilton al. Hamilton 2020). To bridge the spectral and spatial methods, use dn in the paper.
2017
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 metries: edge homophily (Abu-aI-Haija et al.) 2019 Zhu et al. (2000)), node homophily (Pei et al. 2020).
and class homophily (Lim et 2021 defined as follows:
(Fav Cuo E E, Zu, = Zoo!l
1 DV
{u E No, = Zmo
Hedge (G)
(
(G)
[8]
dn
DEV
{vl
Zonk k
1
hy Evev Yu Zn, L, No, Zu.: Zu Ene(v de
Helass (9)
hipe
C
(3) where [a]+ max 0); he is the class-wise homophily metric (Lim et al. 2021). They are all in the range [0, 1] and a value close to corresponds to strong homophily while a value close to indicates strong heterophily. (9) measures the proportion of edges that connect two nodes in the same class; Hnnde evaluates the average proportion of edge-label consistency of all nodes; (9) tries to avoid the sensitivity to imbalanced class, which cause Hedge (9) misleadingly large. The above definitions are all based on the graph-label consistency and imply that the inconsistency will cause negative effect 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.
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 2021) be- cause intuitively features of nodes different classes will be falsely mixed and this will lead nodes indistinguishable (Zhu al. 2020b). Nev- ertheless, it is not always the case, e.g., the bi- partite graph shown in Figure iss highly het- erophilous according the existing homophily metrics in equation 3 but after mean aggrega- tion (operated by
Class
Metries:
After
Hedge(G)
Aggrogation
(G) m0
Hetess (G)
Hagg (G)
Hage (G) =1
aggregator), the nodes in classes and 2 only exchange colors and are still distinguishable. Authors in (Chien al.) 2021) also point out the insufficiency of Haste by examples to show that different graph typologies with the same (9) can carry different label information.
Figure 1: Example of harmless heterophily
To analyze to what extent the graph structure can affect the output of a GNN, we first simplify GCN by removing its nonlinearity (Wu et al. 2019). Let Á E NNNN denote general aggregation operator. Then, equation can be simplified as,
Y softmax(AxW) softmax(Y")
(4)
Thh authors in [Lm et al. 2021 did not name this homophily metric. We name it class homopkily based on its definition.
3

---

Under review as a conference paper at ICLR 2022
dc After each gradient decent step AW Y aw (see Appendix[[ for derivation),
where y is the learning rate, the update of Y' will be
AY' = AxAW - 7Ax dC dW x Ax dc
(5)
dw -
where S(A, Á is post-aggregation node similarity matrix, Z - Y is the prediction error matrix. The update direction of node is essentially a weighted sum of the prediction error, i.e.,
A Ejev (((.A)) i.j
Y))
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
Soze (S(A,X)) K [eMMa ((S(A, X), Zu. Zo;}) 2 Mcan,, (IS(A, Zu, # Ze:
M
(6)
where Meana (1-3) takes the average over u of given multiset of values or variables.
V that will put relatively larger similar- ity weights on nodes in the same class than in other classes after aggregation. It is easy to see that Sage (S X)) E [0. 1]. But in practice, we observe that in most datasets, we will have Sage (S(, x)) 2 0.5. Based on this observation, we rescale equation
Sage (A) measures the proportion of nodes
6 the following modified
aggregation similarity for practical usage,
S.M (((A))) [25 (S(A, - 11
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 (9) aggregation (Å) homophily and its modified version as
Hagg (G) Sags (5(,, H (G) StMd (S(Á,
(8)
In practice, we will only check (nee(() when 1. (9) O. As Figure shows, when À A (9) = Hig = 1. 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 (9) and H. (g) by
additionally exploiting information from aggregation operator Á and the similarity matrix.
To comprehensively compare M (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 edge (9) verify the effectiveness of H HMM (9) and compare it with the existing metrics.
(9) to empirically
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 800
[ 800] inter-class edges. The features of nodes in each class
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%//0%% for train/validationntess. We train 1hhop SGC (sgc-/) (Wu et al.] 2019) and GCN (Kipf & Welling, 2016) on the synthetic graphs For each value of Hedge (G), we take the average test accuracy and standard deviation of
See Appendix A.I for hyperparameter searching range and Appendix B for more detailed description of the data generation process
4

---

Under review as a conference paper at ICLR 2022
over 10 generated graphs. For each generated graph, also calculate its Hode (9), etass (G)
and M (9). Model performance with respect to different homophily values are shown in Figure
agg
Test Accuracy
1.0
sync-cora sggen
syne-chameleon__ _gtm
0.8
sync-cora sgcl
sync mencddhameconn. sggl
sync-citeseer, ggn
syne-squirel
0.6
sync-citeseer, sge1
sync-quurrel, sgcl
0.4
sync-pubmed
sync-fim, gen.
sync pubmed, sgc1
sync fim, spcl
0.2
0.0 0.2 0.6 0.8 Edge Homophily
0.0 0.4 0.8 Node Homophiy
0.0 0.2 0.6 0.8 Class Homophily
0.2 0.4 0.6 0.8 1.0 Modified Agg Homophily
(a) (9)
(b) (9)
(c) Ham
(d) (9)
Figure 2: Comparison of baseline performance under different homophily metrics.
Comparison of Homophily Metries The performance of SGC-1 and GCN are expected to be monotonically increasing with a proper and informative homophily metric. However, Figure (() (b) show that the performance curves under (9), Hode (9) and Hetass (9) are U-shaped while Figure d) reveals nearly monotonic curve with little perturbation around 1. This indicates that H (g) 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
4 ADAPTIVE CHANNEL MIXING (ACM) FRAMEWORK
High-frequent graph sig- nal, which can be extracted by high-pass filter, is em- pirically shown to be useful for addressing heterophily problem (Luan et al. [2020b]
Closs
Claes
AXXTA
(1
XX
(1
A)
350
50
50
50
50
20
25
26
25
60
58
60
58
00
27
333
27
-33
[1.0]
24
00
277
[1.0]
25
00
33
10
300
[1.0.0]
-27
Chien et al. 1 Bo et al. 2021). In this section, based on the similarity matrix pro- posed in equation [3] we will figure out how diversifi- cation operation i.e., high- pass (HP) filter, is poten- tially capable to address
1:10.1
.33
[:
(9.1)
weight in intenelles block mode 1,3.
Large
posiiie
Posiiive weights in istr--llas Mocks, Non-negeeie wright. in emoo-elton books.
7:19.11
Figure Example of how diversification operation addresses harmful
heterophily
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 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 2 to address heterophily challenge.
4.1 How DIVERSIFICATION OPERATION HELPS WITH HARMFUL HETEROPHILY
We first consider the example shown in Figure From S(Á,X) we can that nodes 1,3 assign relatively large positive weights to nodes in class after aggregation, which will make node 1,3 hard 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 / - Á (Ekambaram, 2014) to extract the information of neighborhood differences and address harmful heterophily. As S(T A, X) in Figure shows, nodes 1,3 will assign negative weights to nodes
A similar J-shaped curve for Hedge (9) is found in (hu et al. 2020b), though using different data generation processes. The authors do not mention the insufficiency of edge homophily.
5

---

Under review as a conference paper at ICLR 2022
4.5,6,7 after diversification operation, i.e., nodes 1,3 treat nodes 4,5,6,7 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 this observation, first define diversification distinguishability of a node and graph diversification distinguishability value follows measure the proportion of nodes that diversification operation potentially helpful for.
Definition 2. Diversification Distinguishability (DD) based on S(I - A,X).
Given SIT - Å, X), node is diversification distinguishable the following conditions satisfied at the same time,
1. Mcan, ((S(T- EEEEEVREE Zu Zu;} 2 0;
2. Mean, (I5(I- EVA Zu & Zuni) 50
Then, graph diversification distinguishability value is defined as
1 V
DD A.
Lolu E.VEEVA V.V is diversification distinguishable)
(10)
x We can that DD A.x (G) E [0, Based 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, sup-
pose X = 2, A Anw- Then for any I - A all nodes are diversification distinguishable and
DD A.z ADA (9) 1.
Theorem I theoretically demonstrates the importance of diversification operation on handling het- erophily. 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 æ defined on G, a 2-channel linear (analysis) filterbank (Ekam baram 2014 includes pair of low-pass (LP) and high-pass (HP) filters Hyp, HEP, where Hip and HiP retain the low-frequency and high-frequency content of æ. respectively.
Most existing GNNs under uni-channel filtering architecture (Kipf & Welling 2016 Velickovic et al. 2017 Hamilton et al. 2017) with either HLP or НEP channel that only partially preserves the input information. Unlike the uni-channel architecture, filterbanks with HLP + НHP will not lose any information of the input signal, i.e., perfect reconstruction property (Ekambaram 2014).
Generally, the Laplacian matrices (Lsym- Liw, Lsym= L.w) can be regarded as HP filters (Ekambaram 2014) and affinity matrices (Asym. Arw. Asym. Arw) can be treated LP filters (Macharal 2019
Hamilton 2020). Moreover, it can be interpreted that MLPs uses the identity filterbank with I1
and HHP that satisfy HLP HaP +
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.
From Figure 3
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 Hip and Hup to represent general LP and HP filters. The ACM framework includes 3 steps as
In graph signal processing, an additional synthesis filter (Fkambaram 2014 is required to form the 2-channel filterbank. But synthesis filter not needed in framework, do introduce in our paper.

---

Under review as a conference paper at ICLR 2022
follows,
Step 1. Feature Extraction for Each Channel:
Option 1: Hi ReLU (H Hy
ReLU (Hup HI = ReLU (1H Option 2: Hi_ HiPReLU (H H RuLU (H'- H I ReLU (H'
Ho- = X E N W WH W E =
Step 2. Row-wise Feature-based Weight Learning
aL - ( (uLW)): راy =o (1h)h at =o (H!W)).
W ( W W Rix1
[at, a = Softmax (([ā),, a/n, at] (T)) E xx3 T E RR temperature, Whi E Rax3,
Step Node-wise Adaptive Channel Mixing: = diag(o)))
H =
+ diag(a))
+
(11) The framework with option in step 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 Hi 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 Mix to learn which channel is important or not for each node, leading to the row-wise weight vectors a', d'y,a) a² E N 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' in step 3. See Appendix Forr the performance comparison with basline models on synthetic datasets.
H
Complexity Number of Icarnable parameters in layer 1 of ACM-GCN and ACMII-GCN is 3F- + 1) + 9, while it is Fi-1 in GCN. The computation of step 1-3 takes N Fi + 6F)-1) + 2Fi(nnz HLP) + (Hp)) + 18N flops, while GCN layer takes 2N F Fi + (nnz (HL)) flops, where nnz(-) is the number of non-zero elements. An ablation study and a detailed comparison on running time is conducted in section
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 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 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-HHija al. 2019) acknowledge the difficulty of learning on graphs with weak homophily and propose Mix 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 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. HGGCN (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.] 2020aa models label correlations by the compatibility matrix, which is beneficial for heterophily settings, and propagates 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. (021) learns edge- level aggregation weights 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) al. 202T) 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 for more comprehensive comparison between ACM-GNNs, ACMII-GNNs and FAGCN, GPRGNN.)
7

---

Under review as a conference paper at ICLR 2022
6 EXPERIMENTS ON
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, compare with the state-of-the-arts (SOTA) models in subsection 6.2 The hyperparameter searching range and computing resources for all experiments attached in Appendix A
6.1 ABLATION STUDY & EFFICIENCY
Ablitioon Study on Difffrent Components in ACM-SCIC and (S)
Baseline
Model Components
Comeell
Wisconsin
Texas
Film
Chameleon
Squiree
Cora
CieeSeer
PabMed
LP Idearity Mixing|
Ace +
+
38
25.26
1
181
85.5
83.28
581
91.88
90.88
2446
36,76
101
47.27
137
86
108
80.98
87,21
10:41
ACM-SOC-1
93.93
1
95.35
184
91
2.54
38.38
1
63
2.07
46.70
0.75
96
1.28
50.37
0.99
87.8
0.58
9.44
88.2 4.30
93.5
295
92.98
+
2.44
17.19
037
62
+
184
44.04
093
85
1.35
80.75
88.11
0.21
11:00
82.46 + 3.11
75.5
292
282
88.9
0.32
86.62
99.19
1,35
51.96
ACM-GCN w/
94.26 2:23
96.13
2.2
94.1
2.95
41.51
0.99
67
+ 2.14
53.97
+ 1.39
53.95
+
0.9
81.72
1.22
90.88
0.55
4.44
91.64 +
95.37
+ 3.31
95.25
2.37
40.47
1.49 68.93
+ 200
54.78
1:27
89.13
+
1.77
81.96
2
91.01
0.7
3.11
266
82:46 1:
3.03
91.00
1.75
90.33
38.39
0.75
67.59
2.14
53.67
1.71
89.13
51.75
89.67
7.44
94.26
ACMILGION
91.48
1.43
95.25
2.09
92.27
2.91
40.27
1.07
66.52
2.65
52.9
1.64
53.83
1.16
$1.54
0.95
90.5
0.47
6.67
95.9
1.83
96.62
2.44 95.25
3.15 41.84
1.15 68.38
1 1.36 54.53
1 2.09
89
0.72
$1.79
0.95
90.74
1 0.5
2.78
Compurison of Average Kuuning Time Per Epochims)
2.5
4.01
4.57
4.24
4.55
4.76
5.09
5.39
4.09
4.75
ACM SGC- SOC- m
3.88
4.01
4,34
4.43
4.06
4.5
4,38
3.82
4.16
3.69
3.18
3,7
3.53
4,85
3.92
3.87
4.24
3,96
5,43
5.9
3,74
3.59
4.56
4.18
8.06
7.80
7.83
7.38
ACM-GON wf
5:73
5.91
5.93
6.86
6.35
7.15
7.34
6.66
6.8
5.16
5.25
5.2
5.93
3.64
8.02
5.73
5.65
6 16
7.89
6.62
7.35
7.39
7.62
7.33
9.69
7.49
7.58
7.97
ACMILGON
5.27
5,46
7.87
5.48
5.65
7.59
8.28
8.06
8:85
10
8.27
8.5
$.68
Table Ablation study on 9 real-world datasets Pei et al. 2020). Cell with v means the component is applied to the baseline model. The best test results are highlighted.
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 SGC-1 (Wu et al. 2019) 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%/2054 random splits for train/validationntesst used in (Chien 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 in equation 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 see that the running time is approximately doubled under ACM and ACMII framework than the original model.
6.2 COMPARISON WITH STATE-OF-THE- MODELS
Datasets & Experimental Setup In this section, we implement SGC (w et al. 2019) with 1 hop and 2 hops (SGC-L, SGC-2), GCNII (Chen et al. 2020). GCNII" (Chen et al.) (020). GCN (Kipf & Welling 2016) and snowball networks with 2 and 3 layers (snowball-2, snowball-3) and apply them
'We only test ACM-SGC-1 because SGC-1 does not contrain any non-linearity and ACM-SGC-1 and ACMII-SGCII the same.
8

---

Under review as a conference paper at ICLR 2022
Cornell (SOTA=APPNP)
Wisconsin (SOTA=MLP-2)
Texas (SOTA=GPRGNN)
100
Test Accuracy (%)
Test Accuracy (%)
SOTA
baseline GNNs
Accuracy
90
90
ACM-baseline
ACMIl-baseline
70
80
60
GCN
snowball-2 snowball-3
GCN
snowball-2 snowball-3
GCN
snowball-2 snowball-3
(a) Hag (9) 0.8032, f 4.1
(b) H (9) 0.7768. f3.13 %
(c) H (g) 0.694, 12.82
Chameleon (SOTA=GAT+JK)
Film (SOTA=GPRGNN)
Squirrel (SOTA=GCN+JK)
60
Test Accuracy (%)
70-
Test Accuracy (%)
40
Test Accuracy
65
50
35
60
40
55
snowball-2 snowball-3
GCN snowball-2 snowball-3
GCN snowball-2 snowball-3
(d) H (9) 0.61, 0.9 %
(c) H (9) 0.6822, 12.54%
(f) H (g) 0.3566, 14.62 %
Figure 4: Comparison of selected baseline GNNs (red), ACM-baseline (green), ACMIl-baseline (blue) with SOTA (magenta) models selected datasets. The black line and the bar indicate the standard deviation. The symbol "1" means the amount of improvement of the best ACM-baseline and ACM-baseline over the SOTA models. See Appendix Hor detailed discussion of the relation between agg and the performance of GNNs.
in ACM or ACMII framework? 7
we use Arw as LP filter and the corresponding HP filter is / A,
and they are deterministic. We compare them with several baseline and SOTA GNN models: MLP
with 2 layers (MLP-2), GAT (Velickovic et al., (017). APPNP (Klicpera et al. 2018). GPRGNN
CChin al. 202T), H₂GCN (Zhu et al. 2020b), MixHop (Abu-El-Haija al. 2019).
GCN+JK
(Kipf & Welling 2016]]
Xu et al., 2018 Lim et al., (021), GAT+JK (Velickovic et al. 2017 Xu
ct al. 2018 Lim et al.
2021). FAGCN Bo al. (021) 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 al.
2020), further test the above models in (Roozeberczzki & Sarkar 2020). On each dataset used (Rozemberczki et al.) [2021] [ei et al.
benchmark dataset, Deezer-Europe, that is proposed
2020), test the models 10 times following the same early stopping strategy, the splitting method [ and Adam (Kingma & Ba 2014) optimizer as used in GPRGNN (Chien et al.
random data
202T). For Deezer-Europe, we test the above models 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 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 most commonly used benchmark heterophily datasets (See table 4 in Appendix A.3 4.33foo for the full results and comparison). We can see that after being applied in ACM or ACMII framework, the performance of the baseline models are significantly boosted 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 ACMII framework can help GNNs to generalize better node classification tasks on heterophilous graphs.
7 GGNTI and GCNIC are hard implemented under ACMII framework. See Appendix A.6 explanation. $See table Ø in Appendix for the performance comparison with several SOTA models on the fixed 48%/329//00% splits provided by (Pei al. 2020

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sami Abu-EI-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 vrXXiv:149.044 2014.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 106.:110.. 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, fts/1611.08099) 2016. URL http://
arxiv.org/an abs 11111000011
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. PMIR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. https://openreeiew. 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 graphs with fast localized spectral filtering. arXiv, abs/1606.09335, 2016. |
//arxiv. wwwrxiv.orc//.... abs/ 660./66666...00 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 1903::1100002222. 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. 66666666444 Ieee, 2013.
William Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-153 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive rewreseeetttcttttiiiiionoo learnig large graphs. arXiv, Ais/17066002166 2017. httpp///w..p////aaa.ooooo///////
02216
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma. Hongzhi Chen, and Ming-Chann 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.69880 2014.
Thomas N. Kipf and Max Welling. aennissupperissedddcasssctttttot with graph convolutional networks. arXiv, abs/1
2016. URL/htapp//arriivoor///aa 0297
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 181.099/1 2018.
10

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional 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(1 (((1)))227-22222 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 non- homophilous graphs. arXiv preprint arXiv:2104 01404, 2444440044044 2021.
Vijay Lingam, Rahul Ragesh, Arun Iyer, and Sundararajan Sellamanickam. Simple truncated svd based model for node classification heterophilic graphs. arXiv preprint 106. 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 10X1001711.05101, 2017.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. arXiv preprint arXiv:1906.02177 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.0882 2020a.
Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao- Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint ar 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 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-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 2020.
Benedek Rozemberezki and Rik Sarkar. Characteristic Functions Graphs: Birds of Feather, from Statistical Descriptors to Parametric Models. In Proceedings of the 29th ACM International Conference 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) 20(1):61-80, 2008
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv, abs/ 111117100.0.,00 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 Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 5453-5462, 5462. PMLR, 10-15 Jul 2018. URL /
ngs. pr..ssss///c.. v80 8c. htm

---

Under review as a conference paper at ICLR 2022
Yujum 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.
12

---

Under review as a conference paper at ICLR 2022
A HYPERPARAMETERS & DETAILS OF THE EXPERIMENTS
A.1
HYPERPARAMETER SEARCHING RANGE FOR SYNTHETIC EXPERIMENTS
Hyperparameter Searching Range for Synthetic Experiments
ModelstHypepuurmeeetrss
Ir
weight decay
dropout
hidden
MIP-1
0.05
(5e-5, le-4, 5e-4, le-3, 5e-3
SGC-1
0.05
(5e-5, le-4, 5e-4, Te-3, 5
ACM-SGC-1
0.05
(5e-5, Ie-4, 5e-4, le-3, 5e-3]
[0.1, 0.5
MLP-2
0.05
(5e-5, le-4, 5e-4, (e-3)
(0.1, (0.1,03,,055007,000
64
GCN
0.05
(5e-5, lc-4, 5e-4, le-3, 5e-3
{ [0.1, 0.3, 0.5, 0.7, 0.9
64
ACM-GCN
0.05
(5e-5, le-4, 5e-4, le-3, 5e-3]
0.11, 0.3, 0.5, 0.7, 0.9]
64
Table 2: Hyperparameter Searching Range for Synthetic Experiments
A.2 HYPERPARAMETER SEARCHING RANGE FOR ABLATION STUDY
Hyperpurameter Scarching Range for Ablation Study
MobelsHypeerrrnnteess
weight_decay
dropout
hidden
SGC-LPP+H
[0.01,
[0,
1e-4, 1e-3, 1e:2]
SGC-LP+Idenity
(0.01. 0.05, 0.1)
[0, Se-6, le-5, (e-4, Se-3,
ACM-SGC-no adaptive mixing
(0.01, 0.05, 0.1]
[0, Se-6, le-5, 3e-5, Ie-4, Se-4,
Se-3,
[0. 0.1. 0.2, 0.3, 0.4, 0.5, 0.6, 0.7.0.8.0.9)
GCN-I.P+HP
[0.01, 0.1
[0,
1e-5, 5e-5, Se-4,
1e- 1e-2]
0.7.0.80.91
GCN-LP++de -eN-LLPIdenttty
(0.01. 0.05, 0.1)
[0, Se-6, Ie-5, Se-5, Ic-4,
Io-3,
1e-2)
{0, 0.1, 0.2. 0.3. 0.4. 0.5, 0.6. 0.7.0.8..99
64
ACM- GCN- no adaptive mixing
(0.01, 0.05, 0.1]
[0, 5e-6, le-5, 5e-5, 1e-4, 5e-4, 1e-3, Se-3, 1e-2]
[0, 0.1, 0.2, 0.3. 0.4, 0.5, 0.6, 0.7.0.80.9)
Table 3: 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 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 out 10 datasets. Especially, ACMII-GCN performs the best terms of average rank (3.40) across all datasets. Overall, It suggests that ACM or ACMII framework can significantly increase the performance GNNs on node classification tasks on heterophilous graphs.
A.4 HYPERPARAMETER SEARCHING RANGE FOR GNNs ON REAL-WORLD DATASETS
See 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 and for ACM-GNNs and ACMII-GNNs in 7
Thhe splits for all these experiments are random 60%/20%/20% splits for train/valid/test.
The open source code we use is from https::/ http:///ttuub..cm//aaaaaaaau//// wtt.:////anaaaa111///a/m 2F2/22016//PRN////E0 MCNN/bbbbb/ E (ataacccaa33311233344444444434 for the performance comparison with several SOTA models on the fixed 489/32%%/00% splits provided by (Pei
wttpddfaaa////e//ee///a/ee htt.:////////e/tttt.......eeeee 1y See table Appendix
2020
13

---

Under review as a conference paper at ICLR 2022
Comell
Wisconsin
Texas
Film
Chameleon
Squirel
Burupe
CiteSoer
Anades
183
251
183
7,600
2,277
5,201
28,281
2,708
3.327
19,717
Rodges
295
4599
309
33,544
36,101
217,073
92,752
5,429
4,732
44,338
Bleatures
1,701
1,701
1,703
931
2,325
2,089
31,241
1,433
3,203
500
helesses
5
5
5
5
5
2
7
6
3
Helpe
0.5669
0.4480
0.4106
0,5750
0.2795
0.3416
0,5251
0.8100
0/7362
0.8024
Hoste
0.3855
0.1498
0.0968
0.2210
0,2470
0.2156
0.5299
0.8252
0,7175
0,7924
Haya
0,0168
0.0911
0,0013
0,0110
0,0620
0.0254
0,0304
0,7657
0.6270
0.664]
Data Splits
60% /309//00 60%
/200//20/
/09/200//205 60%/209//0 60%/3099/20 60%/2009/209
50%/2598/25
60%/200/200 60%/2206/20
60%//205/205
H (92)
0.8032
0.7768
0.094
0.6822
0.61
0,3566
0,5790
0.9904
0,9826
0.9482
Test Accuncy (8) State-of-the-i art Models, Baseline GNN Models and ACM-GNN models
Rank
MLP-2*
91.30
0.70
93.87
3.33
92.26
0.71
38.58
0.25
46.72
0:46
31.28
0.27
66.55
0.72
76.44
0.30
76.25
0.28
86.43
0.13
18.60
16.00
71.01
42.72
APENP*
91.80
0.63
92.00
3.59
91.18
0.70
38.86
0.24
51.91
0.56
34.77
0.34
67:21
0.56
79.11
0.38
68.59
0.30
85.02
0.09
18.00
GPRGINN
91.36
0.70
93.75
2.57
92.92
0.61
39.30
0:27
07.48
0.40
49.93
0.53
66.90
+ 0.50
79.51pm
0.36
67.63
0.38
85.07
0.09
14,40
H2GCN
86.25
81.5
1.77
3.53
38.85
52.30
30.39
1.22
67.22
87.52
79.97
87.78
17.00
MixHop
77.25
7.80
76.39
7.66
33.13
24.55
66:80
49.52
13.35
87.04
4.10
GCN+J
66.56 -: 13.82
62.50
= 15:75
90.66
1.91
32.72
2.62
64.08
2.85
53.40
1.00
6099
0.14
86
1.51
75377
1.55
90.99
0.68
18.80
GAT+JK
74.43 + 10.24
69.50
3.12
75.41
7.18
35.41
0.97
68.14
1.18
52.28
3.61
59.66
0.92
89.52
0.43
74.49
8 2.76
89.15
037
16.70
RAGEN
8835
N2.37
89.08
14.10
GraphSAGE
71.41
64.85
79.03
30.37
02.15
41.26
OOM
78.24
86.85
Geam-GEN
6081
64 12
67.57
31.63
60.9
38.14
NA
85.27
77.99
90:05
22.67
SGC-1
10.98
8.39
70.38
2,85
83.28
5.43
25.
1,18
64.86
1881
47.62
1.27
59.73
0.12
85.12
1.64
79.06
0.75
85.5 + 0.76
20.10
SGC-2
72.62
74.75
28.81
62.67
+
85.48
80.35
85.36
20.70
GCND
$9.18
$3.25
40.82
38.81
GUNI
90.49
4
89.12
3.06
38.52
3.02
41.54
0.99
028 + 287
58.31
1.3
06
0.56
8893
1.37
81.33
1.78
8938
0.52
12.30
GCN
$2.46
3.11
75.5
2.92
83.11
3.2
35.51
0.99
64.18
2.62
44.76
1.39
62.23
0.53
87.78
4 0.96
81.29
1.23
88.9 + 0.32
16.30
Soowhall-2
82.62
74.88
35.07
64.9
81.53
0.49
Soowball-3
82995 +:
5.01 69.5
36.00
65.49
48.25
COM
8099
88.3
ACM-S0C-1
03.77
30.33
63.68
46.4
66
66
80.6
87.75
ACM SGC-2
93.77
2.17
94.00
2.61
93
2.54
40.13
1,21
60:18
L.55
40.91
1.39
66.53
0.57
87.64
0.99
80.93
1.16
88.79
13.40
ACM-GCNII
92.62
3.13
94.63
2.96
92 46
1.97
41.37
1.37
53.73
2.52
409
: 1.58
66
0.56
89.1
161
82:28
1 1.12
90.12 1.4
10:40
ACM-GONT*
93.44
2.74
04.37
2.81
93.78
7.79
41.27
1.24
61,66
7.29
53 - 1.5
66.6
4 0.57
89000
2
81
1.25
98.18
10.10
41.62
ACM-Smowhall-2
95.08
3.11
96.38
2.59
95.74
2:22
41.4
1.23
63.51
55.97
2.03
COM
88
1.49
81.58
90.11
0.52
4,44
ACM-Snowhall-3
94.26
2.57
96.62
1.86
94.75
2.41
41.27
= 0.8
68.4
2.05
55.73
2.39
00M
W9.59
2 1.58
81
0.97
01.44
0.59
4.44
ACMIL-GEN
95.9 = 1,83
96.62
2.44
08
2.07
41.84
1.15
68.38
+: 1.36
54.53
2.09
67.15 0.41
89000
0.72
81.79
0.95
90.74
3:40
ACMII-Snowalll-
99.25
1.53
96.63
2.24
95.25
1,55
41.1
+ 0.75
07.83
2.63
53.48
4 0.6
0OM
8899
104
82007
+ 1.04
90.56
+ 0.29
4.78
ACMII Snowball 3 93.61
2.79
97.00
2.63
94.75
3,09
67.33
2.83
52.31
1.57
OOM
89.36
1.26
81.56
1.15
91.31
4 0.6
Table 4: Experimental results: average test accuracy + standard deviation on 10 real-world benchmark datasets. The best results are highlighted. Results **" are reported from Chien et al. (202T); ) [im et al.. (2021) and results "i" are from Pei et al. (022)). NA means the reported results are not available and OOM means out of memory.
14

---

Under review as a conference paper at ICLR 2022
weight decay
dropeut
hilken
lambdd
alpho
hedd
Tayers
JK type
122GNN
0.01
0.001
(0,0.5)
18. 16, 52, 64)
11.2)
Mixllop
0.01
0.001
0.5
18, 16, 52)
12.3]
10.1. 0.01,
(4. 16, 641
[max,
0.001)
GAT+JK
10.1, 0.01.
0.001
0.5
14.8, 12, 12.
[24.8)
[max, cull
0.0013
OCNIL GCNII"
0.01
(0, Se 6, le-5. 5e le-
0.5
[0.5, 1.5)
(0.10.22003.000000 4,0.5)
[4, 8, 32)
4, 50-4, 1e:3) toc Dester- 5e-6, Le-
for Deeter-
Europe Se-4,
Europe
(4. 32, 64) for
Se-3, 1e:2] for others
others
Roselines:
(SEC-- SGC-
10.022,
(0, So-6, lo-5, Sod,, le-
[0, O.1.
2. GCN, Snowhall-2.
0.01.
4. Se-4, 1e:3) for Denoce-
0.2. 0.3.
Snoufsill-3,
FAGCN]:
Eurape
ACM-[SGC-1,
90-5, lesd, 5o-4, 16-3,
2. GCN, Snowhal-22.
Eurupe
Se-3, [e-2] for others
0.8, 0.9)
S:oufuil-3]: ACMII
and (0.1.
SCC-2,
0.11
Snowboll-2, Snowball-5)
others
GradSSGG
10.01,0.5. 0.1)
[0, 6, de
4, 5o-4, 1e-3) for Dester-
0.2, 0.3,
Europe and 64
Burope and (0, Se-6, le-
0.4, 0.S.
for others
5. 5, le-4, Se-4, 1e:3,
Se-3, 16-2] for others
0.9)
ACM- COM-IGCNII,CCM GCNIT)
56-6, 1e-5, 5e-5, le-
1.0.
(1.334)
5o-4, 1o-3) Desses-
0.2, 0.3.
Eurupe and (0, Se-6, le-
0.4, 0.5.
5e-5. le-4, Se-4, Ie-3,
0.6 0.7.
1e-2] others
0.9)
Table 5: Hyperparameter Searching Range for Real-world Datasets
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--CN and ACM(ID-snowbal is straightforward, but SGC- SGC-2, GCNII and GCNII* are not able be applied under ACM(II) framework and we will make an explanation as follows.
SGC-1 I and SGC-2: SGC does not contain nonlinearity, so the option and option 2 in step of equation [1 is the same for ACM-SGC and ACMII-SGC. Thus, only implement ACM-SGC.
GCNII and GCNII*:
GCNII: ((+11) = ((1- ÁH(O) + a0H (11 (1-))) + (w))
GCNII H (++1) = (1 (1-aa) ÁH ((1 (1- + & w + +o (0) (11 (1-33) + Be w(w)
From the above architecture of GCNII and GCNII" we cam see that, without major modifi- cation, GCNII and GCNII* are hard to be put into ACMII framework. In ACMII framework, before apply Á, we first implement nonlinear feature extractor a (H'W(()) But in GCNII and GCNII* before multiplying W* Wf, W5) to extract features, we need to add another term including (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 did not implement GCNII and GCNII* in ACMII framework.
The open source code 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).
15

---

Under review as a conference paper at ICLR 2022
Hoperparnnetes for Buciic
Datara
despot
Alayer
Lit beak
lambia
siptaj)
reralo
1,08-22
2-5mma31
SOC-2
0.05
72.62
GCN
8.1
5.08-03
0.5
62.46
1.01
3.61ma3) Tio
Suneball-2
0.01
5008-00 23
0.4
02.02
2.34
4.34ma31 575
0.01
5008-23
6.56raa1
GCNII
00
0.5
0.5
OCNE
0.01
1008-05
0.5
0.5
0.5
00.49
4.45
15 15,35
RAGEN
0.01
100E.04
0.7
83.03
3.6
Jus/3 pa58s
0.01
0.5
10.57Has221005
R3GCN
0.00
86.23
123
GCN-JK
811
0101
0.5
05.56
13.02
3.550vell 20%
GATUK
111
0101
0.5
74.43
10.24
10.725as2.475.
SDC-1
0105
5000-01
70.38
3.87me3) 57% 2. 2.34moli ETc
SDC-
0.1
1008-03
74.76
7.89
31
1081--5
6.7
75.5
(Tinsl) The
Soowhall-77
100
5000004
69.5
ffinnl 12)
GUNI
1601
1000000
12.
03
31.25
2.89
Waccoela
OCNEB
855
39.12
Michop
1101
0101
125
77.25
10.201 mu22000
JIGGEN
1001
115
82.5
1:71
4:124me) 150a
0.5
GAT JK
0201
685
10 10.70Drs/2 25,
APPND
0.05
0201
0.5
64
3
92
1.59
10 (0.30hnsi2.0 2014s
GPRONN
0.05
0.01
0.5
256
93.75
2.37
11 2855mm22.415
0,05
100E-00
83.21
2.55maah)
SOC-2
0.01
100E-03
9
91.31
3,3
2.6lma 55e
GCN
L,KE-02
6.9
83.11
3.5hmmah 7hy
Swowball-2
0.9
3.96ma00
1000-02
Toxas
GENI
0.01
1000-04
1001--44
15%
855
055
18
04
33.00
4.98
Michop
0101
0.5
76.30
1iiimuu 320c 4 4.Vrauutust
JEGGEN
B101
55.00
1.57
GUNNiK
21
6101
85
50.60
2émul 118be
SDC-1
B.01
5/00-066
75.76
1:38
Himech The
s0c-1
0.0
1/00--66
75.81
Sanwbell-2
0.1
5.008-44
35.07
0.65
5.5hhall 16
Swoebell33
041
5,00 04
0.2
35
1.36
7.5hmaa) 50s 15,55n33322
0.01
1008-24 24
0.5
OCNI
41.54
FAGEN
0.01
5000
0.6
31.99
1.31
45 107,
Miskop
000
0101
0.5
33.13
2.40
17 13 5.66
GCN-JK
0.1
0.01
32.72
5.94enaa) 20:22mu444187
GATUK
6.011
0001
0.5
2
35.41
0.91
64.96
3.40ra Me
SO0-
51
0.00600
GCN
1000-00
69
61.18
7.63
Drincc) 19
Sauahali-2
1:000-01
1000--0
69
61:99
Stesel D0s
Chundten
DCNE
GENII
0.1
5.00--06
1000-004
15%
0.5
1.5
0.5
00.35
62.6
1.87
10.00mu7. 171
PAGEN
45-47
HEGGN
n01
0101
52.3
4 41t9imull.s $7x
GUNelk
65
32
(31
61A5
2.85
5-21 limel IeSs.
GAT
0101
0.5
05.14
1.19
13:77mm/1-7M
SDC-1
47.62
1.21
4.88mal) 40g
SOC
84
0.9
41.25
1.4
GCN
0.01
5X08-55
0.7
44.76
5:4ira22
Sunsball-3
0.005000
0.5
48.25
0.94
1400mu02.35
Squiral
GCNI
000
0.01
5.0E-34
100E 04
0.5
0.5
15
35.81
1.9
13,35maa2.100
EXGCN
16au=5.795i
Mishep
0.01
0.01
0.5
24.35
2.6
17 17,424eu22 2,563
HXGCN
0.01
0101
5
16
30.30
1.23
5:315ma)) B8D,
GATwIK
01011
0101
0.5
53.36
(N777u0 8788
SOC-1
511
5,00-066
85:12
1.64
OCN
011
5.00--44
0.2
87.78
Suonhall-3
511
5000-00
0.1
35.61
1.11
6i0ici Dis
0.05
1008-01
066
39:33
OCNB
0.01
0.5
38.91
BAGUN
800
1000-00
35.35
1.36
kimo/1 11
Michop
0.01
01011
0.5
4.355mal)
GCN-K
6.011
0101
0.5
$6.00
1.51
6655enal) 34to
0.001
0101
0.5
32
89.52
0.42
12 12.9hm222 1006
SUC-1
0101
5/00-004
0.9
90.75
1.15
S.3 4tb
GCN
100b-0
0.9
$1.39
1.23
4. L.imaall Doo
Soosball-2
1008-2
0.8
$1.53
7.54mra))
ClieSexr
GONI
DCNE
n01
0.01
1018-01
1008-00
0.5
0.5
16
16
0.5
31.87
91.58
1.78
1.3
Michep
0.01
0101
0.5
49.53
13.35
JEGEN
0101
70.07
0.69
7Dimee' DoM..
GUNe1K
0101
0.5
71.77
SOC-1 1
0.05
500E-26
0.3
64
$7.75
0.85
6.blrn22 6ls
SOC-5
0.05
S,00-00
0.1
$8.25
8. 18
Seawsall-22
5150--04
59.54
1140
S.biraai 119
Swowballd33
5J00-06
18.6
(182
K.4mma)) 75
PalMlel
GUNI
1008-06
0.5
0.5
103
FAGEN
5.00:00
99.95
(154
Mishop
01001
0.5
16
97334
4.30
17 17.000aur3.3 537x
0.01
$1.78
GCN-KK
12.00
UK
9.1
0101
0.5
3
99.15
0.81
20-40bau44.125
DNGLN
1101
65.30
A1.22mpt 15:3
Decee-Farape
Se6.le5
0.5
0.5
OCNTE
0.11
1o-41e3
0.5
0.5
0.5
66.42
0.56
134.5 19
Table 6: Optimal Hyperparameters for baseline models
16

---

Under review as a conference paper at ICLR 2022
Hyperarammters for ACM-GNNG and ACMILGGNNI
Dulasets
weight_decay
dropost
hiddea
Flayers
Gat heads
IK Type
lambaa
resulls
sid
uvdrage spochs timelererage total time
ACM SGC-1
0U]
5,00E-03
0.5
64
93.77
1.91
5.53mm/2.31a 1.
ACM SGC
001
5.00E-00 03
0.6
64
91.77
2.17
4.73mmx1.87)
ACM GCN
0.5
1000 02
0.2
64
2
94.75
3.8
8.25mm11 1.69s
ACMIL-GCN
0.1
100--22
0.5
64
95.25
2.70
8.43mm21.71 1.71
Cariell
ACM GCNIP
ACM-GGNIL
001
0U1
5 500E-00
1 10NE-00
1.5
0,5
64
64
0..5
01.5
0.4
0.1
92.62
93.84
2.74
3.13
6.81mm/1 1.45%
6.76mm/1 1.3%
ACH-Snmmball-2
00s
00F-00
0.2
64
95.08
3.11
9. 1155m 1.86
ACM--nmmballl1
011
000--02
0.4
64
94.26
2.57
13 1.200mo22 66x
ACMIl- S
aus
1 1006-02
0.6
64
95.25
1.55
8, 8.23mm/1.73
ACMII SMlll-Soowalll-
0.5
I 000-02
0.7
64
91.61
2.79
[1 11.70me22. 2.5%
ACM-SGC-1
aus
5006-00
0.7
64
93.25
2.92
5 5.56mx) 34
ACM-SGC-2
0.1
500E-00
0.2
64
2.61
4.60mm0LL9S
ACM-GCN
0
006--0
0
64
95-75
2.03
8. I 1ik..
ACMIL-ICN
0.1
1 008-00
0.2
64
96.62
2.44
8: 3.20mm11 68c
Wisconsin
ACM OCNT
ACM GCNI
001
0.1
5 000 03
1 000-00 00
0.5
0.5
64
64
1.5
0,4
0.1
94.37
94.63
2.95
2.81
7.1 lime) A8s
9.31m 19c
ACM Snowhall-2
0.1
5 0000-0
0.1
64
96.36
2.59
8 8.63me1 74c
ACM Snowball
0.05
1 10ME 02
0,3
64
96.62
1.86
12, 12,75mm 5.5
ACMI Saowball
0.1
1 1O0E 02
0.1
64
96.63
2.24
8. Lime 1.655
ACMIl Snowhall
0.1
5 OME
03
0.1
64
97
2.63
12.38ms/2.51a
ACM SGC
0.01
5 OME 03
0,5
64
93.61
1.55
5. 5.43ms22 18s
ACM SGC 2
0.05
5 OME 05
0.4
64
93.65
2.54
4 4.59ms5 1.11
ACM GCN
0.05
I MIE 02
0.6
64
2
94.92
2.88
8.30me') 70k
ACMIL-GCN
0.1
S OME-02
0.4
64
95.08
2.54
8.45mm/1 727
Texss
ACM CCNH
ACM-GCNI
0.11
0.01
1 LMI OF
1 AME OF
0.5
0.5
64
03
0.5
0.4
0.4
92.45
93.28
2.79
1.97
7. 7.00mm51 A55
6,47mm/) 3,3
ACM--Snmballl22
0.5
1 088-02
0.1
95.74
2.22
8. 8.35mm/3 7
0.1
S OOB--0
11.
94.75
2.41
12 12.5mm/22.4 6.634
Saowball
Q.1
1 10B-02
0.4
95.25
1.55
9.74mm/ M7s
XCMiI-Snowaall-
0.0
000-00
0,6
94.75
3.09
II 11.0mm22.44 .2x
ACM-SGC-1
Qus
S SIME-05
U.7
64
39.35
1.25
5. 5.21mm/2.33 2.35
ACM 2GC-
0.1
S 05
U,7
64
40.13
1.21
12.4 N7s
ACM-GGN
0
S 009-04
0.5
64
41.62
1.15
10 70mm2m/ 666
ACMIL-ICN
Q1
008-24
0.5
64
41.24
1.16
10. 51 51md2 444.
Film
ACM-OCNII
ACM-GCNII
001
001
DO0E-00
1008-04
0.5
0.5
64
41.37
41.27
1.24
1.37
13 33.6 74.
14 555mem 0
ACM--Smmballl2
011
5 000--04
0
41.4
1.23
10 10:30m/33 08%
ACM-Smmwelll-3
0.0
00F-00
0
41.27
0.8
16.4 ..s
ACMII Snowhall
0.0 03
0.75
10:31me/2
ACMII-Snowhall-
0.05
0000-0
0.2
1.6
16.31mm33.2
ACM-SGC-1
0.1
008-06
0.9
64
63.68
1.62
5.41mel1 21x
ACM-SGC-2
000000
0.9
60.08
1.55
7 3,5mm'
ACM-GCN
001
0066-5
0.8
68.11
1.67
10 00.55mme). 12x
ACMIIGCC
0.5
00F-05
0.7
68.36
1.36
10 10.00mm,, 30x
Chamelesa
ACM OCNH
ACM GCNI
0.01
0.00 06
1.00 03
0.5
0.5
0.1
61.66
2.29
18.3
6 6.68ms1 1.40s
ACM--Smmball-22
9. 2.92mm//16
ACM Snowbllll
100E-04
14 44.49ms/3.
ACMII Sacwball
5.00E
0.5
2.63
9 9,59mms H0s
XCMII-Snoualll3
15 15.00mm23
ACM SGC-1
D:00E-00
6.90mm 16s
ACM SGC
0,00E-00
0.9
1.39
20000mm0000
ACM-GCN
00F-06
1.86
14 44.35mm22.
ACMIL-GUN
DO0E--00
14 14.00mmm3
Squirrel
ACM-DCNII
ACM-GCNI
100EE-0
00F--01
1.58
20: 20.72mm/4.
ACM-Smmmalll-2
500--06
I5 35.32//23
ACM-Sumwalll3
100--04
2.39
26. 1.mue5
5006-06
15
ACMII-Soobilll
5055-05
ACM-S6C-1
0008-006
6.00mm
ACM-SDC-2
ACM-GGN
000--01
1.22
5.mme1 81s
ACMIL-ICN
8 8.00mme' 8%
ACM
1.000000
14.07m/3
34mmmm 92x
Snowball
1000
3
13
ACMII Snowhall
5,0
3.25mm11 90s
ACM
5,50ms4.31
11:35m22.557
ACMIL-GCN
ONIE-05
2
9.55mm211
ACM GCNI
1000
3
15.61mx/3.5
3
15.56mm33.
ACM--Sumnball222
10005-03
0.7
11.14mm/225
001
0.9
0.97
15.91mad5
ACMII- Snowballl
0.8
0000-01
0.7
81.07
1.04
10 10.97m/2..55
ACMII-Sooballl.
0.8
00F-00
0.6
81.56
14 14.05mmm
SONE--06
6.04mu/2200 6.1
ACM-S/C-2
100--05
0.1
0.5
8.60m433
ACM-OCN
100F-04
0.2
0,63
10 11.30mm22
ACMIL-ICN
1000--04
0.2
PobMal
ACM-OCNII
ACM-GUNII
001
001
1000-04
000--04
0.5
0.5
00.12
0.51
0.4
15 (5007/m)
16 Klmme
ACM--Smmbblll22
000--04
0.3
0.92
5.mm22
ACM Snowball 3
0.05
1OO0 03
0.2
91.45
0.59
18 1800mm333
ACMIl Snowball-2
0.1
1.000-000 04
0.3
64
90.55
0.39
I1 11.50mm2.
ACMII Snowhall-3
0.1
5005-04
0.2
91.31
0.6
18 18/51mo
ACM SGC-1
0.05
0.5e
5..ee
0.3
56.67
0.56
146 4
ACM-SGC-2
8.002
Se-4.1ee4
0.3
66.53
0.57
195 mm277.4744
Deczer-Europe
ACMI GCN
ACM-GCN
0.002
0.01
5.00E 08
5005-04
0.5
0.5
67.01
67.15
0.38
0.41
135 253:24mx67.40 A8s
45mo48
ACM GCNIL
0.01
0.5e
0.5
66.39
0.56
30.K2ms440.3
ACM OCNIJ*
0.01
0,000.
0.5
64
0.2
66.8
0.57
30.93ms400 40,
Table 7: Optimal Hyperparameters for ACM-GNNs and ACMII-GNNs
17

---

Under review as a conference paper at ICLR 2022
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 dp-
Given de, we sample hd, intra-class edges and (1 h)d, inter-class edges.
More specifically in our synthetic experiments, for a given h.
we generate node degree d, for nodes in each class from multinomial distribution with
numpy. random. www.muttiiiiiaaa.mmmmmmmmm (800 /h, numpy. ones (400) /400, size-1) [0].
For a sampled de we generate intra-class edges from (does not include self-loop)
numpy. wandom.muml wwlt inomial (ad,, numpy. ones (399) /399, size-1) [0]
www.ommmamniiiiiaammmmmmmm and inter-class edges from numpy- randon. monddo.mmltiiommiae (1-h) der numpy ones (1600) /1600, size=1) [O].
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 turning point, i.e., when (G) (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 based on our proposed similarity matrix which can verify the usefulness H (9). 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 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 10
(9) (g) 10] inter-class edges. The features of nodes in each class are sampled from node
features the corresponding class of the base dataset. Nodes are randomly split into 60%/22%%/20% for train/validation/tess.. We train 1-hop SGC (sgc-/) Wu et al.) (2019) and GCN Kipf & Welling (2016) on synthetic data (see Appendix A.. 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
10
cora_gcn
cara, sgg
ateseer_gee genneer_gcnneooo
dtteeee_5p
Tist Accuracy
pubmed gen
pubmed
06
chameleon, gcn
chameleon
squirrel, gen
squirrel_sp
film gen
sgc
0.2
0.4
0.6
0.8
Edge Homophilyy
Figure 5: Synthetic experiments for edge homophily on regular graphs.
From Figure 5 we
that the turning point is bit less than 0.2. We derive the following proposition for d-regular graph to explain and predict it.
Proposition 1. (See Appendix for proof). Suppose there are classes in the graph & and G is a d-regular graph (each node has d neighhors). Given d, edges for each node ien.raegeeereed, such
18

---

Under review as a conference paper at ICLR 2022
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 À Årw- Then, for nodes v, U1 and u2 where Zu = Zu and Zugi: # Zocs we have
(S(A, - - CC 1)(hd + +1 (1- hid 2 (12)
(h) = E (S(A,
(C -C)- 1)(d+1) +
and the minimum of g(h) is reached
d+1-C
dintra/ / + C
dintra
Cd
O(dimea/
Cdmara + C'
where dimrn = dh, which the expected number of neighbors node that have the same label as the node.
The value of gh) in equation is the expected differences of the similarity values between nodes in the same class and nodes in other classes. 9(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, = 5/27 R 0.1852, which corresponds to the lowest point in the performance curve in Figure 5 In other words, the Hedge (9) where SGC-1 and GCN perform worst where g(h) gets the smallest value, instead of the point with the smallest edge homophily value Hg)g=()) = 0. This reveals the advantage of (9) over Hedge (9) by taking use of the similarity matrix.
have dintr 10, C = 5 and the minimum of g(h) is reached
C DETAILS OF GRADIENT CALCULATION EQUATION
C.1 DERIVATION MATRIX FORM
This derivation similar (Luan al. 2020a).
In output layer, we have
Y softmax (AXW) softmax(Y") = (exp(Y")1c1?)) -1 - exp(('))
[ trace 2 log
where 1c E RCx1, (-)-1 is wiint-wise inverse function and each element of Y is positive. Then
d= -trace (7" trace ((sottmmax(Y"") softmax(Y")))
Note that
d softmax(Y')) ==(exp(("') ((exp(Y') odr') @ exp(Y")
+ (exp(Y") -1 (exp(Y')
= softmax (Y') o (exp(Y") ((xxp((")
softmax (Y') dY
softmax (0 (exx((())) [(exp(Y') " oo'' + dY')
19

---

Under review as a conference paper at ICLR 2022
Then,
dC = trace nt (softmax(Y"))- の softtmx(P")) ( (- (exp(Y")1c1²))
① [(xxp(Y') o dY')ccl]] + dr arrr)))
Irace (7" (-xxp((()))) [lexp(V") o dr +dr")
((22 (exp(("))))) "1) (o1o (exp(Y') dr dy
Irace
(<xx((Y)) の (7 (20(0((M)) 1o1)) dY' - 7²'
trace
(exp((Y)) o (exp(Y (exp(Y))1c))) dr -2'''" ((softmax dY")
trace
Irace
where the 4-th equation holds due to L o (exp(Y))ccZ)) " lclss (exp({")lc1)) Thus,
we have
dC dy softmax(Y")
- -z
For Y' and W, we have
dC
dC dY
dc T dW
dY' = AXdW and dc = trace
dY'
trace
Ax dw
trace
dW
dY
To get JW we have,
dC dW = x AT dL
= x AT 2)
(13)
dY'
C.2 COMPONENT- WISE DERIVATION
Denote X XW. We rewrite L as follows:
L = trace (ZT log
exxp(Y)))
trace 1 (- log(lop((")) + +Y')
trace (z"Y'' + trace (z" log (oxp(Y')1c11)
L AXW) + trace (ZT log
trace
LzT (zTAxTI Axw) + trace (18 log (exp(Y")1c))
trace
N
N
Σ
A., XT
T +
log
Σ exp( Σ
(
1= JEN.
1=1
JEN
N
N
C
A Ans (r0)))
log
exp
Σ
A IricKic {se))
+
log
Σ exp
Σ
6=1 JEN,
t=1
JEN
N
exp
Σ
Σ
Åis ZicKi0
c- jEN;
log
7=1
exp( JEN,
A Rxc)
20

---

Under review as a conference paper at ICLR 2022
C Note that Σ Z3.0 for any j. Consider the derivation of L over Xy.d: c=1
dc
dXj',ee
exp( E sic) jEV.
1=1 exp
Σ
EljEN,
(Agi (Acy Zie
C Σ Σ
Austickze
Auz
E
exp( E A JEN:
exp
c=ljEN:
x
Σ
exp( E AioX)1o)
1=1
JEN:
(And)) exp
Σ Σ
Ans &
exp( E JEN.
Ais (ixe)
JEN.
2
Σ exp( E &ic) 0=1 jEN;
AAryZic)
Σ exp( Σ Aig (,e)
C
(Air)
exp(( Σ AisKiiic JEN,
N
JEN.
Σ exp( E Ais
JEN:
Σ (Zi,e) exp( E Aicx JEN:
+ +Zi,,d -1) eep(( E, A JEN,
Σ
A
c=L.ce
Σ expl Σ A
JENr
N
Σ
Aig +c) c') + (Zi,e' - 1)P(Y, = d'))
1=1
Σ Aig (
P(V: =c) d))
Writing the above matrix form, we have
dC = A(z-Y)
dC dw = xxAA AY' x A'
(14)
dx
D PROOF OF PROPOSITION 1
Proof. According to the given assumptions, for node v, we have A. 1 the expected number of Ø41 intra-class edges is dh (here the self-loop edge introduced by Á is not counted based on the definition of edge homophily and data generation process) and inter-class edges is (1 h h)d. Suppose there C > 2 classes. Consider matrix ÅZ,
Then, have E ((AZ)..]]
E
Σ Av, (Zx. L
Σ kEV
12
where is the indica-
d=1
for function.
21

---

Under review as a conference paper at ICLR 2022
When is in class e, have
Σ KEV
Ad+1 d+1
(hd++1
hd intra-class edges + self-loop
d+1
introduced by A).
1 18 71
When is not in class c, have
Σ
(C- ()d11) ((1 h)d inter-class edges
(1-hid
d+1
KEV
uniformly distributed in the other C classes).
For nodes we have (AZ)o.. (AZ)u,; dently generated for all kt k'' E V. we have
RC and since elements in A and An, are indepen-
E. (AZ)).. v. (A2) v0,
= E
Av, 1 (22,
Σ
Aux (20,-12)
KEV
NEV
E
Au,te ( (Ze,==o1)
E
Σ
Au (2x,
KEV
WEV
Thus,
E [((A, v),u] = E < (AZ) v. (AZ)u,: >
ΣE
R
Σ KEV
Au, (Zu. -
I
E KEV
Au, (22.
hd++1
+ (0 [C-I][++Ij=
((1-1)aja
u, in the same class
d+1
2(hd+ () (1-b) + 2)
u, v are different classes
(c-1)(d+1)=
(C-1)(a+1)2)
For nodes u1, u2, and v, where Zug = Zu and Zug. + Zuz
g(h) ((A 2) v. [{((A, 2)
(15)
(C - (C- (hd + 1)² + (C - 11) [[1 - h)dd² (C (2(dd h)d) (C (C- h]d
(C- 1
(C 1) + 1) (1 h)d
(C (0-1)(d+1)
Setting (hh) O, obtain the optimal h:
d+1-C
(16)
Cd
For the data generation process in the synthetic experiments, we fix djutas then d diatra/ h, which is a function of h. We change d in equation 16 to diara// /h, leading to
h dinrr/ h +
(17)
Cd
is easy to observe that satisfying equation 17 still makes g(h) = O, when in g(h) is replaced by dintra hb. From equation 17 we obtain the optimal h in terms of duum::
diatra
Cduaaa + +C -
D.1 AN EXTENSION OF PROPOSITION 1
Base on the definition of aggregation similarity, we have
| Mean, ((S(A, Z), Zu.; Zv.:)) 2 Mean,, (IS(A, DonnlZu # Zu.
Sage ()(A,)))
|V]
22

---

Under review as a conference paper at ICLR 2022
Σ 1
Mcana ((S(A, ,u, Zz.)) Meana (1.(
V
Then,
Σ 1 NEV
Meany (1n, Meany (l (
(S(A,)))
Sagg
=E
[4|
Σ NE
P (Meanu ((,(A, Zuzl)
Mcan, 2C Zu F Zoi3)
M
P (Mean,
Zoo))) Mean, ((S(A, D),ul # Zouit) 20)
Consider the random variable
RV = Mean., ((S(A, o) lu. Zo Mean,, ((S(A, 2),,u * Zo.:))
Since RV symmetrically distributed and under the conditions 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 2 0) 2 0.5 and this can explain why Hag is always greater than 0.5 many real-world tasks.
E PROOF OF THEOREM 1
Proof. Define W. (ÅZ),.e Then,
C
W
Σ Ao, 10,
Σ
W =1
KEV
Note that
S(T A, = (T- 1\T 77 + ATZ ÅZZT -7.7 AT
(18)
For any node v, let the class v belongs to denoted by cu- For two nodes v, u, if Ze * Zu: we have
(777)) )0,u =
(ĀZZT AT)
W.We &
c=1
(ĀZZ*) )o,, W.C..
(ZzT )T (AZZ)) = We
Then, from equation i8 follows that
(S(T - Å, 2)) Σ W.W. Wc. We.
When C' = 2,
S(I A, 2), = WC (WC. 1) + We (W.. 1) 5
If Zv Zu i.e. Cy Cu. we have
(ZZ )om
C
(AzzT AT )on
Σ
w.we
23

---

Under review as a conference paper at ICLR 2022
(AZZ")u, W (ZZ" )²),.a (AZZT) )n.
Then, from equation 18 follows that
C
S(I 2, v.a = 1+ Σ
w.W. W.r W
c=1
Σ
W.W. + + W. W. W. W
c=1,e0
W.W. + +(1+++1-000 W. (1 W 2 0
Thus, if C 2, for any v E V, if Zu,: # Zu.:, we have S(I A. 2). 0: if Zu.; Zy we have - - Á, Z)... 2 O. Apparently, the two conditions equation are satisfied. Thus e is diversification distinguishable and DD A. The theorem is proved.
MODEL COMPARISON ON SYNTHETIC GRAPHS
1.0
1.0
0.8
0.8
0.8
Accuracy
Accuracy
Accuracy
0.4
1gc1
0.2
0.2
19c1
amm-gr1
acm-grr
#cm-ge1
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Modified Aggregation Hom Homophily
Modified Aggregation Homaphily
Modified Aggregation Hamophily
(a) syn-Cora
(b) syn-CiteSeer
(c) syn-PubMen
1.0
Accuraty
Accuracy
Acturacy
0.6
0.6
0.6
0.4
0.4
0.4
mip1
mp1
m8p1
19c1
0.2
5911
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
Modified Aggregation Homaphily
Modified Aggregation Homaphily
Madified Aggrepation Homophily
(d) Senn-Chamelleen
(e) syn-Squil rrel
(f) syn-Fi
Figure 6: Comparison of test accuracy (mean + std) of MLP-1, SGC-I and ACM-SGC-I on synthetic datasets
24

---

Under review as a conference paper at ICLR 2022
Accuracy
0.6
Accuraci
0.6
Accuracy
0.6
0.4
0.4
0.4
nlp2
mip2
mb2
0.2
0.2
0.6
0.8
1.0
0.2
0.6
0.4
0.6
0.8
1.0
Modified Aggregation Homopphly
Modified Aggregation Homophily
Modified Aggregation Homophily
syn-Cora
(b) syn-CiteSeer
(c) syn-PulMMed
1.0
0.8
0.8
0.8
Acouracy
Accuracy
Acouracy
0.6
0.6
0.6
mlp2
mp2
0.2
g5n
gen
scm-gon
Bom gm
acm-gon
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Modifiid Aggregation Homophily
Modified Aggregation Homophily
Modified Aggregation Homophily
(d) syn- wwn-yhanaaae Chame
(e) syn-Squirrel
(f) syn-Film
Figure 7: Comparison of test accuracy (mean + std) of MI.-2, GCN and ACM-GCN synthetic datasets
In order separate the effects of nonlinearity and graph structure, we compare sge with 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 and Figure we can see that on each H M (9) level, ACM-GNNs will not underperform baseline GNNs and the graph-agnostic models. But when H (9) is small, baseline GNNs will be outperformed by graph-agnostic models by large margin. This demonstrate the advantage of the ACM framework. The curves will almost be the same for ACMII framework.
agg
G DISCUSSION OF THE LIMITATIONS OF DIVERSIFICATION OPERATION
X = Z
Class
Class
Class 3
Class
(1-
(I-A)xX7(1 Â
[1,0,000]
.50
.50
.25
-50
25
.00
-25
.25
[1.0,0.0]
.50
.67
50
-50
.17
17
-50
.17
.17 .11
3: [1,0,000]
.25
.00
50
-25
.0
25
-50
.00
[0,1,000]
-50
-50
-25
500
25
.00
25
-25
-13 .00
[0.10000]
-50
[0,0,1,0]
.00
-17
.25
.00
.25
500
25
-38
-33
[0,0,1.0]
-25
-50
-50
.25
.25
50
113
-17
[0,0,0.1]
25
.17
000
-5
55
25
00
50
38
.7
.13
.17
.13
11
-38
-38
-13
38
38
.25
[0,0,0,1]
800
.11
.1
.00
117
33
17
17
.25
22
[0,0,0.1]
Figure 8: Example of the case (the area black box) that HP filter does not work well for harmful heterophily
From the black box area S(I Å, 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 no edge between them; nodes in class and assign non-negative weights to each other as well. This is because the surrounding differences of class are similar class 4, class 2 and 3. In real-world applications, when
25

---

Under review as a conference paper at ICLR 2022
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 DD DDAxx(9) METRICS AND THEIR ESTIMATIONS
Additional Metries There are three key factors that influence the performance of GNNs in real- world 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 aggregated- feature-label consistency as well to fully investigate the performance of NNs and GNNs. With
aggregation similarity score of the features Sags (5(1, and aggregated features Sage (S(Á,))
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 not the main cause of the performance degradation. And from Table 6 we can see that the Sugg X)) for the above 4 datasets are lower than their corresponding Sugy (S(TT)),, which implies that it is the aggregated-feattre-llle inconsistency that causes the performance degradation.
Example 2: According to the widely used analysis based on node edge homophily, the graph structure of Chameleon, and Squirrel are heterophilous and bad for GNNs. But in practice, GCN outperforms MLP-2 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 Sage (s( is higher than its Sage (S(I, which means its graph-label consistency and segregated-featurre label consistency help the graph- aware model obtain the performance gain; for Squirrel, its modified aggregation homophily is low but its Sags (S(Á, X) is higher than its Sagg (X) which means although its graph-label consistency is bad but the aggregated-featte feadd--etttrraaaaeee 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, Sage (S(Á, x)) and Sage X)) are not deciding or threshold values because they do not consider the nonlincar structure in the features. In practice, low score does not tell us the GNN models will definitely perform bad.
Comell
Wiscocsin
Texas
Film
Chameleon
Squirel
Cora
CiteSeer
PubMed
Haz (9) Saz ())
0.9016
0.8884
0.847
08411
0.805
0.6783
0.9952
0.9913
0.9716
0.8251
0.7769
0.6557
0.5118
0.8292
0,7216
0.9639
0,9393
0.8623
(S(I)X))
038287
0.9672
0.9103
0,9315
DDD x0) (9)
0.3497
0.609
0.459
0.3279
0.3109
0.2711
0,2681
014134
0.1889
A (A)
0.9046 0.0022
0.8906 +: 0,0099
0.8451
1 00041
0.8041
0.0088
0.6788
0.0077
0,9059 4: 0.0011
09907
0.0015
0.9734
0.0015
8 ())
0.8266
0.0826
0,2200
0.0511
0,6835
004498
0,5345
+ 0.421
0.8433
0.0700
0.7352
0.0122
0,9437 + 0.0255
+ 0.0038
0,8626
0.0021
Sug (S(T, (8(T,)))
0.9752
0.0174
0,966)
0.0366
0.5438
0.0844
0.7472
0.9204 1: 0.0044
0.0036
0,8835
DD (G)
0.3936 :: 0.0663
0.6073 + 0.0366
0.4617 + 0,072 0.3300 + 0.136 0.3329 1 0.151
0.5021 + 00101 0.3198 + 0.0255
0.4434 1: 0.136
0.1919
0.0046
Table 8: Additional metrics and their estimations with only training labels (mean + std)
Furthermore, in most real- worldworld 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/validationnee 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 shown in table
26

---

Under review as a conference paper at ICLR 2022
Analysis From the reported results 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.
that the estimations accurate and the errors
I EXPERIMENTS ON FIXED SPLITS PROVIDED BY (PEI ET AL., 2020)
See table 9 for the results and table I0 the optimal searched hyperparameters.
Cornell
Wisconsin
Texas
Film
Chameleon
Squirel
Cora
CiteSeer
PuhMed
Rank
GPRGINN
78.11
5.32 35.16
46.31
2.46
87.95
77.13
H2GCN
82.70
5.28
87.65
4.98
84.36
1: 7.23
35.70
1.00
60.11
2.15
36.48
1.86
87,87
1: 1.20
77.11
1.57
89,9
0.38
6.78
FAGON
76.76
5.87
79.61
1 1.58
76.49
+ 288
34,82
= 1.35
46.07
: 2,11
30.83
1 0.69
W8.05
+ 1.57
77.07
2 2.05
88.09
1 1.38
9.56
Geom: GCN
60.54 à 3667
64.51
a 3,66
66.76
à: 2.72
31.59
1,15
60.00
4 2881
38.15
0,92
85.35
1 1.57
78.02
89.95
0.47
9:22
ACM-SGC-1
82,43 + 5.44
86.47
+
81
81
4.53
35.49
63.99
1.66
45.00 1.4
86.9
1.38
76.73
1.59
8849
8.44
ACM-SGC-2
82.43
4 5.44
86.47
1 3.77
81.89
1 4.53
36.04
= 0.83
59.21
2.22
40.02
1 0.96
87.69
1 1.07
76.59
2 1.69
89.01
= 0.6
8.22
ACM GCN
85.14
4 6.07
88.43
3.22
87.84
4.4
36.28
1.09
66.93
1,85
54.4
1,8
87.91
4 0.95
77.32
+ 1.7
90.00
0.52
2.33
ACM Snowball-2
87.06
87.57
ACM-Snowball-
83.24
5.38
86.67
+ 4.37
87.84
3.87
36.82
0.94
66.91
1.73
53.31
1.88
87.1
0.93
75.91
1.57
89.1
0.43
5.22
ACMIL-GCN
85.95
4: 5.64
87.45
+ 3,74
86.76
+ 4.75
36.16
1,11 66.91
2,55
51.85
+ 1.38
88.01
+ 08
15
14
89,89
0.43
3:22
SCMII-Snowball
87.57
89.84
3aowblll-
82.7
1 4.86
85.29
1
4.23
85.41
4: 6.42
36.49
1.41
66.86
1.74
48.87
1.23
87.16
4
L01
76.18
1.55
89.73
2 0.52
7.00
Table 9: Experimental results on fixed splits provided by Pei et al. (020): average accuracy + standard deviation on real-world benchmark datasets. The best results are highlighted. Results of Geom- GCN, HCGCN and GPRGNN are from Pei al. (2020); Zhu et al. (2020b); Lingam et al.] (2021); results on the rest models are run by ourselves and the hyperparameter searching range is the same as table 5
J A DETAILED EXPLANATION OF THE DIFFERENCES BETWEEN ACM-GNNS, ACM(II)-NNN AND GPRGNN, FAGCN
Difference with GPRGNN CCien et al. 2021): To explain how the channel mixing mechanism makes ACM-GNNs and ACMII-GNNs different from the learning mecha-
K
nism in GPRGNN, we first rewrite GPRGNN as Z Σ HH)
Σ
(H(
K=
H The node-wise channel mixing mechanism in GPRGNN form is Z Σ diag(nh.n
diag(T, "......
((), where N the number of nodes and
1h. 1-11=, 11:=1.... 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 fixed Å, FAGCN learns new filter A' based on Å in similar way as GAT (Velickovic al. 2017). Some people may take Á' 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 Å' can be decomposed into Å' A Å'2. where A', and - represents positive and negative edge (propagation) information respectively. In our paper, we are not discussing the advantages of using the learned filter Å' over the fixed filter Á, we are comparing the models with and without channel mixing mechanism. We believe the empirical results real-world tasks in table and table 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
27

---

Under review as a conference paper at ICLR 2022
Datasets
Modelsstypeppraaneees
weight_
dropout
hidden
results
sverage spoch timelaverage total time
ACM-SGC-1
0.01
5.00E-06
0
64
82.43
5.44
5.37ms/23.055
ACM-SGC-2
5.00E-06
5.92mu/25.666
ACM-GCN
0.05
5.00E-04
0.5
64
85.14
6.07
8.0Hms/1166 667
ACMII-GON
1.005-04
85.95
1.83ms//2
Cornell
FAGCN
0.01
1.00E-04
0.6
76.76
5.87
8.80ms/7 7.67s
ACM-Suowball-2
0.05
5,00E-03
0.3
64
85.41
5.43
11.50ms/2.55
3CM-Snowball-3
5.00E-03
15.06ms/33112
SCMil--nowball-2
0.1
5.00E-03
0.2
64
85.68
5.93
12. 12.63ms/2.55 58s
ACMII Snowball-3
0.05
5.00E-03
0.2
64
82.7
4.86
14.59ms/3.06s
ACM-SGC-1
0.1
5.00E-06
86.47
3.77
5.07mss/14.. 14.07%
ACM-SGC-2
0,1
5,00E-06
0
64
86.47
3.77
5.30ms/16 (00ms/166.00 05%
ACM-GCN
1.005-03
ACMII-GCN
0.01
5.00E-05
0.1
64
87.45
3.74
8.40ms/2 19%
Wisconsin
FAGCN
0.01
5,00E-05
0.5
64
79.61
1.59
8.6 84s
ACM-Saoue -CM-Soowball-2
0.01
1.00E-03
0.4
87.06
12.5 1.51mm/2.60s
-SM--uowball--3
0.01
1.00E-022
0.1
64
86.67
4.37
14, 14.92ms/33115 13.15
ACMII-Sa
11.96ms/2.66
ACMIl-Snowball-3
0.01
5.00E-03
0.5
64
83
4.23
14.8 14.87ma/3.10n 3.s0
ACM-SGC-1
0.01
L00E-05
$1.89
5.34ms/19 00s
ACM-SGC-2
0.05
1.00E-05
0
81.89
4.53
5.50ms/9
ACM-GCN
0.05
5.00E-04
0.5
64
87.84
4.4
9.62ms/1 99%
ACMII-GCN
1.005-03
9.98mm/2
Texas
FAGCN
0.01
LO0E-00
0
64
76.49
2.87
10.45mm/55.70 70s
2CM-Snowbull-2
0.01
5,00E-03
0.2
64
87.57
4.86
11.56ms/2.45
ACM-Spowball-3
0.01
5.00E-03
0.2
87.84
3.87
15.17mms/3.15
ACMII Snowbll2
0.01
L.0E-00
0.2
64
86.76
4.43
11. 11.36ms//..3
SCMll-Snowball-3
15.84ms/3.44B,
ACM-SGC-1
0.05
5.00E-04 04
0
64
35.49
1.06
5.39mss .17
ACM-SGC-2
0.05
5.00E-04
0.1
36.04
0.83
13.222m//3.3s
ACM-GCN
0.01
5.00E-03
36.28
1.09
8.96mm//1
ACMII-GCN
0.01
5.00E-03
0
64
36.16
9.06ms/ 3.66ms/1..83. 1.83s
FAGCN
5.00E-05
15.60ms/2.51
ACM-Snowball-2
0.01
100E-02
0
64
36.89
1.18
14.77ms/3.01s
ACM 3
0.01
1,005-02
0.2
64
36.82
0.94
16.57ms/3.366
ACMII-Suae Snolllll
0.01
5.00E-03
0.1
36.55
1.24
12.76ms/2.57%
(CMMI-Snowballl
0.05
5.00E-033
0.3
64
36.49
1.41
16.5 1..33.43349%
5.00E-00
0.9
5.92ma/
ACM-SGC-2
0.1
0.00E+000
0.9
64
59.21
2.22
8.84ms/ 78s
ACM.GCN
0.05
5.00E-05
0.7
66.93
1.85
8.40ms/ 71ss
ACMII-GCN
0.05
5.00E-06
0.8
66.91
2.55
8.90ms/2 10s
Chameleon
FAGCN
0.01
5.00E-0S
0
64
46.07
2.11
16. 9..90ms/7.000 946
2
0.7
12.50ms/2..6
ACM-Snow/ 3
0.01
1.00-00S
0.8
64
66.91
1.73
16. 22m/44 91s
ACMII Snowbll2o
0.01
5.00E-05
0.8
66.49
1.75
12.65ms/33.d
3holll--oowall3333
0.05
5.00E-05
0.7
66.86
1.74
17.60mz/4.
ACM-SGC-1
0.08
5.00E-06
0.9
64
45
1.4
6. Oms//2 18s
0.9
35.75ms/9 62s
ACM-GCN
0.05
5.00E-06
0.7
64
54.4
1.88
10.4 10.48mm/2.688
ACMIL-GCN
0.05
5.00E-06
0.7
51.85
1.38
1..99ss/2.91s
Squirrel
FAGCN
5.00E-03
0
30.86
0.69
10. 10.90ms// 3.91s
ACM--nowballl
0.01
1.00-04
0.7
64
$2.5
1.49
17. 77.89ms//..70 78s
Snowbull.3
5.00E-05
0.7
22.60ms/7...m
ACMII-Snowbll-2
0.05
5.00E-0S
0.6
64
50.15
1.4
9..55m/3445
(CMIl-Snowball.
0.01
5.00E-04
0.6
48.87
1.23
23, 23.52ma/4.99) 94s
ACM-SGC-1
0.05
5.00E-05
0.7
86.9
1.38
4.99ms/2 40s
ACM-SGC-2
0.1
0
0.8
64
87.69
1.07
5.16ms/1 16s
5.00E-05
ACMII-GCN
0.01
1.00E-04
0.6
64
88.01
1.08
8.59ms// 96s
Corn
FAGON
0.02
1.00-04
0.5
88.05
1.57
9. 9.30ms/10.66
ACM ACM-Snowball-22
0.01
1.005-03
0.5
87.42
1.09
12.54mx/2. 22mmm//2.2...
ACM-Snowball-33
0.01
5:00F-06
0.9
64
87.1
0.93
15.83ms/ 1.33s
ACMIL Snowball22
1.00E-03
12.06ms/22
ACMII-Snowhall-3
0.01
5.00E-03
0.5
87.16
1.01
16.29ms/3
ACM-SGC-1
0.05
0.00F
0.7
76.73
1.59
5.24ms/1 14s
ACM-SGC-2
0.1
0.00E+000
0.8
76.59
1.69
5.14m//1 033
ACM-GCN
0.01
5:00E-06
0.3
64
77.32
1.7
8.89ms/1 79s
8.95ma/
CiteSeer
FAGCN
0.02
5.00E-05
0.4
64
77.07
2.05
10.05ms/5..o 69s
0.01
5.00F-05
76.41
1.38
12.87ms/2.599 59s
ACM-Snowball-3
0.01
5.00E-06
0.9
75.91
17. 17.40ms/11 1.92s
CCMI--Snowall-222
0.01
5:000033
0.5
64
76.92
1.45
13. 1..000//22.0 946
ACMII-Snowball-3
5.00E-05
17.47ms/S..e
ACM-SGC-1
0.05
5.00E-06
0.4
64
88.49
0.51
5.77ms/3 1.65
ACM-SGC-2
0.05
5.00F-06
89.01
8.50ms/55 18s
ACM.GCN
0.01
5.00E-05
0.4
90
0.52
8.99ms/2
ACMII-GCN
0.01
L.00E-04
0.3
64
89.89
0.43
9.70ms/2 2755
PuhMed
10.30ms/8.755
4CM-Snowball-2
0.01
1.00E-03
0.3
64
89.80
0.57
15.05ms/3.11 11s
0.01
5.00F-03
89,81
0.43
20.5 20.51
ACMII-Snowball2
0.01
5.00E-04
0.4
89.84
15. 10ma/3
0.01
1.00--03
0.4
64
89.73
0.52
20. 46.4/44 32s
Table 10: Optimal Hyperparameters for FAGCN and ACM-GNNs on fixed splits
28


Reviews:
[{"review_id": "Gydl9nHqoUZ", "reviewer": "Reviewer_vrWz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n(1) solid and deep analysis of the proposed metric and filterbank-based aggregation scheme.\n(2) solid and comprehensive experiments to show the significance of the proposed ideas.\n\nCons:\n(1) some necessary justifications are missing.\n(2) presentation can be improved.\n\nDetailed comments:\n-In section 3.1, it is not reader friendly to mention \"mean aggregation\" before introducing Definition 1. The same comment can be applied to the beginning of Section 4: explicitly give the definition of diversification operation before discuss about it.\n-Figure 2: how do you get the curves of (b) (c) (d) when you only manipulate H_edge?\n-Some figures are not easily readable in b/w print.\n-The three steps of ACM lacks explanations and justification. Specifically, in Steps 2 and 3, why using such a combination weight calculation scheme? The raw weights are estimated only based on the results from the corresponding filter. I feel it would be better to decide the weight for each channel based on all the filtered results. In step 3, why using W_{mix}? How do we interpret the temperature parameter here? Is the softmax in step 2 row-wise (need to explain it in order to improve readability)?\n-Experiments: In Figure 4, how to interpret the relations between H_{agg}^M and the performance increase? It would be better to put important and necessary discussions in the main text.\n\n-Minor typos: page 7, \"called is\", \"a set of filterbank\".", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper is well written and novel enough for this conference. The presentation can be improved and more justification can be added to further improve the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "EXZsB2Ep7nN", "reviewer": "Reviewer_o6WB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses a well known problem in the literature in a seemingly effective way. It is really well written, offering good background on the problem and going smoothly from the exposition of the problem and the limited view of existing approaches to the proposed ACM architecture to address it. Then, it performs very comprehensive experiments that demonstrate the effectiveness of the proposed scheme.\n\nIf I need to mention a weakness, this is the fact that the paper necessarily compresses a lot of discussion and description due to the conference constraints. For that reason, it misses a thorough analysis and comparison with the state of the art, as well as a more in-depth discussion of the experimental results and conclusions. Yet, the authors make the best of the available space to cover all necessary information.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper proposes a new architecture, called Adaptive Channel Mixing, with the aim to address several cases of harmful heterophily in GNN node classification settings. The paper is well written and motivated and contains convincing experimentations. It could also have a big impact on GNN node classification practice and future research.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6qJ-FgP8UIB", "reviewer": "Reviewer_bk6o", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Heterophily is an important factor for us to understand the performance of GNN on different graphs.  I think the paper found a good point that heterophily is not always harmful for all GNNs. This paper provides a new perspective to understand the problem, and designs a new metric based on the gradient analysis, which is interesting. The filterbank based method does solve the problem to some extent and gained very good performance.\n\nHowever, 1. It is not clear why the gradient leads to the aggregation similarity score as the heterophily metric, and how does it impact the GNNs’ performance. There is also no direct connection with the later diversification analysis. \n2. The diversification operation helps on heterophilous graphs also lacks of enough motivation and theoretic explanation. It seems there is only one example (Figure 3) to illustrate it. That is not enough. In addition, the diversification operation even cannot work well for all cases, especially for multi-class problems. This makes the value of this paper hurt a lot.\n3. The filterbank based method is trivial and not new. Adding that the theoretic analysis of diversification operation or new metric is also not convincing, the novelty of this paper is incremental. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "Good motivation and observations, but the solution is also not novel enough and lacks of theoretic justification. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4yUbO5C2UjK", "reviewer": "Reviewer_ZQM7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. In general, the authors focus on an important problem and the paper is easy to follow. There are a few issues the authors need to address.\n\nMy first concern is that the heterophily analysis might be over-simplified. It is good to see that the authors introduce an example to show when traditional heterophily metrics may fail to provide a meaningful heterophily value. However, the analysis conducted has two major assumptions: binary classification and one-hop aggregation. Though I understand that certain assumption is required for most theoretical analysis, these two seem to be very strong given that multi-layer of GNNs are usually operated on graphs with multiple node labels. This reduces the significance of the analysis.\n\nSome technical terms also need to be better explained or discussed. For example, the authors introduce high-pass (HP) and low-pass (LP) filters in Sec. 4 without introducing any motivation or rationales of applying them. I suggest the authors to better connect these filters with the analysis in Sec. 3 so that readers can better understand why in certain scenarios these two filters can help alleviate the heterophily problem. The authors briefly introduce some potential implementation of HP/LP filters in Sec. 4.2 while the exact implementation selected in the experiments is missing. I suggest the authors to explicitly indicate which filter implementations are selected and whether they're deterministic or learnable.\n\nThe ACM framework seems to be a weighted aggregation of the results after frequency filters. I suggested the authors to add an ablation study by comparing the ACM framework with some multi-head self-attention mechanisms to better understand where the gains are from.", "summary_of_the_paper": "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.", "summary_of_the_review": "Strength:\n+ Focusing on an important problem\n+ Paper is easy to follow\n\nWeakness:\n- Over-simplified theoretical analysis\n- Some technical terms need to be explained / discussed\n- Missing certain ablation studies", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper is addressing an interesting problem. However, the authors analyze the effect of heterophily on GNN for node classification. The authors simplify the analysis by removing the nonlinearity in the GNN model and derive some theoretical results. However, the analysis is very specific to the simplified version of GNN, and the link to later proposed solution is also weak. Furthermore, a more significant improvement in experiments will also make the paper more convincing.
Decision: Reject