# AGS-GNN: Attribute-guided Sampling for Graph Neural Networks

Siddhartha Shankar Das<EMAIL_ADDRESS>Purdue UniversityP.O. Box 1212West
LafayetteINUSA47906 ,  S M Ferdous<EMAIL_ADDRESS>Pacific Northwest
National Lab.P.O. Box 999RichlandWAUSA99352 ,  Mahantesh M Halappanavar
<EMAIL_ADDRESS>Pacific Northwest National Lab.P.O. Box 999RichlandWAUSA99352 ,
Edoardo Serra<EMAIL_ADDRESS>Boise State UniversityP.O. Box
999BoiseIDUSA83725 and  Alex Pothen<EMAIL_ADDRESS>Purdue UniversityP.O.
Box 1212West LafayetteINUSA47906

###### Abstract.

We propose AGS-GNN, a novel attribute-guided sampling algorithm for Graph
Neural Networks (GNNs) that exploits node features and connectivity structure
of a graph while simultaneously adapting for both homophily and heterophily in
graphs. (In homophilic graphs vertices of the same class are more likely to be
connected, and vertices of different classes tend to be linked in heterophilic
graphs.) While GNNs have been successfully applied to homophilic graphs, their
application to heterophilic graphs remains challenging. The best-performing
GNNs for heterophilic graphs do not fit the sampling paradigm, suffer high
computational costs, and are not inductive. We employ samplers based on
feature-similarity and feature-diversity to select subsets of neighbors for a
node, and adaptively capture information from homophilic and heterophilic
neighborhoods using dual channels. Currently, AGS-GNN is the only algorithm
that we know of that explicitly controls homophily in the sampled subgraph
through similar and diverse neighborhood samples. For diverse neighborhood
sampling, we employ submodularity, which was not used in this context prior to
our work. The sampling distribution is pre-computed and highly parallel,
achieving the desired scalability. Using an extensive dataset consisting of 35
small ($\leq 100K$ nodes) and large ($>100K$ nodes) homophilic and
heterophilic graphs, we demonstrate the superiority of AGS-GNN compare to the
current approaches in the literature. AGS-GNN achieves comparable test
accuracy to the best-performing heterophilic GNNs, even outperforming methods
using the entire graph for node classification. AGS-GNN also converges faster
compared to methods that sample neighborhoods randomly, and can be
incorporated into existing GNN models that employ node or graph sampling.

Graph Neural Networks, Heterophily, Submodular Functions

††copyright: none††conference: ; August; Barcelona††isbn:
978-1-4503-XXXX-X/18/06

##  1\. Introduction

Traditional Graph Neural Networks (GNNs) rely on the _homophilic_ property of
the learning problem, which assumes that a significant portion of a node’s
neighbors share the class label of the node. However, this assumption has been
challenged in recent years since graphs in several practical applications do
not satisfy homophily (Zheng et al., 2022; Platonov et al., 2022).
Consequently, GNNs designed with the assumption of homophily fail to classify
heterophilic graphs accurately due to noisy or improper neighborhood
aggregation (Luan et al., 2022). A simple Multi-layer Perceptron (MLP) based
model that ignores the graph structure can outperform existing homophilic GNNs
on heterophilic graphs (Ye and Ji, 2021; Lim et al., 2021; Zhu et al., 2020;
Liu et al., 2021; Luan et al., 2020; Chien et al., 2020). As a result, a
number of special-purpose GNNs have been developed to classify heterophilic
graphs (Zheng et al., 2022; Luan et al., 2022; Zhu et al., 2020; Liu et al.,
2021; Luan et al., 2020; Chien et al., 2020; Zhu et al., 2021; Yan et al.,
2022; Li et al., 2022; Xu et al., 2023).

Although GNNs have been adapted for heterophilic graphs in earlier work, their
applicability is limited since they do not scale to large graphs and are
transductive. Unlike homophilic GNNs (Hamilton et al., 2017; Zeng et al.,
2019; Chen et al., 2018b, a; Huang et al., 2018; Chiang et al., 2019), where
subgraph sampling strategies have been developed for scaling, currently there
are no effective sampling approaches for heterophilic graphs (Lim et al.,
2021). Recent authors have enabled scaling by first transforming node features
and adjacency matrix into lower dimensional representations, and then applying
mini-batching on the combined representations (Lim et al., 2021; Liao et al.,
2023). Thus inference on heterophilic graphs via graph sampling remains
challenging.

The dichotomy of classifying graphs into heterophilic or homophilic graphs, as
used in current literature, is blurred in practice by the presence of locally
homophilic and locally heterophilic nodes. As shown in Fig. 1 (§2), both
homophilic and heterophilic graphs could have nodes with high local homophily
or heterophily. However, there is no systematic and scalable approach for
neighborhood sampling that distinguishes each node w.r.t. its local homophily
property. We propose a new sampling strategy that incorporates both the
adjacency structure of the graph as well as the feature information of the
nodes that is capable of making this distinction. For a homophilic node, we
build our sampling strategy based on a widely used _smoothing_ assumption (Van
Engelen and Hoos, 2020) that labels and features generally correlate
positively. Heterophilic nodes of the same labels, however, are expected to
have the same dissimilar neighborhood (Luan et al., 2022), and our sampling
strategy exploits this. Thus, we generate two sets of local neighborhood
samples for each node: one based on feature similarity that potentially
improves local homophily, while the other encourages diversity and increases
heterophily. These two samples are adaptively learned using an MLP to select
the appropriate one based on the downstream task. Our attribute-based sampling
strategy can be seamlessly plugged into GNNs designed for classifying
heterophilic graphs and performs well in practice. The strength of our
approach, however, is that even when paired with GNNs designed for homophilic
graphs, we obtain better accuracies for heterophilic graphs, thus rendering an
overall scalable approach for the latter graphs. The key contributions and
findings of this work are summarized as follows:

  1. (1)

We propose a novel scalable and inductive unsupervised and supervised feature-
guided sampling framework, AGS-GNN, to learn node representations for both
homophilic and heterophilic graphs.

  2. (2)

AGS-GNN incorporates sampling based on similarity and diversity (modeled by a
submodular function). We are not aware of earlier work that uses submodularity
in this context. AGS-GNN employs dual channels with MLPs to learn from both
similar and diverse neighbors of a node.

  3. (3)

We experimented with $35$ benchmark datasets for node classification and
compared them against GNNs designed for heterophilic and homophilic graphs.
For both types of graphs, AGS-GNN achieved improved accuracies relative to
earlier methods (Fig. 5) (§5.3). Further, AGS-GNN also requires fewer
iterations (up to $50\%$ less) (§5.4) to converge relative to random sampling.

##  2\. Preliminaries

Consider a weighted graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$ with
set of vertices ${\mathcal{V}}$, and set of edges ${\mathcal{E}}$. We denote
the number of vertices and edges by $|{\mathcal{V}}|\equiv n$ and
$|{\mathcal{E}}|\equiv m$. The adjacency matrix of the graph will be denoted
by ${\bm{A}}\in\mathbb{R}^{n\times n}$, and the $f$-dimensional feature matrix
of nodes by ${\bm{X}}\in\mathbb{R}^{n\times f}$. We denote
$y_{u}\in{\mathbb{Y}}=\\{1,2,\cdots,c\\}$ to be the label of a node $u$ that
belongs to one of the $c$ classes, and the vector
${\bm{y}}\in{\mathbb{Y}}^{n}$ to denote the labels of all nodes. Additionally,
the graph may have associated edge features of dimension $f_{e}$. The degree
of node $u$ is denoted by $d_{u}$, the average degree by $d$, and the set
${\mathcal{N}}(u)$ denotes the set of neighboring vertices of a node $u$. For
a GNN, $\ell$ denotes the number of layers, $H$ the number of neurons in the
hidden layer, and ${\bm{W}}^{i}$ the learnable weight of the $i$-th layer.

###  2.1. Homophily Measures

The _homophily_ of a graph characterizes how likely vertices with the same
labels are neighbors of each other. Many measures of homophily fit this
definition, and Appendix 10.2 discusses seven of them, with the values
computed on our benchmark dataset. However, for conciseness, we will focus
here on node homophily (${\mathcal{H}}_{n}$) (intuitive), and adjusted
homophily (${\mathcal{H}}_{a}$) (handles class imbalance). The local node
homophily of node $u$ is
${\mathcal{H}}_{n}(u)=\frac{|\\{v\in{\mathcal{N}}(u):y_{v}=y_{u}\\}|}{|{\mathcal{N}}(u)|}$,
and its mean value node homophily (Pei et al., 2020)is defined as follows:

(1) $\displaystyle{\mathcal{H}}_{n}$
$\displaystyle=\frac{1}{|{\mathcal{V}}|}\sum_{u\in{\mathcal{V}}}{\mathcal{H}}_{n}(u).$

The edge homophily (Zhu et al., 2020) of a graph is
${\mathcal{H}}_{e}=\frac{|\\{(u,v)\in{\mathcal{E}}:y_{u}=y_{v}\\}|}{|{\mathcal{E}}|}.$
Let $D_{k}=\sum_{v:y_{v}=k}d_{v}$ denote the sum of degrees of the nodes
belonging to class $k$. Then the adjusted homophily (Platonov et al., 2022) is
defined as

(2)
${\mathcal{H}}_{a}=\frac{{\mathcal{H}}_{e}-\sum_{k=1}^{c}D_{k}^{2}/(2|{\mathcal{E}}|^{2})}{1-\sum_{k=1}^{c}D_{k}^{2}/2|{\mathcal{E}}|^{2}}.$

The values of the node homophilies and edge homophily range from $0$ to $1$,
and the adjusted homophily ranges from $-\frac{1}{3}$ to $+1$ (Proposition 1
in (Platonov et al., 2022)). In this paper, we will classify graphs with
adjusted homophily less than $0.50$ as heterophilic. Fig. 1 shows the
distribution of the local node homophily of a homophilic and a heterophilic
graph. We see that both the graphs have a mix of locally heterophilic and
locally homophilic nodes.

(a) Reddit (homophilic) (b) Penn94 (heterophilic)

Figure 1. The distribution of local node homophily in a homophilic and a
heterophilic graph. Figs. 13 and 14 in Appendix 10.5 show this for all
datasets.

###  2.2. Effect of Homophily on Classification

To highlight the effect of homophily, we conduct an experiment on node
classification using synthetic graphs with different levels of node homophily.
These synthetic graphs are generated from the existing graphs, ignoring the
structure information of the graph but retaining the node features and class
labels. Following (Luan et al., 2022), to generate an undirected graph with an
average degree of $d$ and node homophily ${\mathcal{H}}_{n}$, for each node
$u$ we randomly assign ${\mathcal{H}}_{n}\cdot d/2$ edges from the same class
as $u$ and $(1-{\mathcal{H}}_{n})\cdot d/2$ edges from other classes. We left
the class distribution unbalanced, as it is in the original graph, making it
more challenging for GNNs since the neighborhood of a heterophilic node could
potentially have more nodes from the majority class.

Fig. 2 shows the performance of GSAGE (Hamilton et al., 2017) (a homophilic
GNN) and ACM-GCN (Luan et al., 2022) (a heterophilic GNN) on the synthetic
graphs generated from Squirrel and Chameleon (Rozemberczki et al., 2021)
datasets. We use two versions of ACM-GCN, one with three channels (low-pass,
high-pass, and identity) and the other with an additional channel with graph
structure information (ACM-GCN-struc). The original Squirrel and Chameleon
datasets are heterophilic, and the ACM-GCN-struc is the best-performing. For
synthetic graphs, on both Squirrel and Chameleon, (Fig. 2), we see that
surprisingly the worst $F_{1}$ score is not achieved on the graphs whose
homophily value is zero but for values near $0.25$. When the homophily score
is high, GNNs perform well since it aggregates relevant information, but as we
observe ACM-GCN also does well at a very low homophily. This is because some
locally heterophilic nodes become easier to classify after neighborhood
aggregation on features (note that features are not considered in the
definition of homophily based solely on labels). Another intuitive reason is
that when two nodes are adjacent to the same dissimilar (wrt class labels)
neighbors, the high pass filters (e.g., graph Laplacian) used in ACM-GCN treat
these nodes as similar and can classify them correctly (Appendix 7.4).

(a) Squirrel Synthetic (b) Chameleon Synthetic

Figure 2. $F_{1}$ Score comparison of GSAGE and ACM-GCN on synthetic graphs
generated from Squirrel (a) and Chameleon (b) datasets with varying node
homophily.

###  2.3. Similarity, Diversity, and Homophily

Nodes with similar features tend to have similar labels (Van Engelen and Hoos,
2020). We carried out an experiment to validate this statement and show in
Appendix 10.4 that the labels of nodes often correlate positively with their
features. Therefore, if instead of sampling the neighbors of a node $u$
uniformly at random, we sample neighbors that are similar to $u$ in feature
space, we are likely to increase the homophily of the sampled subgraph.

However, this strategy alone is not enough for heterophilic graphs as they
include both locally homophilic and heterophilic nodes (Fig. 1). Two
heterophilic nodes with the same label are expected to have similar class
label distributions in their neighbors. In other words, the diversity in their
class labels makes them similar. It has been shown (Luan et al., 2022; Zheng
et al., 2022; Xu et al., 2023) that high-pass filters (Ekambaram, 2014) (e.g.,
variants of graph Laplacians: ${\bm{L}}={\bm{D}}-{\bm{A}}$,
${\bm{L}}_{sym}={\bm{D}}^{-1/2}{\bm{L}}{\bm{D}}^{-1/2}$, or
${\bm{L}}_{rw}={\bm{D}}^{-1}{\bm{L}}$) capture the difference between nodes,
and low-pass filters (e.g., scaled adjacency matrices,
${\bm{A}}_{sym}={\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2}$, or
${\bm{A}}_{rw}={\bm{D}}^{-1}{\bm{A}}$) retain the commonality of node features
(Appendix 7.4). Therefore, if we sample diverse neighbors (in feature space)
and use a GNN with a high-pass filter, we expect a higher chance of mapping
two heterophilic nodes of same class to the same space (after feature
transformation) since they will have the same dissimilar neighborhood.

A mathematical approach to ensure diversity is through _submodular function_
maximization (Krause and Golovin, 2014; Schreiber et al., 2020). A submodular
function is a set function that favors a new node that is most distant in
feature space to add to a partially sampled neighborhood. It accomplishes this
by defining a suitable marginal gain of the new element with respect to the
current neighborhood, and maximizing this value. However, employing only
diverse neighborhoods can also cause issues since two nodes with different
labels may have similar neighborhoods after sampling. In this scenario,
sampling based on similarity is more appropriate. For the spectral domain,
AGS-GNN considers two channels: one with a sampled subgraph ensuring diversity
(used with a high-pass filter) and the other with a subgraph sampled based on
similarity (used with a low-pass filter). Similar to ACM-GCN, we can also use
an identity channel. However, spectral GNNs are difficult to scale as they
often do not support mini-batching, and are transductive. Hence we consider
spatial GNNs for heterophilic graphs, which employ graph topology to develop
aggregation strategies. However, for heterophilic graphs, both similar and
dissimilar neighbors need to be considered, and in AGS-GNN, we achieve this
through attribute-guided biased sampling of similar and diverse samples.

####  2.3.1. Node Homophily with Similar and Diverse neighborhood:

Consider an ego node $t=\\{{\bm{x}}_{t},y_{t}\\}$ with feature ${\bm{x}}_{t}$,
label $y_{t}$, and local node homophily ${\mathcal{H}}_{n}(t)$. Let the
feature and label tuples of the neighbors of $t$ be
${\mathcal{N}}(t)=\\{({\bm{x}}_{1},y_{1}),({\bm{x}}_{2},y_{2}),\cdots,({\bm{x}}_{d_{t}},y_{d_{t}})\\}$.
From the definition of homophily, the probability of randomly selecting a
neighbor $i\in{\mathcal{N}}(t)$ with the same label as the ego node is
$P_{\mathcal{U}}(y_{i}=y_{t})={\mathcal{H}}_{n}(t)$. Here, ${\mathcal{U}}$
refers to the distribution of selecting a neighbor uniformly at random. Let
$s({\bm{x}}_{i},{\bm{x}}_{t})$ be a positive similarity score in features
between a neighbor, $i$, and the ego node, $t$.

###### Assumption 2.1.

For a node $t$, the average similarity of neighbors with the same label as $t$
is greater than or equal to the average similarity of all neighbors.

###### Lemma 2.1.

If the probability of selecting a neighboring node is proportional to its
similarity to the ego node $t$, the local node homophily of sampled
neighborhood ${\mathcal{H}}_{n}^{\prime}(t)\geq{\mathcal{H}}_{n}(t)$. If the
sampling probability distribution is ${\mathcal{S}}$, then
$P_{\mathcal{S}}(y_{i}=y_{t})\geq P_{\mathcal{U}}(y_{i}=y_{t})$.

