pagerefparensbackrefparens

# The Self-Loop Paradox: Investigating the Impact of Self-Loops on Graph
Neural Networks

Moritz Lampert, Ingo Scholtes
Chair of Machine Learning for Complex Networks
Center for Artificial Intelligence and Data Science (CAIDAS)
Julius-Maximilians-Universität Würzburg, DE
<EMAIL_ADDRESS>
###### Abstract

Many Graph Neural Networks (GNNs) add self-loops to a graph to include feature
information about a node itself at each layer. However, if the GNN consists of
more than one layer, this information can return to its origin via cycles in
the graph topology. Intuition suggests that this “backflow” of information
should be larger in graphs with self-loops compared to graphs without. In this
work, we counter this intuition and show that for certain GNN architectures,
the information a node gains from itself can be smaller in graphs with self-
loops compared to the same graphs without. We adopt an analytical approach for
the study of statistical graph ensembles with a given degree sequence and show
that this phenomenon, which we call the _self-loop paradox_ , can depend both
on the number of GNN layers $k$ and whether $k$ is even or odd. We
experimentally validate our theoretical findings in a synthetic node
classification task and investigate its practical relevance in 23 real-world
graphs.

##  1 Introduction

Multi-layer Perceptrons (MLPs) use feature information of a sample to make
predictions. GNNs use the sample represented as a node in a graph and feature
information of the neighbouring nodes for predictions. To include the
information about a node itself, GNN architectures like Graph Convolutional
Network (GCN) [8] add self-loops. For single-layer GNNs, it is necessary to
include the node’s feature but for more than one layer, information can also
flow back via cycles in the topology of the graph. Intuitively, adding self-
loops still increases the information a node learns about itself. Thus, the
influence of self-loops on GNNs remains mainly unexplored up to now.
Recent works investigate the influence of a graph’s topology on GNNs in
combination with over-squashing, i.e. GNNs perform badly on tasks that rely on
interactions between distant nodes. The exponentially growing number of
neighbours with increasing distance is one reason for over-squashing [1]. The
GNNs perform badly because useful information of distant nodes is squashed by
bottlenecks in the graph topology [5, 14] and the redundancy introduced by
close neighbours [2]. The works on over-squashing all have in common that they
connect the graph topology via walks between nodes to the influence nodes have
on each other’s predictions in a GNN. Earlier work [18] uses a similar
approach in a different context and also mentions how self-loops can influence
GNN predictions. [14] build on that idea and investigate it further.
We build upon the concept that the influence of a node feature on the
prediction of another node is proportional to the relative number of walks
between them out of all walks. In particular, we investigate the proportion of
cycles of length $k$ from a node $v$ out of all walks of length $k$ ending in
$v$. Using theory from network science based on random graphs with a given
degree sequence [12, 10], we prove that including self-loops in those random
graphs decreases the proportion of cycles with length $2$. We further show
that this can reduce a node’s influence on its own prediction in two-layered
GNNs. The theoretical findings are validated empirically using synthetic data
generated using a Stochastic Block Model (SBM) [7] and put into context on
real-world datasets in the appendix.

##  2 Background

### Random Graphs

For the statistical analysis, we adopt the probabilistic Molloy-Reed
configuration model [11] that generates random undirected graphs
$\mathcal{G}=(\mathbf{V},\mathbf{E})$ based on a given degree sequence
$S=(d_{v})_{v\in\mathbf{V}}$. Under this model, if the degree sequence $S$ is
graphic, each graph $\mathcal{G}$ with the same degree sequence $S$ is
equiprobable. Computationally, this can be achieved by adding $d_{v}$ edge
stubs for each node $v$ with degree $d_{v}$ and then connecting pairs of
randomly chosen stubs until no stubs are left.
While it is easy to algorithmically generate random graphs based on the
Molloy-Reed model, its true importance in network science is due to our
ability to _analytically_ study expected properties of these random graphs
based on generating functions [16, 12]. For this type of model, we can express
the expected degree of a randomly chosen node as

$\displaystyle\langle
d\rangle=\frac{1}{|\mathbf{V}|}\sum_{d_{v}\in\mathbf{S}}d_{v}.$ (1)

The expected degree of a random neighbour of a randomly chosen node is given
by the expected degree and its second raw moment: [12]

$\displaystyle\langle d_{N}\rangle=\frac{\langle d^{2}\rangle}{\langle
d\rangle}$ (2)

The number of walks of length $k$ from node $u$ to $v$ can be computed using
the adjacency matrix $A$ of graph $\mathcal{G}$ as $A^{k}_{uv}$. The expected
total number of $k$-length walks from or to $v$ is given by [12]

$\displaystyle\mathbb{E}\left(\sum_{u\in\mathbf{V}}A^{k}_{uv}\right)=\mathbb{E}\left(\sum_{u\in\mathbf{V}}A^{k}_{vu}\right)=\langle
d\rangle\cdot\langle d_{N}\rangle^{k-1}=\langle
d\rangle\cdot\left(\frac{\langle d^{2}\rangle}{\langle
d\rangle}\right)^{k-1}.$ (3)

### Graph Neural Networks

Let $\mathcal{G}=(\mathbf{V},\mathbf{E})$ be a graph without self-loops, with
$n$ nodes, $m$ edges and adjacency matrix $A$. Then given the input features
of the previous layer $\mathbf{h}_{u}^{(k-1)}$, a GCN-layer [8] is defined as

$\displaystyle\mathbf{h}_{v}^{(k)}=\sigma^{(k)}\left(\left(\sum_{u\in
N(v)\cup\\{v\\}}\frac{1}{\sqrt{d(v)d(u)}}\cdot\mathbf{h}_{u}^{(k-1)}\right)\cdot
W^{(k)}+b^{(k)}\right),$ (4)

where $N(v)$ yields the set of neighbours of $v$ and $d(v)$ is the degree of
$v$. The weight matrix $W^{(k)}$ and the bias vector $b^{(k)}$ are trainable
parameters of the $k$-th layer and $\sigma^{(k)}$ is a non-linear activation
function.
Note that the feature $\mathbf{h}_{v}^{(k)}$ of the node $v$ itself is
included in the summation without any special treatment. This is the same as
adding self-loops to the graph topology and using the adjacency matrix
$\tilde{A}=A+I$. Other GNNs like GraphSAGE [6] or the Graph Isomorphism
Network (GIN) [17] treat the node’s feature differently and, thus, the
theoretical findings of this work do not directly apply to these GNNs (see
Appendix D).
To measure the influence of an input feature on the prediction of a node $v$,
we use the Jacobian of the output with respect to a certain input feature and
make use of a finding by [2] in the context of over-squashing for Message
Passing GNNs (MPNNs) [4]:

######  Lemma 1.

If the MPNN passes messages along all $k$-length walks from $u$ to $v$ with
equal probability, then the relative influence of input feature
$\mathbf{h}_{u}^{(0)}$ on node output $\mathbf{h}_{v}^{(k)}$ is on average

