# EDEN: A Plug-in Equivariant Distance Encoding to Beyond the 1-WL Test

Chang Liu, Yuwen Yang, Yue Ding, Hongtao Lu∗

###### Abstract

The message-passing scheme is the core of graph representation learning. While
most existing message-passing graph neural networks (MPNNs) are permutation-
invariant in graph-level representation learning and permutation-equivariant
in node- and edge-level representation learning, their expressive power is
commonly limited by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test.
Recently proposed expressive graph neural networks (GNNs) with specially
designed complex message-passing mechanisms are not practical. To bridge the
gap, we propose a plug-in Equivariant Distance ENcoding (EDEN) for MPNNs. EDEN
is derived from a series of interpretable transformations on the graph’s
distance matrix. We theoretically prove that EDEN is permutation-equivariant
for all level graph representation learning, and we empirically illustrate
that EDEN’s expressive power can reach up to the 3-WL test. Extensive
experiments on real-world datasets show that combining EDEN with conventional
GNNs surpasses recent advanced GNNs.

##  1 Introduction

The pervasiveness of graph-structured data in modern society, such as social
networks (Tang et al. 2009), recommendation systems (Fan et al. 2019), and
bio-medicine (Marinka Zitnik and Leskovec 2018), has led to the rapid
development of Graph Neural Networks (GNNs) (Zhou et al. 2020). When
representing a graph, perturbing the IDs of nodes in the graph should ensure
that the representation of the graph does not change. GNNs are preferably
either permutation-invariant for graph-level representation learning or
permutation-equivariant for node- and edge-level representation
learning(Azizian and Lelarge 2020). Message-passing Neural Networks (MPNNs)
(Gilmer et al. 2017; Hamilton, Ying, and Leskovec 2017; Kipf and Welling 2017;
Velickovic et al. 2018; Xu et al. 2019) with the property of permutation-
invariance/equivariance have become the de facto standard for graph
representation learning tasks. However, the expressive power of MPNNs is
commonly limited to the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test
(Huang and Villar 2021), which means MPNNs fail to distinguish nodes or graphs
in many special cases (e.g., $d-$regular graphs). This main issue hinders the
performance of MPNNs and poses a big challenge for the deep graph learning
community.

Recent works have attempted to tackle the problem from three different lines
of thought.

  * •

Learning differentiated global information by randomly labeling nodes (Li et
al. 2020; You, Ying, and Leskovec 2019). But such randomness loses the
property of equivariance and the ability to handle graph-level tasks.

  * •

Building GNNs with higher-order graph isomorphism test capability (e.g., k-WL
test and Folklore test (Huang and Villar 2021)), but higher-order GNNs lead to
high computational complexity (Azizian and Lelarge 2021; Balcilar et al. 2021;
Maron et al. 2019a, b).

  * •

Designing the feature aggregator from new perspectives, such as ego graphs
(You et al. 2021) and overlapping subgraphs (Wijesinghe and Wang 2021). The
potential problem is that it deviates from the message-passing mechanism,
making it difficult to apply to downstream tasks.

Despite the significant progress in the study of the expressiveness of GNNs,
there is still a lack of simple but effective approaches that make GNNs
powerfully expressive and, at the same time, applicable to downstream tasks.
This paper aims to show that it is easy to break through the limitation of the
1-WL test in MPNNs by applying a simple plug-in encoding. To be specific, we
propose Equivariant Distance ENcoding (abbreviate for EDEN), which is inspired
by recent beyond-1-WL GNNs and the position encoding in Transformer (Vaswani
et al. 2017). As shown in Fig.1, EDEN is derived from a series of
interpretable transformations on the distance matrix consisting of the length
of the shortest path between nodes. EDEN is actually a deterministic position
encoding with global information because the distance matrix is innate for a
certain graph. The unique advantage of EDEN is the property of permutation-
equivariance for all-level graph representation learning, providing powerful
expressiveness in graph isomorphism tests and downstream tasks.

Figure 1: Equivariant Distance ENcoding, namely EDEN, is obtained from the
distance matrix of the graph through equivariant mapping, where the distance
matrix records the shortest path length between two nodes. In the graph
isomorphism test, EDEN is used as a deterministic node coloring and enables
classical GNNs to distinguish regular graphs (even 4-regular graphs). EDEN is
also a plug-in embedding representing nodes’ global position to improve MPNNs’
performance on downstream tasks.

Our major contributions include:

  * •

We propose a simple but effective distance encoding called EDEN, and we
theoretically prove that EDEN satisfies the property of permutation-
equivariance in all-level graph representation learning, which is unavailable
for existing plug-in encoding methods for GNN.

  * •

We generalize the cosine positional encoding to non-Euclidean spaces via phase
propagation. We empirically show that the expressive power of EDEN reaches up
to the 3-WL test on graph isomorphism test datasets.

  * •

As a plug-in, EDEN can greatly improve the performance on downstream tasks
when combined with conventional MPNNs. Moreover, experiments show that it is
even superior to state-of-the-art methods.

##  2 Preliminaries

Let $G=(V,E)$ denote a graph, where $V$ is the set of nodes and $E$ is the set
of edges. $|V|=n$ and $|E|$ represent the number of nodes and edges,
respectively. A graph $G$ can also be represented as a composition of the
adjacency matrix $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ and
$\boldsymbol{X}\in\mathbb{R}^{n\times l}$ formed by the feature embeddings of
nodes, where $l$ is the dimension of the node embedding. The row order of
$\boldsymbol{X}$ is the same as $\boldsymbol{A}$.

##### Permutation-Equivariance, Permutation-Invariance and Graph Isomorphism

We denote $\sigma\star$ as a permutation operation on graph $G$, i.e., re-
arranging nodes in $V$ with given order $\sigma$. Permuting node order is
equivalent to swapping the corresponding rows and columns in $\boldsymbol{A}$,
and rows in $\boldsymbol{X}$. $f,g$ are two functions defined on the graph
$G=(\boldsymbol{A},\boldsymbol{X})$.

######  Definition 1.

Function $g$ is permutation-equivariant if $g(\sigma\star G)=\sigma\star
g(G)$, function $f$ is permutation-invariant if $f(\sigma\star G)=f(G)$, and
Graph $G$ and $G^{\prime}$ are isomorphisc if $\exists\sigma\text{,
{s.t.}}\quad G=\sigma\star G^{\prime}$.

######  Lemma 1.

The composition of $f$ and $g$ is permutation-invariant if $f$ and $g$ satisfy
the property of permutation-invariant and permutation-equivariant,
respectively.

$Proof.\quad f(g(\sigma\star G))=f(\sigma\star g(G))=f(g(G)).$

In other words, equivariance makes the output order correspond to the input
order, while invariance makes the output independent of the input order. Since
nodes in the graph are naturally order-independent, changing the node’s ID
should keep its embedding unchanged. For node-level graph representation
learning, nodes’ feature embeddings will be permuted if we change their order
in the graph, which satisfies permutation-equivariance. Regarding graph-level
representation learning, permuting nodes’ ID does not affect the output of the
graph embedding (e.g., graph average pooling), which satisfies permutation-
invariance.

##### Message-passing based GNN

We define MPNNs that satisfy the form defined in GIN (Xu et al. 2019):

$\displaystyle\mathbf{m}_{u}^{(k)}=\operatorname{MSG}^{(k)}\left(\mathbf{h}_{u}^{(k-1)}\right)$
(1)
$\displaystyle\mathbf{h}_{v}^{(k)}=\operatorname{AGG}^{(k)}\left(\left\\{\mathbf{m}_{u}^{(k)},u\in\mathcal{N}(v)\right\\},\mathbf{h}_{v}^{(k-1)}\right),$

where $\mathbf{h}_{v}^{(k)}$ is node $v$’s feature embedding in the $k$-th
layers. $\mathbf{h}_{v}^{(0)}=\mathbf{x}_{v}$, and $x_{v}$ is node $v$’s
feature embedding. $\mathbf{m}_{v}^{(k)}$ is the message embedding, and
$\mathcal{N}(v)$ is the set of (1-hop) neighborhoods of $v$. Different MPNNs
differ in MSG and AGG.

##  3 EDEN:An Equivariant Distance Encoding

In this section, we describe EDEN in detail. We propose our crucial insight
that the position of a node in the graph is an inherently universal feature
that can be represented by measuring the distance to other nodes. Inspired by
the sequential positional encoding method in Transformer (Vaswani et al. 2017)
and the distance-based GNNs (Li et al. 2020; You, Ying, and Leskovec 2019), we
generalize the cosine positional encoding to non-Euclidean spaces and utilize
mathematical transformations to make it permutation-equivariant.

Let $\boldsymbol{D}\in\mathbb{R}^{n\times n}$ denote the distance matrix,
where “distance” means the shortest path length between two nodes in $G$
obtained by the _Dijkstra’s algorithm_ (Dijkstra 1959). The diagonal elements
of $\boldsymbol{D}$ are all 0. We define the “diameter” $d_{i}$ of node
$v_{i}$ as follows:

######  Definition 2.

Diameter is the longest distance among reachable nodes of a given node,

$d_{i}=\max_{j}\boldsymbol{D}_{i,j},\quad\text{where
}\boldsymbol{D}_{i,j}\neq\infty.$ (2)

We map the $i$-th row of the distance matrix $\boldsymbol{D}$ w.r.t. its
diameter $d_{i}$ by the cosine function to obtain a normalized matrix
$\hat{\boldsymbol{D}}$. We call this operation phase propagation:

$\hat{\boldsymbol{D}}_{i,j}=\left\\{\begin{aligned}
&\cos(\frac{\pi}{d_{i}}\times\boldsymbol{D}_{i,j}),&\boldsymbol{D}_{i,j}\neq\infty\\\
&-1.5,&\boldsymbol{D}_{i,j}=\infty.\end{aligned}\right.$ (3)

where $\frac{\pi}{d_{i}}\times\boldsymbol{D}_{i,j}$ means node $v_{i}$’s all
reachable nodes (including $v_{i}$ itself) are mapped to phase $[0,\pi]$. Due
to the nature of the cosine function, the distance between node $v_{i}$ and
its closest neighbor (it is actually itself) is mapped to 1, and the distance
between $v_{i}$ and its farthest reachable node is mapped to -1. We use -1.5
(as long as it is less than -1) to represent the distance between unreachable
nodes.

The processed matrix $\hat{\boldsymbol{D}}$ has the following properties:

  * •

Normalization: The computed phase
$\frac{\pi}{dia_{i}}\times\boldsymbol{D}_{i,j}$ in Eq. (3) ranges in
$[0,\pi]$, so $\hat{\boldsymbol{D}}_{i,j}\in[-1,1]$.

  * •

Distinctiveness: Each row in $\hat{\boldsymbol{D}}$ is distinguished from
others because only $\hat{\boldsymbol{D}}_{i,i}=1$ and only
$\boldsymbol{D}_{i,i}=0$.

  * •

Interpretability: The element $\hat{\boldsymbol{D}}_{i,j}$ is an interpretable
transformation of the distance between node $i$ and $j$.

Matrix $\boldsymbol{D}$ and $\hat{\boldsymbol{D}}$ do not have permutation
equivariance if we consider each row as the feature embedding of the
corresponding node. To develop an intuition for this phenomenon, consider that
we swap node $v_{0}$ and $v_{1}$, and the corresponding rows
$\boldsymbol{D}_{0,:}$ and $\boldsymbol{D}_{1,:}$ should also be swapped if
$\boldsymbol{D}$ is permutation-equivariant. Nevertheless, this contradicts
the fact that the diagonal elements $\boldsymbol{D}_{i,i}=0$ (i.e.,
Distinctiveness). In addition, $\hat{\boldsymbol{D}}$ as the embedding matrix
with the dimension of $n$ is undoubted too large for downstream tasks. So we
employ the Principal Component Analysis (PCA) (Wold, Esbensen, and Geladi
1987) to reduce the dimension of $\hat{\boldsymbol{D}}$ to the size of
$n\times m$, where $m$ is a manually set hyperparameter:

$\boldsymbol{F_{\hat{\boldsymbol{D}}}}=\text{PCA}(\hat{\boldsymbol{D}}).$ (4)

$\boldsymbol{F_{\hat{\boldsymbol{D}}}}$ is our proposed Equivariant Distance
ENcoding (EDEN).

###  3.1 A theoretical proof of EDEN’s equivalence

######  Definition 3.

Permutation matrix $\boldsymbol{P}$ is a square binary matrix that has exactly
one entry of 1 in each row and each column and 0s elsewhere (Godsil and Royle
2001).

######  Lemma 2.

As permutation matrices are orthogonal matrices (i.e.,
$\boldsymbol{P}_{\sigma}\boldsymbol{P}_{\sigma}^{\top}=\boldsymbol{I}$ ), the
inverse matrix exists and can be written as
$\boldsymbol{P}^{-1}=\boldsymbol{P}^{\top}$.

######  Definition 4.

Matrices $\boldsymbol{A},\boldsymbol{B}\in\mathbb{R}^{n\times n}$ are called
similar (i.e., $\boldsymbol{A}\sim\boldsymbol{B}$) if there exists an
invertible matrix $\boldsymbol{T}\in\mathbb{R}^{n\times n}$ such that
$\boldsymbol{B}=\boldsymbol{T}^{-1}\boldsymbol{A}\boldsymbol{T}$. And then
$\boldsymbol{A}$ and $\boldsymbol{B}$ share same eigenvalues (Hefferon 2008).

Considering a distance matrix $\boldsymbol{D}$ and permutation matrix
$\boldsymbol{P}$, the permuted distance matrix $\boldsymbol{D}^{\prime}$ is:

$\boldsymbol{D^{\prime}}=\boldsymbol{P^{\top}DP}.$ (5)

######  Lemma 3.

Node-level Permutation-equivariant Considering a distance matrix
$\boldsymbol{D}$ and permuted distance matrix
$\boldsymbol{D^{\prime}}=\boldsymbol{P^{\top}DP}$, let
$\boldsymbol{F_{D}}=\text{PCA}(\boldsymbol{D}),\boldsymbol{F_{D^{\prime}}}=\text{PCA}(\boldsymbol{D^{\prime}})$
, we have

$\boldsymbol{F_{D^{\prime}}}=\boldsymbol{P^{\top}F_{D}}.$ (6)

###### Proof.

Since

$\boldsymbol{D^{\prime\top}D^{\prime}}=(\boldsymbol{P^{\top}DP})^{\top}(\boldsymbol{P^{\top}DP})=\boldsymbol{P^{-1}D^{\top}DP},$
(7)

with Definition 4, we know that $\boldsymbol{D^{\prime\top}D^{\prime}}$ and
$\boldsymbol{D^{\top}D}$ share same eigenvalues because
$\boldsymbol{D^{\prime\top}D^{\prime}}\sim\boldsymbol{D^{\top}D}.$ We perform
eigen-decomposition on them to employ PCA,

$\boldsymbol{D^{\top}D}=\boldsymbol{V\Sigma_{D}V^{\top}},\boldsymbol{D^{\prime\top}D^{\prime}}=\boldsymbol{W\Sigma_{D^{\prime}}W^{\top}},\\\
$ (8)

the i-th columns of $\boldsymbol{V}$ and $\boldsymbol{W}$ are eigenvectors
corresponding to the i-th largest eigenvalues of $\boldsymbol{D^{\top}D}$ and
$\boldsymbol{D^{\prime\top}D^{\prime}}$. $\boldsymbol{\Sigma_{D}}$ and
$\boldsymbol{\Sigma_{D^{\prime}}}$ are diagonal matrices consisting of ranked
eigenvalues. Notice that $\boldsymbol{\Sigma_{D}=\Sigma_{D^{\prime}}=\Sigma}$
because $\boldsymbol{D^{\prime\top}D^{\prime}}$ and $\boldsymbol{D^{\top}D}$
share same eigenvalues. Select the first $m$ columns of $\boldsymbol{V}$ and
$\boldsymbol{W}$ , and then we have $\boldsymbol{\widetilde{V}}$ and
$\boldsymbol{\widetilde{W}}$ which can be used to project the data from $n$
down to $m$ dimensions according to the definition of PCA (Wold, Esbensen, and
Geladi 1987):

$\displaystyle\boldsymbol{F_{D}}$
$\displaystyle=\text{PCA}(\boldsymbol{D})=\boldsymbol{D\widetilde{V}}$ (9)
$\displaystyle\boldsymbol{F_{D^{\prime}}}$
$\displaystyle=\text{PCA}(\boldsymbol{D^{\prime}})=\boldsymbol{D^{\prime}\widetilde{W}},$

since (7) and (8),

$\boldsymbol{D^{\prime\top}D^{\prime}}=\boldsymbol{P^{\top}D^{\top}DP}=\boldsymbol{P^{\top}V\Sigma
V^{\top}P},$ (10)

we have $\boldsymbol{W=P^{\top}V}$. The left multiplication matrix
$\boldsymbol{P^{\top}}$ doesn’t affect the operation of taking the first
$\boldsymbol{m}$ columns of the matrix by row transformation, so

$\boldsymbol{\widetilde{W}=\widetilde{P^{\top}V}=P^{\top}\widetilde{V}}.$ (11)

In summary,

$\boldsymbol{F_{D^{\prime}}}=\boldsymbol{D^{\prime}\widetilde{W}}=\boldsymbol{D^{\prime}P^{\top}\widetilde{V}}=\boldsymbol{P^{\top}DPP^{\top}\widetilde{V}}=\boldsymbol{P^{\top}F_{D}}.$

It is clear that swapping the order of phase propagation in Eq. (3) and
matrices permutation in Eq. (5) does not change the result:

$\boldsymbol{\hat{D^{\prime}}}=\boldsymbol{\widehat{P^{\top}DP}}=\boldsymbol{P^{\top}\hat{D}P},$
(12)

we can draw a similar conclusion that
$\boldsymbol{F_{\hat{D^{\prime}}}=P^{\top}F_{\hat{D}}}$ is node-level
permutation-equivariant. ∎

######  Lemma 4.

The eigen-decomposition is not unique.

Proof. We assume that the eigenvectors are standard vectors. Considering the
following two cases: (1) When the eigenvalue is unique (i.e., the eigenvalue
is not equal to other eigenvalues), its corresponding eigenvector has a sign
difference: if $X_{i}$ is the eigenvector corresponding to the i-th
eigenvalue, then $-X_{i}$ is also the eigenvector. (2) When the eigenvalues
are not unique (i.e., there are $p$ eigenvalues with the same value), the
dimension $k$ of the eigenvector space corresponding to that eigenvalue will
be less than or equal to $p$ because the geometric multiplicity is less than
or equal to the algebraic multiplicity. The basis of the eigenvector space is
the eigenvector. When $k>1$, there are infinite possibilities of bases, and
different bases can be interconverted by orthogonal matrices.

It is important to note that the sign flipping problem mentioned in the first
case of lemma 4 can be avoided in practice. The deterministic outputs of PCA
or the eigen-decomposition operation used in Eq. (8) can be ensured by a given
rule111 https://github.com/scikit-learn/scikit-
learn/blob/baf0ea25d/sklearn/decomposition/˙pca.py#L519 to guarantee EDEN’s
equivariance.

###  3.2 Complexity analysis

For a graph with $n$ nodes, the computational complexity of EDEN mainly lies
in obtaining the distance matrix $\boldsymbol{D}$ and PCA, both of which have
the complexity of $O(n^{3})$. The space complexity required to store and
transform $\boldsymbol{D}$ is $O(n^{2})$. Although the total complexity
reaches $O(n^{3})$, we show that it is still efficient to apply EDEN in
practice: (1) Recent advanced expressive GNNs (e.g., F-GNN (Maron et al.
2019a) and GNNML3 (Balcilar et al. 2021)) modify the message-passing scheme,
and their time complexity and space complexity are $O(n^{3})$ and $O(n^{2})$
respectively through training and inference. But EDEN does not change the
computational primitives (i.e., message-passing) when applied to deep graph
learning. It works as a simple plug-in, so the total complexity of EDEN is a
“one-shot deal”, which means the additional time complexity incurred during
inference is only $O(k\times n)$. (2) The time complexity of most existing
eigenvalue-based decomposition methods for position encoding is $O(n^{3})$,
e.g., the state-of-the-art Laplacian PE (Dwivedi et al. 2020), and the space
complexity of Laplacian PE is at least $O(n^{2})$. (3) EDEN only takes
$O(k\times n)$ space after PCA, and $k\ll n$ is fully applicable for large
real-world graphs, but recent advanced high-order GNNs require larger memory
resources (See Tab. 2).

##  4 Experiments

We provide the pseudo code and core python implementation of EDEN in Appendix
A.

###  4.1 EDEN for Graph Isomorphic Test

Model | GRAPH8C | SR25 | EXP
---|---|---|---
MLP | 293K | 105 | 600
GCN | 4775 | 105 | 600
GAT | 1828 | 105 | 600
GIN | 386 | 105 | 600
CHEBNET | 44 | 105 | 71
F-GNN | 0 | 105 | 0
GNNML1 | 333 | 105 | 600
GNNML3 | 0 | 105 | 0
EDEN+GIN | 0 | 101 | 0
Table 1:  The results of graph isomorphic test. The total number of pairs is
61M, 105, and 600 for the GRAPH8C, SR25, and EXP datasets, respectively. The
data in the table represents the number of MISJUDGED graph pairs.

We test the expressive power of EDEN on graph isomorphism test datasets of
GRAPH8C, SR25 222http://users.cecs.anu.edu.au/∼bdm/data/graphs.html, and EXP
(Abboud et al. 2021). GRAPH8C has 11,177 non-isomorphic graphs with eight
nodes, which contains $C^{2}_{11117}=62,401,191$ possible different pairs. In
GRAPH8C, 312 of 62M pairs are 1-WL equivalent, which means only GNNs with at
least 2-WL expressiveness can distinguish them. The SR25 dataset contains 15
strong 12-regular graphs with 25 nodes, which contains $C^{2}_{15}=105$
possible non-isomorphic pairs. The EXP dataset has 600 pairs of 1-WL
equivalent non-isomorphic graphs.

Following the previous settings (Balcilar et al. 2021), we compare EDEN (with
a GIN readout) with the following baselines: MLP, GCN (Kipf and Welling 2017),
GAT (Velickovic et al. 2018), GIN (Xu et al. 2019), CHEBNET (Defferrard,
Bresson, and Vandergheynst 2016), F-GNN (Maron et al. 2019a), GNNML1 and
GNNML3 (Balcilar et al. 2021). We iteratively initialize GNN models 100 times
with different random seeds to readout graphs. A pair of graphs are considered
non-isomorphic if they can be separated at least once.

The results are shown in Tab. 1, which describes the number of MISJUDGED graph
pairs. Note that F-GNN and GNNML3 are designed w.r.t. the 3-WL test. It shows
that EDEN can help traditional MPNN (GIN) surpass recent advanced GNNs and
improve the expressive power beyond the 1-WL test. Fig. 1 illustrates a real
example of using EDEN on three 4-regular graphs, where nodes’ colors are
normalized 3-dimensional EDEN and are presented as the RBG brightness to
facilitate visualization. It can be observed that nodes’ colors on the two
non-isomorphic graphs are entirely different, and the isomorphic pair of
graphs share the same colors. Intuitively, we can identify graph pairs by
judging the colors of nodes on them. We also use EDEN on other graphs and find
that up to 2-WL equivalent regular graphs can be correctly judged by nodes’
colors. See Appendix B for more examples (1-WL, 2-WL, and 3-WL tests), and
Appendix C for detailed reproducible settings.

| Node classification | Link prediction | Graph classification
---|---|---|---
Cora | CiteSeer | ENZYMES | PROTEINS | MUTAG | PROTEINS
GCN | 0.864$\pm$0.019 | 0.713$\pm$0.012 | 0.657$\pm$0.004 | 0.613$\pm$0.023 | 0.837$\pm$0.027 | 0.704$\pm$0.008
SAGE | 0.858$\pm$0.016 | 0.728$\pm$0.031 | 0.643$\pm$0.003 | 0.658$\pm$0.002 | 0.842$\pm$0.050 | 0.714$\pm$0.042
GAT | 0.859$\pm$0.028 | 0.721$\pm$0.052 | 0.613$\pm$0.008 | 0.610$\pm$0.002 | 0.811$\pm$0.031 | 0.726$\pm$0.009
GIN | 0.854$\pm$0.019 | 0.716$\pm$0.018 | 0.663$\pm$0.006 | 0.614$\pm$0.015 | 0.847$\pm$0.087 | 0.718$\pm$0.012
F-GNN | OOM | OOM | 0.790$\pm$0.053 | 0.795$\pm$0.042 | 0.906$\pm$0.087 | 0.772$\pm$0.047
ID-GNN | 0.878$\pm$0.010 | 0.742$\pm$0.010 | 0.846$\pm$0.010 | 0.886$\pm$0.020 | 0.965$\pm$0.032 | 0.780$\pm$0.035
GraphSNN | 0.838$\pm$0.012 | 0.735$\pm$0.016 | - | - | 0.947$\pm$0.019 | 0.784$\pm$0.027
Laplacian PE | 0.869$\pm$0.027 | 0.733$\pm$0.036 | 0.713$\pm$0.052 | 0.722$\pm$0.069 | 0.855$\pm$0.097 | 0.735$\pm$0.044
EDEN+GCN | 0.873$\pm$0.023 | 0.748$\pm$0.013 | 0.869$\pm$0.001 | 0.879$\pm$0.001 | 0.926$\pm$0.031 | 0.781$\pm$0.014
EDEN+SAGE | 0.885$\pm$0.021 | 0.750$\pm$0.020 | 0.887$\pm$0.001 | 0.917$\pm$0.001 | 0.932$\pm$0.054 | 0.755$\pm$0.019
EDEN+GAT | 0.870$\pm$0.019 | 0.734$\pm$0.020 | 0.876$\pm$0.002 | 0.881$\pm$0.001 | 0.911$\pm$0.027 | 0.788$\pm$0.013
EDEN+GIN | 0.879$\pm$0.020 | 0.722$\pm$0.023 | 0.878$\pm$0.001 | 0.874$\pm$0.003 | 0.937$\pm$0.086 | 0.744$\pm$0.076
Table 2: Performance comparison. Bold denotes the highest score, italic
denotes the best performing baseline. Since GraphSNN is designed for node- and
edge-level tasks, we only report the best performance on them.

###  4.2 EDEN for Downstream Tasks

We conduct experiments on five real-world datasets, including two citation
networks of Cora and CiteSeer (Sen et al. 2008), two protein datasets of
ENZYMES (Borgwardt et al. 2005) with 600 graphs and PROTEINS (Schomburg et al.
2004) with 1113 graphs, and a chemical dataset of MUTAG (Morris et al. 2020)
with 188 graphs.

In addition to the baseline methods GCN, GAT, GIN and F-GNN used in section
4.1, we add conventional GNN of GraphSage (Hamilton, Ying, and Leskovec 2017),
recent advanced GNNs of ID-GNN (You et al. 2021), GraphSNN (Wijesinghe and
Wang 2021), and the state-of-the-art Laplacian PE (Dwivedi et al. 2020) as new
baselines. We apply a random 80/20% train/validation split, train all models
by the Adam optimizer (Kingma and Ba 2014) with the learning rate of 0.01,
repeat experiments with 10 random seeds and report the average results. Please
refer to Appendix D for more detailed settings.

Tab. 2 describes the results. We can observe that EDEN helps MPNNs to gain
universal improvements in all three tasks, and MPNNs with EDEN achieve state-
of-the-art performance compared with beyond-1-WL GNN counterparts on all
datasets except the MUTAG graph classification dataset. This is because the
graphs contained in MUTAG are very small, and there are only 17.93 nodes per
graph on average. EDEN’s global information becomes less useful for very small
graphs. Combining EDEN with the traditional MPNNs of GCN, GraphSAGE, GAT, and
GIN can bring promising improvements, especially on the link prediction task.
Note that F-GNN requires higher-order computations during inference and raises
the Out-Of-Memory (OOM) error. The performance of Laplacian PE (Dwivedi et al.
2020) has an obvious gap between EDEN in all tasks.

(a) EDEN indicates position

(b) 3D Laplacian

(c) 2D EDEN WITHOUT USING LABELS.

(d) 2D Laplacian

Figure 2: The expressive power of EDEN $\boldsymbol{F_{\hat{\boldsymbol{D}}}}$
and Laplacian PE on Zachary’s karate club network (Girvan and Newman 2002).
(a) EDEN as a Red-Green-Blue value to color each node. (b) Laplacian PE makes
most nodes have similar colors. (c) The 2D scatter of EDEN. Nodes are linearly
separable WITHOUT labels (red or blue). (d) The result of 2D Laplacian PE.

###  4.3 Ablation Study

(a) Laplacian $G$

(b) Laplacian $H$

(c) Laplacian $G^{\prime}$

(d) EDEN $G$

(e) EDEN $H$

(f) EDEN $G^{\prime}$

Figure 3: Ablation study on 1-WL equivalent graph pair.

#### Distance-based vs. Degree-based eigen-decomposition.

Since we introduce the length of the shortest-path between nodes as the global
information to enhance expressiveness and perform PCA to guarantee the
equivariance of EDEN, we call it distance-based eigen-decomposition. In this
section, we analyze and compare EDEN in depth with another close method, i.e.,
Laplacian PE, which relies on the eigen-decomposition on the Graph Laplacian
matrix $\boldsymbol{L}$. We call it degree-based eigen-decomposition since the
$\boldsymbol{L}$ only provides the degree information of nodes, which is
believed as a part of 1-WL’s expressiveness (Balcilar et al. 2021). As
described in Table 2, EDEN outperforms Laplacian PE by a large margin. We
conduct an in-depth analysis of Laplacian PE and find that it selects the
smallest eigenvalues for feature encoding after eigen-decomposition, which
leads to the problem of the over-smooth encoding of adjacent nodes (Dwivedi et
al. 2020). While the alternative way of selecting the largest eigenvalues
leads to the problem that few nodes with the highest degrees will be mapped
far away from the others (See Appendix E), we believe this situation makes
Laplacian PE less meaningful.

To support our insights, we further provide a visual comparison on real-world
datasets (Fig. 2) and 1-WL equivalent graph pairs (Fig. 3). In the real-world
case, we first compute the 3-dimensional EDEN and Laplacian PE, then use them
as the Red-Green-Blue values to color each node for an intuitive
visualization. Compared with EDEN’s coloring effect in Fig. 2(a), the
Laplacian PE in Fig. 2(b) colors most of the nodes with similar colors (purple
or gray), which indicates the over-smoothing problem as mentioned before.
Next, we draw 2-dimensional EDEN and Laplacian PE scatters for all nodes.
Nodes with the same labels are marked with the same color. Although the
positional encodings are computed without supervision (labels), EDEN in Fig.
2(c) maps nodes uniformly into the 2D Euclidean space and makes nodes linearly
separable according to their labels. The Laplacian PE in Fig. 2(d) cannot
achieve either.

Lastly, we choose a 1-WL equivalent graph pair, i.e., Decalin ($G$) and
Bicyclopentyl ($H$) graph to test graph isomorphism. Due to Lemma. 4, the
failure of graph isomorphism test lies in the inability to map isomorphic
graphs to the same results, rather than mapping non-isomorphic graphs to
different results. So we permute nodes in graph $G$ randomly to construct an
isomorphic graph $G^{\prime}$ and then color these three graphs with 3D
Laplacian PE and EDEN. As shown in Fig. 3, the Laplacian PE fails to maintain
deterministic outputs between $G$ and $G^{\prime}$ (_e.g.,_ there is a new
color yellow in $G^{\prime}$’s node of No.5). At the same time, the outputs of
EDEN are still deterministic. There is a one-to-one correspondence between the
nodes of EDEN in an isomorphic graph pair. More test examples are provided in
Appendix E. We find out that the Laplacian PE can neither go beyond 1-WL
expressiveness nor be as meaningful as EDEN.

Datasets | Baseline |  | Direct
---
Distance
| MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
Cora | 0.859 | 0.862 | 0.868 | 0.873 | 0.877
CiteSeer | 0.720 | 0.720 | 0.724 | 0.740 | 0.739
ENZYMES | 0.644 | 0.856 | 0.856 | 0.862 | 0.871
LPROTEINS | 0.624 | 0.795 | 0.871 | 0.880 | 0.888
MUTAG | 0.834 | 0.851 | 0.871 | 0.916 | 0.927
GPROTEINS | 0.716 | 0.721 | 0.752 | 0.752 | 0.767

Table 3: Ablation study on real-world datasets.

#### Cosine phase propagation

To investigate the effectiveness of cosine phase propagation, we use three
distance encoding schemes, namely, direct distance ($S_{1}$), Min-Max
normalized distance ($S_{2}$), and reversed Min-Max normalized distance
($S_{3}$), to replace the cosine phase propagation and compare their
performance.

$S_{1}$: Direct distance. First, we perform PCA directly on the distance
matrix $\boldsymbol{D}$ as an extra feature.

$\hat{\boldsymbol{D}}_{i,j}=\left\\{\begin{aligned}
&\boldsymbol{D}_{i,j},&\boldsymbol{D}_{i,j}\neq\infty\\\
&-1,&\boldsymbol{D}_{i,j}=\infty.\end{aligned}\right.$ (13)

Here we set the distance between a pair of unreachable nodes $v_{i}$ and
$v_{j}$ to -1.

$\boldsymbol{F}=\text{PCA}(\hat{\boldsymbol{D}}).$ (14)

In this case, the norm of $\boldsymbol{F}$ could be very large.

$S_{2}$: Min-Max normalized distance. Next, we perform the min-max
normalization on $D$ before we employ PCA,

$\hat{\boldsymbol{D}}_{i,j}=\left\\{\begin{aligned}
&\frac{\boldsymbol{D}_{i,j}-\min(\boldsymbol{D})}{\max(\boldsymbol{D})-\min(\boldsymbol{D})},&\boldsymbol{D}_{i,j}\neq\infty\\\
&-1,&\boldsymbol{D}_{i,j}=\infty.\end{aligned}\right.$ (15)

In this case, the values of all elements in $D$ range in [0,1], and larger
values indicate longer distances.

$S_{3}$: Reversed Min-Max normalized distance. Last, we transform
$\hat{\boldsymbol{D}}$ in the following way,

$\hat{\boldsymbol{D}}_{i,j}=\left\\{\begin{aligned}
&1-\frac{\boldsymbol{D}_{i,j}-\min(\boldsymbol{D})}{\max(\boldsymbol{D})-\min(\boldsymbol{D})},&\boldsymbol{D}_{i,j}\neq\infty\\\
&-1,&\boldsymbol{D}_{i,j}=\infty.\end{aligned}\right.$ (16)

This is similar to the second case, but the difference is that a larger value
of the element in $\hat{D}$ represents a shorter distance between two nodes.

We choose four MPNNs (GCN, SAGE, GAT, and GIN) and employ the above three
distance encoding schemes on real-world datasets. For a fair comparison, the
hyper-parameters are the same as EDEN. Results are shown in the Tab. 3
(“LPROTEINS” and “GPROTEINS” denote link-prediction and graph classification
tasks on the PROTEINS dataset, respectively). Note that the “Baseline” column
in Tab. 3 describes the average performance of MPNNs, and detailed
experimental results are provided in Appendix F.

It can be observed from Tab. 3 that EDEN achieves the best performance except
on the CiteSeer dataset. We analyze the possible reasons: (1) In $S_{1}$, the
values of some elements in unnormalized matrix $\boldsymbol{D}$ are large,
resulting in large norms of learned positional encoding vectors, which leads
to suboptimal results. (2) In $S_{1}$ and $S_{2}$, the value of
$\boldsymbol{\hat{D}}_{ij}$ is proportional to the distance (hops) between
node $v_{i}$ and $v_{j}$. But it cannot express the distance between two
unreachable nodes (_i.e.,_ the distance is defined as infinite), so we need an
opposite way of representing distance, _i.e.,_ use a smaller value to
represent a longer distance, and use -1 to represent the distance between
unreachable nodes. This means that $S_{1}$ and $S_{2}$ are less interpretable
for distance encoding. (3) $S_{3}$ is close to our proposed cosine phase
propagation, and it also has the property of normalization and
interpretability that makes it superior to $S_{1}$ and $S_{2}$. But $S_{3}$ is
still a linear transformation. Distance encoding using trigonometric functions
is considered to have better properties compared to linear mapping (Vaswani et
al. 2017).

###  4.4 Case study

We choose the Cospectral graph ($G$) and a 4-regular graph ($H$) as a 2-WL
equivalent pair for graph isomorphism test. As shown in Fig. 4, EDEN
distinguishes the non-isomorphism pair and keeps the isomorphism pair $G$ and
$G^{\prime}$ mapped to the same output. We provide a detailed analysis and
more permutation examples of $G^{\prime}$ in Appendix B. Fig. 5 illustrates
the result of employing EDEN on the real-world dataset of Cora (Sen et al.
2008). We find that the 2-dimensional EDEN is capable of providing semantic
information. The contours of different clusters according to node labels can
be observed via EDEN.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 4: EDEN on 2-WL equivalent graph pair. Figure 5: EDEN on Cora dataset
(Sen et al. 2008).

##  5 Related Works

Non-equivariant GNN Representing non-trivial position information for Non-
Euclidean structured data is still challenging. PGNN (You, Ying, and Leskovec
2019) tackles this problem via randomly selecting nodes as anchors and
aggregating anchors’ information to the target node, but a graph with $n$
nodes requires at least $O(\log^{2}n)$ anchors to guarantee the expressiveness
(Bourgain 1985). DE-GNN (Li et al. 2020) proves its expressive power in the
circumstance where parts of nodes’ representations in a graph are given, and
distance-based aggregation is applied to learn the remaining nodes’
representations. Nevertheless, these methods rely on selecting “anchors”,
which means they cannot be transferred to downstream tasks and do not have the
property of permutation-equivariance.

Higher-order GNN It is natural to design advanced GNNs by enhancing
expressiveness. F-GNN (Maron et al. 2019a) introduces the k-Folklore graph
isomorphism test to improve the expressive power. Recent work (Azizian and
Lelarge 2020) proves that F-GNN has the same expressiveness as KGNN (Maron et
al. 2019b). GNNML3 (Balcilar et al. 2021) ensures its expressiveness with the
Matrix Language theory. K-MPNNs (Geerts and Reutter 2022) analyses variants of
Higher-order GNNs (Morris et al. 2019) with Tensor Language. The above methods
have high computational complexity and are time-consuming during training.

Non-MPNNs Identity-aware GNNs (ID-GNNs) (You et al. 2021) are trained with ego
graph-based aggregation functions. One of its two variants, ID-GNN-full, can
work as a plug-in to the aggregation functions of existing MPNNs. The other of
its two variants, ID-GNN-fast, can be viewed as a kind of distance encoding.
But the disadvantages are that training ID-GNN-full is expensive because it
requires ego graphs on all nodes, while ID-GNN-fast tends to have low
prediction accuracy. Similar to EDEN, GraphSNN (Wijesinghe and Wang 2021)
builds a new perspective on the graph isomorphism test. It reconstructs the
aggregation function with overlapping subgraphs, resulting in a lower
computational complexity than other higher-order methods. It works well on
graph-level tasks but is not good at local-view tasks such as node
classification. Local Relation Pooling (LPR) (Chen et al. 2020) is a universal
approximator for permutation-invariant functions based on local subgraph
counts. Natural GNN (de Haan, Cohen, and Welling 2020) passes messages with
kernels that depend on the local graph structure.

Plug-in encodings It’s practical to employ matrix decomposition to obtain
Positional Encodings (PE), such as the Graph Transformer (Dwivedi and Bresson
2020) . The Laplacian PE (Dwivedi et al. 2020) is a representative eigen-
decomposition-based method. But Laplacian PE cannot help the model achieve
expressive power beyond the 1-WL and has less semantic information in real-
world datasets. More details can be found in Appendix E. It is also worth
mentioning that all eigenvalue decomposition-based methods have a time
complexity of at least $O(n^{3})$.

##  6 Conclusion

This paper presents a new distance encoding method called EDEN. We
theoretically prove that EDEN has the property of permutation-equivariance,
which is unavailable for existing plug-in encoding methods for GNN. We
demonstrate EDEN’s powerful expressiveness beyond the 1-WL test and its
superiority in dealing with real-world graphs. EDEN can be employed as a plug-
in extension to existing MPNNs. The experimental results show that EDEN can
improve the performance of conventional MPNNs to the state-of-the-art level in
node-, edge-, and graph-level tasks. Meanwhile, the time complexity of
obtaining the distance matrix is still high, and employing PCA is less
efficient. In future work, we will focus on how to reduce the computational
complexity of EDEN.

## References

  * Abboud et al. (2021) Abboud, R.; Ceylan, I. I.; Grohe, M.; and Lukasiewicz, T. 2021.  The Surprising Power of Graph Neural Networks with Random Node Initialization.  _ArXiv_ , abs/2010.01179.
  * Arvind et al. (2020) Arvind, V.; Fuhlbruck, F.; Kobler, J.; and Verbitsky, O. 2020.  On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.  _J. Comput. Syst. Sci._ , 113: 42–59.
  * Azizian and Lelarge (2020) Azizian, W.; and Lelarge, M. 2020.  Expressive power of invariant and equivariant graph neural networks.  _arXiv preprint arXiv:2006.15646_.
  * Azizian and Lelarge (2021) Azizian, W.; and Lelarge, M. 2021.  Expressive Power of Invariant and Equivariant Graph Neural Networks.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Balcilar et al. (2021) Balcilar, M.; Héroux, P.; Gaüzère, B.; Vasseur, P.; Adam, S.; and Honeine, P. 2021.  Breaking the Limits of Message Passing Graph Neural Networks.  In _ICML_.
  * Borgwardt et al. (2005) Borgwardt, K. M.; Ong, C. S.; Schonauer, S.; Vishwanathan, S.; Smola, A. J.; and Kriegel, H.-P. 2005.  Protein function prediction via graph kernels.  _Bioinformatics_ , 21(suppl1): i47–i56.
  * Bourgain (1985) Bourgain, J. 1985.  On Lipschitz embedding of finite metric spaces in Hilbert space.  _ISR J MATH_ , 52(1-2): 46–52.
  * Chen et al. (2020) Chen, Z.; Chen, L.; Villar, S.; and Bruna, J. 2020.  Can Graph Neural Networks Count Substructures?  In _NeurIPS_.
  * de Haan, Cohen, and Welling (2020) de Haan, P.; Cohen, T. S.; and Welling, M. 2020.  Natural Graph Networks.  In _NeurIPS_.
  * Defferrard, Bresson, and Vandergheynst (2016) Defferrard, M.; Bresson, X.; and Vandergheynst, P. 2016.  Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.  In Lee, D. D.; Sugiyama, M.; von Luxburg, U.; Guyon, I.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain_ , 3837–3845.
  * Dijkstra (1959) Dijkstra, E. W. 1959.  A note on two problems in connexion with graphs.  _NUMER MATH_ , 1: 269–271.
  * Dwivedi and Bresson (2020) Dwivedi, V. P.; and Bresson, X. 2020.  A Generalization of Transformer Networks to Graphs.  _CoRR_ , abs/2012.09699.
  * Dwivedi et al. (2020) Dwivedi, V. P.; Joshi, C. K.; Laurent, T.; Bengio, Y.; and Bresson, X. 2020.  Benchmarking Graph Neural Networks.  _CoRR_ , abs/2003.00982.
  * Fan et al. (2019) Fan, W.; Ma, Y.; Li, Q.; He, Y.; Zhao, E.; Tang, J.; and Yin, D. 2019.  Graph neural networks for social recommendation.  In _The world wide web conference_ , 417–426.
  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Geerts and Reutter (2022) Geerts, F.; and Reutter, J. L. 2022.  Expressiveness and Approximation Properties of Graph Neural Networks.  _CoRR_ , abs/2204.04661.
  * Gilmer et al. (2017) Gilmer, J.; Schoenholz, S. S.; Riley, P. F.; Vinyals, O.; and Dahl, G. E. 2017.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , 1263–1272. PMLR.
  * Girvan and Newman (2002) Girvan, M.; and Newman, M. E. 2002.  Community structure in social and biological networks.  _P NATL ACAD SCI_ , 99(12): 7821–7826.
  * Godsil and Royle (2001) Godsil, C.; and Royle, G. F. 2001.  _Algebraic graph theory_ , volume 207.  Springer Science and Business Media.
  * Hamilton, Ying, and Leskovec (2017) Hamilton, W.; Ying, Z.; and Leskovec, J. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30.
  * Hefferon (2008) Hefferon, J. 2008.  _Linear algebra_.  Open Access.
  * Huang and Villar (2021) Huang, N. T.; and Villar, S. 2021.  A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 8533–8537. IEEE.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _ICLR (Poster)_.
  * Li et al. (2020) Li, P.; Wang, Y.; Wang, H.; and Leskovec, J. 2020.  Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning.  In _NeurIPS_.
  * Marinka Zitnik and Leskovec (2018) Marinka Zitnik, S. M., Rok Sosivc; and Leskovec, J. 2018.  BioSNAP Datasets: Stanford Biomedical Network Dataset Collection.  http://snap.stanford.edu/biodata.
  * Maron et al. (2019a) Maron, H.; Ben-Hamu, H.; Serviansky, H.; and Lipman, Y. 2019a.  Provably Powerful Graph Networks.  In Wallach, H. M.; Larochelle, H.; Beygelzimer, A.; d’Alché-Buc, F.; Fox, E. B.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2153–2164.
  * Maron et al. (2019b) Maron, H.; Ben-Hamu, H.; Shamir, N.; and Lipman, Y. 2019b.  Invariant and Equivariant Graph Networks.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.
  * Morris et al. (2020) Morris, C.; Kriege, N. M.; Bause, F.; Kersting, K.; Mutzel, P.; and Neumann, M. 2020\.  Tudataset: A collection of benchmark datasets for learning with graphs.  _arXiv preprint arXiv:2007.08663_.
  * Morris et al. (2019) Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W. L.; Lenssen, J. E.; Rattan, G.; and Grohe, M. 2019.  Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.  In _AAAI_ , 4602–4609. AAAI Press.
  * Schomburg et al. (2004) Schomburg, I.; Chang, A.; Ebeling, C.; Gremse, M.; Heldt, C.; Huhn, G.; and Schomburg, D. 2004.  BRENDA, the enzyme database: updates and major new developments.  _Nucleic acids research_ , 32(supp1): D431–D433.
  * Sen et al. (2008) Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; and Eliassi-Rad, T. 2008\.  Collective classification in network data.  _AI magazine_ , 29(3): 93–93.
  * Tang et al. (2009) Tang, J.; Sun, J.; Wang, C.; and Yang, Z. 2009.  Social influence analysis in large-scale networks.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 807–816.
  * van Dam and Haemers (2003) van Dam, E. R.; and Haemers, W. H. 2003.  Which graphs are determined by their spectrum.  _Linear Algebra and its Applications_ , 373: 241–272.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention is All you Need.  In _NIPS_ , 5998–6008.
  * Velickovic et al. (2018) Velickovic, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; and Bengio, Y. 2018.  Graph Attention Networks.  In _ICLR (Poster)_.
  * Wijesinghe and Wang (2021) Wijesinghe, A.; and Wang, Q. 2021.  A New Perspective on How Graph Neural Networks Go Beyond Weisfeiler-Lehman?  In _International Conference on Learning Representations_.
  * Wold, Esbensen, and Geladi (1987) Wold, S.; Esbensen, K.; and Geladi, P. 1987.  Principal component analysis.  _CHEMOMETR INTELL LAB_ , 2(1-3): 37–52.
  * Xu et al. (2019) Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. 2019.  How Powerful are Graph Neural Networks?  In _ICLR_.
  * You et al. (2021) You, J.; Gomes-Selman, J. M.; Ying, R.; and Leskovec, J. 2021.  Identity-aware Graph Neural Networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 10737–10745.
  * You, Ying, and Leskovec (2019) You, J.; Ying, R.; and Leskovec, J. 2019.  Position-aware Graph Neural Networks.  In _ICML_ , volume 97, 7134–7143.
  * You, Ying, and Leskovec (2020) You, J.; Ying, R.; and Leskovec, J. 2020.  Design Space for Graph Neural Networks.  In _NeurIPS_.
  * Zhou et al. (2020) Zhou, J.; Cui, G.; Hu, S.; Zhang, Z.; Yang, C.; Liu, Z.; Wang, L.; Li, C.; and Sun, M. 2020.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1: 57–81.

##  Appendix A The Algorithm

The pseudo-code of EDEN is summarized as Algorithm 1. We implement our code in
Python. The “ _zeros_ ” and “ _nanmax_ ” are functions in
NumPy333https://github.com/numpy/numpy, the former assigns elements to zero,
and the latter obtains the maximum number while ignoring NaN (Not a Number) in
Python. The _Dijkstra algorithm_ is implemented by
NetworkX444https://github.com/networkx/networkx, and “PCA” is called from the
Scikit-learn555https://github.com/scikit-learn/scikit-learn package. We
provide core python codes.

[t] from sklearn.decomposition import PCA import networkx as nx import numpy
as np

def graph_to_eden(G, k=3): Distance = dict(
nx.all_pairs_shortest_path_length(G) ) num_node = len(G) D =
np.zeros([num_node, num_node]) for i in range(num_node): for j in
range(num_node): D[i,j] = Distance[i][j] PCA1 = PCA(n_components=k) COS_D =
np.cos(np.pi * D /… np.nanmax(D, axis=1, keepdims=True))
COS_D[np.isnan(cos_dis)]=-1.5 EDEN = PCA1.fit_transform(COS_D) return EDEN

Input: The adjacency matrix $\boldsymbol{A}$, dimension $k$, the number of
nodes $N$

Output: Eden’s matrix $\boldsymbol{F_{\hat{\boldsymbol{D}}}}$

$\boldsymbol{D}$ = _Dijkstra_($\boldsymbol{A}$); // Employ _Dijkstra
algorithm_ to obtain the distance matrix

$\boldsymbol{d}$ = _zeros_($[N,1]$);// Initialize the diameter vector
$\boldsymbol{d}$

$\hat{\boldsymbol{D}}$ = _zeros_($[N,N]$);// Initialize the phase propagation
matrix $\hat{\boldsymbol{D}}$

for  _$i=1,2,\cdots,N$ // Perform phase propagation in Eq.(3) _

1 do

2 $d_{i}=\text{\emph{nanmax}}(\boldsymbol{D_{i,:})}$;

3

4 for  _$j=1,2,\cdots,N$ _ do

5 if  _$\boldsymbol{D}_{i,j}\neq\text{NaN}$_ then

6
$\hat{\boldsymbol{D}}_{i,j}=\cos{(\frac{\pi\times\boldsymbol{D}_{i,j}}{d_{i}})}$;

7

8 else

9 $\hat{\boldsymbol{D}}_{i,j}=-1.5$

10 end if

11

12 end for

13

14 end for

$\boldsymbol{F_{\hat{\boldsymbol{D}}}}=$PCA($\hat{\boldsymbol{D}}$, $k$); //
Perform $k$ dimensional PCA in Eq.(4)

return $\boldsymbol{F_{\hat{\boldsymbol{D}}}}$

Algorithm 1 Equivariant distance encoding

##  Appendix B EDEN on Different Graph Pairs

We plot the result of a 4-regular graph isomorphism test in Figure 1. In this
part, we describe the computational details and show more examples with
different equivalent levels, where the $k$-WL equivalent means non-less than
the $k+1$-WL test can distinguish them (Balcilar et al. 2021).

###  B.1 Computational details

Considering two graphs $G$ and $H$ with adjacency matrices $A_{G}$ and
$A_{H}$, respectively. We apply Algorithm 1 to compute the 3-dimensional EDENs
for these graphs:

$\displaystyle\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G}=\text{EDEN}(\boldsymbol{A}_{G},3)$
, (17)
$\displaystyle\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H}=\text{EDEN}(\boldsymbol{A}_{H},3)$
,

where $\text{EDEN}(\cdot,3)$ denotes getting the 3-dimensional EDENs in
Algorithm 1. Then the computed EDENs are normalized within $[0,1]$ :

$\displaystyle\boldsymbol{F_{\hat{\boldsymbol{D}}}}^{\prime}_{G}=\frac{\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G}-\min(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G})}{\max(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G})-\min(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G})},$
(18)
$\displaystyle\boldsymbol{F_{\hat{\boldsymbol{D}}}}^{\prime}_{H}=\frac{\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H}-\min(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H})}{\max(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H})-\min(\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H})}$
,

