# GRAPH AUTO-ENCODER VIA NEIGHBORHOOD WASSERSTEIN RECONSTRUCTION

**Mingyue Tang[1][∗], Carl Yang[2][∗], Pan Li[3][†]**

1Department of Engineering Systems and Environment, University of Virginia
2Department of Computer Science, Emory University
3Department of Computer Science, Purdue University
utd8hj@virginia.edu, j.carlyang@emory.edu, panli@purdue.edu

ABSTRACT

Graph neural networks (GNNs) have drawn significant research attention recently,
mostly under the setting of semi-supervised learning. When task-agnostic representations are preferred or supervision is simply unavailable, the auto-encoder
framework comes in handy with a natural graph reconstruction objective for unsupervised GNN training. However, existing graph auto-encoders are designed to
reconstruct the direct links, so GNNs trained in this way are only optimized towards
proximity-oriented graph mining tasks, and will fall short when the topological
structures matter. In this work, we revisit the graph encoding process of GNNs
which essentially learns to encode the neighborhood information of each node into
an embedding vector, and propose a novel graph decoder to reconstruct the entire
neighborhood information regarding both proximity and structure via Neighborhood Wasserstein Reconstruction (NWR). Specifically, from the GNN embedding
of each node, NWR jointly predicts its node degree and neighbor feature distribution, where the distribution prediction adopts an optimal-transport loss based on
the Wasserstein distance. Extensive experiments on both synthetic and real-world
network datasets show that the unsupervised node representations learned with
NWR have much more advantageous in structure-oriented graph mining tasks,
while also achieving competitive performance in proximity-oriented ones.[1]

1 INTRODUCTION

Network/Graph representation learning (a.k.a. embedding) aims to preserve the high-dimensional
complex graph information involving node features and link structures in a low-dimensional embedding space, which requires effective feature selection and dimension reduction (Hamilton et al.,
2017b). Graph neural networks (GNNs) have done great jobs to this end, but most of them rely
on node labels from specific downstream tasks to be trained in a semi-supervised fashion (Kipf &
Welling, 2017; Hamilton et al., 2017a; Wu et al., 2019; Veliˇckovi´c et al., 2018a; Klicpera et al.,
2019; Chien et al., 2021). However, similar to other domains, unsupervised representation learning is
preferred in many cases, not only because labeled data is not always available (Hu et al., 2020; Xie
et al., 2021), but also task-agnostic representations can better transfer and generalize among different
scenarios (Erhan et al., 2010; Bengio, 2012; Radford et al., 2016).

To train GNNs in an unsupervised fashion, the classic auto-encoder framework (Baldi, 2012; Goodfellow et al., 2016) provides a natural solution and has been widely explored such as the prominent
work (V)GAE (Kipf & Welling, 2016). Specifically, classic auto-encoders aim to decode from the
low-dimensional representations information in the entire receptive field of the neural networks. For
GNNs, the receptive field of a node representation is its entire neighborhood. However, existing graph
auto-encoders appear away from such a motivation and are designed to merely decode the direct
links between the node pairs by minimizing a link reconstruction loss. The fundamental difficulty to
reconstruct the entire receptive fields of GNNs is due to the non-trivial design of a reconstruction loss
on the irregular graph structures. Unfortunately, the over-simplification into link reconstruction makes
the learned node representations drop much information and thus provides undesired performance in
many downstream tasks.