$\displaystyle\mathbb{E}\left(\frac{\partial\mathbf{h}_{v}^{(k)}/\partial\mathbf{h}_{u}^{(0)}}{\sum_{u^{\prime}\in
V}\partial\mathbf{h}_{v}^{(k)}/\partial\mathbf{h}_{u^{\prime}}^{(0)}}\right)=\frac{\tilde{A}^{k}_{uv}}{\sum_{u^{\prime}\in
V}\tilde{A}^{k}_{u^{\prime}v}}.$ (5)

This means that it is possible to make statements about the influence of
specific input features on the prediction by analysing the graph topology and
the number of walks of a certain length between two nodes.

##  3 The Self-Loop Paradox

### Theoretical Analysis

We prove that relatively speaking, more walks lead back to the node itself in
graphs without self-loops compared to graphs with self-loops:

######  Lemma 2.

Given a graph $\mathcal{G}$ generated using the configuration model [11] with
adjacency matrix $A$ without self-loops and its counterpart with self-loops
$\tilde{\mathcal{G}}$ with $\tilde{A}=A+I$, the proportion of cycles of length
$2$ from a node $v$ to itself out of all walks of length $2$ ending in $v$ is
larger in $\mathcal{G}$ than in $\tilde{\mathcal{G}}$:

$\displaystyle\frac{\mathbb{E}\left(A^{2}_{vv}\right)}{\mathbb{E}\left(\sum_{u\in
V}A^{2}_{uv}\right)}>\frac{\mathbb{E}\left(\tilde{A}^{2}_{vv}\right)}{\mathbb{E}\left(\sum_{u\in
V}\tilde{A}^{2}_{uv}\right)}.$ (6)

We prove Lemma 2 in Appendix A and experimentally validate the given
proportions on example graphs in Appendix B. This means in combination with
Lemma 1 that including self-loops can decrease the information a node retains
about itself in certain MPNNs with two layers. A detailed discussion on which
GNNs are affected is provided in Appendix D. This is counter-intuitive since
for single-layer GNNs, the node’s feature is only included via self-loops.
Although strictly speaking, this only applies to graphs generated from the
configuration model, we show that this effect can also be observed in other
random graphs below and real-world networks in Appendix C. This is in line
with other properties of the configuration model that are also observed in
real-world networks [13, 377–381].

### Empirical Validation

To empirically validate our theoretical results on GNNs, we use a GCN model to
address a node classification task in synthetic graphs generated based on the
Stochastic Block Model (SBM) [7]. This model generates random undirected
graphs with $c$ classes with a label $y_{v}$ for each node. A stochastic block
matrix $P\in(0,1)^{c\times c}$ defines the probability $p_{ij}$ that an edge
between a pair of nodes with class $i$ and $j$ exists.
We use the SBM to generate graphs with ten classes and 100 nodes per class.
For each class, we sample 16-dimensional node features from a Normal
distribution centred around different corners of a unit hypercube with
standard deviation $\sigma=0.4$. Edge probabilities $p_{ii}$ (between nodes
with the same class) and $p_{ij}$ (between nodes in different classes) are
reported in Fig. 1. The generated graphs used for results in the top left
figure ($p_{ii}>p_{ij}$) exhibit strong cluster patterns, while graphs in the
bottom right figure ($p_{ii}=p_{ij}$) exhibit no cluster patterns.
For graphs with strong cluster patterns, a GCN can achieve high accuracy in a
node classification task based on the graph topology alone, while node
features play a subordinate role. On the contrary for graphs with no strong
cluster patterns, the features of nodes play a more pronounced role. This
should highlight the influence of self-loops on the performance of GCNs with
different numbers of layers. Based on our theoretical findings, we thus expect
that the performance difference of GCNs with and without self-loops shows a
dependency on the number of layers $k$, where we expect models without self-
loops to outperform those with self-loops for $k=2$ layers, while we expect
the opposite behaviour for $k=1$.

The GCNs are trained with $80\%$ of the nodes for 70 epochs using an Adam
optimizer with learning rate $0.01$. Fig. 1 shows the accuracies of the
trained GCNs on the remaining nodes. We test different numbers of layers
$k\in\\{1,\dots,6\\}$ for the GCN architecture and average the results over 50
runs. The code of our experiments is available on
GitHub111https://github.com/M-Lampert/self-loop-paradox.

Figure 1: Test set accuracies of GCNs with and without self-loops averaged
over 50 runs for different numbers of layers. Coloured boxes mark the range
between the first and third quartiles. Whiskers stretch to the furthest
outliers within three halves of that range while other outliers outside of the
whiskers are marked with a rhombus. Grey lines show average accuracies of MLPs
with the corresponding number of layers.

The results show that the difference between the accuracies of GCNs with and
without self-loops varies with the number of layers $k$. As expected, with
increasing “noise” in the topology, i.e. less pronounced cluster patterns, the
general performance of a GCN decreases, eventually achieving a performance
that is lower than that of an MLP that exclusively uses node features (grey
line in Fig. 1). Moreover, the results suggest that –for graphs with a high
level of topological noise– the performance of a GCN strongly depends on the
question of whether the number of layers is odd or even. In line with our
theoretical analysis, our results suggest that the inclusion of self-loops for
$k=2$ layers squashes the nodes’ own features. For graphs with the highest
level of “noise” self-loops actually harm the performance of a two-layered GCN
architecture as opposed to a single-layer architecture.
In Appendix C, we further test our theoretical findings using 23 empirical
benchmark graphs from PyTorch Geometric [3]. The results in Tab. 3 show that
the self-loop paradox indeed holds for 13 of the 23 investigated datasets,
which shows the practical relevance of our results. We also find examples that
are not in line with our theoretical prediction, which is likely due to
additional correlations (e.g. degree-degree correlations) that can invalidate
theoretical predictions derived from degree-based ensembles. We finally
investigate the potential impact of the self-loop paradox on the accuracy of a
Graph Convolutional Network in a node classification task. In a first step, we
tested the influence of self-loops on accuracy, finding that self-loops are
useful for node classification in 15 of the 23 graphs (details in Appendix C).
Focusing on those 15 graphs, in Fig. 2, we investigate the performance of GCNs
with and without self-loops for different numbers of layers. The results show
that the parity of the number of layers influences the performance of GCNs. In
line with our analytical results, we find that the accuracy increase of a two-
layer compared to a one-layer GCN is larger without self-loops than with self-
loops for 11 of the 15 graphs. We suspect that this is due to the self-loop
paradox, which states that the inclusion of self-loops limits the backflow of
information from a node to itself for two layers.

##  4 Conclusion

