Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction
Authors: Mingyue Tang
Pan Li
Carl Yang
Venue: ICLR 2022 Poster (2022)
Keywords: graph representation learning
unsupervised learning
autoencoder
wasserstein distance

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.

Published as a conference paper at ICLR 2022
GRAPH AUTO-ENCODER VIA NEIGHBORHOOD WASSERSTEIN RECONSTRUCTION
Mingyue Tang'; Carl Yang"; Li
Department of Engineering Systems and Environment, University of Virginia
2 Department of Computer Science, Emory University
3 Department of Computer Science, Purdue University ut dtd8hjer jeeehhevirgnnaa edu, j carlyang@emory...mo edu, panli@purdue.
ABSTRACT
Graph neural networks (GNNs) have drawn significant research attention recently, mostly under the setting of semi-supervised learning. When task-agnostic rep- resentations are preferred or supervision is simply unavailable, the auto-encoder framework comes in handy with a natural graph reconstruction objective for un- supervised 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. this work, we revisit the graph encoding process of GNNs which essentially learns to encode the neighborhood information of each node into embedding vector, and propose novel graph decoder reconstruct the entire neighborhood information regarding both proximity and structure via Neighbor- hood Wasserstein Reconstruction (NWR). Specifically, from the GNN embedding of each node, NWR jointly predicts its node degree and neighbor feature distribu- tion, where the distribution prediction adopts an optimal-transport loss based on the Wasserstein distance. Extensive experiments 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-orient ones
INTRODUCTION
Network/Grrphh representation learning (a.k.a. embedding) aims preserve the high-dimensional complex graph information involving node features and link structures in a low-dimensional em- bedding 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 remi-supervised fashion (Kipf Welling 2017: Hamilton et al., 2017a Wu et al., 2019: Veličković et al.) [2018a] Klicpera et al.
2019] Chien et al. [dl1]202.) 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. [0200] Xie
(ct al. 202I), but also agssstio 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 Good fellow al. 2016) provides natural solution and has been widely explored such as the prominent work (V) GAE Kiipf& & 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 motivation and are designed 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 the non-trivial design 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.
"qqual contribution. 'Corresponding author.
Code available //httpa://gi wttph/ww.oooooooooooooooooeeeeee 2241///////////-GA

---

