# Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

Xiang Li  Renyu Zhu  Yao Cheng  Caihua Shan  Siqiang Luo  Dongsheng Li
Weining Qian

###### Abstract

We investigate graph neural networks on graphs with heterophily. Some existing
methods amplify a node’s neighborhood with multi-hop neighbors to include more
nodes with homophily. However, it is a significant challenge to set
personalized neighborhood sizes for different nodes. Further, for other
homophilous nodes excluded in the neighborhood, they are ignored for
information aggregation. To address these problems, we propose two models
GloGNN and GloGNN++, which generate a node’s embedding by aggregating
information from global nodes in the graph. In each layer, both models learn a
coefficient matrix to capture the correlations between nodes, based on which
neighborhood aggregation is performed. The coefficient matrix allows signed
values and is derived from an optimization problem that has a closed-form
solution. We further accelerate neighborhood aggregation and derive a linear
time complexity. We theoretically explain the models’ effectiveness by proving
that both the coefficient matrix and the generated node embedding matrix have
the desired grouping effect. We conduct extensive experiments to compare our
models against 11 other competitors on 15 benchmark datasets in a wide range
of domains, scales and graph heterophilies. Experimental results show that our
methods achieve superior performance and are also very efficient.

Machine Learning, ICML

##  1 Introduction

Graph-structured data is ubiquitous in a variety of domains including
chemistry, biology and sociology. In graphs (networks), nodes and edges
represent entities and their relations, respectively. To enrich the
information of graphs, nodes are usually associated with various features. For
example, on Facebook, users are connected by the _friendship_ relation and
each user has features like _age_ , _gender_ and _school_. Both node features
and graph topology provide sources of information for graph-based learning.
Recently, graph neural networks (GNNs) (Kipf & Welling, 2016; Veličković et
al., 2017; Hamilton et al., 2017) have received significant attention for the
capability to seamlessly integrate the two sources of information and they
have been shown to serve as effective tools for representation learning on
graph-structured data.

Based on the implicit graph homophily assumption, traditional GNNs (Kipf &
Welling, 2016) adopt a non-linear form of smoothing operation and generate
node embeddings by aggregating information from a node’s neighbors.
Specifically, _homophily_ is a key characteristic in a wide range of real-
world graphs, where linked nodes tend to share similar features or have the
same label. These graphs include friendship networks (McPherson et al., 2001),
political networks (Gerber et al., 2013) and citation networks (Ciotti et al.,
2016). However, in the real world, there also exist graphs with _heterophily_
, where nodes with dissimilar features or different labels are more likely to
be connected. For example, different amino acid types are connected in protein
structures; predator and prey are related in the ecological food webs. In
these networks, due to the heterophily, the smoothing operation could generate
similar representations for nodes with different labels, which lead to the
poor performance of GNNs.

Figure 1: A toy example to show global homophily. All the homophilous nodes
express the global homophily of the center user.

To generalize GNNs to heterophilous graphs, some recent works (Zhu et al.,
2020b; Bo et al., 2021; Chien et al., 2020) have been proposed to leverage
high-pass convolutional filters and multi-hop neighbors to address the
heterophily issue. On the one hand, the high-pass filters can be used to push
away a node’s feature vector from its neighbors’ while the low-pass filters
used by traditional GNNs do the opposite. The combination of low-pass and
high-pass filters in these models enforces the learned representation of a
node to be close to its homophilous neighbors’ and distant from heterophilous
ones’. On the other hand, in heterophilous graphs, linked nodes are more
likely to be dissimilar while distant nodes could share a certain similarity,
so we have to jump the _locality_ of a node to find its homophilous neighbors.
As shown in Figure 1, a user has only one _local_ neighbor with homophily,
while three homophilous nodes exist multi-hop away. All these four nodes
exhibit the _global homophily_ for the user, which can be used to help predict
her label. Meanwhile, since it has been pointed out in (Zhu et al., 2020b)
that the 2-hop neighborhood of a node under some mild condition will be
homophily-dominant in expectation, some models amplify a node’s neighborhood
with multi-hop neighbors. However, how large the neighborhood size should be
set for different nodes is a challenge. Further, for those homophilous nodes
excluded in the neighborhood, they will not be utilized in information
aggregation. Therefore, we propose to leverage the global homophily for a node
in the graph by adding all the nodes to its neighborhood. As a side effect, in
this case, the traditional neighborhood aggregation will have a quadratic time
complexity, which is practically infeasible. Further, more heterophilous nodes
will be included in the neighborhood, which could adversely affect the model
performance. Therefore, a research question arises: _Can we find global
homophily for a node and develop a GNN model that is both effective and
efficient for heterophilous graphs?_

In this paper, to find Global homophily for nodes in graphs with heterophily,
we propose an effective and scalable GNN model, namely, GloGNN. In the $l$-th
convolutional layer, inspired by the linear subspace model (Liu et al., 2012),
we linearly characterize each node by all the nodes in the graph and derive a
coefficient matrix $Z^{(l)}$ such that $Z_{ij}^{(l)}$ describes the importance
of node $x_{j}$ to node $x_{i}$. We formulate the characterization problem as
an optimization problem that has a closed-form solution for $Z^{(l)}$. After
that, taking $Z^{(l)}$ as the weight matrix, we generate node embedding matrix
$H^{(l)}$ by aggregating information from global nodes. Note that directly
computing such $Z^{(l)}$ and $Z^{(l)}$-based neighborhood aggregation lead to
cubic and quadratic time complexities w.r.t. the number of nodes,
respectively. Hence, we avoid calculating $Z^{(l)}$ directly and reorder
matrix multiplication in neighborhood aggregation, which effectively reduces
the time complexity to linear. Finally, we mathematically show that both
$Z^{(l)}$ and the generated node embedding matrix $H^{(l)}$ have the _grouping
effect_ (Lu et al., 2012), i.e., for any two nodes in a graph, no matter how
distant they are, if they share similar features and local structures, their
embedding vectors will be close to each other. This helps explain the
effectiveness of our models. We summarize the main contributions of our paper
as:

$\bullet$ We propose two effective and efficient GNN models, GloGNN and
GloGNN++.

$\bullet$ We theoretically show that both $Z^{(l)}$ and the generated node
embedding matrix $H^{(l)}$ have the grouping effect.

$\bullet$ We combine low-pass and high-pass convolutional filters in
neighborhood aggregation, as $Z^{(l)}$ allows signed values.

$\bullet$ We show the superiority of our models against 11 other methods on 15
benchmark datasets of diverse domains, sizes and graph heterophilies.

##  2 Related Work

GNNs have recently received significant interest for the superior performance
on graph-based learning. The early model GCN (Kipf & Welling, 2016) extends
the convolution operation from regular data to irregular graph-structured
data. GCN is a spectral model (Bruna et al., 2013; Defferrard et al., 2016),
which decomposes graph signals via graph Fourier transform and convolves on
the spectral components. There are also a class of spatial GNN models that
directly aggregate information from spatially nearby neighbors of a node. For
example, GraphSAGE (Hamilton et al., 2017) generates a node’s embedding by
aggregating information from a fixed number of neighbors. GAT (Veličković et
al., 2017) introduces the attention mechanism to learn the importance of a
node’s neighbors and aggregates information from these neighbors based on the
learned weights. Further, GNNs have been widely studied from various
perspectives, such as the over-smoothing problem (Zhao & Akoglu, 2019; Rong et
al., 2019), the adversarial attack and defense (Dai et al., 2018; Zhu et al.,
2019), and the model explainability (Vu & Thai, 2020; Shan et al., 2021).

There are also works (Zhu et al., 2020b; Bo et al., 2021; Chien et al., 2020;
Yan et al., 2021; Suresh et al., 2021; Pei et al., 2020; Dong et al., 2021;
Lim et al., 2021; Yang et al., 2021; Luan et al., 2021; Zhu et al., 2020a; Liu
et al., 2021) that extend GNNs to heterophilous graphs. Some methods propose
to leverage both low-pass and high-pass convolutional filters in neighborhood
aggregation. For example, GPR-GNN (Chien et al., 2020) adapts to the
homophily/heterophily structure of a graph by learning signed weights for node
embeddings in different propagation steps. ACM-GCN (Luan et al., 2021) applies
both low-pass and high-pass filters for each node in a layer, and adaptively
fuses the generated node embeddings from each filter. Further, some methods
enlarge the node neighborhood size to include more homophilous nodes. As a
representative model, H2GCN (Zhu et al., 2020b) presents three designs to
improve the performance of GNNs under heterophily: ego and neighbor embedding
separation, higher-order neighborhood utilization and intermediate
representation combination. WRGAT (Suresh et al., 2021) transforms the
original graph into a multi-relational one that contains both raw edges and
newly constructed edges. The new edges can connect distant nodes and are
weighted by node local structural similarity. There also exist GNNs that study
the graph heterophily issue from other perspectives. For example, to jointly
study the heterophily and over-smoothing problems, GGCN (Yan et al., 2021)
allows for signed messages to be propagated from a node’s neighborhood. On the
other hand, it adopts a degree correction mechanism to rescale node degrees
and further alleviate the over-smoothing problem. To generalize GNNs to large-
scale graphs, LINKX (Lim et al., 2021) separately embeds node features and
graph topology. After that, the two embeddings are combined with MLPs to
generate node embeddings. Different from all these methods, GloGNN performs
node neighborhood aggregation from the whole set of nodes in the graph, which
takes more nodes in the same class as neighbors and thus boosts the
performance of GNNs on graphs with heterophily.