Many GNNs add self-loops to the input graph to include feature information
about a node itself at each layer. We prove that this inclusion of self-loops
has a counter-intuitive effect, namely that it can decrease the information a
node retains about itself in GNNs with two layers. We analytically prove this
finding for random graphs with arbitrary degree sequences. Experimental
validation using a node classification task in synthetically generated graphs
shows that our theoretical insights hold for synthetic graphs with “noisy”
topologies.
Our work shows how analytical approaches for the study of statistical
ensembles of graphs with given degree sequences –which are frequently used in
network science and complex systems theory– can be applied in the context of
GNNs. In future work, we plan to generalise our analytical proof of the self-
loop paradox for arbitrary numbers of layers $k$. We will further investigate
how this effect is influenced by other properties of the graph topology, e.g.
the average degree, the clustering coefficient, or degree assortativity.
Another promising research direction is to improve our understanding of how
the self-loop paradox may influence open challenges in GNNs like over-
squashing.

## Acknowledgements

Moritz Lampert acknowledges funding from the German Federal Ministry of
Education and Research, Grant No. 100582863 (TissueNet). Ingo Scholtes
acknowledges funding through the Swiss National Science Foundation, Grant No.
176938.

## References

  * [1] Uri Alon and Eran Yahav  “On the Bottleneck of Graph Neural Networks and Its Practical Implications”  In _ICLR_ OpenReview.net, 2021  URL: https://openreview.net/forum?id=i80OPhOCVH2
  * [2] Rongqin Chen, Shenghui Zhang, Leong Hou U and Ye Li  “Redundancy-Free Message Passing for Graph Neural Networks”  In _NeurIPS_ , 2022  URL: https://proceedings.neurips.cc/paper_files/paper/2022/hash/1bd6f17639876b4856026744932ec76f-Abstract-Conference.html
  * [3] Matthias Fey and Jan Eric Lenssen  “Fast Graph Representation Learning with PyTorch Geometric”  In _CoRR_ abs/1903.02428, 2019  URL: https://www.pyg.org/
  * [4] Justin Gilmer et al.  “Neural Message Passing for Quantum Chemistry”  In _ICML_ 70 PMLR, 2017, pp. 1263–1272  URL: http://proceedings.mlr.press/v70/gilmer17a.html
  * [5] Francesco Di Giovanni et al.  “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology”  In _ICML_ 202 PMLR, 2023, pp. 7865–7885  URL: https://proceedings.mlr.press/v202/di-giovanni23a.html
  * [6] William L. Hamilton, Zhitao Ying and Jure Leskovec  “Inductive Representation Learning on Large Graphs”  In _NIPS_ , 2017, pp. 1024–1034  URL: https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html
  * [7] Paul W. Holland, Kathryn Blackmond Laskey and Samuel Leinhardt  “Stochastic Blockmodels: First Steps”  In _Social Networks_ 5.2, 1983, pp. 109–137  DOI: 10.1016/0378-8733(83)90021-7
  * [8] Thomas N. Kipf and Max Welling  “Semi-Supervised Classification with Graph Convolutional Networks”  In _ICLR (Poster)_ OpenReview.net, 2017  URL: https://openreview.net/forum?id=SJU4ayYgl
  * [9] Johannes Klicpera, Aleksandar Bojchevski and Stephan Günnemann  “Predict Then Propagate: Graph Neural Networks Meet Personalized PageRank”  In _ICLR (Poster)_ OpenReview.net, 2019  DOI: 10.48550/arXiv.1810.05997
  * [10] E.. Leicht, Petter Holme and M… Newman  “Vertex Similarity in Networks”  In _Phys. Rev. E_ 73.2 American Physical Society, 2006, pp. 026120  DOI: 10.1103/PhysRevE.73.026120
  * [11] Michael Molloy and Bruce Reed  “A Critical Point for Random Graphs with a given Degree Sequence”  In _Random Structures & Algorithms_ 6.2-3, 1995, pp. 161–180  DOI: 10.1002/rsa.3240060204
  * [12] M… Newman, S.. Strogatz and D.. Watts  “Random Graphs with Arbitrary Degree Distributions and Their Applications”  In _Phys. Rev. E_ 64.2, 2001, pp. 026118  DOI: 10.1103/PhysRevE.64.026118
  * [13] Mark E.. Newman  “Networks”  Oxford University Press, 2018  DOI: 10.1093/oso/9780198805090.001.0001
  * [14] Jake Topping et al.  “Understanding Over-Squashing and Bottlenecks on Graphs via Curvature”  In _ICLR_ OpenReview.net, 2022  URL: https://openreview.net/forum?id=7UmjRGzp-A
  * [15] Petar Velickovic et al.  “Graph Attention Networks”  In _ICLR (Poster)_ OpenReview.net, 2018  URL: https://openreview.net/forum?id=rJXMpikCZ
  * [16] Herbert S Wilf  “generatingfunctionology”  CRC press, 2005
  * [17] Keyulu Xu, Weihua Hu, Jure Leskovec and Stefanie Jegelka  “How Powerful Are Graph Neural Networks?”  In _ICLR_ OpenReview.net, 2019  URL: https://openreview.net/forum?id=ryGs6iA5Km
  * [18] Keyulu Xu et al.  “Representation Learning on Graphs with Jumping Knowledge Networks”  In _ICML_ 80 PMLR, 2018, pp. 5449–5458  URL: https://proceedings.mlr.press/v80/xu18c.html

##  Appendix A Proof of Lemma 2

###### Proof.

The expected total number of incoming walks with a length of $2$ is given by

$\displaystyle\mathbb{E}\left(\sum_{u\in V}A^{2}_{uv}\right)=\langle
d\rangle\cdot\langle d_{N}\rangle^{2-1}=\langle d\rangle\cdot\frac{\langle
d^{2}\rangle}{\langle d\rangle}=\langle d^{2}\rangle.$ (7)

$\tilde{\mathcal{G}}$ only differs from $\mathcal{G}$ in terms of the self-
loops which increases both expected degrees by one leading to

$\displaystyle\mathbb{E}\left(\sum_{u\in
V}\tilde{A}^{2}_{uv}\right)=\left(\langle d\rangle+1\right)\cdot\left(\langle
d_{N}\rangle+1\right)=\langle d^{2}\rangle+\langle d\rangle+\frac{\langle
d^{2}\rangle}{\langle d\rangle}+1.$ (8)

The only closed walks that traverse two edges are those that use the same edge
twice. Introducing self-loops only adds one additional option which is
traversing the self-loop twice. This means the expected values are given by
$\mathbb{E}\left(A^{2}_{vv}\right)=\langle d\rangle$ and
$\mathbb{E}\left(\tilde{A}^{2}_{vv}\right)=\langle d\rangle+1$. Putting
everything together yields:

$\displaystyle\frac{\mathbb{E}\left(A^{2}_{vv}\right)}{\mathbb{E}\left(\sum_{u\in
V}A^{2}_{uv}\right)}$
$\displaystyle>\frac{\mathbb{E}\left(\tilde{A}^{2}_{vv}\right)}{\mathbb{E}\left(\sum_{u\in
V}\tilde{A}^{2}_{uv}\right)}$ (9) $\displaystyle\Leftrightarrow$
$\displaystyle\frac{\langle d\rangle}{\langle d^{2}\rangle}$
$\displaystyle>\frac{\langle d\rangle+1}{\langle d^{2}\rangle+\langle
d\rangle+\frac{\langle d^{2}\rangle}{\langle d\rangle}+1}$ (10)
$\displaystyle\Leftrightarrow$ $\displaystyle\langle d\rangle^{2}+\langle
d\rangle$ $\displaystyle>0$ (11)

