# Graph Neural Networks with Precomputed Node Features

Beni Egressy  Roger Wattenhofer

###### Abstract

Most Graph Neural Networks (GNNs) cannot distinguish some graphs or indeed
some pairs of nodes within a graph. This makes it impossible to solve certain
classification tasks. However, adding additional node features to these models
can resolve this problem. We introduce several such augmentations, including
(i) positional node embeddings, (ii) canonical node IDs, and (iii) random
features. These extensions are motivated by theoretical results and
corroborated by extensive testing on synthetic subgraph detection tasks. We
find that positional embeddings significantly outperform other extensions in
these tasks. Moreover, positional embeddings have better sample efficiency,
perform well on different graph distributions and even outperform learning
with ground truth node positions. Finally, we show that the different
augmentations perform competitively on established GNN benchmarks, and advise
on when to use them.

##  1 Introduction

Given the impressive success of neural networks in the text and image domains,
recently research has also turned its attention to graph-structured data. In
just a few years there has been explosive interest in the area, with Graph
Neural Networks (GNNs) achieving state-of-the-art results in a wide range of
applications, including molecule recognition, physics simulations,
recommendation systems, fake news detection and social networks (Fout, 2017;
Sanchez-Gonzalez et al., 2020; Ying et al., 2018).

Most GNN architectures are based on the message passing framework, which can
be summarized in three main steps: (1) node representations are initialized
with their initial features (if available) or node degrees (if not available);
(2) nodes update their representations by aggregating the representations of
neighboring nodes; (3) the final representations of nodes are combined in a
readout layer to solve the task at hand.

Although this framework has been a recipe for success, it has also been
observed that such GNNs are limited in their power to distinguish even very
simple graphs, e.g., see Figure 1 (top, ignoring the labels). This has been
formalized by proving that message-passing GNNs are upper-bounded by the
Weisfeiler-Lehman (WL) isomorphism test (Weisfeiler & Leman, 1968; Xu et al.,
2018; Morris et al., 2019). We shall refer to such GNNs as Weisfeiler-Lehman
GNNs, or WLGNNs.111We use the term WLGNNs as used in (Li et al., 2020) More
precisely, WLGNNs produce identical representations for (sub-)graphs that the
WL test fails to distinguish. In particular these include regular graphs,
where nodes cannot be distinguished based on their degree and the degree of
the nodes around them.

$2$$3$$0$$1$$4$$5$$2$$3$$0$$1$$4$$5$$(-0.3,-0.35)$$(0.31,0.36)$$(-0.2,0.45)$$(0.16,-0.5)$
Figure 1: Example of limitation of WLGNNs, which cannot distinguish the graphs
on left and right without node features. Both our augmentations, canonical ID
(above) and positional embedding (below) resolve this issue. For example the
two nodes with canonical ID $0$ (top) now have different $1$-hop neighborhoods
(${1,2,3}$ vs ${1,2,4}$) and can be distinguished by $2$ rounds of message
passing. For the positional embeddings, we only show the coordinates of select
nodes, but the positions correspond to the embeddings.

As a consequence there have been various suggestions to overcome the
expressive limit of WLGNNs. These include: breaking symmetries by making
perturbations to the input graph; using higher-order representations of the
input graph; and initializing the nodes with additional features.

The latter approach will be the focus of this paper. We explore the power of
GNNs augmented with precomputed node features. Since initializing node
representations is the first main step of most standard GNNs, this approach
can be combined with many different architectures.

Our main contributions are:

  * •

We propose several new augmentations for standard GNN architectures to improve
their expressive power beyond the WL test: canonical node IDs, $l_{\infty}$
embeddings, positional embeddings, random bits, and combinations of the above.
See Figure 1.

  * •

For several augmentations, we formally prove that they make appropriate GNN
architectures universal.

  * •

We conduct extensive subgraph detection tests on carefully constructed
benchmark datasets to show the empirical validity of these augmentations.

  * •

We show that the augmentations perform competitively on established
benchmarks.

##  2 Preliminaries

###  2.1 Notation

We consider unweighted, undirected, connected graphs $G=(V,E)$ consisting of
$n=|V|$ nodes. We denote an edge between nodes $u$ and $v$ by $e_{uv}$. We
denote the neighborhood of node $v$ by $N(v)=\\{u\in G\mid e_{uv}\in E\\}$,
the degree of node $v$ by $\deg(v)=|N(v)|$, and the maximum degree of all
nodes by $\Delta=\max_{v\in V}\deg(v)$. The graph diameter $D$ is the length
of the longest shortest path between any two nodes.

###  2.2 GNNs

Most GNN architectures are based on the message passing framework, which
consists of: (1) node initialization, (2) node updates via message passing,
and (3) a readout step. The message passing itself is conducted in rounds. In
each round there are three steps. First, every node creates a message based on
its current embedding. It then sends this message to each of its neighbors.
Second, when the nodes have received messages from each of their neighbors,
they aggregate these messages. Finally they update their state by combining
their current state with the aggregate embedding they have just calculated.
One round of message passing corresponds to one layer of a GNN. Usually $k$
layers are stacked on top of each other so that after $k$ rounds of message
passing each node will have received information, either directly or
indirectly, from all of the nodes in its $k$-hop neighborhood. Usually,
message, aggregate, update and readout are functions with learnable
parameters, and they are shared among all the nodes. In the simple case, where
the messages are the current state of the node, the GNN can be summarized as
follows:

$\displaystyle h_{v}^{(0)}$ $\displaystyle=x_{v}$ $\displaystyle a_{v}^{(t)}$
$\displaystyle=\textsc{aggregate}(\\{h_{u}^{(t-1)}\mid u\in N(v)\\})$
$\displaystyle h_{v}^{(t)}$
$\displaystyle=\textsc{update}(h_{v}^{(t-1)},a_{v}^{(t)})$ $\displaystyle
y_{v}$ $\displaystyle=\textsc{readout}(h_{v}^{(t)})$