_∗Equal contribution. †Corresponding author._
[1Code available at https://github.com/mtang724/NWR-GAE.](https://github.com/mtang724/NWR-GAE)


-----

Figure 1: A toy example (redrawn from real experiments) illustrating different types of information
in real-world graphs and the two-dimensional node embedding spaces learned by different models.
Colors indicates node features. The nodes with same digits are transitive in some graph automorphism.

Take Figure 1 as an example, where different types of information are mixed in a graph (e.g., proximity
and structure information as illustrated in Figure 5 in Appendix B (Cui et al., 2021)). The node
representations learned by existing graph auto-encoders such as GAE (Kipf & Welling, 2016) are
driven too much to be similar on linked nodes due to their simple link reconstruction objective,
and thus fail to distinguish node pairs like (2, 4) and (3, 5) in the cliques, though they clearly have
different structural roles and node features. On the other hand, structure-oriented embedding models
like GraphWave (Donnat et al., 2018) cannot consider node features and spatial proximity, and thus
fail to distinguish node pairs like (0, 1), (2, 4) and (3, 5) though they have different features, as well
as (2, 5) and (3, 4) though they are further apart. An ideal unsupervised node representation learning
model as we advocate in this work is expected to be task-agnostic and encode as much information as
possible of all types in a low-dimensional embedding space.

In this work, we aim to fundamentally address the above limitations of existing unsupervised node
representation learning models by proposing a novel graph auto-encoder framework for unsupervised
GNN training. The new framework is equipped with a powerful decoder that fully reconstructs the
information from the entire receptive field of a node representation. Our key technical contribution
lies in designing a principled and easy-to-compute loss to reconstruct the entire irregular structures of
the node neighborhood. Specifically, we characterize the decoding procedure as iteratively sampling
from a series of probability distributions defined over multi-hop neighbors’ representations obtained
through the GNN encoder. Then, the reconstruction loss can be decomposed into three parts, for
sampling numbers (node degrees), neighbor-representation distributions and node features. All of
these terms are easy to compute but may represent the entire receptive field of a node instead of just
the linkage information to its direct neighbors. For the most novel and important term, neighborrepresentation distribution reconstruction, we adopt an optimal-transport loss based on Wasserstein
distance (Frogner et al., 2015) and thus name this new framework as Neighborhood Wasserstein
Reconstruction Graph Auto-Encoder (NWR-GAE). As also illustrated in Figure 1, NWR-GAE can
effectively distinguish all pairs of nodes dissimilar in different perspectives, and concisely reflect
their similarities in the low-dimensional embedding space.

We have conducted extensive experiments on four synthetic datasets and nine real-world datasets.
Among the real-world datasets, three have proximity-oriented tasks, three have structure-oriented
tasks, and three have proximity-structure-mixed tasks. We can observe significant improvements
brought by NWR-GAE over the best method among the state-of-the-art baselines on all structureoriented tasks (8.74% to 18.48%) and proximity-structure-mixed tasks (-2.98% to 8.62%), and
competitive performance on proximity-oriented tasks (-3.21% to -0.32%). In-depth ablation and
hyper-parameter studies further consolidate the claimed advantages of NWR-GAE.

2 PRELIMINARIES, MOTIVATIONS & OTHER RELATED WORKS

In this work, we focus on the auto-encoder framework for unsupervised task-agnostic graph representation learning. The original motivation of auto-encoders is to perform neural-network-based
dimension reduction of the data that originally lies in a high-dimensional space (Hinton & Salakhutdinov, 2006). Specifically, an auto-encoder consists of two components, an encoder and a decoder. The
encoder works to compress each data point into a low-dimensional vector representation, while the
decoder works to reconstruct the original information from this vector. By minimizing the reconstruc

-----

𝑎 𝑐 𝑏 ℎGNN layers has the ௩(ଶ)obtained via two

information from 2-hop

𝑣 𝑎 [ 𝑓] 𝑣 𝑒 neighborhood of 𝑣.


1-hop neighborhood

2-hop neighborhood


𝑒 𝑎

𝑐

𝑣

𝑏

𝑓


ℎ௩(ଶ) 𝑣

𝑎 𝑐 𝑏

𝑣

𝑐 𝑒 𝑣 𝑎 [ 𝑓] 𝑣 𝑒


Figure 2: The information source/receptive field of the node representation h[(2)]v [.]

tion error, the encoder automatically converges to a good compressor that allows the low-dimensional
representations to capture as much information as possible from the original data.

Although the above high-level idea of auto-encoders is clear, when it is applied to graph structured
data, the problem becomes challenging. This is because in graph-structured data, information of data
points (nodes to be specific as most widely studied) is correlated due to the ambient graph structure.
Without a specific task needed in a priori, the learned low-dimensional representation of a node
should carry as much information as possible from not only its own features but also the features of
the nodes it connects to (both directly and indirectly).

This implies that when building auto-encoders for graph-structure data, we expect the node representations to be able to reconstruct all correlated node features. However, existing graph auto-encoders
seem to be away from this motivation. Previous prominent works such as unsupervised GraphSAGE (Hamilton et al., 2017a), GAE (Kipf & Welling, 2016), their generative variants such as
VGAE (Kipf & Welling, 2016), CondGen (Yang et al., 2019) (), and many others (Grover et al.,
2019; Pan et al., 2018; Shi et al., 2020; Yang et al., 2021), use GNNs to encode graph structured
data into node representations. Without exception, they follow the rationale of traditional network
embedding techniques (Perozzi et al., 2014; Qiu et al., 2018; Grover & Leskovec, 2016) and adopt
link reconstruction in the decoder as the main drive to optimize their GNN encoders. The obtained
node representations best record the network linkage information but lose much of other important
information, such as local structures, neighbors’ features, etc. Hence, these auto-encoders will most
likely fail in other tasks such as node classifications (especially structure-oriented ones as manifested
in Figure 1).

To better understand this point, we carefully analyze the source of information encoded in each
node representation via a GNN. Suppose a standard message-passing GNN (Gilmer et al., 2017) is
adopted as the encoder, which is a general framework that includes GCN (Kipf & Welling, 2017),
GraphSAGE (Hamilton et al., 2017a), GAT (Veliˇckovi´c et al., 2018a), GIN (Xu et al., 2019c) and so
on. After k-hop message passing, the source of information encoded in the representation of a node v
essentially comes from the k-hop neighborhood of v (Fig. 2). Therefore, a good representation of
node v should capture the information of features from all nodes in its k-hop neighborhood, which is
agnostic to downstream tasks. Note that this may not be ideal as nodes out of k-hop neighborhood may
also provide useful information, but this is what GNN-based graph auto-encoders can be expected
to do due to the architectures of GNN encoders. This observation motivates our study on a novel
graph decoder that can better facilitate the goal of GNN-based graph auto-encoders, based on the
neighborhood reconstruction principle. We will formalize this principle in Sec. 3.

**Relation to the InfoMax principle. Recently, DGI (Veliˇckovi´c et al., 2018b), EGI (Zhu et al.,**
2021) and others (Sun et al., 2020; Hu et al., 2020; You et al., 2020; Hassani & Khasahmadi, 2020;
Suresh et al., 2021) have used constrasive learning for unsupervised GNN training methods and
may capture information beyond the directed links. They adopt the rule of mutual information
maximization (InfoMax), which essentially works to maximize certain correspondence between the
learned representations and the original data. For example, DGI (Veliˇckovi´c et al., 2018b) maximizes
the correspondence between a node representation and which graph the node belongs to, but this has
no guarantee to reconstruct the structural information of node neighborhoods. Recent works even
demonstrate that maximizing such correspondence risks capturing only the noisy information that
is irrelevant to the downsteam tasks because noisy information itself is sufficient for the models to
achieve InfoMax (Tschannen et al., 2020; Suresh et al., 2021), which gets demonstrated again by
our experiments. Our goal instead is to let node representations not just capture the information to
distinguish nodes but capture as much information as possible to reconstruct the features and structure
of the neighborhood.


-----

|𝑣� er|�, 𝑣�, …, 𝑣|
|---|---|
|||
|𝐻(଴) 𝒩ೡ ℎ(଴) ℎ(଴) ℎ(଴) ௔ ௕ ௖||

|Col1|Col2|
|---|---|
|𝐻(ଵ) 𝒩ೡ ℎ(ଵ) ℎ(ଵ) ℎ(ଵ) ௔ ௕ ௖||

|||ℎ௩଴ −𝜓௦ ℎ௩ଶ ||ଶ|Col2|
|---|---|


use OT-losses to characterize the distance between the variational distribution and the data empirical

**Encoder** 𝑣ଵ, 𝑣ଶ, …, 𝑣௤~𝒩௩ sample neighbors minగ [෍෍||ℎ]ଵ ௤ [௩]௜[ೕ] −ℎ෠௩௜,గ௝ ||ଶ decode

௜ୀ଴ ௝ୀଵ neighborhood

𝐻𝒩(଴)ೡ 𝐻𝒩(ଵ)ೡ 𝐹𝑁𝑁ఓ 𝐹𝑁𝑁௣(଴) 𝐹𝑁𝑁௣(ଵ) 𝜓௣

𝐹𝑁𝑁ఙ 𝜉ଵ, 𝜉ଶ, …, 𝜉௤~𝐺𝑎𝑢𝑠𝑠𝑖𝑎𝑛(𝜇௩, Σ௩)

ℎ௔(଴) ℎ௕(଴) ℎ௖(଴) ℎ௔(ଵ) ℎ௕(ଵ) ℎ௖(ଵ) 𝜓ௗ decode degree 𝑑௩ −𝜓ௗ ℎ௩ଶ ଶ 𝜆ௗ + 𝑙𝑜𝑠𝑠

𝑥௩ 𝜙[(ଵ)] 𝜙[(ଶ)] 𝜓௦ decode initial feature ||ℎ௩଴ −𝜓௦ ℎ௩ଶ ||[ଶ] 𝜆௦

ℎ௩(଴) ℎ௩(ଵ) ℎ௩(ଶ)

**Decoder**

Figure 3: The diagram of our model using an example with 2 GNN layers as the encoder.

**Optimal-transport (OT) losses. Many machine learning problems depend on the characterization**
of the distance between two probability measures. The family f -divergence has the non-continuous
issue when the two measures of interest have non-overlapped support (Ali & Silvey, 1966). Therefore,
OT-losses are often adopted and have shown great success in generative models (Gulrajani et al.,
2017) and domain adaptation (Courty et al., 2016). OT-losses have been used to build variational
auto-encoders for non-graph data (Tolstikhin et al., 2018; Kolouri et al., 2018; Patrini et al., 2020).
But one should note the our work is not a graph-data-oriented generalization of these works: They

distribution while our model even does not use a variational distribution. Our model may be further
improved by being reformulated as a variational autoencoder but we leave it as a future direction.

Here, we give a frequently-used OT loss based on 2-Wasserstein distance that will be used later.

**Definition 2.1. Let P, Q denote two probability distributions with finite second moment defined on**
_Z ⊆_ R[m]. The 2-Wasserstein distance between P and Q defined on Z, Z _[′]_ _⊆_ R[m] is the solution to
the optimal mass transportation problem with ℓ2 transport cost (Villani, 2008):

1/2

2( _,_ ) = inf 2[dγ][(][Z, Z] _[′][)]_ (1)
_W_ _P_ _Q_ _γ_ Γ( _,_ )
 _∈_ _P_ _Q_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][2]_ 

where Γ(P, Q) contains all joint distributions of (Z, Z _[′]) with marginals P and Q respectively._

3 METHODS

3.1 NEIGHBORHOOD RECONSTRUCTION PRINCIPLE (NRP)

Let G = (V, E, X) denote the input graph where V is the node set, E is the edge set and X =
_xv_ _v_ _V_ includes the node features. Given a node v _V, we define its k-hop neighborhood as_
_{_ _|_ _∈_ _}_ _∈_
the nodes which have shortest paths of length no greater than k from v. Let Nv denote the 1-hop
neighborhood of v, and dv denote the degree of node v.

We are to build an auto-encoder to learn a low-dimensional representation of each node. Specifically, the auto-encoder will have an encoder φ and a decoder ψ. φ could be any message-passing
GNNs (Gilmer et al., 2017). The decoder further contains three parts ψ = (ψs, ψp, ψd). The physical
meaning of each part will be clear as we introduce them in the later subsections.

**First-hop neighborhood reconstruction. To simplify the exposition, we start from 1-hop neigh-**
borhood reconstruction. We initialize the node representation by H [(0)] based on X. For every node
_v_ _V, after being encoded by one GNN layer, its node representation h[(1)]v_ collects information from
_∈_
_h[(0)]v_ and its neighbors’ representations H [(0)]v [=][ {][h]u[(0)] _v[}][. Hence, we consider the following]_
_N_ _[|][u][ ∈N]_

principle that reconstructs the information from both h[(0)]v and H [(0)]v [. Therefore, we have]
_N_

min ((h[(0)]v _[, H]_ [(0)]v [)][, ψ][(][h]v[(1)][))][,] s.t. h[(1)]v = φ(h[(0)]v _[, H]_ [(0)]v [)][,][ ∀][v][ ∈] _[V,]_ (2)
_φ,ψ_ _M_ _N_ _N_