where min($\cdot$) and max($\cdot$) denote the minimum and maximum values in
each row, respectively. We obtain the graph $G^{\prime}$ by a random
permutation $\sigma$ on graph $G$,

$G^{\prime}=\sigma\star G.$ (19)

Similarly, the normalized EDEN
$\boldsymbol{F_{\hat{\boldsymbol{D}}}}^{\prime}_{G^{\prime}}$ can be computed
by Eq. (17) and Eq. (18). We plot $G,H$, and $G^{\prime}$ with the same
layout, which means nodes with the same ID will have their specific positions
in different graphs. To facilitate visualization, we treat the 3-dimensional
EDEN as the Red-Green-Blue (RGB) brightness to color each node. We expect
nodes in isomorphic graph pairs (i.e., $G$ and $G^{\prime}$) to have same
colors but with different IDs, and the neighbor relationship of nodes with
different colors remain unchanged. For example, if a green node in graph $G$
is connected with an orange node and an aqua blue node, the green node in
graph $G^{\prime}$ should also be connected with an orange node and an aqua
blue node. There is no such correspondence between the colors of nodes in non-
isomorphic graph pairs, (_e.g.,_ $G$ and $H$). We provide more visual examples
of graph pairs that can show the expressive power of EDEN.

###  B.2 1-WL equivalent graphs