where $x_{v}$ are the initial node features and $h_{v}^{(t)}$ is the embedding
vector, or representation, of node $v$ after $t$ rounds of message passing.
The readout layer above is a function of a single node in the case of node
classification, but could also be a function of all the nodes (graph
classification), or a subset of the nodes (link prediction).

Since reordering the nodes of a graph does not change the underlying topology,
in general we want to learn a graph or node function that is invariant to
permutations of the nodes. This is commonly ensured by treating incoming
messages as a set (or multiset) and learning a (permutation-invariant) set
aggregation function for aggregate.

###  2.3 Weisfeiler-Lehman Test

The message passing framework is closely related to the Weisfeiler-Lehman (WL)
isomorphism test. The WL test is an iterative color refinement procedure
(Weisfeiler & Leman, 1968; Shervashidze et al., 2011). Each node keeps a state
(or color) that gets refined in each iteration by aggregating information from
the neighbors’ states and combining it with its own.

More precisely, in each iteration we assign to each node a tuple containing
the node’s state and a multiset of the node’s neighbors’ states. Then we hash
these tuples to give each node its new state. In this way all nodes with
different tuples receive different new states and all nodes with the same
tuple receive the same new state. In particular two nodes with different
states at time $T\geq 0$ will never have the same state after time $T$; hence
we call this a refinement algorithm. All nodes are assigned the same initial
state, so for example, after the first iteration the state of a node
corresponds to its degree. To check whether two graphs are isomorphic we can
run this procedure on both graphs until convergence and then compare the
multisets of the final node states. If they are different, then the graphs are
not isomorphic. If they are the same, then we cannot be sure.

If the WL test cannot distinguish two graphs, then a standard message-passing
GNN cannot distinguish them either: intuitively, the nodes in the two graphs
receive the same messages and create the same embeddings in each round, and
thus they always arrive at the same final result. As such, a message-passing
algorithm can only be as powerful222as good at distinguishing non-isomorphic
graphs as the WL algorithm. In fact for some GNNs, it can be shown that they
are exactly as powerful as the WL isomorphism test. This is the case with GIN
(Xu et al., 2018), which we shall rely on in this paper.

The WL test can be extended to start with an initial labelling of the nodes.
If the nodes have initial features, then these can be hashed to give the
initial states before continuing the algorithm. Similarly, initial features
can be used to increase the power of a GNN. For example, in chemistry
problems, the nodes might represent atoms of a molecule, and so the type of
atom would be an initial feature for each node (Irwin et al., 2012; Yanardag &
Vishwanathan, 2015).

###  2.4 Distributed Computing Models

The GNN message passing framework is also closely related to message passing
models in distributed computing333The connection between GNNs and distributed
computing models was first noted in (Loukas, 2019)..

As GNNs, distributed computing deals with a network of nodes, connected by
message passing edges, and the task is to calculate some function of the
graph. As GNNs, all nodes also execute the same algorithm; however, the
algorithm is designed rather than learned.

One major difference to GNNs is that in distributed computing, the nodes
usually have unique IDs.444There are exceptions, in particular anonymous
networks (Emek et al., 2014). This ensures that a node can always distinguish
its neighbors and indeed all nodes in the graph. If computation and
communication is unbounded, any problem can be solved in $D$ rounds of message
passing, where $D$ is the diameter of the graph. Each node can simply encode
all the information it has about the graph so far into a message and send this
information to all of its neighbors in every round. With the help of the
unique IDs, after $D$ rounds, every node will know the exact topology of the
graph.

##  3 Motivation

Upon considering the aforementioned distributed computing model, one natural
way to increase the power of GNNs is to treat the node indices as node IDs and
use the one-hot encoding of node indices as an input feature. This way the GNN
can distinguish all the nodes, and it can theoretically distinguish all non-
isomorphic graphs, making it “universal”. However, the embedding will depend
heavily on the initial ordering of the vertices, and there are $n!$ possible
permutations. As such the GNN loses its inductive advantage of mapping nodes
with identical neighborhoods to the same embedding, resulting in a great loss
in generalization ability. Similarly, one could use random features as input
node features (Abboud et al., 2020; Sato et al., 2021). This can also be
proven to give “universal” GNNs, but it also leads to the same generalization
problems. Basically, we want to give each node a label such that:

  1. (a)

the probability to have the same label(s) is high if the graph is the same,
and

  2. (b)

the probability to have the same label(s) is low if the graph is not the same.

Using no labels (or identical labels), as in the WL algorithm, perfectly
achieves a, but does not do well regarding b, since many graphs remain
indistinguishable. On the other hand, using node indices or random features as
labels may achieve “universality” b, but does less well regarding a. The
problem is that the additional information is not permutation invariant. As a
consequence, exponentially more training examples might be needed. The
additional information can also confuse the learning procedure, and the GNN
may weigh the additional information too heavily in the decision process.

We hypothesise that the right balance of a and b is at the core of a deeper
understanding of GNNs. By keeping the additional information low, we get a net
benefit from adding it. We explore this hypothesis by testing different
augmentations aimed at balancing a and b.

First, we propose adding a vector of random bits. By controlling the length of
the vector we have a fine grained control over a and b. Second, we propose
precomputed _canonical node IDs_ ; these do not burden the learner with an
exponential input diversity, while at the same time offering benefits
regarding b.

The most impressive results are obtained by our novel precomputed _positional
node embeddings_. Like random features, these geometric labels also fulfill b
to a sufficient degree. While positional embeddings add even more information
than node IDs, in practice GNNs can interpret positional coordinates well.
GNNs seem to develop an understanding of these coordinates (e.g., the distance
between two positions), without being distracted by the erratic raw values of
the positions.

