capbtabboxtable[][]

# Tuning the Geometry of Graph Neural Networks

Sowon Jeong
Department of Statistics
University of Chicago
Chicago, IL, 60637
<EMAIL_ADDRESS>
&Claire Donnat
University of Chicago
Chicago, IL, 60637
<EMAIL_ADDRESS>

###### Abstract

By recursively summing node features over entire neighborhoods, spatial graph
convolution operators have been heralded as key to the success of Graph Neural
Networks (GNNs). Yet, despite the multiplication of GNN methods across tasks
and applications, the impact of this aggregation operation on their
performance still has yet to be extensively analyzed. In fact, while efforts
have mostly focused on optimizing the architecture of the neural network,
fewer works have attempted to characterize (a) the different classes of
spatial convolution operators, (b) how the choice of a particular class
relates to properties of the data , and (c) its impact on the geometry of the
embedding space. In this paper, we propose to answer all three questions by
dividing existing operators into two main classes (symmetrized vs. row-
normalized spatial convolutions), and show how these translate into different
implicit biases on the nature of the data. Finally, we show that this
aggregation operator is in fact tunable, and explicit regimes in which certain
choices of operators — and therefore, embedding geometries — might be more
appropriate.

##  1 Introduction and Motivation

As the extension of the Deep Neural Network (DNN) machinery to the graph
setting, Graph Neural Networks (GNN) offer a powerful paradigm for extending
Machine Learning tools to the analysis of relational data, typically modelled
through a graph [2, 12, 25, 28, 52, 57]. The recent impressive success of GNNs
across tasks and applications [7, 21, 22, 29, 31, 51] in dealing with this
complex data type has been attributed to their two main components (see Figure
1) : (a) a convolution operator $\mathcal{C}$ (or propagation operator [57,
58]) that aggregates information contained in the neighborhood of any given
node to create neighborhood-aware embeddings; and  b) a non-linear layer — or
transformator[58] —, that multiplies the convolved features by a weight matrix
before applying a non-linearity. All weight and bias parameters of the GNN are
typically trained in an end-to-end fashion and, as for Deep Neural Networks,
have been deemed essential in creating powerful non-linear node embeddings
that can be tailored to any downstream prediction task. Depending on the
architecture of the network, such graph convolution blocks are then stacked
and/or repeated to encode varying “receptive depths” [18, 28, 50]. More
formally, denoting as $H^{(k)}$ the output of the $k^{th}$ layer, GNNs can be
broadly understood as a pipeline of sequential node convolutions of the form
$H^{(k)}_{u}=\sigma(\mathcal{C}_{\mathcal{N}(u)}(H^{(k-1)})W_{k}+b_{k})$,
where $H^{(0)}=X$ are the nodes’ raw features, $\sigma$ is a non-linearity
(e.g. ReLU), and $\mathcal{C}_{\mathcal{N}(u)}$ is the convolution operator
applied to the neighborhood $\mathcal{N}(u)$ of node $u.$ The final layer is
always taken to be linear and written as:

$\displaystyle
H_{u}^{(K)}=\mathcal{C}_{\mathcal{N}(u)}(H^{(K-1)})W^{(K)}+b^{(K)}.$ (1)

Throughout this paper, we interpret the quantity
$\mathcal{C}_{\mathcal{N}(u)}(H^{(K-1)})$ as our node embeddings, so that the
last layer can be understood as a generalized linear model [32] operating on
the transformed input features $\mathcal{C}_{\mathcal{N}(u)}(H^{(K-1)})$.

Figure 1: Graph Neural Network Block: Illustration of the aggregation
(convolution) and transformation steps within each GNN block. GNNs blocks are
typically concatenated to allow information to percolate from all parts of the
network.

The convolution operator. Most existing theoretical analyses of GNNs draw a
distinction between two main classes of convolution operators
$\mathcal{C}$[57]: spectral operators [10, 12, 19, 20, 26], that act of the
eigenvectors of some version of the Graph Laplacian (defined in its
unnormalized version as $L=D-A$, with $A$ the adjacency matrix and $D$ the
degree matrix), and spatial operators, that recursively aggregate node
features within a given neighborhood. While the dichotomy between the two is
in practice often attenuated by their implementation (spectral methods usually
resort to using low-order Chebychev polynomials of the Laplacian [10, 44, 43],
thus effectively “localizing” the signal), these two types of approaches have
different interpretations and downstream consequences for the analysis of the
data. Consequently, in this paper, we propose to focus on spatial
convolutions, as popularized by the framework of Kipf et al [28]. In this
case, for each source node $u$, the aggregation operator usually consists in
summing nodes features over its entire neighborhood $\mathcal{N}(u)$, so that
the convolution becomes the function:
$\mathcal{C}:\\{X_{v}\\}_{v\in\mathcal{N}(u)}\to\mathcal{C}(\\{X_{v}\\}_{v\in\mathcal{N}(u)})=SX$,
where $S$ is a weight matrix. Kipf et al [28] suggest taking $S$ to be
normalized adjacency matrix with added self-loops:
$S=\hat{D}^{-1/2}\hat{A}D^{-1/2}$, where $\hat{A}=A+I$ is the adjacency matrix
of the graph with self-loops, $\hat{D}$ its diagonal degree matrix, and
$X\in\mathbb{R}^{n\times p}$ is the feature matrix for the $n$ nodes. The
summation is crucial in preserving permutation equivariance of the
neighborhood, and has been promoted as being able to construct features that
encode long-range dependencies: by repeating and stacking multiple GNN layers,
information can percolate at various distances through the graph — thus
efficiently capturing information contained in both the nodes’ features and
the graph structure.

Variations on the convolution operator. While GNN methods have grown
increasingly popular, the spatial convolution operator seems to have received
a little less attention from the community. Table 2 in Appendix A provides a
summary of the main graph convolution operators that are currently available
in the Pytorch geometric package [16] — here taken as a proxy for the most
popular convolution choices. As observed from this table, all of these
operators rely on a (weighted) sum of neighborhood features, in line with the
framework of Kipf et al [28]. In fact, while GraphSage [25] has been attempted
using “max” pooling and an LSTM version of the convolution operator, the
authors did not report any significant advantage of these methods over the
simple sum. Similarly, in [54], the authors show that a simple summation is
often sufficient to characterize a multiset. Thus, without too much loss of
generality, we restrict our study to sum-based aggregators. In this setting,
two additional main variations have appeared over the recent years: attention-
based spatial convolutions ([5, 47, 53]), which attempt to learn edge weights
tailored the task at hand, and more broadly, weighted spatial convolutions
(e.g. using graphon weights, [37, 40], kernels [35, 15] among others[56]),
that refine the adjacency matrix by endowing it with edge intensities. While
these efforts have focused on defining “the best edge weights”, little
attention has been put on the type of convolutions that these yield. Yet,
attention-based convolutions tend to be row-normalized, while the latter
usually suggest weighted symmetrized adjacencies. Our purpose here is to show
that this choice is not innocuous, and translates into fundamental differences
in the geometry of the embedding space.

Prior work: studying the effect of the Convolution operator. The literature
focusing on understanding the inner mechanisms behind the success of Graph
Neural Networks has considerably expanded over the past few years. Most
notably, an important body of theoretical work has focused on understanding
the role of this convolution operator in phenomena such as oversmoothing [36,
6, 8] and oversquashing[1, 46]. In this setting, most of the analyses are led
from a spectral perspective, relating the behavior of the embeddings to
properties of the eigenvalues of the convolution operator. However,to the best
of our knowledge, none of these approaches have specifically focused on
understanding the effect of the convolution operator on the underlying
geometry of these embeddings, nor has attempted to tie these properties to
topological properties of the underlying nodes.

Contributions. The objective of this paper is to answer three questions:(a)
how does the choice of a particular convolution operator affect the
organisation of the embedding space, (b) how does it relate to the original
properties (ie features and topological distances) of the graph, and (c) what
is the most appropriate convolution operator for a given dataset? We will
attempt and answer all three questions by studying two larger families of row-
normalized and symmetrized convolution operators (parametrized by the
variables $\alpha\in[0,1]$ and $\beta\in\mathbb{R}^{+}$), allowing to show how
the convolution operator itself is in fact tunable. In particular, we will
show different values of $\alpha$ and $\beta$ impact the organization of the
latent space (Section 3) and the inherent geometry of the embeddings (Section
4), and characterize regimes in which certain choices of operators might be
more relevant than others.

##  2 Defining a family of convolution operators

To analyse the impact of the convolution operator on the embedding geometry,
we define two main families of spatial convolutions:

a. Symmetrized Convolutions Operators,

defined as the family of operators of the form:

$\displaystyle\mathcal{F}=\big{\\{}M_{\alpha,\beta}=D_{\beta}^{-\alpha}(A+\beta
I)D_{\beta}^{-\alpha}\big{|}{\alpha\in[0,1],\beta\in[0,+\infty),D_{\beta}=\text{diag}\big{(}(A+\beta
I)\mathbbm{1})\big{)}}\big{\\}}.$ (2)

Here, $D_{\beta}$ is the degree matrix associated with the $\beta$-augmented
adjacency matrix $A+\beta I$. Note that this family is a generalization of the
traditional GCN convolution $S_{GCN}=\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}$,
which corresponds here to a choice of $\alpha=0.5$ and $\beta=1$. The choice
$\alpha=0.5$ and $\beta=2$ also features amongst the default implementations
in Pytorch Geometric [16]. Similarly, the convolution operator indexed by
$\alpha=0,\beta=1$ corresponds to a version of the GIN convolution [54], and
more generally, the sum-based message-passing versions of GNNs [2] — another
popular set of choices for GNN algorithms.

b. Row-normalized Convolution operators

, which we define the general family of the form:

$\displaystyle\mathcal{M}=\big{\\{}D_{(\alpha,\beta)}^{-1}M_{\alpha,\beta},\qquad\text{with
}D_{(\alpha,\beta)}^{-1}=\text{diag}\big{(}M_{\alpha,\beta}\mathbbm{1})\big{)}\big{|}M_{\alpha,\beta}\in\mathcal{F}\big{\\}}$
(3)

This family encompasses a number of operators, such as the sum-based
convolution deployed in GraphSage[25] — and, to some extent, that of GAT [47],
which considers row-normalized convolutions on a modified version of the
adjacency matrix.

For both families of convolution operators, the parameter $\alpha$ impact the
weight assigned to nodes with high degree: as $\alpha$ increases, high-degree
nodes are increasingly penalised, so that their contribution to neighbouring
node embeddings decreases (relatively to lower degree nodes). On the other
hand, $\beta$ can be interpreted as capturing the amount of “innovation” or
relevant information that the source node brings to the embedding with respect
to its neighbourhood. In particular, for high values of $\beta$, the source
node’s contribution to the node overweighs that of the neighborhood, so the
embedding is essentially identical to the source node’s. Consequently, $\beta$
allows us to interpolate between the traditional GNN regime ($\beta=1$) and
the MLP setting.