This statement is true since $\mathcal{G}$ and $\tilde{\mathcal{G}}$ are
connected. ∎

The estimates used in the proof and the implications of the lemma are
validated empirically in Appendix B.

##  Appendix B Walk Statistics

Tab. 1 shows the average proportion of closed walks of length $k$ from a node
$v$ to itself out of all walks of length $k$ ending in $v$ for
$k\in\\{1,2\\}$. It also includes the estimates that are used in Equation (10)
of the proof. The statistics show that the proportion of closed walks of
length $2$ is smaller in the graph with self-loops than in the graph without
self-loops which validates the theoretical findings. Furthermore, since all of
the estimates are in the range of the standard deviation of the averaged
proportions, it is reasonable to assume that the estimates are correct. Note
that the estimates for $k=1$ are $0$ without self-loops since there is no
other closed walk of length $1$ than a self-loop. With self-loops, the
estimate is $\nicefrac{{1}}{{\langle d\rangle+1}}$ since there is one walk
from or to each neighbour and the self-loop.

Dataset | $\circlearrowleft$ | $k=1$ | $\mathbb{E}_{k=1}$ | $k=2$ | $\mathbb{E}_{k=2}$
---|---|---|---|---|---
$p_{ii}=\nicefrac{{6}}{{100}}$, $p_{ij}=\nicefrac{{3}}{{900}}$ |  |  $0.113\,437\,894\,132\,011\,77$±$0.043\,748\,525\,215\,447\,22$ | $0.101\,874\,490\,785\,908\,86$ |  $0.095\,517\,638\,237\,285\,1$±$0.010\,699\,700\,021\,302\,787$ | $0.092\,624\,502\,672\,375\,15$
|  $0.0$±$0.0$ | $0.0$ |  $0.103\,214\,66$±$0.011\,721\,49$ | $0.102\,079\,57$
$p_{ii}=\nicefrac{{6}}{{100}}$, $p_{ij}=\nicefrac{{6}}{{900}}$ |  |  $0.084\,193\,323\,489\,824\,36$±$0.026\,486\,313\,317\,534\,156$ | $0.077\,748\,403\,344\,459\,04$ |  $0.073\,357\,204\,251\,260\,81$±$0.005\,401\,147\,796\,338\,836$ | $0.072\,220\,059\,566\,354\,01$
|  $0.0$±$0.0$ | $0.0$ |  $0.078\,173\,354$±$0.006\,221\,748\,4$ | $0.077\,841\,796$
$p_{ii}=\nicefrac{{3}}{{100}}$, $p_{ij}=\nicefrac{{6}}{{900}}$ |  |  $0.115\,828\,360\,970\,814\,53$±$0.044\,786\,720\,226\,709\,24$ | $0.103\,220\,481\,869\,359\,21$ |  $0.096\,053\,860\,666\,182\,61$±$0.010\,502\,718\,346\,931\,868$ | $0.092\,893\,954\,532\,292\,49$
|  $0.0$±$0.0$ | $0.0$ |  $0.103\,660\,25$±$0.012\,137\,852$ | $0.102\,406\,94$
$p_{ii}=\nicefrac{{1}}{{100}}$, $p_{ij}=\nicefrac{{9}}{{900}}$ |  |  $0.098\,002\,457\,582\,836\,82$±$0.031\,533\,340\,705\,481\,964$ | $0.089\,831\,117\,745\,367\,24$ |  $0.084\,334\,063\,794\,279\,07$±$0.007\,093\,750\,851\,698\,074$ | $0.082\,615\,788\,548\,559\,03$
|  $0.0$±$0.0$ | $0.0$ |  $0.090\,621\,635$±$0.008\,397\,878$ | $0.090\,055\,816$
Table 1: The number of closed walks with length $k$ for each node $v$ divided
by the total number of walks ending in $v$ and the corresponding estimates
$\mathbb{E}_{k=i}$ from Equation (10) of the proof for $k\in\\{1,2\\}$. The
proportions are averaged over all nodes and the standard deviation is
reported. The larger value is printed in bold for each graph and walk length
$k$ and their corresponding pair of proportions with and without self-loops.
Additionally, the standard deviation is printed in bold if the ranges of both
standard deviations do not overlap.

The statistics in Tab. 2 report the average walk proportions for larger $k$
and suggest that similar behaviour can be observed for all even $k$.

Dataset | $\circlearrowleft$ | $k=3$ | $k=4$ | $k=5$ | $k=6$
---|---|---|---|---|---
$p_{ii}=\nicefrac{{6}}{{100}}$, $p_{ij}=\nicefrac{{3}}{{900}}$ |  |  $0.026\,603\,384\,190\,756\,69$±$0.003\,550\,903\,051\,330\,844$ |  $0.018\,959\,660\,493\,627\,566$±$0.002\,663\,896\,228\,829\,275\,6$ |  $0.008\,475\,457\,974\,386\,473$±$0.001\,668\,048\,427\,144\,601\,5$ |  $0.005\,931\,625\,931\,971\,191$±$0.001\,470\,245\,608\,693\,936\,6$
|  $0.002\,269\,267\,6$±$0.002\,388\,666\,2$ |  $0.020\,353\,615$±$0.003\,423\,984\,6$ |  $0.002\,054\,691\,3$±$0.001\,219\,876\,3$ |  $0.005\,976\,999$±$0.001\,599\,984\,8$
$p_{ii}=\nicefrac{{6}}{{100}}$, $p_{ij}=\nicefrac{{6}}{{900}}$ |  |  $0.016\,272\,000\,621\,432\,647$±$0.001\,489\,318\,972\,300\,125\,3$ |  $0.011\,521\,913\,974\,739\,206$±$0.001\,466\,775\,170\,838\,532$ |  $0.004\,454\,785\,808\,776\,81$±$0.000\,816\,879\,459\,715\,930\,6$ |  $0.003\,115\,965\,555\,091\,865\,8$±$0.000\,716\,026\,334\,680\,257\,8$
|  $0.001\,447\,367\,5$±$0.001\,303\,767\,2$ |  $0.012\,192\,862$±$0.001\,805\,030\,2$ |  $0.001\,280\,507\,5$±$0.000\,569\,023\,54$ |  $0.003\,124\,170\,2$±$0.000\,758\,174\,63$
$p_{ii}=\nicefrac{{3}}{{100}}$, $p_{ij}=\nicefrac{{6}}{{900}}$ |  |  $0.025\,698\,050\,253\,830\,52$±$0.003\,201\,258\,973\,873\,876\,3$ |  $0.018\,027\,546\,544\,119\,928$±$0.002\,377\,286\,659\,590\,112$ |  $0.007\,464\,153\,316\,087\,125$±$0.001\,252\,720\,861\,900\,233\,2$ |  $0.005\,078\,400\,959\,528\,008$±$0.001\,156\,148\,762\,275\,348$
|  $0.000\,823\,967\,2$±$0.001\,373\,714\,4$ |  $0.019\,525\,16$±$0.003\,221\,58$ |  $0.000\,970\,015\,24$±$0.000\,639\,685\,8$ |  $0.005\,268\,694$±$0.001\,379\,166\,6$
$p_{ii}=\nicefrac{{1}}{{100}}$, $p_{ij}=\nicefrac{{9}}{{900}}$ |  |  $0.020\,241\,689\,277\,317\,294$±$0.001\,998\,253\,799\,888\,017$ |  $0.014\,346\,792\,411\,064\,064$±$0.001\,769\,178\,443\,099\,896\,3$ |  $0.005\,571\,283\,053\,296\,202$±$0.000\,898\,088\,907\,862\,485\,2$ |  $0.003\,841\,105\,397\,054\,509$±$0.000\,839\,149\,177\,743\,652\,8$
|  $0.000\,642\,165\,2$±$0.001\,037\,600\,3$ |  $0.015\,488\,376$±$0.002\,335\,122\,8$ |  $0.000\,889\,159\,5$±$0.000\,467\,799\,9$ |  $0.003\,983\,105\,5$±$0.000\,970\,687\,37$
Table 2: The average proportions as in Tab. 1 for larger $k$.