###  3.1 Canonical node IDs

Canonical node IDs are node IDs that are standardized such that all the nodes
in a graph always receive the same IDs however the nodes are permuted at the
input. It is not clear how we can find canonical node IDs fast in practise.
Indeed, an algorithm that produces canonical node IDs also solves the graph
isomorphism problem, and until recently it was not known whether the graph
isomorphism problem can be solved in sub-exponential time. However, Babai et
al. showed that solving graph isomorphism and finding a canonical form can be
done in quasipolynomial time (Helfgott et al., 2017; Babai, 2019). However,
their approach is mostly of academic interest, since in practice the overhead
is too high. Instead, nauty (McKay & Piperno, 2014) and bliss (Junttila &
Kaski, 2007) are used in practice. These algorithms do not guarantee a sub-
exponential runtime, but are fast in practice. We will use nauty when
calculating canonical orderings in this paper. See Figure 1 for example graphs
with canonical IDs.

First we show that GNNs with canonical node IDs can theoretically distinguish
any two non-isomorphic graphs. The proof follows from Corollary 3.1 in
(Loukas, 2019). As such we leave the proof for the appendix.

######  Theorem 3.1.

GIN of sufficient depth augmented with canonical node IDs can distinguish any
two non-isomorphic graphs.

In our empirical tests, we use the one-hot encoding of the canonical node IDs
as initial node features. Note that using canonical node IDs is very similar
to using the node indices as features. But crucially there are no longer $n!$
possible inputs for the same graph. Instead a graph will always receive the
same labelling. We expect this to lead to better learning and sample
efficiency.

###  3.2 Positional node Embeddings

There have been recent attempts to improve GNNs by learning positional
embeddings, see for example (Ma et al., 2021) and (Klemmer et al., 2021).
However, these are based on solving some auxiliary task while training the
main network, with the former using a combined neural network, and the latter
focusing on geographic data.

Using precomputed positional node embeddings has several potential advantages
over learned embeddings. Firstly, the node embedding algorithms we use in this
paper take the whole graph topology into account. This allows them to
differentiate nodes that have the same local neighborhoods. Of course, one
could also use fully connected message passing to achieve this. But message
passing GNNs have a known problem with oversmoothing and fully connected
layers would only exaggerate this problem. GNNs with precomputed node features
do exacerbate this issue, as nodes still aggregate messages from their
neighbors rather than being flooded by information from the whole graph.
Finally, precomputed node features are also very versatile; the node features
can be used to augment any standard GNN.

####  $l_{\infty}$-embeddings

We propose embedding the input graph into $l_{\infty}$ and using the locations
as node features. We begin by showing that any graph can be embedded into
$l_{\infty}$ isometrically (i.e., such that all shortest path distances are
preserved). If we have an embedding that preserves all the distances, then no
information about the graph is lost. One could throw away the graph topology
and the set of embeddings would still hold all the information.

######  Theorem 3.2.

Every graph $G=(V,E)$ embeds isometrically into $l_{\infty}$.

See the appendix for a proof. Unfortunately the embedding in the proof uses
$n$ dimensions, and adding node features of length $n$ is impractical for
large graphs. It can be shown that $\Theta(n)$ is in fact a lower bound for
the dimension of isometric embeddings into $l_{\infty}$ (Coppersmith, 2001).
For other $l_{p}$ spaces, isometric embeddings are not even possible.

We use the isometric $l_{\infty}$-embeddings from the proof in our synthetic
tasks. These graphs are small enough for this approach to be practical.
Moreover, we can prove that GNNs with $l_{\infty}$-embeddings are “universal”.
The proof follows the same approach as Theorem 3.1, see appendix.

######  Theorem 3.3.

GIN of sufficient depth augmented with isometric $l_{\infty}$-embeddings can
distinguish any two non-isomorphic graphs.

Although these embeddings do not lose any information about the graph, there
is a major drawback. The embeddings are large and their dimension depends on
the number of nodes, so if we want our model to work for train or test graphs
of up to $n$ nodes, then we need to use labels of length $n$. This is not only
inconvenient, but makes the learning problem much harder. As an alternative we
introduce approximate Euclidean embeddings.

#### Positional Embeddings

To calculate our positional embeddings we use a force-directed technique based
on an approach proposed in (Kamada et al., 1989). The main idea is to obtain a
layout of the graph minimizing the following stress function:

$\textsc{stress}(P)=\sum_{i<j}w_{ij}\left(||p(v_{i})-p(v_{j})||_{2}-d_{ij}\right)^{2},$

where $p(v_{i})$ is the coordinate position of vertex $v_{i}$ in the Euclidean
vector space; $d_{ij}$ is the shortest path distance between nodes $v_{i}$ and
$v_{j}$; and $w_{ij}$ is a weighting factor for balancing the influence of
certain pairs of nodes. We use $w_{ij}=d_{ij}^{-2}$. The localized Newton-
Raphson method is used to optimize the stress function. This is an iterative
solver, where in each step a single node is chosen and the standard N-R method
is used to find a local minimum of the stress function. See Figure 1 for
example graphs with labels.

One can think of this approach as placing an ideal spring between every pair
of nodes with length equal to the shortest path distance between the
endpoints. The springs are then used to push/pull the nodes so that their
euclidean distance approximates their shortest path distance in the graph.

These algorithms are randomized so they do not produce the same embeddings
when run multiple times555We run the embedding algorithm a single time for
each training and test graph, and thereafter keep these embeddings fixed
during training.. However, the relative positions between nodes are always
optimized. Intuitively, this is something that should help with generalization
to unseen graphs. Regardless of the exact placement of nodes, relative
distances should be preserved. Unlike random features or canonical node
labels, relative positions encode structural information about the nodes.