Empirical consequences of a choice of operator. While seemingly specious,
these families inherently make different assumptions on the nature of the
data. More precisely, row-normalized convolutions create new embeddings that
are convex combinations of the neighbors. This implicitly assumes that the
data lives on some smooth Riemannian manifold, where the degree or centrality
of a node corresponds to an assumption on the sampling distribution over
$\mathcal{M}$: nodes with high degree correspond to “well sampled” areas of
the manifold. Therefore, in this setting, it is intuitively possible to get an
accurate representation of the local information by averaging neighbourhood
features: the higher the degree, the higher the amount of certainty around the
node’s value. By contrast, symmetrized embeddings are weighted sums — but not
convex combinations — of neighbours. Here, the sum simply plays the role of a
permutation-invariant aggregation operator[24], and as we will see, is able to
encode topological features (e.g. structural roles [13]).

Experiments. Finally, to motivate our study before diving into more
theoretical considerations, we propose to highlight the impact of the choice
using standard benchmarks in the literature (we refer the reader to Appendix D
for an overview of the properties of these datasets). Figure 2(b) highlights
the impact of the value of $\alpha$ and $\beta$ on the classification accuracy
for the Cora dataset. In particular, for the symmetric operator, the value of
$\alpha$ seems to drive the “first order” difference, and exhibits the
potential to vastly influence the performance. By contrast, the choice of
$\beta$ seems to affect the performance less — unless $\beta$ becomes too big
and overweighs the rest of the neighbors. This effect might be due to the
significant level of homophily in the Cora dataset: in this setting, the
source node’s feature vector is fairly redundant with that of its neighbours.
However, we show in Appendix D additional examples where the impact of $\beta$
is much more substantial. Most strikingly, the choice of $\alpha$ seems to
have a significant effect on the performance of the symmetrized GCN, with a
phase transition at $\alpha=0.5$: for values of $\alpha$ greater than this
threshold, the performance drops quite substantially. Noticeably, in the
“poor” performance region, the interaction between $\alpha$ and $\beta$ is
more marked: choosing low value of $\beta$ (i.e. $\beta=0$) seems to mitigate
the decrease in performance.

(a) Accuracy as a function of $\alpha$ ($\beta=1$).

(b) Cora dataset: test accuracy as a function of $\alpha$ and $\beta$

Figure 2: Results for Cora for our family of convolutions defined in Eq.2 and
Eq.3 (50 independent experiments, selecting a random training set and test
set). Note the strong dependency of the results on both $\alpha$ and $\beta$
for the normalized convolution.

(a) Amazon Photos ($h_{e}=0.83$)

(b) Cornell ($h_{e}=0.30$)

(c) Wisconsin ($h_{e}=0.21$)

Figure 3: Effect of $\alpha$ on the performance of the algorithm for our
family of convolutions defined in Eq.2 and Eq.3 (30 independent experiments,
with random training and test set). Here, $h_{e}$ denotes the edge homophily
in the dataset (defined as the fraction of edges whose vertices share the same
label) Note the strong dependency of the results on $\alpha$. See Appendix D
for further details and results.

Focusing on the effect of $\alpha$ (and setting $\beta=1$), we try using our
convolution operators with varying intensities of $\alpha$ (using a GCN
architecture), and report the test accuracy and standard deviation over 30
random experiments. The results are presented in Table 1 (see Appendix D for
the experiment parameters). We highlight three main points: (i) $\alpha$
significantly impacts the performance of the GCN architecture;and (ii)
$\alpha$ is tunable and should be optimized – in fact, the default value
$\alpha=0.5$ that is usually used in for the convolution operator is not
necessarily the best. Choosing a value of $\alpha=0.1$ for the CoAuthor CS
dataset for instance results in an average test accuracy of 93%, a 4.37%
increase from that using the default value $\alpha=0.5$. Similarly, using
$\alpha=0.3$ on Amazon increases the accuracy by 6.7% compared to
$\alpha=0.5$. Finally, we observe that (iii) the row-normalized operator is
substantially more robust to the tuning of $\alpha$. These observations seem
to hold across datasets, as shown in Appendix D.

| Alpha |  |  |  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
Dataset | Convolution Type | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0
| Symmetric | 77.02±2.13 | 77.85±1.7 | 78.91±1.78 | 79.37±1.78 | 79.23±2 | 77.63±2.53 | 72.71±3.43 | 60.67±4.09 | 41.59±5.71 | 31.19±2.59
Cora | Row-Normalized | 78.12±2.27 | 78.08±2.01 | 77.97±2.16 | 77.83±2.1 | 77.81±2.07 | 77.73±1.91 | 77.3±2.24 | 77.33±2.21 | 77.24±2.01 | 77.1±2.2
| Symmetric | 75.41±2.51 | 76.09±2.38 | 76.63±2.51 | 76.79±2.48 | 75.4±3.81 | 68.27±6.82 | 54.62±8.52 | 44.11±5.36 | 40.57±2.13 | 39.9±2.09
PubMed | Row-Normalized | 74.42±3.82 | 74.62±3.76 | 74.74±3.65 | 74.75±3.44 | 74.68±3.45 | 74.48±3.44 | 74.28±3.38 | 73.92±3.36 | 73.73±3.36 | 73.42±3.44
| Symmetric | 65.06±2.74 | 65.5±2.57 | 66.51±2.49 | 67.59±2.59 | 67.45±2.56 | 67.32±3.04 | 65.53±3.58 | 60.77±4.17 | 51.41±4.86 | 38.2±5.07
Citeseer | Row-Normalized | 66.69±2.87 | 66.75±2.99 | 66.79±2.69 | 66.99±3.07 | 66.74±2.71 | 66.91±2.84 | 67.02±3.03 | 66.98±2.92 | 66.93±2.92 | 66.96±2.97
| Symmetric | 93.02±0.27 | 92.93±0.25 | 92.9±0.21 | 92.32±0.26 | 88.66±0.39 | 77.88±0.89 | 52.34±1.93 | 24.91±0.48 | 22.63±0.29 | 22.63±0.29
Coauthor CS | Row-Normalized | 88.97±0.4 | 89.4±0.43 | 89.74±0.41 | 90.01±0.45 | 90.13±0.51 | 90.21±0.5 | 90.29±0.5 | 90.26±0.47 | 90.3±0.44 | 90.24±0.42
| Symmetric | 58.77±18.34 | 88.67±1.62 | 90.09±1.02 | 89.18±1.07 | 83.23±1.64 | 37.12±1.4 | 33.17±0.93 | 32±0.91 | 29.05±0.94 | 27.47±0.86
Amazon Photo | Row-Normalized | 82.09±1.34 | 83.75±1.13 | 84.97±1.34 | 86.15±1.26 | 86.75±1.44 | 87.33±1.18 | 88.01±1.11 | 87.9±1.2 | 88.05±0.99 | 87.46±1.3
| Symmetric | 27.06±0.61 | 27.43±0.64 | 27.74±0.61 | 28.27±0.54 | 28.58±0.57 | 28.75±0.52 | 28.9±0.56 | 28.83±0.6 | 28.51±0.67 | 28.33±0.64
Actor | Row-Normalized | 29.42±0.73 | 29.97±0.54 | 30.33±0.65 | 30.71±0.71 | 31±0.83 | 31.26±0.71 | 31.37±0.72 | 31.53±0.6 | 31.58±0.6 | 31.63±0.6
| Symmetric | 51.04±4.08 | 51.01±3.25 | 51.04±2.91 | 51.28±3.08 | 51.25±3.12 | 52.29±3.06 | 53.65±3.21 | 54.38±4.17 | 54.55±3.97 | 54.55±4.65
Cornell | Row-Normalized | 63.78±4.39 | 64.13±4.8 | 63.96±4.53 | 64.65±4.51 | 64.83±4.74 | 65.52±4.65 | 65.87±4.72 | 65.94±4.6 | 66.46±4.5 | 66.39±4.61
| Symmetric | 48.03±3.69 | 49.39±3.5 | 50.29±3.04 | 51.09±3.15 | 51.79±3.1 | 51.6±3.65 | 50.8±4.59 | 49.92±5.04 | 49.07±5.16 | 48.21±4.75
Wisconsin | Row-Normalized | 50.24±4.88 | 51.04±5.38 | 51.28±5.77 | 52.03±6.07 | 52.91±6.32 | 53.6±5.82 | 54.4±6.01 | 55.28±6.06 | 55.76±6.01 | 56.19±5.84

Table 1: Results across 30 different experiments across datasets.

We emphasize here that the scope of this paper is not to suggest another
convolution operator that would achieve state-of-the-art results. Rather,
through this series of experiments, we hope to have convinced the reader that,
empirically, the choice of convolution is important and can help gain up to
almost 7% accuracy on traditional GNN approaches, with no modifications to the
architecture of the network whatsoever. Motivated by these observations, the
rest of this paper focuses on analysing these convolution operators’
characteristics, and subsequent impact on the geometry properties of the
embedding space.

##  3 The geometrical organization of GNN embeddings in latent space

In this section, we analyse the effect of the convolution operator on the
overall organization of the latent space. Our objective is to (a) characterize
the implicit constraints that these operators put on the geometry (we will see
that nodes with different topological characteristics are pushed to
concentrate in different parts of the embedding space), and (b) identify the
downstream consequences in terms of performance. This discussion will be
driven by considerations on nodes’ topological characteristics — rather than
spectral arguments.

###  3.1 Symmetric Convolutions

We begin our study of the “absolute” latent geometry of our embeddings with
the family of symmetric convolution $\mathcal{M}_{\alpha,\beta}$ (see Equation
2). Contrary to many theoretical analysis, our study here is based on an
analysis of the last (linear) layer of the Graph Neural Network (see Equation
1), since it has the benefit of being a simple linear layer on the node
embeddings (since introduction), denoted as:

$H^{(K)}=S\sigma(H^{(K-1)})=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}Z_{v\cdot}$

where $\mathcal{N}(u)$ denotes the neighborhood of node $u$, $A_{uv}$ is the
(possibly weighted) adjacency matrix, with diagonal equal to $\beta$, and
$Z_{v\cdot}=\sigma(H^{(K-1)}_{v\cdot})$. In the rest of the paper, for ease of
notation, we adopt the notation
$\tilde{\mathcal{N}}(u)=\mathcal{N}(u)\cup\\{u\\}$.

As a first step to study of the effect of the choice of convolution operator
on the latent embedding space, we propose the following lemma.

######  Lemma 3.1.

The last layer of the GNN is a simple linear layer on inputs such that for any
node $u$:

$\displaystyle||SZ||_{2}\leq{||Z||_{2,\infty}}\Big{(}(d_{u}+\beta)^{1-2\alpha}-\alpha\frac{\bar{\Delta}_{u}}{(d_{u}+\beta)^{2\alpha}}+\frac{\alpha(\alpha+1)M}{2}\frac{\overline{\Delta^{2}}_{u}}{(d_{u}+\beta)^{1+2\alpha}}\Big{)}$
(4)

where $\bar{\Delta}_{u}$ (respectively $\overline{\Delta^{2}}_{u}$) are the
weighted averages of the degree differences (respectively, squared degree
differences):