Published as a conference paper at ICLR 2022
Feature-wise clusters
Proximity-wise clusters
Structure-wiss clusters
GraphWave (Donnat et al.)
GAE (Kipf Welling)
NWR-GAE (ours)
Figure I: 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 as an example, where different types of information are mixed in a graph (e.g., proximity and structure information illustrated in Figure 5 in Appendix (Cui al. (001)). The node representations learned by existing graph auto-encoders such as GAE (Kipf & Welling 2016) are driven too much 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-orient
embedding models like Graph Wave (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 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- neighbor-represenn representttrnnnn 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, neighbor- representation distribution reconstruction, we adopt an aptimal-transpea distance (Frogner et al., 2015) and thus name this new framework Neighborhood Wasserstein Reconstruction Graph Auto-Encodes (NWR-Ga GGE). As also illustrated in Figure | NWR- GAE can effectively distinguish all pairs of nodes dissimilar in different perspectives, and concisely reflect their similarities in the low-dimensional embedding space.
loss based on Wasserstein
We have conducted extensive experiments 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 mrxiintty-structure-nn brought by NWR -AE over the best method among the state-of-the-art baselines on all structure- oriented tasks (8.74% to 18.48%) and proximity-structtre--ii competitive performance on proximity- -rrented tasks (-3.21% % to -0.32%). In-depth ablation and haper-parameter studies further consolidate the claimed advantages of NWR-GAE.
tasks. We can observe significant improvements
tasks (-2.98% 8.62%), and
2 PRELIMINARIES MOTIVATIONS & OTHER RELATED WORKS
In this work, we focus on the auto-encoder framework for unsupervised task-agnostic graph repre- sentation learning. The original motivation of auto-encoders is to perform neural-network-bne dimension reduction of the data that originally lies in high-dimensional space (Hinton Salakhutdi nov] 2006). Specifically,
auto-encoder consists of two components, encoder and decoder. The encoder works to compress each data point into low-dimensional vector representation, while the decoder works to reconstruct the original information from this vector. By minimizing the reconstruc-
2

---

Published as a conference paper at ICLR 2022
Two GNN layers
1-hop neighborhood
hg (2) obtained via two GNN layers has the Information from 2- 2-hop neighborhood of v. Figure 2: The information source/receptive field of the node representation (2)
2-hop neighborhaod
tion error, the encoder automatically converges to a good compressor that allows the low-dimensional representations to capture 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-structure' data, information of data points (nodes to be specific as most widely studied) is correlated due to the ambient graph structure. Without specific task needed in priori, the learned low-dimensional representation of node should carry as much information as possible from not only its own features but also the features of the nodes connects (both directly and indirectly).
This implies that when building auto-encoders for graph-structure data, we expect the node represen- tations to be able reconstruct all correlated node features. However, existing graph auto-encoders seem to be away from this motivation. Previous prominent works such as unsupervised Graph- SAGE (Hamilton al., 2017a). GAE (Kipf & Welling 2016), their generative variants such as VGAE Kiipf & Welling, 2016)) CondGen (Yang et al. (2019) O. 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 & Leskoved 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
To better understand this point, we carefully analyze the source of information encoded in each node representation via GNN. Suppose a standard message- paassagg GNN (Gilmer et al. (017)) 7) is
adopted as the encoder, which is general framework that includes GCN (Kipf & Welling (017)) GraphSAGE (Hamiltnn al. 2017a), GAT (Veličković et al.) 8a). GIN (Xu et al., (009cc) and so on. After k-hop message passing, the source of information encoded in the representation of node essentially comes from the k-hop neighborhood of (Fig. ( Therefore, a good representation of node should capture the information of features from all nodes in its k--hpp neighborhood, which is agnostic to downstream tasks. Note that this may not ideal as nodes out of k-hhop 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 Sec.
Relation to the InfoMax principle. Recently. DGI (Veličković al. 2018b), EGI (Zhu al. 2021) and others (Sun et al. 2020 Hu et al., 22200] You et al.) 2020) Hassani & Khasahmadi 2020 Suresh 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 (InfoMaxx) which essentially works to maximize certain correspondence between the learned representations and the original data. For example, DGI (Veličković et al. (018b) 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 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.
3

---

Published as a conference paper at ICLR 2022
Encoder
Pr. Pa. m. Po sample neighbors
min
decode neighborhood
H %
4/P
FMNN,
FNN
f2 sm - Gaussion((H..
hg
(0)
D
(0)
(1)
D
(1)
h
decode degree
(o. the ((421)
loss
decode initial feature
11 vs (A.5)) IP
hp
hp
hpp
Decoder
Figure The diagram of our model using an example with 2 GNN layers as the encoder.
aptimal-transppe (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. (020). But one should note the work is not graphedata-oriented generalization of these works: They use OT-losses to characterize the distance between the variational distribution and the data empirical distribution while our model even does use 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 frequently-used OT loss based on 2- Z-Wassesstein distance that will be used later.
Definition 2.1. Let P, Q denote two probability distributions with finite second moment defined on 2 C Rm The 2- Wasserstein distance between PP and Q defined on 2, 2' C Ihm is the solution to the optimal mass transportation problem with & transport cost (Villani 2008
inf / (PI @) 2x2'
1/2
W2 Q)
IZ Z (z,
(1)
where I(P, Q) contains all joint distributions of (Z, Z") with marginals P and Q respectively.
METHODS
3.1 NEIGHBORHOOD RECONSTRUCTION PRINCIPLE (NRP)
Let G FV X) denote the input graph where V is the node set, F. is the edge set and X {rr|v E V) includes the node features. Given a node v E V. we define its k-hop neighborhood as the nodes which have shortest paths of length no greater than & from Let N₂ denote the 1-hop neighborhood of v, and d, denote the degree of node c.
We build an auto-encoder to learn low-dimensional representation of each node. Specifi- cally, the auto-encoder will have an encoder á and a decoder sb. & could be any message-passing GNNs (Gilmer et al. 2017). The decoder further contains three parts &i (v)., spp vsa). 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 (0) based on X. For every node v E V, after being encoded by one GNN layer, its node representation (1) collects information from (0) and its neighbors' representations 11 (1 |u E N.). Hence, we consider the following principle that reconstructs the information from both a and ( Therefore, we have
min Σ M(( H ((()))) s.t. A Φ(h HH Vu E V. 6.0
(2)
VEV
4

---

Published as a conference paper at ICLR 2022
where M(.-) defines the reconstruction loss. M can be split into two parts that measure self-featur reconstruction and neighborhood reconstruction respectively:
M((h,) H. H2) (((")) (h. (h.")) + (
(3)
Note that MM works just as the reconstruction loss of a standard feedforward neural network (FNN)- based auto-encoder, so we adopt
M, (h.g)) = | v.. (A."0)1
(4)
Mn. is much harder to characterize, as it measures the loss to reconstruct set of features (0) There are two fundamental challenges: First, as in real-world networks the distribution of node dégrees 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 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 u the neighborhood information represented as an empirical realization of i.i.d. sampling d, elements from P(", where p! _
d. EuEN, 6/00
Based on this view, we are able to decompose the reconstruction into the part for the node degree and that for the distribution respectively, where the various sizes of node neighborhoods handled properly. Specifically, we adopt
Mn X. (h.")) (d, (d, ba(hh))))))))) (2(P (h.))
(5)
where (2(+,-) -) is the 2- 2-Wasserstein distance as defined in Eq objective for first-hop neighborhood reconstruction.
1 Plug Eqs 4 into Eq we obtain the
Generalizing to k-hop neighborhood reconstruction. Following the above derivation for the first- hop case, can similarly generalize the loss for reconstructing (h.) (i-1), H(-")) based on (i) for all 1 S & k. Then, if we sum such losses over all nodes v E V and all hops 1 I i S k, we may achieve the objective for k-hop neighborhood reconstruction. We may further simplify such an objective. Typically, only the final layer representation representations. Too many intermediate hops make the model hard to train and slow to converge. Therefore, adopt more economic way by merging the multi-step reconstruction:
(K) is used the output dimension-reducee
(1)) ho
(k-1) 7 Ryp Mip
(1) + h (0)
hg
H (k-1)
No H
(K--2) > (1(0)
H
(k 1)
H (k-2)
H
(0) No
Nr
That is, we expect h to directly reconstruct H even if i < k - 1. Specifically, for each node v E V, we use the reconstruction loss
R-1
(M((N (H 1o sisk ((())) Ma ((h())) + Σ
Mn (H ((H)))))))))))
1=0
= - - + Aa(de - (a(h(()))2
Cg (n())))
(6)
2=0
where v. is to decode the initial features, va is to decode the degree and w/ 0 < i is to decode the i-layer neighbor representation distribution !!! + ΣnEN, ), X and \ are non-negative hyperparameters. Hence, the entire objective for k-hop neighborhood reconstruction is
min 6.10
Σ (( (H(- S SisAi k)), (T())) s.t. H 2000 (H(- sisk. k. (7)
NEV
where á (010) < < k) include GNN layers and M' defined in Eq
Remark 3.1. The loss in Eq. 6 not directly push the k-layer representation h to reconstruct the features of all nodes that are direct neighbors but lie in k-hop neighborhood of However, by definition, there exists a shortest path of length no greater than from 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. o i.c., the objective in Eq. 7 This guarantees that the optimization in Eq. pushes (k) (k)
reconstruct the entire h-hop neighborhood of e.
5

---

Published as a conference paper at ICLR 2022
3.2 DECODING DISTRIBUTIONS DECODERS 1/2 . v
Our NRP essentially represents the node neighborhood H N as sampling number (node degree d.))
plus distribution of neighbors' representations p( (Eqs 5 We adopt Wasserstein distance to characterize the distribution reconstruction loss because P has atomic non-zero measure supports in a continuous space, where the family of f-divergences such as KI--divergence cannot be applied. Maximum mean discrepancy may be applied but it needs to specify kernel function.
We set the decoded distribution 2/p" (hi as an FNN-based transformation a Gaussian distribution parameterized by 1e The rationale of this setting is due to the universal approximation capability of FNNs to (approximately) reconstruct any distributions in 1- I-Wasserstein distance, as formally stated in Theorem 3.1 (See the proof in Appendix reproduced by Theorem 2.1 in (Lu & Lu 2020)). For a better empirical performance, our case adopts the 2- 2-Wasserstein distance and an FNN with m-dim output instead of the gradient of FNN with 1-dim outout. Here, the reparameterization trick needs to be used (Kingma & Welling 2014), i.c.,
( ()) FN (S), 5 ~ N(uu; E.,), where jt, = FNN, (h!h)), E., = (FNggexpPFNNN.(11
Theorem 3.1. For any >> 0, if the support of the distribution P(() lies in a bounded space of RT, there exists a FNN u(-) : RT - IR (and thus its gradient Vu(.): Ihm - "R"" with large enough width and depth (depending on e) such that W2 Vw(g)) < where Vu(g) is the distribution generated via the mapping Vu(g). & ~ a m-dim non-degenerate Gaussian distribution.
(1) A further challenge is that the Wasserstein distance between p!d) and vp (hi does not have closed form. Therefore, we adopt the empirical Wasserstein distance that can provably approximate the population
stated in Sec.8.4.1 in (Peyré et al. 2019). For every forward pass, the model will get q sampled nodes N₁, denoted by U1, U2, M..,... Ug and thus (n.) S S 4) are q samples from P! Next, get g samples from (uu, E,), denoted by E2, Eg- and thus (K65)) F p (E)) S j S 4} are samples from wi (he ); Adopt the following empirical surrogated loss of Σ/ W up (0) (he ()) in Eq
A-1 9
min 1=0
R (()
12, S.L. æ is a bijective mapping:(4] [q] + [q]
(8)
Computing the above loss is based on solving matching problem and needs the Hungarian algorithm with O(q²) complexity (Jonker & Volgenant 1987). More efficient types of surrogate loss may be adopted, such as Chamfer loss based on greedy approximation (Fan al. 2017) or Sinkhorn loss based on continuous relaxation (Cuturi 2013). whose complexities are O(q" In our experiments, as q is fixed as a small constant, say 5, we use Eq g based on 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 Borrowing such a concept, one can view our OT-loss also to measure the distance between the original graph and the decoded graph.
3.3 FURTHER DISCUSSION DECODERS vh, AND Vid
The decoder ah, to reconstruct the initial features (0) is an FNN. The decoder ehe to reconstruct the node degree is FNN plus exponential neuron to make the value non-negative.
(a(()(()) cxp(FNN,(h!*)) 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 (0))) However, (0) is used in both representation learning and reconstruction, it has the risk to collapse to trivial points. Hence, we normalize ( { E V} properly via pair-norm (Zhao & Akoglu 2020) to avoid this trap as follows
(M(()) = FNN, (A(()), FNN,(A(*)),
(9)
(n(0) lo E V} pair-norm( W V}), where W is learnable parameter matrix.
(10)

---

Published as a conference paper at ICLR 2022
4 EXPERIMENTS
We design our experiments to evaluate NWR-GAE, focusing on the following research questions: RQI: How does NWR-GAE perform structure-role-based synthetic datasets in comparison to state-of-the-arr 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 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 (ct al., at.l. 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-rok labels for nodes in the graphs in the Real-world graph Datasets. We use a total of nine public real-world graph datasets, which roughly belong three types, one with proximity-oriente ceuuture--rientee (disassortative) labels, and one with proximity-structure--me mixed labels. Among them, Cora, Citeseer, Pubmed are publication networks (Namata et al. 20012;; Cornell, Texas, and
way as (Donnat et al. (0018).
(assortative (Liu et al. 2020) labels, with
Wisconsin are school department webpage networks (Pei et al. (020);; 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 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).
Welp (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 Skipgram language model.
node2vec (Grover & Leskoved 2016): method similar to DeepWalk but uses two hyper-paramter p and g 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.
struc2vee (Ribeiro et al.] (017):: graph structural embedding method that encodes the structural similarities of nodes and generates structural context for each node.
Graph Wave (Donnat et al. 2018): graph structural embedding method that models the diffusion of a spectral graph wavelet and learns embeddings from network diffusion spreads.
GAE (Kipf & Welling 2016): GCN encoder trained with link reconstruction decoder.
VGAE (Kipf & Welling 2016): the variational version of GAE.
ARGVA (Pan et al., 2018): method which considers topological structure and node content,
trained by reconstructing the graph structure.
DGI (Veličković et al. 2018b): 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): constastive learning method by contrasting encodings
from first-order neighbors and a graph diffusion.
4.1.3 EVALUATION METRICS
Following (Donnat et al. 2018), measure the performance of compared algorithms the synthetic datasets based on agglomeratio 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.
7

---

Published as a conference paper at ICLR 2022
Table I: Performance of compared algorithms structure role identification with synthetic data.
Dataset
Meniic
DeepWall
node2vee
RolX
strccvee
GiuphWWave
GAB
VGAB
ARGVA
DG
GraphCt
MVGRL
NMB-GAE
Homogeneely
[0]]
1,8
0:39
1.0
1.8
0.25
0.23
1.0
1.3
13
1.0
House
Completenees
0.01
0.01
1,9
0.99
1.0
1.0
0.27
0.28
1.0
1.0
1.0
1,0
Silhouene
0.29
0.35
0.99
0.45
0.99
0.99
0.21
0.19
0.99
0.89
0.99
0.99
Homogeenclly
1725
1145
0.21
0.22
0.36
0.29
0.23
0.21
0.41
1053
0.63
House Pentrbee
Completeeesi
0.06
0.63
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.39
0.44
0.43
0.69
0.54
Honogenecty
0.26
0.24
0.1
050
0.87
0.3
0.30
0.56
0.35
0.33
0.93
0.93
Varied
Completeness
0.25
0.22
0.93
0.58
0.88
0.68
0.36
0.57
0.57
0.89
0.89
0.94
Silhoustte
0.35
0.40
0.82
0.24
0.66
0.66
0.21
0.25
0.94
0.93
0.90
6.95
Honogeenclly
01300
11:00
1274
0346
010
0.44
0.42
0.37
0.35
0.70
1073
0.75
Peturbed& & Varied
Completeness
0.27
0.27
0.72
0.4
0.50
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.
Proxmiy Creauer
Straeture Texcss
Mineed Squareel
Algorithms
Cora
Pubmed
Cornell
Wiscomsin
Chameleon
Actor
WaepWWal
58. C21 1205
52 52.0322
1.85
41.21 3.45
41.50 7:31
11.02 2:20
58.00 2:15
V9.22 2:15
2:34
81 0933-11
1.43
6n 50 1005
61. (22
1.15
10.54
1.02
18. 03.61
2.522
56.27
2.05
65 67.67 2:51
10. 20
1.67
24:
1.00
RaIX
29.70 8 2.50
20.50 0.72
50. 03.85-1
2:55
25.07
18.75
42. 50
7.15
21.02
13:43
22:
73 = 2.12
20.50
1.18
25.
05.
0.56
Stru:2exx
41 8: 1.49
51.70 8: 0.07
$1.49
0.85
23.72
13.00
47:20 0: 7:21
21.50
# 12.14
60.63 2.90
52.50
0.60
25.13
0.77
GrapkiWave
28.88 4: 2.30
20.79
1.50
20.96
2.85
45.96
= 2.20
57.45 8: 7.00
59.24
5.16
17:50 = 3.42
25.00
0.58
27:29
3.00
GAE
72.06 4: 2.54
57.30 8: 1.62
78.24
0.85
45.40
= 5.00
58.78 3.41
54.11
5.05
22.00 8: 1.09
29.34
1:12
25.65
1.06
VGAE
7287 4: 1.45
60.77
1.02
51.34
0.75
40.32
9.19
30.18 5.96
58.27
6.12
20.17 2: 1.30
19.07
1.63
26.41
1.07
ARGVA
72885 8: 31.53
63:36
2.08
70.32
0.63
41.00
4.85
41.24 3.38
41.37
5.20
21.17 0.778
20.61
0.77
05.07 1.17
84.
1.30
71.68
1.54
84:20
5.64
2.97
25.80
1.00
25.89
1.62
20.45
GuayCCL
84
1.51
78.51
1.78
82.50
41.55
66.48 3,85
1.07
26.27
1.63
21.82
1.66
28.64
1.38
MVGRL
2.71
78.81
53.91
50.51
56.75
5.97
57.25
5.94
58.73
2.03
40.04
1.15
31
BMR--CA deg.
0076 2.41
7028
51.04 0.57
50.05
6.79
2.63
1.07
1:34
BAR-CAE
82.08
68.55
1.79
0.36
50.81
67.50
8.07
02.35
2.00
02.63
2.27
1.32
EMR-CRE
8007
69.78
2.42
S1.13
40.72
63.94
5.53
02.07
0.50
IMR-GRE
83.02
71.45
83.44
58.64
72.04
64.81
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 al. 2020 Pei al. 2020
Ma et al. 202T). The overall performance is the average performance over 1O random splits. Due to space limitation, we put details of the compared models and slyper-paramend settings in Appendix C
4.2 PERFORMANCE ON SYNTHETIC DATASETS (RQ1)
We compare WWR-GAS with all baselines on the synthetic datasets. As can be observed in Table [ NWR-GAR 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, Graph and GAB; (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, stre2vec and GraphWav 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 NWR-GAE achieves significantly better results compared to all baselines on all structure- oriented and proximity-structtrr-mii
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-orienter or cenectrr--orenntr 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.
8

---

Published as a conference paper at ICLR 2022
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-orien -rriened labels due to their strongly proximity-preseriing loss functions, and perform rather poorly most graphs with structure-oriented and mixed labels; MVGRI. achieves relatively better but still inferior performance
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 mroximity-oriente and mixed labels; (3) the structural role oriented methods of RolX, struc2vec and Graph Wave perform rather poorly on graphs with proximity-orient and mixed labels, and sometimes also the sruccurre-rientee ones, due their incapability of modeling node features.
4.4 IN-DEPTH ANALYSIS OF NWR-CAE (RQ3)
In Table 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 wrtchigg based loss), and the one without feature distribution reconstructor, which 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 important metric for unsupervised representation learning, which reflects the effectiveness information compression. As can be seen in Figure NWR GAE quickly converges when the embedding size reaches 200-300 and maintains good performance as the sizes further increase without overfitting. Moreover, as we can observe from the training curves of NWR-GAE Chameleon in Figure (b), the performance of NWR-GAE 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-GAF, 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 NWR-GB 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 Deep Walk and
the mid-scale datasets of Chameleon and Squirrel,
DGI, especially under the fact that can converge rather rapidly observed from Figure 4 (b).
Finally, to further understand the effectiveness of our proposed neighborhood Wasserstein reconstruc- tion 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 larger sampling factor q especially on larger datasets, while the performances on downstream tasks are already satisfactory even with smaller values, allowing the training to be rather efficient.
1900
Size:
1000
Deepriesk (sonvercence)
Sample Size:
Time
50C
BGI (convengencca)
DeecWWll (convergence)
BGG (convergence)
0.00
Deteset: Squirre
Dataset: Chameleon
206
0.55
Dimansion
Epoch
Epoch
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
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 well- understood, we believe it to have the potential to serve the de facto method for unsupervised graph representation learning. In the future, it will be promising to see its applications studied in different domains, well as its potential issues such robustness and privacy carefully analyzed.

---

Published as a conference paper at ICLR 2022
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 (Methodological) 28 (1):131-12,, 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):1833-1865 2016.
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neural networks non-attributed graphs. In KDD-DLG, 2021.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. NewrIPS, 2013.
Claire Donnat, Marinka Zitikk, David Hallac, and Jure Leskovec. Learning structural node embed- dings 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 single image. In CVPR, 2017.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya-Polo, and Tomaso A Poggio. Learning with a wasserstein loss. In NewrlPS, 2015.
Justin Gilmer, Samuel 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 NeurlPS, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017a
William 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 graphs. ICML, 2020.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. SIGKDD, 2012.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313:504-507, 2006.
10

---

Published as a conference paper at ICLR 2022
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- 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 Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojehevski, 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 Rohde. Sliced wasserstein auto- encoders. In ICLR, 2018.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint UrXiv:2005.14611 2020.
Yulong Lu and Jianfeng Lu. A universal approximation theorem of deep neural networks for expressing probability distributions. NeurlPS, 2020.
Romero-Soriano. 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, Hu, G Long, Jiang, Yao, and 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-gen: Geometric graph convolutional networks. ICLR, 2020.
Bryan Perozzi. Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, 2014.
Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications data science. Foundations and Trends@ in Machine Learning, 115-6)):355-677 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 Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9())ccnab014, 2021.
Han Shi, Haozheng Fan, and James 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 semi- supervised graph-level representation learning via mutual information maximization. ICLR, 2020.
11

---

Published as a conference paper at ICLR 2022
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances 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. 2018.
Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. ICLR, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018a.
Petar Veličković, William Fedus, William 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: 19090039990 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty. Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICMI., 2019.
Yaochen Xie, Zhao Xu, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning graph neural networks: A unified review. arXiv preprint arXiv:2102.10757, 2021.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable grasevewasserstein 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 NewrIPS, 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. NeurlPS, 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 NewrlPS, 2021.
12

---

Published as a conference paper at ICLR 2022
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 2020).
Theorem 2.1 in (Lu
Theorem A.1 (Theorem 2.1 & (020)). Let P and Q be the target and the source distri- butions respectively, both defined on E. Assume that Ez~p|[æ]] is bounded and Q is absolutely continuous with respect to the Lebesgue measure. It holds that for any given approximation error e, setting n O (=),, ), there is a fully connected and feed-forward deep neural network u(-) of depth = [log, nl and width N 2L, with inputs and a single output and with ReLU activation such that W1 (P, Vu(Q)) < Here, Vu(-) is the function I + H induced by the gradient of while (u( is the distribution that is generated from the distribution Q through the mapping Vu(-).
To prove Theorem 3.1 we just need to verify the conditions in the above theorem. We need to show that P ( has bounded Ex-p]|=]] and Q as a non non-degenerate m-dim Gaussian distribution absolutely continuous with respect to the Lebesgue measure. Also, the original statement for ()(:.)) while we use -) We need to show the connection between (..,)) and Wa(:;)) )).
Fortunately, all these aspects are easy to be verified.
P T= = has bounded 3-order moment because the support P! are in a bounded space of R"..
Q as a Gaussian distribution is absolutely continuous with respect to the Lebesgue measure, long as Q is not degenerate.
Lastly we show the connection between Wi (.,+) and W2 ( The support P= p! is bounded, i.e., E supp(P), ||ól|2 I B. According to Lu & Lu 2020), the Q = Vu(g) also has bounded support. B. Then, we may show that
Without loss of generality, 5 supp(Q), |
(P, = inf (ET(P.I) [/
11 - 2 2112d7(2, 2
2x2'
U "XX
1 - 7 (2, 2))
< 2B
inf *ET(P.Q)
U/ 1 - Z 11 21)
inf $ 2mBmm
TE((P.)
2B Q) 2Bvme.
As B and just constant, so we may have (P, Occ). Note that the above first inequality 1 < Z 1 + | = 2B. The second inequality is because
because | Z
// Zxz'
Vm inf (ET(P.Q)
12 Z' (2,
lim
v /mll Z' 21111xx(2.2))
10000
Zx
(There exists sequence of measures {3 achieving the infimum)
[ | Z 111dd) 2
lim 61000
2X2'
[/ VExz 1 - 2' 112d (112d)
inf (Er(P.Q)
B ADDITIONAL DATASET DETAILS
In this section, we provide some additional important details about the synthetic and real-world network datasets
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 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 provided in Table 4
13

---

Published as a conference paper at ICLR 2022
Close in Proximity
Close in Structure
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 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 deleting edges)
C DETAILED SETTINGS OF THE COMPARED MODELS
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 Python code (GPLv3 license) provided by Perozzi et al. (0144).
Walk:
node2vec: similar DeepWalk, we also ran 10 random walks of length 40 with p and q equal to 0.25. The implementation is provided by Grover & Leskoved (2016).
RolX: by using Henderson al. (2012)* 's code, set the initial learning rate 0.01 and the algorithm with batch size 32.
struc2vec: similar to WeepWalk 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 al. (017)
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 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 noss-validattin, the implementation is based on the code provided by Kipf & Welling (2016)
VGAE: same encoder structure and similar decoder GAE, the implementation also based on
Kipf & Welling (2016).
ARGVA: same encoder structure as GAE and VGAE, 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 10000 but may early stop when the algorithm is converged. We use the DGI method based on the implementation of Veličković et al. (2018b).
Table 3: Real-world network datasets description
Dalasets
Type
Nodes
Edges
Node Features
Node Labels
Cora
Citeseer
Citation Networks
Papers
Citations
Bag-of-words papers
Academic topics
Pubmed
Texas
WebKB
Web pages
Hyperlinks
Bag-of-words of web pages
Identity roles (Student, Project, eto.)
Wisconsin
Chameleon
Squireel
Wikipedia Network
Web pages
Mutual links
Informative nouns
Number of monthly traffic
14

---

Published as a conference paper at ICLR 2022
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
2708
3327
19717
183
183
251
2277
5201
7600
Edges
S429
4732
44338
295
309
499
36101
217073
33544
Features
1433
3703
500
1703
1703
1703
2325
2089
931
Classes
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 contribution in this work is on the decoder and we wanted to be fair and focus on the comparison of different
decoders. Specifically, we the default encoders in their original work for all baselines that
involve GNN encoders (GraphSAGE (Hamilton et al. (2017)) for GraphCI. (You et al. 2020 GCN
(Kipf & Welling 2017) for GAE (Kipf & Welling 2016). VGAE (Kipf Welling 2016), DGI
(Veličković et al., 2018b), MVGRL (You et al. (020)). The GCN encoders all have the same two- layer architecture, which the same as we used for NWR-CAE. 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. (019cc) and GraphSage (Hamilton et al. (017a) encoders, which are clearly worse than that with GCN.
flyper-paramete 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 g from (3, 5, 8, 10), and the trade-off weight parameters Ad, A from [10, 1, le-1, 1e-2, 1e-3, le-4, le-5).
Notes 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, NAR-
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 8GB NVIDIA GeForce RTX 3070 GPU.
Table 5: Selected baseline with different encoders
Algorithms
Corell
Texas
Wisconsin
Chameleon
Squirrel
Actor
GAE w/GCN
45.40 + 9.99
58.78 = 3.41
34.11 + 8.06
22.03
1.09
29.34 1.12
28.63 # 1.05
GAE w/GIN
39.33 1 4.17
53.30 + 2.75
32.84
4 3.94
24.99 + 2.56
23.46 1:6661100 1.04
25.34 +: 1.43
GAF w/GraphSage
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 good trade-off between efficiency and performance, which makes the method have reasonable running time 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, provide detailed results 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 from N, in layer i, where < i < k. thus {h < j S q} denotes the q ground truth embeddings of v's neighbor. Next the model gets q samples {E,, j q) from Gaussian
15

---

Published as a conference paper at ICLR 2022
distribution parameterized by GNN encoder, and uses an FNN-based transformation (1!-.) (N)) to reconstruct n.)
Based above, create x-y pairs with
x Σ}= (11i
q
ming:
(9]-
Ei=o Ej=1
11
y
q 9.k
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
O. 0.1080
0.1504
0.2120
0.2704
15
0.0423
0.0624
0.0884
0.1384
0.2272
30
In T 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 reasonably good approximation to the ground-truth neighborhood information (the smaller the better approximation). We tried different sample sizes y such as 5, 15, 30, which do not make 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 with smaller values (the results we show in Table aree with = 5, and the results we show in Figure 4 (b) with g 5, 10, 15). This indicates that while our model has the ability more ideally approximate the entire neighborhood information, often may not be necessary to guarantee satisfactory performance in downstream tasks, which allows to train the model with small sample sizes and achieve good efficiency.
downstream tasks already satisfactory even
To better understand the effect of number of GNN layers in our proposed model, we vary from I to on the synthetic dataset of "House". The model performance only gets better when & grows over because the important graph structures there cannot be captured by GNNs with less than 3 layers. Motivated by such observations and understandings, we set l 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.
Table The effect of i (exemplified on the synthetic dataset of "House").
Metrics
k=1
k=2
k=3
k=4
k=5
Homogeneity
0.89
0.94
0.99
1.0
1.0
Completeness
0.92
0.93
1.0
1.0
1.0
Silhouette
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 (reduced to two-dimensional via PCA). As 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 low- dimensional, it is hard for any algorithm to achieve perfectly clear class separation, but NWR-GAE
16

---

Published as a conference paper at ICLR 2022
capture more discriminative information and deliver less uniform node distribution, which is more useful for the node classification task as consistent with our results T
Nodo Label
hode Lebo
Node Latel
(a) node2vec
(b) struc2vec
(c) Wave Wave
Node Label
Node Label
(d) GAE
(e) DGI
(f) NWR-GAE
Figure 7: Embedding spaces reduced to two-dimensional through PCA on Chameleon dataset.
17


Reviews:
[{"review_id": "HVS2RuZY6kV", "reviewer": "Reviewer_mWmk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1. The method is intuitive and the way that the neighbourhood information is reconstructed appears novel.\n2. The empirical evaluation is extensive and highlights the models benefit across a range of different datasets when compared to several categories of baseline approaches, covering both structure-based, graph auto-encoder based and contrastive learning approaches.\n3. The paper is mostly well written.\n\nConcerns:\n1. How does an increase in k affect the model?\n2. Delta in the expression for P_v^(0) does not seem to be defined, which impacts the clarity of how the distribution is computed.\n3. A loss is introduced to predict the degree based on the node feature, however, it is not explicitly used in the neighbourhood reconstruction process. Why not sample q according to or proportional to the degree? How is the neighbour-sampling handled when a node has less than q neighbours? \n\nMinor: \n- For improved clarity, I suggest to include in Table 2, the heading that indicates which datasets are structure-oriented or proximity-oriented, etc. (as is done in Table 4 in the appendix). \n- The second sentence in Section 3.2 seems to be incomplete. \n- In the second sentence of Section 4.3, you mention that DGI is the best performing model. Should it be MVGRL?", "summary_of_the_paper": "The paper proposes a novel approach to graph representation learning. In particular, a graph auto-encoder is proposed that aims to better capture the topological structure by utilising a neighbourhood reconstruction and a degree reconstruction objective. An optimal-transport based objective is proposed for the neighbourhood reconstruction that optimises the 2-Wasserstein distance between the decoded distribution and an empirical estimate of the neighbourhood distribution. An extensive experimental analysis is performed, highlighting the benefits of the proposed approach on a range of synthetic datasets to capture structure information. The experimental results also highlight its robustness across 9 different real-world graph datasets (ranging from proximity-oriented to structure-oriented datasets).", "summary_of_the_review": "Overall, the paper is well written and presents an interesting and efficient approach to graph representation learning. I lean towards accepting the paper if the authors address the above-mentioned concerns and questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HFVlO2HSirA", "reviewer": "Reviewer_dc6B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The appreciated side of this paper is the correctness of the method, detailed illustration of implementation and the thorough experiment comparison. The proposal to adopt degree decoder, Wasserstein distance and its approximation into GAE looks reasonable to me, and the empirical examination verifies this.\n\nThe disadvantage is on the novelty side, considering that i) enforcing awareness of the context of nodes to highlight structure information is not new in the graph field (https://arxiv.org/abs/1905.12265, etc); ii) the employment of the OT theory into networks existed in even a more fancy way (https://arxiv.org/pdf/2003.03892.pdf, https://openreview.net/pdf?id=ATUh28lnSuW, etc). The benefits of individual components were established and therefore directly combining them together further boosting is not surprising.\n\nI would recommend digging further into either theory or ablations to strengthen this interesting work, to characterize the real \"structure information\" captured by the proposed method compared with literature, probably following the thought as: 1) defining structure information (SI) and its quantitative assessment metric; 2) showing the proposed method can capture certain SI but the existing methods cant; 3) showing OT can capture better.", "summary_of_the_paper": "The paper proposes a new loss in graph auto-encoder (GAE) model for unsupervised learning, composing of degree prediction and Wasserstein distance, which helps to identify structure information better vs the original loss. Extensive experiments demonstrate the advantages of the proposed loss.", "summary_of_the_review": "I am satisfied with the solidness of the paper, including the methods part and experiments, while I feel it is limited in novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DZ51VNqglt0", "reviewer": "Reviewer_W8Ew", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: Especially clear descriptive figures and writing. Experimental benefits on both toy and real world datasets and additional exploration as to why these improvements might be occurring.\n\nWell motivated and well placed in the literature, the empirical comparisons are extensive.\n\nThe idea of NWR is seems novel and useful to me.\n\nWeaknesses:\n\nThe notation is a bit cumbersome with many subscripts and superscripts that are difficult to keep track of.\n\nSome of the choices in matching neighborhoods seem a bit arbitrary and not sufficiently justified (see questions below), although this is somewhat understandable as there are large number of tricks used in this paper.\n\nLimited theoretical contribution, with some small inconsistencies.\n\nQuestions:\nHow much does the neighborhood Wasserstein reconstruction improve over a naive reconstruction of something like the mean of the neighborhood? Is it the Wasserstein distribution matching that is important, or just that it helps to reconstruct something about the neighborhood of each node. \n\nTheorem 3.1 seems a bit out of place given that you don't actually want a universally approximating network here, if you had a large enough network then the NWR loss would have no benefit right, as the FNN \\psi_p^(i) could always approximate the neighborhood distribution from any initial \\mu, \\sigma input?\n\nDo you use W_2^2 (as in eq. 6, Figure 3) or W_2 ( as in eq. 1)? Not that it matters much but would be good to clarify.\n\nSmall notes:\nIt would be slightly better to prove approximation in the W_2 metric rather than W_1 in Theorem 3.1, as this is what is used in the empirical results and the rest of the paper. This seems trivially true to me.\n\nTheorem 3.1 You are missing a closing paren in W_1(P, u(G))", "summary_of_the_paper": "The authors propose a graph autoencoder architecture using what they term as Neighborhood Wasserstein Reconstruction (NWR). They show experimentally that this reconstruction loss improves the embedding performance in structure-oriented graph mining tasks.\n", "summary_of_the_review": "This paper was an interesting read and provided insightful and clear justifications for the results. There remain some questions as to the theory and some particular loss choices made, but these are relatively minor points. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1hOR_MWPURA", "reviewer": "Reviewer_hC5R", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n**Writing**\n1. While most of the paper is well written, it can be still improved. For instance, the paper mentions that existing approaches are either structure-oriented or proximity-oriented approaches and they cannot distinguish certain node pairs. However, the concept of the structure or proximity information of a graph is not defined and introduced well at all in the introduction, making the paper hard to follow at the very beginning. \n2. Figure 1 tries to illustrate the disadvantages of existing approaches. It is unclear why there are two nodes with the same numbers (such as 5 and 4). Are they the node labels or IDs in the graph?\n\n**Method**\n\n  The time complexity of the proposed method looks very high. The paper briefly describes the time complexity of Eq 8. It would be good to know the overall time complexity of the proposed algorithm.\n\n\n**Experiments**\n\n1. The idea of training a graph encoder in supervised manner links to the early graph embedding and the recent self-supervised learning (SSL) for graph data. It is good to see that both random walk based approaches, as well as SSL based approaches, are compared in the experiments. But it is unclear why GraphCL and MVGRL are only compared on the real-life datasets but are missing in the synthetic datasets in Table 1.\n2. The proposed algorithm is significantly worse than the SSL based approaches such as DGL and MVGRL on Cora, Citeseer, and Pubmed. These datasets are identified as *Proximity*-oriented datasets in Table 2. More detailed explanation would be expected. \n3. All datasets are relatively smaller in this paper.  It is unclear the scalability of the proposed method.", "summary_of_the_paper": "This paper studies the problem of graph representation learning with graph autoencoder. The paper argues that most GNNs are designed for semi-supervised learning and cannot learn task-agnostic embedding. As a result, the paper proposes a graph autoencoder architecture that trains the GNN in an unsupervised manner. The key idea is to develop a decoder to reconstruct both the node degree and feature distribution. Experimental results show that the results outperform existing autoencoder baselines in several datasets.", "summary_of_the_review": "The paper describes a new graph autoencoder approach that could encoder more information into the latent space. However, the scalability of the proposed method is questionable. Also, the proposed method did not outperform baselines on three datasets. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel approach to graph representation learning. In particular, a graph auto-encoder is proposed that aims to better capture the topological structure by utilising a neighbourhood reconstruction and a degree reconstruction objective. An optimal-transport based objective is proposed for the neighbourhood reconstruction that optimises the 2-Wasserstein distance between the decoded distribution and an empirical estimate of the neighbourhood distribution. An extensive experimental analysis is performed, highlighting the benefits of the proposed approach on a range of synthetic datasets to capture structure information. The experimental results also highlight its robustness across 9 different real-world graph datasets (ranging from proximity-oriented to structure-oriented datasets).

Strengths:
- The problem studied is well motivated and the method proposed is well placed in the literature.
- The method is intuitive and the way that the neighbourhood information is reconstructed appears novel.
- The empirical comparisons are extensive.


Weaknesses: 
- Some of the choices in matching neighborhoods seem a bit arbitrary and not sufficiently justified. 
- The scalability of the proposed method is questionable. The method has a high complexity of O(Nd^3) (where N is the number of nodes and d is the average node degree). The authors address this problem by resorting to the neighborhood sampling method (without citing the prior art), which is only very briefly discussed in the paper. 
- The reviewers have also expressed concerns about the fixed sample size q. The question of how the neighbour-sampling is handled when a node has less than q neighbours remains unanswered.
Decision: Accept (Poster)