Figure 2: Example graphs that cannot be embedded into Euclidean space (of any
dimension).

In general, unlike with the $l_{\infty}$ space, graphs cannot always be
isometrically embedded into the euclidean space, see Figure 2. Moreover there
can be optimum solutions (with lowest stress), where different nodes receive
the same position. This means that we cannot apply the same universality
result that we used in Theorem 3.1, and the associated augmented GNNs are no
longer universal function approximators. This is highly unlikely in multiple
dimensions.

###  3.3 Random Baselines

Using random node features to initialize GNNs was first explored in (Sato et
al., 2021), and was shown to give universal function approximators in (Abboud
et al., 2020). In the latter, uniform and normal distributions, and in the
former discrete uniform distributions are used to initialize the nodes. We
initialize our random features in three different ways:

Random Gaussian: In this model, we add a vector of $d$ random Gaussian samples
to each node. The samples are generated i.i.d., from a $\mathcal{N}(0,1)$
distribution. This is similar to (Abboud et al., 2020). We denote this as
_rNormal( $d$)_.

Random Uniform Integer: In this model, we assign a random integer from $0$ to
$99$ to each node; denoted _rUniform_.

Randombits: In this model, we add a vector of $d$ random bits to each node.
The random bits are generated i.i.d., from a Bernouilli(0.5) distribution. We
denote this as _rBits( $d$)_.

Note that random features can be viewed as a form of training data
augmentation. We generate the features freshly each time an input graph is
presented to the model. As such the model sees many versions of the same
training graph. This could be an advantage over the precalculated canonical
and positional node features.

###  3.4 Our Model

First we precalculate the additional node features for a given input graph, be
they canonical node IDs, positional node embeddings, or random features. We
then concatenate the precalculated node features with the provided node
features (if available) and use these as input for our GNN. We mainly use the
GIN architecture for consistency (Xu et al., 2018). We choose GIN as it can be
shown to be theoretically as powerful as the WL test.

##  4 Experiments

###  4.1 Model Parameters

Unless otherwise stated, we use GIN as our standard WLGNN. We use $5$ layers
by default with hidden dimension $64$. We use weighted cross-entropy loss,
Adam optimizer with initial learning rate 0.01 and decay of rate $0.5$ after
every $50$ epochs. We use dropout on the final layer and we train for $300$
epochs by default with a batch size of $32$.

###  4.2 Datasets beyond WL

model | C3 | C4 | C5 | C6 | K4 | K5 | K6 | LCC
---|---|---|---|---|---|---|---|---
GIN | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500
+canon(20) | 0.943 | 0.605 | 0.544 | 0.560 | 0.673 | 0.594 | 0.577 | 0.843
+$l_{\infty}$(20) | 0.686 | 0.597 | 0.526 | 0.548 | 0.598 | 0.562 | 0.536 | 0.701
+pos(2) | 0.968 | 0.910 | 0.763 | 0.723 | 0.780 | 0.751 | 0.752 | 0.880
+pos(2)+rBits(1) | 0.968 | 0.910 | 0.773 | 0.722 | 0.783 | 0.755 | 0.758 | 0.884
+rUniform(1) | 0.913 | 0.675 | 0.593 | 0.598 | 0.551 | 0.519 | 0.514 | 0.686
+rNormal(1) | 0.898 | 0.652 | 0.587 | 0.609 | 0.553 | 0.512 | 0.508 | 0.685
+rBits(2) | 0.949 | 0.701 | 0.612 | 0.622 | 0.546 | 0.507 | 0.515 | 0.695
ppgn∗ (Maron et al., 2019) | 0.707 | 0.742 | 0.667 | 0.623 | 0.629 | 0.651 | 0.706 | 0.645
dropgnn (Papp et al., 2021) | 0.665 | 0.671 | 0.671 | 0.624 | 0.655 | 0.675 | 0.658 | 0.660

Table 1: AUROC scores on the synthetic tasks using GIN with $5$ layers as the
base GNN model. Model name indicates the node feature used to augment the base
model, with numbers in brackets indicating the size of the additional node
features. All models were run with the same hyperparameter settings (epochs,
learning rate, dropout, etc.). ∗Ppgn had to be adapted for node
classification.

To systematically test the practical expressiveness of GNNs with the suggested
node features, we propose a series of binary node classification tasks on
regular graphs. The model is tasked with detecting a particular subgraph in
the input, and outputting $1$ for all nodes that are in such a subgraph, and
$0$ for all nodes that are not in such a subgraph. Since the graphs are
regular, the tasks cannot be solved by standard WLGNNs; indeed all nodes look
identical to the WL test.

Ci_N: We generate N regular train and N regular test graphs, with ground truth
labels indicating whether a node is in a cycle of length i. This synthetic
task is based on C3_1000 from (Sato et al., 2021). The degree we use for
generating these regular graphs is given by the degree that leads to the
closest-to-even split of ground truth labels.666An exception to this is
C3_1000, where we use degree $3$ (instead of $4$) to match the degree from
(Sato et al., 2021).

Ki_N: We generate N train and N test graphs, with ground truth labels
indicating whether a node is in a clique of size i.

LCC_N: We generate N train and N test graphs, with ground truth labels
indicating how many triangles a node is in. See (Sato et al., 2021). 777LCC,
or local clustering coefficient, of a node in a graph quantifies how close its
neighbors are to being a clique. This is given by the number of triangles
divided by the number of potential triangles based on the number of neighbors.
Here we do not divided by the number of potential triangles, so the labels are
just a triangle counts.