To retrieve a diverse set of neighbors we can employ a submodular function. An
example could be the facility location function based on maximizing pairwise
similarities between the points in the data set and their nearest chosen
point, $f(S,A)=\sum_{y\in A}\max_{x\in S}\phi(x,y),$ where $A$ is the ground
set, $S\subseteq A$ is a subset, and $\phi$ is the similarity measure. In our
context $S$ is the current set of selected nodes initialized with ego node
$t$, and ground set $A={\mathcal{N}}(t)\cup\\{t\\}$. The _marginal gain_ is
$f_{i}=f(S\cup\\{i\\},A)-f(S,A)$ for each neighbor
$i\in{\mathcal{N}}(t)\setminus S$. Successively, neighbors are added to the
sampled neighborhood by choosing them to have maximum marginal gain with
respect to the current sample of the neighborhood.

###### Assumption 2.2.

The average marginal gain of the neighbors of a node $t$ with the same label
as $t$ is less than or equal to the average marginal gain of all neighbors.

###### Lemma 2.2.

If the probability of selecting a neighboring node is proportional to its
marginal gain wrt the ego node $t$, then the local node homophily of sampled
neighborhood ${\mathcal{H}}_{n}^{\prime}(t)\leq{\mathcal{H}}_{n}(t)$. If the
sampling probability distribution is ${\mathcal{D}}$, then
$P_{\mathcal{D}}(y_{i}=y_{t})\leq P_{\mathcal{U}}(y_{i}=y_{t})$.

Proofs of Lemmas 2.1 and 2.2 are included in the Appendix 7.1 and Appendix 7.2
respectively. We also report experimental verification of these properties in
Appendix 7.3. From the Lemma 2.1, sampling neighbors based on feature-
similarity improves homophily, which potentially helps to map homophilic nodes
of the same labels into the same space. We assume features and labels to be
positively correlated; thus, if we ensure feature diversity among neighbors,
we can also expect label diversity in the samples, reducing local homophily
(as shown in Lemma 2.2) and increasing the chances of mapping two heterophilic
nodes into the same space. We devise feature-similarity and feature-diversity-
based sampling based on these results in the next section.

##  3\. Proposed Method: AGS-GNN

Fig. 3 shows an overview of the AGS-GNN framework. AGS-GNN has a _pre-
computation_ step that ranks the neighbors of nodes and computes edge weights
to form a distribution to sample from in the _sampling_ phases during
training.

(a) Rank of neighbors for similar and diverse sampling. (b) Node Sampling from
training vertices with hop size $2$

Figure 3. AGS-GNN framework with Node Sampling. a) Pre-computation step to
rank the neighbor of vertices. b) Demonstrates how weighted node sampling is
performed based on the selection probabilities of ranked neighbors.

###  3.1. Pre-computing Probability Distribution

An ideal graph sampling process should have the following key requirements:
(i) Nodes with strong mutual influences (in terms of structure and attributes)
should be sampled together in a subgraph (Zeng et al., 2019).  (ii) Should be
able to distinguish between similar and dissimilar neighbors (especially for
heterophilic graphs) (Zheng et al., 2022).  (iii) Every edge should have a
non-zero probability of being sampled in order to generalize and explore the
full feature and label space.

In this section, we will devise sampling strategies satisfying these
requirements. We assume that we have access to a similarity measure between
any two nodes in the graph. This similarity function typically depends on the
problem and the dataset. For an example, in text based datasets, we may use
cosine similarity of the feature vectors (e.g., TF-IDF) generated from the
texts of the corresponding items. We may also learn the similarities when an
appropriate similarity measure is not apparent. Once we have the similarity
function, for each vertex $u$, we construct a probability distribution over
its neighbors as follows:  (i) _rank_ the neighboring nodes
(${\mathcal{N}}(u)$) using the similarity scores to $u$.  (ii) assign weights
to the adjacent edges of $u$ based on this ranking. A few choices are shown in
Fig. 10 in Appendix.  (iii) normalize the weights to construct the probability
mass function (PMF) ${\mathcal{P}}(u)$ of the distribution over
${\mathcal{N}}(u)$.

We construct the probability distribution using the rank rather than the
actual similarity values, since the distribution using the similarity values
could be skewed and extremely biased towards a few top items. Here we consider
two choices of rankings of neighborhoods that are suited for homophilic and
heterophilic graphs.

####  3.1.1. Ranking based on similarity:

For this case, our goal is to sample subgraphs favoring similar edges to be
present more frequently in the subgraph. To achieve that we propose to
construct a probability distribution over the edges based on the similarity
scores. We sort the similarity values of all the neighboring vertices of a
vertex from high to low and assign ranking based on the order to the adjacent
edges. Thus, although the similarity function is symmetric, we may get two
different ranks for each edge. Note that the computation required to generate
the rankings are local to each vertex and thus highly parallel. For cosine
similarity the time complexity to compute the ranking of the adjacent edges of
a vertex $u$ is ${\mathcal{O}}(fd_{u}\log{d_{u}})$.

Once we have the rankings, we can use these to construct different probability
distributions. Some choices of Probability Mass Functions (PMF) can be linear
or exponential decay with non-zero selection probability to the later elements
in the ranking order. Another options is the step function where the top
$k_{1}\%$ neighbors of a vertex are given a uniform weight ($\lambda_{1}$),
the next $k_{2}\%$ as $\lambda_{2}$, and the rest $\lambda_{3}$, where
$\lambda_{1}>\lambda_{2}>\lambda_{3}$. The benefit of using such function is
that we can partially sort the top $(k_{1}+k_{2})\%$ of neighbors avoiding the
full ordering. Fig. 10 in Appendix 8 shows pictorial representations of some
of the PMFs mentioned.

####  3.1.2. Ranking based on diversity:

As discussed in section 2.3, for a heterophilic graph, in general it is
desirable to construct subgraphs based on diversity in the class labels. To
accomplish that, we propose a sampling strategy based on optimizing (a
nonlinear) submodular function. A submodular function is a set function that
has the diminishing returns property. Formally, given a ground set $V$ and two
subsets $A$ and $B$ with $A\subseteq B\subseteq V$, a function $f$ is
submodular if and only if, for every $e\in V\setminus B$, $f(A\cup e)-f(A)\geq
f(B\cup e)-f(B)$. The quantity on either side of the inequality is called the
_marginal gain_ of an element $e$ with respect to the two sets $A$ or $B$. For
maximizing cardinality constrained submodular functions, where the solution
set ($S$) is required to be at most $k$ in size, a natural _Greedy_ algorithm
that starts with empty solution and augments it with the element with highest
marginal gain is $(1-1/e)$-approximate (Nemhauser et al., 1978).

To see how a submodular function may behave differently than the (linear)
similarity based function (section 3.1.1), consider a paper citation graph
(Sen et al., 2008) where the nodes are the scientific documents and the
feature on each node is the binary count vector of the associate text. For a
vertex $u$, our goal is to find a set of $k$ neighboring vertices of $u$,
($S\subseteq{\mathcal{N}}(u)$ where $|S|=k$), such that given the initial set
$\\{u\\}$, we maximize the number of _unique_ word counts. This objective can
be modeled as a submodular function known as maximum $k$-coverage problem, and
the Greedy approach would select successive nodes with maximum marginal gains
wrt to $S$. Intuitively, the Greedy algorithm prioritizes neighbors that have
more distinct words than what has been covered through the selected nodes.
Therefore, if different word sets correspond to different class labels, the
final set $S$ will likely represent a diverse set. This contrasts sharply with
the ranking based on similarity, where we would encourage neighbors with
similar words. Facility Location, Feature-based functions, and Maximum
Coverage are some submodular functions applicable in the graph context.

Given a submodular function, for a vertex $u$, we execute the Greedy algorithm
on the neighbors of $u$ to compute their marginal gains, assuming $u$ is in
the initial solution. We use these marginal gains to rank neighbors of $u$ and
then use the ranks to construct a probability distribution as described in
section 3.1.1. To compute the solution faster, we employed a variant of the
Greedy algorithm which is called Lazy Greedy (Minoux, 1978) that can reduce
the number of marginal gain computations. Algorithm 3 and 4 in Appendix 8.3
shows the pseudocode of the Lazy Greedy version of the ranking procedure using
the Facility Location function. Since we need to compute pairwise similarity
for this function, the complexity of computing the ranks of the neighbors of a
vertex $u$ is ${\mathcal{O}}(fd_{u}^{2})$.

####  3.1.3. Learnable Similarity Function:

When we lack domain knowledge to compute an appropriate similarity metric, we
can use the training subgraph to train a regression model to learn the edge
weights of the graphs (Chien et al., 2020). We form training batches using
equal numbers of edges and randomly chosen non-edges of the graph. We set the
target label as $1$ for nodes with the same labels and $0$ otherwise, and then
train a model using the batches to get an approximation of edge weights. We
use these weights as similarity values to compute ranks based on similarity or
diversity (as detailed in section 3.1.1 and section 3.1.2), and to compute a
probability distribution over the directed edges. Given the number of training
edges and an equal number of non-edges, we can expect the computation
complexity to be $\mathcal{O}(fm)$. The neural network model is shallow,
learnable parameters are relatively small, and computation is performed in
batches, making it very fast. Appendix 8.4 shows the architecture of a Siamese
(Chicco, 2021) edge-weight computation model and the training and inference
process (Algorithm 5) in detail.

###  3.2. Sampling

Algorithm 1 describes AGS-GNN, using the node sampling process for training
denoted as AGS-NS. The method NodeSample is employed for sampling an
$\ell$-hop neighborhood based on the probability distribution derived from
learned or computed weights.

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Label, ${\bm{y}}\in{\mathbb{Y}}^{n}$

1

1: ${\mathcal{S}}=\mathrm{LearnSimilarity({\mathcal{G}},{\bm{X}},{\bm{y}})}$

2: ${\mathcal{P}}=\mathrm{{}^{\prime}step^{\prime}}$ /* probability mass
function */

2

3:
$\mathrm{R_{1}=RankBySimilarity({\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}})}$/*
Alg. 2 */

3

4:
$\mathrm{R_{2}=RankByDiversity({\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}})}$/*
Alg. 3 */

4

5: for $\mathrm{epoch}$ in $\mathrm{num\\_epochs}$ do

6: $\mathrm{nodes,y_{nodes}=BatchOfTrainingNodes({\mathcal{G}},{\bm{y}})}$ /*
random nodes from training vertices */

7: $\mathrm{g_{1}=NodeSample(R_{1},nodes)}$ /* similar samples */

8: $\mathrm{g_{2}=NodeSample(R_{2},nodes)}$ /* diverse samples */

9: $\mathrm{output=GNN_{\bm{W}}(g_{1},g_{2})}$

10: $l=\mathrm{loss(output,y_{nodes}}$)

11: Backward propagation from $l$ to update ${\bm{W}}$

12: end for

Algorithm 1 AGS-NS (${\mathcal{G}},{\bm{X}},{\bm{y}}$) [Node Sampling]

AGS can be plugged in with other GNNs that use sampling strategy. Here, we
demonstrate this with GSAGE and call it AGS-GSAGE. The original formulation of
GSAGE for $i$-th layer is,

(3)
${\bm{h}}_{v}^{(i)}=\sigma({\bm{W}}^{(i)},{\bm{h}}_{v}^{(i-1)}|\mathrm{AGG}(\\{{\bm{h}}_{u}^{(i-1)}:u\in{\mathcal{N}}_{rn}(v)\\}).$

Here ${\bm{h}}$ denotes feature vectors, ${\mathcal{N}}_{rn}(v)$
($\subseteq{\mathcal{N}}(v)$) is the subset of neighbors of $v$ (of size $k$)
sampled uniformly at random. AGG is any permutation invariant function (mean,
sum, max, LSTM, etc.).

In AGS-GSAGE, we use the probability distribution derived in section 3.1 to
sample with or without replacement from the neighborhood of a node. Depending
on the nature of the graph, single or dual-channel GNNs might be necessary.
Some homophilic graphs may have only a few locally heterophilic nodes, where
samples from a distribution generated by similarity only may be sufficient.
However, we expect the dual-channel AGS to perform better for heterophilic
graphs since they typically have both locally homophilic and heterophilic
nodes (see Fig. 1, and Fig. 13, Fig. 14 from Appendix 10.5). Fig. 4 shows some
possible computation graphs. The dual-channel AGS mechanism can be
incorporated easily into GSAGE. We generate two similar and diverse
neighborhood samples for the target node, compute the transformed feature
representations using both samples, and use MLPs to combine these
representations.

(4)
$\displaystyle{\bm{h}}_{v_{sim}}^{(i)}=\sigma({\bm{W}}^{(i)}_{sim},{\bm{h}}_{v}^{(i-1)}|\mathrm{AGG}(\\{{\bm{h}}_{u}^{(i-1)}:u\in{\mathcal{N}}_{sim}(v)\\})$
(5)
$\displaystyle{\bm{h}}_{v_{div}}^{(i)}=\sigma({\bm{W}}^{(i)}_{div},{\bm{h}}_{v}^{(i-1)}|\mathrm{AGG}(\\{{\bm{h}}_{u}^{(i-1)}:u\in{\mathcal{N}}_{div}(v)\\}).$

Here ${\mathcal{N}}_{sim}(v)$ and ${\mathcal{N}}_{div}(v)$ are the subset of
neighbors of $v$ sampled from the distribution based on similarity and
diversity, respectively. We can combine these representations by
concatenating,
${\bm{h}}_{v}^{(i)}=\mathrm{MLP}({\bm{h}}_{v_{sim}}^{(i)}|{\bm{h}}_{v_{div}}^{(i)})$
or using skip connections,

(6)
$\displaystyle{\bm{h}}_{v}^{(i)}=\mathrm{MLP}(\sigma({\bm{W}}({\bm{h}}_{v_{sim}}^{(i)}|{\bm{h}}_{v_{div}}^{(i)})+{\bm{h}}_{v_{sim}}^{(i)}+{\bm{h}}_{v_{div}}^{(i)})).$

Figure 4. Computation graph with sample size $k=2$ and hop-size $2$. a), b)
samples from similarity and diversity ranking for a single channel, c) dual
channel with combined representation at the target node, and d) similar and
diverse weighted samples at each sampled node.

Combining representations at the root of the computation graph as shown in
Fig. 4c can be better than combining two different samples at each node of the
tree, as in Fig. 4d. This is to avoid overfitting and make it computationally
efficient. For transductive learning, as we have already precomputed the
probability distributions, the inference process works similarly to the
training phase. In inductive setting, we have to compute the probability
distribution over the neighbors of a node as described in section 3.1.

####  3.2.1. Other sampling strategies and models:

AGS can also be integrated into ACM-GCN (Luan et al., 2022) and other filter-
based spectral GNNs. At the start of the epoch, we sample $k$ neighbors of
each node from the similarity and diversity based distributions and construct
two sparse subgraphs. We can then use the subgraph based on similarity with a
low-pass filter and the subgraph based on diversity with a high-pass filter.
We can employ _graph sampling_ strategies (instead of node sampling), such as
weighted random walks, and use them with existing GNNs. We can also
incorporate heuristics by first computing edge-disjoint subgraphs and then
sampling a sparse subgraph. We call our graph sampling GNN AGS-GS, and its
details are provided in Appendix 9 for conciseness. We call AGS-GS-RW
(Appendix 9.1) the weighted random walk version, and call AGS-GS-Disjoint
(Appendix 9.2) the edge-disjoint subgraph-based sampling version). For the
downstream model, there is flexibility to adapt existing models like ChebNet
(He et al., 2022), GSAINT (Zeng et al., 2019), GIN (Xu et al., 2018a), GCN
(Kipf and Welling, 2016), and GAT (Veličković et al., 2017). We can also use
two separate GNNs in two separate channels.

###  3.3. Computation Complexity

The pre-computation of the probability distribution requires
$\mathcal{O}(fn\cdot d\log d)$ and $\mathcal{O}(fnd^{2})$ operations for
similarity and facility location based ranking, respectively. If the
similarity metric is required to be learned the added time complexity is
$\mathcal{O}(fm)$. The training and memory complexity depend on the usage of
underlying GNNs. Let the number of hidden dimensions ($H$) be fixed and equal
to $H=f$ for all $\ell$ layers. For Stochastic Gradient Descent (SGD)-based
approaches, let $b$ be the batch size, and $k$ be the number of sampled
neighbors per node. When a single channel is used, each node expands to
$k^{\ell}$ nodes in its computation graph, and requires $f^{2}$ operations to
compute the embedding (a matrix-vector multiplication) in every epoch.
Therefore, for $n$ nodes, the per epoch training time complexity is
$\mathcal{O}(nk^{\ell}f^{2})$. The memory complexity is
$\mathcal{O}(bk^{\ell}f+\ell f^{2})$, where The first term corresponds to the
space for storing the embedding, and the second term corresponds to storage
for all weights of neurons of size, ${\bm{W}}\in\mathbb{R}^{f\times f}$.

For single channel node sampling (Fig. 4a,b), the training and memory
complexity of AGS-GNN is similar to GSAGE. The training and memory
requirements are twice as much for dual channels using the same sampling size,
leaving the asymptotic bounds unchanged. However, for the dual channel with
computation graph scenario shown in Fig. 4d, where each node generates two
types of samples of size $k$, the per epoch computation complexity becomes
$\mathcal{O}(n2^{\ell}k^{\ell}f^{2})$. One way to ameliorate this cost is to
reduce the sample neighborhood size by half.

##  4\. Related Work