##  3 Preliminaries

In this section we introduce notations and concepts used in this paper.

[Notations]. We denote an undirected graph without self-loops as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{i}\\}_{i=1}^{n}$ is a set of nodes and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of edges. Let $A$
denote the adjacency matrix such that $A_{ij}$ represents the weight of edge
$e_{ij}$ between nodes $v_{i}$ and $v_{j}$. For each node $v_{i}$, we use
$\mathcal{N}_{i}$ to denote $v_{i}$’s neighborhood, which is the set of nodes
directly connected to $v_{i}$. We further construct a diagonal matrix $D$
where $D_{ii}=\sum_{j=1}^{n}{A_{ij}}$. We denote the node representation
matrix in the $l$-th layer as $H^{(l)}$, where the $i$-th row is the embedding
vector $h_{i}^{(l)}$ of node $v_{i}$. For the initial node feature matrix, we
denote it as $X$. We use $Y\in\mathbb{R}^{n\times c}$ to denote the ground-
truth node label matrix, where $c$ is the number of labels in node
classification and the $i$-th row $y_{i}$ is the one-hot encoding of node
$v_{i}$’s label.

[Homophily/Heterophily]. The homophily/heterophily of a graph is typically
defined based on the similarity/dissimilarity between two connected nodes
w.r.t. node features or node labels. In this paper, we focus on
homophily/heterophily in node labels. There have been some metrics of
homophily proposed. For example, _edge homophily_ (Zhu et al., 2020b) is
defined as the fraction of edges that connect nodes with the same label.
Further, high homophily indicates low heterophily, and vice versa. We thus
interchangeably use these two terms in this paper.

[GNN basics]. The convolution operation in GNNs is typically composed of two
steps: (1) feature propagation and aggregation:
$\hat{h}_{i}^{(l)}=\texttt{AGGREGATE}(h_{j}^{(l)},\forall
v_{j}\in\mathcal{N}_{i})$; (2) node embedding updating:
$h_{i}^{(l+1)}=\texttt{Update}(h_{i}^{(l)},\hat{h}_{i}^{(l)})$. One of the
most widely used GNN models is vanilla GCN (Kipf & Welling, 2016), which
adopts a renormalization trick to add a self-loop to each node in the graph.
After that, the normalized affinity matrix
$\hat{{A}}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$, where
$\tilde{A}=A+I_{n}$, $\tilde{D}=D+I_{n}$ and $I_{n}\in\mathbb{R}^{n\times n}$
is the identity matrix. Note that $\hat{{A}}$ is a low-pass filter while the
corresponding Laplacian matrix $L=I_{n}-\hat{{A}}$ is a high-pass filter. The
output in the $(l+1)$-th layer of vanilla GCN is
$H^{(l+1)}=\sigma(\hat{A}H^{(l)}W^{(l)})$, where $W^{(l)}$ is a learnable
weight matrix and $\sigma$ is the Relu function. After $L$ layers, $H^{L}$ is
then subsequently fed into a softmax layer to generate label probability
logits and a cross-entropy function for node classification.

##  4 Algorithm

In this section, we describe our models. We first show how to capture node
correlations and derive the coefficient matrix $Z$ in each layer. After that,
we introduce how to accelerate neighborhood aggregation based on $Z$. Further,
we theoretically prove that both $Z$ and $H$ have the desired grouping effect.
Finally, we summarize GloGNN and upgrade the model to GloGNN++. The overall
framework of GloGNN is given in Figure 2.

Figure 2: The overall framework of GloGNN. In each layer, we derive a
coefficient matrix, based on which a node’s embedding is generated by
aggregating information from global nodes.

###  4.1 Coefficient matrix

In graphs with heterophily, connected nodes are more likely to have different
labels while distant nodes could be from the same class. We thus have to
enlarge a node’s neighborhood to leverage more distant nodes. A
straightforward way is to use all the nodes in the graph. Inspired by the
linear subspace model (Liu et al., 2012), we characterize each node by all the
nodes in the graph. Specifically, in the $l$-th layer, we can determine a
coefficient matrix $Z^{(l)}\in\mathbb{R}^{n\times n}$:

$H^{(l)}=Z^{(l)}H^{(l)}+O^{(l)},$ (1)

where $O^{(l)}$ is a noise matrix. One can interpret $Z_{ij}^{(l)}$ as a value
that reflects how well node $x_{j}$ characterizes $x_{i}$, so $Z^{(l)}$ plays
the role of a weight matrix. Note that $Z_{ij}^{(l)}$ allows signed values. On
the one hand, the more similar two nodes are, the more likely that one node
can be represented by the other. Homophilous neighbors will thus be assigned
large positive coefficients. On the other hand, heterophilous neighbors will
be given small positive or negative coefficients due to the dissimilarities.
Further, since it has been pointed out in (Liu et al., 2020) that the over-
smoothing problem is caused by the coupling of neighborhood aggregation and
feature transformation, we decouple these two processes by first performing
feature transformation to generate $H^{(0)}$. Specifically, we use MLPs to map
feature matrix and adjacency matrix into $H_{X}^{(0)}\in\mathbb{R}^{n\times
c}$ and $H_{A}^{(0)}\in\mathbb{R}^{n\times c}$, respectively:

$H_{X}^{(0)}=\texttt{MLP}_{1}(X),\ H_{A}^{(0)}=\texttt{MLP}_{2}(A).$ (2)

Here, $c$ is the number of labels. Then we derive the initial node embedding
matrix $H^{(0)}$:

$H^{(0)}=(1-\alpha)H_{X}^{(0)}+\alpha H_{A}^{(0)},$ (3)

where $\alpha\in[0,1]$ is the term weight. Note that $H^{(0)}$ captures the
information of both nodes’ features and connectivities. Inspired by (Klicpera
et al., 2018), we use skip connection and further modify $H^{(l)}$ in Equation
1 into:

$H^{(l)}=(1-\gamma)Z^{(l)}H^{(l)}+\gamma H^{(0)}+O^{(l)},$ (4)

where $\gamma\in[0,1]$ is a hyper-parameter that balances the term importance.
Here, we characterize node correlations based on $H^{(l)}$. However, as
suggested in (Suresh et al., 2021), if two nodes share similar local graph
structures, they are more likely to have the same label. We thus measure node
correlations in terms of both feature similarity and topology similarity by
further regularizing $Z^{(l)}$ with nodes’ multi-hop reachabilities. We have
the following objective function:

$\scriptsize\min_{Z^{(l)}}\|H^{(l)}-(1-\gamma)Z^{(l)}H^{(l)}-\gamma
H^{(0)}\|_{F}^{2}+\beta_{1}\|Z^{(l)}\|_{F}^{2}+\beta_{2}\|Z^{(l)}-\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}\|_{F}^{2}$
(5)

where $\beta_{1}$ and $\beta_{2}$ are weighting factors for adjusting the
importance of different components, and $K$ is the maximum hop count. To show
the importance of the $k$-hop graph connectivity, we further introduce a
learnable parameter $\lambda_{k}$. The objective function consists of three
terms. The first term reduces noise and drives the linear representation for
nodes to be close to their own embeddings, the second term is a Frobenius
norm, and the third term regularizes $Z^{(l)}$ by the multi-hop regularized
graph adjacency matrices. A closed-form solution $Z^{{(l)}*}$ to the
optimization problem is

$\scriptsize\begin{split}Z^{(l)*}=&\left[(1-\gamma)H^{(l)}(H^{(l)})^{T}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}-\gamma(1-\gamma)H^{(0)}(H^{(l)})^{T}\right]\cdot\\\
&\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}\\\
\end{split}$

###  4.2 Aggregation acceleration

Based on $Z^{(l)*}$, we can write neighborhood aggregation in the $l$-th
layer:

$H^{(l+1)}=(1-\gamma)Z^{(l)*}H^{(l)}+\gamma H^{(0)}.$ (6)

However, directly updating $H^{(l+1)}$ by Equation 6 is infeasible due to the
cubic time complexity in computing $Z^{(l)*}$ and the quadratic time
complexity in calculating $Z^{(l)*}H^{(l)}$. To accelerate the updates of
$H^{(l+1)}$, instead of directly calculating $Z^{(l)*}$, we transform Equation
6 into (see Section C in the appendix):

$\begin{split}H^{(l+1)}=&(1-\gamma)H^{(l)}(H^{(l)})^{T}Q^{(l+1)}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}Q^{(l+1)}\\\
&-\gamma(1-\gamma)H^{(0)}(H^{(l)})^{T}Q^{(l+1)}+\gamma H^{(0)}\\\ \end{split}$
(7)

where