Note that we do not discard any randomly generated graphs based on the number
of $0$ and $1$ labels. This ensures that our datasets do not have any prior
biases resulting from the generation process. They come from the uniform
distribution over all connected regular graphs of given degree with given
size. Also note that this means that the GIN test accuracy baseline (with no
additional node features) is given by the $max$ of the proportion of $0$’s and
$1$’s. However the weighted AUROC (Area Under the Receiver Operating
Characteristic Curve) baseline for WLGNNs is $0.5$. As such we will generally
quote weighted AUROC scores, following (Sato et al., 2021). Please check the
appendix for the accuracy scores.

We ran all our augmentations individually and we combined the top two
augmentation (positional embeddings and random bits) by concatenating the
features. All GIN based models were run with the same hyperparameter settings.
We compare against ppgn (Maron et al., 2019) and the recent DropGNN (Papp et
al., 2021), both of them models specifically designed to go beyond the WL
test. We adapted ppgn for node classification, as it was implemented as a
graph classification model. See Table 1 for the results. Most notable is that
the positional embeddings outperform all the alternatives on all the datasets.
We ran the same experiments with GCN (Kipf & Welling, 2016) as our base model
and got similar results, see appendix.

###  4.3 Effect of Embedding Dimension

We experiment with using larger embedding spaces for the positional
embeddings. Additional dimensions allow for better separation of the nodes;
this can be particularly advantageous for dense graphs. However, we find that
$2$-dimensional embeddings perform the best across the synthetic tasks. See
Figure 3 for results on C3.

Figure 3: Weighted test AUROC scores for different positional embedding
dimensions. Results for C3 task.

###  4.4 Investigating Learning Efficiency

As noted in our description, we expect GNNs with canonical IDs to have a
better learning efficiency, because the nodes of an input graph will always
receive the same IDs. This is in contrast to the random augmentations. To
confirm this, we plot the training loss per epoch for C3_1000 in Figure 4. We
see that the training loss for the model with canonical IDs drops the fastest
and levels off the soonest. The model with positional node embeddings levels
off next and the random augmentations level off last. See the appendix for a
similar plot of the test AUROC.

Figure 4: Training loss over the first 300 epochs on C3.

###  4.5 Investigating Sample Efficiency

The models utilizing positional node embeddings perform significantly better
on all the synthetic tasks with the limited training data (N=1000). This
suggests that positional node embeddings, although not necessarily consistent
between isomorphic graphs, store graph topological data is a somewhat
consistent and generalizable way. Since neighboring nodes are placed closer
together, it becomes possible to check whether two neighbors are themselves
connected based on their positions. This, at least intuitively, might explain
why GNNs with positional node embeddings are dramatically better at finding
small cycles and cliques in regular graphs.

As we increase the training data available, the GNN with one-hot canonical
node labels eventually ends up overtaking even the GNNs with positional node
embeddings for the smaller cycle detection tasks, C3 and C4. We show results
for C4 in Table 2. On all other synthetic tasks, the positional node
embeddings still outperform the alternatives.

model | C4_1000 | C4_2000 | C4_4000 | C4_8000
---|---|---|---|---
GIN | 0.500 | 0.500 | 0.500 | 0.500
+canon(20) | 0.624 | 0.645 | 0.794 | 0.970
+$l_{\infty}$(20) | 0.577 | 0.598 | 0.624 | 0.635
+pos(2) | 0.904 | 0.932 | 0.945 | 0.949
rUniform(1) | 0.669 | 0.673 | 0.677 | 0.669
rNormal(1) | 0.669 | 0.665 | 0.666 | 0.667
rBits(2) | 0.689 | 0.708 | 0.696 | 0.709

Table 2: Weighted AUROC scores with different training dataset sizes on the C4
cycle detection task.

###  4.6 Effect on Other Graph Distributions

We check that the higher expressivity of our model with positional embeddings
does not come at the cost of lower accuracy on other graph distributions,
where standard GNNs already perform well. We repeat the synthetic tasks with
Erdős-Renyi graphs in place of regular graphs. A graph is constructed by
initializing $n$ nodes and connecting every pair of nodes independently with
probability $p$. We choose $p$ separately for each task so as to balance the
ground truth labels of the dataset. The results can be seen in Figure 5.

Figure 5: Weighted test AUROC on Erdős-Rényi graphs.

We see that in most tasks, the model with random bits achieves the highest
test accuracy. However the other models do not perform much worse. In
particular, the model using positional embeddings also performs similarly to
using no additional node features.

###  4.7 Positional Embeddings vs Ground Truth Positions

To compare the positional embeddings with ground truth positions, we generate
unit disk graphs in the two dimensional euclidean plane. We select $20$ points
in the unit square uniformly at random and connect nodes that are within a
certain threshold distance to give us our graph. The threshold distance is
chosen per task so as to keep the classes balanced. We augment the GNN with
ground truth positions and compare against using our own positional
embeddings.

Figure 6: Weighted test AUROC on unit disk graphs.

The results can be seen in Figure 6. The positional embeddings perform better
than the ground truth positions in almost every task. In several tasks the
standard GNN performs the best. This indicates that unit disk graphs can be
distinguished by standard GNNs with a high probability.

###  4.8 Benchmark Datasets