While Spatial GNNs focus on graph structure (topology) to develop aggregation
strategies, spectral GNNs leverage graph signal processing to design graph
filters. Spectral GNNs use low-pass and high-pass filters to extract low-
frequency and high-frequency signals adaptively for heterophilic graphs. ACM-
GCN (Luan et al., 2022) is one of the best-performing heterophilic GNNs that
uses adaptive channels with low-pass and high-pass filters. Recently, the
authors of (Xu et al., 2023) proposed an adaptive filter-based GNN, ALT, that
combines signals from two filters with complementary filter characteristics to
classify homophilic and heterophilic graphs. These methods perform well for
small heterophilic graphs but do not scale to large graphs. In the _spectral_
domain, AGS-GNN can be used in conjunction with these approaches by computing
feature-similarity and feature-diversity-based sparse graphs at first before
applying filters for large graphs.

For applying spatial GNNs to heterophilic graphs, rather than using average
aggregation (as in homophilic GNNs), edge-aware weights of neighbors can be
assigned according to the spatial graph topology and node labels. DMP (Yang et
al., 2021) considers node attributes as weak labels and aggregates element-
wise weights from neighbors. GGCN (Yan et al., 2022) uses cosine similarity to
create signed neighbor features; the intuition is to send positive attributes
to neighbors in the same class and negative ones to neighbors in different
classes. GPNN (Yang et al., 2022) considers ranking the neighbors based on
similarity and uses a 1D convolution operator on the sequential nodes. Another
related work is SimP-GCN (Jin et al., 2021), which computes the node
similarity and then chooses the top $k$ similar node pairs in terms of
feature-level cosine similarity for each ego node, and then constructs the
neighbor set using the $k$-NN algorithm. AGS-GNN, in contrast, uses
submodularity, node-similarity, reweighting, and sampling of the subgraph
instead of reconstructing neighbor sets.

When learned weight functions are considered, AGS-GNN can be placed into the
category of supervised sampling. LAGCN (Chen et al., 2020b) trains an edge
classifier from the existing graph topology, similar to our regression task of
weight approximation. NeuralSparse (Zheng et al., 2020) learns a
sparsification network to sample a $k$-neighbor subgraph (with a predefined
$k$), which is fed to GCN (Kipf and Welling, 2016), GraphSAGE (Hamilton et
al., 2017) or GAT (Veličković et al., 2017). Unlike our heuristic-based
sampler, NeuralSparse has end-to-end training of the sampler network and GNN,
and may require more iterations to find appropriate sampling probabilities.

There are only a few scalable GNNs for heterophilic graphs. The most notable
one is LINKX (Lim et al., 2021), which is transductive as the model
architecture depends on node size. A recent scalable GNN, LD2 (Liao et al.,
2023), attempts to remedy this by transforming the adjacency and the feature
matrix into embeddings as a pre-computation and then applying feature
transformation in a mini-batch fashion.

##  5\. Experiments

###  5.1. Dataset, Setup, and Methods

####  5.1.1. Dataset:

We experimented with $35$ graphs of different sizes and varying homophily. We
also generated synthetic graphs of different homophily and degrees while
retaining the node features for ablation studies and scaling experiments. We
considered the node classification task in our experiments. For heterophily
studies, we used: Cornell, Texas, Wisconsin (Pei et al., 2020); Chameleon,
Squirrel (Rozemberczki et al., 2021); Actor (Pei et al., 2020); Wiki, ArXiv-
year, Snap-Patents, Penn94, Pokec, Genius, Twitch-Gamers, reed98, amherst41,
cornell5, and Yelp (Lim et al., 2021). We also experiment on some recent
benchmark datasets, Roman-empire, Amazon-ratings, Mineswe-eper, Tolokers, and
Questions from (Platonov et al., 2023). We converted a few multi-label
multiclass classification problems (Flickr, AmazonProducts) to single-label
multiclass node classification, and their homophily values become relatively
small, making them heterophilic. For homophily studies we used Cora (Sen et
al., 2008); Citeseer (Giles et al., 1998); pubmed (Namata et al., 2012);
Coauthor-cs, Coauthor-physics (Shchur et al., 2018); Amazon-computers, Ama-
zon-photo (Shchur et al., 2018); Reddit (Hamilton et al., 2017); Reddit2 (Zeng
et al., 2019); and, dblp (Fu et al., 2020). Details of datasets, homophily
measures (Table 8), homophily distributions (Fig. 13, 14), origins, splits,
etc. (Table 9) are in Appendix 10.

####  5.1.2. Experimental Setup:

All evaluations are repeated $10$ times using a split of $60\%/20\%/20\%$
(train/validation/test), unless a specific split is specified. All experiments
are executed on 24GB NVIDIA A10 Tensor Core GPU. For all benchmark models, we
use the settings specified in their corresponding papers, and for AGS-GNN, we
use two message-passing layers ($\ell=2$) and a hidden layer with dimension
$H=256$. We use the Adam (Kingma and Ba, 2014) optimizer with a learning rate
of $10^{-3}$ and train for $250$ epochs or until convergence. A model
converges if the standard deviation of the training loss in the most recent
$5$ epochs (after at least $5$ epochs) is below $10^{-4}$. For node sampling,
we use a batch size of $512$ to $1024$ with $k=[25,10]$ or $[8,4]$ in the two
layers unless otherwise specified. For graph sampling, we use a batch size of
$6000$ and a random walk step size of $2$. For reporting accuracy, we select
the model that gives the best validation performance. Depending on the models,
we use a dropout probability of $0.2$ or $0.5$ during training. All of the
implementations are in PyTorch (Paszke et al., 2019), PyTorch Geometric (Fey
and Lenssen, 2019), and Deep Graph Library (DGL) (Wang et al., 2019). For
computing distribution based on submodular ranking, we use Apricot library
(Schreiber et al., 2020). We modified the Apricot code to make the
implementation more efficient. Source codes for all our implementations are
provided anonymously on GitHub111GitHub link for AGS-GNN and all other
methods..

####  5.1.3. Implemented Methods:

We consider graphs with ${\mathcal{H}}_{a}\leq 0.5$ to be heterophilic. The
small instances contain graphs with less than $100K$ nodes, and they fit in
the GPU memory. The larger instances are compared against only scalable
homophilic and heterophilic GNNs. We compare AGS-GNN (the Node Sampling AGS-NS
variant) with other Node Sampling methods (GSAGE (Hamilton et al., 2017)),
GraphSampling (GSAINT (Zeng et al., 2019)), and Heterophilic GNNs (LINKX (Lim
et al., 2021), ACM-GCN (Luan et al., 2022)). LINKX is used for only the small
graphs, where the entire graph fits into GPU memory. For large graphs, we used
the row-wise minibatching of the adjacency matrix (_AdjRowLoader_) for LINKX,
which is denoted by LINKX$+$. Since, most of the heterophilic GNNs require
entire graph and do not support mini-batching, we compare AGS-GNN with $18$
standard heterophilic and homophilic GNNs on small heterophilic graphs only.
Appendix 11.2 provides details on these method and results.

###  5.2. Key Results

(a) Small Heterophilic Graphs

(b) Small Homophilic Graphs

(c) Large Heterophilic Graphs

(d) Large Homophilic Graphs

Figure 5. Performance Profile: The X-axis shows the differences in
$F_{1}$-scores (scaled to 100) between the best algorithm for a specific
problem, and the Y-axis shows the fraction of the problems. We compare AGS to
two scalable homophilic GNNs (GSAGE, GSAINT) and two heterophilic GNNs (ACM-
GCN, LINKX). For small ($<100K$ vertices) and large ($\geq 100K$ vertices)
graphs, we consider LINKX (full-batch) and LINKX$+$ (mini-batch),
respectively. Full results are in Appendix 11.1.

In Fig. 5, we show the performance profile plot of the algorithms w.r.t. their
relative $F_{1}$-score. For each graph, we compute the relative $F_{1}$-score
for all algorithms by subtracting their $F_{1}$-score from the best one. Thus
the best performing algorithm for a problem receives a score of $0$, and for
all other algorithms the difference is positive. The X-axis of Fig. 5
represents these relative values from the best-performing algorithms across
the graph problems, and the Y-axis shows the fraction of problems that achieve
$F_{1}$-score within the bound on the difference specified by the X-axis
value. Thus, the performance plot reveals a ranking of the algorithms in terms
of their quality. The closer a curve (algorithm) is to the Y-axis, and the
smaller the difference in the X-axis, the better its performance w.r.t. other
algorithms across all the problems considered. Fig. 5a summarizes results from
five algorithms across $17$ test problems for small heterophilic graphs, where
we observe that AGS-NS performs the best or close-to-best for about half of
the problems and has up to $10\%$ lower $F_{1}$ scores compared to the best
algorithm for the other half. ACM-GCN performs similarly to AGS-NS for these
small graphs. While LINKX achieves comparable accuracies to AGS-NS for most of
the problems (about $80\%$), for a few problems it achieves lower $F_{1}$
scores.

For large heterophilic graphs (Fig. 5c), performance improvement for AGS-NS is
considerably better than all algorithms. LINKX$+$ performs second-best for
$75\%$ of the problems. In small homophilic graphs (Fig. 5b), AGS-NS and GSAGE
are the top two performers for most of the problems, followed by GSAINT, ACM-
GCN, and LINKX. This is expected since ACM-GCN and LINKX are tailored for
heterophilic graphs. In large homophilic graphs (Fig. 5d), AGS-NS is the best-
performing algorithm in terms of accuracy, followed by GSAGE. We also observe
from this figure that for homophilic graphs, LINKX$+$ is not competitive.

In Table. 15 (Appendix 11.2) we present performance of AGS-NS compared to $18$
recent competing algorithms on small heterophilic graphs. ACM-GCN, AGS-NS, and
LINKX remain the best-performing, with AGS-NS as the leading method for these
inputs. The full set of results with numerical values are provided in Appendix
(Tables 11, 12, 13, 14, 15). These tables present the mean ($\mu$) and
standard deviation ($\sigma$) of the runs. We use a one-tailed statistical
hypothesis $t$-test to verify whether one set of values is better than the
other. The better-performing results are highlighted in boldface.

###  5.3. Ablation study

We now investigate the contribution of individual components of AGS-GNN,
employing different sampling strategies and GNNs. For GNNs, we consider GSAGE
(_spatial_) and ChebNet (He et al., 2022) (_spectral_). We sample $\lfloor
d_{u}\cdot k^{\prime}\rfloor$ ($k^{\prime}\in[0,1]$) neighbors for each node
$u$ using _similarity_ and _diversity_ -based sparsification using precomputed
weights (detailed in section 3.2), and _random_ sparsification that selects a
subgraph uniformly at random. Only a _single_ sampled subgraph is used
throughout the training. For experiments, we generate three synthetic versions
of Cora with average degree $d=200$, keeping the original nodes and features
the same but changing the connectivity to have strong ($0.05$), moderate
($0.25$), and weak ($0.50$) heterophily. The distribution of heterophily for
each node is close to uniform. Table 1 shows that diversity-based selection
performs best with strong heterophily, and with spectral GNN, it even achieves
accuracy better than using the entire graph. In contrast, on moderate
heterophily, the similarity-based selection performs the best (even better
than the whole graph). For weak heterophily (homophily), similar and random
sparse perform alike. When we convert these into a sampling paradigm (node
sampling or graph sampling), similar behavior can be seen (Table 2) as we get
the best performance from diversity-based selection for strong heterophily and
similarity-based for moderate heterophily with a wide margin than random. For
weak heterophily or homophily, the similarity-based performs slightly better
than the random sampler.

Dataset | CoraSyn0.05 | CoraSyn0.25 | CoraSyn0.50
---|---|---|---
GNN | GSAGE | ChebNet | GSAGE | ChebNet | GSAGE | ChebNet
Sparse | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
Random | 57.08 | 0.46 | 56.44 | 0.14 | 61.85 | 0.94 | 62.14 | 1.29 | 92.09 | 0.79 | 92.48 | 0.72
Similar | 48.50 | 0.29 | 50.91 | 0.22 | 71.66 | 0.42 | 71.02 | 0.17 | 92.48 | 0.51 | 91.71 | 0.25
Diverse | 61.79 | 0.17 | 64.67 | 0.22 | 53.91 | 0.22 | 57.03 | 0.30 | 79.48 | 0.36 | 76.07 | 0.36
Whole | 63.67 | 0.43 | 62.79 | 0.25 | 69.49 | 0.38 | 67.61 | 0.22 | 96.94 | 0.08 | 96.47 | 0.14

Table 1. $F_{1}$ score of a single sparse subgraph keeping $\lfloor 0.25\cdot
d_{u}\rfloor$ neighbors of node $u$. Three synthetic versions of Cora are
produced ($d=200$ and ${\mathcal{H}}_{n}$ $0.05,0.25$, and $0.50$,
respectively).

Dataset | CoraSyn0.05 | CoraSyn0.25 | CoraSyn0.50
---|---|---|---
GNN | GSAGE | ChebNet | GSAGE | ChebNet | GSAGE | ChebNet
Sampler | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
Random | 59.20 | 0.22 | 57.50 | 0.80 | 62.85 | 0.55 | 61.67 | 0.46 | 91.06 | 0.36 | 88.89 | 1.32
Similar | 54.44 | 0.68 | 54.03 | 0.51 | 69.19 | 0.08 | 67.43 | 0.30 | 92.00 | 0.08 | 91.71 | 0.29
Diverse | 60.96 | 0.55 | 61.73 | 0.43 | 56.67 | 0.46 | 58.38 | 0.25 | 86.65 | 0.44 | 83.54 | 0.79

Table 2. $F_{1}$ score using different subgraph samples ($k=[25,25]$). Three
synthetic versions of Cora are produced ($d=200$ and ${\mathcal{H}}_{n}$
$0.05,0.25$, and $0.50$, respectively).

Since real-world graphs have nonuniform node homophily, we generated a
synthetic version of Cora where individual nodes have different local node
homophily in the range $[0.05,0.50]$. Table 3 shows that our proposed two
channel (one for homophily and one for heterophily) AGS-GNN performs the best,
significantly outperforming ACM-GCN and LINKX. Detailed studies on the
parameters and different submodular functions used in diversity-based sampling
are presented in Appendix 12.2.

ACM-GCN | LINKX | AGS (Sim. + Sim.) | AGS (Div. + Div.) | AGS (Sim. + Div.)
---|---|---|---|---
$\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
35.3394 | 0.6922 | 34.2081 | 0.7889 | 60.8145 | 0.7759 | 62.8394 | 0.8522 | 63.0317 | 0.5079

Table 3. $F_{1}$ Score of two-channel GNNs with a differently weighted sampler
in synthetic Cora graph with locally heterophilic and homophilic nodes mixed
(${\mathcal{H}}_{n}(u)=[0.05,0.50])$. Figure 6. Performance Profile: X-axis is
the difference in $F_{1}$-scores (scaled to 100) for different GNNs coupled
with AGS sampler on five benchmark heterophilic graphs.

We coupled our sampling strategy (both node sampling and graph sampling (§9))
to existing GNNs (GSAGE, ChebNet, GSAINT, GIN, GAT, and GCN) and evaluated
them on five heterophilic graphs (Reed98, Roman-empire, Actor, Minesweeper,
Tolokers). While detailed numerical values are provided in Table 16 in
Appendix 12, we summarize the key results as a performance profile in Fig. 6.
We observe that AGS with GSAGE, ChebNet, and GSAINT performed the best.

###  5.4. Experimental Runtime and Convergence

Table 4 shows per epoch training time of different methods under the same
settings. For large datasets such as Reddit, with single worker thread, our
current implementation of weighted sampling requires around $3$ times more
than the random sampling used in GSAGE due to the dual channels and a few
implementation differences with PyTorchGeometric. We plan to improve our
implementation next. Since our precomputation is embarrassingly parallel, we
can accelerate our algorithm by increasing the number of worker threads. Our
weighted random walk, is faster than the library implementation even for
sequential execution. Fig. 7 shows the number of epochs required to converge
for random sampling (GSAGE) and our weighted sampling (AGS-GNN). Using the
same settings, we see that AGS-GNN is more stable and requires fewer epochs on
average to converge than GSAGE.

Method | Settings | Reddit | Genius | Yelp
---|---|---|---|---
GSAGE |  $k$ = [25, 10], $b$ = 1024, $\ell$ = 2, H=256 | 5.47 | 2.16 | 7.71
GSAINT |  $b$ = 4096, rw, step = 2, $\ell$ = 2, H = 256 | 8.01 | 2.10 | 4.34
LINKX$+$ | random 100 parts, b = 2, H = 32 | 10.63 | 2.35 | 3.54
AGS-NS |  $k$ = [25, 10], b = 1024, $\ell$ = 2, H = 256 | 18.44 | 2.43 | 13.30
AGS-GS |  $b$ = 4096, wrw, step = 2, $\ell$ = 2, H = 256 | 5.90 | 1.72 | 4.06

Table 4. Average training time (seconds/epoch). rw and wrw refer to random
walk and weighted random walk, respectively.