_vX∈V_


-----

where M(·, ·) defines the reconstruction loss. M can be split into two parts that measure self-feature
reconstruction and neighborhood reconstruction respectively:

((h[(0)]v _[, H]_ [(0)]v [)][, ψ][(][h]v[(1)][)) =][ M][s][(][h]v[(0)][, ψ][(][h]v[(1)][)) +][ M][n][(][H] [(0)]v _[, ψ][(][h]v[(1)][))][.]_ (3)
_M_ _N_ _N_

Note that Ms works just as the reconstruction loss of a standard feedforward neural network (FNN)based auto-encoder, so we adopt

_Ms(h[(0)]v_ _[, ψ][(][h]v[(1)][)) =][ ∥][h]v[(0)]_ _−_ _ψs(h[(1)]v_ [)][∥][2][.] (4)

_n is much harder to characterize, as it measures the loss to reconstruct a set of features H_ [(0)]v [. There]
_M_ _N_
are two fundamental challenges: First, as in real-world networks the distribution of node degrees is
often long-tailed, the sets of node neighbors may have very different sizes. Second, to compare even
two equal-sized sets, a matching problem has to be solved, as no fixed orders of elements in the sets
can be assumed. The complexity to solve a matching problem is high if the size of the set is large. We
solve the above challenges by decoupling the neighborhood information into a probability distribution
and a sampling number. Specifically, for node v the neighborhood information is represented as
an empirical realization of i.i.d. sampling dv elements from Pv[(0)][, where][ P]v[(0)] ≜ _d1v_ _u∈Nv_ _[δ]h[(0)]u_ [.]

Based on this view, we are able to decompose the reconstruction into the part for the node degree

P

and that for the distribution respectively, where the various sizes of node neighborhoods are handled
properly. Specifically, we adopt

_n(H_ [(0)]v _[, ψ][(][h]v[(1)][)) = (][d][v]_ _v_ [))][2][ +][ W]2[2][(][P]v[(0)][, ψ]p[(1)][(][h]v[(1)][))][,] (5)
_M_ _N_ _[−]_ _[ψ][d][(][h][(1)]_

where 2( _,_ ) is the 2-Wasserstein distance as defined in Eq.1. Plug Eqs.4,5 into Eq.3, we obtain the
_W_ _·_ _·_
objective for first-hop neighborhood reconstruction.

**Generalizing to k-hop neighborhood reconstruction. Following the above derivation for the first-**
hop case, one can similarly generalize the loss for reconstructing (h[(]v[i][−][1)], HN[(][i]v[−][1)]) based on h[(]v[i][)]
for all 1 ≤ _i ≤_ _k. Then, if we sum such losses over all nodes v ∈_ _V and all hops 1 ≤_ _i ≤_ _k, we_
may achieve the objective for k-hop neighborhood reconstruction. We may further simplify such an
objective. Typically, only the final layer representation H [(][k][)] is used as the output dimension-reduced
representations. Too many intermediate hops make the model hard to train and slow to converge.
Therefore, we adopt a more economic way by merging the multi-step reconstruction:


(௞) (௞ିଵ) (ଵ) (଴)

ℎ௩ →ℎ௩ →⋯→ℎ௩ →ℎ௩

𝐻𝒩(௞ିଵ)ೡ 𝐻𝒩(௞ିଶ)ೡ … 𝐻𝒩(଴)ೡ


(௞) (଴)

𝐻𝒩(௞ିଵ)ೡ 𝐻𝒩(௞ିଶ)ೡ … 𝐻𝒩(଴)ೡ


That is, we expect h[(]v[k][)] to directly reconstruct HN[(][i]v[)] [even if][ i < k][ −] [1][. Specifically, for each node]
_v ∈_ _V, we use the reconstruction loss_

_k−1_

((h[(0)]v _[,][ {][H]_ [(][i]v[)] _[|][0][ ≤]_ _[i][ ≤]_ _[k][ −]_ [1][}][)][, ψ][(][h]v[(][k][)][)) =][ M][s][(][h]v[(0)][, ψ][(][h]v[(][k][)][)) +] _n(H_ [(][i]v[)] _[, ψ][(][h]v[(][k][)][))]_
_M[′]_ _N_ _M_ _N_

_i=0_

X


_k−1_

_W2[2][(][P]v[(][i][)][, ψ]p[(][i][)][(][h]v[(][k][)][))][,]_ (6)
_i=0_

X


= λs _h[(0)]v_ _ψs(h[(]v[k][)][)][∥][2][ +][ λ][d][(][d][v]_ _v_ [))][2][ +]
_∥_ _−_ _[−]_ _[ψ][d][(][h][(][k][)]_


where ψs is to decode the initial features, ψd is to decode the degree and ψp[(][i][)][,][ 0][ ≤] _[i][ ≤]_ _[k][ −]_ [1][ is]
to decode the i-layer neighbor representation distribution Pv[(][i][)][(:][≜] _d1v_ _u∈Nv_ _[δ]h[(]u[i][)]_ [)][.][ λ][s][ and][ λ][d][ are]

non-negative hyperparameters. Hence, the entire objective for k-hop neighborhood reconstruction is

P

minφ,ψ _M[′]((h[(0)]v_ _[,][ {][H]N[(][i]v[−][1)]|1 ≤_ _i ≤_ _k}), ψ(h[(]v[k][)][))]_ s.t. H [(][i][)] = φ[(][i][)](H [(][i][−][1)]), 1 ≤ _i ≤_ _k,_ (7)

_vX∈V_

where φ = {φ[(][i][)]|1 ≤ _i ≤_ _k} include k GNN layers and M[′]_ is defined in Eq.6.

_Remark 3.1. The loss in Eq. 6 does not directly push the k-layer representation h[(]v[k][)]_ to reconstruct
the features of all nodes that are direct neighbors but lie in k-hop neighborhood of v. However,
by definition, there exists a shortest path of length no greater than k from v to every node in this
_k-hop neighborhood. As every two adjacent nodes along the path will introduce at least one term_
of reconstruction loss in the sum of Eq. 6, i.e., the objective in Eq. 7. This guarantees that the
optimization in Eq. 7 pushes h[(]v[k][)] to reconstruct the entire k-hop neighborhood of v.


-----

3.2 DECODING DISTRIBUTIONS — DECODERS ψp[(][i][)][,][ 0][ ≤] _[i][ ≤]_ _[k][ −]_ [1]

Our NRP essentially represents the node neighborhood HN[(][i]v[)] [as a sampling number (node degree][ d][v][)]

plus a distribution of neighbors’ representations _v_ (Eqs.5,6). We adopt Wasserstein distance to
_P_ [(][i][)]
characterize the distribution reconstruction loss because _v_ has atomic non-zero measure supports
_P_ [(][i][)]
in a continuous space, where the family of f -divergences such as KL-divergence cannot be applied.
Maximum mean discrepancy may be applied but it needs to specify a kernel function.


We set the decoded distribution ψp[(][i][)][(][h]v[(][k][)][)][ as an FNN-based transformation of a Gaussian distribution]
parameterized by h[(]v[k][)][. The rationale of this setting is due to the universal approximation capability of]
FNNs to (approximately) reconstruct any distributions in 1-Wasserstein distance, as formally stated
in Theorem 3.1 (See the proof in Appendix A, reproduced by Theorem 2.1 in (Lu & Lu, 2020)). For
a better empirical performance, our case adopts the 2-Wasserstein distance and an FNN with m-dim
output instead of the gradient of an FNN with 1-dim outout. Here, the reparameterization trick needs
to be used (Kingma & Welling, 2014), i.e.,
_ψp[(][i][)][(][h][(]v[k][)][) =][ FNN]p[(][i][)][(][ξ][)][, ξ][ ∼N]_ [(][µ][v][,][ Σ][v][)][,][ where][ µ][v] [=][ FNN][µ][(][h][(]v[k][)][)][,][ Σ][v] [=][ diag][(exp(][FNN][σ][(][h][(]v[k][)][)))][.]

**Theorem 3.1. For any ϵ > 0, if the support of the distribution Pv[(][i][)]** lies in a bounded space of R[m],
there exists a FNN u(·) : R[m] _→_ R (and thus its gradient ∇u(·) : R[m] _→_ R[m]) with large enough
width and depth (depending on ϵ) such that W2[2][(][P]v[(][i][)][,][ ∇][u][(][G][))][ < ϵ][ where][ ∇][u][(][G][)][ is the distribution]
generated via the mapping ∇u(ξ), ξ ∼ a m-dim non-degenerate Gaussian distribution.

A further challenge is that the Wasserstein distance between Pv[(][i][)] and ψp[(][i][)][(][h]v[(][k][)][)][ does not have a]
closed form. Therefore, we adopt the empirical Wasserstein distance that can provably approximate
the population one as stated in Sec.8.4.1 in (Peyré et al., 2019). For every forward pass, the
model will get q sampled nodes Nv, denoted by v1, v2, ..., vq and thus {h[(]v[i]j[)][|][1][ ≤] _[j][ ≤]_ _[q][}][ are]_
_q samples from Pv[(][i][)][; Next, get][ q][ samples from][ N]_ [(][µ]v[,][ Σ]v[)][, denoted by][ ξ]1[, ξ]2[, ..., ξ]q[, and thus]
_{h[ˆ]v[(][i,j][)]_ = FNNp[(][i][)][(][ξ][j][)][|][1][ ≤] _[j][ ≤]_ _[q][}][ are][ q][ samples from][ ψ]p[(][i][)][(][h]v[(][k][)][)][; Adopt the following empirical]_

surrogated loss of _i=0_ 2 [(][P]v[(][i][)][, ψ]p[(][i][)][(][h]v[(][k][)][))][ in Eq.6,]

_k−1_ _q_ _[W]_ [2]

minπ [P]i=0[k][−]j=1[1] _∥h[(]v[i]j[)]_ _[−]_ _h[ˆ][(]v[i,π][(][j][))]∥[2], s.t. π is a bijective mapping:[q] →_ [q]. (8)

X X

Computing the above loss is based on solving a matching problem and needs the Hungarian algorithm
with O(q[3]) complexity (Jonker & Volgenant, 1987). More efficient types of surrogate loss may be
adopted, such as Chamfer loss based on greedy approximation (Fan et al., 2017) or Sinkhorn loss
based on continuous relaxation (Cuturi, 2013), whose complexities are O(q[2]). In our experiments, as
_q is fixed as a small constant, say 5, we use Eq.8 based on a Hungarian matching and do not introduce_
much computational overhead.

Although not directly related, we would like to highlight some recent works that use OT losses as
distance between two graphs, where Wasserstein distance between the two sets of node embeddings
of these two graphs is adopted (Xu et al., 2019a;b). Borrowing such a concept, one can view our
OT-loss as also to measure the distance between the original graph and the decoded graph.

3.3 FURTHER DISCUSSION — DECODERS ψs AND ψd

The decoder ψs to reconstruct the initial features h[(0)]v is an FNN. The decoder ψd to reconstruct the
node degree is an FNN plus exponential neuron to make the value non-negative.
_ψs(h[(]v[k][)][) =][ FNN][s][(][h][(]v[k][)][)][,]_ _ψd(h[(]v[k][)][) = exp(][FNN][d][(][h]v[(][k][)][))][.]_ (9)
In practice, the original node features X could be very high-dimensional and reconstructing them
directly may introduce a lot of noise into the node representations. Instead, we may first map X
into a latent space to initialize H [(0)]. However, if H [(0)] is used in both representation learning and
reconstruction, it has the risk to collapse to trivial points. Hence, we normalize H [(0)] = _h[(0)]v_
_{_ _[|][v][ ∈]_ _[V][ }]_
properly via pair-norm (Zhao & Akoglu, 2020) to avoid this trap as follows
_h[(0)]v_ (10)
_{_ _[|][v][ ∈]_ _[V][ }][ =][ pair-norm][(][{][x][v][W]_ _[|][v][ ∈]_ _[V][ }][)][,][ where][ W][ is a learnable parameter matrix.]_


-----

4 EXPERIMENTS

We design our experiments to evaluate NWR-GAE, focusing on the following research questions:
**RQ1: How does NWR-GAE perform on structure-role-based synthetic datasets in comparison to**
state-of-the-art unsupervised graph embedding baselines? RQ2: How do NWR-GAE and its ablations
compare to the baselines on different types of real-world graph datasets? RQ3: What are the impacts
of the major model parameters including embedding size d and sampling size q on NWR-GAE?

4.1 EXPERIMENTAL SETUP

4.1.1 DATASETS

**Synthetic datasets. Following existing works on structure role oriented graph embedding (Henderson**
et al., 2012; Ribeiro et al., 2017; Donnat et al., 2018), we construct multiple sets of planted structural
_equivalences graphs, which are generated by regularly placing different basic shapes (House, Fan,_
_Star) along a cycle of certain length. We use node degrees as the node features, and generate the_
structural-role labels for nodes in the graphs in the same way as (Donnat et al., 2018).
**Real-world graph Datasets. We use a total of nine public real-world graph datasets, which roughly**
belong to three types, one with proximity-oriented (assortative (Liu et al., 2020)) labels, one with
structure-oriented (disassortative) labels, and one with proximity-structure-mixed labels. Among
them, Cora, Citeseer, Pubmed are publication networks (Namata et al., 2012); Cornell, Texas, and
Wisconsin are school department webpage networks (Pei et al., 2020); Chameleon, Squirrel are
page-page networks in Wikipedia (Rozemberczki et al., 2021); Actor is an actor co-filming network
(Tang et al., 2009). More details of the datasets are put in Appendix B.

4.1.2 BASELINES

We compare NWR-GAE with a total of 11 baselines, representing four types of state-of-the-art on
unsupervised graph embedding, 1) Random walk based (DeepWalk, node2vec), 2) Structural role
based (RoleX, struc2vec, GraphWave), 3) Graph auto-encoder based (GAE, VGAE, ARGVA), 4)
Contrastive learning based (DGI, GraphCL, MVGRL).