dataset | MUTAG | PTC | PROTEINS | NCI1 | COLLAB | IMDBBINARY | IMDBMULTI | REDDITBINARY
---|---|---|---|---|---|---|---|---
size | 188 | 344 | 1113 | 4110 | 5000 | 1000 | 1500 | 2000
classes | 2 | 2 | 2 | 2 | 3 | 2 | 3 | 2
avg node count | 17.9 | 25.5 | 39.1 | 29.8 | 74.4 | 19.7 | 13 | 429.6
WL subtree (Shervashidze et al., 2011) | 90.4 $\pm$ 5.7 | 59.9 $\pm$ 4.3 | 75.0 $\pm$ 3.1 | 86.0 $\pm$ 1.8 | 78.9 $\pm$ 1.9 | 73.8 $\pm$ 3.9 | 50.9 $\pm$ 3.8 | 81.0 $\pm$ 3.1
Invariant Graph Networks (Maron et al., 2018) | 83.89$\pm$12.95 | 58.53$\pm$6.86 | 76.58$\pm$5.49 | 74.33$\pm$2.71 | 78.36$\pm$2.47 | 72.0$\pm$5.54 | 48.73$\pm$3.41 | NA
GIN (Xu et al., 2018) | 89.4$\pm$5.6 | 64.6$\pm$7.0 | 76.2$\pm$2.8 | 82.7$\pm$1.7 | 80.2$\pm$1.9 | 75.1$\pm$5.1 | 52.3$\pm$2.8 | 92.4 $\pm$ 2.5
1-2-3 GNN (Morris et al., 2019) | 86.1$\pm$ | 60.9$\pm$ | 75.5$\pm$ | 76.2$\pm$ | NA | 74.2$\pm$ | 49.5$\pm$ | NA
ppgn (Maron et al., 2019) | 90.55$\pm$8.7 | 66.17$\pm$6.54 | 77.2$\pm$4.73 | 83.19$\pm$1.11 | 80.16$\pm$1.11 | 72.6$\pm$4.9 | 50$\pm$3.15 | NA
DropGNN (Papp et al., 2021) | 90.4 $\pm$7.0 | 66.3 $\pm$8.6 | 76.3 $\pm$6.1 | NA | NA | 75.7 $\pm$4.2 | 51.4 $\pm$2.8 | NA
GIN∗ | 89.33$\pm$5.6 | 63.65$\pm$11.2 | 73.68$\pm$3.7 | 82.24$\pm$1.3 | 78.00$\pm$2.1 | 74.90$\pm$2.9 | 51.20$\pm$2.8 | 89.95$\pm$1.6
+canon(20) | 86.14$\pm$7.2 | 61.89$\pm$4.2 | 70.81$\pm$4.8 | 67.42$\pm$2.2 | 74.22$\pm$1.9 | 69.30$\pm$3.9 | 47.13$\pm$2.9 | 79.25$\pm$4.3
+pos(2) | 83.51$\pm$5.2 | 61.39$\pm$7.7 | 74.21$\pm$3.6 | 74.40$\pm$2.5 | 74.70$\pm$1.9 | 70.60$\pm$3.0 | 49.60$\pm$3.8 | 89.15$\pm$2.0
+pos(2)+rBits(1) | 86.67$\pm$6.3 | 59.04$\pm$7.3 | 73.76$\pm$3.7 | 74.96$\pm$1.6 | 75.20$\pm$1.3 | 71.50$\pm$2.5 | 50.67$\pm$3.3 | 89.00$\pm$1.6
+rBits(2) | 89.80$\pm$7.9 | 65.10$\pm$8.3 | 75.38$\pm$3.8 | 81.73$\pm$2.0 | 76.10$\pm$2.2 | 75.30$\pm$3.6 | 51.87$\pm$2.3 | 90.60$\pm$2.1

Table 3: Test accuracies and standard deviations on the benchmark tasks. ∗We
include scores for our base GIN model for consistency; these are slightly
lower than the official values. We highlight the best augmentation and the
best overall model.

We evaluate our augmented GIN models on real-world graph classification
datasets. We compare against the original GIN architecture and various GNN
models that aim to go beyond the WL test. We consider four bioinformatics
datasets (MUTAG, PTC, PROTEINS, NCI1) and four social network datasets
(COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY) (Yanardag & Vishwanathan,
2015).

We follow the experimental setup from the original GIN paper (Xu et al.,
2018). For the social network datasets we use the node degree as the input
feature and for the bioinformatics datasets we use the categorical node
features supplied with the graphs. We report the 10-fold cross-validation
accuracies, with mean and standard deviation (Yanardag & Vishwanathan, 2015).
We use the original 5-layer GIN model (4 layers + input layer) and we apply
the most promising augmentations from our synthetic experiments.

Out of the different augmentations, random bits preforms the best on most of
the benchmark datasets, outperforming also the base model without additional
node features. The augmentations are not state of the art, but they perform
competitively on all the tasks. Given how well the WL subtree baseline
performs on the datasets, it is possible that classifying graphs in this
dataset rarely requires higher expressiveness. As such there is little added
value in our augmentations elevating GIN beyond the WL barrier. This is also
the case for the other expressive GNNs.

##  5 Related Work

The first works applying neural networks to graphs used recurrent neural
networks to learn node representations (Gori et al., 2005; Scarselli et al.,
2008). Afterwards many works drew on the success of convolutional neural
networks (Krizhevsky et al., 2012) and generalized this approach to graphs
(Henaff et al., 2015; Kipf & Welling, 2016; Hamilton et al., 2017; Veličković
et al., 2017). Many of these approaches were later shown to fit into the same
general framework of message passing neural networks (Gilmer et al., 2017). In
turn this whole framework was shown to be related to, and indeed upper-bounded
by the WL isomorphism test. Although the WL test can distinguish graphs with a
very high probability, it has some notable blind spots such as detecting
cycles in regular graphs.

In an effort to overcome this boundary, there have been many proposals for
increasing the expressive power of GNNs. These include: adding port numbers to
edges (Sato et al., 2019), adding random features (Sato et al., 2021; Abboud
et al., 2020), randomly dropping nodes or edges (Papp et al., 2021; Rong et
al., 2019), adding subgraph counts (Bouritsas et al., 2020), or mimicking
higher order WL tests (Maron et al., 2019; Morris et al., 2019). But many of
these either still fail to distinguish simple graphs or are prohibitively
expensive.