$\begin{split}Q^{(l+1)}=&\frac{1-\gamma}{\beta_{1}+\beta_{2}}H^{(l)}-\frac{1-\gamma}{(\beta_{1}+\beta_{2})^{2}}H^{(l)}\cdot\\\
&\left[\frac{1}{(1-\gamma)^{2}}I_{c}+\frac{1}{\beta_{1}+\beta_{2}}(H^{(l)})^{T}H^{(l)}\right]^{-1}(H^{(l)})^{T}H^{(l)}\\\
\end{split}$ (8)

Here, $H^{(l)},Q^{(l+1)}\in\mathbb{R}^{n\times c}$,
$I_{c}\in\mathbb{R}^{c\times c}$ is the identity matrix and $c$ is the number
of labels. In this way, we avoid computing $Z^{(l)*}$ directly and can
accelerate the updates of $H^{(l+1)}$ by matrix multiplication reordering.
Specifically, we first compute $Q^{(l+1)}$, where the second term is
calculated from right to left. In particular, the matrix inversion is
performed on a matrix in $\mathbb{R}^{c\times c}$, whose time complexity is
only $O(c^{3})$ and $c$ is generally a very small number. This significantly
improves the model efficiency. The overall time complexity of updating
$Q^{(l+1)}$ is $O(nc^{2}+c^{3})$, where $c^{2}\ll n$. After $Q^{(l+1)}$ is
calculated, we then update $H^{(l+1)}$. We compute each term of $H^{(l+1)}$ in
a similar right-to-left manner. For example, to calculate
$H^{(l)}(H^{(l)})^{T}Q^{(l+1)}$, we first compute $(H^{(l)})^{T}Q^{(l+1)}$ but
not $H^{(l)}(H^{(l)})^{T}$. This reduces the time complexity to be
$O(nc^{2})$, but not $O(n^{2}c)$. When calculating
$\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}Q^{(l+1)}$, we can first compute
$\hat{A}Q^{(l+1)}$ due to the sparsity of $\hat{A}$ for a general graph, which
only requires a time complexity of $O(k_{1}cn)$. Here, $k_{1}$ is the average
number of nonzero entries in a row of $\hat{A}$. While $\hat{A}Q^{(l+1)}$
generates a dense matrix, we can further employ the sparsity of $\hat{A}$ to
get $\hat{A}^{2}Q^{(l+1)}$. In this way, we can sequentially derive
$\hat{A}Q^{(l+1)}$, $\hat{A}^{2}Q^{(l+1)}$, …, $\hat{A}^{K}Q^{(l+1)}$ in
$O(k_{1}cn)$. In summary, the total time complexity to update $H^{(l+1)}$ by
Equation 7 is $O(k_{2}n)$, where $k_{2}$ is a coefficient and $k_{2}\ll n$.

###  4.3 Grouping effect

For a node $v_{i}$, we denote $\hat{a}_{i}^{k}$ as the $i$-th row of
$\hat{A}^{k}$, which represents $v_{i}$’s $k$-hop node reachability in a
graph. Given two nodes $v_{i}$ and $v_{j}$, if they have similar feature
vectors and local graph structures, their characterizations from other nodes
are expected to be similar. Formally, we have

######  Definition 4.1.

(Grouping effect (Li et al., 2020)). Given a set of nodes
$\mathcal{V}=\\{v_{i}\\}_{i=1}^{n}$, let $v_{i}\rightarrow v_{j}$ denote the
condition that (1) $\lVert x_{i}-x_{j}\rVert_{2}\rightarrow 0$ and (2)
$\lVert\hat{a}_{i}^{k}-\hat{a}_{j}^{k}\rVert_{2}\rightarrow 0,\ \forall
k\in[1,K]$. A matrix $Z$ is said to have grouping effect if

$v_{i}\rightarrow v_{j}\Rightarrow|Z_{ip}-Z_{jp}|\rightarrow 0,\forall 1\leq
p\leq n.$ (9)

We next theoretically show the grouping effect of $Z^{(l)*}$, $(Z^{(l)*})^{T}$
and $H^{(l+1)}$ by giving the following lemmas. Proofs of all these lemmas are
deferred to Section D in the appendix.

######  Lemma 4.2.

$\forall 1\leq i,j,p\leq n$,

$\begin{split}|Z_{ip}^{(l)*}-Z_{jp}^{(l)*}|&\leq\frac{1-\gamma}{\beta_{1}+\beta_{2}}\|{h}_{i}^{(l)}-{h}_{j}^{(l)}\|_{2}\|(h_{p}^{(l)})^{T}-(1-\gamma)^{2}(H^{(l)})^{T}R\|_{2}\\\
&+\frac{\gamma(1-\gamma)}{\beta_{1}+\beta_{2}}\|h_{i}^{(0)}-h_{j}^{(0)}\|_{2}\|(h_{p}^{(l)})^{T}-(1-\gamma)^{2}(H^{(l)})^{T}R\|_{2}\\\
&+\frac{\beta_{2}(1-\gamma)^{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}\|\hat{a}_{i}^{k}-\hat{a}_{j}^{k}\|_{2}\|R\|_{2}\\\
&+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}|\hat{A}_{{ip}}^{k}-\hat{A}_{{jp}}^{k}|\\\
\end{split}$

where
$R=\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}H^{(l)}(h_{p}^{(l)})^{T}$.

######  Lemma 4.3.

$\forall 1\leq i,j,p\leq n$,

$|Z_{pi}^{(l)*}-Z_{pj}^{(l)*}|\leq\frac{\eta(1-\gamma)\lVert
h_{i}^{(l)}-h_{j}^{(l)}\rVert_{2}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}|\hat{A}_{{pi}}^{k}-\hat{A}_{{pj}}^{k}|}{\beta_{1}+\beta_{2}}$

where $\eta=\sqrt{\lVert{h}_{p}^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}^{2}+\beta_{2}\lVert\sum_{k=1}^{K}\lambda_{k}\hat{a}_{p}^{k}\rVert_{2}^{2}}$.

######  Lemma 4.4.

Matrices $Z^{(l)*}$, $(Z^{(l)*})^{T}$ and $H^{(l+1)}$ all have grouping
effect.

The grouping effect of $Z^{(l)*}$, $(Z^{(l)*})^{T}$ and $H^{(l+1)}$ indeed
explains the effectiveness of our model. In fact, for any two nodes $v_{i}$
and $v_{j}$, no matter how distant they are in a graph, if they share similar
feature vectors and local structures, we conclude that (1) they will be given
similar coefficient vectors; (2) they will play similar roles in
characterizing other nodes; and (3) they will be given similar representation
vectors. On the other hand, in graphs with heterophily, adjacent nodes are
more likely to be dissimilar and they will thus be given different embeddings.
Further, for two nodes with low feature similarity, using one to characterize
the other can be enhanced by the regularization term of local graph structure,
if they share high structural similarity. This also applies to nodes that have
high feature similarity but low structural similarity. After $L$ convolutional
layers, we derive $H^{(L)}$. We then normalize $H^{(L)}$ by a Softmax layer,
whose results are further fed into the Cross-entropy function for
classification. Finally, we summarize the pseudocodes of GloGNN in Algorithm 1
(Section A of the appendix).

###  4.4 GloGNN++

Given $H^{l}$, the coefficient matrix $Z^{(l)*}$ in Equation 6 plays the role
of “longitudinal” attention that characterizes the importance of a node to
another. In neighborhood aggregation, not only varies the importance of a
node’s neighbors, but also that of hidden features. For example, in node
classification, the imbalance of node labels could lead to the various
importance of hidden features corresponding to different labels. Therefore, we
further upgrade our model by considering “horizontal” attention w.r.t. hidden
features. We introduce a diagonal matrix $\Sigma\in\mathbb{R}^{c\times c}$
such that $\Sigma_{ii}$ describes the importance of the $i$-th dimension in
$H^{(l)}$. We modify Equation 5 into:

$\scriptsize\min_{Z^{(l)}}||H^{(l)}-(1-\gamma)Z^{(l)}H^{(l)}\Sigma-\gamma
H^{(0)}||_{F}^{2}+\beta_{1}\|Z^{(l)}\|_{F}^{2}+\beta_{2}||Z^{(l)}-\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}||_{F}^{2},$
(10)

and derive the optimal solution $Z^{(l)*}$:

$\scriptsize\begin{split}Z^{(l)*}=&\left[(1-\gamma)H^{(l)}\Sigma(H^{(l)})^{T}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}-\gamma(1-\gamma)H^{(0)}\Sigma(H^{(l)})^{T}\right]\cdot\\\
&\left[(1-\gamma)^{2}H^{(l)}\Sigma\Sigma(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}\\\
\end{split}$

Following the same procedure in Sec. 4.2 and 4.3, we can also accelerate
neighborhood aggregation and further prove that such $Z^{(l)*}$,
$(Z^{(l)*})^{T}$ and $H^{(l+1)}$ have the desired grouping effect. We omit the
details due to the space limitation.

###  4.5 Discussion

We next discuss the major differences between our models and the adapted GAT
model that takes global nodes as a node’s neighbors. First, the attention
weights in GAT are automatically learned and lack of interpretability, but
$Z^{(l)}$ in our models is derived from a well-designed optimization problem
and has a closed-form solution. Second, the attention weights in GAT are
always non-negative values while $Z^{(l)}$ in our methods allows signed
values. Therefore, GAT only employs low-pass convolutional filters while our
methods combine both low-pass and high-pass filters. Third, for each node, the
neighborhood aggregation performed by GAT over all the nodes in the graph is
computationally expensive, which has a quadratic time complexity w.r.t. the
number of nodes. However, our methods accelerate the aggregation and derive a
linear time complexity.

##  5 Experiments

In this section, we comprehensively evaluate the performance of GloGNN and
GloGNN++. In particular, we compare them with 11 other methods on 15 benchmark
datasets, to show the effectiveness and efficiency of our models. Due to the
space limitation, we move experimental setup (Sec. E) and ablation study (Sec.
F) to the appendix.

###  5.1 Datasets

For fairness, we conduct experiments on 15 benchmark datasets, which include 9
small-scale datasets released by (Pei et al., 2020) and 6 large-scale datasets
from (Lim et al., 2021). We use the same training/validation/test splits as
provided by the original papers. In particular, these datasets span various
domains, scales and graph heterophilies. The statistics of these datasets are
summarized in Tables 1 and 2. Details on these datasets can be found in
Section B of the appendix.

Table 1: The classification accuracy (%) over the methods on 9 small-scale
datasets released in (Pei et al., 2020). The error bar ($\pm$) denotes the
standard deviation score of results over 10 trials. We highlight the best
score on each dataset in bold and the runner-up score with underline. Note
that Edge Hom. (Zhu et al., 2020b) is defined as the fraction of edges that
connect nodes with the same label.

| Texas | Wisconsin | Cornell | Actor | Squirrel | Chameleon | Cora | Citeseer | Pubmed |  Avg. Rank
---|---|---|---|---|---|---|---|---|---|---
Edge Hom. | 0.11 | 0.21 | 0.30 | 0.22 | 0.22 | 0.23 | 0.81 | 0.74 | 0.80
#Nodes | 183 | 251 | 183 | 7,600 | 5,201 | 2,277 | 2,708 | 3,327 | 19,717
#Edges | 295 | 466 | 280 | 26,752 | 198,493 | 31,421 | 5,278 | 4,676 | 44,327
#Features | 1,703 | 1,703 | 1,703 | 931 | 2,089 | 2,325 | 1,433 | 3,703 | 500
#Classes | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 3 |
MLP | $80.81\pm 4.75$ | $85.29\pm 3.31$ | $81.89\pm 6.40$ | $36.53\pm 0.70$ | $28.77\pm 1.56$ | $46.21\pm 2.99$ | $75.69\pm 2.00$ | $74.02\pm 1.90$ | $87.16\pm 0.37$ | 9.72
GCN | $55.14\pm 5.16$ | $51.76\pm 3.06$ | $60.54\pm 5.30$ | $27.32\pm 1.10$ | $53.43\pm 2.01$ | $64.82\pm 2.24$ | $86.98\pm 1.27$ | $76.50\pm 1.36$ | $88.42\pm 0.50$ | 10.22
GAT | $52.16\pm 6.63$ | $49.41\pm 4.09$ | $61.89\pm 5.05$ | $27.44\pm 0.89$ | $40.72\pm 1.55$ | $60.26\pm 2.50$ | $87.30\pm 1.10$ | $76.55\pm 1.23$ | $86.33\pm 0.48$ | 11.11
MixHop | $77.84\pm 7.73$ | $75.88\pm 4.90$ | $73.51\pm 6.34$ | $32.22\pm 2.34$ | $43.80\pm 1.48$ | $60.50\pm 2.53$ | $87.61\pm 0.85$ | $76.26\pm 1.33$ | $85.31\pm 0.61$ | 10.11
GCNII | $77.57\pm 3.83$ | $80.39\pm 3.40$ | $77.86\pm 3.79$ | $37.44\pm 1.30$ | $38.47\pm 1.58$ | $63.86\pm 3.04$ | $\bm{88.37\pm 1.25}$ | $\underline{77.33\pm 1.48}$ | $\bm{90.15\pm 0.43}$ | 5.89
H2GCN | ${84.86\pm 7.23}$ | ${87.65\pm 4.98}$ | $82.70\pm 5.28$ | $35.70\pm 1.00$ | $36.48\pm 1.86$ | $60.11\pm 2.15$ | $87.87\pm 1.20$ | $77.11\pm 1.57$ | $89.49\pm 0.38$ | 6.72
WRGAT | $83.62\pm 5.50$ | ${86.98\pm 3.78}$ | $81.62\pm 3.90$ | $36.53\pm 0.77$ | $48.85\pm 0.78$ | $65.24\pm 0.87$ | $88.20\pm 2.26$ | $76.81\pm 1.89$ | $88.52\pm 0.92$ | 6.17
GPR-GNN | $78.38\pm 4.36$ | $82.94\pm 4.21$ | $80.27\pm 8.11$ | $34.63\pm 1.22$ | $31.61\pm 1.24$ | $46.58\pm 1.71$ | $87.95\pm 1.18$ | $77.13\pm 1.67$ | $87.54\pm 0.38$ | 8.83
GGCN | $\underline{84.86\pm 4.55}$ | $86.86\pm 3.29$ | $\underline{85.68\pm 6.63}$ | $\underline{37.54\pm 1.56}$ | $55.17\pm 1.58$ | $\underline{71.14\pm 1.84}$ | $87.95\pm 1.05$ | $77.14\pm 1.45$ | $89.15\pm 0.37$ | 3.89
ACM-GCN | $\bm{87.84\pm 4.40}$ | $\bm{88.43\pm 3.22}$ | $85.14\pm 6.07$ | $36.28\pm 1.09$ | $54.40\pm 1.88$ | $66.93\pm 1.85$ | $87.91\pm 0.95$ | $77.32\pm 1.70$ | $\underline{90.00\pm 0.52}$ | 3.78
LINKX | $74.60\pm 8.37$ | $75.49\pm 5.72$ | $77.84\pm 5.81$ | $36.10\pm 1.55$ | $\bm{61.81\pm 1.80}$ | $68.42\pm 1.38$ | $84.64\pm 1.13$ | $73.19\pm 0.99$ |  $87.86\pm$ 0.77 | 8.78
GloGNN | $84.32\pm 4.15$ | $87.06\pm 3.53$ | $83.51\pm 4.26$ | $37.35\pm 1.30$ | $57.54\pm 1.39$ | ${69.78\pm 2.42}$ | $88.31\pm 1.13$ | $\bm{77.41\pm 1.65}$ | ${89.62\pm 0.35}$ | $\underline{3.22}$
GloGNN++ | $84.05\pm 4.90$ | $\underline{88.04\pm 3.22}$ | $\bm{85.95\pm 5.10}$ | $\bm{37.70\pm 1.40}$ | $\underline{57.88\pm 1.76}$ | $\bm{71.21\pm 1.84}$ | $\underline{88.33\pm 1.09}$ | $77.22\pm 1.78$ | $89.24\pm 0.39$ | $\bm{2.56}$

Table 2: The classification results (%) over the methods on 6 large-scale
datasets released in (Lim et al., 2021). Note that we compare the AUC score on
genius as in (Lim et al., 2021). For other datasets, we show the
classification accuracy. The error bar ($\pm$) denotes the standard deviation
score of results over 5 trials. We highlight the best score on each dataset in
bold and the runner-up score with underline. Note that OOM refers to the out-
of-memory error.

| Penn94 | pokec | arXiv-year | snap-patents | genius | twitch-gamers |  Avg. Rank
---|---|---|---|---|---|---|---
Edge Hom. | 0.47 | 0.44 | 0.22 | 0.07 | 0.61 | 0.54
#Nodes | 41,554 | 1,632,803 | 169,343 | 2,923,922 | 421,961 | 168,114
#Edges | 1,362,229 | 30,622,564 | 1,166,243 | 13,975,788 | 984,979 | 6,797,557
#Features | 5 | 65 | 128 | 269 | 12 | 7
#Classes | 2 | 2 | 5 | 5 | 2 | 2 |
MLP | $73.61\pm 0.40$ | $62.37\pm 0.02$ | $36.70\pm 0.21$ | $31.34\pm 0.05$ | $86.68\pm 0.09$ | $60.92\pm 0.07$ | 10.00
GCN | $82.47\pm 0.27$ | $75.45\pm 0.17$ | $46.02\pm 0.26$ | $45.65\pm 0.04$ | $87.42\pm 0.37$ | $62.18\pm 0.26$ | 7.00
GAT | $81.53\pm 0.55$ | $71.77\pm 6.18$ | $46.05\pm 0.51$ | $45.37\pm 0.44$ | $55.80\pm 0.87$ | $59.89\pm 4.12$ | 8.50
MixHop | $83.47\pm 0.71$ | $81.07\pm 0.16$ | $51.81\pm 0.17$ | $52.16\pm 0.09$ | $90.58\pm 0.16$ | $65.64\pm 0.27$ | 4.17
GCNII | $82.92\pm 0.59$ | $78.94\pm 0.11$ | $47.21\pm 0.28$ | $37.88\pm 0.69$ | $90.24\pm 0.09$ | $63.39\pm 0.61$ | 6.00
H2GCN | $81.31\pm 0.60$ | OOM | $49.09\pm 0.10$ | OOM | OOM | OOM | 10.50
WRGAT | $74.32\pm 0.53$ | OOM | OOM | OOM | OOM | OOM | 11.92
GPR-GNN | $81.38\pm 0.16$ | $78.83\pm 0.05$ | $45.07\pm 0.21$ | $40.19\pm 0.03$ | $90.05\pm 0.31$ | $61.89\pm 0.29$ | 7.83
GGCN | OOM | OOM | OOM | OOM | OOM | OOM | 12.25
ACM-GCN | $82.52\pm 0.96$ | $63.81\pm 5.20$ | $47.37\pm 0.59$ | $55.14\pm 0.16$ | $80.33\pm 3.91$ | $62.01\pm 0.73$ | 6.83
LINKX | $84.71\pm 0.52$ | $82.04\pm 0.07$ | $\bm{56.00\pm 1.34}$ | $61.95\pm 0.12$ | $\underline{90.77\pm 0.27}$ | $66.06\pm 0.19$ | 2.50
GloGNN | $\underline{85.57\pm 0.35}$ | $\underline{83.00\pm 0.10}$ | $\underline{54.68\pm 0.34}$ | $\bm{62.09\pm 0.27}$ | $90.66\pm 0.11$ | $\underline{66.19\pm 0.29}$ | 2.17
GloGNN++ | $\bm{85.74\pm 0.42}$ | $\bm{83.05\pm 0.07}$ | $54.79\pm 0.25$ | $\underline{62.03\pm 0.21}$ | $\bm{90.91\pm 0.13}$ | $\bm{66.34\pm 0.29}$ | 1.33

###  5.2 Algorithms for comparison

We compare GloGNN and GloGNN++ with 11 other baselines, including (1) MLP; (2)
general GNN methods: GCN (Kipf & Welling, 2016), GAT (Veličković et al.,
2017), MixHop (Abu-El-Haija et al., 2019) and GCNII (Chen et al., 2020); (3)
heterophilous-graph-oriented methods: H2GCN (Zhu et al., 2020b), WRGAT (Suresh
et al., 2021), GPR-GNN (Chien et al., 2020), GGCN (Yan et al., 2021), ACM-GCN
(Luan et al., 2021) and LINKX (Lim et al., 2021). For these methods specially
designed for heterophilous graphs, LINKX is a MLP-based method while others
are GNN models. Further, although several ACM-variants are proposed in (Luan
et al., 2021), ACM-GCN is reported to achieve the overall best performance on
the same splits of benchmark datasets from (Pei et al., 2020), so we choose it
as the baseline. For other models like Geom-GCN (Pei et al., 2020) and FAGCN
(Bo et al., 2021), since they have been shown to be outperformed by the state-
of-the-arts, we exclude their results in our paper.

###  5.3 Performance results

Tables 1 and 2 summarize the performance results of all the methods on 15
benchmark datasets. Note that we compare the AUC score on genius as in (Lim et
al., 2021). For other datasets, we show the results of classification
accuracy. Each column in the tables corresponds to one dataset. For each
dataset, we highlight the winner’s score in bold and the runner-up’s with
underline. From the tables, we make the following observations:

(1) MLP that uses only node features performs surprisingly well on some
datasets with large heterophily, such as Actor. This shows the importance of
node features for node classification in heterophilous graphs.

(2) Compared with the plain GNN models GCN and GAT, MixHop and GCNII generally
perform better. For example, on Wisconsin, the accuracy scores of MixHop and
GCNII are $0.7588$ and $0.8039$, respectively, which significantly outperform
that of GCN and GAT. On the one hand, MixHop amplifies a node’s neighborhood
with its multi-hop neighbors. This introduces more homophilous neighbors for
the node. On the other hand, the initial residual and identity mapping
mechanisms in GCNII implicitly combine intermediate node representations to
boost the model performance.

(3) Although H2GCN, WRGAT and GGCN can achieve good performance on small-scale
datasets, they fail to run on very large-scale datasets due to the out-of-
memory (OOM) error. This hinders the wide application of these models. For
ACM-GCN and LINKX, they cannot consistently provide superior results. For
example, LINKX ranks third on large-scale datasets, but performs poorly on
small-scale ones (rank 8th). ACM-GCN is the winner on Texas, but its accuracy
score on pokec is only $0.6381$ (the best result is $0.8305$). While GPR-GNN
leverages both low-pass and high-pass filters, it only utilizes one type of
convolutional filters in each layer, which restricts its effectiveness.

(4) GloGNN++ achieves the first average rank over all the datasets while
GloGNN is the runner-up. This shows that both of them can consistently provide
superior results on datasets in a wide range of diversity. On the one hand,
both methods learn to utilize more neighbors with homophily for node
neighborhood aggregation. This boosts the model performance. On the other
hand, GloGNN++ further learns the importance of hidden features of nodes,
which improves the classification accuracy.

###  5.4 Efficiency study

In this section, we study GloGNN’s efficiency. For fairness, we compare the
training time for methods that are specially designed for graphs with
heterophily. In particular, we make the comparison on the large-scale datasets
for better efficiency illustration. For all these methods, we use the same
training set on each dataset and run the experiments for 500 epochs. We repeat
the experiments three times and show the average training time of these
methods w.r.t. accuracy/AUC scores on the validation set in Figure 3. Note
that due to the OOM error, GGCN fails to run on these datasets and we exclude
it for comparison. We also drop WRGAT because it takes long time to precompute
the multi-relational graph. For example, with default hyper-parameter
settings, WRGAT takes around $3200$ seconds to compute the multi-relational
graph of Penn94 on a server with 48 CPUs. However, the runs of all other
models that perform on the original graph are finished within the period. We
next recap the major difference of these methods: all the methods except LINKX
are GNN models. Specifically, for each node, ACM-GCN and GPR-GNN perform
convolution directly from its adjacent neighbors while H2GCN, GloGNN and
GloGNN++ amplify the neighborhood of the node. Here, H2GCN considers multi-hop
neighbors in the node’s neighborhood while both GloGNN and GloGNN++ employ the
whole set of nodes in the graph. Compared with GloGNN, GloGNN++ further
incorporates an attention mechanism to learn the importance of node hidden
features. Finally, LINKX is a simple MLP-based model that does not include the
graph convolution operation.

(a) arXiv-year (b) Penn94 (c) genius (d) pokec (e) snap-patents (f) twitch-
gamers

Figure 3: Efficiency study: x-axis shows the training time and y-axis is the
accuracy/AUC score on the validation set.

From Fig. 3, we see that GloGNN and GloGNN++ converge very fast to the
best/runner-up results over all the datasets. While GPR-GNN runs faster, it
generally performs poorly. For LINKX, the MLP-based model structure instead of
GNN-based explains its scalability. However, the 8th-ranked accuracy score on
datasets in Table 1 restricts its wide usage. For H2GCN and ACM-GCN, they are
slower than GloGNN and GloGNN++. For example, GloGNN++ achieves almost
$8\times$ speedup than ACM-GCN on genius; it is also $2\times$ faster than
H2GCN on Penn94. These results show that GloGNN and GloGNN++ are highly
effective and also efficient; hence they can be widely applied to large-scale
datasets.

###  5.5 Grouping effect

Lemma 4.4 shows that both the coefficient matrix $Z^{*}$ and the node
embedding matrix $H$ have the desired grouping effect. Considering the dataset
size for clear illustration, we choose Texas, Wisconsin and Cornell as
representatives to show the grouping effect of $Z^{*}$ in Figure 4 (a)-(c).
All these datasets contain nodes in five labels. In each sub-figure, rows and
columns are reordered by ground-truth labels. We use red and blue to indicate
positive and negative values, respectively. We further use pixel color
brightness to show the positive/negative degree of a value. The brighter a
pixel, the larger the degree. From the figures, the matrix exhibits the well-
defined block diagonal structure. This shows the grouping effect of $Z^{*}$.
For Texas and Cornell, we see only four blocks along the diagonal. This is
because in both datasets, there exists one object class that includes only one
node. Similarly, Figure 4 (d)-(f) further show the grouping effect of the
output node embedding matrix $H$ on these datasets. We reorder columns by
gold-standard classes. Each column in the matrix corresponds to a node’s
embedding vector. For nodes in the same class, their embedding vectors are
close to each other. This further explains the superior performance of our
models.

(a) Texas (b) Wisconsin (c) Cornell (d) Texas (e) Wisconsin (f) Cornell

Figure 4: The grouping effect of $Z^{*}$ (a)-(c) and $H$ (d)-(f) on Texas,
Wisconsin and Cornell (better view in color).

###  5.6 Global homophily

We end this section with a study to show how GloGNN finds global homophily for
nodes in the graph. Given a graph, we first calculate the average number of
$k$-hop neighbors that share the same label with a node. We further inspect
the average number of positive $Z^{*}$ values for these neighbors. After that,
we compare the results on 6 graphs with large heterophily in Figure 5. We see
that for each node in these datasets, the average number of adjacent neighbors
in the same class is less than that of multi-hop ones (2-hop to 6-hop). There
also exist many $>6$-hop neighbors that can be used to predict a node’s label.
This necessitates jumping the locality of a node and finding its global
homophily. Further, for each node, our model GloGNN can correctly assign
positive values to the global nodes in the same class, including both adjacent
neighbors and those that are distant. This also explains the effectiveness of
our models.

(a) Texas (b) Wisconsin (c) Cornell (d) Actor (e) Squirrel (f) Chameleon

Figure 5: Global homophily study

##  6 Conclusions

In this paper, we generalized GNNs to graphs with heterophily. We proposed
GloGNN and GloGNN++, which generate a node’s embedding by aggregating
information from global nodes in the graph. In each layer, we formulated an
optimization problem to derive a coefficient matrix $Z$ that describes the
relationships between nodes. Neighborhood aggregation is then performed based
on $Z$. We accelerated the aggregation process by matrix multiplication
reordering without explicitly calculating $Z$. We mathematically proved that
both $Z$ and the generated node embedding matrix $H$ have the desired grouping
effect, which explains the model effectiveness. We conducted extensive
experiments to evaluate the performance of our models. Experimental results
show that our methods performs favorably against other 11 competitors over 15
datasets of diverse heterophilies; they are also efficient and converge very
fast.

## References

  * Abu-El-Haija et al. (2019) Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Galstyan, A.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing.  In _ICML_ , pp. 21–29. PMLR, 2019.
  * Bo et al. (2021) Bo, D., Wang, X., Shi, C., and Shen, H.  Beyond low-frequency information in graph convolutional networks.  _arXiv preprint arXiv:2101.00797_ , 2021.
  * Bruna et al. (2013) Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y.  Spectral networks and locally connected networks on graphs.  _arXiv preprint arXiv:1312.6203_ , 2013.
  * Chen et al. (2020) Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y.  Simple and deep graph convolutional networks.  In _ICML_ , pp. 1725–1735. PMLR, 2020.
  * Chien et al. (2020) Chien, E., Peng, J., Li, P., and Milenkovic, O.  Adaptive universal generalized pagerank graph neural network.  _arXiv preprint arXiv:2006.07988_ , 2020.
  * Ciotti et al. (2016) Ciotti, V., Bonaventura, M., Nicosia, V., Panzarasa, P., and Latora, V.  Homophily and missing links in citation networks.  _EPJ Data Science_ , 5:1–14, 2016.
  * Dai et al. (2018) Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., and Song, L.  Adversarial attack on graph structured data.  In _ICML_ , pp. 1115–1124. PMLR, 2018.
  * Defferrard et al. (2016) Defferrard, M., Bresson, X., and Vandergheynst, P.  Convolutional neural networks on graphs with fast localized spectral filtering.  _NeurIPS_ , 29:3844–3852, 2016.
  * Dong et al. (2021) Dong, Y., Ding, K., Jalaian, B., Ji, S., and Li, J.  Graph neural networks with adaptive frequency response filter.  _arXiv preprint arXiv:2104.12840_ , 2021.
  * Gerber et al. (2013) Gerber, E. R., Henry, A. D., and Lubell, M.  Political homophily and collaboration in regional planning networks.  _American Journal of Political Science_ , 57(3):598–610, 2013.
  * Hamilton et al. (2017) Hamilton, W. L., Ying, R., and Leskovec, J.  Inductive representation learning on large graphs.  In _NeurIPS_ , pp. 1025–1035, 2017.
  * Kipf & Welling (2016) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Klicpera et al. (2018) Klicpera, J., Bojchevski, A., and Günnemann, S.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ , 2018.
  * Li et al. (2020) Li, X., Kao, B., Shan, C., Yin, D., and Ester, M.  Cast: A correlation-based adaptive spectral clustering algorithm on multi-scale data.  In _KDD_ , pp. 439–449, 2020.
  * Lim et al. (2021) Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N.  Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.  _NeurIPS_ , 34, 2021.
  * Liu et al. (2012) Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., and Ma, Y.  Robust recovery of subspace structures by low-rank representation.  _TPAMI_ , 35(1):171–184, 2012.
  * Liu et al. (2020) Liu, M., Gao, H., and Ji, S.  Towards deeper graph neural networks.  In _KDD_ , pp. 338–348, 2020.
  * Liu et al. (2021) Liu, M., Wang, Z., and Ji, S.  Non-local graph neural networks.  _TPAMI_ , 2021.
  * Lu et al. (2012) Lu, C.-Y., Min, H., Zhao, Z.-Q., Zhu, L., Huang, D.-S., and Yan, S.  Robust and efficient subspace segmentation via least squares regression.  In _ECCV_ , pp. 347–360, 2012.
  * Luan et al. (2021) Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D.  Is heterophily a real nightmare for graph neural networks to do node classification?  _arXiv preprint arXiv:2109.05641_ , 2021.
  * Max (1950) Max, A. W.  Inverting modified matrices.  In _Memorandum Rept. 42, Statistical Research Group_ , pp. 4. Princeton Univ., 1950.
  * McPherson et al. (2001) McPherson, M., Smith-Lovin, L., and Cook, J. M.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ , 27(1):415–444, 2001.
  * Pei et al. (2020) Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ , 2020.
  * Rong et al. (2019) Rong, Y., Huang, W., Xu, T., and Huang, J.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_ , 2019.
  * Shan et al. (2021) Shan, C., Shen, Y., Zhang, Y., Li, X., and Li, D.  Reinforcement learning enhanced explainer for graph neural networks.  _NeurIPS_ , 34, 2021.
  * Suresh et al. (2021) Suresh, S., Budde, V., Neville, J., Li, P., and Ma, J.  Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns.  In _KDD_ , pp. 1541–1551, 2021.
  * Tang et al. (2009) Tang, J., Sun, J., Wang, C., and Yang, Z.  Social influence analysis in large-scale networks.  In _KDD_ , pp. 807–816, 2009.
  * Veličković et al. (2017) Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Vu & Thai (2020) Vu, M. N. and Thai, M. T.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  _arXiv preprint arXiv:2010.05788_ , 2020.
  * Yan et al. (2021) Yan, Y., Hashemi, M., Swersky, K., Yang, Y., and Koutra, D.  Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks.  _arXiv preprint arXiv:2102.06462_ , 2021.
  * Yang et al. (2021) Yang, Y., Liu, T., Wang, Y., Zhou, J., Gan, Q., Wei, Z., Zhang, Z., Huang, Z., and Wipf, D.  Graph neural networks inspired by classical iterative algorithms.  _arXiv preprint arXiv:2103.06064_ , 2021.
  * Zhao & Akoglu (2019) Zhao, L. and Akoglu, L.  Pairnorm: Tackling oversmoothing in gnns.  _arXiv preprint arXiv:1909.12223_ , 2019.
  * Zhu et al. (2019) Zhu, D., Zhang, Z., Cui, P., and Zhu, W.  Robust graph convolutional networks against adversarial attacks.  In _KDD_ , pp. 1399–1407, 2019.
  * Zhu et al. (2020a) Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D.  Graph neural networks with heterophily.  _arXiv preprint arXiv:2009.13566_ , 2020a.
  * Zhu et al. (2020b) Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _arXiv preprint arXiv:2006.11468_ , 2020b.

##  Appendix A Pseudocodes

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and a label set
$\mathcal{C}$ with $|\mathcal{C}|=c$, let
$\mathcal{V}=\mathcal{L}\cup\mathcal{U}$, where $\mathcal{L}$ is a set of
labeled objects and $\mathcal{U}$ is a set of unlabeled ones, the node
classification problem is to learn a mapping $\psi$:
$\mathcal{V}\rightarrow\mathcal{C}$ to predict the labels of nodes in
$\mathcal{U}$. We next summarize the pseudocodes of GloGNN as follows.

Algorithm 1 GloGNN

1: Input: $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
$\mathcal{V}=\mathcal{L}\cup\mathcal{U}$, $A$, $X$, $L$, $\mathcal{C}$,
$Y_{\mathcal{L}}$

2: Output: the label matrix $Y_{\mathcal{U}}$ of unlabeled nodes

3: Calculate $H_{X}^{(0)}$ and $H_{A}^{(0)}$ by Eq. 2

4: Calculate $H^{(0)}$ by Eq. 3

5: for $l\leftarrow 0$ to $L-1$ do

6: Calculate $Q^{(l+1)}$ by Eq. 8

7: Calculate $H^{(l+1)}$ by Eq. 7

8: end for

9: Normalize $H^{(L)}$ with the Softmax function and feed the results into the
Cross-entropy function

10: Optimize the objective function to update weight matrices

11: Return: $Y_{\mathcal{U}}$

##  Appendix B Datasets

We first use 9 small-scale datasets from (Pei et al., 2020) and divide them
into the following four categories:

$\bullet$ [Citation network]. _Cora_ , _Citeseer_ and _Pubmed_ are citation
graphs, where each node represents a scientific paper. These graphs use bag-
of-words representations as the feature vectors of nodes. Each node is
assigned a label indicating the research field. Note that these three datasets
are homophilous graphs.

$\bullet$ [WebKB]. _Texas_ , _Wisconsin_ and _Cornell_ are web page datasets
collected from computer science departments of various universities. In these
datasets, nodes are web pages and edges represent hyperlinks between them. We
take bag-of-words representations as nodes’ feature vectors. The task is to
classify the web pages into five categories including _student_ , _project_ ,
_course_ , _staff_ and _faculty_.

$\bullet$ [Actor co-occurrence network]. _Actor_ is a graph induced from the
film-director-actor-writer network in (Tang et al., 2009), which describes the
co-occurrence relation between actors in Wikipedia pages. Node features are
constructed by keywords contained in the Wikipedia pages of actors. The task
is to classify actors into five categories.

$\bullet$ [Wikipedia network]. _Squirrel_ and _Chameleon_ are two subgraphs of
web pages in Wikipedia. Our task is to classify nodes into five categories
based on their average amounts of monthly traffic.

To further show the effectiveness and efficiency of our models, we also use 6
large-scale datasets released by (Lim et al., 2021):

$\bullet$ [Social network]. _Penn94_ is a subgraph extracted from Facebook
whose nodes are students. Node features include major, second major/minor,
dorm/house, year and high school. We take students’ genders as nodes’ labels.
_Pokec_ is a friendship network from a Slovak online social network, whose
nodes are users and edges represent directed friendship relations. We
construct node features from users’ profiles, such as geographical region,
registration time, age. The task is to classify users based on their genders.
_genius_ is a subnetwork extracted from genius.com, which is a website for
crowdsourced annotations of song lyrics. In the graph, nodes are users and
edges connect users that follow each other. User features include expertise
scores, counts of contributions, roles held by users, etc. Some users are
marked with a “gone” label on the site, which are more likely to be spam
users. Our goal is to predict whether a user is marked with “gone”. _twitch-
gamers_ is a subgraph from the streaming platform Twitch, where nodes are
users and edges connect mutual followers. Node features include the number of
views, the creation and update dates, language, life time and whether the
account is dead. The task is to predict whether the channel has explicit
content.

$\bullet$ [Citation network]. _arXiv-year_ is a directed subgraph of ogbn-
arXiv, where nodes are arXiv papers and edges represent the citation
relations. We construct node features by taking the averaged word2vec
embedding vectors of tokens contained in both the title and abstract of
papers. The task is to classify these papers into five labels that are
constructed based on their posting year. _snap-patents_ is a US patent network
whose nodes are patents and edges are citation relations. Node features are
constructed from patent metadata. Our goal is to classify the patents into
five labels based on the time when they were granted.

##  Appendix C Aggregation acceleration

To accelerate the updates of $H^{(l+1)}$ in Equation 6, we first follow the
Woodbury formula (Max, 1950) to derive

$\begin{split}&\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}\\\
&=\frac{1}{\beta_{1}+\beta_{2}}I_{n}-\frac{1}{(\beta_{1}+\beta_{2})^{2}}H^{(l)}\left[\frac{1}{(1-\gamma)^{2}}I_{c}+\frac{1}{\beta_{1}+\beta_{2}}(H^{(l)})^{T}H^{(l)}\right]^{-1}(H^{(l)})^{T}\\\
\end{split}$ (11)