_• DeepWalk (Perozzi et al., 2014): a two-phase method which generates random walks from all_
nodes in the graph and then treats all walks as input to a Skipgram language model.

_• node2vec (Grover & Leskovec, 2016): a method similar to DeepWalk but uses two hyper-paramters_
_p and q to control the behavior of the random walker._

_• RolX (Henderson et al., 2012): a structure role discovery method which extracts features and group_
features of each node, and then generates structure roles via matrix factorization.

_• struc2vec (Ribeiro et al., 2017): a graph structural embedding method that encodes the structural_
similarities of nodes and generates structural context for each node.

_• GraphWave (Donnat et al., 2018): a graph structural embedding method that models the diffusion_
of a spectral graph wavelet and learns embeddings from network diffusion spreads.

_• GAE (Kipf & Welling, 2016): a GCN encoder trained with a link reconstruction decoder._

_• VGAE (Kipf & Welling, 2016): the variational version of GAE._

_• ARGVA (Pan et al., 2018): a method which considers topological structure and node content,_
trained by reconstructing the graph structure.

_• DGI (Veliˇckovi´c et al., 2018b): a GCN encoder trained via graph mutual information maximization._

_• GraphCL (You et al., 2020): a contrastive learning method via four types of graph augmentation._

_• MVGRL (Hassani & Khasahmadi, 2020): a constastive learning method by contrasting encodings_
from first-order neighbors and a graph diffusion.

4.1.3 EVALUATION METRICS

Following (Donnat et al., 2018), we measure the performance of compared algorithms on the synthetic
datasets based on agglomerative clustering (with single linkage) with the following metrics

_• Homogeneity: conditional entropy of ground-truth among predicting clusters._

_• Completeness: ratio of nodes with the same ground-truth labels assigned to the same cluster._

_• Silhouette score: intra-cluster distance vs. inter-cluster distance._


-----

Table 1: Performance of compared algorithms on structure role identification with synthetic data.

Dataset Metrics DeepWalk node2vec RolX struc2vec GraphWave GAE VGAE ARGVA DGI GraphCL MVGRL NWR-GAE