Positional encodings also play a major role in NLP. The current state-of-the-
art NLP models are based on the permutation invariant attention mechanism
(Devlin et al., 2018; Lewis et al., 2019). But since the relative positions of
words is of great importance to meaning, positional embeddings are added to
the input tokens to indicate order (Shaw et al., 2018).

##  6 Conclusion

We find that positional node embeddings can be very effective for subgraph
detection, and can learn to generalize with limited training data. They should
be used in applications where subgraph detection is critical, or where the
data has inherent spatial meaning. Canonical node IDs will be more useful in
applications with plenty of data. Random bits can be useful in any scenario
and clearly outperform more noisy random features. They can be considered both
for increasing expressivity in WL blind spots, and as a form of data
augmentation. One could also consider using additional node features only for
the “difficult” cases. These could be identified by running a WL test before
applying a GNN.

## References

  * Abboud et al. (2020) Abboud, R., Ceylan, I. I., Grohe, M., and Lukasiewicz, T.  The surprising power of graph neural networks with random node initialization.  _arXiv preprint arXiv:2010.01179_ , 2020.
  * Babai (2019) Babai, L.  Canonical form for graphs in quasipolynomial time: preliminary report.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 1237–1246, 2019.
  * Bouritsas et al. (2020) Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M.  Improving graph neural network expressivity via subgraph isomorphism counting.  _arXiv preprint arXiv:2006.09252_ , 2020.
  * Coppersmith (2001) Coppersmith, D.  L infinity embeddings.  In _Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques_ , pp. 223–228. Springer, 2001.
  * Devlin et al. (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Emek et al. (2014) Emek, Y., Pfister, C., Seidel, J., and Wattenhofer, R.  Anonymous Networks: Randomization = 2-Hop Coloring.  In _33rd ACM Symposium on Principles of Distributed Computing (PODC), Paris, France_ , July 2014.
  * Fout (2017) Fout, A. M.  _Protein interface prediction using graph convolutional networks_.  PhD thesis, Colorado State University, 2017.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , pp. 1263–1272. PMLR, 2017.
  * Gori et al. (2005) Gori, M., Monfardini, G., and Scarselli, F.  A new model for learning in graph domains.  In _Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005._ , volume 2, pp. 729–734. IEEE, 2005.
  * Hamilton et al. (2017) Hamilton, W. L., Ying, R., and Leskovec, J.  Inductive representation learning on large graphs.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pp. 1025–1035, 2017.
  * Helfgott et al. (2017) Helfgott, H. A., Bajpai, J., and Dona, D.  Graph isomorphisms in quasi-polynomial time.  _arXiv preprint arXiv:1710.04574_ , 2017.
  * Henaff et al. (2015) Henaff, M., Bruna, J., and LeCun, Y.  Deep convolutional networks on graph-structured data.  _arXiv preprint arXiv:1506.05163_ , 2015.
  * Irwin et al. (2012) Irwin, J. J., Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G.  Zinc: a free tool to discover chemistry for biology.  _Journal of chemical information and modeling_ , 52(7):1757–1768, 2012.
  * Junttila & Kaski (2007) Junttila, T. and Kaski, P.  Engineering an efficient canonical labeling tool for large and sparse graphs.  In _2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX)_ , pp. 135–149. SIAM, 2007.
  * Kamada et al. (1989) Kamada, T., Kawai, S., et al.  An algorithm for drawing general undirected graphs.  _Information processing letters_ , 31(1):7–15, 1989.
  * Kipf & Welling (2016) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Klemmer et al. (2021) Klemmer, K., Safir, N., and Neill, D. B.  Positional encoder graph neural networks for geographic data.  _arXiv preprint arXiv:2111.10144_ , 2021.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * Lewis et al. (2019) Lewis, M., Liu, Y., Goyal, N., Ghazvininejad, M., Mohamed, A., Levy, O., Stoyanov, V., and Zettlemoyer, L.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ , 2019.
  * Li et al. (2020) Li, P., Wang, Y., Wang, H., and Leskovec, J.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  _arXiv preprint arXiv:2009.00142_ , 2020.
  * Loukas (2019) Loukas, A.  What graph neural networks cannot learn: depth vs width.  _arXiv preprint arXiv:1907.03199_ , 2019.
  * Ma et al. (2021) Ma, L., Rabbany, R., and Romero-Soriano, A.  Graph attention networks with positional embeddings.  In _PAKDD (1)_ , pp. 514–527. Springer, 2021.
  * Maron et al. (2018) Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y.  Invariant and equivariant graph networks.  _arXiv preprint arXiv:1812.09902_ , 2018.
  * Maron et al. (2019) Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y.  Provably powerful graph networks.  _arXiv preprint arXiv:1905.11136_ , 2019.
  * McKay & Piperno (2014) McKay, B. D. and Piperno, A.  Practical graph isomorphism, ii.  _Journal of symbolic computation_ , 60:94–112, 2014.
  * Morris et al. (2019) Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 4602–4609, 2019.
  * Papp et al. (2021) Papp, P. A., Martinkus, K., Faber, L., and Wattenhofer, R.  DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Rong et al. (2019) Rong, Y., Huang, W., Xu, T., and Huang, J.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_ , 2019.
  * Sanchez-Gonzalez et al. (2020) Sanchez-Gonzalez, A., Godwin, J., Pfaff, T., Ying, R., Leskovec, J., and Battaglia, P.  Learning to simulate complex physics with graph networks.  In _International Conference on Machine Learning_ , pp. 8459–8468. PMLR, 2020.
  * Sato et al. (2019) Sato, R., Yamada, M., and Kashima, H.  Approximation ratios of graph neural networks for combinatorial problems.  _arXiv preprint arXiv:1905.10261_ , 2019.
  * Sato et al. (2021) Sato, R., Yamada, M., and Kashima, H.  Random features strengthen graph neural networks.  In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_ , pp. 333–341. SIAM, 2021.
  * Scarselli et al. (2008) Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G.  The graph neural network model.  _IEEE transactions on neural networks_ , 20(1):61–80, 2008.
  * Shaw et al. (2018) Shaw, P., Uszkoreit, J., and Vaswani, A.  Self-attention with relative position representations.  _arXiv preprint arXiv:1803.02155_ , 2018.
  * Shervashidze et al. (2011) Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M.  Weisfeiler-lehman graph kernels.  _Journal of Machine Learning Research_ , 12(9), 2011.
  * Veličković et al. (2017) Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Weisfeiler & Leman (1968) Weisfeiler, B. and Leman, A.  The reduction of a graph to canonical form and the algebra which appears therein.  _NTI, Series_ , 2(9):12–16, 1968.
  * Xu et al. (2018) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Yanardag & Vishwanathan (2015) Yanardag, P. and Vishwanathan, S.  Deep graph kernels.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 1365–1374, 2015.
  * Ying et al. (2018) Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J.  Graph convolutional neural networks for web-scale recommender systems.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 974–983, 2018.