There are three graphs in Fig. 6, Decalin ($G$), Bicyclopentyl ($H$), and
randomly permuted Decalin ($G^{\prime}$). $G$ and $H$ are 1-WL equivalent
graph pairs and the adjacency matrices $\boldsymbol{A}_{G}$ and
$\boldsymbol{A}_{H}$ are written as:

$A_{G}=\left(\begin{array}[]{llllllllll}0&1&1&0&0&0&1&0&0&0\\\
1&0&0&0&0&1&0&0&0&1\\\ 1&0&0&1&0&0&0&0&0&0\\\ 0&0&1&0&1&0&0&0&0&0\\\
0&0&0&1&0&1&0&0&0&0\\\ 0&1&0&0&1&0&0&0&0&0\\\ 1&0&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&1&0&1&0\\\ 0&0&0&0&0&0&0&1&0&1\\\
0&1&0&0&0&0&0&0&1&0\end{array}\right),$
$A_{H}=\left(\begin{array}[]{llllllllll}0&1&1&0&0&1&0&0&0&0\\\
1&0&0&0&0&0&1&0&0&1\\\ 1&0&0&1&0&0&0&0&0&0\\\ 0&0&1&0&1&0&0&0&0&0\\\
0&0&0&1&0&1&0&0&0&0\\\ 1&0&0&0&1&0&0&0&0&0\\\ 0&1&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&1&0&1&0\\\ 0&0&0&0&0&0&0&1&0&1\\\
0&1&0&0&0&0&0&0&1&0\end{array}\right).$

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 6: Decalin and Bicyclopentyl graphs are 1-WL equivalent (Balcilar et
al. 2021).