Method | Settings | Reddit | Genius | Yelp
---|---|---|---|---
GraphSAINT | Norm Computation | 414.93 | 92.30 | 215.99
Similarity Ranking |  $k_{1}=$ 20%, $k_{2}=$ 20% | 60.03 | 6.00 | 41.20
Diversity Ranking |  $k_{1}=$ 20%, $k_{2}=$ 20% | 600.00 | 16.37 | 55.62
LearningSimilarity | H = 256, b = 10000 | 7.01 | 1.00 | 4.03

Table 5. Pre-computation time (seconds) of different components of AGS-GNN and
GSAINT with single worker thread. Figure 7. Num. of epochs for AGS-GNN and
GSAGE to converge.

##  6\. Conclusions

In this work, we proposed attribute-guided sampling that uses node features in
an unsupervised and supervised fashion. We have shown that through a biased
sampling of similar and diverse neighbors, we get improved performance in
homophilic graphs and can handle challenging heterophilic graphs. We verify
our claims through exhaustive experimentation on various benchmark datasets
and methods. A limitation of our work is the time required for submodular
optimization when the facility location function is used; the computation
complexity is higher for dense graphs. We will optimize implementations in our
future work. We will also build an end-to-end process for supervised sampling.

## References

  * (1)
  * Abu-El-Haija et al. (2019) Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In _International Conference on Machine Learning_. PMLR, 21–29.
  * Chen et al. (2020b) Hao Chen, Yue Xu, Feiran Huang, Zengde Deng, Wenbing Huang, Senzhang Wang, Peng He, and Zhoujun Li. 2020b.  Label-aware graph convolutional networks. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 1977–1980.
  * Chen et al. (2018a) Jie Chen, Tengfei Ma, and Cao Xiao. 2018a.  FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In _International Conference on Learning Representations_.
  * Chen et al. (2018b) Jianfei Chen, Jun Zhu, and Le Song. 2018b.  Stochastic Training of Graph Convolutional Networks with Variance Reduction. In _International Conference on Machine Learning_. PMLR, 942–950.
  * Chen et al. (2020a) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020a.  Simple and deep graph convolutional networks. In _International Conference on Machine Learning_. PMLR, 1725–1735.
  * Chiang et al. (2019) Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 2019.  Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 257–266.
  * Chicco (2021) Davide Chicco. 2021.  Siamese neural networks: An overview.  _Artificial neural networks_ (2021), 73–94.
  * Chien et al. (2020) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2020.  Adaptive universal generalized pagerank graph neural network.  _arXiv preprint arXiv:2006.07988_ (2020).
  * Ekambaram (2014) Venkatesan Nallampatti Ekambaram. 2014.  _Graph-structured data viewed through a Fourier lens_.  University of California, Berkeley.
  * Fey and Lenssen (2019) Matthias Fey and Jan Eric Lenssen. 2019.  Fast graph representation learning with PyTorch Geometric.  _arXiv preprint arXiv:1903.02428_ (2019).
  * Fu et al. (2020) Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. 2020.  Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In _Proceedings of The Web Conference 2020_. 2331–2341.
  * Gasteiger et al. (2018) Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2018.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ (2018).
  * Giles et al. (1998) C Lee Giles, Kurt D Bollacker, and Steve Lawrence. 1998.  CiteSeer: An automatic citation indexing system. In _Proceedings of the third ACM Conference on Digital Libraries_. 89–98.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016.  _Deep learning_.  MIT press.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs. In _Advances in Neural Information Processing Systems_. 1024–1034.
  * He et al. (2022) Mingguo He, Zhewei Wei, and Ji-Rong Wen. 2022.  Convolutional neural networks on graphs with chebyshev approximation, revisited.  _Advances in Neural Information Processing Systems_ 35 (2022), 7264–7276.
  * Huang et al. (2020) Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. 2020.  Combining label propagation and simple models out-performs graph neural networks.  _arXiv preprint arXiv:2010.13993_ (2020).
  * Huang et al. (2018) Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018.  Adaptive sampling towards fast graph representation learning.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Jin et al. (2021) Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. 2021.  Node similarity preserving graph convolutional networks. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_. 148–156.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Krause and Golovin (2014) Andreas Krause and Daniel Golovin. 2014.  Submodular function maximization.  _Tractability_ 3, 71-104 (2014), 3.
  * Li et al. (2022) Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022.  Finding global homophily in graph neural networks when meeting heterophily. In _International Conference on Machine Learning_. PMLR, 13242–13256.
  * Liao et al. (2023) Ningyi Liao, Siqiang Luo, Xiang Li, and Jieming Shi. 2023.  LD2: Scalable Heterophilous Graph Neural Network with Decoupled Embeddings. In _Thirty-seventh Conference on Neural Information Processing Systems_.  https://openreview.net/forum?id=7zkFc9TGKz
  * Lim et al. (2021) Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021.  Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.  _Advances in Neural Information Processing Systems_ 34 (2021), 20887–20902.
  * Liu et al. (2021) Meng Liu, Zhengyang Wang, and Shuiwang Ji. 2021.  Non-local graph neural networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 44, 12 (2021), 10270–10276.
  * Luan et al. (2022) Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2022.  Revisiting heterophily for graph neural networks.  _arXiv preprint arXiv:2210.07606_ (2022).
  * Luan et al. (2020) Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao-Wen Chang, and Doina Precup. 2020.  Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks.  _arXiv preprint arXiv:2008.08844_ (2020).
  * Minoux (1978) Michel Minoux. 1978.  Accelerated greedy algorithms for maximizing submodular set functions.  _Optimization Techniques_ (1978), 234–243.
  * Namata et al. (2012) Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. 2012.  Query-driven active surveying for collective classification. In _10th International Workshop on Mining and Learning with Graphs_ , Vol. 8. 1.
  * Nemhauser et al. (1978) George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions—I.  _Mathematical programming_ 14 (1978), 265–294.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ (2020).
  * Platonov et al. (2022) Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. 2022.  Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy.  _arXiv preprint arXiv:2209.06177_ (2022).
  * Platonov et al. (2023) Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2023.  A critical look at the evaluation of GNNs under heterophily: are we really making progress?  _arXiv preprint arXiv:2302.11640_ (2023).
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ 9, 2 (2021), cnab014.
  * Schreiber et al. (2020) Jacob Schreiber, Jeffrey Bilmes, and William Stafford Noble. 2020.  apricot: Submodular selection for data summarization in Python.  _The Journal of Machine Learning Research_ 21, 1 (2020), 6474–6479.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008.  Collective classification in network data.  _AI magazine_ 29, 3 (2008), 93–93.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018.  Pitfalls of graph neural network evaluation.  _arXiv preprint arXiv:1811.05868_ (2018).
  * Van Engelen and Hoos (2020) Jesper E Van Engelen and Holger H Hoos. 2020.  A survey on semi-supervised learning.  _Machine learning_ 109, 2 (2020), 373–440.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Wang et al. (2019) Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. 2019\.  Deep graph library: A graph-centric, highly-performant package for graph neural networks.  _arXiv preprint arXiv:1909.01315_ (2019).
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019.  Simplifying graph convolutional networks. In _International Conference on Machine Learning_. PMLR, 6861–6871.
  * Xu et al. (2018a) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018a.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * Xu et al. (2018b) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018b.  Representation learning on graphs with jumping knowledge networks. In _International Conference on Machine Learning_. PMLR, 5453–5462.
  * Xu et al. (2023) Zhe Xu, Yuzhong Chen, Qinghai Zhou, Yuhang Wu, Menghai Pan, Hao Yang, and Hanghang Tong. 2023.  Node Classification Beyond Homophily: Towards a General Solution. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 2862–2873.
  * Yan et al. (2022) Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2022.  Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In _2022 IEEE International Conference on Data Mining (ICDM)_. IEEE, 1287–1292.
  * Yang et al. (2021) Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, et al. 2021\.  Diverse message passing for attribute with heterophily.  _Advances in Neural Information Processing Systems_ 34 (2021), 4751–4763.
  * Yang et al. (2022) Tianmeng Yang, Yujing Wang, Zhihan Yue, Yaming Yang, Yunhai Tong, and Jing Bai. 2022.  Graph pointer neural networks. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 8832–8839.
  * Ye and Ji (2021) Yang Ye and Shihao Ji. 2021.  Sparse graph attention networks.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Zeng et al. (2019) Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019.  GraphSAINT: Graph Sampling Based Inductive Learning Method. In _International Conference on Learning Representations_.
  * Zheleva and Getoor (2009) Elena Zheleva and Lise Getoor. 2009.  To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles. In _Proceedings of the 18th International Conference on World Wide Web_. 531–540.
  * Zheng et al. (2020) Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. 2020.  Robust graph representation learning via neural sparsification. In _International Conference on Machine Learning_. PMLR, 11458–11468.
  * Zheng et al. (2022) Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022.  Graph neural networks for graphs with heterophily: A survey.  _arXiv preprint arXiv:2202.07082_ (2022).
  * Zhou et al. (2003) Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. 2003.  Learning with local and global consistency.  _Advances in Neural Information Processing Systems_ 16 (2003).
  * Zhu et al. (2021) Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2021.  Graph neural networks with heterophily. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 11168–11176.
  * Zhu et al. (2020) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in Neural Information Processing Systems_ 33 (2020), 7793–7804.

##  7\. Appendix: Preliminaries

###  7.1. Homophily of similarity-based selection

Let $t$ be an ego node of a graph with degree $d_{t}$, local node homophily
${\mathcal{H}}_{n}(t)$, and label $y_{t}$. From the definition of homophily,
the probability of selecting a neighbor $i\in{\mathcal{N}}(t)$ with the same
label as the ego node uniformly at random is
$P_{\mathcal{U}}(y_{i}=y_{t})={\mathcal{H}}_{n}(t)$, where ${\mathcal{U}}$
denotes to the distribution obtained by selecting a neighbor uniformly at
random. If features and labels correlate positively, and similarity is
computed from the features, we can expect the following assumption to be
valid:

###### Assumption 7.1.

For a node $t$, the average similarity of neighbors with the same label as $t$
is greater than or equal to the average similarity of all neighbors.

###### Lemma 7.1.

If the probability of selecting a neighbor is proportional to its similarity
to the ego node $t$, then the local node homophily of a sampled neighborhood
${\mathcal{H}}_{n}^{\prime}(t)\geq{\mathcal{H}}_{n}(t)$. If the sampling
probability distribution is ${\mathcal{S}}$ then
$P_{\mathcal{S}}(y_{i}=y_{t})\geq P_{\mathcal{U}}(y_{i}=y_{t})$.

###### Proof.

Consider an ego node $t=\\{{\bm{x}}_{t},y_{t}\\}$ where ${\bm{x}}_{t}$, and
$y_{t}$ are its feature and label, respectively. Let the feature and labels of
the neighboring nodes of $t$ be
${\mathcal{N}}(t)=\\{({\bm{x}}_{1},y_{1}),({\bm{x}}_{2},y_{2}),\cdots,({\bm{x}}_{d_{t}},y_{d_{t}})\\}$.

Let $s({\bm{x}}_{i},{\bm{x}}_{t})$ be a similarity function that measures how
similar the feature of a neighbor $x_{i}$ is to the feature of the ego node
${\bm{x}}_{t}$. This function returns a positive value, and higher values
indicate higher similarity.

A probability distribution with probability mass function $p_{\mathcal{S}}(i)$
assigns a probability to each neighbor $i$ based on its similarity to the ego
node. The distribution should satisfy the following properties:

  * •

$p_{\mathcal{S}}(i)\geq 0$ for all $i$;

  * •

$\sum_{i=1}^{d_{t}}p_{\mathcal{S}}(i)=1$;

  * •

$p_{\mathcal{S}}(i)$ is proportional to $s({\bm{x}}_{i},{\bm{x}}_{t})$. (An
example is
$p_{\mathcal{S}}(i)=\frac{s({\bm{x}}_{i},{\bm{x}}_{t})}{\sum_{j=1}^{d_{t}}s({\bm{x}}_{j},{\bm{x}}_{t})}$.)

Let $I(y_{i}=y_{t})$ be an indicator function that returns $1$ if
$y_{i}=y_{t}$ and $0$ otherwise. If a neighbor $i$ of a node $t$ is selected
randomly then $p_{\mathcal{U}}(i)=\frac{1}{d_{t}}$. Therefore the probability
of selecting a neighbor randomly having the same label as the ego node is

$\displaystyle P_{\mathcal{U}}(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}p_{\mathcal{U}}(i)\cdot I(y_{i}=y_{t}),$
$\displaystyle=\frac{1}{{d_{t}}}\cdot\sum_{i=1}^{d_{t}}I(y_{i}=y_{t}).$

If the selection probability is based on similarity, then

$\displaystyle P_{\mathcal{S}}(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}p_{\mathcal{S}}(i)\cdot I(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}\frac{s({\bm{x}}_{i},{\bm{x}}_{t})}{\sum_{j=1}^{d_{t}}s({\bm{x}}_{j},{\bm{x}}_{t})}\cdot
I(y_{i}=y_{t}).$

  * •

Let $n$ be the number of neighbors having the same label as ego node $t$,
i.e., $n=\sum_{i=1}^{d_{t}}I(y_{i}=y_{t})$.

  * •