After that, based on Eq. 4.1 and Eq. LABEL:eq:inverse, we can easily transform
Eq. 6 into Eq. 7.

##  Appendix D Proof

In this section, we prove Lemma 4.2, Lemma 4.3 and Lemma 4.4, respectively. In
the following discussion, we use $z_{i}^{(l)*}$ to denote the $i$-th row of
$Z^{(l)*}$, which is the coefficient vector for representing node $v_{i}$; we
denote $\hat{a}_{i}^{k}$ as the $i$-th row of $\hat{A}^{k}$, which represents
$v_{i}$’s $k$-hop node reachability in a graph. We first consider Lemma D.1:

######  Lemma D.1.

$\forall 1\leq i,p\leq n$, the optimal solution $Z^{(l)*}$ in Eq. 5 satisfies

$Z_{ip}^{(l)*}=\frac{(1-\gamma)[{h}_{i}^{(l)}-(1-\gamma)z_{i}^{(l)*}H^{(l)}-\gamma
h_{i}^{(0)}](h_{p}^{(l)})^{T}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{A}_{{ip}}^{k}}{\beta_{1}+\beta_{2}}.$
(12)

###### Proof.

For $1\leq i\leq n$, we define
$J(z_{i}^{(l)})=\|{h}_{i}^{(l)}-(1-\gamma)z_{i}^{(l)}H^{(l)}-\gamma
h_{i}^{(0)}\|_{2}^{2}+\beta_{1}\|z_{i}^{(l)}\|_{2}^{2}+\beta_{2}\|z_{i}^{(l)}-\sum_{k=1}^{K}\lambda_{k}\hat{a}_{i}^{k}\|_{2}^{2}$.
Since $Z^{(l)*}$ is the optimal solution of Equation 5, we have
$\frac{\partial{J}}{\partial{Z}_{ip}^{(l)}}|_{{z}_{i}^{(l)}={z}_{i}^{(l)*}}=0,\
\forall 1\leq p\leq n$. We take the derivative and get
$-(1-\gamma)[{h}_{i}^{(l)}-(1-\gamma)z_{i}^{(l)*}H^{(l)}-\gamma
h_{i}^{(0)}](h_{p}^{(l)})^{T}+\beta_{1}Z_{ip}^{(l)*}+\beta_{2}(Z_{ip}^{(l)*}-\sum_{k=1}^{K}\lambda_{k}\hat{A}_{{ip}}^{k})=0$,
which induces Eq. 12. ∎