###  B.3 2-WL equivalent graphs

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 7: Cospectral and 4-regular graphs are 2-WL equivalent (van Dam and
Haemers 2003).

Fig. 7 shows non-isomorphic 2-WL equivalent graphs Cospectral ($G$) and
4-regular graph ($H$) from (van Dam and Haemers 2003). The adjacency matrices
$\boldsymbol{A}_{G}$ and $\boldsymbol{A}_{H}$ can be written as:

$A_{G}=\left(\begin{array}[]{llllllllll}0&1&0&1&0&1&0&1&0&0\\\
1&0&1&1&1&0&0&0&0&0\\\ 0&1&0&0&1&0&1&0&0&1\\\ 1&1&0&0&0&1&0&1&0&0\\\
0&1&1&0&0&0&1&0&0&1\\\ 1&0&0&1&0&0&0&0&1&1\\\ 0&0&1&0&1&0&0&1&1&0\\\
1&0&0&1&0&0&1&0&1&0\\\ 0&0&0&0&0&1&1&1&0&1\\\
0&0&1&0&1&1&0&0&1&0\end{array}\right),$
$A_{H}=\left(\begin{array}[]{llllllllll}0&1&0&1&0&0&1&1&0&0\\\
1&0&1&1&1&0&0&0&0&0\\\ 0&1&0&0&1&1&0&0&0&1\\\ 1&1&0&0&0&1&0&1&0&0\\\
0&1&1&0&0&0&1&0&0&1\\\ 0&0&1&1&0&0&0&1&1&0\\\ 1&0&0&0&1&0&0&0&1&1\\\
1&0&0&1&0&1&0&0&1&0\\\ 0&0&0&0&0&1&1&1&0&1\\\
0&0&1&0&1&0&1&0&1&0\end{array}\right).$

We also plot EDENs for $G$ and $H$, and randomly permute nodes in $G$ to get
$G^{\prime}$. EDEN can distinguish non-isomorphic graphs under the premise
that isomorphic graphs have same color layout, Up to 2-WL Equivalent.

###  B.4 3-WL equivalent graphs

We propose the fail example of our EDEN on strongly regular graphs, which are
3-WL equivalent in Fig. 8.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 8: The failure case on strongly regular graph pair. 4 $\times$ 4-rook’s
graph and the Shrikhande graph are 3-WL equivalent (Arvind et al. 2020).

Although EDEN has different color layouts on the two non-isomorphic graphs
($G$ and $H$), the color layouts on the isomorphic graphs ($G$ and
$G^{\prime}$) are also different. This is because EDEN is very different from
other algorithms for the graph isomorphism test, _i.e.,_ EDEN may map
isomorphic strongly regular graphs to different results. In this case, the
adjacency matrices $A_{G}$ and $A_{H}$ are as follows,

$A_{G}=$

${\left(\begin{array}[]{llllllllllllllll}0&1&1&1&1&0&0&0&1&0&0&0&1&0&0&0\\\
1&0&1&1&0&1&0&0&0&1&0&0&0&1&0&0\\\ 1&1&0&1&0&0&1&0&0&0&1&0&0&0&1&0\\\
1&1&1&0&0&0&0&1&0&0&0&1&0&0&0&1\\\ 1&0&0&0&0&1&1&1&1&0&0&0&1&0&0&0\\\
0&1&0&0&1&0&1&1&0&1&0&0&0&1&0&0\\\ 0&0&1&0&1&1&0&1&0&0&1&0&0&0&1&0\\\
0&0&0&1&1&1&1&0&0&0&0&1&0&0&0&1\\\ 1&0&0&0&1&0&0&0&0&1&1&1&1&0&0&0\\\
0&1&0&0&0&1&0&0&1&0&1&1&0&1&0&0\\\ 0&0&1&0&0&0&1&0&1&1&0&1&0&0&1&0\\\
0&0&0&1&0&0&0&1&1&1&1&0&0&0&0&1\\\ 1&0&0&0&1&0&0&0&1&0&0&0&0&1&1&1\\\
0&1&0&0&0&1&0&0&0&1&0&0&1&0&1&1\\\ 0&0&1&0&0&0&1&0&0&0&1&0&1&1&0&1\\\
0&0&0&1&0&0&0&1&0&0&0&1&1&1&1&0\end{array}\right),}$

$A_{H}=$

${\left(\begin{array}[]{llllllllllllllll}0&1&0&1&1&1&0&0&0&0&0&0&1&0&0&1\\\
1&0&1&0&0&1&1&0&0&0&0&0&1&1&0&0\\\ 0&1&0&1&0&0&1&1&0&0&0&0&0&1&1&0\\\
1&0&1&0&1&0&0&1&0&0&0&0&0&0&1&1\\\ 1&0&0&1&0&1&0&1&1&1&0&0&0&0&0&0\\\
1&1&0&0&1&0&1&0&0&1&1&0&0&0&0&0\\\ 0&1&1&0&0&1&0&1&0&0&1&1&0&0&0&0\\\
0&0&1&1&1&0&1&0&1&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&1&0&1&0&1&1&1&0&0\\\
0&0&0&0&1&1&0&0&1&0&1&0&0&1&1&0\\\ 0&0&0&0&0&1&1&0&0&1&0&1&0&0&1&1\\\
0&0&0&0&0&0&1&1&1&0&1&0&1&0&0&1\\\ 1&1&0&0&0&0&0&0&1&0&0&1&0&1&0&1\\\
0&1&1&0&0&0&0&0&1&1&0&0&1&0&1&0\\\ 0&0&1&1&0&0&0&0&0&1&1&0&0&1&0&1\\\
1&0&0&1&0&0&0&0&0&0&1&1&1&0&1&0\end{array}\right).}$

###  B.5 Analysis on the above three cases

The multiple roots of singular values may cause EDEN to fail on strongly
regular graphs. We compute the three largest singular values of
$\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{G}$ and
$\boldsymbol{F_{\hat{\boldsymbol{D}}}}_{H}$ for each case:

  * •

1-WL equivalent: [4.9790, 3.5061, 2.1254], [6.2486, 2.0653, 1.3309],

  * •

2-WL equivalent: [4.2360, 3.5615, 3. ], [4.2360, 3.5615, 3. ],

  * •

3-WL equivalent: [4., 4., 4.], [4., 4., 4.].

Based on the above results, we have the following analysis. In the first case,
EDENs of non-isomorphic graphs have different singular values. It is easy to
judge that $G$ and $H$ are non-isomorphic. In the second case, although
4-regular graphs $G$ and $H$ share the same singular values, we can also
distinguish them from EDEN. It indicates that EDEN is more expressive than
using singular values as a graph readout. While for the last case, we find
that the largest three singular values of both strongly regular graphs are
equal to 4. As described in Eq. (8), PCA performs eigendecomposition of the
original matrix, the columns of the eigenvector matrix $\boldsymbol{V}$ can
theoretically be sorted according to eigenvalues from largest to smallest. The
two strong regular graphs in the last case have multiple identical eigenvalues
at the same time. Therefore, the order of eigenvectors in $\boldsymbol{V}$ has
randomness in the process of numerical calculation, which eventually leads to
inconsistent results of the model.

##  Appendix C Graph Isomorphic Test

Baseline methods utilize nodes’ degrees as input features, which is considered
the output of executing a 1-WL Test iteration (Balcilar et al. 2021). But
ENDEN obtains $k$-dimensional singular vectors after PCA, and isomorphic
graphs may be projected to different embeddings because of the inevitable
numerical precision caused by PCA. Due to EDEN’s nature, it is necessary to
adjust the judgment threshold for EDEN. We propose strict judgment conditions
for graph isomorphism. To be specific, we randomly generate isomorphic graphs
for each dataset, and apply EDEN to judge whether the graph pairs are non-
isomorphic under the premise that the known isomorphic pairs graphs are judged
correctly.

##  Appendix D Experiments on Real-World Datasets

###  D.1 Experimental environments

We implement codes with Python 3.7, PyTorch 1.8.0, and Cuda 11.3. Experiments
are run on an Ubuntu 16.04 LTS server with the Intel i7-6900K CPU and four
NVIDIA 1080 Ti GPUs.

###  D.2 Hyper-parameters

##### Determine hyper-parameters

We use a consistent data split strategy (_i.e.,_ 80/20% train/validation
split), and set the batch size to 128 and the learning rate to 0.01 for all
methods. We use Adam as the optimizer, ReLU as the activation function, and
MLP as the readout function. The number of layers is set to 5 for the link
prediction task and 3 for other tasks. We use a grid search strategy to tune
the embedding size of EDEN in $[2,3,\cdots,10]$.

The optimal embedding sizes of baseline methods on test datasets are as
follows:

  * •

Cora: 32 for all MPNNs (i.e., GCN, GraphSAGE, GAT and GIN).

  * •

CiteSeer: 32 for all MPNNs.

  * •

ENZYMES: 128 for GraphSAGE, 256 for the other MPNNs.

  * •

PROTEINS (link prediction): 128 for all MPNNs.

  * •

MUTAG: 256 for all MPNNs.

  * •

PROTEINS (graph classification): 128 for all MPNNs.

###  D.3 Fair comparison

We implement EDEN with Pytorch-Geometric (Fey and Lenssen 2019) and GraphGym
(You, Ying, and Leskovec 2020). For a fair comparison, we use the official
code of ID-GNN (You et al. 2021) and manually fine-tune the hyper-parameter of
feature dimension to achieve close accuracy reported by ID-GNN, because ID-GNN
does not specify it in the original article. We re-implement the baselines in
IDGNN’s, and the maximum accuracy difference is less than $\pm 0.01$. In
addition, we choose the best results reported in related works. When
implementing Laplacian PE (Dwivedi et al. 2020), we keep the same settings as
EDEN. Moreover, we choose the best results among the four GNN backbones.