$\bar{\Delta}_{u}=\frac{\sum_{v\in\tilde{\mathcal{N}}(u)}A_{uv}(d_{v}-d_{u})}{d_{u}+\beta}\qquad\overline{\Delta^{2}}_{u}=\frac{\sum_{v\in\tilde{\mathcal{N}}(u)}A_{uv}(d_{v}-d_{u})^{2}}{d_{u}+\beta}.$

In this equation, $||Z||_{2,\infty}=\max_{v}||Z_{v}||_{2}$, and
$M=\frac{d_{\max}+\beta}{\beta+1})^{2}$, where $d_{\max}$ denote the maximal
degree of the nodes in the network.

Proof The proof is simple (see Appendix B), and relies on the triangle
inequality coupled with a MacLaurin expansion of the function
$d_{v}\to\frac{1}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}$ around $0$. ∎

Note that this bound is not necessarily tight. In particular, the proof relies
on an application of the triangular inequality, along with Hölder’s inequality
to separate the convolution from the embeddings. However, while potentially
crude, this bound already allow us to shed more light into the behaviour of
the embedding as a function of the parameters $\alpha$, $\beta$, and their
topology. In particular, this bound allows to highlight:

(a) The determining role of $\alpha$ in organizing the latent space.

The leading term in inequality 4 is $d_{u}^{1-2\alpha}$, and offers a first
explanation for the change of phase we have observed in some of our
experiments in the previous section. For values of $\alpha<0.5$, this term is
an increasing function of the degree: after even a single convolution, nodes
with small degree have less leeway to spread, and will generally remain close
to the origin; high-degree nodes, on the other hand, will be less limited, and
able to spread to far greater radii. Conversely, if $\alpha>0.5$, the upper
bound decreases for nodes with high degree — forcing them to concentrate
around the origin. The parameter $\alpha$ therefore controls the "attraction"
of nodes towards the origin of as a function of their degree.

(b) The effect of $\beta$.

The coefficient $\beta$, on the other hand, acts as added mass to the degree
$d_{u}$ and can be understood as the "strength" of the attraction: for
$\alpha>0.5$, the attraction of high-degree nodes to the origin is an
increasing function of $\beta$. Conversely, for $\alpha<0.5$, the repulsion of
the nodes from the origin is an increasing function of $\beta$.

(c) The influence of the surrounding topology

As previously exhibited, the node degree plays a defining role in "placing"
the node in concentric circles around the origin. The bound also exhibits a
dependency on the neighborhood topology through the terms $\bar{\Delta}_{u}$
and $\bar{\Delta^{2}}_{u}$. Therefore, the more topologically homogeneous the
neighborhood, the lesser the impact of these extra terms. Moreover, as shown
in the proof, $\beta$ also controls the variable $M$: the higher the $\beta$,
the lesser the impact of the neighborhood.

Consequences. The previous observations yield two main conclusions. First, the
choice of the convolution vector drives the geometry of the embedding space:
values of $\beta$ and $\alpha$ allow the embedding space to expand or contract
around the origin. By induction, in a similar fashion to [36], it is possible
to show that consecutive convolutions followed by 1-Lipschitz (e.g. ReLU) non-
linearities contract even further the embedding towards the origin.
The second consequence pertains the accuracy of the recovery. Since the last
layer of GNN is a linear classifier, we can use known results from statistical
theory about the influence of the different points on the performance of the
algorithm. In particular, in linear regression, it is known that high-leverage
points (that is, points with “extreme ” predictor values”) are more likely to
be highly influential points [49] (the same follows for generalized linear
models, with some nuances). As such, by preventing high-degree nodes
(respectively low-degree) to take on extreme embedding value and concentrating
them around the origin, the convolution operator is implicitly limits the
amount of trust, or leverage, that these points may have. We summarize these
observations in the following corollary.

######  Corollary 3.1 (Effect of symmetric convolutions on node embeddings).

In networks with non-homogeneous degree distributions, the exponent $\alpha$
constrains the leverage associated to each of the embeddings as a function of
their degree and local topology:

  * •

For values of $\alpha>0.5$: High-degree nodes are constrained to concentrate
around the origin, allowing the performance of the algorithm be driven by more
peripheral (low-degree) nodes.

  * •

For high-values of $\alpha<0.5$: Low-degree nodes need lie closer to the
origin than their high-degree counterparts, thereby allowing high-degree nodes
to have higher leverage and potentially become more influential.

Experiments. To illustrate these bounds and check their validity, we perform a
set of synthetic experiments. We generate a set of four cliques on 20 nodes
(the ”hubs”). To each node in each clique, we add a link to a sparse Barabasi-
Albert network on 10 nodes (’the periphery’), with parameter $m=1$, so that
the average degree of the periphery is low ($\approx 1$). The peripheries are
endowed with the same class label as their associated hub. Finally, we ensure
that the network is connected by randomly connecting the hubs together (one
new random link per hub). To generate node features, we take the first $k=4$
features to be the one-hot label vector, to which we concatenate 16 additional
“dummy features”(random Gaussians). We finally add Gaussian noise with scale
$\sigma^{2}=4$ entrywise: the result is a feature vector that is only weakly
indicative of the class. The trained embeddings are presented in Figure 4.
Note the lack of separability of the different classes based on their raw
feature vectors, as captured by the PCA plot in the left column. As expected
from our bounds, we observe an inversion of the geometry around the origin as
$\alpha$ increases: high-degree nodes shift from the outskirts of the plot to
being concentrated around the origin as $\alpha$ increases. We also refer the
reader to Appendix D.3.2, in which we also verify these phenomena in standard
datasets by providing PCA and UMAP plots of the corresponding node embeddings.