Let $s_{t}$ be the sum of similarities of all neighbors having the same label
as $t$, i.e., $s_{t}=\sum_{i=1}^{d_{t}}(s({\bm{x}}_{i},{\bm{x}}_{t})\cdot
I(y_{i}=y_{t})$. Also let $s_{d}$ denote the sum of similarities of all
neighbors of $t$, then $s_{d}=\sum_{j=1}^{d_{t}}s({\bm{x}}_{j},{\bm{x}}_{t})$.

  * •

If the features and labels are positively correlated, the average similarity
of neighbors having the same label as the ego node should be higher than the
average similarity of all neighbors of the ego node. That is,
$\frac{s_{t}}{n}\geq\frac{s_{d}}{d_{t}}$.

We can now use these expressions and the substitutions shown below to derive
the result. From Assumption 7.1,

$\displaystyle\frac{s_{t}}{n}$ $\displaystyle\geq\frac{s_{d}}{d_{t}}$
$\displaystyle\frac{s_{t}}{s_{d}}$ $\displaystyle\geq\frac{n}{d_{t}}$
$\displaystyle\frac{1}{\sum_{j=1}^{d_{t}}s(x_{j},x_{t})}\sum_{i=1}^{d_{t}}s({\bm{x}}_{i},{\bm{x}}_{t})\cdot
I(y_{i}=y_{t})$
$\displaystyle\geq\frac{1}{d_{t}}\cdot\sum_{i=1}^{d_{t}}I(y_{i}=y_{t})$
$\displaystyle\sum_{i=1}^{d_{t}}\frac{s({\bm{x}}_{i},{\bm{x}}_{t})}{\sum_{j=1}^{d_{t}}s({\bm{x}}_{j},{\bm{x}}_{t})}\cdot
I(y_{i}=y_{t})$ $\displaystyle\geq\sum_{i=1}^{d_{t}}\frac{1}{{d_{t}}}\cdot
I(y_{i}=y_{t})$ $\displaystyle\sum_{i=1}^{d_{t}}p_{\mathcal{S}}(i)\cdot
I(y_{i}=y_{t})$ $\displaystyle\geq\sum_{i=1}^{d_{t}}p_{\mathcal{U}}(i)\cdot
I(y_{i}=y_{t})$ $\displaystyle P_{\mathcal{S}}(y_{i}=y_{t})$
$\displaystyle\geq P_{\mathcal{U}}(y_{i}=y_{t})$
$\displaystyle{\mathcal{H}}_{n}^{\prime}(t)$
$\displaystyle\geq{\mathcal{H}}_{n}(t).$

∎

###  7.2. Homophily of diversity-based selection

A submodular function is a set valued function that assigns a value to every
subset of a ground set that satisfies the diminishing returns property, i.e.,
for two subsets $S$, $T$ with $S\subseteq T$ of a ground set $A$, and any
element $e\in A\setminus T$,

$f(S\cup{e})-f(S)\geq f(T\cup{e})-f(T).$

The quantity on either side of the inequality is the _marginal gain_. An
example of a submodular function is the facility location function

(7) $f(S,A)=\sum\limits_{y\in A}\max_{x\in S}\phi(x,y),$

where $S$ and $A$ are as above and $\phi$ is a similarity measure on the
elements of $A$. The facility location function can be maximized by a Greedy
algorithm, which starts with the empty subset and iteratively adds an element
that gives the largest marginal gain to the function value until a cardinality
(or other) constraint on $S$ is reached.

In this context, $S$ is the current set of selected nodes initialized with ego
node $t$, and ground set $A={\mathcal{N}}(t)\cup\\{t\\}$. The marginal gain is
$f_{i}=f(S\cup\\{i\\},A)-f(S,A)$ for each neighbor
$i\in{\mathcal{N}}(t)\setminus S$. The neighbors are iteratively added based
on marginal gain. If node features and labels are positively correlated, then
we can expect the following assumption to be valid:

###### Assumption 7.2.

The average marginal gain of the neighbors of a node $t$ with the same label
as $t$ is less than or equal to the average marginal gain of all neighbors.

###### Lemma 7.2.

If the probability of selecting a neighbor of the ego node $t$ is proportional
to the marginal gain of the neighbor, then the local node homophily of a
sampled neighborhood ${\mathcal{H}}_{n}^{\prime}(t)\leq{\mathcal{H}}_{n}(t)$.
If the sampling probability distribution is ${\mathcal{D}}$ then
$P_{\mathcal{D}}(y_{i}=y_{t})\leq P_{\mathcal{U}}(y_{i}=y_{t})$.

###### Proof.

Let the probability mass function of the distribution ${\mathcal{D}}$ be
proportional to the marginal gain value,
$p_{\mathcal{D}}(i)=\frac{f_{i}}{\sum_{j=1}^{{d_{t}}}f_{j}}$. The higher the
marginal gain, the higher is the selection probability.

If a neighbor is selected randomly, then $p_{\mathcal{U}}(i)=\frac{1}{d_{t}}$.
Therefore, the probability of selecting a neighbor randomly having the same
label as the ego node is

$\displaystyle P_{\mathcal{U}}(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}p_{\mathcal{U}}(i)\cdot I(y_{i}=y_{t})$
$\displaystyle=\frac{1}{{d_{t}}}\cdot I(y_{i}=y_{t}).$

If the selection probability is based on diversity, then

$\displaystyle P_{\mathcal{D}}(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}p_{\mathcal{D}}(i)\cdot I(y_{i}=y_{t})$
$\displaystyle=\sum_{i=1}^{d_{t}}\frac{f_{i}}{\sum_{j=1}^{d_{t}}f_{j}}\cdot
I(y_{i}=y_{t}).$

  * •

As in the earlier subsection, let $n$ be the number of neighbors having the
same label as the ego node $t$, i.e., $n=\sum_{i=1}^{d}I(y_{i}=y_{t})$.

  * •

Let $m_{t}$ be the sum of marginal gains of all neighbors having the same
label as $t$, i.e., $m_{t}=\sum_{i=1}^{d_{t}}(f_{i})\cdot I(y_{i}=y_{t})$, and
let $m_{d}$ denote the sum of all marginal gains of the neighbors
$m_{d}=\sum_{j=1}^{d_{t}}f_{j}$.

  * •

If the features and labels are positively correlated, the average marginal
gains of neighbors having the same label as the ego node should be less than
or equal to the average marginal gains of all neighbors of the ego node. Hence
$\frac{m_{t}}{n}\leq\frac{m_{d}}{{d_{t}}}$.

We use the above expressions and the substitutions shown below get the desired
result. From Assumption 7.2,

$\displaystyle\frac{m_{t}}{n}$ $\displaystyle\leq\frac{m_{d}}{{d_{t}}}$
$\displaystyle\frac{m_{t}}{m_{d}}$ $\displaystyle\leq\frac{n}{{d_{t}}}$
$\displaystyle\frac{1}{\sum_{j=1}^{d}f_{j}}\sum_{i=1}^{d_{t}}f_{i}\cdot
I(y_{i}=y_{t})$
$\displaystyle\leq\frac{1}{{d_{t}}}\cdot\sum_{i=1}^{d}I(y_{i}=y_{t})$
$\displaystyle\sum_{i=1}^{d_{t}}\frac{f_{i}}{\sum_{j=1}^{d_{t}}f_{j}}\cdot
I(y_{i}=y_{t})$ $\displaystyle\leq\sum_{i=1}^{d_{t}}\frac{1}{{d_{t}}}\cdot
I(y_{i}=y_{t})$ $\displaystyle\sum_{i=1}^{d_{t}}p_{\mathcal{D}}(i)\cdot
I(y_{i}=y_{t})$ $\displaystyle\leq\sum_{i=1}^{d_{t}}p_{\mathcal{U}}(i)\cdot
I(y_{i}=y_{t})$ $\displaystyle P_{\mathcal{D}}(y_{i}=y_{t})$
$\displaystyle\leq P_{\mathcal{U}}(y_{i}=y_{t})$
$\displaystyle{\mathcal{H}}_{n}^{\prime}(t)$
$\displaystyle\leq{\mathcal{H}}_{n}(t).$

∎

###  7.3. Empirical verification of the Lemmas

Fig. 8 empirically verifies our assumptions that a subgraph selected from a
similar neighborhood increases the homophily, and selecting a diverse
neighborhood using a submodular function decreases homophily, relative to the
values in the original graph. For each vertex $u$, we take $\lfloor d_{u}\cdot
k^{\prime}\rfloor$ ($k^{\prime}\in[0,1]$) neighbors based on the ranking from
similarity and diversity and compare against random selection.

Figure 8. Empirical homophily comparison of different sampled subgraphs
keeping $\lfloor 0.25\cdot d_{u}\rfloor$ neighbors of node $u$. The synthetic
graphs are from squirrel with $d=42$. The figure shows that similar neighbors
increase ${\mathcal{H}}_{n}$, diverse samples obtained from a submodular
function decrease ${\mathcal{H}}_{n}$, and random selection keeps
${\mathcal{H}}_{n}$ the same as in the original graph.

###  7.4. High-Pass and Low-Pass Filters for GNN

We consider the following heterophilic graph in Fig. 9 to demonstrate how
_high-pass_ filters can help in node classification in heterophilic graphs.
Assume a heterophilic graph ${\mathcal{G}}$ has $18$ nodes of five different
classes where nodes in the range $[0,14]$ are locally heterophilic and
$[15,17]$ are locally homophilic. We assume the graph’s node feature
${\bm{X}}$ be the one-hot encoding of labels, thus the features and labels are
(perfectly) correlated. This is to show how _low-pass_ and _high-pass_ filters
perform in an ideal scenario with heterophily.

Figure 9. A heterophilic graph to demonstrate the performance of high-pass and
low-pass filter. Here, nodes $0-14$ are locally heterophilic, and nodes
$15-17$ are locally homophilic. In the figure, vertices with the same color
correspond to the same class label. ${\bm{X}}=\begin{bmatrix}1&0&0&0&0\\\
1&0&0&0&0\\\ 1&0&0&0&0\\\ 1&0&0&0&0\\\ 1&0&0&0&0\\\ 1&0&0&0&0\\\ 0&1&0&0&0\\\
0&1&0&0&0\\\ 0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&1&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&1&0\\\ 0&0&0&1&0\\\ 0&0&0&0&1\\\ 0&0&0&0&1\\\ 0&0&0&0&1\\\
\end{bmatrix}$

In the graph convolution step, the feature information of the neighbors gets
aggregated with the ego node. So, we get different transformed representations
of features depending on the representation of the underlying graph. For this
example, we use a symmetric normalized adjacency matrix, ${\bm{A}}_{sym}$ as a
low-pass filter and a symmetric normalized graph Laplacian, ${\bm{L}}_{sym}$
as a high-pass filter (Ekambaram, 2014). These filters are defined as,

$\displaystyle{\bm{A}}_{sym}$
$\displaystyle={\bm{D}}^{-\frac{1}{2}}{\bm{A}}{\bm{D}}^{-\frac{1}{2}}$
$\displaystyle{\bm{L}}_{sym}$
$\displaystyle={\bm{I}}-{\bm{D}}^{-\frac{1}{2}}{\bm{A}}{\bm{D}}^{-\frac{1}{2}}$

If self-loops are added, then,

$\displaystyle\bar{{\bm{A}}}$ $\displaystyle={\bm{A}}+{\bm{I}}$
$\displaystyle\bar{{\bm{A}}}_{sym}$
$\displaystyle=\bar{{\bm{D}}}^{-\frac{1}{2}}\bar{{\bm{A}}}\bar{{\bm{D}}}^{-\frac{1}{2}}$
$\displaystyle\bar{{\bm{L}}}_{sym}$
$\displaystyle={\bm{I}}-\bar{{\bm{D}}}^{-\frac{1}{2}}\bar{{\bm{A}}}\bar{{\bm{D}}}^{-\frac{1}{2}}$

Graphs under heterophily may perform well if the node features of the
neighbors make two heterophilic nodes similar after aggregation. To evaluate
this, we first compute aggregated feature information based on the filters and
then inspect pairwise similarities.

$\displaystyle S({\bm{A}},{\bm{X}})$
$\displaystyle={\bm{A}}{\bm{X}}({\bm{A}}{\bm{X}})^{T}$ $\displaystyle
S(\bar{{\bm{A}}}_{sym},{\bm{X}})$
$\displaystyle=\bar{{\bm{A}}}_{sym}{\bm{X}}(\bar{{\bm{A}}}_{sym}{\bm{X}})^{T}$
$\displaystyle S(\bar{{\bm{L}}}_{sym},{\bm{X}})$
$\displaystyle=\bar{{\bm{L}}}_{sym}{\bm{X}}(\bar{{\bm{L}}}_{sym}{\bm{X}})^{T}$

In these matrices, for a particular node $u$, if the average similarity of
nodes with the same label as $y_{u}$ is greater than the average similarity of
the nodes not having the same label as $y_{u}$, then we can expect that node
to be appropriately classified (Definition 2 and Theorem 1 in (Luan et al.,
2022)).

V/V | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 | 0.59 | 0.59 | 0.59 | 0.12 | 0.12 | 0.12 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.16 | -0.16 | -0.16
1 | 0.59 | 0.59 | 0.59 | 0.12 | 0.12 | 0.12 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.16 | -0.16 | -0.16
2 | 0.59 | 0.59 | 0.59 | 0.12 | 0.12 | 0.12 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.3 | -0.16 | -0.16 | -0.16
3 | 0.12 | 0.12 | 0.12 | 0.04 | 0.04 | 0.04 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.04 | -0.04 | -0.04
4 | 0.12 | 0.12 | 0.12 | 0.04 | 0.04 | 0.04 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.04 | -0.04 | -0.04
5 | 0.12 | 0.12 | 0.12 | 0.04 | 0.04 | 0.04 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.06 | -0.04 | -0.04 | -0.04
6 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
7 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
8 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
9 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
10 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
11 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
12 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
13 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
14 | -0.3 | -0.3 | -0.3 | -0.06 | -0.06 | -0.06 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
15 | -0.16 | -0.16 | -0.16 | -0.04 | -0.04 | -0.04 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.1 | 0.1 | 0.1
16 | -0.16 | -0.16 | -0.16 | -0.04 | -0.04 | -0.04 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.1 | 0.1 | 0.1
17 | -0.16 | -0.16 | -0.16 | -0.04 | -0.04 | -0.04 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.1 | 0.1 | 0.1

Table 6. $\bar{{\bm{A}}}={\bm{A}}+{\bm{I}}$, Graph Laplacian
$\bar{{\bm{L}}}_{sym}={\bm{I}}-\bar{{\bm{D}}}^{-\frac{1}{2}}\bar{{\bm{A}}}\bar{{\bm{D}}}^{-\frac{1}{2}}$,
and the pairwise similarity weight after aggregation is,
$S(\bar{{\bm{L}}}_{sym},{\bm{X}})=\bar{{\bm{L}}}_{sym}{\bm{X}}(\bar{{\bm{L}}}_{sym}{\bm{X}})^{T}$.
The highlighted values show that this high-pass filter can properly classify
heterophilic nodes. Here, nodes $0-2$ are mapped in the same space and have
high similarity weight since they have the same dissimilar neighborhood.

V/V | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 | 0.5 | 0.5 | 0.5 | 0.36 | 0.36 | 0.36 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.25 | 0.25 | 0.25
1 | 0.5 | 0.5 | 0.5 | 0.36 | 0.36 | 0.36 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.25 | 0.25 | 0.25
2 | 0.5 | 0.5 | 0.5 | 0.36 | 0.36 | 0.36 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.25 | 0.25 | 0.25
3 | 0.36 | 0.36 | 0.36 | 0.62 | 0.62 | 0.62 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.16 | 0.16 | 0.16
4 | 0.36 | 0.36 | 0.36 | 0.62 | 0.62 | 0.62 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.16 | 0.16 | 0.16
5 | 0.36 | 0.36 | 0.36 | 0.62 | 0.62 | 0.62 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | 0.16 | 0.16 | 0.16
6 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
7 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
8 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
9 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
10 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
11 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.08 | 0.08 | 0.08 | 0.06 | 0.06 | 0.06
12 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
13 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
14 | 0.28 | 0.28 | 0.28 | 0.23 | 0.23 | 0.23 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.33 | 0.33 | 0.33 | 0.06 | 0.06 | 0.06
15 | 0.25 | 0.25 | 0.25 | 0.16 | 0.16 | 0.16 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.6 | 0.6 | 0.6
16 | 0.25 | 0.25 | 0.25 | 0.16 | 0.16 | 0.16 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.6 | 0.6 | 0.6
17 | 0.25 | 0.25 | 0.25 | 0.16 | 0.16 | 0.16 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.6 | 0.6 | 0.6

Table 7. $\bar{{\bm{A}}}={\bm{A}}+{\bm{I}}$, Symmetric normalized adjacency
matrix of ${\mathcal{G}}$,
$\bar{{\bm{A}}}_{sym}=\bar{{\bm{D}}}^{-\frac{1}{2}}\bar{{\bm{A}}}\bar{{\bm{D}}}^{-\frac{1}{2}}$,
and the pairwise similarity weight after aggregation is,
$S(\bar{{\bm{A}}}_{sym},{\bm{X}})=\bar{{\bm{A}}}_{sym}{\bm{X}}(\bar{{\bm{A}}}_{sym}{\bm{X}})^{T}$.
The highlighted values show that this low-pass filter cannot properly classify
heterophilic nodes. Here, nodes $0-2$ have positive similarity weights to all
other nodes.

In AGS-GNN based sampler, along with similarity based sampling, we also sample
the neighborhood of vertices based on feature diversity. The feature
diversity-based sampler will attempt to create the same diverse neighborhood
of two heterophilic nodes, thus potentially mapping in the same vector space.
In a low-pass filter, however, the neighboring nodes of the same label as the
ego node with similar features help to map them in the same space; therefore,
the feature-similarity-based sampler will work in conjunction with the low-
pass filter. AGS-GNN uses a dual channel of feature-similar and feature-
diverse samples for each node in the graph and adaptively learns a better
representation.

##  8\. Appendix: Additional Details on AGS-GNN

###  8.1. Probability Mass Functions

Fig. 10 shows some possible Probability Mass Functions that take the rank of
neighbors as input and return weights for sampling probabilities.

Figure 10. Probability Mass Functions (PMFs) for weights used later for
selection probabilities

###  8.2. Computation of sampling probability for similar samples

Algorithm 2 shows how the similarity based sampling algorithm with the _step_
function is used to rank and pre-compute the probability distribution. Here we
can use any known similarity functions or a learned function. The pseudocode
shows how step functions with three different selection probabilities are used
to compute sampling probabilities.

1

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Similarity function ${\mathcal{S}}$,
Probability Mass Function, ${\mathcal{P}}$

2

3

1: if ${\mathcal{P}}=\mathrm{{}^{\prime}step^{\prime}}$ then

2:
$\mathrm{k_{1}=params[^{\prime}k_{1}^{\prime}],k_{2}=params[^{\prime}k_{2}^{\prime}]}$

3:
$\mathrm{\lambda_{1}=params[^{\prime}\lambda_{1}^{\prime}],\lambda_{2}=params[^{\prime}\lambda_{2}^{\prime}],\lambda_{3}=params[^{\prime}\lambda_{3}^{\prime}]}$

44: end if

5: for $u\in{\mathcal{V}}$ do

6: ${\mathcal{N}}(u)$ is the neighbors of $u$

57: Similarity from $u$ to its neighbor,
$S_{u}=\mathrm{{\mathcal{S}}({\bm{X}}[u],{\bm{X}}[{\mathcal{N}}(u)])}$

8: $\mathrm{top_{k1}=\lfloor k_{1}\times|{\mathcal{N}}(u)|\rfloor}$

9: $\mathrm{top_{k2}=\lfloor k_{2}\times|{\mathcal{N}}(u)|\rfloor}$

610: $\mathrm{l=|{\mathcal{N}}(u)|-top_{k1}-top_{k2}}$

711: Partition the similarities at $\mathrm{top_{k1},top_{k2}}$ position in
descending order of $S_{u}$ and rank them

12: Weight $\mathrm{W_{u,v}=\lambda_{1}}$ to $\mathrm{top_{k1}}$ neighbors,
$v\in{\mathcal{N}}(u)$

13: Weight $\mathrm{W_{u,v}=\lambda_{2}}$ to next $\mathrm{top_{k2}}$,
$v\in{\mathcal{N}}(u)$

814: Weight $\mathrm{W_{u,v}=\lambda_{3}}$ to residual $l$ neighbors,
$v\in{\mathcal{N}}(u)$

15: Sampling probability of an edge,
$P_{u,v}=W_{u,v}/\sum_{v\in{\mathcal{N}}(u)}W_{u,v}$

16: end for

17: return $P$

Algorithm 2
RankBySimilarity(${\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}},\mathrm{*params}$)

###  8.3. Computation of sampling probability for diverse samples

We can use submodular functions to rank the neighbors of a vertex. Multiple
submodular functions are available for finding a useful subset from a larger
set; e.g., ‘MaxCoverage‘, ‘FeatureBased‘, ‘GraphBased‘, ‘FacilityLocation‘,
etc. Algorithm 3 shows the pseudocode for computing sampling probabilities
using ranking by diversity. Algorithm 4 shows the pseudocode of a simplified
Lazy Greedy algorithm using the facility location function. For distance
measures such as ‘Euclidean‘, distance.max()-distance is used to convert into
similarity measure. Note that the ego node $u$ is already taken as an initial
set for submodular selections, and the remaining nodes are to be selected from
the neighbors.