Task-specific settings. We adjust settings due to the different nature of
tasks. The MPNNs have three massage-passing layers for node and graph
classification tasks, and they report the validation accuracy after 100
epochs. The graph classification task needs an additional MLP for the readout
operation. We train models with five message-passing layers for the link
prediction task, and report the ROC-AUC. The dimensions of EDEN and Laplacian
PE are set to 8 for Cora and CiteSeer datasets, and 3 for other datasets.

##  Appendix E Limitations of Laplacian PE

###  E.1 Laplacian PE can’t go beyond 1-WL

We perform similar visual results of other cases with Laplacian PE. As
illustrated in Fig 9 to 12, Laplacian PE fails in ALL cases, no matter how
powerful the WL equivalence is. Especially for Fig. 10(a) and Fig. 10(c), just
two nodes swapped (#6 and #7) in a 1-WL equivalent graph pair will result in
great changes. These failures behave the same as EDEN fails on the 3-WL
equivalent example, because the eigenvalues of the Laplacian matrix have
multiple roots. In essence, this means that the information contained in the
Laplace matrix cannot exceed the 1-WL test.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 9: Graph Laplacian failed to be deterministic in the case of regular
graphs pair in Fig 1.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 10: Graph Laplacian failed to be deterministic in the case of 1-WL
equivalent Decalin and Bicyclopentyl graphs.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 11: Graph Laplacian failed to be deterministic in the case of 2-WL
equivalent Cospectral and 4-regular graphs.

(a) $G$

(b) $H$

(c) $G^{\prime}$

Figure 12: Graph Laplacian failed to be deterministic in the case of 3-WL
equivalent strong-regular graphs.

###  E.2 Laplacian PEs are less meaningful in real-world graphs

We plot Laplacian PE on real-word datasets in Fig. 13 in the same way as Fig.
2. The layout of the nodes is somewhat different, but their IDs remain the
same. We find that EDEN has more uniform and rich colors on the real-world
dataset. It shows that EDEN maps nodes more evenly to a board Euclidean space.
Nevertheless, the existing Laplace PEs, as shown in Fig. 13(b), are drabber in
color (primarily gray or purple), which means that Laplacian PE maps most of
the nodes into a small part of the Euclidean space. In addition, we take the
decomposition results corresponding to the largest eigenvalues like EDEN. At
this time, only the points with highest degrees have bright colors, and the
colors of other nodes are almost indistinguishable (See Fig. 13(c)). It is
worth mentioning that all positional encodings are equally normalized to
convert to RGB brightness. We visualize the 2D EDEN and Laplacian PEs in Fig.
14 without node labels. It can be observed that the results of EDEN are
linearly separable according to actual node labels, but the Laplacian PE using
minimal or maximal eigenvalues map all the nodes to a a small range in the
Euclidean space. In summary, the Laplace’s PE is less meaningful than EDEN in
real-world graphs.

(a) EDEN

(b) Minimal non-trivial eigenvalues

(c) Maximal non-trivial eigenvalues

Figure 13: Graph Laplacian based Position Encodings are too smoothing in real-
world graphs.

(a) 2D EDEN WITHOUT USING LABELS.

(b) 2D Laplacian PE with Minimal non-trivial eigenvalues

(c) 2D Laplacian PE with Maximal eigenvalues

Figure 14: Graph Laplacian based Position Encodings are less meaningful in real-world graphs.  Cora | Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.864$\pm$0.019 | 0.869$\pm$0.021 | 0.866$\pm$0.020 | 0.879$\pm$0.019 | 0.873$\pm$0.023
GraphSAGE | 0.858$\pm$0.016 | 0.862$\pm$0.010 | 0.874$\pm$0.008 | 0.875$\pm$0.015 | 0.885$\pm$0.021
GAT | 0.859$\pm$0.028 |  0.855$\pm$0.013 | 0.863$\pm$0.009 | 0.863$\pm$0.009 | 0.870$\pm$0.019
GIN | 0.854$\pm$0.019 | 0.863$\pm$0.016 | 0.867$\pm$0.008 | 0.874$\pm$0.017 | 0.879$\pm$0.020
Average | 0.859 | 0.862 | 0.868 | 0.873 | 0.877
Table 4: Ablation study on Cora dataset, where the underline denotes “being even lower than the baseline” and the bold means the best performance for a given MPNN (or the average of four MPNNs). CiteSeer | Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.713$\pm$0.012 | 0.717$\pm$0.010 | 0.722$\pm$0.020 | 0.743$\pm$0.006 | 0.748$\pm$0.013
GraphSAGE | 0.728$\pm$0.031 | 0.736$\pm$0.012 | 0.736$\pm$0.008 | 0.742$\pm$0.001 | 0.750$\pm$0.020
GAT | 0.721$\pm$0.052 |  0.719$\pm$0.011 | 0.721$\pm$0.009 | 0.733$\pm$0.008 | 0.734$\pm$0.020
GIN | 0.716$\pm$0.018 |  0.709$\pm$0.007 | 0.718$\pm$0.007 | 0.729$\pm$0.009 | 0.722$\pm$0.023
Average | 0.720 | 0.720 | 0.724 | 0.740 | 0.739
Table 5: Ablation study on CiteSeer dataset, where the underline denotes “being even lower than the baseline” and the bold means the best performance for a given MPNN (or the average of four MPNNs). ENZYMES | Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.657$\pm$0.004 | 0.834$\pm$0.004 | 0.852$\pm$0.007 | 0.862$\pm$0.004 | 0.869$\pm$0.001
GraphSAGE | 0.643$\pm$0.003 | 0.871$\pm$0.013 | 0.871$\pm$0.004 | 0.880$\pm$0.002 | 0.887$\pm$0.002
GAT | 0.613$\pm$0.008 | 0.862$\pm$0.009 | 0.868$\pm$0.004 | 0.868$\pm$0.004 | 0.876$\pm$0.002
GIN | 0.663$\pm$0.006 | 0.857$\pm$0.004 | 0.855$\pm$0.002 | 0.871$\pm$0.005 | 0.878$\pm$0.001
Average | 0.644 | 0.856 | 0.862 | 0.871 | 0.878
Table 6: Ablation study on ENZYMES dataset, where the underline denotes “being even lower than the baseline” and the bold means the best performance for a given MPNN (or the average of four MPNNs). | PROTEINS
---
Edge
Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.613$\pm$0.023 | 0.817$\pm$0.149 | 0.873$\pm$0.028 | 0.876$\pm$0.003 | 0.879$\pm$0.001
GraphSAGE | 0.658$\pm$0.002 | 0.790$\pm$0.172 | 0.882$\pm$0.003 | 0.884$\pm$0.003 | 0.917$\pm$0.001
GAT | 0.610$\pm$0.002 | 0.783$\pm$0.179 | 0.876$\pm$0.003 | 0.886$\pm$0.004 | 0.881$\pm$0.001
GIN | 0.614$\pm$0.015 | 0.791$\pm$0.004 | 0.853$\pm$0.004 | 0.872$\pm$0.003 | 0.874$\pm$0.003
Average | 0.624 | 0.795 | 0.871 | 0.880 | 0.888
Table 7: Ablation study on PROTEINS dataset (link prediction task), where the underline denotes “being even lower than the baseline” and the bold means the best performance for a given MPNN (or the average of four MPNNs). MUTAG | Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.837$\pm$0.027 | 0.855$\pm$0.149 | 0.873$\pm$0.028 | 0.911$\pm$0.003 | 0.926$\pm$0.031
GraphSAGE | 0.842$\pm$0.050 | 0.845$\pm$0.172 | 0.882$\pm$0.003 | 0.928$\pm$0.078 | 0.932$\pm$0.054
GAT | 0.811$\pm$0.031 | 0.837$\pm$0.179 | 0.876$\pm$0.003 | 0.911$\pm$0.051 | 0.911$\pm$0.027
GIN | 0.847$\pm$0.087 | 0.866$\pm$0.028 | 0.853$\pm$0.004 | 0.915$\pm$0.055 | 0.937$\pm$0.086
Average | 0.834 | 0.851 | 0.871 | 0.916 | 0.927
Table 8: Ablation study on MUTAG dataset, where the underline denotes “being even lower than the baseline” and the bold means the best performance for given MPNN (or the average of four MPNNs). | PROTEINS
---
Graph
Baseline | Distance |  | MinMax
---
Distance
| R-MinMax
---
Distance
EDEN
GCN | 0.704$\pm$0.008 | 0.718$\pm$0.043 | 0.776$\pm$0.018 | 0.786$\pm$0.041 | 0.781$\pm$0.014
GraphSAGE | 0.714$\pm$0.042 | 0.721$\pm$0.009 | 0.739$\pm$0.171 | 0.723$\pm$0.050 | 0.755$\pm$0.019
GAT | 0.726$\pm$0.009 |  0.723$\pm$0.009 | 0.757$\pm$0.022 | 0.775$\pm$0.011 | 0.788$\pm$0.013
GIN | 0.718$\pm$0.012 | 0.720$\pm$0.018 | 0.735$\pm$0.012 | 0.723$\pm$0.024 | 0.744$\pm$0.076
Average | 0.716 | 0.721 | 0.752 | 0.752 | 0.767
Table 9: Ablation study on PROTEINS dataset (graph classification task), where
the underline denotes “being even lower than the baseline” and the bold means
the best performance for a given MPNN (or the average of four MPNNs).

##  Appendix F The Advantages of Cosine Phase Propagation

EDEN is inspired by the sinusoidal positional encoding in Transformer (Vaswani
et al. 2017) and distance-based GNNs (Li et al. 2020; You, Ying, and Leskovec
2019). Transformer states that a set of trigonometric functions can directly
characterize positions. The distance-based GNNs show that the distance can
measure the relationship between two nodes, and the strength of the
relationship should be inversely related to the distance. Therefore, the
motivation of EDEN is straightforward. We want to use a set of trigonometric
functions to represent the position of each node. This representation is based
on the distance between each pair of nodes. The longer the distance, the
weaker the relationship. The unreachable situation between two nodes in the
graph should be considered, so we manually set a fixed value for them. Taking
all of the above into consideration, it ends up being EDEN. Furthermore, the
input features are preferably normalized real vectors for GNNs. The unweighted
graph distance matrix consists of integers, and its norm can be large, which
is not conducive to model training. We propose three sets of distance-based
node encodings for the ablation study to test our viewpoint, namely, direct
distance, Min-Max normalized distance, and Reversed Min-max normalized
distance.

We implement these three encodings in real-world datasets and compare them
with EDEN. Results are shown in Tab. 4 to 9. The experimental results show
that directly using the distance as an augmented feature has the least
contribution to the MPNNs and may even have negative effects. Normalizing the
distance matrix can improve the performance of the models, but it is often not
as good as reversed normalization. On the other hand, reversed Min-Max
normalized node encoding performs well on all tasks. In some cases, it can
achieve better results than EDEN, but on average, EDEN with phase propagation
achieves the best results.


11institutetext:  1Spectra, Australia
www.spectra.art
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
#  Shackled: a 3D Rendering Engine Programmed Entirely in Ethereum Smart
Contracts

Ike Smith 11 Casey Clifton 1122

###### Abstract

The Ethereum blockchain permits the development and deployment of smart
contracts which can store and execute code “on-chain” — that is, entirely on
nodes in the blockchain’s network. Smart contracts have traditionally been
used for financial purposes, but since smart contracts are Turing-complete,
their algorithmic scope is broader than any single domain. To that end, we
design, develop, and deploy a comprehensive 3D rendering engine programmed
entirely in Ethereum smart contracts, called Shackled. Shackled computes a 2D
image from a 3D scene, executing every single computation on-chain, on
Ethereum. To our knowledge, Shackled is the first and only fully on-chain 3D
rendering engine for Ethereum. In this work, we 1) provide three unique
datasets for the purpose of using and benchmarking Shackled, 2) execute said
benchmarks and provide results, 3) demonstrate a potential use case of
Shackled in the domain of tokenised generative art, 4) provide a no-code user
interface to Shackled, 5) enumerate the challenges associated with programming
complex algorithms in Solidity smart contracts, and 6) outline potential
directions for improving the Shackled platform. It is our hope that this work
increases the Ethereum blockchain’s native graphics processing capabilities,
and that it enables increased use of smart contracts for more complex
algorithms, thus increasing the overall richness of the Ethereum ecosystem.

###### Keywords:

3D rendering rendering engine Blinn-Phong lighting on-chain Ethereum
blockchain smart contracts Solidity non-fungible tokens NFTs

22footnotetext: Corresponding author.

##  1 Introduction

The Ethereum blockchain has often been described as a “World Computer” [B+] as
it offers a smart contract platform that allows for general algorithms to be
ran “on-chain” — that is, entirely on nodes in the blockchain’s network. Smart
contract code has interesting and novel benefits [ZXD+20], namely;
immutability (records on Ethereum cannot be edited once committed to a block),
permanance (the code lasts as long as the blockchain remains in existence),
transparency (all smart contract source code is visible publically),
scalability (smart contract code can be executed on any node in the network),
exact reproducibility (other programs can execute the code identically given
the same inputs), and composability (other programs can use the code as a
building block in a larger system).