##  Appendix C Real-World Examples

To investigate this effect on real-world data, we use 23 datasets from PyTorch
Geometric [3]. Since we have only considered undirected graphs in our
theoretical analysis, we drop the direction of the edges in the datasets that
are directed. To avoid mathematical errors, we remove isolated nodes from all
datasets. We further disregard existing self-loops and either remove them or
add the missing ones.

Tab. 3 shows the statistics discussed in Appendix B for the real-world
examples. We can see that the degrees vary far more in the real-world examples
than in the synthetic graphs. Consequently, the standard deviations are larger
and the estimates are less accurate. The expected pattern from our theoretical
findings that the proportions are larger for walks of length 2 without self-
loops cannot be observed in all of the datasets. Although the estimates
falsely predict the pattern in all datasets, they still give a good indication
of when the pattern exists because the difference is very small ($<0.001$) in
most datasets where the pattern does not exist. The predicted pattern also
continues for larger walk lengths for some of the datasets which further
supports our hypothesis from Appendix B that this alternating pattern
continues for larger walk lengths.

Dataset | $\circlearrowleft$ | $k=1$ | $\mathbb{E}_{k=1}$ | $k=2$ | $\mathbb{E}_{k=2}$ | $k=3$ | $k=4$
---|---|---|---|---|---|---|---
Planetoid: |  |  $0.275\,317\,198\,695\,434\,4$±$0.127\,740\,723\,206\,358\,51$ | $0.204\,161\,636\,009\,594\,22$ |  $0.173\,741\,957\,271\,353\,44$±$0.112\,403\,660\,357\,576\,33$ | $0.083\,968\,371\,641\,792\,15$ |  $0.092\,251\,831\,747\,790\,77$±$0.106\,213\,393\,511\,941\,3$ |  $0.068\,979\,013\,570\,071\,7$±$0.104\,643\,439\,814\,865\,78$
Cora |  |  $0.0$±$0.0$ | $0.0$ |  $0.212\,607\,95$±$0.207\,334\,74$ | $0.091\,665\,365$ |  $0.016\,834\,421$±$0.031\,987\,876$ |  $0.090\,490\,595$±$0.203\,789\,47$
Planetoid: |  |  $0.350\,096\,093\,302\,264\,8$±$0.140\,101\,576\,307\,427\,34$ | $0.264\,798\,522\,437\,901\,7$ |  $0.274\,028\,758\,675\,982\,03$±$0.135\,704\,778\,842\,070\,83$ | $0.126\,367\,220\,317\,017\,78$ |  $0.199\,506\,910\,137\,516\,1$±$0.157\,364\,860\,802\,098\,9$ |  $0.176\,168\,243\,426\,699\,76$±$0.164\,110\,676\,604\,107\,25$
CiteSeer |  |  $0.0$±$0.0$ | $0.0$ |  $0.398\,827\,6$±$0.311\,160\,65$ | $0.144\,645\,69$ |  $0.017\,072\,25$±$0.039\,937\,202$ |  $0.286\,995\,35$±$0.350\,433\,53$
Planetoid: |  |  $0.339\,476\,675\,460\,045\,56$±$0.168\,729\,337\,008\,313\,3$ | $0.181\,949\,884\,205\,144\,44$ |  $0.104\,408\,605\,405\,920\,67$±$0.067\,992\,679\,941\,462\,02$ | $0.056\,249\,447\,832\,670\,364$ |  $0.032\,575\,956\,289\,999\,32$±$0.037\,484\,308\,252\,884\,23$ |  $0.017\,871\,887\,051\,941\,957$±$0.024\,460\,339\,874\,375\,406$
PubMed |  |  $0.0$±$0.0$ | $0.0$ |  $0.091\,916\,986$±$0.094\,300\,54$ | $0.059\,602\,03$ |  $0.001\,688\,375\,5$±$0.005\,851\,866\,7$ |  $0.017\,526\,256$±$0.030\,662\,94$
CitationFull: |  |  $0.271\,843\,525\,730\,537\,55$±$0.165\,239\,028\,731\,153\,54$ | $0.143\,507\,488\,980\,935\,96$ |  $0.151\,854\,903\,788\,674$±$0.128\,281\,437\,236\,251\,66$ | $0.046\,267\,213\,502\,470\,865$ |  $0.076\,211\,345\,375\,150\,15$±$0.120\,174\,819\,057\,316\,67$ |  $0.057\,391\,816\,916\,176\,494$±$0.117\,337\,881\,674\,100\,86$
DBLP |  |  $0.0$±$0.0$ | $0.0$ |  $0.185\,734\,42$±$0.234\,632\,86$ | $0.048\,511\,717$ |  $0.004\,685\,337$±$0.012\,634\,584$ |  $0.089\,139\,16$±$0.233\,149\,2$
Amazon: |  |  $0.078\,875\,624\,659\,817\,4$±$0.096\,446\,574\,099\,248\,59$ | $0.026\,665\,055\,435\,899\,972$ |  $0.022\,355\,942\,922\,862\,73$±$0.044\,919\,404\,644\,574\,6$ | $0.005\,714\,481\,606\,273\,39$ |  $0.005\,579\,272\,566\,361\,443\,6$±$0.033\,380\,615\,926\,525\,91$ |  $0.003\,590\,332\,367\,882\,722$±$0.031\,680\,452\,865\,369\,656$
Computers |  |  $0.0$±$0.0$ | $0.0$ |  $0.023\,424\,393$±$0.067\,648\,39$ | $0.005\,747\,325$ |  $0.002\,311\,902\,6$±$0.012\,156\,788$ |  $0.005\,118\,413$±$0.057\,773\,616$
Amazon: |  |  $0.080\,640\,943\,009\,227\,88$±$0.095\,877\,419\,117\,898\,43$ | $0.030\,667\,855\,660\,653\,55$ |  $0.026\,096\,422\,129\,453\,397$±$0.044\,793\,386\,711\,103\,93$ | $0.009\,622\,897\,560\,427\,756$ |  $0.007\,877\,852\,626\,339\,927$±$0.035\,428\,929\,847\,985\,756$ |  $0.005\,579\,726\,484\,124\,402$±$0.034\,426\,237\,878\,067\,374$
Photo |  |  $0.0$±$0.0$ | $0.0$ |  $0.027\,591\,048$±$0.072\,085\,425$ | $0.009\,716\,397$ |  $0.004\,052\,574$±$0.012\,209\,515$ |  $0.007\,448\,488\,4$±$0.064\,633\,54$
Coauthor: |  |  $0.169\,832\,777\,041\,121\,35$±$0.118\,506\,938\,716\,673\,25$ | $0.100\,663\,843\,611\,309\,24$ |  $0.090\,237\,748\,902\,795\,79$±$0.063\,675\,394\,668\,390\,9$ | $0.052\,037\,389\,272\,409\,03$ |  $0.029\,794\,177\,156\,373\,43$±$0.036\,273\,544\,115\,593\,866$ |  $0.014\,179\,928\,826\,730\,578$±$0.022\,391\,862\,484\,508\,21$
CS |  |  $0.0$±$0.0$ | $0.0$ |  $0.092\,180\,02$±$0.076\,811\,28$ | $0.054\,893\,926$ |  $0.010\,777\,668$±$0.015\,071\,858$ |  $0.011\,500\,124$±$0.020\,568\,62$
Wikipedia: |  |  $0.114\,582\,483\,811\,724\,21$±$0.118\,200\,333\,449\,005\,75$ | $0.035\,020\,531\,532\,058\,08$ |  $0.028\,410\,243\,790\,987\,885$±$0.048\,802\,390\,435\,707\,04$ | $0.009\,380\,244\,984\,107\,389$ |  $0.009\,624\,134\,924\,088\,834$±$0.023\,728\,623\,088\,808\,624$ |  $0.006\,285\,199\,527\,719\,737$±$0.013\,120\,278\,037\,002\,444$
Chameleon |  |  $0.0$±$0.0$ | $0.0$ |  $0.028\,610\,826$±$0.055\,304\,72$ | $0.009\,469\,067$ |  $0.005\,133\,608$±$0.011\,901\,251$ |  $0.005\,821\,18$±$0.011\,708\,718$
Wikipedia: |  |  $0.090\,863\,281\,004\,251\,37$±$0.107\,024\,554\,202\,867\,26$ | $0.012\,940\,804\,546\,974\,098$ |  $0.019\,512\,244\,529\,125\,46$±$0.036\,020\,446\,700\,296\,964$ | $0.002\,386\,784\,982\,759\,940\,6$ |  $0.003\,362\,435\,781\,398\,157$±$0.010\,472\,713\,155\,583\,872$ |  $0.001\,185\,908\,239\,504\,327\,2$±$0.003\,914\,279\,371\,318\,472$
Squirrel |  |  $0.0$±$0.0$ | $0.0$ |  $0.018\,372\,118$±$0.035\,970\,498$ | $0.002\,392\,495\,5$ |  $0.001\,267\,384\,5$±$0.003\,589\,850\,2$ |  $0.001\,055\,734\,5$±$0.003\,636\,138\,3$
Actor |  |  $0.247\,730\,611\,375\,073\,07$±$0.158\,800\,946\,790\,956\,72$ | $0.124\,757\,871\,564\,863\,7$ |  $0.080\,844\,782\,357\,299\,07$±$0.080\,512\,099\,706\,405\,01$ | $0.018\,854\,846\,147\,781\,514$ |  $0.015\,248\,481\,582\,201\,61$±$0.032\,462\,243\,812\,594\,986$ |  $0.004\,555\,490\,364\,665\,44$±$0.012\,755\,459\,513\,039\,363$
|  $0.0$±$0.0$ | $0.0$ |  $0.076\,522\,68$±$0.089\,827\,36$ | $0.019\,217\,184$ |  $0.001\,071\,362\,9$±$0.005\,477\,993\,3$ |  $0.003\,405\,577\,7$±$0.010\,085\,894$
Airports: |  |  $0.195\,990\,123\,727\,429\,1$±$0.172\,704\,366\,255\,191\,1$ | $0.041\,919\,119\,273\,777\,61$ |  $0.030\,099\,259\,242\,845\,386$±$0.050\,390\,756\,437\,836\,47$ | $0.010\,477\,485\,502\,397\,497$ |  $0.006\,670\,628\,032\,705\,2$±$0.031\,320\,317\,715\,542\,945$ |  $0.003\,948\,154\,109\,802\,572$±$0.029\,320\,086\,506\,934\,576$
USA |  |  $0.0$±$0.0$ | $0.0$ |  $0.027\,469\,004$±$0.070\,619\,28$ | $0.010\,588\,425$ |  $0.002\,530\,215\,8$±$0.005\,670\,297\,4$ |  $0.005\,394\,706$±$0.057\,932\,05$
Airports: |  |  $0.112\,796\,838\,915\,738\,5$±$0.125\,848\,710\,819\,478\,43$ | $0.032\,216\,390\,954\,084\,17$ |  $0.019\,573\,940\,995\,356\,906$±$0.023\,262\,616\,492\,304\,9$ | $0.014\,079\,146\,039\,569\,697$ |  $0.003\,585\,590\,264\,416\,338$±$0.002\,924\,077\,016\,330\,324\,4$ |  $0.002\,877\,351\,629\,693\,407$±$0.002\,598\,868\,753\,548\,429\,2$
Europe |  |  $0.0$±$0.0$ | $0.0$ |  $0.017\,306\,89$±$0.019\,381\,14$ | $0.014\,280\,199$ |  $0.002\,730\,973\,3$±$0.002\,471\,577\,4$ |  $0.002\,858\,33$±$0.002\,624\,297$
Airports: |  |  $0.159\,600\,512\,063\,881\,6$±$0.151\,097\,374\,708\,823\,6$ | $0.061\,300\,890\,081\,702\,87$ |  $0.032\,607\,481\,488\,784$±$0.012\,185\,113\,007\,722\,4$ | $0.029\,029\,548\,881\,512\,71$ |  $0.010\,358\,520\,678\,639\,902$±$0.006\,648\,955\,074\,708\,86$ |  $0.008\,550\,160\,860\,850\,503$±$0.007\,132\,599\,827\,304\,364$
Brazil |  |  $0.0$±$0.0$ | $0.0$ |  $0.028\,981\,725$±$0.012\,137\,854$ | $0.029\,897\,459$ |  $0.008\,120\,432$±$0.007\,033\,595$ |  $0.008\,447\,790\,5$±$0.007\,219\,271$
Twitch: |  |  $0.107\,490\,430\,489\,671\,34$±$0.119\,977\,861\,677\,002\,88$ | $0.030\,078\,473\,165\,004\,768$ |  $0.011\,045\,386\,733\,080\,283$±$0.027\,351\,286\,219\,759\,06$ | $0.003\,902\,644\,174\,448\,818\,5$ |  $0.000\,464\,802\,062\,471\,289\,4$±$0.002\,692\,635\,586\,394\,934$ |  $0.000\,183\,523\,902\,090\,283\,9$±$0.000\,233\,191\,086\,959\,590\,49$
DE |  |  $0.0$±$0.0$ | $0.0$ |  $0.009\,455\,832$±$0.024\,991\,876$ | $0.003\,917\,934\,4$ |  $0.000\,165\,118\,49$±$0.000\,205\,888\,43$ |  $0.000\,179\,539\,52$±$0.000\,224\,558\,67$
Twitch: |  |  $0.217\,150\,121\,895\,999\,7$±$0.155\,585\,664\,339\,702\,94$ | $0.091\,624\,454\,170\,602\,76$ |  $0.051\,042\,980\,754\,698\,57$±$0.068\,458\,657\,837\,860\,01$ | $0.016\,508\,600\,624\,765\,95$ |  $0.006\,728\,277\,680\,000\,525$±$0.020\,952\,626\,554\,511\,633$ |  $0.001\,740\,407\,556\,329\,444\,6$±$0.006\,475\,772\,568\,654\,605\,5$
EN |  |  $0.0$±$0.0$ | $0.0$ |  $0.046\,679\,903$±$0.073\,002\,03$ | $0.016\,785\,71$ |  $0.000\,807\,013\,5$±$0.002\,837\,603\,4$ |  $0.001\,340\,2$±$0.004\,200\,716\,5$
Twitch: |  |  $0.162\,742\,906\,791\,554\,2$±$0.144\,073\,874\,193\,718\,86$ | $0.055\,511\,245\,069\,598\,17$ |  $0.025\,490\,183\,595\,571\,942$±$0.046\,102\,539\,435\,202\,365$ | $0.008\,325\,968\,347\,750\,262$ |  $0.001\,956\,471\,880\,917\,455\,7$±$0.008\,755\,151\,700\,990\,128$ |  $0.000\,642\,672\,975\,552\,536\,7$±$0.003\,466\,500\,452\,551\,349\,7$
RU |  |  $0.0$±$0.0$ | $0.0$ |  $0.022\,015\,173$±$0.043\,955\,12$ | $0.008\,395\,872$ |  $0.000\,385\,645\,4$±$0.000\,739\,530\,4$ |  $0.000\,580\,433\,35$±$0.002\,306\,96$
WebKB: |  |  $0.350\,276\,730\,906\,584\,23$±$0.140\,504\,115\,646\,158\,5$ | $0.248\,303\,941\,779\,136\,34$ |  $0.132\,208\,212\,807\,339\,3$±$0.118\,742\,297\,602\,234\,43$ | $0.049\,270\,719\,115\,347\,15$ |  $0.045\,546\,356\,762\,835\,32$±$0.052\,639\,554\,648\,568\,67$ |  $0.024\,841\,605\,966\,097\,073$±$0.024\,467\,273\,547\,213\,727$
Cornell |  |  $0.0$±$0.0$ | $0.0$ |  $0.142\,929\,45$±$0.150\,085\,67$ | $0.051\,824\,13$ |  $0.006\,088\,204$±$0.011\,886\,508$ |  $0.023\,082\,197$±$0.030\,792\,281$
WebKB: |  |  $0.352\,732\,240\,437\,158\,5$±$0.132\,640\,524\,222\,439\,96$ | $0.246\,963\,566\,328\,787\,6$ |  $0.117\,944\,923\,374\,708\,5$±$0.113\,753\,291\,222\,484\,47$ | $0.041\,629\,361\,859\,526\,94$ |  $0.035\,471\,480\,784\,694\,52$±$0.042\,335\,413\,828\,001\,99$ |  $0.018\,224\,955\,719\,978\,32$±$0.018\,385\,903\,516\,872\,373$
Texas |  |  $0.0$±$0.0$ | $0.0$ |  $0.121\,115\,334$±$0.142\,193\,32$ | $0.043\,437\,645$ |  $0.003\,239\,942\,5$±$0.005\,992\,305\,5$ |  $0.016\,329\,2$±$0.021\,792\,298$
WebKB: |  |  $0.310\,338\,999\,823\,743\,8$±$0.133\,288\,384\,521\,872\,36$ | $0.218\,071\,242\,985\,142\,55$ |  $0.118\,652\,001\,078\,837\,39$±$0.106\,475\,253\,654\,442\,52$ | $0.045\,221\,586\,795\,943\,63$ |  $0.035\,557\,234\,568\,962\,94$±$0.044\,340\,790\,230\,216\,57$ |  $0.018\,173\,313\,591\,318\,4$±$0.018\,609\,359\,970\,902\,11$
Wisconsin |  |  $0.0$±$0.0$ | $0.0$ |  $0.123\,353\,42$±$0.129\,387\,63$ | $0.047\,363\,438$ |  $0.004\,182\,137\,5$±$0.008\,422\,742$ |  $0.016\,383\,175$±$0.019\,072\,773$
LastFM- |  |  $0.250\,626\,827\,754\,420\,36$±$0.163\,232\,815\,948\,024\,63$ | $0.120\,564\,238\,834\,876\,21$ |  $0.097\,551\,828\,172\,987\,26$±$0.085\,744\,710\,312\,931\,57$ | $0.037\,847\,150\,980\,930\,33$ |  $0.025\,993\,335\,133\,682\,505$±$0.040\,866\,427\,417\,655\,705$ |  $0.010\,763\,609\,765\,008\,484$±$0.021\,633\,415\,985\,961\,774$
Asia |  |  $0.0$±$0.0$ | $0.0$ |  $0.093\,838\,95$±$0.100\,823\,306$ | $0.039\,335\,903$ |  $0.004\,383\,334\,4$±$0.008\,357\,784$ |  $0.008\,732\,138$±$0.021\,267\,174$
Amazon- |  |  $0.137\,172\,464\,942\,435\,85$±$0.038\,715\,520\,579\,149\,384$ | $0.116\,300\,711\,989\,379\,41$ |  $0.093\,505\,150\,019\,158\,8$±$0.034\,706\,005\,310\,906\,94$ | $0.075\,239\,463\,589\,342\,75$ |  $0.056\,583\,720\,462\,568\,314$±$0.033\,541\,313\,077\,607\,57$ |  $0.049\,954\,916\,617\,174\,54$±$0.031\,791\,530\,835\,530\,9$
Ratings |  |  $0.0$±$0.0$ | $0.0$ |  $0.101\,498\,984$±$0.044\,048\,37$ | $0.081\,361\,026$ |  $0.041\,748\,278$±$0.031\,576\,995$ |  $0.049\,615\,096$±$0.031\,619\,69$
Roman- |  |  $0.270\,834\,560\,667\,761\,6$±$0.058\,951\,858\,373\,089\,076$ | $0.256\,021\,517\,433\,441\,54$ |  $0.246\,246\,847\,967\,984\,52$±$0.029\,787\,532\,993\,463\,817$ | $0.234\,305\,828\,588\,506\,1$ |  $0.173\,568\,241\,164\,477\,3$±$0.030\,147\,319\,133\,717\,945$ |  $0.149\,273\,027\,736\,832\,8$±$0.029\,802\,465\,243\,873\,325$
Empire |  |  $0.0$±$0.0$ | $0.0$ |  $0.315\,549\,37$±$0.059\,182\,01$ | $0.306\,004\,46$ |  $0.058\,811\,68$±$0.043\,280\,795$ |  $0.171\,570\,99$±$0.043\,354\,24$
Mine- |  |  $0.113\,344\,444\,444\,444\,48$±$0.011\,122\,766\,109\,467\,821$ | $0.112\,607\,537\,908\,053\,93$ |  $0.112\,560\,250\,000\,000\,01$±$0.005\,175\,395\,698\,103\,137$ | $0.112\,049\,552\,178\,403\,39$ |  $0.068\,437\,595\,433\,814\,03$±$0.003\,931\,543\,359\,049\,382$ |  $0.056\,009\,674\,848\,501\,6$±$0.003\,109\,596\,510\,996\,095\,3$
sweeper |  |  $0.0$±$0.0$ | $0.0$ |  $0.126\,705\,2$±$0.005\,929\,091\,5$ | $0.126\,188\,96$ |  $0.047\,669\,828$±$0.002\,691\,617$ |  $0.053\,629\,268$±$0.002\,950\,947$
Table 3: The average proportions and statistics as in Tab. 1 and Tab. 2 for
real-world datasets. The names of the datasets that are in line with our
theoretical results are marked in orange. As in Tab. 1, the larger number of
each value pair is printed in bold. Note that some values are rounded to the
same values. In this case, the value that was larger before rounding is
printed in bold.