1

2

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Similarity function ${\mathcal{S}}$,
Probability Mass Function, ${\mathcal{P}}$

3

1: for $u\in{\mathcal{V}}$ do

2: ${\mathcal{N}}(u)$ is the neighbors of $u$

3: Ranks,
$\mathrm{R_{u}=LazyGreedy({\mathcal{N}}(u),u,X_{u}|X_{{\mathcal{N}}(u)})}$

4: Assign weights $W_{u,v}$ for $v\in{\mathcal{N}}(u)$ from the ranks $R_{u}$
using ${\mathcal{P}}$.

5: Sampling probability of neighbors,
$P_{u,v}=W_{u,v}/\sum_{v\in{\mathcal{N}}(u)}W_{u,v}$

6: end for

7: return $P$

Algorithm 3 RankByDiversity
(${\mathcal{G}},{\bm{X}},{\mathcal{V}},{\mathcal{S}},{\mathcal{P}},\mathrm{*params}$)

1

2

Input : ${\mathcal{N}}(u)$ is the neighbors of ego node $u$,
${\bm{X}}^{\prime}\in\mathbb{R}^{|{\mathcal{N}}(u)\cup\\{u\\}|}$ is the
feature of ${\mathcal{N}}(u)\cup\\{u\\}$, Similarity function ${\mathcal{S}}$

3

4

1:
$\mathrm{kernel=compute\\_pairwise\\_similarity({\bm{X}}^{\prime},{\mathcal{S}})}$

2: Initial set, $S=\\{u\\}$

3: Ground set, $Y$ = $\\{u\\}\cup{\mathcal{N}}(u)$

54: Gain of set $S$ is $\mathrm{S_{gain}=Gain(S,Y,kernel)}$ {Eq.7 is used}

65: Initialize max-heap $H$, where key is the marginal gain w.r.t $S$ and the
element is neighboring vertex $v$

6: while $H\neq\emptyset$ do

7: $\mathrm{(gain,v)=H.pop()}$

8: $\mathrm{gain_{v}=Gain(S\cup\\{v\\},Y,kernel)-S_{gain}}$

9: $\mathrm{(gain_{2},\cdot)=H.top()}$

10: if $\mathrm{gain_{v}\geq gain_{2}}$ then

11: $\mathrm{S=S\cup\\{v\\}}$

12: $\mathrm{S_{gain}=Gain(S,Y,kernel)}$

13: else

14: $\mathrm{H.push(gain_{v},v)}$

15: end if

716: end while

17: Rank the vertices by marginal gain, $\mathrm{R_{u}=Rank(S)}$

818: return $R_{u}$

Algorithm 4 LazyGreedy (${\mathcal{N}}(u),u,{\bm{X}}^{\prime},{\mathcal{S}}$)

Ablation studies on different submodular functions are provided in Appendix
12.2, and more details on functions and implementations are provided in
Apricot (Schreiber et al., 2020) (url). Similar to the pseudocode of
RankBySimilarity in Algorithm 2, we can also use a step function to reduce
computation complexity by ranking only the top few items.

###  8.4. Training and inference of a similarity learning model

We use the Siamese (Chicco, 2021) model to predict the edge weights given two
node features. Here are simplified equations showing the architecture used for
the regression task of edge weight predictions.

The network can be described by

$\displaystyle\mathrm{mlp_{1}}$ $\displaystyle=\mathrm{MLP}(f,H_{1}),$
$\displaystyle\mathrm{mlp_{2}}$ $\displaystyle=\mathrm{MLP}(H_{1},H_{2}),$
$\displaystyle\mathrm{mlp_{3}}$ $\displaystyle=\mathrm{MLP}(2*H_{2},1).$

The forward propagation is described by

$\displaystyle{\bm{x}}_{1}$
$\displaystyle=\sigma_{1}(\mathrm{mlp_{2}}(\sigma_{1}(\mathrm{mlp_{1}}({\bm{x}}_{u}))))$
$\displaystyle{\bm{x}}_{2}$
$\displaystyle=\sigma_{1}(\mathrm{mlp_{2}}(\sigma_{1}(\mathrm{mlp_{1}}({\bm{x}}_{v}))))$
$\displaystyle{\bm{x}}$
$\displaystyle=\sigma_{2}(\mathrm{mlp_{3}}({\bm{x}}_{1}-{\bm{x}}_{2}|{\bm{x}}_{1}\times{\bm{x}}_{2})).$

Here MLP corresponds to Multi-Layer Perceptron or linear neural network
layers, $\sigma_{1}$ refers to _ReLU_ activation function, and $\sigma_{2}$ is
_Sigmoid_ for predicting edge weight between $0$ to $1$. The _MSELoss_
function is used as an optimization function.

1

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Label ${\bm{y}}\in{\mathbb{Y}}^{n}$

2

3

41: Extract the training subgraph, ${\mathcal{G}}^{\prime}$, containing
training vertices only.

52: Initialize a model, $\mathrm{SIM_{{\bm{W}}}}$

3: while condition do

4: Batch $B$ contains an equal number of edges and non-edges in the
${\mathcal{G}}^{\prime}$

5: Target label, $T=[(y_{u}=y_{v}):(u,v)\in B]$

6: Train, $\mathrm{SIM_{{\bm{W}}}}$ using $B,T$

67: end while

8: Get edge weight,
$\mathrm{{\mathcal{E}}^{\prime}=SIM_{{\bm{W}}}({\mathcal{E}})}$

9: return $\mathrm{SIM_{{\bm{W}}}},{\mathcal{E}}^{\prime}$

Algorithm 5 LearnSimilarity (${\mathcal{G}},{\bm{X}},{\bm{y}}$)

Algorithm 5 shows the training process for the regression task of predicting
edge weights between $0$ and $1$. We form a mini-batch by sampling an equal
number of edges and non-edges from the training subgraph. The target labels
are computed using the labels of each endpoint of the edges. For a few
training nodes, training subgraphs mostly contain isolated vertices. In such a
scenario, we can construct a new graph where all training nodes with the same
class are connected and use that for training purposes.

##  9\. Appendix: AGS-GS: AGS-GNN with Graph Sampling

This section covers how feature-similarity and feature-diversity-based
samplers can be used in graph sampling. The graph sampling paradigm is
significantly faster than node sampling since it avoids neighborhood
expansions.

###  9.1. AGS-GS-RW: Graph Sampling with Random Walk

A simple way to perform graph sampling is to use weighted random walks on the
precomputed graphs, as shown in Fig. 11.

(a) Weighted Random walk Figure 11. Graph Sampling using Weighted Random walk.
The weights for sampling are computed based on the ranks by similarity and
diversity.

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Label, ${\bm{y}}\in{\mathbb{Y}}^{n}$

1: ${\mathcal{S}}=\mathrm{LearnSimilarity({\mathcal{G}},{\bm{X}},{\bm{y}})}$
/* model for feature similarity, if an appropriate function not known, Alg. 5
*/

2: ${\mathcal{P}}=\mathrm{{}^{\prime}step^{\prime}}$ /* probability mass
function */

1

3:
$\mathrm{R_{1}=RankBySimilarity({\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}})}$
/* Algorithm 2 */

2

4:
$\mathrm{R_{1}=RankByDiversity({\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}})}$
/* Algorithm 3 */

3

5: for $\mathrm{epoch}$ in $\mathrm{num\\_epochs}$ do

6: $\mathrm{nodes=BatchOfSeedNodes({\mathcal{G}})}$ /* random nodes from
${\mathcal{V}}$ */

7: $\mathrm{g_{1}=SubgraphSample(R_{1},nodes)}$ /* for homophily */

8: $\mathrm{g_{2}=SubgraphSample(R_{2},nodes)}$ /* for heterophily */

9:

10: \- /* take output for homophilic GNN, heterophilic GNN, and combined
representation */

$\mathrm{out_{g_{1}},out_{g_{2}},out_{com}=GNN_{{\bm{W}}}(g_{1},g_{2})}$

11: $l_{1}=\mathrm{loss(out_{g_{1}},{\bm{y}}[g_{1}.train])}$

12: $l_{2}=\mathrm{loss(out_{g_{2}},{\bm{y}}[g_{1}.train])}$

13: $l_{3}=\mathrm{loss(out_{com},{\bm{y}}[nodes.train])}$

414: $l=l_{1}+l_{2}+l_{3}$

15: Backpropagate from $l$ and update ${\bm{W}}$

16: end for

Algorithm 6 AGS-GS-RW (${\mathcal{G}},{\bm{X}},{\bm{y}}$) [Weighted Random
Walk]

Algorithm 6 shows the pseudocode when the weighted random walk is performed.
Here for a minibatch we first generate random seed nodes from ${\mathcal{V}}$
and then start the random walk of $k$ steps from these nodes to generate
subgraphs. If we use a single channel, the training process can be similar to
GSAINT. However, if two channels are used, the nodes of sampled subgraphs from
two random walks will differ, and there are a few choices to compute loss:

  1. (i)

Only compute the loss of training nodes from the seed nodes.

  2. (ii)

Compute loss from common training nodes of the two sampled subgraphs.

  3. (iii)

Combine the loss of training nodes from seed nodes, training nodes of the
first and second subgraphs

During inference, we can sample two subgraphs starting from the test nodes and
check predictions from the combination network.

###  9.2. AGS-GS-Disjoint: AGS-GNN with edge-disjoint subgraph sampling

####  9.2.1. Edge Disjoint Sparse Graph for Graph Sampling

We can use the pre-computed weighted graph from Section 3.1 and go one step
further in graph sampling and incorporate some heuristics into the sampling
process. To do this, we take some high-quality sparse subgraphs with unique
properties and compute edge-disjoint subgraphs. Subgraph selection examples
include Spanning Trees, $k$-Nearest Neighbor, $b$-matching subgraph, and
Spectral Sparsifier. Algorithm 7 shows the process of computing edge-disjoint
subgraphs and their corresponding weights. Note that the weight of the
residual subgraph is set to zero.

Consider the heuristic of ensuring connectivity among sampled nodes. We
compute $k$-edge-disjoint Maximum Spanning Trees (MSTs) for a graph, sample a
few of them, and combine these subgraphs to get a sparse representation of the
original graph. Note that the best-quality sparse graphs will be in in the
order of selection when similarity and diversity-based edge weights are
considered for edge-disjoint subgraph computation. Therefore, the importance
of the sparse graph quality should also be considered in the sparse graph
sampling. Fig. 12 shows how an edge-disjoint subgraph can be used to sample a
sparse representation. In the example scenario, the original graph
${\mathcal{G}}$ is split into $k=4$ edge-disjoint subgraphs
$\\{(g_{1},w_{1}),(g_{1},w_{1}),(g_{1},w_{1}),(g_{4},w_{4})\\}$. The $w_{i}$
is the weight of the subgraph used for sampling. Here
$g_{4}={\mathcal{G}}-g_{1}-g_{2}-g_{3}$ is the residual subgraph. In the
DisjointSubgraphSample process, we randomly sample $k=2$ of these subgraphs
from $g_{1},g_{2},g_{3}$, excluding the residual graph. We combine these
sampled subgraphs and add random edges from the residual graph.

Figure 12. We split the original graph $G$ into a collection of disjoint edges
(here, a spanning tree is used), and then we sample such subgraphs to get a
sparse graph, $G^{\prime}=g_{1}+g_{2}$ for an epoch/batch.

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, $R$ is the rank from similarity or
diversity of the neighborhood, $K$ is the number of edge-disjoint graph,
Subgraph selection ${\mathcal{F}}$ could be MST, $k$-NN, $b$-matching, or
combinations of these

1

2

31: Get edge weights, $W$, from rank $R$ using Probability Mass Function
${\mathcal{P}}$

42: Graph collections, $\mathrm{{\mathcal{G}}_{col}=\\{\\}}$, Graph Weights,
$\mathrm{{\mathcal{G}}_{w}=\\{\\}}$

3: while True do

4: Compute, $\mathrm{Sub_{\mathcal{G}}={\mathcal{F}}({\mathcal{G}},W)}$

5: $\mathrm{{\mathcal{G}}_{col}={\mathcal{G}}_{col}\cup Sub_{\mathcal{G}}}$

6: \- /* make sure the sparse graph weight doesn’t become too small */

7: $\mathrm{{\mathcal{G}}_{w}={\mathcal{G}}_{w}\cup
max(Weight(Sub_{\mathcal{G}}),K\times 1e^{-3})}$

58: $\mathrm{{\mathcal{G}}={\mathcal{G}}-Sub_{\mathcal{G}}}$

9: $K=K-1$

10: if $K=0$ then

11: $\mathrm{{\mathcal{G}}_{col}={\mathcal{G}}_{col}\cup Sub_{\mathcal{G}}}$

12: $\mathrm{{\mathcal{G}}_{w}={\mathcal{G}}_{w}\cup\\{0\\}}$

13: break

614: end if

15: end while

16: return $\mathrm{{\mathcal{G}}_{col},{\mathcal{G}}_{w}}$

Algorithm 7 Disjoint Graphs
(${\mathcal{G}},{\bm{X}},R,K,\mathrm{{\mathcal{F}}=^{\prime}MST_{max}^{\prime}}$)

####  9.2.2. AGS-GS-Disjoint: AGS-GNN with edge-disjoint graph sampling

Algorithm 8 shows overall AGS-GNN as a graph sampling process for training
when disjoint graphs sampling with heuristics are used. For simplicity, we
include the pseudocode on a single channel; the dual-channel implementation is
similar to the Random Walk version. Here, we sample a sparse graph at the
start of the epoch and perform random walk-based graph sampling as a mini-
batch process to ensure that the subgraph remains small for GNN iterations.
The second step is unnecessary if the initial sampled sparse graph fits in the
GPU memory. We can also directly perform random-walk on the collection of
edge-disjoint subgraphs instead of the two-stage process.

Input : Graph ${\mathcal{G}}({\mathcal{V}},{\mathcal{E}})$, Feature matrix
${\bm{X}}\in\mathbb{R}^{n\times f}$, Label, ${\bm{y}}\in{\mathbb{Y}}^{n}$

1

2

1: ${\mathcal{S}}=\mathrm{LearnSimilarity({\mathcal{G}},{\bm{X}},{\bm{y}})}$
/* model for feature similarity, if an appropriate function not known, Alg. 5
*/

2: ${\mathcal{P}}=\mathrm{{}^{\prime}step^{\prime}}$ /* probability mass
function */

3

3:
$\mathrm{R=RankBySimilarity({\mathcal{G}},{\bm{X}},{\mathcal{S}},{\mathcal{P}})}$
/* Algorithm 2 */

4

4:
$\mathrm{({\mathcal{G}}_{col},{\mathcal{G}}_{w})=DisjointGraphs({\mathcal{G}},{\bm{X}},R,K,{\mathcal{F}}=`ST_{max}`)}$
/* Algorithm 7 */

5

5: for $\mathrm{epoch}$ in $\mathrm{num\\_epochs}$ do

6: \- /* sample a sparse graph using the process explained in Fig. 12 */

6

77:
$\mathrm{{\mathcal{G}}^{\prime}=DisjointSubgraphSample({\mathcal{G}}_{col},{\mathcal{G}}_{w},*params)}$

8: for $\mathrm{mini\\_batch}$ in $\mathrm{num\\_batches}$ do

9: $\mathrm{nodes=BatchOfSeedNodes({\mathcal{G}}^{\prime})}$

10: $\mathrm{g=SubgraphSample({\mathcal{G}}^{\prime},nodes)}$/* weighted
random walk on the sparse graph */

11: $\mathrm{output=GNN_{{\bm{W}}}(g)}$

12: $l=\mathrm{loss(output,{\bm{y}}[g.train])}$

13: Backpropagate from $l$ and update ${\bm{W}}$

14: end for

15: end for

Algorithm 8 AGS-GS-Disjoint (${\mathcal{G}},{\bm{X}},{\bm{y}}$) [Disjoint
subgraph sample* (single channel)]

##  10\. Appendix: Dataset Details

###  10.1. Dataset Description

####  10.1.1. Dataset with Heterophily:

Cornell, Texas, and Wisconsin are three sub-datasets from the WebKB set (Pei
et al., 2020). Chameleon and Squirrel are web page datasets collected from
Wikipedia (Rozemberczki et al., 2021). The actor is an actor co-occurrence
network (Pei et al., 2020), where nodes are actors and edges represent two
actors whose names occur together on the same Wikipedia page. Recently (Lim et
al., 2021) collected and released a series of large-scale benchmark datasets
from diverse areas which include a Wikipedia web page dataset (Wiki), two
citation network datasets (ArXiv-year and Snap-Patents), online social network
datasets (Penn94, Pokec, Genius, and Twitch-Gamers). We also use the dataset
from (Lim et al., 2021), which includes reed98, amherst41, cornell5, Yelp and
johnshopkins55. In (Platonov et al., 2023), the authors proposed new benchmark
datasets, Roman-empire, Amazon-ratings, Minesweeper, Tolokers, and Questions
to show the effect of homophilic and heterophilic GNNs. We also converted a
few multi-label multiclass classification problems (Flickr, AmazonProducts) to
single-label multiclass node classification problems. Through this process,
their homophily values are reduced, rendering them heterophilic.