Based on Lemma D.1, we first prove Lemma 4.2:

###### Proof.

From Equation 12, we get

$\begin{split}Z_{ip}^{(l)*}-Z_{jp}^{(l)*}&=\frac{1-\gamma}{\beta_{1}+\beta_{2}}({h}_{i}^{(l)}-{h}_{j}^{(l)})(h_{p}^{(l)})^{T}-\frac{(1-\gamma)^{2}}{\beta_{1}+\beta_{2}}(z_{i}^{(l)*}-z_{j}^{(l)*})H^{(l)}(h_{p}^{(l)})^{T}\\\
&-\frac{\gamma(1-\gamma)}{\beta_{1}+\beta_{2}}(h_{i}^{(0)}-h_{j}^{(0)})(h_{p}^{(l)})^{T}+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}(\hat{A}_{{ip}}^{k}-\hat{A}_{{jp}}^{k})\\\
\end{split}$ (13)

Since

$\begin{split}z_{i}^{(l)*}=&\left[(1-\gamma)h_{i}^{(l)}(H^{(l)})^{T}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{a}_{i}^{k}-\gamma(1-\gamma)h_{i}^{(0)}(H^{(l)})^{T}\right]\cdot\\\
&\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}\\\
\end{split}$ (14)

and

$\begin{split}z_{j}^{(l)*}=&\left[(1-\gamma)h_{j}^{(l)}(H^{(l)})^{T}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}\hat{a}_{j}^{k}-\gamma(1-\gamma)h_{j}^{(0)}(H^{(l)})^{T}\right]\cdot\\\
&\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}\\\
\end{split}$ (15)