The aforementioned datasets are further used to evaluate the performance of
the GCN model on node classification tasks. The training parameters are set to
similar values as above. We train the GCNs for 70 epochs on 80% of the nodes.
An Adam optimizer is used with learning rate $0.01$ and we include a dropout
layer with a dropout rate of $0.2$ after each GCN layer.

Our theoretical results make statements about the amount of information a node
retains about itself for MPNN architectures with two layers. Thus, it is
reasonable to assume that we can only expect results that are in line with our
theoretical findings if the node’s own feature is useful for the node
classification task. We measure the usefulness of a node’s own feature on the
performance of single-layered GCNs. The node’s own feature does not influence
the predictions of single-layered GCNs without self-loops and thus if that GCN
performs better than the one with self-loops, the node’s own feature can be
assumed to be not useful or even harmful to the task. We can observe those
results for 8 of the investigated datasets and report only the remaining 15
datasets in Fig. 2.

The results show that the parity of the number of message passing layers
strongly influences the performance of GCNs. In line with our analytical
results, we further find that for 11 out of 15 data sets the accuracy increase
of a two-layer compared to a one-layer GCN is larger for an input graph
without self-loops than a graph with self-loops. We suspect that this is due
to the self-loop paradox, which states that the inclusion of self-loops
actually limits the backflow of information from a node to itself for two
message passing layers.