In order to test corollary 3.1, we modify this setting slightly, and now let
the variance of the noise depend on the degree $d_{u}$ of the node:
$\sigma^{2}_{u}=e^{3(-1.5+\log(d_{u}))}$. This means that low degree nodes
here have very small variance $\sigma<1$, while high-degree noise are
extremely noisy $\sigma\approx 9$. Consequently, we expect that the geometries
in which the high-degree nodes are placed on the outskirts (and have more
leverage), and low-degree nodes are constrained to lie close to the origin
will perform poorly. Conversely, we flip this scenario (we choose
$\sigma^{2}_{u}=e^{3(-1.5+\log(d_{(n-u)})}$ where, if $d_{u}$ has rank
$rk(u)$, $d_{(n-rk(u))}$ is the degree of the $n-rk(u)$ largest node), and
expect the opposite phenomenon. The results are shown in Figure5(b)(a), and
are well aligned with our expectations.

Figure 4: Symmetric Embeddings, plotted using the first two principal
components (left), and the raw latent embeddings (or ‘latent components’,
shown in the right three plots on each row). Note the inversion: the high
degree nodes migrate from the periphery of the latent space ($\alpha=0.2$) to
the origin $(\alpha=0.7)$. See Appendix D for the equivalent plot for row-
normalized Embeddings.

###  3.2 Row-normalized Convolutions

Let us now turn to the case of row-normalized convolutions. In this case, the
convolutions write as:

$SX=\frac{\frac{1}{(d_{u}+\beta)^{\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{1}{(d_{v}+\beta)^{\alpha}}X_{v}}{\sum_{v\in\mathcal{N}(u)}\frac{1}{(d_{u}+\beta)^{\alpha}}\frac{1}{(d_{v}+\beta)^{\alpha}}}=\frac{1}{\sum_{v\in\mathcal{N}(u)}\frac{1}{(d_{v}+\beta)^{\alpha}}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{1}{(d_{v}+\beta)^{\alpha}}X_{v}$

The embedding is thus no longer a function of the degree of the node. Rather,
it lies within the convex hull of its neighbours, whose contributions are
inversely proportional to their degrees. This effect can be strengthened
through different choices of $\alpha$: the decay of a neighbor’s contribution
is an increasing function of $\alpha$. The latter can be compared to an form
of attention that effectively filters out nodes with high-degree: here the
discounting procedure is not learned, but imposed ahead of time. Appendix D.4
and Figure5(b)(b) show the result of the same experiments than in the last
subsection. As in the previous part, the results are less dependent on the
value of $\alpha$.

(a) Results for symmetric convolutions.

(b) Results for row-normalized convolutions.

Figure 5: Results for 50 independent trials of our second experiment using
symmetric (left) and row-normalized (right) convolutions. Note that the
accuracy of the symmetric convolutions increases $\alpha$ increases when the
noise is higher in high-degree nodes, and decreases in the opposite scenario.

##  4 The inherent geometry of node embeddings

We now turn to the analysis of the evolution of the relative distances between
embedding points.

Embedding structural features. The first point that we would like to raise in
this section is that the two families of convolution operators differ
radically in their encoding of topological features.o illustrate this,
consider a simple two-layer GCN such as the one suggested by Kipf et al [28].
In this case, for the directions in which the term is positive, the embedding
$H$ (i.e., the transformed features that are being fed into the last linear
layer) can be written as:

$\displaystyle
H_{u\cdot}=\sum_{k=1}^{d}\sum_{\begin{subarray}{c}v\in\tilde{\mathcal{N}}(u)\\\
(SXW+b)_{vk}\geq
0\end{subarray}}\big{(}S_{uv}(SXW)_{vk}W^{(2)}_{k\cdot}+S_{uv}b_{vk}W^{(2)}_{k\cdot}\big{)}$
(5)

The embedding is thus the sum of two components: a function of a (subset of)
neighboring node features and a term that has the potential to encode local
topology. To see why this is the case, consider a scenario where nodes in
$\mathcal{N}(u)$ are all such that $(SXW+b)_{vk}\geq 0$ for all $k$ or
$(SXW+b)_{vk}<0$ for all $k$. Denote
$\tilde{A}(u)=\\{v\in\tilde{N}(u):\quad(SXW+b)_{vk}\geq 0\quad\text{for all
}k\\}$. In this case, Equation 10 becomes:
$H_{u\cdot}=\sum_{v\in{\tilde{A}(u)}}\big{(}S_{uv}(SX\tilde{W})_{v\cdot}+S_{uv}\tilde{b}_{v\cdot}\big{)}$,
with $\tilde{b}=bW^{(2)}$ and $\tilde{W}=WW^{(2)}$.

Using this notation, it becomes clear that:

  * •

For row-normalized embeddings, for two nodes to be close, it is sufficient for
their neighborhood to have similar features. the distance between two features
can be related to an ANOVA test between two neighborhood, and is devoid of
topological information:

$||H_{u\cdot}-H_{u^{\prime}\cdot}||^{2}=\sum_{j=1}^{p}\Big{(}\overline{(SX\tilde{W})_{\cdot
j}}_{\tilde{A}(u)}-\overline{(SX\tilde{W})_{\cdot
j}}_{\tilde{A}(u^{\prime})}\Big{)}^{2},$

where $\overline{X}_{\tilde{A}(u)}$ denote the mean of $X$ over the set
$\tilde{A}(u)$. Consequently, these embeddings are appropriate when
presumably, topology does not carry information relevant to the prediction.

  * •

For symmetric embeddings, on the other hand, the embedding depends strongly on
the topology:

$H_{uk}=\sum_{v\in{\tilde{A}(u)}}\Big{(}\sum_{w\in\mathcal{N}(v)}\frac{(X\tilde{W})_{wk}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{2\alpha}(d_{w}+\beta)^{\alpha}}\Big{)}+\sum_{v\in{\tilde{A}(u)}}\frac{\tilde{b}_{k}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}$

In this case, note the existence of a bias term that is a function of both the
source node’s degree and that of its neighbours: this bias term can be seen as
an offset that differentiates between high-degree nodes and low-degree nodes.

Let us try and formalize this more precisely through two toy examples that
allow us to control for feature similarity and node similarity separately.

Toy example 1: Identical Topologies, Different features. Consider two nodes
$u$ and $v$ have structurally similar neighborhoods (i.e. there exists a
mapping $\phi$ that transforms each node in the neighborhood of $v$ into its
corresponding one in the neighborhood of $u$, see Figure 6), but whose feature
vectors are different. Mathematically, we write:

$\displaystyle\forall j\in N(v),\quad
X_{j\cdot}=X_{\phi(j)\cdot}+\epsilon,\qquad\epsilon_{jk}\overset{\text{i.i.d}}{\sim}N(0,\sigma^{2}).$

Figure 6: Results for our Structural Equivalents experiment

######  Lemma 4.1.

For symmetric convolution, with probability at least $1-\delta$, with $M$ as
in 3.1, we have:

$\displaystyle||H_{u}-H_{u^{\prime}}||^{2}\leq\mu+2\sqrt{2}\sigma||W||_{2}(d_{u}+\beta)^{1-2\alpha}\sqrt{1+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-1}+\alpha(2\alpha+1)M}\log(1/\delta)$

where
$\mu=\sigma^{2}||W||^{2}\Big{(}(d_{u}+\beta)^{2-4\alpha}+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-4\alpha}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}({d_{u}+\beta})^{-1-4\alpha}\Big{)}.$
Conversely, for row-normalized embeddings:

$\displaystyle||H_{u}-H_{u^{\prime}}||^{2}$
$\displaystyle\leq\mu+2\sqrt{2}\sigma||W||_{2}\sqrt{\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{1}{(d_{v}+\beta)^{2\alpha}}}\log(1/\delta),\quad\mu=\frac{\sigma^{2}||W||^{2}}{\sum_{v\in\tilde{\mathcal{N}}(u)}(d_{v}+\beta)^{-2\alpha}}\frac{1}{1+\beta}$

This highlights fundamental differences in dealing with the embeddings:
symmetric embeddings will shrink distances between nodes depending on their
topology, so that the cluster density is a function of the node degree. The
impact of the topology is expected to be more marked at the extremities of the
spectrum of $\alpha$. The proof is in Appendix C.

Toy example 2: Identical Features, structurally different neighbourhoods.
Conversely, $u$ and $v$ have radically different neighborhoods from a
topological perspective, but have similar features:

$\forall
j\in\tilde{\mathcal{N}}(u)\cup\tilde{\mathcal{N}}(u^{\prime}),X_{j}=\bar{X}+\epsilon$

In this case, as stated earlier in this section, for row-normalized
embeddings, the difference will be 0: the embeddings are therefore more
sensitive to the node feature values that the symmetric convolution.
Conversely, for symmetric convolutions, we can also show (see Appendix C) that
the leading term for the difference is of the order of
$(d_{u}+\beta)^{1-2\alpha}-(d_{u^{\prime}}+\beta)^{1-2\alpha}$ — and is
therefore a decreasing function of $\alpha$.

Experiments. We illustrate these results by running a set of final
experiments. We generate a structurally equivalent networks (see smaller
replica in Figure 6a), and evaluate the distance between untrained embeddings
(using a 2-layer GCN architecture). The mean distance over 100 experiments is
presented in Figure 6b, and a visualization of the latent space for symmetric
convolutions is shown in Figure 6c. As expected, the density of the cluster of
structurally equivalent high-degree nodes (cliques on 40 nodes), in grey
varies as a function of $\alpha$. In AppendixD.3.3, we also provide
visualization of the interplay between node features and topologies on a
subset of real datasets, using the Gromov Wasserstein distance as a way of
measuring the distance of the embedding space with the original
characteristics of the dataset (features and adjacency matrix),

##  5 Conclusion

In conclusion, in this paper, we have shown that the choice of the convolution
operator has fundamental consequences on the geometry of the embedding space:
symmetric convolutions are generally more sensitive to the topology, and
encode it in the embedding,. In that case, the choice of $\alpha$ amounts to
selecting “who to trust”: high-values of $\alpha$ push high-degree nodes
towards the origin, thereby limiting their leverage. Conversely, row-
normalized are more limited in the amount of topological information that they
carry, and convolutions are more robust to the choice of $\alpha$ — this is
probably a better choice when the data is assumed to be sampled from a
manifold (e.g. point cloud data). Our analysis — which we hope to be
insightful — has room for further improvement. Our reasoning relies on upper
bounds which, while providing intuition, are not extremely tight, and could be
complemented with lower bounds to fully characterize the behavior of the
geometry. All experiments resort to using GCN types of architectures. However,
we believe that the intuition and guidelines that we derived from this
analysis will nonetheless hold for other types of architectures.

## References

  * [1] Uri Alon and Eran Yahav.  On the bottleneck of graph neural networks and its practical implications.  arXiv preprint arXiv:2006.05205, 2020.
  * [2] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al.  Relational inductive biases, deep learning, and graph networks.  arXiv preprint arXiv:1806.01261, 2018.
  * [3] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi.  Graph neural networks with convolutional arma filters.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [4] Xavier Bresson and Thomas Laurent.  Residual gated graph convnets.  arXiv preprint arXiv:1711.07553, 2017.
  * [5] Shaked Brody, Uri Alon, and Eran Yahav.  How attentive are graph attention networks?  arXiv preprint arXiv:2105.14491, 2021.
  * [6] Chen Cai and Yusu Wang.  A note on over-smoothing for graph neural networks.  arXiv preprint arXiv:2006.13318, 2020.
  * [7] Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun.  Spatially-aware graph neural networks for relational behavior forecasting from sensor data.  arXiv preprint arXiv:1910.08233, 2019.
  * [8] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3438–3445, 2020.
  * [9] Ronald R Coifman and Stéphane Lafon.  Diffusion maps.  Applied and computational harmonic analysis, 21(1):5–30, 2006.
  * [10] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  arXiv preprint arXiv:1606.09375, 2016.
  * [11] Francesco Di Giovanni, Giulia Luise, and Michael Bronstein.  Heterogeneous manifolds for curvature-aware graph embedding.  2022\.
  * [12] Xiaowen Dong, Dorina Thanou, Laura Toni, Michael Bronstein, and Pascal Frossard.  Graph signal processing for machine learning: A review and new perspectives.  IEEE Signal processing magazine, 37(6):117–127, 2020.
  * [13] Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec.  Learning structural node embeddings via diffusion wavelets.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1320–1329, 2018.
  * [14] Jian Du, Shanghang Zhang, Guanhang Wu, José MF Moura, and Soummya Kar.  Topology adaptive graph convolutional networks.  arXiv preprint arXiv:1710.10370, 2017.
  * [15] Aosong Feng, Chenyu You, Shiqiang Wang, and Leandros Tassiulas.  Kergnns: Interpretable graph neural networks with graph kernels.  arXiv preprint arXiv:2201.00491, 2022.
  * [16] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  arXiv preprint arXiv:1903.02428, 2019.
  * [17] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  Pot: Python optimal transport.  Journal of Machine Learning Research, 22(78):1–8, 2021.
  * [18] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti.  Sign: Scalable inception graph neural networks.  arXiv preprint arXiv:2004.11198, 2020.
  * [19] Fernando Gama, Antonio G Marques, Geert Leus, and Alejandro Ribeiro.  Convolutional neural network architectures for signals supported on graphs.  IEEE Transactions on Signal Processing, 67(4):1034–1049, 2018.
  * [20] Fernando Gama, Alejandro Ribeiro, and Joan Bruna.  Diffusion scattering transforms on graphs.  arXiv preprint arXiv:1806.08829, 2018.
  * [21] Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al.  Utilizing graph machine learning within drug discovery and development.  Briefings in bioinformatics, 22(6):bbab159, 2021.
  * [22] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International Conference on Machine Learning, pages 1263–1272. PMLR, 2017.
  * [23] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring network structure, dynamics, and function using networkx.  In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008.
  * [24] William L Hamilton.  Graph representation learning.  Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1–159, 2020.
  * [25] William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  arXiv preprint arXiv:1706.02216, 2017.
  * [26] Mikael Henaff, Joan Bruna, and Yann LeCun.  Deep convolutional networks on graph-structured data.  arXiv preprint arXiv:1506.05163, 2015.
  * [27] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for pre-training graph neural networks.  arXiv preprint arXiv:1905.12265, 2019.
  * [28] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [29] Michelle M Li, Kexin Huang, and Marinka Zitnik.  Representation learning for networks in biology and medicine: Advancements, challenges, and opportunities.  arXiv preprint arXiv:2104.04883, 2021.
  * [30] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  arXiv preprint arXiv:1511.05493, 2015.
  * [31] Tengfei Ma, Junyuan Shang, Cao Xiao, and Jimeng Sun.  Genn: predicting correlated drug-drug interactions with graph energy neural networks.  arXiv preprint arXiv:1910.02107, 2019.
  * [32] Peter McCullagh and John A Nelder.  Generalized linear models.  Routledge, 2019.
  * [33] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * [34] Facundo Mémoli.  Gromov–wasserstein distances and the metric approach to object matching.  Foundations of Computational Mathematics, pages 1–71, 2011.  10.1007/s10208-011-9093-5.
  * [35] Giannis Nikolentzos and Michalis Vazirgiannis.  Random walk graph neural networks.  Advances in Neural Information Processing Systems, 33:16211–16222, 2020.
  * [36] Kenta Oono and Taiji Suzuki.  Graph neural networks exponentially lose expressive power for node classification.  arXiv preprint arXiv:1905.10947, 2019.
  * [37] Alejandro Parada-Mayorga, Luana Ruiz, and Alejandro Ribeiro.  Graphon pooling in graph neural networks.  In 2020 28th European Signal Processing Conference (EUSIPCO), pages 860–864. IEEE, 2021.
  * [38] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  2019\.
  * [39] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  2020\.
  * [40] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro.  Graphon neural networks and the transferability of graph neural networks.  Advances in Neural Information Processing Systems, 33:1702–1712, 2020.
  * [41] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  2018\.
  * [42] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun.  Masked label prediction: Unified message passing model for semi-supervised classification.  arXiv preprint arXiv:2009.03509, 2020.
  * [43] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE signal processing magazine, 30(3):83–98, 2013.
  * [44] David I Shuman, Pierre Vandergheynst, and Pascal Frossard.  Chebyshev polynomial approximation for distributed signal processing.  In 2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS), pages 1–8. IEEE, 2011.
  * [45] Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li.  Attention-based graph neural network for semi-supervised learning.  arXiv preprint arXiv:1803.03735, 2018.
  * [46] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  Understanding over-squashing and bottlenecks on graphs via curvature.  arXiv preprint arXiv:2111.14522, 2021.
  * [47] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [48] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * [49] Sanford Weisberg.  Applied linear regression, volume 528.  John Wiley & Sons, 2005.
  * [50] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In International conference on machine learning, pages 6861–6871. PMLR, 2019.
  * [51] Shiwen Wu, Fei Sun, Wentao Zhang, and Bin Cui.  Graph neural networks in recommender systems: a survey.  arXiv preprint arXiv:2011.02260, 2020.
  * [52] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE transactions on neural networks and learning systems, 2020\.
  * [53] Yu Xie, Yuanqiao Zhang, Maoguo Gong, Zedong Tang, and Chao Han.  Mgat: Multi-view graph attention networks.  Neural Networks, 132:180–189, 2020.
  * [54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [55] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov.  Revisiting semi-supervised learning with graph embeddings.  2016\.
  * [56] Fengyi Zhang, Zhiyong Liu, Fangzhou Xiong, Jianhua Su, and Hong Qiao.  Wagnn: A weighted aggregation graph neural network for robot skill learning.  Robotics and Autonomous Systems, 130:103555, 2020.
  * [57] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  AI Open, 1:57–81, 2020.
  * [58] K Zhou, Y Dong, K Wang, WS Lee, B Hooi, H Xu, and J Feng.  Understanding and resolving performance degradation in graph convolutional networks.  arXiv preprint arXiv:2006.07107, 2020.
  * [59] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  2020\.

.

##  Appendix A Comparison of GNN operators

Method Operator GCNConv [28]
$x_{i}^{\prime}=\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}XW$
$x_{i}^{\prime}=\sum_{j\in\mathcal{N}(i)}\frac{e_{ij}}{\sqrt{\hat{d}_{i}\hat{d}_{j}}}x_{j}$
ChebConv [10] $X=XW_{1}+\hat{L}XW_{2}+(2\hat{L}^{2}X-X)W_{3}$ with
$\hat{L}=\frac{2}{\lambda_{\max}}L-I$ SAGEConv [25]
$x=W_{1}x_{i}+W_{2}\bar{X}_{j\in\mathcal{N}(i)}$ with
$\bar{X}_{j\in\mathcal{N}(i)}=\frac{\sum_{j\in\mathcal{N}(i)}x_{j}}{d_{i}}$
GraphConv[33]
$x_{i}^{\prime}=W_{1}x_{i}+W_{2}\sum_{j\in\mathcal{N}(i)}e_{ij}x_{j}$
GatedGraphConv [30] $h_{i}^{(0)}=x_{i}||0$
$m_{i}^{(l+1)}=\sum_{j\in\mathcal{N}(i)}e_{j,i}Wh_{j}^{(l)}$
$h_{i}^{(l+1)}=GRU(m_{i}^{(l+1)},h_{i}^{(l)}$ ResGatedGraphConv [4]
$x_{i}^{\prime}=W_{1}x_{i}+\sum_{j\in\mathcal{N}(i)}\eta_{ij}\circ W_{2}x_{j}$
with $\eta_{ij}=\sigma(W_{3}x_{i}+W_{4}x_{j})$ GAT [47]/GATv2Conv [5]
$x_{i}^{\prime}=\alpha_{ii}Wx_{i}+\sum_{j\in\mathcal{N}(i)}\alpha_{ij}Wx_{j}$
with $\alpha_{ij}=\frac{\exp\\{\text{LeakyReLU}(a^{T}[\Theta x_{i}||\Theta
x_{j}]\\}}{\sum_{k\in\mathcal{N}(i)\cup\\{i\\}}\exp\\{\text{LeakyReLU}(a^{T}[\Theta
x_{i}||\Theta x_{j}]\\}}$ AGNN [45] $X^{\prime}=PX$
$P_{ij}=\frac{\exp\\{\beta\dot{\cos}(x_{i},x_{j})\\}}{\sum_{k\in\mathcal{N}(i)\cup\\{i\\}}\exp\\{\beta\dot{\cos}(x_{i},x_{k})\\}}$
Transformer Conv [42]
$x_{i}^{\prime}=W_{1}x_{i}+\sum_{j\in\mathcal{N}(i)}\alpha_{ij}W_{2}x_{j}$
$\alpha_{ij}=\text{Softmax}\frac{(W_{3}x_{i})^{T}(W_{4}x_{j})}{\sqrt{d}}$
TAGConv [14] $X^{\prime}=\sum_{k=0}^{K}(D^{-1/2}AD^{-1/2})^{k}XW_{k}$ GINConv
[54]
$X^{\prime}=h_{\theta}\Big{(}(\mathbf{A}+(1+\epsilon)\mathbf{I})X\Big{)})$
GINEConv [27]
$x^{\prime}_{i}=h_{\theta}\Big{(}((1+\epsilon)x_{i}+\sum_{j\in\mathcal{N}(i)}\text{ReLU}(x_{j}+e_{ij})\Big{)})$
ARMAConv [3] $X^{\prime}=\frac{1}{K}\sum_{k=1}^{K}X_{k}^{(T)}$ SGCConv [50]
$X^{\prime}=(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2})^{K}XW$

Table 2: Comparison of the different convolution operators

##  Appendix B Proofs of Section 3

Proof[Lemma 3.1] As per section 3, we study the last (linear) layer of the
Graph Neural Network (see Equation 1). This layer has indeed the advantage of
being linear — and thereby easy to analyse. In this setting, we simply want to
show that the use of a spatial convolution imposes a special geometry on the
embeddings. By induction, we expect this result to hold for the other layers
as well (assuming that the non-linearity that is chosen is ReLU — other
choices of non-linearities (e.g. $\tanh$), while linearisable close to 0,
would require a more careful proof).

In this section, we analyse the embedding that is fed into the last linear
layer, denoted as:

$H^{(K)}=S\sigma(H^{(K-1)})=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}Z_{v\cdot}$