In this work, we program a 3D rendering engine — that is, a program which
takes as input a three dimensional scene, and computes as an output a two
dimensional image representing what that scene would look like from a given
camera pose — entirely within Solidity smart contracts. We then deploy it on
the Ethereum blockchain. We name the engine Shackled due to its on-chain
nature. To the best of our knowledge, Shackled is the first fully on-chain 3D
rendering engine.

The contributions of this work are as follows:

  1. 1.

Quantification of the efficiency of Shackled in terms of gas usage.

  2. 2.

Three 3D object datasets that are compatible with Shackled.

  3. 3.

A demonstration of the utility of Shackled: we develop and deploy a generative
art project (Shackled Genesis), integrating Shackled with non-fungible tokens
(NFTs).

  4. 4.

A user interface to the Shackled smart contract library called Shackled
Creator111Available at https://shackled.spectra.art/#/creator., which allows
users to render 3D objects entirely on the blockchain through a simple, no-
code, visual interface on the web.

  5. 5.

A complete discussion regarding the challenges of programming complex
algorithms as Solidity smart contracts.

##  2 Related work

Solidity smart contracts are a relatively young technology [Dan17], and have
been used for primarily financial use cases. Perhaps most notably, enabling
the development of Decentralised Finance (DeFi); a class of finance
characterised by blockchain-based trustlessness and secure peer-to-peer
transactions in the absence of a trusted third party [CPP21]. However, the
applications of smart contracts extend well beyond the domain of finance, with
on-chain implementations of complex algorithms appearing in the Ethereum
ecosystem (e.g., an on-chain chess engine [fiv21]).

One novel yet controversial application of smart contracts is the tokenisation
of art NFTs [WLWC21, Cho21]. NFTs have been criticised for their implications
on traditional copyright law [Gol21], breaches of intellectual property
[Yod22], effect on art [Fry21], environmental impact [TBDI22] (this is
discussed in the context in this project in Appendix A), over-hyped status in
the modern in zeitgeist [MB21], and their lack of regulation promoting a
predatory culture of scamming, manipulation, and fraud [TM20].

Conversely, they have also been praised for redefining the nature of ownership
in the digital age [WLWC21, Cho21], status as a novel investment opportunity,
and for the positive effect that they have had on art culture [Kug21] and
collectorship.

Much work has been done regarding the tokenisation of art, including Ethereum-
based generative art projects [Hub21, HA21, Nou21], on-chain graphics
libraries [Wu21], storing of 3D objects on-chain [say22], and using on-chain
technology for the generation and preservation of digital art [MJ19, MJ17,
Hol22].

At the intersection of art tokenisation and smart contract programming is the
potential for performing 3D rendering on-chain. Approaches to decentralised 3D
rendering are being explored and commercialised [Tok17], with a focus on
large-scale computing on custom blockchains by leveraging graphs of computing
nodes [Alc22, WJL+20] optimised for graphics processing. These approaches
transfer the hardware burden from the user to a decentralised network of
compute providers, essentially creating a market for specialised computation.

Although Solidity smart contracts represent a great opportunity for
algorithmic development, the scale of computation that they allow at this time
is limited; modern graphics engines could not currently be implemented in
Solidity. As such, Shackled is based on the work of early graphics pioneers,
using technology from nearly $50$ years ago (which is more suited for
implementation on-chain today). Specifically, we modify versions of Bui Tong
Phuong’s [Pho75] and Jim Blinn’s [Bli77] original 3D rendering and lighting
models, and use them to create a Solidity version of a simple rendering
pipeline inspired by OpenGL [SA99].

##  3 Datasets

We begin by developing and presenting three datasets in Table 1 for use with
Shackled which will be used throughout this work (see Appendix B for data
availability). Firstly, the Shackled Genesis Dataset, which comprises $1024$
triangular prism-based geometries generated using an on-chain geometry
generating algorithm. Secondly, the Shackled Icons Dataset, which is comprised
of a series of hand-crafted 3D objects. Thirdly, the Shackled Common Graphics
Objects Dataset, which is comprised of common objects from 3D graphics
history, processed for compatibility with Shackled.

##  4 Approach

###  4.1 Development

Shackled was developed using common development tools for programming and
testing Solidity smart contracts on Ethereum. Our technical stack included
Hardhat as the primary development environment, Ethers for interfacing with
the smart contracts, and Chai for testing. We catalogue the development
challenges and how they were overcome in Table 1.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
(a) Examples from the Shackled Genesis Dataset, as rendered in Shackled. Each
instance features a number of triangular prisms placed generatively and
rendered with different colour and lighting parameters. There are $1024$
instances in the dataset.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
(b) Examples from the Shackled Icons Dataset, as rendered in Shackled. The
subjects of each render were chosen for recognisability and relevance in the
on-chain art and NFT community.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
(c) Examples from the Shackled Common Graphics Object Dataset, as rendered in
Shackled. Top row: 3DBenchy (3D printing benchmark), Cornell’s box [GTGB84],
wireframe renders of a Cube and an Isosphere, a 3D scan of the bust of
Nefertiti [WB82], and a 3D scan of Michaelangelo’s sculpture David [LPC+00].
Bottom row: Stanford’s Dragon, Bunny, Armadillo, and Tyra [Sta14], the Utah
Teapot, and Blender’s Suzanne [Bla19].

Figure 1: Datasets used in this work. Table 1: Descriptions of development challenges and the solutions used to overcome them during the development of Shackled. We categorise the challenges as being imposed by Solidity, or by the Ethereum ecosystem. Description | Solution
---|---
Solidity programming language challenges
No support for floating point or fixed-point numbers. |  Use whole numbers in the gwei designation ($10^{9}$).
Data types less than 32 bytes being assembled into the same storage slot, reducing division precision. |  Pad variables to ensure they take up $32$ bytes, and use unit tests to ensure correct behavior.
Overflow and underflow errors are common as integers are a fixed size. |  The latest versions of Solidity include automatic checks for these errors.
Limited best-practice documentation. |  Learn from exemplar projects (all on-chain code is open source).
Uninformative stack trace errors. |  use development environments such as Hardhat.
Limited / no typecasting. |  Develop workarounds for types that can’t be cast to other types. There is not necessarily a ‘catch-all’ solution to this issue.
Only 16 variables being usable at a time due to the stack depth limit. |  Use structs to store and pass variables.
Ethereum ecosystem challenges
Exceeding gas limits imposed by node providers. |  Run your own node or find a provider willing to provide a higher limit (Alchemy in our case).
Modifying / writing storage incurs significant expense on the Ethereum blockchain. |  No general solution, but on-chain compression and generation can be useful to avoid directly storing data.
True randomness is not possible as Ethereum is deterministic. |  Psuedorandomness can be achieved by using a block’s hash or number as input.
The EVM stack has only 1024 slots available for functions calling other functions. |  Use loops in lieu of recursion.

To benchmark Shackled and estimate the cost of computation, we estimate the
amount of gas; a unit describing the amount of computational power required to
perform some specific computation on the Ethereum network [B+]. Our gas
estimation approach involves binary searching the upper and lower gas limits
until a ‘not enough gas’ error is triggered; we repeatedly attempt to complete
renders with less and less gas until we converge on the true gas required to
perform a specific render operation, allowing us to accurately measure the
computational cost of completing a given render.

Importantly, Shackled does not require the expenditure of gas to perform
rendering operations. The entire rendering operation is implemented in a read
call, and thus does not write any data to the Ethereum blockchain. As such,
all gas estimations presented in this study are gas-equivalents, e.g., a
Shackled render benchmarked at $10$ billion units of gas does not actually
consume that amount of gas, but its computational cost is equivalent to an
operation that would consume that amount.

###  4.2 Design of the rendering pipeline

Shackled converts a 3D model into a 2D image using a sequential rendering
pipeline inspired by OpenGL [SA99] and modified for on-chain implementation
and execution (see Figure 2). The key steps are as follows.

Vertex specification involves providing the 3D positions and colours for all
points in the object’s mesh. Faces will be constructed from these 3-vectors as
per the .obj file format specification [MB08].

The vertex shader is traditionally a program written in a language designed
for accelerated computation on graphics hardware, which allows for parallel
processing of independent vertex computations. In Shackled, we have no such
accelerative capability. The vertex shader still assumes the traditional role
of projecting the points using a perspective or orthographic camera matrix,
and transforming the points via a model view matrix (translations and scaling
are supported), converting the points to world space.

|  |  |  |  |
---|---|---|---|---|---
Figure 2: The results of the key steps of the Shackled rendering pipeline for
rending a single triangle. From left to right, we display the outputs of 1)
vertex specification, 2) the vertex shader, 3) primitive assembly, 4)
rasterization, 5) the fragment shader, 6) compositing and image buffer return.
Ultimately the render comprises of a red-green-blue coloured triangle light
with a harsh specular light with a steep fall-off from the bottom right,
composited onto a blue gradient background. All steps are computed on the
Ethereum blockchain entirely within smart contracts.

Primitive assembly involves taking groups of 3 vertices and constructing
triangles out of them (Shackled only supports triangulated objects as input).
The vertex indices of the triangles are specified during vertex specification.
No form of clipping or frustrum culling is performed at this stage.

Rasterization uses a combination of Bresenham’s algorithm [Koo87] and the
Scanline algorithm [LC79] to convert sets of three vertices into a wireframe
triangle, and then into a filled triangle with interpolated colours. No form
of anti-aliasing or subpixel interpolation is implemented. Fragments
(candidate pixels) may overlap at this stage (i.e., have the same (x,y)
position in the final image), but will be discarded if they are outside of the
bounds of the canvas.

The fragment shader applies Blinn-Phong shading [Pho75, Bli77] to each
fragment depending on the lighting configuration provided. The projected
depths of each fragment are also used for depth testing, and only the closest
fragments are kept (i.e., near parts of the object are rendered in favor of
far away parts of the object if they occupy the same position in the render).

Compositing is the process whereby the pixel data is written into an image
buffer (i.e. a 2D matrix with an RGB tuple at each element), and applied on
top of a background. Shackled supports the generation of unicolour
backgrounds, or two-color vertical gradient backgrounds. The image buffer is
then encoded as a bitmap image.

###  4.3 Deployment

Shackled’s on-chain code consists of 13 smart contracts and libraries. The
deployment of Shackled cost $0.258\Xi$ ($427$ USD at the time) and the
deployment of Shackled Icons (a follow up tokenised art collection) cost
$0.05\Xi$ ($80$ USD at the time). The cost of the follow up project was
significantly less as the rendering engine code had already been deployed and
could be used in a composable manner. The deployed and verified contracts can
be found in Appendix B. These projects tokenised the renders of Shackled as
ERC-721A tokens (i.e., NFTs), demonstrating Shackled’s commercial potential
and viability in niche rendering use cases.

Figure 3: Shackled Creator; a simple user interface to the Shackled rendering
engine contracts. Note that rotation is provided as a transformation, however,
the rotation matrix multiplications are calculated off-chain in the front-end.
All other computations are performed on-chain.

We also implemented, deployed, and provided a custom user interface (UI) to
the Shackled smart contracts which enables a user to use Shackled for on-chain
3D rendering without any expertise in on-chain programming, Solidity, or smart
contracts (see Figure 3). This UI — Shackled Creator — is free to use and
publically available222Available at https://shackled.spectra.art/#/creator..

##  5 Results and discussion

###  5.1 Computation scales quadratically with canvas size

We render the same object from a canvas size of $8\times 8$ to $128\times 128$
doubling the canvas size in each axis for each step. We use our gas estimation
procedure to estimate the computational cost, and plot it in Figure 4 (right).
We compute two sets of results: one using the perspective camera projection
model, and one using the orthographic camera projection model. The resultant
renders are depicted in Figure 4 (left).

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

Figure 4: Rendering different cubes on-chain whilst varying canvas size and
camera model parameters. Left, top row: varying the canvas size from 8 — 128
pixels using a perspective camera. Left, bottom row: varying the canvas size
from 8 — 128 pixels using an orthographic camera. Right: plotting the gas
estimates as a function of canvas size for each render using the perspective
and orthographic camera settings.

We note that the computation cost scales quadratically with the canvas size,
as expected due to the quadratic increase in fragments with canvas size.
Additionally, the computation cost is invariant to the camera projection
model. This quadratic scaling greatly limits the scalability of Shackled to
larger renders, and potential improvements to alleviate this issue are
suggested in Section 6.

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

Figure 5: Left: the resultant renders from testing how the gas cost scales
with the number of rendered pixels. The gas-pixel relationship is explored by
rendering 1 — 16 identical triangles, which result in a near-identical number
of pixels per triangle in the final render. Right: the estimated gas usage
increases approximately linearly with the number of triangles, and thus
pixels. We note that the y-axis offset suggests that there is a constant
amount of gas which is always ‘paid’ regardless of the render. Figure 6:
Estimated gas costs plotted against number of triangles in the rendered
object, for every instance of the Shackled Genesis Dataset (see Table 1). A
linear fit is applied using the NumPy package’s polyfit function [HMvdW+20],
and the result is plotted and displayed. Each triangular prism in each
instance is comprised of $7$ triangles: $1$ for the front face, and $2$
triangles each for the $3$ sides of the prism (the prisms have no back), hence
the $7$ unit separation in the x-axis.