##  Appendix A Proof of Theorem 3.1

######  Theorem A.1.

GINs of sufficient depth augmented with canonical node IDs can distinguish any
two non-isomorphic graphs.

The proof follows from Corollary 3.1 in (Loukas, 2019). First we state the
corollary again for convenience:

Corollary 3.1. $GNN^{n}_{mp}$ can compute any Turing computable function over
connected attributed graphs if the following conditions are jointly met: each
node is uniquely identified; (MSG) and UP are Turing-complete for every layer;
the depth is at least $d\geq D$ layers; and the width is unbounded.

$D$ denotes the diameter of the graph. $GNN^{n}_{mp}$ refers to a general
message passing GNN. (MSG) and UP are alternative characterizations of the
aggregate and update steps. The equivalence of the two models is shown in the
paper. And GIN (with sufficient width and depth) is used an example of a
network that satisfies the conditions of the theorem.

###### Proof.

First note that if we can compute any Turing computable function over
connected attributed graphs, then in particular we can also solve the graph
isomorphism problem. So what remains to be shown is that GIN augmented with
canonical node IDs satisfies the condition of the corollary. We already know
that GIN with appropriate hyperparameters satisfies the conditions on the GNN.
And finally, if we assign a canonical ID to each node, then each node is
uniquely identified. ∎

##  Appendix B Proof of Theorem 3.2

######  Theorem B.1.

Every graph $G=(V,E)$ embeds isometrically into $l_{\infty}$.

###### Proof.

Let $V=\\{v_{1},v_{2},\ldots v_{n}\\}$. We define
$f_{i}(v_{j})=d(v_{i},v_{j})$, i.e., as the distance between nodes $v_{i}$ and
$v_{j}$ in $G$, and we define the mapping of the nodes into $l_{\infty}$ as:

$f(v_{j})=\begin{pmatrix}f_{1}(v_{j})\\\ \ldots\\\ f_{n}(v_{j})\end{pmatrix}$

Then by the triangle inequality, we have for any $k\in 1,2,\ldots,n$

$\lvert f_{k}(v_{i})-f_{k}(v_{j})\rvert=\lvert
d(v_{i},v_{k})-d(v_{k},v_{j})\rvert\leq d(v_{i},v_{j}).$

Therefore,

$\lVert f(v_{i})-f(v_{j})\rVert_{\infty}\leq d(v_{i},v_{j}).$

And by construction, considering $k=i$ gives

$\lVert f(v_{i})-f(v_{j})\rVert_{\infty}=\max_{k}\lvert
f_{k}(v_{i})-f_{k}(v_{j})\rvert\geq\lvert
f_{i}(v_{i})-f_{i}(v_{j})\rvert=f_{i}(v_{j})=d(v_{i},v_{j}).$

Combining these we have

$\lVert f(v_{i})-f(v_{j})\rVert_{\infty}=d(v_{i},v_{j}).$

∎

##  Appendix C Proof of Theorem 3.3

######  Theorem C.1.

GIN of sufficient depth augmented with isometric $l_{\infty}$-embeddings can
distinguish any two non-isomorphic graphs.

###### Proof.

The proof follows the same reasoning as the proof of Theorem A.1 above. What
remains to be shown is that the $l_{\infty}$-embeddings we defined in the
proof of Theorem B.1 are unique. However, this is trivial by construction,
since for all $v_{i},v_{j}\in V$, we have

$\lVert f(v_{i})-f(v_{j})\rVert_{\infty}=d(v_{i},v_{j})\geq 0.$

This of course holds for all isometric embedding, since the distance between
any two nodes in an unweighted graph is always at least $1$. ∎

##  Appendix D Synthetic Datasets

Here are the complete results for the synthetic datasets using GIN as the base
GNN architecture. We include both test AUROC and test accuracy tables. Scores
are always from the final epoch.

Figure 7: AUROC scores on the synthetic tasks using GIN with 5 layers as the
base GNN model. Figure 8: Test accuracies on the synthetic tasks using GIN
with 5 layers as the base GNN model.

Here are the complete results for the synthetic datasets using GCN as the base
GNN architecture. We include both test AUROC and test accuracy tables. Scores
are always from the final epoch.

Figure 9: AUROC scores on the synthetic tasks using GCN with 5 layers as the
base GNN model. Figure 10: Test accuracies on the synthetic tasks using GCN
with 5 layers as the base GNN model.

##  Appendix E Further Experiments

###  E.1 Canon has better learning efficiency

In terms of the test AUROC, canon and pos models level out at around the same
time, at epoch $100$, but the pos model at a higher value. The models with the
random augmentations level off much later, after epoch $250$.

Figure 11: Weighted test AUROC over the first 300 epochs on C3.