where $\mathcal{N}(u)$ denotes the neighbourhood of node $u$, $A_{uv}$ is the
(potentially weighted) adjacency matrix, with diagonal equal to $\beta$, and
$Z_{v\cdot}=\sigma(H^{(K-1)}_{v\cdot})$.

Writing $\Delta_{v}={d_{v}-d_{u}}$, note that $H^{(K)}$ can be rewritten as:

$\displaystyle H^{(K)}$
$\displaystyle=\frac{1}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(1+\frac{\Delta_{v}}{d_{u}+\beta})^{\alpha}}Z_{v\cdot}$
(6)

Note that $\frac{\Delta_{v}}{d_{u}+\beta}\geq-1$ as long as $d_{v}-d_{u}\geq-
d_{u}-\beta\implies d_{v}\geq-\beta$, which holds necessarily, since
$d_{v}\geq 1$. Since the function $x\to(x+1)^{-\alpha}$ is infinitely
differentiable for $x\in(-1,\infty)$, using the Maclaurin expansion of
$(x+1)^{-\alpha}$ around $0$, we know that there exists
$\xi\in[\min(0,x),\max(0,x)]$ such that:

$\displaystyle\frac{1}{(x+1)^{\alpha}}=1-\alpha
x+\frac{\alpha(\alpha+1)}{2}\frac{x^{2}}{(\xi+1)^{\alpha+2}}$ (7)

It is easy to check that if $\frac{\Delta_{v}}{d_{u}+\beta}\geq 0$, then
$\frac{1}{(1+\xi)^{\alpha+2}}\leq 1$. Conversely, if $d_{v}\leq d_{u}$, then
$\frac{1}{(\xi+1)^{\alpha+2}}\frac{1}{(1+\frac{\Delta_{v}}{d_{u}+\beta})^{\alpha+2}}\leq\frac{1}{(1+\frac{1-d_{u}}{d_{u}+\beta})^{\alpha+2}}\leq\frac{1}{(\frac{\beta+1}{d_{u}+\beta})^{2+\alpha}}\leq(d_{\max}+\beta)^{2+\alpha}=M$.

Equation 6 thus becomes:

$\displaystyle||SZ||_{2}\leq\frac{1}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(1+\frac{\Delta_{v}}{d_{u}+\beta})^{\alpha}}||Z_{v}||_{2}$
$\displaystyle\leq\frac{||Z||_{2,\infty}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}A_{uv}(1-\alpha\frac{\Delta_{v}}{d_{u}+\beta}+\frac{\alpha(\alpha+1)M}{2}\frac{\Delta^{2}_{v}}{(d_{u}+\beta)^{2}})$
$\displaystyle={||Z||_{2,\infty}}\Big{(}(d_{u}+\beta)^{1-2\alpha}-\alpha\frac{\bar{\Delta}_{v}}{(d_{u}+\beta)^{2\alpha}}+\frac{\alpha(\alpha+1)M}{2}\frac{\overline{\Delta^{2}}_{v}}{(d_{u}+\beta)^{1+2\alpha}}\Big{)}$
(8)

where $\bar{\Delta}_{u}$ (respectively $\bar{\Delta^{2}}_{u}$) are the
weighted averages of the degree differences:
$\bar{\Delta}_{u}=\frac{\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}A_{uv}\Delta_{v}}{d_{u}+\beta}$
(respectively, squared degree differences:
$\bar{\Delta^{2}}_{u}=\frac{\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}A_{uv}\Delta_{v}^{2}}{d_{u}+\beta}$).
In the previous equation, we have also introduced the notation
$||Z||_{2,\infty}=\max_{v}||Z_{v}||_{2}$.

Remark Note that, when $\sigma=\text{ReLU}$, then, by positivity of the
entries in $Z$, we have the following (entrywise) inequality:

$\displaystyle 0\leq
SZ\leq\frac{1}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(1+\frac{\Delta_{v}}{d_{u}+\beta})^{\alpha}}Z_{v}$
$\displaystyle\leq{||Z||_{\infty}}\Big{(}(d_{u}+\beta)^{1-2\alpha}-\alpha\frac{\bar{\Delta}_{v}}{(d_{u}+\beta)^{2\alpha}}+\frac{\alpha(\alpha+1)M}{2}\frac{\overline{\Delta^{2}}_{v}}{(d_{u}+\beta)^{1+2\alpha}}\Big{)}$
(9)

∎

##  Appendix C Proofs of Section 4

###  C.1 Section 4: Proof of the observations

We begin by revisiting in greater details the observations made in section 4.
To see how the two families of spatial operators differ in the importance they
attribute to topology and node feature information, consider a simple two-
layer GCN such as suggested by Kipf et al [28]. In this setting, node
embeddings can be written as: $H=S\sigma(SXW+b),$ so that the output of the
network is $Y=S\sigma(SXW+b)W^{(2)}+b^{(2)}=HW^{(2)}+b^{(2)}$. We also choose
the non-linearity $\sigma$ to be the ReLU function. In this case, for the
directions in which the term is positive, the embedding $H$ (ie, the
transformed features that are being fed into the last linear layer) can be re-
written as:

$\displaystyle
H_{u\cdot}=\sum_{k=1}^{d}\sum_{\begin{subarray}{c}v\in\tilde{\mathcal{N}}(u)\\\
(SXW+b)_{vk}\geq
0\end{subarray}}\big{(}S_{uv}(SXW)_{vk}W^{(2)}_{k\cdot}+S_{uv}b_{vk}W^{(2)}_{k\cdot}\big{)}$
(10)

The embedding is thus the sum of two components: a function of a (subset of)
neighbouring feature vector and a term that has the potential to encode local
topology. To see why this is the case, consider a scenario where nodes in
$\mathcal{N}(u)$ are all such that $(SXW+b)_{vk}\geq 0$ for all $k$ or
$(SXW+b)_{vk}<0$ for all $k$. Denote
$\tilde{A}(u)=\\{v\in\tilde{N}(u):\quad(SXW+b)_{vk}\geq 0\quad\text{for all
}k\\}$. In this case, Equation 10 becomes:
$H_{u\cdot}=\sum_{v\in{\tilde{A}(u)}}\big{(}S_{uv}(SX\tilde{W})_{v\cdot}+S_{uv}\tilde{b}_{v\cdot}\big{)}$,
with $\tilde{b}=bW^{(2)}$ and $\tilde{W}=WW^{(2)}$. Therefore, for symmetric
convolutions, the term $(\sum_{v\in{\tilde{A}(u)}}S_{uv})b$ encodes
information about the neighborhood (it is proportional to the number of terms
in the sum $|{\tilde{A}(u)}|$.) Conversely, for row-symmetric convolutions,
this term is identically equal to $b$, resulting in an embedding that is less
sensitive to topology.

###  C.2 Proof of lemma 4.1: Symmetric Convolutions

In this subsection, we prove the results stated in lemma 4.1 for symmetric
convolutions. We remind the reader of the setting of lemma 4.1: we consider
two structurally equivalent neighbourhoods (meaning that there exists a
mapping $\phi$ that transforms each node in the neighborhood of $v$ into its
corresponding one in the neighborhood of $u$ — see Figure 6), but the feature
vectors are different. Mathematically, we model this situation as:

$\forall j\in N(v),\quad X_{j}=X_{u\phi(j)}+\epsilon$

where $\epsilon$ is a vector with independent centered Gaussian entries with
parameter $\sigma$. The purpose of this subsection is to analyze the effect of
the convolution on the relative distance between embeddings.

Lemma 4.1 is re-written here, to make this appendix self-contained:

Lemma 4.1. For symmetric convolutions, with probability at least $1-\delta$,
with $M$ as in 3.1, we have:

$\displaystyle||H_{u}-H_{u^{\prime}}||^{2}\leq\mu+2\sqrt{2}\sigma||W||_{2}(d_{u}+\beta)^{1-2\alpha}\sqrt{1+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-1}+\alpha(2\alpha+1)M}\log(1/\delta)$

where
$\mu=\sigma^{2}||W||^{2}\Big{(}(d_{u}+\beta)^{2-4\alpha}+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-4\alpha}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}({d_{u}+\beta})^{-1-4\alpha}\Big{)}.$
Conversely, for row-symmetric embeddings:

$\displaystyle||H_{u}-H_{u^{\prime}}||^{2}$
$\displaystyle\leq\mu+2\sqrt{2}\sigma||W||_{2}\sqrt{\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{1}{(d_{v}+\beta)^{2\alpha}}}\log(1/\delta),\quad\mu=\frac{\sigma^{2}||W||^{2}}{\sum_{v\in\tilde{\mathcal{N}}(u)}(d_{v}+\beta)^{-2\alpha}}\frac{1}{1+\beta}$

As previously stated, the purpose of this subsection is to analyze the effect
of the convolution on the relative distance between embeddings. Consequently,
we consider a simplified one-layer setting, with no non-linearities. We argue
that this is indeed sufficient to characterize the effect of the convolution
on the organization of the data, and we expect results for deeper networks to
follow by induction, and to hold by 1-Lipschitzness of the ReLU activation for
ReLU non-linear GNNs.

Proof of Lemma 4.1(symmetric convolutions). Therefore, in the simplified
setting, the distance between the outputs of a GCN layer for nodes $u$ and $v$
can be written as:

$\begin{split}H^{(k)}_{u}-H^{(k)}_{u^{\prime}}=(SX_{u}-SX_{u^{\prime}})W&=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}(X_{v}-X_{\phi(v)})W\\\
&=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}\epsilon_{v}W\\\
\end{split}$ (11)

Since $\epsilon_{v}\sim\mathcal{N}(0,\sigma^{2}),$ each entry of the vector
$H^{(k)}_{u}-H^{(k)}_{u^{\prime}}$ is Gaussian:

$\displaystyle
H^{(k)}_{uj}-H^{(k)}_{u^{\prime}j}=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}\sum_{k=1}^{d}\epsilon_{vk}W_{kj}\sim\mathcal{N}(0,\frac{\sigma^{2}||W_{\cdot
j}||^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}})$

The mean of $||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}$ is simply given by:

$\displaystyle\mu=\mathbb{E}[||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}]$
$\displaystyle=\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}}$
$\displaystyle\leq\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{4\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}A_{uv}^{2}(1-2\alpha\frac{\Delta_{v}}{d_{u}+\beta}+\alpha(2\alpha+1)M\frac{\Delta_{v}^{2}}{(d_{u}+\beta)^{2}})$

for some constant $M$, using the same Taylor expansion reasoning as for Lemma
3.1. Therefore, denoting as
$\tilde{d}_{u}=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}A_{uv}^{2}$, we have:

$\displaystyle\mu$
$\displaystyle\leq\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{4\alpha}}\Big{(}(\tilde{d}_{u}+\beta^{2})-2\alpha\overline{\Delta}_{u}\frac{\tilde{d}_{u}+\beta^{2}}{d_{u}+\beta}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}\frac{\tilde{d}_{u}+\beta^{2}}{(d_{u}+\beta)^{2}})$
$\displaystyle\overset{(i)}{\leq}\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{4\alpha}}\Big{(}(d_{u}+\beta)^{2}+2\alpha|\overline{\Delta}_{u}|\frac{({d}_{u}+\beta)^{2}}{d_{u}+\beta}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u})$
$\displaystyle=\sigma^{2}||W||^{2}\Big{(}(d_{u}+\beta)^{2-4\alpha}+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{1-4\alpha}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}({d_{u}+\beta})^{-4\alpha}\Big{)}$

where line (i) follows from the fact that, assuming the edge weights are less
than 1, $A_{uv}^{2}\leq A_{uv}$, implying that $\tilde{d}_{u}\leq d_{u}$. Note
that in the case where $\beta\leq 1$ (so that $\beta^{2}\leq 1)$, this bound
can be made even tighter by considering:

$\mu\leq\sigma^{2}||W||^{2}\Big{(}(d_{u}+\beta)^{2-4\alpha}+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-4\alpha}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}({d_{u}+\beta})^{-1-4\alpha}\Big{)}.$

Let us now turn to the analysis of the concentration of this norm. By
Gaussianity of each of its coordinate, the squared norm
$||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}=\sum_{j=1}^{p}\big{(}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}\epsilon_{v\cdot}W_{\cdot
j}\big{)}^{2}$ is sub-exponential.

To see this, note that since each of the $p$ coordinate of the vector
$H^{(k)}_{u}-H^{(k)}_{u^{\prime}}$ is Gaussian with variance
$\tilde{\sigma}_{j}^{2}=\frac{\sigma^{2}||W_{\cdot
j}||^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}})$,
its square is sub-Exponential with parameter
$(2\tilde{\sigma}_{j}^{2},4\tilde{\sigma}_{j}^{2})$ ([48]), so the squared
norm (ie the sum of the squared entries) is sub-Exponential with parameter:

$(2\sum_{j=1}^{p}\tilde{\sigma}_{j}^{2},4\max_{j}\tilde{\sigma}_{j}^{2})=\Big{(}2\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}},4\frac{\sigma^{2}||W||_{2,\infty}^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}}\Big{)}.$

By property of the sub-exponential tail, we know that:

$\displaystyle\mathbb{P}[||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}-\mu\geq
t]\leq\min(e^{-t^{2}/(4\sum_{j=1}^{p}\tilde{\sigma}_{j}^{2}},e^{-t/(2\sqrt{2}\sqrt{\sum_{j=1}^{p}\tilde{\sigma}_{j}^{2}}})$
(12)

Therefore, with probability at least $1-\delta$, for any $\delta\in(0,1)$, we
must have:

$\displaystyle||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}\leq\mu+2\sqrt{2}\sqrt{\frac{\sigma^{2}||W||^{2}}{(d_{u}+\beta)^{2\alpha}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}\frac{A_{uv}^{2}}{(d_{v}+\beta)^{2\alpha}}}\log(1/\delta)$
(13)
$\displaystyle\leq\mu+2\sqrt{2}\sigma||W||_{2}(d_{u}+\beta)^{1-2\alpha}\sqrt{1+2\alpha|\overline{\Delta}_{u}|({d_{u}+\beta})^{-1}+\alpha(2\alpha+1)M\overline{\Delta^{2}}_{u}({d_{u}+\beta})^{-2}}\log(1/\delta)$
(14)

The concentration is thus a function of the node degree: the leading term is
in $(d_{u}+\beta)^{1-2\alpha}$, and we observe again the existence of a
critical threshold at $\alpha=0.5$. ∎

###  C.3 Proof of lemma 4.1: the case of row-normalized Convolutions

We now turn to the proof of Lemma 4.1 for row-normalized convolutions.

Proof of Lemma 4.1(row-normalized convolutions). In the case of row-normalized
convolutions, we have instead:

$\begin{split}(SX_{u}-SX_{u^{\prime}})W&=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}s_{uv}\epsilon_{v}W\\\
\end{split}$ (15)

where, as highlighted in section 3, $s_{uv}$ is proportional to
$\frac{1}{(d_{v}+\beta)^{\alpha}}$, but does not depend on $d_{u}$. In this
case, following a similar reasoning to the previous subsection:

$\displaystyle\mu=\mathbb{E}[||H^{(k)}_{u}-H^{(k)}_{u^{\prime}}||^{2}]$
$\displaystyle=\frac{\sigma^{2}||W||^{2}}{Z^{2}}\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}s_{uv}^{2}\quad\text{with
}Z=\sum_{v\in\mathcal{N}(u)\cup\\{u\\}}s_{uv}$
$\displaystyle\leq\frac{\sigma^{2}||W||^{2}}{Z^{2}}\max_{v\in\mathcal{N}(u)\cup\\{u\\}}\\{s_{uv}\\}\quad\text{
by Holder's inequality}$
$\displaystyle\leq\frac{\sigma^{2}||W||^{2}}{Z^{2}}\frac{1}{(d_{\min}+\beta)^{\alpha}}$
$\displaystyle\leq\frac{\sigma^{2}||W||^{2}}{Z^{2}}\frac{1}{(1+\beta)^{\alpha}}$

∎

###  C.4 Toy example 2

Conversely, $u$ and $u^{\prime}$ have radically different neighborhoods from a
topological perspective, but have similar features:

$\forall j\in\mathcal{N}(u)\cup\mathcal{N}(u^{\prime}),\quad
X_{j}=\bar{X}_{u}$

In the symmetric case:

$\displaystyle||(SX)_{u\cdot}-(SX)_{u^{\prime}\cdot}||^{2}$
$\displaystyle=||\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}\bar{X}-\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}}{(d_{v^{\prime}}+\beta)^{\alpha}(d_{u^{\prime}}+\beta)^{\alpha}}\bar{X}||^{2}$
$\displaystyle=\Big{(}\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}}{(d_{u}+\beta)^{\alpha}(d_{v}+\beta)^{\alpha}}-\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}}{(d_{v^{\prime}}+\beta)^{\alpha}(d_{u^{\prime}}+\beta)^{\alpha}}\Big{)}^{2}||\bar{X}||^{2}$
$\displaystyle=\Big{(}\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}}{(d_{u}+\beta)^{2\alpha}(1+\frac{\Delta_{v}}{d_{u}+\beta})^{\alpha}}-\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}}{(d_{u^{\prime}}+\beta)^{2\alpha}(1+\frac{\Delta_{v}}{d_{u^{\prime}}+\beta})^{\alpha}}\Big{)}^{2}||\bar{X}||^{2}$
$\displaystyle=\Big{(}(d_{u}+\beta)^{1-2\alpha}-\alpha\overline{\Delta}_{u}+\frac{\alpha(\alpha+1)}{2(d_{u}+\beta)^{2+2\alpha}}\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}(d_{v}-d_{u})^{2}}{((1-t_{v})+t_{v}\frac{\Delta_{v}}{d_{u}+\beta}+\beta)^{2+2\alpha}}$
$\displaystyle-(d_{u^{\prime}}+\beta)^{1-2\alpha}+\alpha\overline{\Delta}_{u^{\prime}}-\frac{\alpha(\alpha+1)}{2(d_{u^{\prime}}+\beta)^{2+2\alpha}}\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}(d_{v}^{\prime}-d_{u}^{\prime})^{2}}{((1-t_{v^{\prime}})+t_{v^{\prime}}\frac{\Delta_{v^{\prime}}}{d_{u^{\prime}}+\beta}+\beta)^{2+2\alpha}}\Big{)}^{2}||\bar{X}||^{2}$

where $t_{v},t_{v^{\prime}}\in[0,1]$. In this case, note that:

  * •

When $\alpha=0$, this difference writes as:
$||(SX)_{u\cdot}-(SX)_{u^{\prime}\cdot}||^{2}=d_{u}-d_{u^{\prime}}$, and is
thus extremely sensitive to the degree of the nodes,

  * •

When $\alpha=1$, the difference can be written as:

$\displaystyle||(SX)_{u\cdot}-(SX)_{u^{\prime}\cdot}||^{2}$
$\displaystyle=\Big{(}\frac{1}{d_{u}+\beta}-\overline{\Delta}_{u}+\frac{1}{(d_{u}+\beta)^{4}}\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}(d_{v}-d_{u})^{2}}{((1-t_{v})+t_{v}\frac{\Delta_{v}}{d_{u}+\beta}+\beta)^{4}}$
$\displaystyle-\frac{1}{d_{u^{\prime}}+\beta}+\overline{\Delta}_{u^{\prime}}-\frac{1}{(d_{u^{\prime}}+\beta)^{4}}\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}(d_{v}^{\prime}-d_{u}^{\prime})^{2}}{((1-t_{v^{\prime}})+t_{v^{\prime}}\frac{\Delta_{v^{\prime}}}{d_{u^{\prime}}+\beta}+\beta)^{4}}\Big{)}^{2}||\bar{X}||^{2}$

In this case, the leading terms are functions of the inverse of the node
degrees $\frac{1}{d_{u}+\beta}-\frac{1}{d_{u^{\prime}}+\beta}$ and the
difference in local homogeneity of topology
$\overline{\Delta}_{u}-\overline{\Delta}_{u^{\prime}}$. Consequently, the
distance is still sensitive to topological properties of the neighborhood.

  * •

When $\alpha=0.5$: in this case, the distance writes as:

$\displaystyle||(SX)_{u\cdot}-(SX)_{u^{\prime}\cdot}||^{2}$
$\displaystyle=\Big{(}\frac{1}{2}\overline{\Delta}_{u^{\prime}}-\frac{1}{2}\overline{\Delta}_{u}$
$\displaystyle+\frac{3}{8(d_{u}+\beta)^{3}}\sum_{v\in\tilde{\mathcal{N}}(u)}\frac{A_{uv}(d_{v}-d_{u})^{2}}{((1-t_{v})+t_{v}\frac{\Delta_{v}}{d_{u}+\beta}+\beta)^{3}}$
$\displaystyle-\frac{3}{8(d_{u^{\prime}}+\beta)^{3}}\sum_{v^{\prime}\in\tilde{\mathcal{N}}(u^{\prime})}\frac{A_{u^{\prime}v^{\prime}}(d_{v^{\prime}}-d_{u^{\prime}})^{2}}{((1-t_{v^{\prime}})+t_{v^{\prime}}\frac{\Delta_{v^{\prime}}}{d_{u^{\prime}}+\beta}+\beta)^{3}}\Big{)}^{2}||\bar{X}||^{2}$

Consequently, this distance is less directly related to the degree of the
node, and relies more on the topological traits of the neighborhood.

In the regularised case:

$\begin{split}&||(SXW_{1}+b_{1})_{u}-(SXW_{1}+b_{1})_{u^{\prime}}||^{2}=0\end{split}$
(16)

In this case, the distance is entirely driven by the features.

##  Appendix D Further results and experiments

We analyzed the impact of the choice of operator across $\alpha$ and $\beta$
using standard benchmark datasets. In particular, the node classification task
has been performed. The performance turns out to be dependent on the choice of
an operator as well as the inherent characteristics of the datasets. We use
visualizations to further investigate the properties of each embedding space
in relation to the choice of operator.

###  D.1 Dataset statistics

Name | Node | Edge |  | Features
---
Class |  | Avg.Degree
---
| Mean
---
Centrality
$h_{\text{edges}}$ | $h_{\text{nodes}}$
Cora | 2,708 | 10,556 | 1,433 | 7 | 3.90 | $1.65E-03$ | 0.81 | 0.83
Pubmed | 19,717 | 88,648 | 500 | 3 | 4.50 | $2.71E-04$ | 0.80 | 0.79
Citeseer | 3,327 | 9,104 | 3,703 | 6 | 2.74 | $1.02E-03$ | 0.74 | 0.71
Coauthor CS | 18,333 | 163,788 | 6,805 | 15 | 8.93 | $2.42E-04$ | 0.81 | 0.83
Amazon Photos | 7,650 | 238,162 | 745 | 8 | 31.13 | $3.82E-04$ | 0.83 | 0.84
Actor | 7,600 | 30,019 | 932 | 5 | 3.95 | $3.18E-04$ | 0.22 | 0.21
Cornell | 183 | 280 | 1,703 | 5 | 1.53 | $1.07E-04$ | 0.31 | 0.21
Wisconsin | 251 | 515 | 1,703 | 5 | 2.05 | $2.42E-04$ | 0.20 | 0.13

Table 3: Statistics for datasets used for experiments. Node and edge homophily
indices are calculated by the formula suggested in [39], [59] respectively.

Datasets. We used eight datasets used for experiments, namely, Cora, Pubmed,
Citeseer, and Amazon Photos, Coauthor CS, as well as three heterophilic graph
datasets, namely, Actor, Cornell, Wisconsin. We use the processed version
provided by PyTorch Geometric[16]. Detailed statistics for the datasets used
in the experiments are shown in Table 3.

Citation networks. Cora, Citeseer, and Pubmed are standard citation network
benchmark datasets.[55] In these networks, nodes represent scientific
publications, and edges denote citation links between publications. Node
features are the bag-of-words representation of papers, and node label is the
academic topic of a paper.

Coauthor In Coauthor CS[41] network, each node represents the author of the
scientific publication, and edge shows whether any of the authors coauthored
the paper. Node features are bag-of-word representations of these documents,
and node labels denote the field of study.

Amazon In Amazon Photo[41] network, nodes represent goods and edges show
whether two goods are frequently bought together. Node features are bag-of-
word representation of product reviews.

WebKB. WebKB is a webpage dataset collected from computer science departments
of various universities by Carnegie Mellon University. We use Cornell, and
Wisconsin among them. Nodes represent web pages, and edges are hyperlinks
between them. Node features are the bag-of-words representation of web pages.
The web pages are manually classified into the five categories: student,
project, course, staff, and faculty.

Cooccurrence network Actor dataset is the actor-only induced subgraph of the
film-director-actor-writer network[39]. Each node corresponds to an actor, and
the edge between two nodes denotes co-occurrence on the same Wikipedia page.
Node features correspond to corresponding Wikipedia keywords.

###  D.2 Experiment setup

Models. We use a two-layer GCN[28] model with varying families of spatial
convolution operator across the choice of $\alpha$ while keeping
$\beta\in\\{0,1\\}$. For each experiment, we randomly split the data into
training and test sets (using the default number of train and test points in
Pytorch geometric). The number of training nodes used are specified in Table
4. Further training details including data split, number of experiments and
learning rate are also summarized in Table 4.

Name |  | num of
---
training nodes
lr | epoch |  | num of
---
experiments
| training time
---
per epoch(sec)
| dim of
---
hidden layer
| num of
---
GCN layers
Cora | 140 | 0.02 | 200 | 50 | 9.58 | 32 | 2
Pubmed | 60 | 0.001 | 500 | 30 | 100.49 | 32 | 2
Citeseer | 1694 | 0.05 | 500 | 30 | 31.73 | 32 | 2
Coauthor CS | 9194 | 0.05 | 200 | 30 | 150.68 | 32 | 2
Amazon Photos | 3844 | 0.05 | 200 | 30 | 88.04 | 32 | 2
Actor | 3804 | 0.02 | 200 | 30 | 13.02 | 32 | 2
Cornell | 87 | 0.01 | 500 | 30 | 2.95 | 32 | 2
Wisconsin | 126 | 0.001 | 500 | 30 | 3.52 | 32 | 2

Table 4: Hyperparameters and training details for all datasets.

Hardware and Software Specifications.. Our models are implemented with Python
3.8.8, PyTorch Geometric 2.0.5 [16], and PyTorch 1.10.0 [38]. We conduct
experiments on a computer equipped with 2.3 GHz Quad-Core Intel Core i7
processor and Intel Iris Plus Graphics 1536 MB.

###  D.3 Experiment results

In this section, we highlight the results of our experiments on the various
datasets aforementioned. Additional plots are provided in the folder of
supplementary materials associated with this paper.

####  D.3.1 Node Classification

First, we want to investigate the impact of the choice of operators on the
node classification task. We observe that the performance of the node
classification task varies by choice of $\alpha$. We fix $\beta=1$ — in other
words, we add self-loops, consistently with the standard GCN architecture. In
general, we observe that performance are highly dependent on the choice of
$\alpha$ especially for the symmetrized operator, but the performance of node
classification task of row-normalized operator is relatively robust to the
choice of $\alpha$