####  10.1.2. Dataset with Homophily:

Cora (Sen et al., 2008), Citeseer (Giles et al., 1998) and pubmed (Namata et
al., 2012) are three classic _paper citation network_ benchmarks. For Cora and
Citeseer, class labels correspond to paper topics, while for pubmed, labels
correspond to the type of diabetes. Coauthor-cs and Coauthor-physics (Shchur
et al., 2018) are coauthorship networks, where nodes represent authors and an
edge connects two authors if they co-authored a paper. Node labels correspond
to fields of study. The Amazon-computers and Amazon-photo (Shchur et al.,
2018) are co-purchasing networks with nodes representing products and edges
representing two products that are frequently bought together. Here labels
correspond to product categories. Reddit (Hamilton et al., 2017) is one of the
most popular large homophilic benchmark datasets. The graph contains Reddit
posts belonging to different communities; the node label is the community, or
subreddit, that a post belongs to. Reddit2 (Zeng et al., 2019) is the sparse
version of the original Reddit graph with average degree $100$ instead of the
original $492$. The dblp (Fu et al., 2020) is from a subset of the DBLP
computer science bibliography website.

###  10.2. Homophily measures of Dataset

Dataset | ${N}$ | ${E}$ | ${d}$ | ${C}$ | ${{\mathcal{H}}_{n}}$ | ${{\mathcal{H}}_{e}}$ | ${{\mathcal{H}}_{i}}$ | ${{\mathcal{H}}_{a}}\downarrow$ | ${{\mathcal{H}}_{agg}^{LP}}$ | ${{\mathcal{H}}_{agg}^{HP}}$ | ${{\mathcal{H}}_{t}}$ | ${{\mathcal{H}}_{u}}$ | ${{\mathcal{A}}}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Cornell | 183 | 298 | 1.63 | 5 | 0.11 | 0.13 | 0.15 | -0.42 | 0.62 | 0.61 | 0.05 | 0.01 | -0.38
Texas | 183 | 325 | 1.78 | 5 | 0.07 | 0.11 | 0.00 | -0.26 | 0.55 | 0.56 | 0.09 | 0.00 | -0.35
Wisconsin | 251 | 515 | 2.05 | 5 | 0.17 | 0.20 | 0.08 | -0.20 | 0.50 | 0.51 | 0.06 | 0.00 | -0.27
reed98 | 962 | 37,624 | 39.11 | 2 | 0.45 | 0.45 | $-$ | -0.10 | 0.55 | 0.54 | $-$ | $-$ | 0.02
amherst41 | 2,235 | 181,908 | 81.39 | 2 | 0.47 | 0.46 | $-$ | -0.07 | 0.50 | 0.58 | $-$ | $-$ | 0.06
penn94 | 41,554 | 2,724,458 | 65.56 | 2 | 0.48 | 0.47 | $-$ | -0.06 | $-$ | $-$ | $-$ | $-$ | 0.00
Roman-empire | 22,662 | 65,854 | 2.91 | 18 | 0.05 | 0.05 | 0.02 | -0.05 | $-$ | $-$ | 0.31 | 0.00 | -0.03
cornell5 | 18,660 | 1,581,554 | 84.76 | 2 | 0.48 | 0.48 | $-$ | -0.04 | $-$ | $-$ | $-$ | $-$ | 0.02
Squirrel | 5,201 | 217,073 | 41.74 | 5 | 0.09 | 0.22 | 0.04 | -0.01 | 0.43 | 0.55 | 0.68 | 0.28 | 0.37
johnshopkins55 | 5,180 | 373,172 | 72.04 | 2 | 0.50 | 0.50 | $-$ | 0.00 | 0.49 | 0.56 | $-$ | $-$ | 0.08
AmazonProducts | 1,569,960 | 264,339,468 | 168.37 | 107 | 0.48 | 0.09 | 0.01 | 0.01 | $-$ | $-$ | $-$ | $-$ | -0.03
Actor | 7,600 | 30,019 | 3.95 | 5 | 0.16 | 0.22 | 0.01 | 0.01 | 0.36 | 0.36 | 0.34 | 0.11 | -0.11
Minesweeper | 10,000 | 78,804 | 7.88 | 2 | 0.68 | 0.68 | 0.01 | 0.01 | 0.58 | 0.59 | $-$ | 0.86 | 0.39
Questions | 48,921 | 307,080 | 6.28 | 2 | 0.90 | 0.84 | 0.08 | 0.02 | $-$ | $-$ | $-$ | 0.23 | -0.15
Chameleon | 2,277 | 36,101 | 15.85 | 5 | 0.10 | 0.24 | 0.06 | 0.03 | 0.51 | 0.53 | 0.55 | 0.17 | -0.11
Tolokers | 11,758 | 1,038,000 | 88.28 | 2 | 0.63 | 0.59 | 0.18 | 0.09 | $-$ | $-$ | $-$ | 0.92 | -0.08
Flickr | 89,250 | 899,756 | 10.08 | 7 | 0.32 | 0.32 | 0.07 | 0.09 | $-$ | $-$ | 0.47 | 0.01 | -0.04
Yelp | 716,847 | 13,954,819 | 19.47 | 100 | 0.52 | 0.44 | 0.02 | 0.12 | $-$ | $-$ | $-$ | $-$ | 0.10
Amazon-ratings | 24,492 | 186,100 | 7.60 | 5 | 0.38 | 0.38 | 0.13 | 0.14 | $-$ | $-$ | 0.37 | 0.03 | -0.09
genius | 421,961 | 984,979 | 2.33 | 2 | 0.48 | 0.62 | 0.22 | 0.17 | $-$ | $-$ | $-$ | 0.03 | -0.11
cora | 19,793 | 126,842 | 6.41 | 70 | 0.59 | 0.57 | 0.50 | 0.56 | $-$ | $-$ | 0.09 | 0.00 | -0.05
CiteSeer | 3,327 | 9,104 | 2.74 | 6 | 0.71 | 0.74 | 0.63 | 0.67 | 0.72 | 0.73 | 0.03 | 0.00 | 0.05
dblp | 17,716 | 105,734 | 5.97 | 4 | 0.81 | 0.83 | 0.65 | 0.68 | $-$ | $-$ | 0.05 | 0.01 | -0.01
Computers | 13,752 | 491,722 | 35.76 | 10 | 0.79 | 0.78 | 0.70 | 0.68 | $-$ | $-$ | 0.15 | 0.00 | -0.06
pubmed | 19,717 | 88,648 | 4.50 | 3 | 0.79 | 0.80 | 0.66 | 0.69 | $-$ | $-$ | 0.04 | 0.05 | -0.04
Reddit | 232,965 | 114,615,892 | 491.99 | 41 | 0.81 | 0.76 | 0.65 | 0.74 | $-$ | $-$ | 0.28 | 0.00 | 0.11
cora_ml | 2,995 | 16,316 | 5.45 | 7 | 0.81 | 0.79 | 0.74 | 0.75 | 0.84 | 0.78 | 0.06 | 0.00 | -0.07
Cora | 2,708 | 10,556 | 3.90 | 7 | 0.83 | 0.81 | 0.77 | 0.77 | 0.85 | 0.81 | 0.04 | 0.00 | -0.07
Reddit2 | 232,965 | 23,213,838 | 99.65 | 41 | 0.81 | 0.78 | 0.69 | 0.77 | $-$ | $-$ | 0.21 | 0.00 | 0.10
CS | 18,333 | 163,788 | 8.93 | 15 | 0.83 | 0.81 | 0.75 | 0.78 | $-$ | $-$ | 0.07 | 0.00 | 0.11
Photo | 7,650 | 238,162 | 31.13 | 8 | 0.84 | 0.83 | 0.77 | 0.79 | 0.77 | 0.81 | 0.13 | 0.00 | -0.04
Physics | 34,493 | 495,924 | 14.38 | 5 | 0.92 | 0.93 | 0.85 | 0.87 | $-$ | $-$ | 0.04 | 0.00 | 0.20
citeseer | 4,230 | 10,674 | 2.52 | 6 | 0.96 | 0.95 | 0.94 | 0.94 | 0.96 | 0.95 | 0.00 | 0.00 | -0.08

Table 8. Properties of all datasets used in the experiments and their
different homophily measure. The datasets are sorted (in ascending order)
based on their adjusted homophily, $h_{adj}$. The ’$-$’ represents the value
that is not computed due to memory complexity or an error in computation. The
datasets are termed heterophily and homophily based on the $h_{adj}$ cutoff
$0.5$

Here we provide more homophily measures than included in the paper, and
provide additional details.

  1. (1)

Edge homophily (Zhu et al., 2020): is defined as the fraction of edges in a
graph that join nodes that have the same class label

(8) ${\mathcal{H}}_{e}=\frac{|(u,v):(u,v)\in{\mathcal{E}}\land
y_{u}=y_{v}|}{|{\mathcal{E}}|}.$

Recall that $y_{u},y_{v}$ represent labels of node $u$ and $v$, respectively.

  2. (2)

Node homophily (Pei et al., 2020):

(9) ${\mathcal{H}}_{n}=\frac{1}{|{\mathcal{V}}|}\sum_{u\in V}\frac{|(u,v):v\in
N(u)\land y_{u}=y_{v}|}{|{\mathcal{N}}(u)|}.$

Here ${\mathcal{N}}(u)$ represents neighbors of node $u$.

  3. (3)

Class insensitive edge homophily (Lim et al., 2021): Edge homophily is
modified to be insensitive to the number of classes and size of each class as
follows.

(10)
${\mathcal{H}}_{i}=\frac{1}{c-1}\sum_{k=1}^{c}max(0,{\mathcal{H}}_{k}-\frac{|c_{k}|}{|V|}),$

where $c$ denotes the number of classes, $|c_{k}|$ denotes the number of nodes
of class $k$, and ${\mathcal{H}}_{k}$ denotes the edge homophily ratio of
nodes of class $k$.

These homophily score range between $[0,1]$. The definitions of homophily
scores given above may not represent heterophilic graphs well; hence we
consider a few more. In addition, we define two more intuitive definitions to
understand the distribution of labels in the neighborhood of a vertex.

  1. (1)

Aggregated Homophily (Luan et al., 2022): is the only measure that considers
associated node features. It is defined as

(11) $\displaystyle\centering{\mathcal{H}}_{agg}\@add@centering$
$\displaystyle=[2S_{agg}(S({\bm{A}},{\bm{X}}))-1]_{+}$ (12) $\displaystyle
S=S({\bm{A}},{\bm{X}})$
$\displaystyle=({\bm{A}}{\bm{X}})\times({\bm{A}}{\bm{X}})^{T}$ (13)
$\displaystyle S_{agg}(S({\bm{A}},{\bm{X}}))$
$\displaystyle=\frac{1}{|V|}\\{v|\mu_{u}(S_{v,u}|y_{u}=y_{v})\geq\mu_{u}(S_{v,u}|y_{u}\neq
y_{v}).\\}$

Here $S({\bm{A}},{\bm{X}})$ is an $N\times N$ matrix, and the method computes
the average similarity weights for edges that share the same label for each
row. Moreover, it counts the expected number of correctly classified nodes
with a single-layer GNN.

  2. (2)

Adjusted Homophily (Platonov et al., 2022) is defined as

(14)
${\mathcal{H}}_{a}=\frac{{\mathcal{H}}_{e}-\sum_{k=1}^{C}D_{k}^{2}/(2|{\mathcal{E}}|^{2})}{1-\sum_{k=1}^{C}D_{k}^{2}/2|{\mathcal{E}}|^{2}};$

here $d_{v}$ denotes the degree of node $v$ and $D_{k}=\sum_{v:y_{v}=k}d_{v}$.

  3. (3)

Entropy Score: A vertex may have edges connecting it to clusters with labels
that differ from its own, and we evaluate if these edges are connected to
specific clusters or distributed across all cluster labels. Entropy is an
excellent measure for this, and it is defined as

(15) ${\mathcal{H}}_{t}=\sum_{u\in V}\mathrm{Entropy}(u)/|{\mathcal{V}}|.$

  4. (4)

Uniformity Score: Another metric with the same inspiration comes from checking
the distribution of neighboring node labels of the vertex.

(16) ${\mathcal{H}}_{u}=\sum_{u\in V}\mathrm{Uniformity(u)}/|{\mathcal{V}}|,$

where $\mathrm{Uniformity(u)}$ does the Chi-square test with expected uniform
distribution with $95\%$ confidence.

Table 8 shows different homophily measures of all the datasets used for
experimentation. Here, ${\mathcal{A}}$ refers to the degree assortativity
coefficient of the graph. Assortivity measures how similar the nodes are in
terms of some degree. It is calculated as the correlation coefficient between
the degree values for pairs of connected nodes. A positive assortivity means
that nodes tend to connect with other nodes that have similar degrees. In
contrast, a negative assortivity means that nodes tend to connect with other
nodes with different degrees.

(17)
${\mathcal{A}}=\frac{\sum_{ij}(e_{ij}-p_{i}q_{j})}{\sqrt{(\sum_{i}p_{i}^{2}-(\sum_{i}p_{i})^{2})(\sum_{j}q_{j}^{2}-(\sum_{j}q_{j})^{2})}}.$

Here $e_{ij}$ is the fraction of edges in the network that join nodes of
degrees $i$ and $j$, $p_{i}$ is the fraction of edges connecting nodes of
degree $i$ to each other, and $q_{j}$ is the fraction of edges that connect
nodes of degree $j$ to each other.

###  10.3. Additional Dataset Properties

Dataset | Feat. | Isolated | Self-loop | Directed | Tr./Va./Te. | Context
---|---|---|---|---|---|---
Cornell | 1,703 | No | Yes | No | 0.48/0.32/0.20 | Web Pages
Texas | 1,703 | No | Yes | No | 0.48/0.32/0.20 | Web Pages
Wisconsin | 1,703 | No | Yes | No | 0.48/0.32/0.20 | Web Pages
reed98 | 745 | No | No | Yes | 0.60/0.20/0.20 | Social Network
amherst41 | 1,193 | No | No | Yes | 0.60/0.20/0.20 | Social Network
penn94 | 4,814 | No | No | Yes | 0.47/0.23/0.23 | Social Network
Roman-empire | 300 | No | No | Yes | 0.50/0.25/0.25 | Wikipedia
cornell5 | 4,735 | No | No | Yes | 0.60/0.20/0.20 | Web pages
Squirrel | 2,089 | No | Yes | No | 0.48/0.32/0.20 | Wikipedia
johnshopkins55 | 2,406 | No | No | Yes | 0.60/0.20/0.20 | Web Pages
AmazonProducts | 200 | Yes | Yes | Yes | 0.80/0.05/0.15 | Reviews
Actor | 932 | No | Yes | No | 0.48/0.32/0.20 | Actors in Movies
Minesweeper | 7 | No | No | Yes | 0.50/0.25/0.25 | Synthetic
Questions | 301 | No | No | Yes | 0.50/0.25/0.25 | Yandex Q
Chameleon | 2,325 | No | Yes | No | 0.48/0.32/0.20 | Wiki Pages
Tolokers | 10 | No | No | Yes | 0.50/0.25/0.25 | Toloka Platform
Flickr | 500 | No | No | Yes | 0.50/0.25/0.25 | Social network
Yelp | 300 | No | Yes | Yes | 0.75/0.15/0.10 | Review
Amazon-ratings | 300 | No | No | Yes | 0.50/0.25/0.25 | Co-purchase network
genius | 12 | Yes | No | No | 0.60/0.20/0.20 | Social Network
cora | 8,710 | No | No | Yes | 0.60/0.20/0.20 | Citation Network
CiteSeer | 3,703 | Yes | No | Yes | 0.04/0.15/0.30 | Citation Network
dblp | 1,639 | No | No | Yes | 0.60/0.20/0.20 | Citation Network
Computers | 767 | Yes | No | Yes | 0.60/0.20/0.20 | Co-purchase Network
pubmed | 500 | No | No | Yes | 0.60/0.20/0.20 | Social Network
Reddit | 602 | No | No | Yes | 0.66/0.10/0.24 | Social Network
cora_ml | 2,879 | No | No | Yes | 0.60/0.20/0.20 | Citation Network
Cora | 1,433 | No | No | Yes | 0.05/0.18/0.37 | Citation Network
Reddit2 | 602 | Yes | No | Yes | 0.66/0.10/0.24 | Social Network
CS | 6,805 | No | No | Yes | 0.60/0.20/0.20 | Co-author Network
Photo | 745 | Yes | No | Yes | 0.60/0.20/0.20 | Co-purchase Network
Physics | 8,415 | No | No | Yes | 0.60/0.20/0.20 | Co-author Network
citeseer | 602 | No | No | Yes | 0.60/0.20/0.20 | Citation Network

Table 9. Additional details of the dataset used for experiments

Additional dataset properties are included in Table 9. The table includes
feature size, whether isolated nodes exist, whether self-loops are present,
and whether the graphs are directed or undirected. We also include train,
test, validation split provided from the benchmark or our random split size
and the context from which the graphs arise.