###  5.2 Computation scales linearly with the number of triangles rendered

We investigate the cost of rendering increasing numbers of pixels by
incrementally rendering duplicates of an identical geometry (a single
triangle), as illustrated in Figure 5. We note that linearly increasing the
number of triangles (and thus the number of fragments / pixels), results in a
linear increase in the computational cost (as approximated by estimated gas).

This allows Shackled to scale well to geometries with a large number of
triangles, as long as the number of pixels on screen remains bounded. Indeed,
this enables Shackled to successfully render an expressive range of objects
on-chain, as illustrated in Table 1; the number of triangles in these objects
range from $20$ (default cube) to $1198$ (Michaelangelo’s David).

Additionally, we demonstrate a similar pattern using the entirety of the
Shackled Genesis Dataset (samples illustrated in Table 1). The results are
shown in Figure 6 and demonstrate again that there is an approximately linear
relationship between the number of rendered pixels and the cost of computation
(again approximated by estimated gas).

###  5.3 Backface culling reduces computation significantly

Furthermore, we investigate how backface culling [Bli93] — an approach which
analyses the normal vector of a triangle as it compares to the direction that
the camera is pointing — can greatly reduce the number of fragments that are
computed by removing triangles that would never be visible in the final
render. By reducing the number of fragments, we reduce the amount of required
computation, and thus increase the capability of the rendering engine.

We render the Shackled Common Graphics Objects Dataset with backface culling
and without backface culling enabled. Without backface culling, the average
gas estimate for rendering any object in the dataset is $1.54\times 10^{11}$,
compared to $4.39\times 10^{10}$ with backface culling enabled; a decrease of
$3.51$ times. We conclude that implementing on-chain backface culling greatly
increases the capacity of Shackled to render complex objects, without any
visible change to the output renders.

##  6 Conclusion and future work

In this work, we have introduced and implemented Shackled, the first fully on-
chain 3D rendering engine. We have benchmarked its efficiency using three
custom datasets, demonstrated its use cases with respect to decentralised
rendering, tokenised art, and as a blockchain-based platform for native 3D
graphics processing. The datasets, source code, and a user interface for
Shackled have been made available publically (see Appendix B). Moreover, we
have outlined the challenges associated with implementing complex algorithms
(e.g. linear algebraic equations, trigonometry, and tensor operations)
entirely in Solidity smart contracts.

In this early stage, Shackled illustrates only a fragment of the potential for
fully on-chain algorithms — particularly rendering engines. Candidates for
future work that could improve Shackled include:

  * •

Removing rendering artifacts along straight lines and edges by implementing
the digital differential analyzer algorithm in lieu of Bresenhams algorithm
[Koo87], as it is a better fit for interpolating with only integer arithmetic.

  * •

Implementing on-chain rotation transformations using quaternions, Rodrigues’
rotation, matrix products, or some other suitable 3D rotation algorithm.

  * •

Taking proper advantage of the ‘embarassingly parallel’ nature of 3D graphics
rendering, e.g. rendering patches of a render simultaneously across nodes and
compositing them together once complete.

## Acknowledgements

We would like to thank the entire team at Spectra for working behind the
scenes, sharing ideas which greatly improved the final Shackled renders, and
for supporting the development of Shackled and its related projects.

Moreover, running Shackled uses a relatively large gas-equivalent of
computation (compared to traditional Ethereum smart contract functions). We
would like to thank our partners at Alchemy for specially raising the
computation limits of an Ethereum read-call on their nodes so as to allow
Shackled to operate.

Finally, the creation of Shackled would not have been possible without the
Spectra community, and we would like to give a warm thanks to Doubtingtrev,
HollywoodMeta.eth, Awesomerrificus, and Max Bridgland for their work in
directly managing, promoting, supporting, and moderating the community.

In addition, we would like to thank Aubjectivity, nodallydude, Bon(g/j)e, Paul
Balaji, Ntando Mhlungu, Divirzion.eth, a7111a.eth, I2DT, wakeupremember.eth,
Ian Orz, Animechanic, TriPoloski, ZiK$\\_$WaN, NFTxDeFi, Michael Slonim,
cearwylm, Petter Rasmussen, rpl.eth, Dalst, reechard.eth, JP, El Citadel,
Ralph Clayton, Parker Thompson, Ott Erlord, and Jordysure for their support,
feedback, and endorsements of Shackled. Fostering a positive community of
folks that are excited about the technological advancement of on-chain art
would not have been possible without you all.

## References

  * [Alc22] Alchemy.  Alchemy node provider documentation.  2022\.  Accessed on the 9th of August 2022.  URL: https://docs.alchemy.com/docs/.
  * [B+] Vitalik Buterin et al.  Ethereum white paper.
  * [Bla19] John M Blain.  The complete guide to Blender graphics: computer modeling & animation.  AK Peters/CRC Press, 2019.
  * [Bli77] James F Blinn.  Models of light reflection for computer synthesized pictures.  In Proceedings of the 4th annual conference on Computer graphics and interactive techniques, pages 192–198, 1977.
  * [Bli93] James F Blinn.  Backface culling snags (rendering algorithm).  IEEE Computer Graphics and Applications, 13(6):94–97, 1993.
  * [Cho21] Usman W Chohan.  Non-fungible tokens: Blockchains, scarcity, and value.  Critical Blockchain Research Initiative (CBRI) Working Papers, 2021\.
  * [CPP21] Francesco Maria De Collibus, Alberto Partida, and Matija Piškorec.  The role of smart contracts in the transaction networks of four key defi-collateral ethereum-based tokens.  In International Conference on Complex Networks and Their Applications, pages 792–804. Springer, 2021.
  * [Dan17] Chris Dannen.  Introducing Ethereum and solidity, volume 1.  Springer, 2017.
  * [fiv21] fiveoutofnine.  On chain chess project.  2021\.  URL: https://www.fiveoutofnine.com/.
  * [Fry21] Brian L Frye.  Nfts & the death of art.  Available at SSRN 3829399, 2021.
  * [Gol21] Matt Goldman.  Non-fungible tokens: Copyright implications in the wild west of blockchain technology.  2021\.
  * [GTGB84] Cindy M Goral, Kenneth E Torrance, Donald P Greenberg, and Bennett Battaile.  Modeling the interaction of light between diffuse surfaces.  ACM SIGGRAPH computer graphics, 18(3):213–222, 1984.
  * [HA21] Harri and Arran.  Brotchain.  Divergence, 2021.  URL: https://brotchain.art/.
  * [HMvdW+20] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.  Array programming with numpy.  Nature, 585(7825):357–362, September 2020.  URL: https://doi.org/10.1038/s41586-020-2649-2.
  * [Hol22] PROOF Holdings.  Moonbirds, the official proof pfp.  2022\.  URL: https://www.moonbirds.xyz/.
  * [Hub21] David Huber.  Strange attractors technical details.  Strange Attractors, 2021.  URL: https://strangeattractors.art/details.
  * [Koo87] P Koopman.  Bresenham line-drawing algorithm.  Forth Dimensions, 8(6):12–16, 1987.
  * [Kug21] Logan Kugler.  Non-fungible tokens and the future of art.  Communications of the ACM, 64(9):19–20, 2021.
  * [LC79] Jeff Lane and Loren Carpenter.  A generalized scan line algorithm for the computer display of parametrically defined surfaces.  Computer Graphics and Image Processing, 11(3):290–297, 1979.
  * [Lim21] Offsetra Limited.  Carbon fyi.  2021\.  URL: https://carbon.fyi/.
  * [LPC+00] Marc Levoy, Kari Pulli, Brian Curless, Szymon Rusinkiewicz, David Koller, Lucas Pereira, Matt Ginzton, Sean Anderson, James Davis, Jeremy Ginsberg, et al.  The digital michelangelo project: 3d scanning of large statues.  In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 131–144, 2000.
  * [MB08] Kenton McHenry and Peter Bajcsy.  An overview of 3d data content, file formats and viewers.  National Center for Supercomputing Applications, 1205:22, 2008.
  * [MB21] Simon Mackenzie and Diāna Bērziņa.  Nfts: Digital things and their criminal lives.  Crime, Media, Culture, page 17416590211039797, 2021.
  * [MJ17] Matt and John.  Cryptopunks project.  Larva Labs, 2017.  URL: https://www.larvalabs.com/cryptopunks.
  * [MJ19] Matt and John.  Autoglyphs project.  Larva Labs, 2019.  URL: https://www.larvalabs.com/autoglyphs.
  * [Nou21] Nouns.  Nouns dao project.  2021\.  URL: https://nouns.wtf/.
  * [Pho75] Bui Tuong Phong.  Illumination for computer generated pictures.  Communications of the ACM, 18(6):311–317, 1975.
  * [SA99] Mark Segal and Kurt Akeley.  The opengl graphics system: A specification (version 1.1), 1999.
  * [say22] sayangel.  Building the first on-chain 3d nft with gltf.  Blitblox, 2022.  URL: https://mirror.xyz/angelsay.eth/Fpqj6Hawn-IWGgXm9oEYXyscIgolotYscShuNaVTmI4.
  * [Sta14] Stanford.  The stanford 3d scanning repository.  2014\.  URL: http://graphics.stanford.edu/data/3Dscanrep/.
  * [TBDI22] Jon Truby, Rafael Dean Brown, Andrew Dahdal, and Imad Ibrahim.  Blockchain, climate damage, and death: Policy interventions to reduce the carbon emissions, mortality, and net-zero implications of non-fungible tokens and bitcoin.  Energy Research & Social Science, 88:102499, 2022.
  * [TM20] David Twomey and Andrew Mann.  Fraud and manipulation within cryptocurrency markets.  Corruption and fraud in financial markets: malpractice, misconduct and manipulation, 624, 2020.
  * [Tok17] Render Token.  Render token (rndr) whitepaper.  2017\.  Accessed on the 9th of August 2022.
  * [WB82] Hans Georg Wiedemann and Gerhard Bayer.  The bust of nefertiti.  Analytical chemistry, 54(4):619–628, 1982.
  * [WJL+20] Isaac Ronald Ward, Jack Joyner, Casey Lickfold, Stash Rowe, Yulan Guo, and Mohammed Bennamoun.  A practical guide to graph neural networks.  arXiv preprint arXiv:2010.05234, 2020.
  * [WLWC21] Qin Wang, Rujia Li, Qi Wang, and Shiping Chen.  Non-fungible token (nft): Overview, evaluation, opportunities and challenges.  arXiv preprint arXiv:2105.07447, 2021.
  * [Wu21] Wattsy and untokyo.  We permanently preserve digital art online.  Kohi Art, 2021.  URL: https://kohi.art/onchain.
  * [Yod22] Madison Yoder.  An” opensea” of infringement: The intellectual property implications of nfts.  The University of Cincinnati Intellectual Property and Computer Law Journal, 6(2):4, 2022.
  * [ZXD+20] Zibin Zheng, Shaoan Xie, Hong-Ning Dai, Weili Chen, Xiangping Chen, Jian Weng, and Muhammad Imran.  An overview on smart contracts: Challenges, advances and platforms.  Future Generation Computer Systems, 105:475–491, 2020.

## Appendix

###  A Environmental considerations

Shackled was developed during the Ethereum blockchain’s proof-of-work era. The
deployment and subsequent use of the two main contract libraries discussed in
this work (Shackled Genesis and Shackled Icons) resulted in a total energy use
equivalent to the emission of 54.6 metric tonnes of carbon dioxide, as
measured by the Ethereum emissions calculator Carbon.FYI [Lim21].

We are aware of the environmental impact of proof-of-work blockchains and have
offset five times this amount of carbon dioxide — 273 tonnes — via the
retirement of verified carbon credit units provided by Offsetra Limited.
Verra-accredited retired unit records are available at the following links:

  1. 1.

https://registry.verra.org/myModule/rpt/myrpt.asp?r=206&h=162735.

  2. 2.

https://registry.verra.org/myModule/rpt/myrpt.asp?r=206&h=166285.

###  B Data availability and reproducibility

Data, tools, and code are available at the following links:

  * •

Shackled website.

  * •

Shackled no-code user interface website.

  * •

GitHub repository for accessing datasets.

  * •

Verified smart contracts for Shackled on Etherscan.

###  C The first on-chain render computed by Shackled

As Shackled is the first on-chain 3D rendering engine, we believe its first
output to be the first on-chain 3D render. We have embedded that render into
this paper for posterity (Figure 7).

Figure 7: The first on-chain render computed by Shackled. We believe this to
be the first on-chain 3D render ever computed on Ethereum. The triangles
naturally appear 2D in the render, but are defined in 3D space by the points
(-1,0,0), (-1,2,0), (0,2,0) and (1,0,5), (1,-2,5), (0,-2,5) respectively.