(a) Citeseer, symmetrized, PCA, colored by node label

(b) Citeseer, symmetrized, UMAP, colored by node label

(c) Citeseer, row-normalized, PCA, colored by node label

(d) Citeseer, row-normalized, UMAP, colored by node label

Figure 7: Citeseer. The plots are colored by node labels(product categories).
Embedding spaces generated by symmetric operator, (a), (b), as $\alpha$
increases the level of distinction between the cluster of different node
labels decreases. Embedding space generated by row-normalized operator seems
to be robust to the choice of $\alpha$– it gives relatively constant level of
clustering regardless of $\alpha$.

(a) Wisconsin, symmetrized, PCA, colored by node label

(b) Wisconsin, symmetrized, UMAP, colored by node label

(c) Wisconsin, row-normalized, PCA, colored by node label

(d) Wisconsin, row-normalized, UMAP, colored by node label

Figure 8: Wisconsin.The plots are colored by node label(categories for the
webpage). Unlike the graph in Figure 8, it is hard to detect the change in the
level of clustering or separation of each node class as $\alpha$ varies. PCA
transformed embedding plot for row-normalized operator (c) even shows that the
clustering of node label improves as $\alpha$ gets closer to 1.

Analysis. For standard homophilic datasets such as Citeseer(Figure 7),
clustering of each node class has become less identifiable for a symmetric
operator when $\alpha$ increases. On the other hand, the node class has been
well separated across the alpha for the row-normalized operator– the row-
normalized operator is robust to the choice of $\alpha$ when it comes to node
classification performance. Conversely, for the datasets with low homophily
shown in Table 4, such as Wisconsin(Figure 8), the separation of the node
label does not change much depending on the choice of $\alpha$ or the choice
of operator. The visual inspections on the embedding space transformed by PCA
and UMAP are in line with the numerical result of test accuracy, Figure 9.

(a) Citeseer

(b) Wisconsin

Figure 9: Test accuracy for node classification task on two datasets: Citeseer
and Wisconsin.

####  D.3.2 Degree

In this subsection, we propose to investigate how basic topological
characteristics (more specifically, here, the node degree) drive the
organization of the embedding space. Consequently, to complement the analysis
performed in the main text, we conduct visual inspection on the embedding
plots of our benchmark datasets colored by node degree.

Figures 10 and 11 show the embedding spaces transformed by PCA, and the size
and color of points denote the node degree. It is noted that the high degree
nodes are marginalized when $\alpha$ close to 0, and lower degree nodes tend
to be located at the origin. As $\alpha$ gets closer to 1, this pattern seems
to be reverted— the higher degree nodes are located at the origin and the
lower degree nodes are pushed out to be at the periphery.

(a) Coauthor CS, symmetrized, colored by degree

(b) Coauthor CS, row-normalized, colored by degree

Figure 10: Coauthor CS. The point size and color denote the node degree. For
both symmetrized and row-normalized operator, high degree nodes are located
farther from the origin when $alpha\approx 0$. As $\alpha$ increases, high
degree nodes are concentrated on the origin, and low degree nodes are spread
out instead.

(a) Amazon Photo, symmetrized, colored by degree

(b) Amazon Photo, row-normalized, colored by degree

Figure 11: Amazon Photo. The point size and color denote the node degree.
Amazon Photo networks have a few nodes with extremely high degree$(>500)$.
Even for such nodes, as $\alpha$ increases the effect of high degree vanishes
and all points are clustered near the origin.

####  D.3.3 Distance to the Original Space

In this subsection, we investigate the link between the relative distances
between embedding points, and that of the original data.

Distance Calculation. The original dataset provides two separate views of the
data, for which we can define two separate notions of distance: (1) a distance
based on the graph structure (e.g the adjacency matrix), and (2) a distance
based on the node features. For the distance in the graph, we choose to
consider a distance in the graph space based on the diffusion distance [9]
using Gaussian kernel with $\epsilon=0.5$.

$\displaystyle K(u,v)=exp\big{(}-\frac{d_{\text{shortest path}}(\text{node
u},\text{node v})_{\alpha}^{2}}{\epsilon}\big{)}$

The shortest path distance is computed by build-in function in [23]. Distance
in the feature space is measured by the pairwise euclidean distance of node
features space. Finally, the distance in the embedding space is all based on
the pairwise $\ell_{2}$ Euclidean distance.

Correlation Analysis. It is a natural question to ask how embedding space
closely resembles the original graph space or the feature space. The notion of
closeness can be defined in several ways, but in this experiment, we first see
the correlation between the distance in the original space and in the
embedding space. We will use Spearman’s rank correlation, which measures the
monotonic relationship between the two.

Higher correlation could be interpreted as the amount of information that is
retained in the embedding space regarding graph structure or node features.
From Figure 12, both dataset show decreasing correlation as alpha increases;
however, the correlation itself is actually close to 0($<0.05$). It is be
reasonable to suspect no information regarding graph structure has been
preserved in the embedding space, so we will come back to this question in
D.3.4

Figure 13 shows the trend in consonance with the test accuracy for the node
classification task, Figure 9. That is, for row-normalized operator the amount
of node feature information is relatively constant for both standard
homophilic dataset and heterophilic dataset such as Wisconsin. On the other
hand, when it comes to the symmetrized operator, for Cora dataset, the
correlation between the embedding spaces and the original feature space drops
from 0.15(when $\alpha\approx 0.6$), to 0.005(when $\alpha\approx 1$). For
Wisconsin dataset, the correlation still increases for the symmetrized
operator, but the absolute value of correlation for the symmetrized operator
is lower than that of the row-normalized operator.

(a) Cora

(b) Wisconsin

Figure 12: Spearman’s correlation between the pairwise distances in the graph
space and pairwise distance in the embedding space.

(a) Cora

(b) Wisconsin

Figure 13: Spearman’s correlation between the pairwise distances in the
feature space and pairwise distance in the embedding space

Gromov-Wasserstein Distance. To this extent, we use Gromov-Wasserstein
distance[34] which allows to measure the distance between two probability
spaces of different dimensions, by comparing the within distance of
probability spaces. By estimating Gromov-Wasserstein distance we can evaluate
how close our embedding space is to the original space upon the choice of
operators.

Based on the within distance calculated as described earlier, Gromov-
wasserstein distance is calculated using python implemented
`ot.gromov.gromov.wasserstein` function in `ot` package.[17]
https://pythonot.github.io. The detailed values from computations are shown in
Figure 14 and Figure 15.

Analysis. For the distance, we need to interpret in the opposite way we
comprehend the correlation from earlier subsection. The lower the distance,
the more the information regarding graph structure of feature has preserved in
the embedding spaces. First, Cora shows the opposite pattern of distance with
graph space and feature space. It can be viewed as for Cora, feature
information has maximally preserved when $\alpha\approx 0.5$ for both
symmetrized and row-normalized operator, while the information regarding graph
structure has minimally estimated. When $\alpha\approx 0$ or $\alpha\approx
1$, the distance to the graph space is close to 0, while the distance to the
feature space is close to the highest value.

On the contrary, Wisconsin seems to have similar pattern of distance for both
graph and feature spaces. Embedding space recovered by the symmetrized
operator, the information for both graph structure and node features are
minimally retained when $\alpha\approx 0.5$. With the row-normalized operator,
the distances to the original spaces increase as $alpha$ increases.

(a) Cora

(b) Wisconsin

Figure 14: Gromov-Wasserstein distance between the graph space and embedding
space. For both datasets, when $\alpha$ is close to 0 or 1, the distance
between two spaces is small for symmetrized operator.

(a) Cora

(b) Wisconsin

Figure 15: Gromov-Wasserstein distance between the feature space and embedding
space. Note that the distance variation across $\alpha$ is very similar to the
accuracy of node classification task along $\alpha$ on Figure 9

####  D.3.4 Curvature

In this section, the embedding space is compared to the original space with
regard to the geometry of the original space. We first narrow down the notion
of geometry to a graph curvature. Graph curvature could explain the structural
properties of the data that cannot be fully captured by the node degree. One
might reasonably wonder how this structural information or geometry of the
graph could be preserved from original space to the embedding space. We use
augmented Forman curvature for the graph defined in [11].

| Cora | Pubmed | Citeseer |  | Coauthor
---
CS
| Amazon
---
Photo
Actor | Cornell | Wisconsin
Mean | -9.6178 | -18.9898 | -3.2427 | -14.4801 | -99.8552 | -8.2625 | -41.9855 | -46.2206
SD | 16.0352 | 15.9152 | 8.5414 | 11.7537 | 110.3011 | 21.2629 | 43.2669 | 52.3953

Table 5: Mean and Standard deviation of augmented forman curvature[11] for 8
Datasets

To calculate the graph curvature on the embedding space, we have to
reconstruct the graph on the embedding space. First, based on the euclidean
distance of each node in the embedding space, we connect the same number of
edges as the original graph. With this "reconstructed graph" on the embedding
space, we calculate the graph curvature. Finally, we compare how much
curvature has been preserved upon varying operators by Spearman’s rank
correlation.

Figure 16 shows (a) Cora and (b) Amazon Photos, standard datasets with high
homophily as shown in Table 3, Spearman’s correlation between the original
curvature and embedding curvature are relatively constant around 0.3 with row-
normalized operator. On the other hand, symmetrized operator has stronger
positive correlation when $\alpha\approx 1$. For the dataset with low
homophily, denoted as heterophilic graph dataset, such as (c) Cornell or (d)
Wisconsin, not only the absolute value of the Spearman’s correlation is much
lower than that of results from homophilic dataset, but also there is a
decreasing trend across the $\alpha$ for both symmetrized and row-normalized
operator.

Based on these observations, the geometry in terms of curvature seems to be
better preserved when $\alpha\approx 1$ for the dataset with high homophily.
When the graph is of low homophily, symmetrized operator works slightly better
preserving the curvature, but the absolute value of the correlation itself is
fairly low compared with the result of high homophily dataset, such as Figure
16 (a) or (b).

(a) Cora

(b) Citeseer

(c) Cornell

(d) Wisconsin

Figure 16: Spearman’s correlation between the original and embedding
curvature.

(a) Cora, symmetrized, colored by embedding curvature

(b) Cora, row-normalized, colored by embedding curvature

Figure 17: Cora. The points are colored by embedding curvature and the size is
proportional to the original curvature.

(a) Wisconsin, symmetrized, colored by embedding curvature

(b) Wisconsin, row-normalized, colored by embedding curvature

Figure 18: Wisconsin. The points are colored by embedding curvature and the
size is proportional to the original curvature.

###  D.4 Additional Experimental results

Figure 19: Row-Normalized Embeddings, plotted using the first two principal
components (left), and the raw latent embeddings (or ‘latent components’,
shown in the right three plots on each row). Note the inversion: the high
degree nodes migrate from the periphery of the latent space ($\alpha=0.2$) to
the origin $(\alpha=0.7)$.