Figure 2: Test set accuracies as in Fig. 1 for real-world examples. Outliers
outside of the whiskers are omitted for readability.

##  Appendix D The Self-Loop Paradox for Other GNNs

So far, we only considered the Graph Convolutional Network (GCN) [8] although
there exists a large variety of other GNN architectures. Lemma 1 holds for all
Message Passing GNNs (MPNNs) –sometimes also called Weisfeiler-Leman (WL) test
based GNNs [2]. By definition of [4], this includes all GNNs that can be
expressed with a message function

$\displaystyle\mathbf{m}_{v}^{(k+1)}=\sum_{u\in
N(v)}M^{(k)}\left(\mathbf{h}_{v}^{(k)},\mathbf{h}_{u}^{(k)},\mathbf{e}_{vu}\right)$
(12)

and an update function

$\displaystyle\mathbf{h}_{v}^{(k+1)}=U^{(k)}\left(\mathbf{h}_{v}^{(k)},\mathbf{m}_{v}^{(k+1)}\right).$
(13)

This includes GNNs like the GCN [8], GraphSAGE [6] or the Graph Isomorphism
Network (GIN) [17] but does not include models like Personalized Propagation
of Neural Predictions (PPNP) [9].

In contrast to the original formulation of the GCN, this general framework
does not rely on self-loops for all nodes since it includes the node’s own
feature in the update step. Our theoretical findings, on the other hand, are
based on the assumption that the node’s own feature is included via self-
loops. This means our findings do not apply to all MPNNs but only to those
that can be reformulated using a modified message step that includes self-
loops