let
$R=\left[(1-\gamma)^{2}H^{(l)}(H^{(l)})^{T}+(\beta_{1}+\beta_{2})I_{n}\right]^{-1}H^{(l)}(h_{p}^{(l)})^{T}$
and we derive

$\begin{split}Z_{ip}^{(l)*}-Z_{jp}^{(l)*}&=\frac{1-\gamma}{\beta_{1}+\beta_{2}}({h}_{i}^{(l)}-{h}_{j}^{(l)})(h_{p}^{(l)})^{T}-\frac{(1-\gamma)^{3}}{\beta_{1}+\beta_{2}}(h_{i}^{(l)}-h_{j}^{(l)})(H^{(l)})^{T}R\\\
&-\frac{\beta_{2}(1-\gamma)^{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}(\hat{a}_{i}^{k}-\hat{a}_{j}^{k})R+\frac{\gamma(1-\gamma)^{3}}{\beta_{1}+\beta_{2}}(h_{i}^{(0)}-h_{j}^{(0)})(H^{(l)})^{T}R\\\
&-\frac{\gamma(1-\gamma)}{\beta_{1}+\beta_{2}}(h_{i}^{(0)}-h_{j}^{(0)})(h_{p}^{(l)})^{T}+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}(\hat{A}_{{ip}}^{k}-\hat{A}_{{jp}}^{k})\\\
\end{split}$ (16)

We further have

$\begin{split}|Z_{ip}^{(l)*}-Z_{jp}^{(l)*}|&\leq\frac{1-\gamma}{\beta_{1}+\beta_{2}}\|{h}_{i}^{(l)}-{h}_{j}^{(l)}\|_{2}\|(h_{p}^{(l)})^{T}-(1-\gamma)^{2}(H^{(l)})^{T}R\|_{2}\\\
&+\frac{\gamma(1-\gamma)}{\beta_{1}+\beta_{2}}\|h_{i}^{(0)}-h_{j}^{(0)}\|_{2}\|(h_{p}^{(l)})^{T}-(1-\gamma)^{2}(H^{(l)})^{T}R\|_{2}\\\
&+\frac{\beta_{2}(1-\gamma)^{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}\|\hat{a}_{i}^{k}-\hat{a}_{j}^{k}\|_{2}\|R\|_{2}+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}|\hat{A}_{{ip}}^{k}-\hat{A}_{{jp}}^{k}|\\\
\end{split}$ (17)