###  10.4. Feature Similarity versus Label Matching

###### Assumption 10.1.

The nodes with similar features tend to have a similar labels (Van Engelen and
Hoos, 2020).

Here, we provide evidence to support this assumption. Table 10 shows the
Pearson correlation between feature similarity and labels for our benchmark
dataset. The Pearson correlation between two vectors ${\bm{x}}$ and ${\bm{y}}$
with $n$ elements is,

(18)
$r=\frac{\sum_{i=1}^{n}(x_{i}-\bar{x})(y_{i}-\bar{y})}{\sqrt{\sum_{i=1}^{n}(x_{i}-\bar{x})^{2}}\sqrt{\sum_{i=1}^{n}(y_{i}-\bar{y})^{2}}}.$

Here $\bar{x}$ and $\bar{y}$ are the means of the vectors ${\bm{x}}$ and
${\bm{y}}$, respectively. In Table 10, we show a comparison between Cosine
Similarity, Euclidean distance, and Learned model for similarity measure.

| Rand. | Rand. | Rand. | Balance. | Balance. | Balance. | Edge | Edge | Edge | Edge
---|---|---|---|---|---|---|---|---|---|---
Dataset | Learned | Cosine Sim. | Euclidean$\times-1$ | Learned | Cosine Sim. | Euclidean$\times-1$ | Learned | Learned (Balanced) | Cosine Sim | Euclidean$\times-1$
Cornell | 0.71 | 0.29 | 0.19 | 0.72 | 0.29 | 0.19 | 0.44 | 0.63 | 0.30 | 0.09
Texas | 0.73 | 0.28 | 0.21 |  0.77 | 0.28 | 0.21 | 0.50 | 0.52 | 0.58 | 0.47
Wisconsin | 0.77 | 0.45 | 0.29 | 0.77 | 0.45 | 0.29 | 0.48 | 0.47 | 0.39 | 0.31
reed98 | 0.38 | -0.02 | -0.01 | 0.37 | -0.02 | -0.01 | 0.36 |  0.36 | 0.04 | 0.05
amherst41 | 0.44 | -0.02 | -0.01 | 0.45 | -0.02 | -0.01 | 0.44 | 0.44 | 0.01 | 0.01
penn94 | 0.37 | -0.03 | -0.03 | 0.24 | 0.17 | 0.20 | 0.41 | 0.41 | 0.07 | 0.07
Roman-empire | 0.60 | 0.26 | 0.06 | 0.34 | 0.24 | 0.09 | 0.29 | 0.22 | 0.10 | 0.06
cornell5 | 0.44 | -0.02 | -0.01 | 0.40 | 0.15 | 0.19 | 0.44 | 0.44 | 0.05 | 0.05
Squirrel | 0.16 | 0.02 | 0.02 |  0.15 | 0.02 | 0.02 | 0.19 | 0.18 | 0.05 | -0.05
johnshopkins55 | 0.42 | -0.02 | -0.02 | 0.31 | 0.18 | 0.21 | 0.41 | 0.42 | 0.00 | 0.00
AmazonProducts | 0.29 | 0.02 | -0.01 | 0.01 |  0.02 | 0.00 | 0.23 | -0.11 | 0.12 | -
Actor | 0.22 | 0.00 | -0.05 | 0.20 | 0.01 | 0.02 | 0.22 | 0.22 | 0.02 | -0.05
Minesweeper | 0.03 | 0.00 | -0.01 | 0.00 | 0.00 | 0.00 | 0.09 | 0.08 | 0.03 | 0.03
Questions | 0.29 | 0.00 | 0.03 | 0.01 | 0.04 | 0.02 | 0.17 | 0.17 | 0.00 | -0.03
Chameleon | 0.43 | 0.04 | 0.05 | 0.43 | 0.04 | 0.05 | 0.31 | 0.29 | 0.09 | -0.04
Tolokers | 0.22 | -0.04 | -0.04 | 0.05 | 0.06 | 0.06 | 0.20 | 0.20 | -0.03 | -0.03
Flickr | 0.07 | 0.03 | 0.02 | 0.02 | 0.02 | 0.00 | 0.04 | 0.05 | 0.05 | 0.02
Yelp | 0.48 | 0.08 | 0.09 |  0.10 | 0.03 | 0.05 | 0.35 | 0.35 | 0.20 | 0.28
Amazon-ratings | 0.05 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.05 | -0.03 | -0.03 | -0.03
genius | 0.00 | 0.46 | -0.02 | 0.01 | 0.28 | 0.01 |  0.05 | 0.05 | 0.04 | -0.17
cora | 0.22 | 0.10 | 0.01 | 0.04 | 0.11 | 0.01 | 0.12 | -0.09 | 0.16 | 0.03
CiteSeer | 0.24 | 0.18 | 0.04 | 0.21 | 0.18 | 0.04 | 0.15 | 0.11 |  0.15 | 0.10
dblp | 0.50 | 0.10 | -0.01 | 0.48 | 0.11 | 0.02 | 0.40 | 0.33 | 0.01 | -0.06
Computers | 0.68 | -0.04 | 0.09 | 0.48 | 0.05 | 0.05 | 0.37 | 0.41 | -0.10 | 0.06
pubmed |  0.47 | 0.17 | 0.08 | 0.61 | 0.20 | 0.05 | 0.28 | 0.29 | 0.12 | 0.08
Reddit | 0.48 | 0.18 | 0.02 | 0.23 | 0.14 | 0.02 | 0.21 | 0.15 | 0.13 | 0.02
cora_ml | 0.66 | 0.13 | 0.00 |  0.65 | 0.13 | 0.00 | 0.26 | 0.59 | 0.12 | -0.04
Cora | 0.23 | 0.14 | 0.00 | 0.24 | 0.14 | 0.00 | 0.14 | 0.14 | 0.13 | 0.03
Reddit2 | 0.17 | 0.07 | 0.03 | 0.01 | 0.04 | 0.00 | -0.09 | 0.01 | 0.09 |  0.37
CS | 0.86 | 0.57 | 0.01 | 0.54 | 0.45 | 0.05 | 0.41 | 0.51 | 0.29 | 0.20
Photo | 0.63 | 0.08 | 0.07 | 0.66 | 0.08 | 0.06 | 0.28 | 0.51 | -0.15 | 0.12
Physics | 0.81 | 0.48 | 0.10 | 0.84 | 0.44 | 0.06 | 0.52 | 0.53 | 0.17 | 0.14
citeseer | 0.69 | 0.27 | 0.06 | 0.66 | 0.27 | 0.06 | 0.26 | 0.29 | 0.09 | 0.02

Table 10. Pearson correlation coefficient between feature similarity and label
matching. The table shows results in three categories: 1) evaluation done on
nodes taken randomly, the model is also trained with random training node
samples; 2) training and evaluation done where nodes are taken from each class
of equal size; 3) evaluation done only to the given edges, the learned model
is trained both random sampling and balanced sampling (from the training
nodes).

To compute the similarity between two node features, we use cosine similarity
and Euclidean distances. We also train a similarity function learning
regression model that learns from training nodes and evaluates on test nodes.
Here is a brief explanation of each column in the table.

The three categories are based on how we evaluated or computed the Pearson
correlations of the nodes.

  1. (1)

In the first category, we take random sets of test nodes and consider all pair
of edges to compute the Pearson correlation between them.

    1. (a)

Rand Learned: We train a regression model to learn similarity functions based
on training subgraphs. Then, we evaluate $r$ on random test nodes.

    2. (b)

Rand Cosine Sim. We consider the same random test nodes and use cosine
similarity measures.

    3. (c)

Rand Euclidean $\times-1$: We consider the negative Euclidean distance of two
node features since the distance is minimum when similarity is maximum.

  2. (2)

The problem with the previous type of evaluation is that the number of edges
with non-matching labels at the endpoints will be high due to the
consideration of all pairs, which introduces a bias in the Pearson correlation
computation. To handle that, we evaluated on random sets of test nodes but
with an equal number of edges and non-edges.

    1. (a)

Balance. Learned: The regression model is trained on a training subgraph with
an equal number of positive and negative edges.

    2. (b)

Balance. Cosine Sim: The Pearson correlation with cosine similarity is
evaluated on the same number of equal edges and non-edges.

    3. (c)

Balance. Euclidean$\times-1$: The same evaluation is done with the negative of
the Euclidean distance.

  3. (3)

The previous two categories were evaluated on random sets of training nodes.
In this category, we computed Pearson correlation only on the given edges for
cosine similarity and Euclidean distance. For learned models, we evaluated on
test subgraph edges only.

    1. (a)

Edge Learned: We trained a regression model with training edges and set a
target with equal endpoint labels as one and zero otherwise.

    2. (b)

Edge Learned Balanced: We trained the regression model with equal training
edges and non-edges from the training subgraph.

    3. (c)

Edge Cosine Sim.: We evaluated only on given edges using cosine similarity.

    4. (d)

Edge Euclidean$\times-1$: We evaluated only on given edges using the negative
of the Euclidean distance.

The table shows that the feature similarity and labels are positively
correlated for all datasets. We specifically have a higher correlation value
on the trained model. It highlights the importance of training a model for
computing similar and diverse neighborhoods of a subgraph in the pre-
computation step. This experiment also validates the importance of our
supervised sampling strategy.

###  10.5. Local Node Homophily Distribution of Dataset

Figs. 13 and 14 show a histogram of _local node homophily,
${\mathcal{H}}_{n}(u)$_ values of all vertices of a graph. For example, Fig.
13a shows that most of the nodes of Cornell graphs have local node homophily
$0$ and only a few have $1$, meaning the graph is strongly heterophilic with
the majority of nodes having no neighbors of the same label as ego node. In
contrast, Reddit (in Fig. 14f) has the most nodes with high homophily. We can
use a single channel AGS-GNN based on a feature-similarity sampler for graphs
like Reddit, where we have only a few heterophilic nodes. In contrast, when a
graph consists of both local homophilic and heterophilic (as in Amherst41 in
Fig. 13e), we need both feature-similarity and feature-diversity samplers.
Therefore, the histogram plots of graphs give us a good insight into the
distribution of local homophily. It explains when and why dual channel
samplers work for homophilic and heterophilic graphs.

|  |  |
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |

(a) Cornell

(b) Texas

(c) Wisconsin

(d) reed98

(e) amherst41

(f) penn94

(g) Roman-empire

(h) cornell5

(i) Squirrel

(j) johnshopkins55

(k) AmazonProducts

(l) Actor

(m) Minesweeper

(n) Questions

(o) Chameleon

(p) Tolokers

(q) Flickr

(r) Yelp

(s) Amazon-ratings

(t) genius

Figure 13. _Local Node Homophily_ distributions of our benchmark datasets
(Part 1)

|  |  |
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |

(a) cora

(b) CiteSeer

(c) dblp

(d) Computers

(e) pubmed

(f) Reddit

(g) cora_ml

(h) Cora

(i) Reddit2

(j) CS

(k) Photo

(l) Physics

(m) citeseer

(n) pokec

(o) arxiv-year

(p) snap-patents

(q) twitch-gamer

(r) wiki

Figure 14. _Local Node Homophily_ distributions of our benchmark datasets
(Part 2)

##  11\. Appendix: Detailed Experimental Results

###  11.1. AGS-GNN performance comparison

Table 11 shows numerical results of the algorithms for small heterophilic
graphs ($N<100K$). The performance plot in Fig. 5a (§5) is drawn based on the
data from this table.

Table 12 shows the comparison for small homophilic graphs ($N<100K$). The
performance plot in Fig. 5b (§5) is drawn based on the data from this table.

Table 13 shows the comparison of algorithms for large heterophilic graphs
($N>=100K$). The performance plot in Fig. 5c (§5) is drawn based on the data
from this table.

Table 14 compares the algorithms for large heterophilic graphs ($N>=100K$).
The performance plot in Fig. 5d (§5) is drawn based on the data from this
table.

Small Heterophilic Graphs | GSAGE | GSAINT |  LINKX${\dagger}$ | ACMGCN | AGS-NS | AGS-GS
---|---|---|---|---|---|---
$\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
Cornell | 71.35 | 6.07 | 67.03 | 3.15 | 76.76 | 4.32 | 74.59 | 1.32 | 74.59 | 2.16 | 70.27 | 4.83
Texas | 77.30 | 5.57 | 79.46 | 6.53 | 81.62 | 2.02 | 84.32 | 7.13 | 84.86 | 6.19 | 80.00 | 5.57
Wisconsin | 79.61 | 3.64 | 79.61 | 6.86 | 83.53 | 4.74 | 84.31 | 3.28 | 81.96 | 4.71 | 85.10 | 6.49
reed98 | 61.87 | 0.53 | 64.15 | 0.69 | 66.63 | 1.37 | 66.11 | 1.25 | 66.74 | 1.37 | 64.66 | 0.89
amherst41 | 66.62 | 0.33 | 69.57 | 0.71 | 78.64 | 0.35 | 78.12 | 0.30 | 79.19 | 0.47 | 77.14 | 0.90
penn94 | 75.65 | 0.42 | 75.11 | 0.33 | 85.92 | 0.32 | 85.38 | 0.53 | 76.06 | 0.41 | 81.56 | 0.45
Roman-empire | 79.52 | 0.42 | 77.51 | 0.47 | 59.14 | 0.45 | 71.42 | 0.39 | 80.49 | 0.48 | 75.38 | 0.25
cornell5 | 69.22 | 0.12 | 68.10 | 0.15 | 80.10 | 0.27 | 78.43 | 0.50 | 82.84 | 0.01 | 74.84 | 0.35
Squirrel | 38.66 | 1.24 | 39.14 | 1.45 | 35.91 | 1.09 | 72.06 | 2.21 | 68.24 | 0.97 | 51.73 | 1.30
johnshopkins55 | 67.37 | 0.54 | 67.43 | 0.20 | 79.63 | 0.16 | 77.37 | 0.61 | 78.13 | 0.42 | 75.93 | 0.48
Actor | 34.82 | 0.55 | 35.24 | 0.81 | 33.93 | 0.82 | 34.42 | 1.08 | 36.55 | 0.93 | 34.88 | 0.63
Minesweeper | 85.74 | 0.25 | 85.46 | 0.49 | 80.02 | 0.03 | 80.33 | 0.23 | 85.56 | 0.28 | 85.25 | 0.71
Questions | 97.13 | 0.01 | 97.18 | 0.04 | 97.06 | 0.03 | 97.02 | 0.00 | 97.27 | 0.04 | 97.23 | 0.04
Chameleon | 51.18 | 2.70 | 52.32 | 2.47 | 50.18 | 2.01 | 75.81 | 1.67 | 73.46 | 2.29 | 66.67 | 1.65
Tolokers | 79.15 | 0.32 | 78.89 | 0.37 | 80.07 | 0.53 | 80.45 | 0.54 | 80.52 | 0.41 | 80.50 | 0.61
Flickr | 50.86 | 0.32 | 50.28 | 0.11 | 53.81 | 0.31 | 52.19 | 0.24 | 51.52 | 0.13 | 50.79 | 0.13
Amazon-ratings | 48.08 | 0.38 | 52.21 | 0.27 | 52.68 | 0.26 | 52.94 | 0.23 | 53.21 | 0.46 | 52.25 | 0.34

Table 11. The table shows micro $F_{1}$-measure in small heterophilic graphs.

Small Homophilic Graphs | GSAGE | GSAINT | LINKX${\dagger}$ | ACMGCN | AGS-NS | AGS-GS
---|---|---|---|---|---|---
$\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
cora | 52.59 | 0.25 | 65.85 | 0.27 | 57.18 | 0.16 | 66.79 | 0.24 | 69.32 | 0.11 | 69.18 | 0.25
CiteSeer | 71.14 | 0.10 | 65.84 | 3.86 | 44.20 | 2.49 | 55.42 | 3.43 | 69.33 | 0.31 | 68.14 | 0.56
dblp | 85.80 | 0.16 | 85.65 | 0.21 | 80.47 | 0.04 | 85.68 | 0.24 | 85.97 | 0.11 | 85.40 | 0.05
Computers | 91.31 | 0.11 | 91.77 | 0.14 | 91.38 | 0.17 | 92.03 | 0.48 | 92.18 | 0.08 | 91.28 | 0.14
pubmed | 89.00 | 0.09 | 88.57 | 0.14 | 85.05 | 0.25 | 83.79 | 0.15 | 89.34 | 0.07 | 87.41 | 0.17
cora_ml | 88.71 | 0.23 | 87.21 | 0.37 | 80.67 | 0.32 | 85.28 | 0.12 | 87.70 | 0.08 | 87.95 | 0.41
Cora | 80.56 | 0.52 | 79.12 | 1.22 | 59.28 | 3.80 | 71.16 | 0.98 | 81.13 | 0.90 | 79.54 | 0.14
CS | 95.13 | 0.19 | 95.81 | 0.07 | 94.48 | 0.12 | 94.80 | 0.34 | 95.18 | 0.06 | 95.81 | 0.06
Photo | 96.58 | 0.09 | 96.51 | 0.10 | 95.48 | 0.15 | 96.21 | 0.11 | 96.56 | 0.16 | 95.86 | 0.12