$\displaystyle\mathbf{m}_{v}^{(k+1)}=\sum_{u\in
N(v)\cup\\{v\\}}M^{(k)}\left(\mathbf{h}_{v}^{(k)},\mathbf{h}_{u}^{(k)},\mathbf{e}_{vu}\right)$
(14)

and an update step that excludes the node’s own feature

$\displaystyle\mathbf{h}_{v}^{(k+1)}=U^{(k)}\left(\mathbf{m}_{v}^{(k+1)}\right).$
(15)

This includes the GCN as defined in Equation (4) but also the Graph Attention
Network (GAT) by [15]:

$\displaystyle\mathbf{m}_{v}^{(k+1)}$ $\displaystyle=\sum_{u\in
N(v)\cup\\{v\\}}a_{vu}^{(k)}\mathbf{h}^{(k)}_{u}W^{(k)}$ (16)
$\displaystyle\mathbf{h}_{v}^{(k+1)}$
$\displaystyle=\sigma\left(\mathbf{m}_{v}^{(k+1)}+\mathbf{b}^{(k)}\right)$
(17)

Technically, this is only true if one disregards that the Softmax function
considers the whole neighbourhood $N(v)$ to calculate the attention weights
$a_{vu}$ which would require a message function
$M^{(k)}\left(\mathbf{h}_{v}^{(k)},\mathbf{h}_{u}^{(k)},\mathbf{e}_{vu},\\{h_{w}^{(k)}:w\in
N(v)\\}\right)$. Other models like GraphSAGE and GIN do not fall into this
category since they both either concatenate or add the node’s feature
$\mathbf{h}_{v}^{(k)}$ to the aggregated message $\mathbf{m}_{v}^{(k+1)}$ in
the update function.