∎

We next prove Lemma 4.3:

###### Proof.

From Equation 12, we get

$\begin{split}Z_{pi}^{(l)*}-Z_{pj}^{(l)*}&=\frac{(1-\gamma)[{h}_{p}^{(l)}-(1-\gamma)z_{p}^{(l)*}H^{(l)}-\gamma
h_{p}^{(0)}](h_{i}^{(l)}-h_{j}^{(l)})^{T}}{\beta_{1}+\beta_{2}}\\\
&+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}(\hat{A}_{{pi}}^{k}-\hat{A}_{{pj}}^{k})\\\
\end{split}$ (18)

That implies

$\begin{split}|Z_{pi}^{(l)*}-Z_{pj}^{(l)*}|&\leq\frac{(1-\gamma)\lVert{h}_{p}^{(l)}-(1-\gamma)z_{p}^{(l)*}H^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}\lVert
h_{i}^{(l)}-h_{j}^{(l)}\rVert_{2}}{\beta_{1}+\beta_{2}}\\\
&+\frac{\beta_{2}}{\beta_{1}+\beta_{2}}\sum_{k=1}^{K}\lambda_{k}|\hat{A}_{{pi}}^{k}-\hat{A}_{{pj}}^{k}|\\\
\end{split}$ (19)

Since $Z^{(l)*}$ is the optimal solution to Equation 5, we have

$\begin{split}&J(z_{p}^{(l)*})=\lVert{h}_{p}^{(l)}-(1-\gamma)z_{p}^{(l)*}H^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}^{2}+\beta_{1}\|z_{p}^{(l)*}\|_{2}^{2}\\\
&+\beta_{2}\lVert
z_{p}^{(l)*}-\sum_{k=1}^{K}\lambda_{k}\hat{a}_{p}^{k}\rVert_{2}^{2}\leq
J(0)=\lVert{h}_{p}^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}^{2}+\beta_{2}\lVert\sum_{k=1}^{K}\lambda_{k}\hat{a}_{p}^{k}\rVert_{2}^{2}.\\\
\end{split}$ (20)

Hence,

$\lVert{h}_{p}^{(l)}-(1-\gamma)z_{p}^{(l)*}H^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}\leq\sqrt{\lVert{h}_{p}^{(l)}-\gamma
h_{p}^{(0)}\rVert_{2}^{2}+\beta_{2}\lVert\sum_{k=1}^{K}\lambda_{k}\hat{a}_{p}^{k}\rVert_{2}^{2}}=\eta.$
(21)

Equation 19 can be further simplified as

$|Z_{pi}^{(l)*}-Z_{pj}^{(l)*}|\leq\frac{\eta(1-\gamma)\lVert
h_{i}^{(l)}-h_{j}^{(l)}\rVert_{2}+\beta_{2}\sum_{k=1}^{K}\lambda_{k}|\hat{A}_{{pi}}^{k}-\hat{A}_{{pj}}^{k}|}{\beta_{1}+\beta_{2}}$
(22)

∎

The proof of Lemma 4.4 is given as follows:

###### Proof.

Given two nodes $v_{i}$ and $v_{j}$, if $v_{i}\rightarrow v_{j}$, we can get
by definition (1) $\|x_{i}-x_{j}\|_{2}\rightarrow 0$ and (2)
$\lVert\hat{a}_{i}^{k}-\hat{a}_{j}^{k}\rVert_{2}\rightarrow 0,\ \forall
k\in[1,K]$. Then based on Equations 2 and 3, we can easily get
$\|h_{i}^{(0)}-h_{j}^{(0)}\|_{2}\rightarrow 0$. Hence $H^{(0)}$ has grouping
effect. We next show that $Z^{(0)*}$ has grouping effect. Since
$\lVert\hat{a}_{i}^{k}-\hat{a}_{j}^{k}\rVert_{2}\rightarrow 0$, then
$|\hat{A}_{{ip}}^{k}-\hat{A}_{{jp}}^{k}|\rightarrow 0$ and
$|\hat{A}_{{pi}}^{k}-\hat{A}_{{pj}}^{k}|\rightarrow 0$ (due to the symmetry of
$\hat{A}^{k}$). According to Equation 17, the R.H.S. of the equation will
become close to 0, which induces that
$|Z_{ip}^{(0)*}-Z_{jp}^{(0)*}|\rightarrow 0$ and $Z^{(0)*}$ thus has grouping
effect. Similarly, the R.H.S. of Equation 22 also approaches 0, leading to the
grouping effect of $(Z^{(0)*})^{T}$. Then we show $H^{(1)}$ has grouping
effect. From Eq. 6, $H^{(l+1)}$ is updated based on $H^{(0)}$ and
$Z^{(l)*}H^{(l)}$. Due to the grouping effect of $Z^{(0)*}$ and $H^{(0)}$, the
linear representation $Z^{(0)*}H^{(0)}$ also has grouping effect, which
further induces that $H^{(1)}$ has grouping effect. In this way, we can
inductively prove that $Z^{(l)*}$, $(Z^{(l)*})^{T}$ and $H^{(l+1)}$ all have
grouping effect.

∎

##  Appendix E Ablation study

We next conduct an ablation study to understand the main components of GloGNN.
To construct the initial node embedding matrix $H^{(0)}$, GloGNN first
transforms both feature matrix and adjacency matrix into low-dimensional
embedding vectors, respectively. To show the importance of feature matrix in
constructing $H^{(0)}$, we set $\alpha=0$ in Equation 3 and derive
$H^{(0)}=H_{X}^{(0)}$. We call this variant GloGNN-na (no adjacency matrix).
Similarly, to understand the importance of feature matrix, we set $\alpha=1$
and call the variant GloGNN-nf (no feature matrix). Further, to utilize the
local structural information of a node, GloGNN regularizes the coefficient
matrix $Z$ with multi-hop graph adjacency matrices, as shown in Equation 5. We
thus consider a variant GloGNN-nl (no local regularization) by removing the
regularization term to study the importance of local graph structures of
nodes. Finally, we compare GloGNN with these variants on all the benchmark
datasets and show the results in Fig. 6. From the figure, we see

(1) While GloGNN-na and GloGNN-nf can achieve comparable performance with
GloGNN on some datasets, GloGNN significantly outperforms them on others. This
shows the necessity of GloGNN to adaptively learn the importance of feature
matrix and adjacency matrix when constructing the initial node embedding
vectors on various datasets.

(2) GloGNN generally performs better than GloGNN-nl. Since GloGNN-nl ignores
the local regularization term, it could fail to identify two homophilous nodes
that share similar local graph structures. On the other hand, GloGNN measures
node similarity in terms of both node features and local graph structures,
which further explains GloGNN’s robustness towards graphs with various
heterophilies.

Figure 6: Ablation study

##  Appendix F Experimental setup

We implemented GloGNN by PyTorch. For fairness, we run the experiments of 9
small-scale datasets on CPUs and optimize the models by Adam as in (Yan et
al., 2021). Meanwhile, we run the experiments of 6 large-scale datasets on a
single Tesla V100 GPU with 32G memory and use AdamW as the optimizer following
(Lim et al., 2021). We perform a grid search to tune hyper-parameters based on
the results on the validation set. Details of these hyper-parameters are
listed in Tables 3 and 4. Further, since the results of most baseline methods
on these benchmark datasets are public, we directly report these results. For
those cases where the results are absent, we use the original codes released
by their authors and fine tune the model parameters as suggested in (Yan et
al., 2021; Lim et al., 2021; Suresh et al., 2021). We provide our code and
data at https://github.com/RecklessRonan/GloGNN.

Table 3: Grid search space on small-scale datasets Notation | Range
---|---
lr | $\\{0.01,0.005\\}$
dropout | $[0,0.9]$
early_stopping | $\\{40,200,300\\}$
weight_decay | $\\{1\mathrm{e}{-5},5\mathrm{e}{-5},1\mathrm{e}{-4}\\}$
$\alpha$ | $[0,1]$
$\beta_{1}$ | $\\{0,1,10\\}$
$\beta_{2}$ | $\\{0.1,1,10,10^{2},10^{3}\\}$
$\gamma$ | $[0,0.9]$
norm_layers | $\\{1,2,3\\}$
max_hop_count $K$ | $[1,6]$
Table 4: Grid search space on large-scale datasets Notation | Range
---|---
lr | $\\{0.01,0.005,0.001\\}$
dropout | $[0,0.9]$
weight_decay | $\\{0,1\mathrm{e}{-3},1\mathrm{e}{-2},1\mathrm{e}{-1}\\}$
$\alpha$ | $\\{0.1,0.5,0.9\\}$
$\beta_{1}$ | $\\{0,0.1,1\\}$
$\beta_{2}$ | $\\{0.1,1\\}$
$\gamma$ | $\\{0.1,0.5,0.9\\}$
norm_layers | $\\{1,2,3\\}$
max_hop_count $K$ | $\\{1,2,3\\}$