Homogeneity 0.01 0.01 **1.0** 0.99 **1.0** **1.0** 0.25 0.28 **1.0** **1.0** **1.0** **1.0**
House Completeness 0.01 0.01 **1.0** 0.99 **1.0** **1.0** 0.27 0.28 **1.0** **1.0** **1.0** **1.0**
Silhouette 0.29 0.33 **0.99** 0.45 **0.99** **0.99** 0.21 0.19 **0.99** **0.99** **0.99** **0.99**

Homogeneity 0.06 0.03 **0.65** 0.21 0.52 0.36 0.29 0.24 0.24 0.41 0.63 **0.65**
House Perturbed Completeness 0.06 0.03 0.69 0.24 0.53 0.37 0.29 0.24 0.25 0.42 0.63 **0.72**
Silhouette 0.25 0.28 0.51 0.18 0.39 0.67 0.21 0.19 0.44 0.43 0.69 **0.94**

Homogeneity 0.26 0.24 0.91 0.63 0.87 0.65 0.50 0.66 0.36 **0.93** **0.93** **0.93**
Varied Completeness 0.23 0.22 0.93 0.58 0.88 0.69 0.36 0.57 0.37 0.89 0.89 **0.94**
Silhouette 0.35 0.40 0.82 0.24 0.66 0.66 0.21 0.23 0.94 0.93 0.90 **0.95**

Homogeneity 0.30 0.30 0.74 0.46 0.63 0.44 0.42 0.57 0.36 0.70 0.73 **0.78**
Perturbed & Varied Completeness 0.27 0.27 0.72 0.43 0.60 0.45 0.43 0.49 0.36 0.63 0.67 **0.81**
Silhouette 0.33 0.36 0.61 0.29 0.50 0.52 0.21 0.20 0.45 0.69 0.61 **0.84**

Table 2: Performance of compared algorithms on different types of real-world graph datasets.

|Col1|Proximity|Structure|Mixed|
|---|---|---|---|
|Algorithms|Cora Citeseer Pubmed|Cornell Texas Wisconsin|Chameleon Squirrel Actor|
|DeepWalk node2vec RolX struc2vec GraphWave GAE VGAE ARGVA DGI GraphCL MVGRL|82.97 ± 1.67 68.99 ± 0.95 82.39 ± 4.88 81.93 ± 1.43 64.56 ± 1.65 81.02 ± 1.48 29.70 ± 2.89 20.90 ± 0.72 39.85 ± 2.33 41.46 ± 1.49 51.70 ± 0.67 81.49 ± 0.33 28.83 ± 2.39 20.79 ± 1.59 20.96 ± 2.35 72.06 ± 2.54 57.10 ± 1.62 73.24 ± 0.88 72.87 ± 1.48 60.78 ± 1.92 81.34 ± 0.79 72.88 ± 3.83 63.36 ± 2.08 75.32 ± 0.63 84.76 ± 1.39 71.68 ± 1.54 84.29 ± 1.07 84.23 ± 1.51 73.51 ± 1.73 82.59 ± 0.71 86.23 ± 2.71 73.81 ± 1.53 83.94 ± 0.75|41.21 ± 3.40 41.89 ± 7.81 43.62 ± 2.46 40.54 ± 1.62 48.64 ± 2.92 36.27 ± 2.08 25.67 ± 11.78 42.56 ± 7.13 24.92 ± 13.43 23.72 ± 13.69 47.29 ± 7.21 24.59 ± 12.14 45.96 ± 2.20 37.45 ± 7.09 39.24 ± 5.16 45.40 ± 9.99 58.78 ± 3.41 34.11 ± 8.06 49.32 ± 9.19 39.18 ± 8.96 38.27 ± 6.12 41.08 ± 4.85 43.24 ± 5.38 41.17 ± 5.20 46.48 ± 7.97 52.97 ± 5.64 55.68 ± 2.97 44.86 ± 3.73 46.48 ± 5.85 53.72 ± 1.07 53.51 ± 3.26 56.75 ± 5.97 57.25 ± 5.94|68.03 ± 2.13 59.22 ± 2.35 23.84 ± 2.14 65.67 ± 2.31 48.29 ± 1.67 24.14 ± 1.02 22.75 ± 2.12 20.50 ± 1.18 25.42 ± 0.55 60.63 ± 2.90 52.59 ± 0.69 25.13 ± 0.79 17.59 ± 3.42 25.69 ± 0.53 27.29 ± 3.09 22.03 ± 1.09 29.34 ± 1.12 28.63 ± 1.05 20.17 ± 1.30 19.57 ± 1.63 26.41 ± 1.07 21.17 ± 0.78 20.61 ± 0.73 28.97 ± 1.17 25.89 ± 1.49 25.89 ± 1.62 20.45 ± 1.32 26.27 ± 1.53 21.32 ± 1.66 28.64 ± 1.28 58.73 ± 2.03 40.64 ± 1.15 31.07 ± 0.29|
|NWR-GAE w/o deg. NWR-GAE w/o Hun. NWR-GAE w/o dist. NWR-GAE full|79.75 ± 2.41 70.68 ± 0.51 81.04 ± 0.57 82.38 ± 2.11 68.95 ± 1.79 80.30 ± 0.36 80.67 ± 2.49 69.78 ± 2.42 81.13 ± 0.27 83.62 ± 1.61 71.45 ± 2.41 83.44 ± 0.92|54.05 ± 5.97 65.13 ± 6.79 65.09 ± 5.04 50.81 ± 4.44 67.59 ± 8.67 62.35 ± 4.88 49.72 ± 5.04 65.94 ± 6.53 68.12 ± 4.41 58.64 ± 5.61 69.62 ± 6.66 68.23 ± 6.11|70.54 ± 2.63 64.20 ± 1.07 29.57 ± 1.14 70.98 ± 2.05 62.63 ± 2.27 29.47 ± 1.32 71.64 ± 1.85 62.07 ± 1.41 28.59 ± 0.96 72.04 ± 2.59 64.81 ± 1.83 30.17 ± 0.17|



For the experiments on real-world graph datasets, we learn the graph embeddings with different
algorithms and then follow the standard setting of supervised classification. To be consistent across
all datasets in our experiments, we did not follow the standard semi-supervised setting (20 labels per
class for training) on Cora, Citeseer and Pubmed, but rather randomly split all datasets with 60%
training set, 20% validation set, and 20% testing set, which is a common practice on WebKB and
Wikipedia network datasets (i.e. Cornell, Texas, Chameleon, etc.) (Liu et al., 2020; Pei et al., 2020;
Ma et al., 2021). The overall performance is the average performance over 10 random splits. Due to
space limitation, we put details of the compared models and hyper-parameter settings in Appendix C.

4.2 PERFORMANCE ON SYNTHETIC DATASETS (RQ1)

We compare NWR-GAE with all baselines on the synthetic datasets. As can be observed in Table 1,
NWR-GAE has the best performance over all compared algorithms regarding all evaluation metrics,
corroborating its claimed advantages in capturing the neighborhood structures of nodes on graphs.

Specifically, (1) on the purely symmetrical graphs of House, NWR-GAE achieves almost perfect
predictions on par with RolX, GraphWave and GAE; (2) on the asymmetrical graphs of House
_Perturbed (by randomly adding or deleting edges between nodes), Varied (by placing varied shapes_
around the base circle such as Fans and Stars) and Varied perturbed, the performances of all
algorithms degrade significantly, while NWR-GAE is most robust to such perturbation and variance;
(3) among the baselines, proximity oriented methods of DeepWalk and node2vec perform extremely
poorly due to the ignorance of structural roles, while structural role oriented methods of RolX,
strc2vec and GraphWave are much more competitive; (4) GNN-based baselines of GAE, VGAE and
DGI still enjoy certain predictive power, due to the structure representativeness of their GIN encoder,
but such representativeness is actually impeded by their improper loss functions for structural role
identification, thus still leading to rather inferior performance.

4.3 PERFORMANCE ON REAL-WORLD DATASETS (RQ2)

All 11 baselines are included in the real-world datasets performance comparison. As can be observed
in Table 2, NWR-GAE achieves significantly better results compared to all baselines on all structureoriented and proximity-structure-mixed graph datasets, and maintains close performance to the best
baselines of DGI, GraphCL and MVGRL on all proximity-oriented graph datasets. Note that, most of
the strong baselines can only perform well on either of the proximity-oriented or structure-oriented
datasets, while NWR-GAE is the only one that performs consistently well on all three types. Such
results again indicate the superiority of NWR-GAE in capturing the structural information on graphs,
yet without significantly sacrificing the capturing of node proximity.


