A Deep Latent Space Model for Directed Graph Representation Learning
Authors: Hanxuan Yang
Qingchao Kong
Wenji Mao
Venue: ICLR 2022 Submitted (2022)
Keywords: graph representation learning
directed graph
latent space model
variational autoencoder

Abstract: Graph representation learning is a fundamental problem for modeling relational data and benefits a number of downstream applications. Traditional Bayesian-based random graph models and recent deep learning based methods are complementary to each other in interpretability and scalability. To take the advantages of both models, some combined methods have been proposed. However, existing models are mainly designed for \textit{undirected graphs}, while a large portion of real-world graphs are directed. The focus of this paper is on \textit{directed graphs}. We propose a Deep Latent Space Model (DLSM) for directed graphs to incorporate the traditional latent space random graph model into deep learning frameworks via a hierarchical variational auto-encoder architecture. To adapt to directed graphs, our model generates multiple highly interpretable latent variables as node representations, and the interpretability of representing node influences is theoretically proved. Moreover, our model achieves good scalability for large graphs via the fast stochastic gradient variational Bayes inference algorithm. The experimental results on real-world graphs demonstrate that our proposed model achieves the state-of-the-art performances on link prediction and community detection tasks while generating interpretable node representations.

Under review as a conference paper at ICLR 2022
A DEEP LATENT SPACE MODEL FOR DIRECTED GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph representation learning is a fundamental problem for modeling relational data and benefits number of downstream applications. Traditional Bayesian bassedan-based random graph models and recent deep learning based methods are complementary to each other in interpretability and scalability. To take the advantages of both models, some combined methods have been proposed. However, existing models are mainly designed for undirected graphs, while a large portion of real-world graphs directed. The focus of this paper is on the more challenging directed graphs where both the existences and directions of edges need to be learned. We propose a Deep Latent Space Model (DLSM) for directed graphs to incorporate the traditional latent space random graph model into deep learning frameworks via hierarchical variational auto-encoder architecture. To adapt to directed graphs, our model generates multiple highly interpretable latent variables as node repre- sentations, and the interpretability of representing node influences is theoretically proved. The experimental results on real-world graphs demonstrate that our pro- posed model achieves the state-of-the-arr performances on link prediction and community detection tasks while generating interpretable node representations of directed graphs.
INTRODUCTION
Learning representations on graphs is a fundamental problem for graph analysis and benefits number of downstream applications, typically including link prediction, community detection and influential node identification. Traditionally, a plethora of Bayesian based random graph models have been proposed for learning graph representations (Holland et al. 1983] Hoff et al., 2002 Karrer & Newman 2011: Sewell & Chen 2015). Despite the ideal interpretability of these methods, they are unscalable to model large-scale graphs due to the expensive iterative inference procedures. Boosted by the powerful representation learning ability, graph neural networks (GNNs) have been proposed to learn the topology of graph-structured data (Kipf & Welling 2017 Hamilton et al., [207]] Veličković et al.) 2018 Zeng et al., (2020). However, these GNN-based methods usually bring about the interpretability issues, which restrict the practical applications of these methods.
As an effective deep learning method based on the Bayesian theory, the variational auto-encoders (VAEs) (Kingma Welling (201b) have been proposed for representation learning on graph- structured data (Kipf & Welling 2016 Grover et al. 2019 Salha et al.) 2019). To capture the mutual facilitation of random graph models and deep learning based methods, some recent research attempts to combine them using VAEs, and build the deep generative random graph models (Mehta et al. 2019 Sarkar et al.) 2020). However, most of these VAE-based methods are designed only for undirected gruphs. In contrast, a large portion of real-world graphs, such as social and citation networks, are directed graphs, of which undirected graphs are special cases (i.e. an undirected edge can be regarded as bidirectional edge). The representation learning on directed graphs is particularly challenging since not only the existences but also the directions of edges need to be learned. Although directed graphs have been extensively studied by traditional research random graph models (Hoff et al. 2002 Krivitsky et al. 2009 Sewell& & Chen, 2013). there are still few deep learning based methods and combined models existed to address them.
In this paper, we present the first VAE- based generative model for directed graphs and propose the Deep Latent Space Model (DLSM), which combines graph convolutional networks (GCNs) with the

---