-----

Specifically, (1) Most GNN-based methods (both auto-encoder based, and contrastive learning based),
like GAE, VGAE, ARGVA, DGI and GraphCL only perform well on graphs with proximity-oriented
labels due to their strongly proximity-preserving loss functions, and perform rather poorly on most
graphs with structure-oriented and mixed labels; MVGRL achieves relatively better but still inferior
performance to ours on structure oriented datasets due to its structure aware contrastive training. (2)
the random walk based methods of DeepWalk and node2vec perform well mostly on graphs with
proximity-oriented and mixed labels; (3) the structural role oriented methods of RolX, struc2vec
and GraphWave perform rather poorly on graphs with proximity-oriented and mixed labels, and
sometimes also the structure-oriented ones, due to their incapability of modeling node features.

4.4 IN-DEPTH ANALYSIS OF NWR-GAE (RQ3)

In Table 2, we also compare several important ablations of NWR-GAE, i.e., the one without degree
predictor, the one without Hungarian loss (replaced by a greedy-matching based loss), and the one
without feature distribution reconstructor, which all lead to inferior performance on all datasets,
demonstrating the effectiveness of our novel model designs.

In Figure 4, we present results on hyper-parameter and efficiency studies of NWR-GAE. Embedding
size efficiency is an important metric for unsupervised representation learning, which reflects the
effectiveness in information compression. As can be seen in Figure 4 (a), NWR-GAE quickly converges
when the embedding size reaches 200-300 on the mid-scale datasets of Chameleon and Squirrel,
and maintains good performance as the sizes further increase without overfitting. Moreover, as we
can observe from the training curves of NWR-GAE on Chameleon in Figure 4 (b), the performance
of NWR-GAE is robust to the neighborhood sampling sizes, where the larger size of 15 only leads
to slightly better performance than the smaller size of 5. NWR-GAE also converges rapidly after
1-2 training epochs, achieving significantly better performance compared with the best baseline of
DeepWalk and typical baselines like DGI. As we can observe from the runtimes of NWR-GAE on
Chameleon in Figure 4 (c), smaller neighborhood sampling sizes do lead to significantly shorter
runtimes, while our runtimes are much better compared with typical baselines like DeepWalk and
DGI, especially under the fact that we can converge rather rapidly observed from Figure 4 (b).

Finally, to further understand the effectiveness of our proposed neighborhood Wasserstein reconstruction method, we provide detailed results on how well the generated neighbor features can approximate
the real ones in Appendix D. The results show that the method can indeed recover the entire real
neighbor features, and the approximation gets better as we use a larger sampling factor q especially
on larger datasets, while the performances on downstream tasks are already satisfactory even with
smaller q values, allowing the training to be rather efficient.

(a) Perf. vs. emb. sizes (b) Train curves vs. samp. sizes (c) Runtimes vs. samp. sizes

Figure 4: Hyper-parameter and efficiency studies of NWR-GAE

5 CONCLUSION

In this work, we address the limitations of existing unsupervised graph representation methods and
propose the first model that can properly capture the proximity, structure and feature information of
nodes in graphs, and discriminatively encode them in the low-dimensional embedding space. The
model is extensively tested on both synthetic and real-world benchmark datasets, and the results
strongly support its claimed advantages. Since it is general, efficient, and also conceptually wellunderstood, we believe it to have the potential to serve as the de facto method for unsupervised graph
representation learning. In the future, it will be promising to see its applications studied in different
domains, as well as its potential issues such as robustness and privacy carefully analyzed.


-----

REFERENCES

Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one
distribution from another. Journal of the Royal Statistical Society: Series B (Methodological), 28
(1):131–142, 1966.

Pierre Baldi. Autoencoders, unsupervised learning, and deep architectures. In ICML workshop on
_unsupervised and transfer learning, 2012._

Yoshua Bengio. Deep learning of representations for unsupervised and transfer learning. In ICML
_workshop on unsupervised and transfer learning, 2012._

Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank
graph neural network. In ICLR, 2021.

Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. Optimal transport for domain
adaptation. TPAMI, 39(9):1853–1865, 2016.

Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph
neural networks on non-attributed graphs. In KDD-DLG, 2021.

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. NeurIPS, 2013.

Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embeddings via diffusion wavelets. In SIGKDD, 2018.

Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent. Why does unsupervised
pre-training help deep learning? In Proceedings of the thirteenth international conference on
_artificial intelligence and statistics, 2010._

Haoqiang Fan, Hao Su, and Leonidas J Guibas. A point set generation network for 3d object
reconstruction from a single image. In CVPR, 2017.

Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya-Polo, and Tomaso A Poggio.
Learning with a wasserstein loss. In NeurlPS, 2015.

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural
message passing for quantum chemistry. In ICML, 2017.

Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.

Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD,
2016.

Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs.
In ICML, pp. 2434–2444. PMLR, 2019.

Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved
training of wasserstein gans. In NeurIPS, 2017.

Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In
_NeurlPS, 2017a._

William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and
applications. IEEE Data Engineering Bulletin, 40(3), 2017b.

Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on
graphs. In ICML, 2020.

Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu,
Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large
graphs. In SIGKDD, 2012.

Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural
networks. Science, 313:504–507, 2006.


-----

Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.
Strategies for pre-training graph neural networks. ICLR, 2020.

Roy Jonker and Anton Volgenant. A shortest augmenting path algorithm for dense and sparse linear
assignment problems. Computing, 38(4):325–340, 1987.

Diederik P Kingma and Max Welling. Auto-encoding variational bayess. In ICLR, 2014.

Thomas N Kipf and Max Welling. Variational graph auto-encoders. NeurIPS Bayesian Deep Learning
_Workshop, 2016._

Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In ICLR, 2017.

Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph
neural networks meet personalized pagerank. In ICLR, 2019.

Soheil Kolouri, Phillip E Pope, Charles E Martin, and Gustavo K Rohde. Sliced wasserstein autoencoders. In ICLR, 2018.

Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint
_arXiv:2005.14612, 2020._

Yulong Lu and Jianfeng Lu. A universal approximation theorem of deep neural networks for
expressing probability distributions. NeurIPS, 2020.

Liheng Ma, Reihaneh Rabbany, and Adriana Romero-Soriano. Graph attention networks with
positional embeddings. In PAKDD (1), 2021.

Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active
surveying for collective classification. In 10th International Workshop on Mining and Learning
_with Graphs, 2012._

S Pan, R Hu, G Long, J Jiang, L Yao, and C Zhang. Adversarially regularized graph autoencoder for
graph embedding. In IJCAI, 2018.

Giorgio Patrini, Rianne van den Berg, Patrick Forre, Marcello Carioni, Samarth Bhargav, Max
Welling, Tim Genewein, and Frank Nielsen. Sinkhorn autoencoders. In UAI, 2020.

Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric
graph convolutional networks. ICLR, 2020.

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In SIGKDD, 2014.

Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data
science. Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as
matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM, 2018.

Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep
convolutional generative adversarial networks. In ICLR, 2016.

Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node
representations from structural identity. In SIGKDD, 2017.

Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal
_of Complex Networks, 9(2):cnab014, 2021._

Han Shi, Haozheng Fan, and James T Kwok. Effective decoding in graph auto-encoder using triadic
closure. In AAAI, 2020.

Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semisupervised graph-level representation learning via mutual information maximization. In ICLR,
2020.


-----

Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve
graph contrastive learning. Advances in Neural Information Processing Systems, 34, 2021.

Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In
_SIGKDD, 2009._

Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto-encoders.
In ICLR, 2018.

Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual
information maximization for representation learning. In ICLR, 2020.

Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua
Bengio. Graph attention networks. In ICLR, 2018a.

Petar Veliˇckovi´c, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon
Hjelm. Deep graph infomax. In ICLR, 2018b.

Cédric Villani. Optimal transport: old and new, volume 338. 2008.

Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma,
Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang.
Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv
_preprint arXiv:1909.01315, 2019._

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 2019.

Yaochen Xie, Zhao Xu, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural
networks: A unified review. arXiv preprint arXiv:2102.10757, 2021.

Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstein learning for graph
partitioning and matching. NeurIPS, 2019a.

Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserstein learning
for graph matching and node embedding. In ICML, 2019b.

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In ICLR, 2019c.

Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation
through graph variational generative adversarial nets. In NeurIPS, 2019.

Carl Yang, Haonan Wang, Ke Zhang, Liang Chen, and Lichao Sun. Secure deep graph generation
with link differential privacy. In IJCAI, 2021.

Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph
contrastive learning with augmentations. NeurIPS, 2020.

Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In ICLR, 2020.

Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han. Transfer learning of
graph neural networks with ego-graph information maximization. In NeurIPS, 2021.


-----

A PROOF OF THEOREM 3.1

Theorem 3.1 can be obtained by properly revising Theorem 2.1 in (Lu & Lu, 2020). We first state
Theorem 2.1 in (Lu & Lu, 2020).

**Theorem A.1 (Theorem 2.1 in Lu & Lu (2020)). Let P and Q be the target and the source distri-**
butions respectively, both defined on R[m]. Assume that Ex _P_ _x_ is bounded and Q is absolutely
continuous with respect to the Lebesgue measure. It holds that for any given approximation error∼ _∥_ _∥[3]_ _ϵ,_
setting n = O( _ϵ[1][m][ )][, there is a fully connected and feed-forward deep neural network][ u][(][·][)][ of depth]_

_L = ⌈log2 n⌉_ and width N = 2L, with d inputs and a single output and with ReLU activation such
that W1(P, ∇u(Q)) < ϵ. Here, ∇u(·) is the function R[d] _→_ R[d] induced by the gradient of u while
_∇u(Q) is the distribution that is generated from the distribution Q through the mapping ∇u(·)._

To prove Theorem 3.1, we just need to verify the conditions in the above theorem. We need to show
that P = _v_ has a bounded Ex _P_ _x_, and Q as a non-degenerate m-dim Gaussian distribution
is absolutely continuous with respect to the Lebesgue measure. Also, the original statement is for P [(][i][)] _∼_ _∥_ _∥[3]_
1( _,_ ) while we use 2( _,_ ). We need to show the connection between 1( _,_ ) and 2( _,_ ).
_W_ _·_ _·_ _W_ _·_ _·_ _W_ _·_ _·_ _W_ _·_ _·_
Fortunately, all these aspects are easy to be verified.

_P = Pv[(][i][)]_ has a bounded 3-order moment because the support Pv[(][i][)] are in a bounded space of R[m].

_Q as a Gaussian distribution is absolutely continuous with respect to the Lebesgue measure, as long_
as Q is not degenerate.

Lastly we show the connection between 1( _,_ ) and 2( _,_ ). The support P = _v_ is bounded, i.e.,
_W_ _·_ _·_ _W_ _·_ _·_ _P_ [(][i][)]
_δ_ supp(P ), _δ_ 2 _B. According to Lu & Lu (2020), the Q =_ _u(_ ) also has bounded support.
Without loss of generality, ∈ _∥_ _∥_ _≤_ _δ_ supp(Q), _δ_ 2 _B. Then, we may show that ∇_ _G_
_∈_ _∥_ _∥_ _≤_

2 [(][P, Q][) =] inf 2[dγ][(][Z, Z] _[′][)]_
_W_ [2] _γ_ Γ(P,Q)
_∈_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][2]_ 

2B inf
_≤_ _γ_ Γ(P,Q)
_∈_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][2][dγ][(][Z, Z]_ _[′][)]_

2B[√]m inf
_≤_ _γ_ Γ(P,Q)
_∈_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][1][dγ][(][Z, Z]_ _[′][)]_

= 2B[√]m 1(P, Q) < 2B[√]mϵ.
_W_
As B and m are just constant, so we may have W2[2][(][P, Q][) =][ O][(][ϵ][)][. Note that the above first inequality]
is because ∥Z − _Z_ _[′]∥2 ≤∥Z∥2 + ∥Z_ _[′]∥2 = 2B. The second inequality is because_
_√m_ inf
_γ∈Γ(P,Q)_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][1][dγ][(][Z, Z]_ _[′][)]_

= lim _√m_ _Z_ _Z_ _′_ 1dγi(Z, Z _′)_
_i_ _∥_ _−_ _∥_
_→∞_ ZZ×Z _[′]_ 

(There exists a sequence of measures {γi}i[∞]=1 [achieving the infimum)]

lim
_≥_ _i_
_→∞_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][2][dγ][i][(][Z, Z]_ _[′][)]_

inf
_≥_ _γ_ Γ(P,Q)
_∈_ ZZ×Z _[′][ ∥][Z][ −]_ _[Z]_ _[′][∥][2][dγ][(][Z, Z]_ _[′][)]_

B ADDITIONAL DATASET DETAILS

In this section, we provide some additional important details about the synthetic and real-world
network datasets we use in the node classification experiments.

From table B, the node labels shows how the node are classified. For example, the node labels of
citation networks are academic topics, which is highly related to proximity information. But the
identity roles of website is more structural oriented since similar identity have similar hyperlinks
structure. Detailed statistics of the real-world graph datasets are provided in Table 4.


-----

Figure 5: Toy example of proximity and structure information: A and B are “close in proximity”
since they are relatively close in terms of node distances in the global network, whereas A and C are
“close in structure” since they have relatively similar local neighborhood structures.

(a) Houses on a Cycle (b) Perturbed (c) Varied (house, star, fan, etc.)

Figure 6: Synthetic dataset examples (Colors denote structural role labels and dashed lines denote
randomly adding or deleting edges)

C DETAILED SETTINGS OF THE COMPARED MODELS

**DeepWalk: for all datasets, we ran 10 random walks of length 40 and input these walks into a**
skipgram langauge model. We implement the DeepWalk method based on Python code (GPLv3
license) provided by Perozzi et al. (2014).

**node2vec: similar to DeepWalk, we also ran 10 random walks of length 40 with p and q equal to**
0.25. The implementation is provided by Grover & Leskovec (2016).

**RolX: by using Henderson et al. (2012)’s code, we set the initial learning rate as 0.01 and ran the**
algorithm with batch size 32.

**struc2vec: similar to DeepWalk and node2vec, we ran the same number of random walks with walk**
length 40. We set window size 5 as context size for optimization. The reference implementation is
provided by Ribeiro et al. (2017)

**GraphWave: the implementation is under the MIT license and provided by Stanford SNAP lab**
(Donnat et al., 2018). All the parameters are automatically determined by the algorithm itself.

**GAE: we use a two layer GCN as graph encoder for node classification task and a three layer GIN for**
synthetic structural identification task. The decoder hyperparameters are selected by cross-validation,
the implementation is based on the code provided by Kipf & Welling (2016)

**VGAE: same encoder structure and similar decoder as GAE, the implementation is also based on**
Kipf & Welling (2016).

**ARGVA: same encoder structure as GAE and VGAE. We use the Tensorflow implementation based**
on the implementation of Pan et al. (2018).

**DGI: same encoder structure as GAE and VGAE, the initial number of epochs is 10000 but may**
early stop when the algorithm is converged. We use the DGI method based on the implementation of
Veliˇckovi´c et al. (2018b).

|Col1|Table 3: Real-world network datasets description|
|---|---|
|Datasets|Type Nodes Edges Node Features Node Labels|
|Cora Citeseer Pubmed|Citation Networks Papers Citations Bag-of-words of papers Academic topics|
|Cornell Texas Wisconsin|WebKB Web pages Hyperlinks Bag-of-words of web pages Identity roles (Student, Project, etc.)|
|Chameleon Squirrel|Wikipedia Network Web pages Mutual links Informative nouns Number of monthly traffic|


-----

Table 4: Statistics of the real-world graph datasets.

|Task type|Proximity|Structure|Mixed|
|---|---|---|---|
|Dataset|Cora Citeseer Pubmed|Texas Wisconsin Cornell|Chameleon Squirrel Actor|
|Nodes Edges Features Classes|2708 3327 19717 5429 4732 44338 1433 3703 500 7 6 3|183 183 251 295 309 499 1703 1703 1703 5 5 5|2277 5201 7600 36101 217073 33544 2325 2089 931 5 5 5|



**GraphCL: use the default encoder GraphSage and all the four different types of augumentation. The**
implementation is based on You et al. (2020).