Under review as a conference paper at ICLR 2022
Bayesian random graph model using hierarchical VAE architecture. Within model, deep GCN leveraged to encode the asymmetric adjacency matrix and node features as hidden states, which are layer-wise transformed to variational parameters generate latent random variables as interpretable node representations. Then, the hierarchical decoder network reconstructs the adjacency matrix using the learned representations.
To better capture the characteristics of graphs for deep random graph models, our method generates three types of interpretable representations, including the latent positions, node random factors and community memberships. The latent positions measure the distances between nodes and enable our method model the link reciprocity of directed graphs, which means that both bidirectional and unidirectional edges exist. To characterize the degree heterogeneity, we introduce pair of node random factors, namely the social activity and popularity, thus the asymmetric structure of directed edges can be modeled. Besides, we use binary latent variable, named the community membership, to accommodate an overlapping community structure. We further prove that these node-specific variables, including the latent positions and random factors, are interpretable for representing the existence and strength of node influences.
For fast inference, we leveraged the stochastic gradient variational Bayes (SGVB) algorithm (Kingma & Welling 2014a), which is far more efficient and scalable compared to the traditional iterative inference methods. We conduct experiments on link prediction task to verify the effectiveness of directed graph modeling with several real-world graphs, and further demonstrate the interpretability of latent variables on community detection task.
The main contributions of this work are summarized as follows:
1. We propose the DLSM model for directed graphs to incorporate the latent space model into deep learning frameworks using a hierarchical VAE architecture, which can generate highly interpretable representations of graph nodes for multiple downstream tasks.
2. To adapt our method to directed graphs, we introduce the social activity and popularity fac- tors of each node, with thcoretical proof of their capabilities in representing node influences.
3. We conduct experiments on five real-world graph datasets, and the results show that our proposed method can well support downstream tasks and achieve the state-of-the-ard perfor- mances in link prediction and community detection.
RELATED WORK
In this section, we briefly review the traditional Bayesian Bayesian-bbsed random graph models and deep learning based generative graph representation methods.
2.1 BAYESIAN BASED RANDOM GRAPH MODELS
Classic Bayesian- based random graph models have developed for decades and are still valued in modeling and generating relational data. This methods regard graph nodes as random variables following a prior distribution, and learns low-dimensional embeddings via the posterior distributions of nodes. One of the most well-known methods is the stochastic blockmodel (SBM) (Holland) et al. 1983), which generates a latent variable indicating the community membership of each node.
Following SBM, a large number of variants have been proposed, such as allowing an overlapping community structure (Miller et al., 2009) and involving degree heterogeneity (Karrer & Newman 2011
Another important random graph model is the latent space model (LSM) (Hoff et al. 2002), which assumes each node as a position in an unobservable latent space and use distances to measure the relationships between nodes. Such method has soon been extended to model directed graphs by involving the degree heterogeneity these above methods provide good theoretical properties and learn interpretable node embeddings, they rely on either the MCMC posterior sampling or mean-field variational inference with dramatically high computational complexity, and thus usually unfeasible when modeling large-scale graphs.
nodes (Krivitsky et al. 2009 Sewell & Chen, 2015). Although
2

---

Under review as a conference paper at ICLR 2022
2.2 DEEP LEARNING BASED MODELS FOR UNDIRECTED GRAPHS
The intriguing achievements of deep learning models for learning representations of Euclidean data have encouraged efforts to employ them on graph-structune data. The earliest attempts include DeepWalk (Perozzi et al. 2014) and node2vec (Grover & Leskoved 2016), both of which encode local relations as node representations by conducting random walks on a graph.
GNN-based graph models More recently, many GNN- models have been proposed for graph representation learning. Kipf & Welling (2017) first leverages the spectral GCN to learn node embeddings using the global topology of a graph. GraphSAGE (Hamilton et al. 2017) samples a fixed-size neighborhood of each node for the inductive representation learning, which allows unseen nodes to be excluded during training. The graph attention networks (Veličković et al. 20188) introduce the attention mechanism to aggregate the information from neighbors. GraphSAINT (Zeng et al. 2020) constructs minibatches by sampling subgraphs across GCN layers. (Zhang et al. 2021a) proposes multi-node representation learning method for link prediction using the node labeling trick. These methods usually learn representations for a single or a set of nodes and only focus on some specific task of graph modeling, such as node classification or link prediction.
Deep generative graph models Another stream of research is the deep generative models, which attempt to generate the full structures of graphs and are typically able to applied for multiple downstream tasks. These methods usually consist of a inferential model to capture the inner prob- abilistic distribution of graphs and an unsupervised generative model to generate the similar data. The variational graph auto-encoders (VGAE) Kiipf & Welling/ 2016). for example, sample node embeddings from variational Normal distributions to reconstruct the adjacency matrix. GraphGAN Wang et al. (008)) unifies a generator and discriminator learn node embeddings by playing minimax game. GraphRNN You et al. (2018) generates small graphs through a sequence of node and edge formations. Recently, some work tries incorporate traditional random graph models into deep learning frameworks. |Mehta et al. (211)) first combines the classic SBM with GCN to learn sparse node embeddings. Furthermore, /aarkar al. (2020) builds Gamma ladder VAE (Sønderby et al. 2016) architecture to discover the communities at multiple levels of granularities.
2.3 DEEP LEARNING BASED MODELS FOR DIRECTED GRAPHS
Despite a plethora of literature for undirected graph modeling, the deep learning based methods for directed graphs are still relatively rare. Existing methods are mostly designed for some special cases and are not generalizable enough. For instance, Salha et al. (2019) and Zhang et al. (2021b) focus on the unidirectional graphs and neglect the link reciprocity of generalized directed graphs. Funke et al. (2020) learns the low-dine diw-dimensional statistical manifold embedding for unsupervised directed graph modeling. Zhu et al. 2021) learns a pair of source and target embeddings for each node using the generative adversarial network. In this paper, we propose novel deep generative model and learn interpretable node representations for generalized directed graphs where both uni- and bi-directional edges exist.
DEEP LATENT SPACE MODEL
Consider a directed graph containing n nodes. The input data include an asymmetric adjacency matrix (A.j)= E [0,1]nxx nxX" where each binary element At denotes the presence (1) or (0) of the directed edge from node to j. and node attribute matrix X E Raxp, Throughout this paper we Bernoulli(ps)) where the collection of latent variables (representations) and P.j E (0, 1) is the posterior probability to form an edge. The objective is to learn the representations which can best reconstruct the adjacency matrix.
assume all edges to be conditionally independent and satisfy A A
We propose deep VAE architecture composed of a GCN encoder and a hierarchical latent space model (HLSM) decoder, as shown in Fig. [ The encoder block takes the adjacency A and attribute matrices X, if available, inputs and learns hidden state for each node using a directed GCN. Then, the decoder block recursively generates interpretable latent variables from variational posteriors via Monte Carlo sampling and reconstructs the adjacency matrix outputs. For inference, the
3

---

Under review as a conference paper at ICLR 2022
H
A
IP
H
H
S
S
5
Å
X
F
GCN Encoder
HLSM Decoder
Figure 1: The architecture of hierarchical variational auto-encoder. The HLSM decoder generates adjacency matrix with latent variables, which are sparsified by the community membership (black dashed arrows). The GCN encoder learns variables using not only the feedforward priors from previous layers (black solid arrows), but also the skipping likelihood of the inputs (orange arcs).
hierarchical architecture enables the model to learn variables using not only the priors passed from previous layers of the decoder, but also the approximate likelihood learned by the encoder.
3.1 HLSM DECODER
The HLSM decoder learns interpretable node representations based on the classic LSM approach and generates an adjacency matrix. Assume each node correspond unobservable D-dimensional space, denoted as z, E IR The distances between latent positions indicate the relationships of nodes. The closer two latent positions are, the more possible an edge will exist. Formally, an directed edge is generated by following
latent position in an
(AA. = X θ) = (Bo - Bout I| @ (z: - 23) Bm. 10 o (z; 12,,-1,)11 1))
(1)
where (-) is the sigmoid function. The latent positions z; are involved as Euclidean distances, indicating the relationships between nodes. 7; and 6; E IR are the activity and popularity factors, the reverse of which represent the tendencies for node to send and receive an edge, respectively. The global weights Bout and 3m are to measure the importance of activity and popularity, respectively, and Bp is a bias. To be mentioned, though Eq. (T) is designed for directed graphs, it can be easily degraded
undirected variant by setting Y/ ò; and Bout Bin-
We build an HLSM decoder to generate three types of latent variables, i.e. the latent positions =(") RG, the community membership s(") R and the node random factors 7/s, 50h RG, where G, is the size of the /-th decoder layer. All of these variables are randomly sampled from the variational distributions. At the first layer (1 1), the parameters of variational distributions defined by priors solely, while for other layers = 2,..., L 1), the parameters are obtained by the feedforward representations generated from previous layers as well as priors.
Latent position The latent positions represent the location of each node in latent space, generated as
Normal $ (()
1) (111))),,, diag(o("?))
(2)
where f(.) is a nonlinear activation function (e.g. leaky ReI.U), @ denotes the element-wise multi- plication, diag(-) denotes a diagonal matrix, af (1)
E G is the prior variance to be specified, and w((-1) G 1 is weight matrix to transform the variable from dimension Gi-1 to Gy-
Community membership
The latent positions in Eq. 2 are separated into different communities by the sparse binary variables s(!) (811; -51...... 81G,) thus overlapping community structure
4

---

Under review as a conference paper at ICLR 2022
be adapted. Referring to Miller et al. (2009), we employ the Indian buffet process (IBP) prior on 8 to learn the effective number of communities given a sufficiently large truncation parameter G1, i.e.
ig = logit I
Bernoulli (o(TT))
ig
(1) Typically, the log odds Tig is generated using stick- brick-breaking construction, where Vin is drawn from a Beta distribution (Teh et al. 2007). our model we simplify such hierarchical prior structure by
(
specifying global for all nodes. At each layer, the community membership Sig denotes whether node belongs to community g, hence the size of each decoder layer Gr can explained as the number of communities. Additionally, the proposed HVAE architecture enables our model to detect community structures at multiple levels of granularities. Letting the layer sizes Gj be downward increasing, the top layers indicate the coarse-grained communities and the bottom layers indicate the fine-grained communities.
(?)
Node random factors random factors Y: 8(1)
To model the prevalent power-law of node degrees, propose the Dirichlet E RC. i.e.
Dirichlet (c.) - 8 2 f(( (1
y (1-1)))))
(4)
(1) (1) Dirichlet v + s o f(W (1 8
(5)
where _ and 1b? are prior parameters to be specified, and W
((1-1) G.GGG are weight matrices. Note that the node random factors are dependent on the community membership s! as well, which can be explained as only the random effects within the community are involved in the representations.
At the output layer (1 I.), the latent positions z; and node random factors 7i ó; are obtained by linear transformation from dimension GY-1 to D. Each column of the weight matrices belongs to (D - -immipeeex. Such transformation also changes the interpretation of the layer size, from the number of communities to the dimension of the latent space. Last, the adjacency matrix is reconstructed with the latent variables by Eq. (I).
3.2 GCN ENCODER
The proposed DLSM employs deep encoder as non-iterative recognition model infer the parameters of posterior distributions. Assuming the mean-field approximation of the variational distributions, the true joint posterior of the latent variables po (o(OA, (0IAX) can be approximated by variational posterior (9),, where and & denote the generative (decoder) and inference (encoder) parameters be trained, respectively. Then, the variational posterior is given as
L
qo(z, (12,8,7,8))
IIII go (z) 11
(1-1)) (0))) (s:h)) म.." (""1))
L (% Y (1 (6. o(1-1))
(6)
where h1 E Kr the output of the encoder and K₁ denotes the size of the I-th layer.
GCN has been proved effective in learning the topology of non- -un-ldulid data, and thus is ideal choice for the encoder of our model. Referring Kipf & Welling (2017), we propose the directed GCN operator as
(+1) = (Dour AD H w())
Here À = A I, and I, is the n-dimensional identity matrix. Dout and D,n are diagonal matrices with elements as the out- and in-degrees of Á, respectively. (0) = X if is available and (o) I, not. During inference, the hidden states are passed to the corresponding layer of the decoder and then combined with the prior information from previous layers to generate the parameters of variational distributions. Note that the vanilla GCN used here can be substituted by any other GNN for directed graphs.
5

---

Under review as a conference paper at ICLR 2022
4 INFERENCE
We now introduce our fast inference method using the SGVB algorithm (Kingma & Welling 2014a) Compared with the iterative methods such MCMC adopted by traditional Bayestan random graph approaches, SGVB is much more efficient and scalable. Such method requires differential Monte Carlo expectations perform backpropagation, thus the reparameterization trick for each of the latent variables is leveraged.
Denoting x²
RC a vector with standard Normal elements, the latent positions are reparametrized as (1-1)
8 (1-1) h + a! (=. (111)) (1-1) h (1) C =", where jr (z) (t-1) (1-1) h (1)
11-1) A,"") are variational posterior parameters.
Following Mehta et al. (2019). the Bernoulli posterior pe ( is approximated by the Binary Concrete distribution Maddison et af. 2017). i.c. i.c.
A (s! (1-1) h2 logit(u)).
(8)
where u ~ 1), Rig
8
(0) h
is a variational posterior parameter, R+ is the lemperature
to be specified, and then ig Referring to the recent literature (Joo et al. 2020), we use multiple normalized Gamma variables with unified rate parameters compose the Dirichlet distributions po (7,")) and po (5()), i.e.
( ig
(1-1) 111,,,1)) ()) 1):
Gamma
(7i
8 Gamma +
(8
(1 (t-1) (1) (n))))))))))))
(10)
where & (1) (,!-) / ((-1), h and 2h. (6 of " h ()) are variational posterior parameters.
For the convenience of notations, here the parameters of Gamma distribution symbolized as vectors, meaning the element wise operations. The node random factors are then derived by >!")
(1) 7 /E Tj
(1)
8 Ej 55 In practice, the Dirichlet variables are magnified by times to (1) and 6 when n is large.
avoid too small values of 7
In particular, the initial variational posterior parameters (1 = 0) are set as nonlinear combinations of h (1) and h (L-1), illustrated in Fig.
The loss function defined by minimizing the negative evidence lower bound (ELBO), i.e.
KL [ao(2/))) (poo2
+ KI. 1o (s( pp + KL [a0(7) (aalrt)///o(( pp((
x
+KL (o000"")(/((00)))
E. [108p((Ac]1(11)]]
(11)
where (L(p())llp()) denotes the Kullback-Leibler (KL) divergence between g(-) and p(-) (of which the full expression is given in Appendix [A). The second term is the cross entropy of adjacency matrix reconstruction. Here all of the true posteriors pe (e(()) and variational posteriors qs (e("), except for the input layer (1 1), conditioned on ( which is omitted for simplification.
MODEL INTERPRETABILITY
In this section, we show that the proposed latent positions and node random factors interpretable for representing the existence and strength of node influences, by hypothesizing that the true posterior of z; can be approximated by the variational Normal distribution.
Imagine that there is a new node with n; 2 2 neighbors entering a graph and we want to calculate z; using other existed nodes. It is rational to suppose that the new node should be posited around its

---

Under review as a conference paper at ICLR 2022
neighbors and thus can be denoted as residual to the mean of its neighbors, i.e.
Normal (2; + E,, diag (o::),
(12)
where
7i EjeN, 2j is the mean position of node i's neighbors, and 6; TR. is the residual for to the mean position. Intuitively, the residual should depend on all of the neighbors to various extent, of which the influential ones are likely to contribute more. Formally, we decompose the residual
Σ JEN;
Tijeisi
(13)
where rij 2 O is a scalar and Gi E RR. is unit vector at the direction of 2j E,. The non-negative scalar denotes the strength of influences neighbor j exerting on node i (see Fig. i Appendix for an example in two-dimensional latent space). An extreme case is rij 0, which means the latent position of is not influenced by neighbor j at all.
To further analyze the relation between the latent variables and node influences, we define the prior of rij as a mixture of a point mass on O and an exponential distribution, i.e.
f+(ri)) - (1-Pol fEss,, (ras)
Po
if rij = 0 rig > 0,
(14)
where 0 < po < and fExpa (.) denotes the density function of the exponential distribution with parameter A. What is of our interest is the posterior odds ratio (OR) for Tiy > 0, defined as OR(ri > O X) = So fr(ri- = vlA. 0/A, X)du, which measures the ratio for node
influences to exist.
Theorem Let @ denote a collection of all parameters except z, The posterior OR for rij > 0 satisfies
OR(r, > O,A,)
(zi, θ) Miy O.A.X
(15)
The full expression and proof are provided in Appendix B. It is interesting that in the proof (z, 2, -EKEN Ta is a sealar projection of 2, s residual component onto the unit vector whose direction is determined by zj. In a word, it shows that the posterior latent positions are able to model the existence of node influences via the residual component projections.
Now we consider the interpretation of node random factors, which explains the strengths of node influences. Formally, have the following conclusion, i.e.
Theorem 2
Assume the vectors from ž; to all influential neighbors (riz >> 0) are orthogonal to each other, and the random faadooffcttor factors are the same at all dimensions of the latent space, denoted as " and ö, respectively. The strength of inftuences for neighbor j exerting node can be denoted
rij = - 55. 0, 0))l)zz zill.
(16)
where 0 is the angle between 2, - Σ; and zj 2,, o is the angle between E, Zj and Z; Zj-
Here 1(7,, Ky, o) is function of the random factors as well as and o. The full expression and proof are given in Appendix B.2 Theorem reflects that given the direction of esj and z; 2;. the node random factors can be regarded as coefficients for measuring the ratio of Fıj to ||z z; ||- which means that the strength of influences for neighbor delivering the node can be strengthened or undermined via shrinking or enlarging the distance between them by the random factors.
EXPERIMENTS
To evaluate the effectiveness and interpretability of the proposed model, we conduct a series of experiments, including link prediction and community detection, several real-world graphs. Ablation study for the components our method, including the community membership. node random factors and the HL.M decoder architecture also conducted.
7

---

Under review as a conference paper at ICLR 2022
Table I: Results (in %) for link prediction on directed graphs. The best results are in bold and the second are underlined.
Emails
Political blogs
Cora
WikiVote
Google
AUC
AP
AUC
AP
AUC
AP
AUC
AP
AUC
AP
LSM
91.3 0.1
90.6 1: 0.1
88.7 0.3
86.5 +: 0.2
86.2 4: 0.2
$5.7.:0.22
N/A
NIA
NIA
NIA
VGAE
85.9 0.5
0.6
84.8 0.5
83.0
0.4
0.
0.
78.6 + 0.2
77.- =
78.3 = 0.4
80.0
0.4
SEAL
0.3
9.
0.2
0.4
DGLURM
0.34
93.1 0.3
0.
73.7 8.
0.66
88.4
86.0 0.0
0.12
GOVAE
0.3
90.3
0.6
92.1 0.
91.9
9.
96.2 0.1
9..
97.8 = 0.3
9.1
LGVG
0.
92.4 0.3
0.44
90.2 2 0.3
85.3 0.2
88.2 0.4
94.0 0.0
=.0
95.7 4: 0.0
95.9 0.0
DGGAN
0.74
91.0
0.6
0.7
0..6
92.7 0.4
DLSM
94.1 0.6
93.7 0.8
9..6+002
9
97.0+002
98.8
6.1 DATASETS
The experiments of link prediction are conducted on five real-world benchmark datasets, namely Emails (Leskovec et al. 2007), Political blogs (Adamic & Glance, 2005). Cora (Sen al., (2008). Wiki (Leskovec et al. 2010) and Google (Palla et al. 2007) All of the graphs have been preprocessed by omitting the isolated nodes and loops. In our experiments, the edges are randomly splitted 85% for training, 10% for testing, and 5% for validation. More details and descriptive statistics of the datasets are given in Appendix C
6.2 BASELINES
We compare our proposed DLSM with four recent deep generative methods for graph representation learning, i.c. the variational graph auto-encoder (VGAE) (Kipf & Welling 2016). the deep generative latent feature relational model (DGLFRM) (Mehta et al., 2019), the gravity graph variational auto- encoder (GGVAE) (Salha al. 2019). the ladder Gamma variational auto-encoder for graphs (LGVG) (Sarkar et al.) 2020), and the directed graph generative adversarial network (DGGAN) (Zhu et al.) 2021). b. For link prediction, we also consider a -ongeeeerte GNN-based model, i.e. SEAL (Zhang et al. 2a2 which is the state-of-the-art method for this task. The methods that are not particularly designed for directed graphs, including VGAE, DGLFRM and LGVG, are slightly modified by altering the original encoder with proposed directed GCN given in Eq (7p.
6.3 EXPERIMENTAL RESULTS
Link Prediction For link prediction, we employ the widely used area under the ROC curve (AUC) and average precision (AP) as evaluation metrics. Hyperparameter settings are provided in Appendix[D D. The experimental results of DLSM and the baselines are presented in Table where the reported results are the means and standard deviations of 10 independent random splits. On all datasets, our model achieves better or comparable performances to the non-generative method SEAL. However, since it requires to materialize subgraph for each link, SEAL is much more unscalable than our DLSM and takes about 20 multiples longer for running one epoch. The traditional LSM model is unpractical to fit large graphs such Viki and Google because of the MCMC-based inference methods, while the SGVB method adopted by our model is much more computationally efficient. In addition, it seems that GGVAE performs well approximately unidirectional graphs (i.e. the reciprocal rate close to 0 as shown in Table 4 such as Cora, whereas on other more generalized directed graphs where more bidirectional edges exist, our method is significantly superior to GGVAE. This is because our proposed DLSM considers the link reciprocity of directed graphs, which is neglected by GGVAE due its absolutely asymmetric decoding scheme. We also conduct experiments of link prediction on three real-world undirected graphs. given in Appendix E which show that our proposed model achieves comparable performances with the baselines and verify the capability for modeling undirected graphs special cases.
Community Detection We further conduct community detection on three real-world datasets with ground-truth community labels, i.e. Emails, political blogs and Cora, particular, for the Emails
'The source code is available httph:tt////gt http://///g.hhbb...oo///////////
8

---

Under review as a conference paper at ICLR 2022
Table 2: Results (in %) for community detection on directed graphs. The best results are in bold and the second are underlined.
Emails
Political blugs
Cora
micro F1
macro Et
micro
macro F]
micro FI
VGAB
31.5 1.6
42.5 + 1.5
34,9 1.2
52.3
1,4
23.2 + 1,0
24.8 0.4
DGLERM
433
60.7 + 1.0
42.4
50.5 1.3
18.2 0.5
0.5
GGVAR
6..8+155
67.7 14
92.0+111
22.7 92
24.0++04
LGVG
63.8 1.3
728
1.3
2.
0.79
DOGAN
62.1
66.7
0 1.3
88.9
8
18.7 1.0
21.4 1.2
DLSM
72.0 1.0
77.0 +: 1.2
92.5 1:
0.7
92.6 :: 0.7
24.6 à: 0.8
25.7 a: 0.5
Table 3: Ablation study results (in %) for link prediction.
Emails
Political blogs
Cora
Wote
Google
AUC
AP
AUC
AP
AUC
AP
AUC
AP
AUC
AP
-S-A-1
94.3 0.4
93.2 0.4
90.6 + 0.3
90.2 0.4
86.5 0.5
88.9
=
93.1 0.4
92.9 0.9=0.3
033
=5.
-A-1'
0.5
0.6
90.1 0.4
87.5
8.
86.0 0.7
872 0.6
85.1 0.
9.
93.9 0.4
91.0
0.
93.6 0.7
93.6
98,5
-S
94.8
0.66
0.5
9.69
0.6
9..9
96.5
96.4
98.2 9.2
-HI.SM
95.2++0.5 0.5
94.0
93.9+ 0.4
92.5+
86.8 0.7
86.9 + 0.6
95.6 0.3
95.8 + 0.4
98.0 0.3
97.3-02
DLSM
95.2 4 0.2
94.1 0.6
94.8 +: 0.4
93.7 +: 0.8
91.6
92.5 0.2
97.0 +: 0.2
97.0 = 0.2
98.8 = 0.2 98.8 = 0.1
dataset, communities (departments) with less than 30 nodes are excluded and finally 10 communities are retained. We utilize the node embeddings learned by each model (the latent positions ž; for DLSM) to conduct K-means clustering with ground-truth community numbers. The commonly used macro and micro Fl scores are leveraged as evaluation metrics, which are computed using the most likely mappings between true and predicted clusters. Table shows that proposed model significantly outperforms all other baselines for graph representation learning. Such results verify the advantages of leveraging the Euclidean distance rather than inner product to compute the divergences between nodes for community detection. (See Appendix G for visualizations of node embeddings using 2D t-SNE projectionthe distributions of the reverse node random factors, which shows consistent power-law with node degrees and offers more interpretabilityy)
Ablation study To justify the effectiveness of each component in our framework, including the community membership 8,, node random factors, d,, Yi and the HLSM decoder architecture, we compare the proposed DLSM with several variants of our method, which are named by the corresponding ablated components. For example, -A-T indicates the variant removed node random factors (see Appendix F for more details). The link prediction results are presented in Table and the community detection results are in Table of Appendix. Our DLSM performs best on all datasets for both tasks, verifying that all components are useful under the proposed framework. Interestingly, from the first two lines of Table we find that the community membership seems ineffective when the node random factors are not involved. This reflects that the binary s; mainly benefits our model by shrinking the redundant latent variables to O when there are too many parameters to optimize.
CONCLUSION
We establish a deep generative model learn multiple highly interpretable node representations for directed graphs. Our proposed DLSM, comprised of deep GCN encoder and a HLSM decoder, combines the traditional random graphs models with deep learning based methods to take the complementary advantages of interpretability and scalability. Series of experiments have shown that the model is effective for fitting directed graphs and achieves the state-of-the-ar performance on link prediction and community detection. In addition, the interpretable node representations learned by the model can naturally represent both the community structure and degree heterogeneity of complex directed graphs. In the future, we shall extend model for the more complicated scenes such as weighted or dynamic graphs. While the former with multi-valued edges can be simply achieved, the latter demands for more efficient method to learn the evolutionary topology of graphs.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Lada A Adamic and Natalic Glance. The political blogosphere and the 2004 US election: divided they blog. In International Workshop on Link Discovery, pp. 36-43, 2005.
Albert-Láásıíó Barabási and Réka Albert. Emergence of scaling random networks, science, 286 (5439):509-512, 1999.
Giorgio Fagiolo. Clustering in complex directed networks. Physical Review E, 76(2):226177,
Thorben Funke, Tian Guo, Alen Lancic, and Nino Antulov-Fantulin. Statistical manifold embedding for directed graphs. In International Conference on Learning Representations, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855-864, 2016.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs In International Conference on Machine Learning, pp. 2434-2444, 2019.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs In International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1000-1998 2002.
Paul Holland, Kathryn Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps.
Social Networks, 5(2):109-137, 1983.
Weonyoung Joo, Wonsung Lee, Sungrae Park, and I1-Chul Moon. Dirichlet variational autoencoder. Pattern Recognition, 107:107514, 2020.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83(1):016107, 2011.
Diederik Kingma and Max Welling. Efficient gradient- gradient-based inference through transformations between Bayes nets and neural nets. In International Conference Machine Learning, pp- 1782-1790, 2014a.
Diederik P Kingma and Max Welling, Auto-encoding variational Bayes. In International Conference on Learning Representations, 2014b.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian
Deep Learning, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Pavel N Krivitsky, Mark S Handcock, Adrian E Raftery, and Peter D Hoff. Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models. Social Networks, 31(3):204-213 2009.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1(1):2-es, 2007.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In International Conference on World Wide Web, pp. 641-650, 2010.
Chris Maddison, Andriy Mnih, and Yee W Teh. The concrete distribution: A continuous relaxation of discrete random variables. In International Conference Learning Representations, 2017.
Nikhil Mehta, Lawrence C Duke, and Piyush Rai. Stochastic blockmodels meet graph neural networks.
In International Conference on Machine Learning, pp. 4466-4474, 2019.
Kurt Miller, Michael Jordan, and Thomas Griffiths. Nonparametric latent feature models for link prediction. Advances in Neural Information Processing Systems, 22:1 22:1276-2844 2009.
10

---

Under review as a conference paper at ICLR 2022
Gergely Palla, Illés J Farkas, Péter Pollner, Imre Derényi, and Tamás Viesek. Directed network modules. New Journal of Physics, 96):186, 2007.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 701-710, 2014.
Guillaume Salha, Stratis Limnios, Romain Hennequin, Viet-Anh Tran, and Michalis Vazirgiannis. Gravity-inspired graph autoencoders for directed link prediction. In ACM International Conference on Information and Knowledge Management, pp. 589-598, 2019.
Arindam Sarkar, Nikhil Mchta, and Piyush Rai. Graph representation learning via ladder Gamma variational autoencoders. In AAAI Conference on Artificial Intelligence, pp. 5604-5611, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93-99 99,93, 2008.
Daniel K Sewell and Yuguo Chen. Latent space models for dynamic networks. Journal of the American Statistical Association, 1106512):164-16663 2015.
Casper K Sønderby, Tapani Raiko, Lars Maaløe, Søren Sønderby, and Ole Winther. Ladder variational autoencoders. In International Conference on Neural Information Processing Systems, pp. 01.3374433533 2016.
Yee W Teh, Dilan Grür, and Zoubin Ghahramani. Stick Stick-breaking construction for the Indian buffet process. In Artificial Intelligence and Statistics, pp. 556-563, 2007.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11), 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Hongwei Wang. Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. GraphGAN: Graph representation learning with generative adversarial nets. In AAAI Conference on Artificial Intelligence, volume 32, 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, pp. 5708-5717 5717, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. International Conference on Neural Information Processing Systems, la.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. Magnet: A neural network for directed graphs. arXiv preprint arXiv:2102.11391, 2021b.
Mingyuan Zhou Infinite edge partition models for overlapping community detection and link prediction. In International Conference on Artificial Intelligence and Statistics, pp. 1135-1143, 2015.
Shijie Zhu, Jianxin Li, Hao Peng, Senzhang Wang, and Lifang He. Adversarial directed graph embedding. In AAAI Conference Artificial Intelligence, pp. 4741-4748 2021.
11

---

Under review as a conference paper at ICLR 2022
A
LOss FUNCTIONS
The KI. divergence between Normal distributions
Kingma & Welling (014h) for zi is
KL 96 (2(")
po
G₁ Σ
(
1 [+ log (0!0) (1!1 (/
-(0)=~(11)) (1) 2
10002-0000 -0)))))
(17)
2
g=1
The KL. divergence between Binary Concrete distributions
Maddison et 2017 for s
(1) Fig
(1) - A2 2
1 + "ig
KL
9o (8) pe
(0
log
(18)
(1)
a (3) c xx -
π ig
where 200) the log odds of s/y
The KL divergence between Gamma distributions Joo et al. (020 for Y (1)
(the same for )(4) is
KI. [s (2.00) Ipo (7:²)
Σ log r (Egg)
r (Eeg) (Eig Lig (Eeg)
(19)
where r'() and vl(-) denote the Gamma and digamma function, respectively.
B DETAILS OF THEOREMS
B. PROOF THEOREM
For any positive value
0, the posterior probability density of rij at v is
f f = x)
= =I/ f (Tip = u. u. 2,, A X) dz,de
= -// (A,X| zi, 9) (rij = U, 2i, ②) dzzd0
((,
= f (A,X zi Q) frir = 0, A)
f f(r = U; θ)
[(ir 0, 0, +) dz,d0
f(A,X)
-[ f O)
((rg00, 0) ((1g = 0, 2, A X) dz
= -Iʃ [(, = v, () (r)
[( = 0,0) (ri) (e)
= - (z, 0/r = A, dz,dO.
(20)
12

---

Under review as a conference paper at ICLR 2022
Assume that the true posterior of 2, be approximated by the variational Normal distribution.
Then, according to Eq. (12) and 13
we have
(z) Tig = v. θ) f (rg- v) [z Fij 0, Q) f (Tg) = 0)
1 D
1- Po
Σ
exp
2;
VRij
Tiklik
2i 2;
ueij
Pu
2 d
NEN.Ra
Σ Tike
2: 21
Σ
Tikeis
2i --
Σ kEN,KyS
Tis
-A00
KEN
KEA
D
PO
exp
1
2 2u
2, - 2,
Tikeik
Eij
xu
2
0
d
kEN
2
D
D
Pa
exp
2: E
Tik
Eij
A
oi
2
D
E
2i - 2;
2
2
id
kEN
By dividing f(rig = 0|A, X) on both sides Eq. obtain
20 and integrating over on (0, +00). we can
OR(rg) > 0|A, X)
=ʃʃ (z/ u. 0) (raj 1)
f =0,, dz,d0
(zi rij = 0) f (rij = =0)
// 9 (2. f (z 0z. A, dz,d0
= g (z 0) Mi = A.A,.
where
(1 P
[Td Ozd
(zj (z-- -2; EKEN eij -IIIa oid
g (z,, O)
Poch
Il' -1
(2, ž ExEN, rieesh) eij 2II ofd
and (-)) and ø(-) denote the cumulative distribution function and probability density function of the standard Normal distribution, respectively.
The conclusion is proved.
B.2 PROOF OF THEOREM
We start our proof by giving two definitions, the standard distance (SD) and actual distance (AD) between node i and neighbor j. Consider simple case, where the influence discrepancies of all neighbors are neglected and the latent position z; only dependent on the distances between the node and neighbors (see Fig. b)) for an illustration). In this case, the residual c; O and z, will coincide with 2,, thus the distance from neighbor j to node is equal to ||æ, 2, which we refer as the standard distance.
Now we reconsider the influence discrepancies of neighbors upon the node. According to Eq. (T). the actual distance between node and neighbor j when involving node influences is node influences in
13

---

Under review as a conference paper at ICLR 2022
our DLSM are involved by rescaling the standard distance. Assume the vectors from the ž; to all influential neighbors (Tay > 0) are orthogonal to each other, and the random factors are the same at all dimensions of the latent space, denoted as %/ and ö,, respectively. Then, the actual distance between 2; and 2j is
Aj = (Bout + bm)d)) )| (zi -1) 1|-
(21)
The coefficients Yout' + 6n enlarge or shrink SD = ||z -z:ll to AD using the node activity and popularity factors. Let (0, a/2) be the angle between 2; 2s and 2j 2, i.e.
(z, 2, ( 2,) ||2 x 1 x,
arccos
(22)
Since eij orthogonal other residual components, the modulus of e; can be denoted as ||E:|| T cos 0. According to the law of cosines, we have
AD =SD? + ||=:l12 2SD
cos 0
=SD sj
+
2SD,
(23)
cos 0
By combining Eq. 21) and Eq. 123 we obtain
ri
||z 11
2||2, Vallrs =BBout V/ + +,3 (z, - -2,) 11?
cos 0
-
Fij
cos A||z, =xil) [(ooc + B,n sin? 8/ || (zi - 23) 112
cos
cos 0 [| - 2; = + (Bout + Beno,)² - sin? 0) ||ا zi|l-
cos 0
Given 8 E (0, x /2) (when 0 E (n/2, R), Tij = 0), the sign for the right side depends on the positive or negative correlation for ||: and AD given 0. which is determined by the angle between ž; 2j and z; Zj. denoted as
(Bout + Bend,) (z, (Z, 2,)
0 arccos
(Bous Y6 + B,n |z 2,
2; Zj
arccos
(24)
2i Zj
The sign is positive when o E (0, n 2 - 0) and negative when o E (T/2 - 0, m).
In summary, we have the following conclusion, i.e. Tij =1(7,, 05,0,,0,0000 0)]1 zill,
where
cos2 - cos
(Boue + Bind,)² -sin??
o (0. - 8)
1(% 0,0
cos 2 + cos (Bout + 3,n sin
if E (g 0, m)
and 0, is defined by Eq. 22 and Eq. 24 respectively.
The conclusion is proved.
C DIRECTED GRAPH DATASETS
Here we provide more details about the directed graph datasets employed in our experiments. Emails network consists of the members from 42 departments of a European research institution (Leskoved et al. 2007). An edge exists if person sends at least one email to another. Political blogs is a well-studies social network composed of U.S. political blog nodes (Adamic & Glance 2005). which are labeled as "liberal" and "conservative" clusters. Two blog pages are connected if one is referenced by another. Cora is citation network of scientific publications which are classified into seven
14

---

Under review as a conference paper at ICLR 2022
Zx
3
2
2
achil distanon
Z
Z
Tj
standard distence
2
Z
(a) Decomposion of the residual
(b) Standard and actual distances
Figure 2: (a) An illustration for the residual decomposition with two influential neighbors (the influence strengths for other neighbors are assumed be 0). The residual for z; can be decomposed as components at the direction of neighbor 2, and and Taj. are the corresponding influence strengths. (b) An example for the standard and actual distances two-dimensional latent space. The vectors from the mean position 2; to influential neighbors, i.e. 2j and 2k. are orthogonal and equal length.
Table 4: Descriptive statistics of the real graph datasets. [V] and [3] are the numbers of nodes and edges, respectively, CC is the clustering coefficient (Fagiolo 2007 ). dent and d are the maximal in-degree and out-degree of all nodes, respectively, dang the average degree of all nodes (average in-degree equals to average out-degree), ED = Σi= L Aij/(n(n 1)) is the edge density, and
Aij/
RR Σ
1 Aijaji/ E Eド= Aij is the reciprocal rate.
Dataset
VV
[
CC
dout max
fin maz
davg
ED
RR
Emails
986
24,929
0.4124
333
211
25.3
0.0257
0.7112
Political blogs
1,222
19,021
0.2459
256
337
15.6
0.0127
0.2426
Cora
2,708
5,429
0.1600
166
2.0
0.0007
0.0556
WikiVote
7,115
103,689
0.0896
893
457
14.6
0.0020
0.0565
Google 15,763
171,206
0.4007
852
11,397
10.8
0.0007
0,2541
classes (Sen et al. 2008). Each node and directed edge represent a paper and a citation, respectively. WikiVote is network Wikipedia users (Leskovec al., 2010), where each edge represents user voting on another to become the administrator. Google is a network of web pages which are connected by hyperlinks (Palla et al. 2007).
The descriptive statistics of the directed graph datasets for link prediction and community detection are summarized in Table
D HYPERPARAMETER SETTING AND SENSITIVITY ANALYSIS
The proposed DLSM employs a hierarchical VAE architecture composed of a GCN encoder and HL.M decoder. In practice, both of the two parts have three layers, and the layer sizes are fixed to be 32/64/128 and 50/100/50 for the encoder and decoder, respectively. Note that the last layer of the decoder (1 L) is linear full connection layer which transforms the sparse latent variables to dense for adjacency reconstruction. Fig. 3] shows the link prediction results for increasing numbers of layers, and the performance of method is continuously rising until more than 4 layers.
15

---

Under review as a conference paper at ICLR 2022
The HLSM stochastic decoder requires prior distributions generate latent variables. Specifically, we employ standard Normal prior for the latent positions 2; community membership 8; G2 (i.c. layer sizes of the decoder) and a ttckkbreaking parameters v E (0, 1). Typically, a smaller results in fewer active communities (i.e. non-zero elements of { Fig. (b) presents the link prediction results our method with different values v on the Political blogs dataset, and our method performs best when E (0.9, 1). Therefore,
(1) i.e. the variance of 1. For the the IBP prior to infer community numbers given the truncation
0.9 to ensure the model fully exploring the potential community structure of graphs. Last, we adopt flat priors for the Dirichlet node random factors 7/2 and o;, where all parameters set as cig ii 1/G
For inference, the temperature parameter À of the Binary Concrete distribution is fixed to 1. All models are trained by 1,000-2,000 iterations with learning rate of 0.01 on an RTX 2080 GPU.
DLSM
96.5
94-
Iink pww.erccnn...o AUC
54.4
93-
93.8
DLSK Platn
0.2
0.3
0.4
0.5
0.6
0.7
0.8
1.0
(a) Number of layers
(b) Stick-breaking parameter
Figure 3: Sensitivity analysis for link prediction on the Political blogs dataset. (a) The plain VAE (green) tends to collapse as the number of layers increases, while the performance of DLSM (blue) much more stable and continuously rises until more than 4 layers. (b) The performance of DLSM (blue solid line) reaches peak when v about 0.9, and consistently better than that of the ablated variant -S (black dashed line).
E LINK PREDICTION UNDIRECTED GRAPHS
Undirected graphs can be regarded as special cases in our framework, as an undirectional edge is treated as bidirectional one. In this section we provide some experimental results for link prediction on three real-world undirected graph datasets. The baselines are the same as those in the experiments of directed graphs.
E. DATASETS
We consider three real-world undirected graph datasets, namely NIPS12, Cora and Pubmed. NIPS12 is coauthor network of the authors in NIPS papers from volumes 1-12 Zhou (201)). Cora is the same dataset used the experiments for directed link prediction, except that directions of edges are neglected here. Pubmed is citation network of scientific publications (Sen et al. (2008). Both Cora and Pubmed datasets contain sparse bag-of-wordh feature matrices, which are used as node attributes. The descriptive statistics of the datasets are summarized in Table 5
E.2 LINK PREDICTION RESULTS
The results of link prediction undirected graphs presented in Table 6 On all datasets, DLSM achieves the best or comparative performances with the ofate-of-the-ar baselines for undirected graphs.
16

---

Under review as a conference paper at ICLR 2022
Table 5: Descriptive statisties of the real-world undirected graph datasets. |V] and || are the numbers of nodes and edges, respectively, CC is the clustering coefficient, dmaz is the maximal node degrees, dang is the average degree of all nodes, ED the edge density, defined as ED 2|E1/(IV((V) 1)), and FD is the dimension of attribute features (0 denotes features available).
Dataset
[1
[8]
CC
dmaz
d davg
ED
FD
NIPS12 2,037
3,134
0.7463
45
3.1
0.0015
0
Cora
2,708
5,278
0,3893
168
3,9
0.0014
1,433
Pubmed
19,717
88,648
0.1117
171
4.5
0.0002
500
Table 6: Results (in %) for link prediction undirected graphs. The best results in bold and the second are underlined.
NIPS12
Cora
Pubmed
AUC
AP
ALC
AP
AUC
AP
1SM
85.7 1.5
86.4 + 0.6
86.1 + 0.7
87.2 122+0.. 0.5
N/A
NIA
YGAE
91.1 0.
92.6
942 0.8
93.9
9..7
0.
DGLFRM
8.3
90.1 0.3
93
93
9..0
95.0 0.4
GGVAE
0.8
90.7 0.7
8.
9.4
93
94.1 0.4
LGVG
0.3
9.7
03.6404
9..0006
94
92
DGGAN
91.3
94
DLSM
9..5
93.1
9.
96.7 9.
F MORE DETAILS FOR ABLATION STUDY
We consider five variants our proposed model. Here we provide more details about these variants. -HLSM indicates to replace the HLSM decoder of our model using plain VAE with the same numbers of layers. Others are simplified variants by removing the corresponding components, as presented in Table 7 In particular, -A refers to set y 6; (thus the model has degenerated to undirected form yet still involves degree heterogeneity of graphs), and -S-A-T can be viewed as a variant of VGAE by changing the plain decoder with proposed HLSMM architecture.
The community detection results of ablation study is given in Table & Generally, models including the community membership perform better than those without this component, and the full version DLSM reaches the best performances on all datasets.
G VISUALIZATIONS OF NODE REPRESENTATIONS
Latent position We leverage 2D t-SNE projection (Van der Maaten & Hinton 2008 to visualize the learned latent positions for the Emails dataset. As comparisons, we also illustrate the node representations learned by DGLFRM and LGVG, both of which also consider the community structure but overlook the degree heterogeneity of graphs. The transformed latent variables learned by these three models plotted in Fig. It is clearly seen that our model performs best in fitting such directed graphs.
Table 7: Components of ablation variants. A circle denotes the component is involved.
22
S.A.T O
-A--
Q
T
Q
S
O
0
DLSM
17

---

Under review as a conference paper at ICLR 2022
Table Ablation study results (in %) for community detection.
Emails
Political blogs
Cora
mazro F1
micm
macro
micro
micro FI
mikro
-S---1
64.8 1.7
67.8 1.5
89.6 0.66
90.7 1 0.5
19.0
18.9 1
-A-F
66.5
1.
90.9
01
2.
0.
2.5
-S
6.
6.
91.1
9..3
20.9
2.
-HLSM
1.10
1.2
90. 90.6
0.
0.
DLSM
72.0
77.0
92.5 0.7
9.
24.6
25.7 3..7.00055
20-
-20
-20-
-20
-00
40
(a) VGAE
(b) DGLFRM
(c) GGVAE
-20
-20-
-00
(d) LGVG
(e) DGGAN
( DLSM
Figure 4: Visualizations of the latent positions learned on the Emails network using 2D t-SNE projection. Points in different colors denote nodes from the ground-truth communities.
18

---

Under review as a conference paper at ICLR 2022
Community membership The IBP prior enables the community membership 5 freely detect the true number of communities. In the experiments we set the truncation K2 to be 50/100, which are far larger than the true numbers of communities. Therefore, the hyperparameter (truncation) actually exert little impact for community detection. In Fig. 5 we illustrate the learned s with IBP and independent Bernoulli priors for fitting the Emails network, of which most nodes belong to of the 10 communities. A lighter color indicate a larger probability for the corresponding dimension (community) of latent variables be activated (* 0). It shows that IBP prior condenses the activated communities to be the first 10-15 dimensions, which is relatively approximate to the true number of communities, while the independent Bernoulli variables are much more chaotic and uniformly distributed at all dimensions. Therefore, the proposed IBP prior provide better interpretability for the community membership, addition the improvement of model performances.
200
0.8
200
08
600
600
32
(a) IBP prior (v = 0.9)
(b) Independent Bermoulli prior (y 0.5)
Figure 5: Illustration of the community membership with different priors learned the Emails network.
Reverse node random factors The pairwise node random factors 7 and ô; are supposed to measure the heterogeneity of out-degrees and in-degrees, respectively, which typically follow the power-law (Barabási & Albert 1999). Fig. ((a) and (b) present the probability density distributions (PDD) of the node degrees and reverse random factors learned by DLSM network. seems that the degree distributions are well fitted by the reverse node random factors, indicating that our DLSM can well represent the degree heterogeneity via these latent variables. Furthermore, Fig. 6 c) illustrates the complementary cumulative distributions (CCD) of the random factors. As can seen, the logarithm CCD of both % and 6, are approximately linear, with different slopes though. This shows that the proposed Dirichlet latent variables are flexible enough to accommodate the power-law distribution of degrees.
the political blogs
0000
0003
0025 1/v
out-degree
1/6 In-degree
1/v
60/0
0.003
10-1
0525
0.03
10-
0000
0.03
08
1.2
257
237
32*
(a) PDD out-degrees
(b) PDD in-degrees
(c) CCD random factors
Figure 6: Probability density distributions of the degrees and node random factors learned by DLSM.
19


Reviews:
[{"review_id": "keS38rwuX4P", "reviewer": "Reviewer_D8S8", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThe paper proposed an interesting graphical model for modeling the latent factors in directed graph adjacency matrix generation. The proposed solution that leverages VAE for optimizing the ELBO is also valid. Empirical results on the selected benchmarks seem to be significant as well. \n\nHowever I have several concerns regarding the current draft.\n\n1. Regarding the correctness of the paper, I’m a bit worried about the claims in Sec 5, saying that “we theoretically prove that the latent variables learned by our proposed method, …, are interpretable, …”. Given the fact that the paper uses a variational method to learn a variational posterior, where the posterior takes a mean-field approximation, there’s no guarantee that the model will learn the true posterior. So no matter how good the ideal posterior is, the framework proposed by the paper is not guaranteed to learn that.\n\n2. I’m not sure if the paper is well motivated. The model design seems to be arbitrary, with three components (latent position, community membership, node random factors) combined in an arbitrary way without justification. For example, why one has to adapt the IBP as a prior for Bayesian nonparametric purposes?  Given that you are doing truncation anyway,  I’m wondering whether you would gain anything using the Bayesian nonparametric for community assignment? \n\n3. The benefit of the deep hierarchical graphical model is not properly justified either. From the appendix it seems that the authors are using a 3-layer decoder by default. To justify the benefit of hierarchical graphical models, one should run the experiment with a 1-layer graphical model, parameterized with a 3-layer neural network. \n\n4. The experiments are conducted on small scaled graphs. How practical is it for the proposed method to be applied on realistic social networks? Having results on the latest benchmarks like OGB would be more convincing. \n", "summary_of_the_paper": "This paper proposed a directed graphical model called deep latent space model for modeling the graph adjacency matrix generation process, where the latent variables are organized in a hierarchical way with three meaningful components: “latent position”, “community membership” and “node random factors” for each node. The learning leverages the variational framework originated from VAE, with GCN as the core component for posterior parameterization. Experiments on link prediction and community detection show that the proposed method is able to achieve better empirical results. \n", "summary_of_the_review": "The paper lacks a motivation and justification for the proposed model design. The theoretical claim might not be correct. The experimental results are not convincing enough and larger scaled experiments on OGB are needed.\n\n---\n# After rebuttal: \nI would thank the authors' effort in addressing my concerns. However the concerns like the technical contribution and experimental improvements are not fully resolved, but I do appreciate the authors' effort in making the code accessible which improves the reproducibility in the community. I suggest the authors double check the code provided and make sure it is consistent as well. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XvnxHnSH-MP", "reviewer": "Reviewer_NCEy", "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": "Pros:\nThe paper is well-written and easy to read. The details of the model and related derivations are provided.\n\nFrom a technical viewpoint, the proposed model can be viewed as a new member of the probabilistic directed graph models. Its learning algorithm is based on (amortized) variational inference and the implementation is compatible with neural networks. Overall, the methodology is solid and interpretable. \n\nI like section 5, which provides some useful insights into the model.\n\n\nCons:\nIt seems that the proposed method is not as good as GGVAE on some datasets. It would be nice if the authors can explain this phenomenon to some degree.\n\nIn Figure 2, the authors should show the t-SNE figures of GGVAE and VGAE.\n\nBesides node embeddings z’s, the authors introduced another kind of latent code, i.e., s’s to indicate the community structure of a graph. It is worth doing an ablation study to demonstrate the necessity of this latent code.\n\nThe influence of the number of layers on the performance of the model should be discussed.\n", "summary_of_the_paper": "In this paper, the authors proposed a new directed graph representation model. The proposed model is developed from a Bayesian viewpoint and is implemented in the framework of the variational autoencoder. Additionally, the authors justified the interpretability of the model. They indicate that the proposed model quantitatively captures the influence of each node on its neighbors. Experimental results show that the proposed model performs well in commonly-used datasets. ", "summary_of_the_review": "Overall, the methodology of this work is solid, which is a reasonable combination of several solid probabilistic models. The learning method is easy to implement. Although the novelty of the whole method is not very strong, the experimental results show its feasibility to some degree.  ", "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": "XQT5wohhcPQ", "reviewer": "Reviewer_bcyE", "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": "Overall this paper is well-written and easy to follow, but the technical contribution is incremental, given that VAEs have been used to represent undirected graph-structured data [1,2,3]. It seems a natural extension of hierarchical VAEs to directed graphs, with some sort of variables for edge direction. The strong points include (1) a VAE with some well-tailed designs to directed graphs, (2) efforts to interpret latent variables, and (3) seemingly promising experimental performance.\n \nThe technical weakness mainly comes from the design of the model architecture and experiments. (1) I’m not fully convinced by the model design that variables in the decoder (e.g., z^(i) ) are lay-by-layer influenced by those in the encoder (e.g., H_z^(i)). I’d like to see an intuitive explanation and experiments that show z^(i) conditioned on H_z^(i) performs better than alternative model architectures. (2) As there are so many latent variables to be inferred (n*L*4), seen in Equation 11, I doubt the effectiveness of VI. Is there any model collapse when you optimize Equation 11? You can refer to [4,5,6] for mode collapse in VI. (3) In terms of experiments, I would ask the authors to try some directed graph networks as baselines, not limited to variational or Bayesian. As the authors said, most baselines are “designed for undirected graphs and are not appropriate for learning on asymmetric adjacency matrices”, and the authors modified these baselines for directed graphs. More commonly-used directed graph models as baselines will be convincing, such as [7,8,9]. (4) It’s good to present a model sensitivity analysis of hyper-parameters.\n \nMinor weakness: (1) the \\theta in the second last line on page 3 is claimed to denote the collection of model parameters, but it has been used to denote the collection of latent representations in the first paragraph in section 3. Fix this misuse. (2)In the first sentence of the second paragraph on page 4, the authors said four types of latent variables, but in the first sentence of the second paragraph on page 2, they said three types. (3) In the first sentence on page 7, “A extreme” should be “An extreme”. (4) Misplaced subgraph titles in Figure 3 in Appendix.\n\n[1] Thomas N Kipf and Max Welling. Variational graph auto-encoders. In NIPS Workshop on Bayesian Deep Learning, 2016.\n\n[2] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International Conference on Machine Learning, pp. 2434–2444, 2019.\n\n[3] Guillaume Salha, Stratis Limnios, Romain Hennequin, Viet-Anh Tran, and Michalis Vazirgiannis. Gravity-inspired graph autoencoders for directed link prediction. In ACM International Conference on Information and Knowledge Management, pp. 589–598, 2019.\n\n[4] Lucas, James, et al. \"Understanding posterior collapse in generative latent variable models.\" (2019).\n\n[5] Deasy, Jacob, Nikola Simidjievski, and Pietro Liò. \"Constraining variational inference with geometric jensen-shannon divergence.\" arXiv preprint arXiv:2006.10599 (2020).\n\n[6] He, Junxian, et al. \"Lagging Inference Networks and Posterior Collapse in Variational Autoencoders.\" International Conference on Learning Representations. 2018.\n\n[7] ​​Zhang, Xitong, et al. \"MagNet: A Neural Network for Directed Graphs.\" arXiv preprint arXiv:2102.11391 (2021).\n\n[8] Ou, Mingdong, et al. \"Asymmetric transitivity preserving graph embedding.\" Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.\n\n[9] Funke, Thorben, et al. \"Low-dimensional statistical manifold embedding of directed graphs.\" arXiv preprint arXiv:1905.10227 (2019).\n", "summary_of_the_paper": "This paper studies a deep latent space model for directed graph representation. The model is basically a hierarchical variational auto-encoder architecture and some latent variables like social activity and popularity factors of node account for the edge directions. Some latent variables are interpreted as positions in the latent space or community membership. The model, therefore, is claimed to be interpretable and superior in experiments.\n\n----Update after rebuttal\n\nThe authors basically answered my questions and I'd like to increase the recommendation score. I still think this submission has incremental technical contributions so my new recommendation score is 6 (marginally above the acceptance threshold).", "summary_of_the_review": "Given the above content, I think this paper is an okay submission, and I will give boardline rejection. I’m willing to increase the score if the authors (1) intuitively and empirically motivate the layer-by-layer variable dependency in the decoder, (2) analyze the effectiveness of VI and how your method prevents mode collapse, (3) conduct comparative experiments with suggested baselines, and (4) analyze how your model is sensitive to the community number.\n \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": "H0xMfjXVsHr", "reviewer": "Reviewer_s9T6", "summary": "", "questions": "", "limitations": "", "rating": 3, "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:\n1. Explicit modeling of community structure, latent positions, and random node factors. \n2. The asymmetric modeling of link existence thus suitable for directed graphs.\n3. The learned node embeddings have some interpretability.\n\nWeaknesses:\n1. Experiments did not compare with state-of-the-art non-VAE-based GNN methods, nor discussed them. For example, the state-of-the-art link prediction method, SEAL [1], should be compared. It can work on directed graphs too. Merely from Table 5 and results reported from [2], SEAL achieves better performance on Cora and Pubmed than the proposed method.\n2. Some larger datasets should be used to evaluate the scalability as well as the effectiveness for large networks. Currently, the largest dataset used contains 15,763 nodes and 171,206 edges. However, people are switching gradually to larger datasets with millions of nodes/edges such as Open Graph Benchmark [3].\n3. No ablation study on whether the proposed $s,\\gamma,\\delta$ are useful.\n\n[1] Zhang, Muhan, and Yixin Chen. \"Link prediction based on graph neural networks.\" Advances in Neural Information Processing Systems 31 (2018): 5165-5175.\\\n[2] Zhu, Zhaocheng, et al. \"Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction.\" arXiv preprint arXiv:2106.06935 (2021).\\\n[3] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).", "summary_of_the_paper": "This paper proposes a VAE-based graph representation learning model for directed graphs. The model is composed of a GCN encoder and a hierarchical latent space model decoder. The decoder explicitly models three kinds of node representations: the node latent position vectors $z$, the community membership vectors $s$ and node random factors $\\gamma,\\delta$. Specifically, the community membership vectors $s$ are used to gate control which of $z$ and $\\gamma,\\delta$ pass to the next layer. And finally the adjacency matrix is reconstructed by the distance between $z$'s filtered by node influences $\\gamma,\\delta$. Experiments show better link prediction and community detection performance than plain VGAE and other VGAE methods.", "summary_of_the_review": "Overall, although the paper proposes some interesting ideas by explicitly modeling community structure, latent positions, and random node factors, the paper lacks a discussion and comparison with state-of-the-art non-VAE-based baselines and uses relatively small datasets in the experiments, thus is less convincing in performance. Considering the abstract states \"The experimental results on real-world graphs demonstrate that our proposed model achieves the state-of-the-art performances on link prediction and community detection tasks\", I cannot recommend an accept given that stronger baselines clearly exist.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Meta-review: This to me looks like quality work not yet adequately developed, and thus is borderline work.  The authors seem to have achieved a good result:  equalling SotA SEAL (although, one reviewer did preliminary experiments and could not match this) with a sophisticated algorithm using a variety of Bayesian tricks, a more scalable algorithm, and one potentially adapted to further tasks.  However, not all of these impressive feats are adequately demonstrated in this paper, though many had parts included in the rewrite.  So I'd say the paper needs a rewrite and more focussed experimental work to broaden the presentation of empirial performance, for instance to node classification.
I certaintly appreciated the use of IBP and Dirichlet models within the system, so would love to see the work further developed.
The reviewers agreed in several aspects:  (1) more experimental work, for instance on better and larger benchmark data, (2) better presentation and discussion of the theory, (3) better discussion of the motivation for the model (as per reviewer D8S8), and oftentimes linked to the ablation study to support this, which you have done some of (4) additional connections to recent related work in graph representation learning on link prediction works
The authors have done a good job or addressing many of the reviewers concerns, ultimately lifting the paper from Reject to Borderline Negative, but I think more work is needed.
Decision: Reject