**MVGRL: the same default GCN encoder as GAE, We use the PyTorch implementation of Hassani &**
Khasahmadi (2020).

**NWR-GAE: same encoder structure as the above GNN-based methods, learning rate, trade-off**
weight between degree loss and neighborhood reconstruction loss and sample size q are tuned using
grid search.

**Encoder setting. We used the same GCN encoders for almost all baselines because our contribution**
in this work is on the decoder and we wanted to be fair and focus on the comparison of different
decoders. Specifically, we use the default encoders in their original work for all baselines that
involve GNN encoders (GraphSAGE (Hamilton et al., 2017a) for GraphCL (You et al., 2020), GCN
(Kipf & Welling, 2017) for GAE (Kipf & Welling, 2016), VGAE (Kipf & Welling, 2016), DGI
(Veliˇckovi´c et al., 2018b), MVGRL (You et al., 2020)). The GCN encoders all have the same twolayer architecture, which is the same as we used for NWR-GAE. In our experiments, we have actually
tried to use other GNNs as the encoders for all methods including NWR-GAE and the baselines, but
found GCN to have the best performance. For example, in the following Table C, we provide the
results of GAE with the GIN (Xu et al., 2019c) and GraphSage (Hamilton et al., 2017a) encoders,
which are clearly worse than that with GCN.

**Hyper-parameter tuning. For all compared models, we performed hyper-parameter selection on**
learning rate {5e-3, 5e-4, 5e-5, 5e-6, 5e-7} and epoch size {100, 200, 300, 400, 500, 600}. For
NWR-GAE, we selected the sample size q from {3, 5, 8, 10}, and the trade-off weight parameters
_λd, λs from {10, 1, 1e-1, 1e-2, 1e-3, 1e-4, 1e-5}._

**Notes on fairness. We set all random walk based method (DeepWalk, node2vec, struc2vec) with**
same number of random walks and walk lengths. For all graph neural network based methods (GAE,
VGAE, DGI, NWR-GAE), we use the same GCN encoder with same number of encoder layer from
DGL library (Wang et al., 2019). For the node classification task, all methods use the same 4-layer
MLP predictor with learning rate 0.01. For all settings, we use Adam optimizer and backward
propagation from PyTorch Python package, and a fix dimension size as same as the graph node
feature size. Most experiments are performed on a 8GB NVIDIA GeForce RTX 3070 GPU.

|Col1|Table 5: Selected baseline with different encoders|
|---|---|
|Algorithms|Cornell Texas Wisconsin Chameleon Squirrel Actor|
|GAE w/GCN GAE w/GIN GAE w/GraphSage|45.40 ± 9.99 58.78 ± 3.41 34.11 ± 8.06 22.03 ± 1.09 29.34 ± 1.12 28.63 ± 1.05 39.33 ± 4.17 53.30 ± 2.75 32.84 ± 3.94 24.99 ± 2.56 23.46 ± 1.04 25.34 ± 1.43 44.97 ± 4.61 47.29 ± 5.43 37.25 ± 6.25 22.97 ± 1.29 20.05 ± 0.34 28.34 ± 0.51|



**Notes on neighborhood sampling. due to the heavy tailed nature of node distribution, we down**
sample the number of neighbors in NWR-GAE method. We only sampled at most 10 neighbors per
node. This provides a good trade-off between efficiency and performance, which makes the method
have reasonable running time on one GPU machine and also achieve great enough accuracy.

D ADDITIONAL EXPERIMENTAL RESULTS

To further understand the effectiveness of our proposed neighborhood Wasserstein reconstruction
method, we provide detailed results on how well the generated neighbor features can approximate the
real ones.

Specifically, for every node v, to reconstruct k-hops neighborhood, the model will sample q neighbor
nodes fromembeddings of v’s neighbor. Next the model gets Nv in layer i, where 0 ≤ _i ≤_ _k, thus { qh samples[(]v[i]j[)][|][1][ ≤]_ _[j][ ≤]ξj,[q] 1[}][ denotes the q ground truth]j_ _q_ from Gaussian
_{_ _≤_ _≤_ _}_


-----

distribution parameterized by GNN encoder, and uses an FNN-based transformation _h[(]v[i,j][)]_ =
_{[ˆ]_
FNN[(][i][)](ξj)} to reconstruct h[(]v[i]j[)][.]

Based on above, we create x-y pairs with

_x =_ _qj=1[(][||]h[ˆ][(]v[k,j][)]||[2])_ _,_

_q_

P

_y =_ minπ:[q]→[q] _ik=0−1_ _qj=1_ _[||][h]v[(][i]j[)]_ _[−]_ _h[ˆ][(]v[i,π][(][j][))]||[2]_ _._

_q_ _k_

P P ·

Table 6: Box-plot like approximation power table.

|Dataset|5% 25% 50% 75% 95% q|
|---|---|


|Cornell|0.0086 0.0336 0.0618 0.0822 0.1095 5 0.0089 0.0344 0.0617 0.0813 0.1130 15 0.0027 0.0398 0.0848 0.1204 0.1436 30|
|---|---|


|Texas|0.0025 0.0477 0.0869 0.1304 0.1792 5 0.0078 0.0559 0.0897 0.1445 0.1828 15 0.0077 0.0285 0.0489 0.0869 0.1048 30|
|---|---|


|Wisconsin|0.0060 0.0472 0.0723 0.0966 0.1451 5 0.0364 0.0526 0.0671 0.0848 0.1080 15 0.0124 0.0529 0.0716 0.0946 0.1398 30|
|---|---|


|Chameleon|0.1590 0.2587 0.3183 0.3858 0.5067 5 0.0958 0.1180 0.1504 0.2120 0.2704 15 0.0423 0.0624 0.0884 0.1384 0.2272 30|
|---|---|



In Table 6, we ranked all x-y pairs by the ratio, and presented the ratio at 5%, 25%, 50%, 75%, 95%
(like a box-plot). As we can observe, our model can get a reasonably good approximation to the
ground-truth neighborhood information (the smaller the better approximation). We tried different
sample sizes q such as 5, 15, 30, which do not make a large difference in the first three datasets
since most nodes in the graphs have rather small numbers of neighbors. Our model shows better
approximation power on the neighborhood information with larger sample sizes such as Chameleon
with denser links. However, the performances on downstream tasks are already satisfactory even
with smaller q values (the results we show in Table 2 are with q = 5, and the results we show in
Figure 4 (b) are with q = 5, 10, 15). This indicates that while our model has the ability to more
ideally approximate the entire neighborhood information, it often may not be necessary to guarantee
satisfactory performance in downstream tasks, which allows us to train the model with small sample
sizes and achieve good efficiency.

To better understand the effect of number of GNN layers k in our proposed model, we vary k from 1
to 5 on the synthetic dataset of “House”. The model performance only gets better when k grows over
3, because the important graph structures there cannot be captured by GNNs with less than 3 layers.
Motivated by such observations and understandings, we set k to 4 for all real-world experiments,
which can empirically capture most important local graph structures, to achieve a good trade-off
between model effectiveness and efficiency.

|The effect of k (ex|xemplified on the synthetic dataset of|
|---|---|
|Metrics|k=1 k=2 k=3 k=4 k=5|
|Homogeneity Completeness Silhouette|0.89 0.94 0.99 1.0 1.0 0.92 0.93 1.0 1.0 1.0 0.88 0.87 0.91 0.99 0.98|



To gain more insight into the behavior of different unsupervised graph embedding methods, we
visualize the embedding space learned by several representative methods on Chameleon in Figure 7
(reduced to two-dimensional via PCA). As we can observe, in these unsupervised two-dimensional
embedding spaces, our baselines of node2vec, struc2vec, GraphWave, GAE and DGI can hardly
distinguish the actual node classes, whereas NWR-GAE can achieve relatively better class separation.
Note that since all algorithms are unsupervised and the visualized embedding space is very lowdimensional, it is hard for any algorithm to achieve perfectly clear class separation, but NWR-GAE


-----

can capture more discriminative information and deliver less uniform node distribution, which is
more useful for the node classification task as consistent with our results in Table 2.

(a) node2vec (b) struc2vec (c) GraphWave

(d) GAE (e) DGI (f) NWR-GAE

Figure 7: Embedding spaces reduced to two-dimensional through PCA on Chameleon dataset.


-----

