Low-dimensional statistical manifold embedding of directed graphs
Authors: Thorben Funke
Tian Guo
Alen Lancic
Nino Antulov-Fantulin
Venue:  (2020)
Keywords: graph embedding
information geometry
graph representations

Abstract: We propose a novel node embedding of directed graphs to statistical manifolds, which is based on a global minimization of pairwise relative entropy and graph geodesics in a non-linear way. Each node is encoded with a probability density function over a measurable space. Furthermore, we analyze the connection of the geometrical properties of such embedding and their efficient learning procedure. Extensive experiments show that our proposed embedding is better preserving the global geodesic information of graphs, as well as outperforming existing embedding models on directed graphs in a variety of evaluation metrics, in an unsupervised setting.

Published as a conference paper at ICLR 2020
LOW-DIMENSIONAL STATISTICAL MANIFOLD EMBED- DING OF DIRECTED GRAPHS
Thorben Funke
Tian Guo
L3S Research Center
Computationl Social Science ETH Zürich
Leibniz University Hannover
Hannover, Germany
Zurich, Switzerland
Alen Laneic
Nino Antulov-Fantulin
Faculty of Science
Computationl Social Science
Department of Mathematics University of Zagreb, Croatia
ETH Zürich
Zurich, Switzerland
anino@ hz. ch
ABSTRACT
We propose a novel node embedding of directed graphs to statistical manifolds, which is based on global minimization of pairwise relative entropy and graph geodesics in a non-linear way. Each node is encoded with probability density function over a measurable space. Furthermore, the geometrical properties of such embedding and their efficient learning procedure. Extensive experiments show that our proposed embedding better in preserving the global geodesic information of graphs, well outperforming existing embedding models on directed graphs in variety of evaluation metrics, in an unsupervised setting.
analyze the connection between
INTRODUCTION
In this publication, we study the directed graph embedding problem in an unsupervised learning setting. graph embedding problem usually defined as a problem of finding vector representation X E R for every node of a graph G = (V, E) through mapping Φ: V + X. On every graph G G= (V, E), defined with of nodes V and two vertices is defined the number of edges connecting them in the shortest path, also called graph geodesic. In case that is equipped with a distance metric function dx x X + R.,, we can quantify the embedding distortion by measuring the ratio dx dg between pairs of corresponding embedded points and nodes. Alternatively, one can measure the quality of the mapping by using a similarity function between points. In contrast to distance, the similarity is usually a bounded value [0, and is in some ad-hoc way connected to a notion of distance e.g. inverse of the distance. Usually, are interested in low-dimensional (K < n1) embedding of graphs with n nodes possible to find an embedding [32] with Loo norm with no distortion in an n-dimensional Euclidean space. Bourgain theorem (1985) 6 proved that it possible to construct an Olog (r))g(()))))))) ((lo(()))-dimenstt -dm)-diimnsional Euclidean embedding of an undirected graph with nodes with finite distortion.
edges E, the distance dæ Vx V - R_ between
always
For the last couple decades, different communities such as machine learning [6 33 10 physics 29
40
38 35], and computer science 42 43 independently from mathematics community
32
25
nutshell, they can be characterized by having one of the following properties (i-iv). (i) The Type of loss function that quantifies the
12 developed novel graph representation techniques.
distortion is optimizing local neighbourhood [44] 21 or global graph structure properties [53]
40 [4].
(ii) The target property to be preserved is either geodesic (shortest paths) 42 43
[2] or diffusion
distance (heat or random walk process) 46: 40: [4] or another similarity property 21
55 39].
(iii) The mapping is a linear
223
39 lonelinear dimensionality reduction technique such as
SNE (1]] t-SNE [55], ISOMAP
53 Laplacian eigenmaps 3 or deep learning work DeepWalk [40),
2ode2vec
[4]
HOPE 39]. GraphSAGE
17 NetMF 33 and others [16]. (iv) The geometry of

---

Figure 1: Visualization of synthetic example network together with our embedding. The graph is embedded into the 2-variate normal distributions, which are represented by ellipse (boundary of standard deviation around mean pt). The a ellipses of the green nodes are contained in one of the greys nodes, which represents that the distance (measured with divergence in embedded space) Published as a conference paper at ICLR 2020
20
0
220
-20
20
between green and grey is small, but the opposite direction very large.
X has zero curvature (Euclidean) B2 12 positive curvature [57 (spherical) or negative curvature
29
35 T0] (hyperbolic) mixed curvatures
[5]
However, for directed graphs the asymmetry of graph shortest path distances da(u;: ut) F da("), v;) violating the symmetry assumption (not metric function). This is the reason why only recently this problem was tackled by constructing two independent representations for each node (source and target representations) [39 59] (27). In this paper, we propose a single-node embedding for directed graphs to the space of probability distributions, described with the geometry of statistical manifold theory. Up to this point, different probability distributions were used for different embedding purposes such as: (i) applications to word embedding [45] [5)]. knowledge graphs 220. attributed graphs 4 or (ii) generalized point embeddings with elliptical distributions [36, but not for oow-dimensional embedding of directed graphs, characterized by the theory of statistical manifolds.
The main contributions of this paper are: We propose a node embedding for directed graphs to the elements of the statistical manifolds (51), to jointly capture asymmetric and infinite distances in a low-dimensional space. We determine the connection between geometry and gradient- optimization. (ii) Furthermore, develop sumpling-based scalable learning algorithm for large- scale networks. (iii) Extensive experiments demonstrate that the proposed embedding outperforms several directed network embedding baselines, i.e. random walks based (59] and matrix factorization
based 339 methods, as well as the deep learning undirected representative [40] and deep Gaussian embeddings for attributed graphs
2 STATISTICAL MANIFOLD DIVERGENCE EMBEDDING FOR DIRECTED GRAPHS
In this section, we analyze the limits of metric embedding. Then, we continue by providing an intuition of our embedding with a synthetic example before presenting the learning procedure of the embedding method. Bourgain theorem (1985) [6 states that it possible to construct an (log(n))- dimensional embedding (Ø: + x.) of an undirected graph with nodes to Euclidean space with (log(n)) distortion by using random subset projection. But, on directed graph G (V, E), the directed shortest paths are not necessarily symmetric d, u * d..r. This does not imply that it is not with a variant of Bourgain theorem. In the appendix A.T show that the main problem is asymmetry, but the existence of infinite directed distances, which is quite common in real directed networks, see Table
possible to provide low dimensional metric embedding 6 32 25 [2
2.1 LEARNING STATISTICAL MANIFOLD EMBEDDING
Instead of a conventional network embedding in a metric space, we propose to use the Kullback- Leibler divergence defined on probability distributions to capture asymmetric finite and infinite distances in directed graphs. Each node is mapped to a corresponding distribution described by some parameters, which learn during training. In this paper, we choose the class of exponential power distributions due to analytical and computational merits. With minor modifications, our method can also be applied to other distribution classes.
2

---

Published as a conference paper at ICLR 2020
a toy example to qualitatively illustrate that our embedding can represent infinite distances without requiring a high dimensional embedding space. More precisely, the network consists of five groups (color-coded), with five nodes each. The two top blocks have connection only to the center group and, similarly, the two bottom groups have only a link from the central group to them. Our model learns this connectivity pattern by embedding members of these groups in similar fashion. In this example, each node u is embedded as 2-variate normal distribution with mean yv, (Mu (e) and variances Σ. diag(o o which can be visualized by the o-ellipse, the curve which represent one-o distance from their respective means. The nodes of graphs are embedded by minimizing the difference between the pair-wist graph distances and corresponding Kullback-Leibee divergences between embeddings. For two distribution p(x), ((x), , if p(1) >> g(x) on an open subset U, the Kullback-Leibhe Leibler divergence (T((p(x), ((x)) then relatively high. In other words, if in Tigure[the o-ellipse of node u is contained in or very similar to the a-ellipse of node v, then the embedding represents d(u, v) < oc. Using this, we see that the embedding retrieved by our optimization and visualized in Fig. Lincludes most of the observed infinite distances.
Intuition. In Fig.
Statistical manifold embedding. Our embedding space is the space of k-variate exponential power distributions (37 (also called generalized error distributions), described by the following probability density function for > 0
AN (x E. 2 2 det E))T((((
[x p1) E (r [1)
exp
(1)
2
with mean vector i E & and covariance matrix Σ E Rixk I(.) denotes the Gamma function and x² denotes the transposed vector of z. Note that X 2 results in the multivariate Gaussian distribution and À = yields the multivariate Laplacian distribution. As we are interested in non-degenerate distributions,
enforce positive definite co-variance matrices and further restrict ourselves to diagonal matrices, i.e. E, = diag(o".. .. ...,.,)) oh) with of E R.. With the latter, we reduce the degrees of freedom for each node to 2k: and simplify our optimization by replacing positive definite constraint on Σ,, with the constraints of, > O. common asymmetric function operating on continuous random variables is the Kullback-Leible divergence. The asymmetric distance between nodes u and v, denoted by kL is
KL KL pú)
dx pe
with p2 ()x(r)) ph) and p. (a Mn), We approximate it with importance sampling Monte Carlo estimation. In particular, KLn,w can be expressed as the expectation (for X = 2 2 X)
P
KT E. Bg
log
PM
where p x'xx (x) Eg, (.)) is easy to sample and proposal function for px (x E.. p.). If closed expression for KL,,v is known, its evaluation replaces the importance sampling Monte Carlo estimation, like in the special case of X 2. See Appendix AA9 for more details.
Now, in order to learn these statistical manifold embeddings, we can define the loss function over asymmetric distances (du,e),,eev of directed graph and { Σn)} as:
(H((H,)E))) Σ 11(1 KLu,v)
d_ 112.
where R., is a free (trainable) parameter and R, a fixed value. This loss function given in the Eq. (2) is minimized during the learning process so that the KL, based on learned node distribution representations captures the distances du in the directed graph. Empirically, we transform the given distances into finite numbers with d e [o, 1], for all u لf v and a 3 E R,, which can be used to increase the differentiation between large du,. values and between finite and infinite distances. We modify the unbounded Kullback-Leibler divergence in similar fashion (1 + 7 KL [o. 1], where 7 E R, is free (trainable) parameter and the additional 1 ensures a value in the same interval [0, 1]. We start the optimization from random initial parameters {Mu. Σn Juev and iteratively minimize the loss function with stochastic gradient descent optimizers, such as Adam (28). For small k, which will consider in the next section, more enhanced initialization strategies, such using
3

---

Published as a conference paper at ICLR 2020
graph plotting algorithms to determine the means and exploiting memberships of strongly connected components for the covariance initialization, probably reduce the number of training epochs.
Scalable learning procedure. The full objective function Eq. (2) consists of [V((V-- 1) terms and only graphs with up to the magnitude of around 10* nodes can be applied. To extend our method beyond this limit, propose approximated solution, where the size of the training data scales linearly in the number of nodes and thus can be applied to large graphs.
This approximation solution is based decomposition of the loss function Eq. hood term and singularity term as:
22 into neighbor-
((((uu En)
Σ I(1+ + KL.,)) -d d
+ d
u 6000
u
neighhorhood term
singularity
We efficiently sample from each of these sums for each node small number of B samples and optimize our model based on the sampled information about closeness and infinite distances.
One straightforward approach to approximate the neighborhood term is to use all direct neighbors. Yet, the number of samples available via the directed neighbors is limited by E), which usually corresponds small B in sparse real-world examples. Therefore, we apply for each node Seauthh-frrt-searchh into both directions until we retrieve B new samples. In this way, we obtain smaller e first, and the approximation tends the original term in the limit B + [V].
For the singularity term, we use the topological sorting (26) of the strongly connected components. In topological sorting of a directed acyclic graph, all edges are from lower indices higher indices (with respect to the topological sorting).
Two important restrictions are noteworthy. First, the reverse statement does not hold, i.c. not all infinite distances are given via single topological sorting (26). As consequence, we won't 't sample uniformly from all infinities, but from a subset of the infinities given by the topological sorting. Second, the construction of topological sorting is only possible for acyelic graphs, and most directed graphs have cycles.
Since we only interested in sampling singularities and the graph defined by the strongly connected components of directed graph is acyclic, we use Tarjan's ' algorithm [52] to retrieve the strongly efficiently
connected components and topological sorting of them. After this preprocessing, generate samples of infinite distance for the nodes.
With these two approximations we can construct two sets Uclose and Use and the loss function reduces to
Č= Σ 11(1 kLu,,)
d
Σ (u,v)EU>>
1I(1 + KLn,,)
d
(u,v)EUem.:
Lemma 1. Let = (V, EV.E) be a graph. Then our embedding has 2k|V| + degrees of freedom and one hyperparameter (B). Generating the training samples for the full method, is equivalent to the all pair shortest path problem, which can be solved within 2 log [V|+ [V]+)) for sparse graphs and evaluating the loss function has time complexity (2V The scalable variant has, for [V), a time complexity of O(BB + 1)[V+ + (E)) and the loss function has O(B(V)) terms.
B &
See Appendix A.2 for proof using Johnson's 's algorithm 24 and the pseudo-code of our methods.
STATISTICAL MANIFOLDS AND DIRECTED GRAPH GEOMETRY
In this section, show the properties of representation space and the effects on our learning procedure.
Theorem Let be an even number. Then the distributions with density of Eq. / and parametriza- (>xxx = diag(oo).....
tion (a+ ... " (......+)) - X
(n².... ....,,,. )r*)) with o² > 0
are a statistical manifolds S with the following properties:
1. For univariate exponential power distribution, the curvature is constant and equal - -1/2.
4

---

Published as a conference paper at ICLR 2020
2. the Fisher information matrix, i.e. the Riemannian metric tensor, in this coordinate system at point (x(x (1) with Σ = diag(o
0") and μ = (p)
is given by
(gt)) = diag
C1
C1
C2
C2
(al)2
(ak)2
(a1)2
(at)2
where
r(1 1)1(1-11 -
C1
02 0= X.
I(2)
3. the Riemannian distance between (2: E, 14) and th (x) (x is
(ni-
+ for - و2:²
dr(bx (2), (1) R))
arcosh?
1+
20
((t)
with (1-
See the Appendix A.4 for more details and proofs.
The first observation of Theorem is that the geometry of the statistical manifold has constant
negative curvature (see [22] 48 58 for detailed derivation). Negative curvature also comes
natural model for power-law degree distributions complex networks 229 38 Fig. of Appendix
A.5 we exemplify the negative curvature of our embedding for the graph representations of Fig. by making the isometric mapping (preserving distances) to the hyperbolic space. See the Appendix A.5 for the derivation of the used isometry. Since our representation space is not flat, the Riemannian
metric is different from the Euclidean. Therefore, we need to adjust the Euclidean gradient VL of one of our objective functions L E {C, L} with respect to the metric tensor [2]. The steepest descent direction is given by VL = VV. where G-1 is the inverse of the metric tensor G of S evaluated the specific point. In other words, starting from the same representations and performing step into the direction of V will always result in lower values of the loss function L than going into the direction of V L. In our experiments, report the results using L. Further discussions and details can be found in Appendix A.8
With the last property of embedding space, the non-Euclidean Riemannian distance, is important for embedding based applications, like clustering. Note, that the value of c3 is approximately close to the value 1.0 for different values of It implies that after the embedding is done with one family of distributions, we can see that the pair-wise Riemannian distance of embedded points for different representations (A) is scaling only by the multiplicative factor VÀ (see Appendix A.4 for more details). Also note another useful connection, the Hessian of KI. divergence
Fisher information metric Rtj. When the Fisher distance is small, we have KL (på |l pt) x (p pd)² < dp (p. ra). Furthermore, the Fisher information metric unique (up to scaling) and the only Riemannian metric on the statistical manifolds (9) 8). Due to this fact and its connection with KL divergence, this the reason why we have not used other divergence functions.
EXPERIMENTS
4.1 DATASETS
From the Koblenz Network Collection [30 we retrieved three datasets of different sizes and connec- tivity. See Table [ for overview.
Political blogs. The small dataset is compiled during the 2004 US election [I addition, we evaluate two larger networks with different proportions of reachability between their nodes.
Cora. [50] consists citations between computer science publications and was used as an example in baseline APP [59 and HOPE 39 as well.
Publication network. With a higher density but lower reciprocity, our largest example is the publication network given by arXiv's High Energy Physics Theory (hep-th) section (11.
5

---

Published as a conference paper at ICLR 2020
Table 1: Properties of datasets
Name
[V]
E
[du,0 du, = /
Reciprocity
Synthetic example
25
30
0.48
34.3%
Political blogs
1224
19,025
0.34
24.3%
Cora
23,166
91,500
0.83
5.1%
arXiv hep-th
27,770
352,807
0.71
0.3%
4.2 BASELINES
APP is the asymmetric proximity preserving graph embedding method [59] based the skip-gram model, which is used by many other methods like Node2 and DeepWalk. In contrast to the symmetric counterparts, APP explicitly splits the representation into source vector and target vector, which are updated in direction-aware manner during the training with random walks with reset. Their method implicitly preserves the rooted PageRank score for any two vertices.
This method uses a generaliza- tion of the singular value decomposition to efficiently retrieve low-rank approximation of proximity measures like Katz Index or rooted PageRank.
HОРE stands for High-Order Proximity preserved Embedding 39
DeepWalk the deep learning representative of the undirected graph embedding methods. It does not differentiate between source and target and retrieves single representation E R& for each node. Like APP, DeepWalk uses the skip-gram model, trains the representation with random walks, and evaluates by cosine similarity between two node representations.
Graph2Gauss trains a neural network to output mean and variance of Gaussians way such that ranking loss is minimized [5] Their loss function concentrates on preserving the 1-hop and 2-hop neighborhood, but not the global graph structure (du,v > 2). The method was designed for graphs with additional node feature data, and in the absence of such information, one-hot vector encoding should be used instead.
4.3 SET-UP
In this paper, we focus on directed network embedding, which preserves global properties of directed graphs. Considering this, our emphasis is different from the conventional evaluation tasks of network embedding, e.g. the link prediction task only evaluates the differentiation between (u, v) = 1 and d(u,v) > 1, which respectively correspond the case of link existence and not.
Evaluation metrics. Three evaluation metrics are used on the pairs of inverse true distances and approximated values derived by learned embedding from baselines and our methods. We use the Pearson correlation coefficient for checking linear dependency [47] and Spear- man's rank correlation coefficient r for evaluating to these statistical measures, we propose to use information-theoretii non-linear evalua- tion metric, i.c. mutual information (MI). We choose the non-parametric k-ncarest-ncighbor based MI estimator, LNC [13] It is recently developed to overcome local non-uniformity and can capture relationships with limited data. We briefly describe the LNC MI here as: p(a.9)
monotonic relationship.
addition
& Σx=1 log V(n) where N is the total number of data instances, the second term a correction term handling non-uniform region V(n) surrounding point n, and p(.) represents the kNN density estimator.
i= NN Em=1 log p(x)-
V(n)
Hyper-parameters. With the nonlinear interactions our embedding, our method needs only a small number of dimensions, and for the presented results used embedding into 2-variate normal distribution, i.c. = 2 and the number of free parameters for each node is 4. The initial means n. and variannces Σ,, randomly initialized.
For the random walk based methods APP and DeepWalk, we unified both default settings with 20 random walks for each node and length 100. The embedding dimension was set to K = 4, where allowed APP to use two dimensional vectors. In the same fashion, we set the embedding dimension for HOPE to 4, resulting in two [V] matrices. All other parameters we left at the default value. For

---

Published as a conference paper at ICLR 2020
proposed embedding, evaluate both the exact and approximate version. For the approximate one, we report the results based on B 10 and = 100 samples for each node.
We exccuted the optimization with 3 E { 3: 2 1 and consistently retrieved the best results for 3 For our method, selected from the runs the point with the highest Pearson correlation between d and (1 + x ) which usually coincided with the minimal observed objective function value, like in Figure In the experiments, applied Adam optimizer with learning rates in [.001,001,-. } and retrieved the reported results with the 11 for political blogs and .001 for the others.
HOPE was executed with GNU Octave version 4.4.1, and the other methods executed in Python 3.6.7 and Tensorflow on a server with 258 GB RAM and a NVIDIA Titan Xp GPU.
4.4 RESULTS
First, we compared the performance of the embedding using different X, i.e. different classes of distri- butions. From the results in Appendix 3 we observe no significant performance improvement. So we fixed
for the other experiments have the performance gains of the analytical known KI. divergence.
Table 2 shows the results of evaluation metries on different datasets. KL(-) and KL((full) refer the approximate and exact version of our proposed embedding. We report the mean and standard deviation of MI by 40 bootstrap samples. For all metrics, the higher the value, the better the performance.
The results support this intuition that our method retrieves the highest values in all cases and significantly outperforms baselines. In addition, our approximated variant using only 10 neighbors and 10 infinities for each node already achieves higher values than baselines. Increasing the number of samples to 100, further enhances the performance of the approximate version, which even embeds the large network in similar quality
full method. A visualization of the results is given in Figure Further details are the Appendix [A.6] Additional experiments such as dimensionality experiment, graph reconstruction, and evaluation on undirected graph can be found in Appendix A..
Table 2: Results including Pearson correlation coefficient p. Spearman's 's rank correlation coefficient and mutual information (MI). The p-value for p and r are in all cases below 10-8 For our method, we include the results with 10 samples, 100 samples for each node, and using the full distance matrix.
Network
APP
HOPE
DeepWalk
Graph2Gauss
KL (10)
KL (100)
KL. (full)
Political
P
.45
.25
-.17
.73
.77
.88
Blogs
r
.29
.45
.24
-.33
.71
.72
.89
avg. MI
.15
.65
.12
.09
.47
.59
.85
std. MI
.006
.007
.005
.005
.005
.005
.006
Cora
P .10
.17
.07
.000
.53
.66
.77
r
.02
.013
.56
.62
.65
avg. MI
.018
.13
.013
.01
.23
.35
.43
std. MI
002
.005
.004
.003
.005
.006
.007
arXiv
.01
.20
.08
-00
.53
.62
688
hep-th
.12
.28
.04
-006
.59
.68
.72
avg. MI
.033
.15
.014
.01
.25
.36
std. MI
.003
.004
.003
.003
.005
.005
.005
CONCLUSION AND DISCUSSION
40 14, there still exist obstacles for using them for directed graphs. Obstacle arises from the asymmetric property of graph geodesics and a large ratio of pairs with infinite distances. Motivated by this, we propose mapping of nodes to the elements of the statistical manifolds [5]] by minimizing the divergence function between embedded points a graph geodesics. This allows a single representation that allows elegant geometrical encoding of infinite and finite distances in -ww-dimensional statistical manifolds by using the divergence function. One can encode an arbitrary number of infinities into the dow-dinensional space, this embedding does need push point infinite geodesic distance
Although the techniques for graph embedding are quite mature 16

---

Published as a conference paper at ICLR 2020
Political Blogs
Cora
arxiv hep-th
1e-3
2
2
APP
I
1e6
1
HOPE
0
I
0
approximated values
Graph2Gauss DeepWalk
0
lel
2
0
0.5
0.5
0.0
0.0
inverse true distance
Figure 2: Visualization of approximated values w.r.t. inverse true distance (d with boxplots, representing the means, first and third quartiles as well as 1.5 interquartile range. Violin plots indicate the kernel densities. Columns respectively correspond Cora (second column), and arXiv hep-th (last column). Rows from top to bottom represent APP, HOPE, WeepWalk, Graph2Gauss, and our KL method. Ideally, as the ground-truth value increases, approximated values are expected to follow this trend as well. The baseline methods show only weak separation between the closest distances and all other. For our embedding method (last row) monotonic increasing relation is visible, which was reflected in the highest mutual information, Pearson and Spearman's ' correlation coefficient in Table
dataset political blogs (first column),
8

---

Published as a conference paper at ICLR 2020
on manifold. Furthermore, this embedding allows the of analytical tools from statisties and differential geometry, c.g. connection of curvature and natural gradient 2 48 7 In contrast to the previous work, we have characterized the geometrical structure of the underlying space which nodes are being embedded into, and its connection to the learning via curvature corrected gradient. Furthermore, we have proposed efficient divergence estimation method via importance sampling method. Theoretical understanding of the geometrical structures for directed graph embeddings opened many interesting theoretical and practical questions. This is the reason why had restrict the scope of this work only to unsupervised setting and leave link prediction and node classification task for future work.
REFERENCES
[1] ADAMIC, L. A., AND GLANCE, N. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery (2005), ACM, pp. 36-43.
[2] AMARI, S.-I. Natural gradient works efficiently in learning. Neural Comput. 10, 2 (Feb. 1998), 256-276.
[3] BELKIN, M., AND NIYOGI, P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15, 6 (June 2003), 1373-1396.
[4] BOJCHEVSKI, A., AND GÜNNEMANN, S. Deep gaussian embedding of attributed graphs: Unsupervised inductive learning via ranking. In ICLR (2018).
[5] BOJCHEVSKI, A., AND GÜNNEMANN, S. Deep Gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference Learning Representattons (2018).
[6] BOURGAIN, J. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics 52, 1-2 (Mar. 1985), 46 52.
[7] BURBEA, J., AND Rao, C. Entropy differential metrie, distance and divergence measures in probability spaces: A unified approach. Journal of Multivariate Analysis 12, (Dec. 1982), 575-596.
[8] CATICHA, A. The basics of information geometry. AIP Conference Proceedings (2015). AIP, pp. 15 26.
[9] CENCOV, N. N. Statistical Decision Rules and Optimul Inference (Translations of Mathematical Mono- graphs). American Mathematical Society, 2000.
[10] CHAMBERLAIN, B. P., CLOUGH, J. R.. AND DEISENROTH, M. P. Neural embeddings of graphs in hyperholic space. CoRR abs/1705. 10359 (2017).
[11] EFRON, B. Curvature and inference for maximum likelihood estimates. Ann. Statist. 46, 4 (08 2018). 1664-1692,
[12] FRANKL,, Journal of Combinatorial Theory, Series 44, 3 (June 1988), 355-362.
MAEHARA, H. The
lemma and the sphericity of some graphs.
[13] GAO, S., VER STEEG, G., AND GALSTYAN, Efficient estimation of mutual information for strongly dependent variables. In Artificial Intelligence and Statistics (2015), pp. 277-286
[14] GROVER, A., AND LESKOVEC, J. Node2Vec: Scalable feature learning for networks. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2016), KDD '1, ACM, pp. 855-864.
[15] GU, A., SALA, F., GUNEL, B., AND Ré, C. Learning mixed-curvature representations in product spaces. In ICLR (2019).
[16] HAMILTON, W. L., YING, R., AND LESKOVEC, J. Representation lcarning on graphs: Methods and applications, 2017. cite arxiv: 1709.05584Comment Published in the IEEE Data Engineering Bulletin, September 2017; version with minor corrections.
[17] HAMILTON, W. L., YING. Z., AND LESKOVEC. Inductive representation learning large graphs. In NIPS (2017).
[18] Hamsterster full network dataset KONECT, Sept. 2016.
[19] HAYTER, R. The hyperholic plane "a strange new universe", 2008. "Technical report, accessed May 2019".

---

Published as a conference paper at ICLR 2020
[20] HE, S., LIU, K., J1. G., AND ZHAO, Learning represent knowledge graphs with Gaussian embedding. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management (New York, NY, USA, 2015), CIKM 15, ACM, pp. 623 -3-2.
[21] HINTON, G., AND ROWEIS, S. Stochastic neighbor embedding. Advances neural information processing systems 15 (2003), 833-840.
[22] ICHI AMARI, S. Differential-eoomenn Geometrical Methods Statistics. Springer New York, 1985.
[23] JIANCHAO YANG, SHUICHENG YANG, YUN Fu, XUELONG LI, AND HUANG, T. Non-negative graph embedding. 2008 IEFE Conference on Computer Vision and Pattern Recognition (June 2008), pp. 1-8.
[24] JOHNSON, D. Efficient algorithms for shortest paths sparse networks. Journal of the ACM (JACM) 24, 1 (1977), 1-13.
[25] JOHNSON, B., LINDENSTRAUSS, J., AND SCHECHTMAN, G. Extensions of Lipschitz maps into Banach spaces. Israel Journal of Mathematics 54, (June 1986), 129-138.
[26] KAHN, A. B. Topological sorting of large networks. Communications of the ACM 5, (Nov. 1962). 558 562.
[27] KHOSLA, M., LEONHARDT, J., NEIDL, W., AND ANAND, A. Node representation learning for directed graphs. CoRR abs/1810.09176 (2018).
[28] KINGMA, D. P., AND BA, J. Adam: A method for stochastic optimization. arXiv preprint arXiiv:4422.66 (2014).
[29] KRIOUKOV, D., PAPADOPOULOS, F., KITSAK, M.. VAHDAT, A., AND BOGUÑÁ, M. Hyperbolic geometry of complex networks. Phys. Rev. E 82 (Sep 2010), 036106.
[30] KUNEGIS, J. Konect: the Koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web (2013), ACM, pp. 1343-1350.
[31] LESKOVEC, J., KLEINBERG, J., AND FALOUTSOS, C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1, 1 (2007), 2.
[32] LINIAL, N., LONDON, E., AND RABINOVICH, Y. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2 (June 1995), 215-245.
[33] LIU, X., MURATA, T., KIM, K.-S., KOTARASU, C., AND ZHUANG, C. A general view for network embedding matrix factorization. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (New York, NY, USA, 2019), WSDM '19, ACM. pp. 375-383.
[34] LOvÁsz, L., AND VESZTERGOMBI, K. Geometric representations of graphs. In IN PAUL ERDÖS, PROC. CONF (1999), Springer-Verlag, pp. 17-3.
[35] MUSCOLONI, A., THOMAS, J. M., CIUCCI, S., BIANCONI, G., AND CANNISTRACI, C. V. Machine lcarning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communica- tions 8, (Nov, 2017).
[36] MUZELLEC, B., AND CUTURL, M. Generalizing point embeddings using Wasserstein space of elliptical distributions. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems (USA, 2018), NIPS'15 18, Curran Associates Inc., pp. 10258-10269.
[37] NADARAJAH, S. A generalized normal distribution. Journal of Applied Statistics 32, (Sept. 2005),
[38] NARAYAN, O., AND SANIEE, 1. Large-scale curvature of networks. Phys. Rev. E 84 (Dec 2011), 066108.
[39] Ou, M., CUI, P., PEI, J., ZHANG, Z., AND ZHU, W. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD 16 (2016), ACM Press.
[40] PEROZZI, B., AL-RFOU, R., AND SKIENA, S. DeepWalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (New York, NY, USA, 2014), KDD '14, ACM, pp. 701-710.
[41] PEYRÉ, G., CUTURI, M., FT AI.. Computational optimal transport. Foundations and Trends in Machine Learning 11, 5-6 (2019), 355-607.
10

---

Published as a conference paper at ICLR 2020
[42] POTAMIAS, M., BONCHI, F., CASTILLO, C., AND GIONIS, A. Fast shortest path distance estimation in large networks. Proceedings of the 18th ACM Conference on Information and Knowledge Management (New York, NY, USA, 2009), CIKM '09, ACM, pp. 867-876.
[43] RATTIGAN. MAIER, M., AND JENSEN, D. Using structure indices for efficient approximation of network properties. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2006), KDD '06, ACM, pp. 357-366.
[44] ROWEIS, T. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500 (Dec. 2000), 2323-23222
[45] RUDOLPH, M., RUIZ, F. J. R., MANDT, S., AND BLEI, D. M. Exponential family embeddings. In Proceedings of the 30th International Conference on Neural Information Processing Systems (USA, 2016), NIPS' 16, Curran Associates Inc., pp. 478 486.
[46] SAERENS, M., FOUSS, F., YEN. L.. AND DUPONT, P. The principal components analysis of a graph, and its relationships to spectral clustering. In Machine Learning: ECMI. 2004 (Berlin, Heidelberg, 2004), J.FF Boulicaut, Esposito, F. Giannotti, and D. Pedreschi, Eds., Springer Berlin Heidelberg, pp. 371-383.
[47] SHALEV-SHWARTZ, S., AND BEN- DAVID, S. Understanding machine learning: From theory algo-
rithms. Cambridge university press, 2014.
[48] SKOVGAARD, L. T. A Riemannian geometry of the multivariate normal model. Scandinavian Journal of Statistics 11, 4 (1984), 211-223.
[49] STALEY, M. D. Models of hyperbolic geometry, 2019. "Technical report, accessed May 2019".
[50] ŠUBELI, L., AND BAJEC, M. Model of complex networks based on citation dynamics. In Proceedings 22nd international conference on World Wide Web (2013), ACM, pp. 527-530.
[51] SUN, K., AND MARCHAND-MAILLET, Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32 (2014), ICML' 14, JMLR.org, pp. 11-1-11-9.
An information geometry of statistical manifold learning. In
[52] TARIAN, R. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1, (1972), 146-160.
[53] TENENBAUM, J.. SILVA, AND LANGFORD, global geometric framework for nonlinear dimen- sionality reduction. Science 290, 5500 (2000), 2319-2323.
[54] TSITSULIN, A., MOTTIN, D., KARRAS, P., AND MÜLLER, Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference (2018), International World Wide Web Conferences Steering Committee, pp. 539-548.
[55] VAN DER MAATEN, L., AND HINTON, G. Visualizing data using L-SNE, Journal of Machine Learning Research 9 (2008), 2579-2605.
[56] VILNIS, L.,, AND MCCALLUM, A. Word representations via Gaussian embedding. In ICLR (2015).
[57] WILSON, R. C.,, HANCOCK, E. R., PEKALSKA, E., AND DUIN, R. Spherical and hyperbolic embeddings of data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 11 (Nov 2014), 2255-2269.
[58] YUAN, M. On the geometric structure of some statistical manifolds. arXiv preprint arXiv: 1902.06144 (2019).
[59] ZHOU, C., LIU, Y., LIU, X., LIv, Z., AND GAO, J. Scalable graph embedding for asymmetric proximity. In AAAI (2017), S. P. Singh and S. Markovitch, Eds., AAAI Press, pp. 2942-2948.
11

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 LIMITS OF NOW-DIMENSIONAL METRIC REPRESENTATIONS
Definition define following metric function du,c = min (nn,, do,u).
Definition For > I, we say that the directed graph G (V; is a-asymmelric if Vu, v du, add,, (control maximal asymmetry).
The following Lemma can viewed as the corollary of Bourgain theorem. It implics that distortion w.r.t. directed graph is not finite when a = oc. Note that the co-asymmetry is quite common in real directed networks, see Table 1.
Lemma 2. If a graph is a-asymmetric, then there exists metric representations that uses random subsets embedding (Ø: E Te) in [Iog(n)] dimensional space, such that for every pair (u, the following bounds: | xella//aa du,e and B[I xelli// du,y 2 _ hold, where ||-I|1 denotes the Ll and El.] is the expectation operator over random subsets.
16m
((log(n))-dimensii)) emhedding (c): + s.e) of undirected graph with n nodes to Enclidean space with ((log(n) distortion by using random subset projection. Distortion defined as the ratio
Proof. Bourgain theorem (1985) 6 constructs
maxu.veV [ 1/ where du, denotes the shortest path in graph and |z.. æu|l1 the Ll distance between the embedded points. For directed graphs du, is not symmetric and we propose to use the metric da,.- = min(d..... de..) function, which fulfills the properties of non-negation negativityy, symmetry and triangle inequality (proof omitted).
wine [|xy bou-xxlls /du.e l/s//dd/
It is possible to construct the probability 1/2'. The following embedding for node j can be constructed as æj = (d)),A1). A1).... ...,.d(. d(j, Am)),
[log(n]] random subsets A; S V, where each node from V is put inside with
where å(j, A1) denotes distance from node j to set A.. Then, the following L1 bounds M for Bourgain theorem [6] for every pair (u, v) hold
|| - 20 S mda,e
and
B[[ xelli] 2 du,r/16.
where |]-I1ı denotes the L1 norm and [B]] the expectation operator over random subset.
Together with definition à and a-asymmetry gives [.n sulla/ du, S. m and E[[ - /elli// du. 2 Iea It implies that distortion w.r.t. directed graph is D 2 not finite when co.
maxu,etV || [| mulll/ /du..
maxa.eV [[a -oo - ////d, is
Bllre xx /
A.2 PROOF OF LEMMA
Lemma. Let (V, E) be a graph. Then our embedding has 2k|V| + 1 degrees of freedom and one hyperparameter (3). Generating the training samples for the full method, is equivalent to the all pair shortest path problem, which can be solved within O(V log V + [V[ for sparse graphs and evaluating the loss function has time complexity O(V The scalable variant has for < &V] a time complexity of O(BB + 1) |EE) and the loss function has O(B(V() terms.
Proof. The embedding maps each node u to a v-vaiiate normal distribution Nc, with mean μa. = (puy.... pu) and covariance E., diag(o)..... ..)). which are in total 24 [ parameters. With the trainable in objective function, we have in total 2 [V| degrees freedom.
Johnson's 's algorithm 24] solves the problem of all pair shortest path length in O([V) log log [V] The result are the 2 distances, which are used in the full loss function.
For the scalable variant, we need perform Tarjan's 's algorithm (52) one time, which has time complexity of O(VV [E). This assigns every nade its strongly connected component and the same time returns a topological sorting of the strongly connected component. Using this, sampling of infinities reduces to sampling from an array, which needs for B samples OBB). The neighborhood terms can be retrieved using a breadth- first search, which stops after finding B new samples. Under the assumption of B & [V] the total time complexity is O( + V) [F.). Finally, the approximated loss function uses two sums over each B V elements.
12

---

Published as a conference paper at ICLR 2020
A.3 ALGORITHM
To clarify our two algorithms, we include the pscudo-code of the full algorithm (Algorithm D and the scalable variant (Algorithm 2. The main differences between Algorithm aadd Algorithm is the reduced amount of pre-processing needed and consequentyy the reduced amount of elements the loss function Lemma gives the complexity for pre pr-prroessing and an optimization step.
Algorithm Full algorithm
Input: Graph G (V, F))
1: Pre-processing: Calculate all graph distances du,e. for all u, E V
2: Initialization: Uniformly sample random values for distribution parameters Pu, E,, for each node u E V
3: Optimizing: Update Mu, Eu, using Adam optimizer and loss function L
Algorithm Scalable algorithm
Input: Graph G (V, E))
1: Pre-proce pre-processing: Calculate the strongly connected components and their topological sorting using Tarjans algorithm. Sample for each node E V up B nodes with du, oc.
2: Pre-processing: Perform for each node u a treadth-first-sene the predecessors sample up B nodes with du, oo
for the successors and another for
3: Initialization: Uniformly sample random values for distribution parameters Pu, En for each node u V
4: Optimizing: Update pa, Eu, T using Adam optimizer and loss function č
A.4 PROOF OF THEOREM 1
Let us consider a surface S fy (μ, Ø): (u, 0' E R x }+} of natural logarithms PDFs univariate exponential power distributions parameterized by their expectation and deviation, y (H, = In (al (p, o)) Z (~ For given μr, a, À let have an exponential power distribution with those parameters and define the inner product at (H, as (y)ly)) (p,o) == E [ln (pi (X(,,))) In (p2 (X (X),, o)]]. Let us calculate the metric coefficients:
a²2(A (1 1)
X - aj A-2
9n o) =
o²
a2>(x-1) 11 E (X a-2 A-2
a2> 1) 1) T (
d²
22A 1) (1-
0²
(())
g²
T(2)
ax n1) A-1
a12
912 (api o) =921 (a)1, = E
xx+1 E
(X
0,
x++l
(X - a41)
(au, =- σ² A(A + 1)
a²+2
(
A( 1(++))r(*t)
A
(X a4)aa
+
o2
x+2
o²
T())
I(+)
We that that for
the metric tensor at (aju, a) is given by
V (x-1)r(113) 2)
-2
gF (ap, =
Aaxa (H,
0
22
13

---

Published as a conference paper at ICLR 2020
Similarly, for a multivariate exponential power distribution with parameters μ (uz pex) E diag (fI...., ok). A, we get gr (aps 2) = À diag (01 2 ,...., get
Ok x=2
ox 22) = Aggza (fe. Σ) so we
(af,, 2) p = /xxT Or (ap, Σ)x= vx Agua (n, Σ) x VAlix (m,, E)|
de (x (aper E1) x (apzz Ez)) = =v yaa (er, E1). (uz, Ez))
arcosh? (1+ (Je1 pia) 2 (0tl - 012)
20110022
from which it follows that
(1+
[1ن) - 2 (as1 012)
de (x (Hu, Ex). x (u2 Σz))
Σ arcosh?
1+
20.10/12
The detailed derivation of the curvature for the univariate case is given in [58] where the closed form solution for a-Gaussian curvature is given. In this paper, we are interested only in the case a = 0 Gaussian curvature of the Riemannian metric, which leads to the -1/A curvature.
A.5 DERIVATION OF MAPPING FROM GAUSSIAN STATISTICAL MANIFOLD TO HYPERBOLOID
To see how the points the manifold relate each other in terms of distance, we will map them to the upper half of a two-sheathed hyperboloid (see Figure 3) while preserving their distance up to a multiplicative constant factor, To do this, we first map a point (1, 0) to the Poincaré half-planc through the mapping (n,, 0) + (H/V2, 0), which can be shown to be similarity with the similarity coefficient v2
7 Then we isometrically map the Poincaré half-plane the Poincaré disc by using the Cayley mapping 19 We finish by mapping the Poincaré disc to the above- above-mentions mentioned hyperboloid by using the inverse of the stereographic projection. which can be shown is also an isometry [49]. where the distance of two points on the hyperboloid is the length of the curve which is an intersection of the hyperboloid and the plane passing through the origin and those two points. Note that the composition of these three maps is also a similarity with the similarity coefficient /2.
We have combined existing 7 19 49). well-known results about similarities, isometries and geodesics being mapped by those maps between the Gaussian stnchastic manifold and various models for the hyperholic geometry (Poincaré half- half-plane, Poincaré disc and two-sheathed hyperholoid), using minor adjustments suit our needs when necessary, allow casy, direct visualisation of distances between the points the stochastic manifold in the natural framework in which they were defined (hyperbolic geometry).
It is a well-know fact that the Cayley map (H, +>
+"((++))=+ ()+++1]) is an isometry from the
Poincaré half- to the Poincaré disc. It is also known that the stereographic projection of the upper half of the two-sheathed hyperboloid 2² - 2 y²² 1 through the point (0, 0, -1) to the plane is an isometry from the hyperboloid onto the Poincaré disc, it's inverse, which can be computed be (z, 3)
0
(VI-z-- VI--2-y2 V1-
also an isometry. To obtain the inverse, we must find
such that the point& ((2, y, (0,0, -1) (tx, ty,t) t) lies the hyperboloid, i.c. t² - (tx)) + (ty)² 1 VI- since we're interested only the upper sheath. From here, we read that the inverse of the stereographic projection is as stated above.
Finally, it he shown that similarity f: S1 + Sa maps geodesic a on Si a curve a on S2 which can be reparameterized by are length and such reparameterization ff a yp is a geodesic on S2. If f has the similarity coefficient c, then it is easy to see that ds, (r, y) = eds, (f (x) (v)) by using those two geodesics and the fact that geodesics are shortest lines between points they pass through.
A.6 FURTHER DETAILS OF EXPERIMENTS
For baseline HOPE, as input HOPE operates on any proximity measure S in the form M Mr, we use HOPE with M, the identity matrix and M;- ((1 8u, (dl,e +s)- Ju. the matrix of clement-wise inverse distances shifted by small 10-6 avoid division by zero The output of HOPE are two matrices U E / _ E R. K XX|V| and the approximated values are calculated via 8 U*.
The initial means nt, are drawn uniformly from [0, 10] and the initial co-variances of, are drawn uniformly from [4, 7]. As initial value of selected 2.5.
14

---

Published as a conference paper at ICLR 2020
Figure 3: Visualization of the hyperboloid geometry of directed graphs for one-dimensional Gaussian distributions. The coordinate frame is shown with the green (α) and orange lines (J)). The nodes from the synthetic directed network from Figure 1 are shown as points with different colors of groups, depending on the position in the network. The embeddings for nodes (H, σ)) in the statistical manifold found by minimizing the objective function (2) and then making the mappings the hyperboloid model.
Table Results the exponential power distributions for E {2, 4, 8} and 100 samples evaluated with Pearson correlation coefficient p. Spearman's 's rank correlation coefficient and mutual infor- mation (MI). P and r were evaluated on all edges (u, v) with u # e using the values given by each method and the ground truth distance. The p-value for p and are in all cases below 10-5.
Network
=
A= 4
Political
.77
.78
.78
Blogs
r
.74
.74
.72
MI
.57
.005
.61 + .005
.61 + .005
our method, we used batching for the political blogs network, 410 batches for Cora 2777 batches for arXiv hep-th with and without shuffling between each epoch, where we saw an increased performance with shuffling especially for the larger datasets. The approximated approach uses no batch for the variant with B = 10 and 10 batches for B 100.
The computation time of pre-processing and learning for (KL 10, KL 100, KL full) experiments were blogs (0sec/11.55mng 0min), Cora (15sec/2min/5. 5hours))) and arXiv hep-th (30sec/3min/1.50) (.ay)..
A.7 FURTHER EVALUATION EXPERIMENTS
In this section, report further results of experiments with different hyperparameters, another baseline for political blogs as well as down-stream task graph reconstruction and experiments on an undirected graph.
First, we want to verify different hyperparameters exponential power distributions. i.c. À E {2, 8). The results were calculated using the proposed importance sampling, see Appendix A.9 for more details. Since for higher À the evaluation measures do not increase significantly, have fixed 2 for the other experiments, due the analytical KL. divergence in that case.
our method. Table 3 shows the results for different
Another hyperparameter the embedding dimension. which translates to selecting k-variate exponential power distributions. hable/4reppott the results for E (2,5, 5, 10, 50}. Up to the value A 10 all values increase, whereby in particular the mutual information registers the strongest increase. A further increase of the dimension k=50 does not seem to bring any further advantage. Since the focus of this publication is on low-dimensional emheddings, have set & 2.
15

---

Published as a conference paper at ICLR 2020
Table Results of the k-variate exponential power distributions for E (2, 5, 10,50) of KI. (full) evaluated with Pearson correlation coefficient p. Spearman's ' rank correlation coefficient and mutual information (MI) and r were evaluated on all edges (u, v) with u A v using the values given by each method and the ground truth distance. The p-value for and are in all cases below 10 10-8
Network
==2
k ==
k = 10
k 50
Political
.88
.90
.91
.88
Blogs
.89
.90
.92
.90
MI .85 + .006
.90
= 007
.97
+ .006
.90
.006
Table 5: Comparision of results of elliptical embedding political blogs and method
Method
p
MI
Elliptical
-0.17
-0.14
.04 .004
KL (full)
0.88
0.89
.85 + .006
APP
0.16
0.29
.15 2006
HOPE
0.45
0.45
.65 + .007
DeepWalk
0.25
0.24
.12 + .005
Graph2Gauss
-0.17
-0.33
.09 + .005
the political blogs network, we have evaluated as an additional baseline elliptical embedding [36] The work [36] of Muzellec et al. studies the problem of embedding objects as elliptical probability distributions, which are the generalization of Gaussian multivariate densities. Their work is rooted in the optimal transport theory by using the Wasserstein distance. The physical interpretation of this distance in the case of optimal transport given by the cost moving mass from one distribution another one (see Mlonge-Kantrre transportation problem 41).. In particular, for univariate Gaussian distributions, the Wasserstein distance between embedded points becomes the two-dimensional Euclidean distance of (f), 01) and (122 02), i.e. flat geometry. In case, the geometry of univariate Gaussians has constant negative curvature, and distance is measured with the Fisher distance. Our work is rooted in statistical manifold theory, where the Fisher distances arise from measuring distinguishability between different distributions. According to the results Table we observe that this method not outperforming our method.
Our method was created with the motivation to embed directed graphs. However, we also evaluated the perfor- mance on undirected example. We have selected Hamsterster [8] from the Koblenz Network Collection 30) With 126 nodes and 166 edges this friendship network has medium size. The results in Table 6 show even
scenario our full method outperforms the others. intuition to these results is following: Although KL divergence is an asymmetric function, in special cases can also become symmetric. E.g. in the case of two Gaussian distributions with equal standard deviations. the KL divergence is symmetric. This demonstrates the generality of representation. Note that did not set the additional equality constraint the standard deviation parameters in the learning phase for this experiment. However, this only works, if all data available and thus our approximation method does not generalize in similar quality as seen before from the training samples to the full data set in the undirected case.
As last additional experiment, we have verified the performance of our method on the down-stream task graph reconstruction. In particular, for every node u with outdegrec 9... retrieve the 6,, best candidate successors No. (u) from each embedding and compare them the dircct successors of node u. To assess the performance, precision is computed
Σn
No...
n Successors(u)
Precision our
E
Table 6: Results undirected network Hamsterster
Network
APP
HOPE
DeepWalk
Graph2Gauss
KL (10)
KL (100)
KI (full)
Hamsterster
-.03
.23
.36
-.26
.17
.19
.91
.45
.37
.37
-.76
.12
.12
.89
avg. MI
.29
.43
.10
.45
.63
.64
.89
std.
.006
.007
.006
.005
.005
.004
.005
16

---

Published as a conference paper at ICLR 2020
Table 7: Results of graph reconstruction for the political blogs network
Method
out-degree precision
in-degre precision
APP
0.1077
0.2624
HОPE
0.1010
0.1125
Deep Walk
0.2620
0.1669
Graph2Gauss
0.0258
0.0003
Elliptical
0.0383
0.0250
KL (full)
0.2861
0.2329
reletive ingrovement
1.5
0.0
200
400
800 number of modes
1000
Figure 4: Relative effect of correction L in comparison to VL. L. Starting from the same representa- tion, we optimized with gradient descent optimization with VL. and V. with learning rate * 10-6, calculated and averaged over 1000 random initial-
Then the relative improvement AvLL-AsuL ization, where Av is the value of our loss function after applying gradient descent with gradient VL. For this experimented we generated directed random networks with the Erdös-Rénye model for p .15 and (50, 100, 250, 500, 750, 1000].
AvuL.
This tells the ratio of actual neighboring links the embedding extract. The same is done for incoming links, using the in-degree of each node. This kind of task previously used in several papers that study graph embeddings e.g.
27
Table 7 shows the resulting in- and out precisions for the political blogs network. Although, on average, our method (KL) is performing well, it was not designed to encode only the local neighborhood but rather the whole spectrum of finite and infinite distances. Our representation is designed for preserving the global geodesic information of directed graphs in unsupervised setting. To excel at other supervised tasks, would have modify the loss function include additional terms more suitable that down-streaming task.
A.8 CORRECTION OF EUCLIDEAN GRADIENT
section 3, we have deduced that the steepest direction is given by - other words, in cach step of our optimization, we need to correct (2] the Euclidean gradient by the inverse of Fisher information matrix at the respective point. To be more specific, update the representation of node with a¹ ....o yt ...... .1" we apply
(
(o
è Dx
L
V D
L=
L,
C1
C2
where and the constants from Theorem 1 corrected gradient decreases with the network size.
As see in Figure 4 the relative improvement of the
17

---

Published as a conference paper at ICLR 2020
A.9 IMPORTANCE SAMPLING
As there exists no closed form of divergence for the generalized exponential power distributions, we propose an efficient importance sampling Monte Carlo estimation, which is applicable for even more distributions. In particular for this class of exponential power distribution, we perform
R KL(p) (2)) f
pa(xr dx (x))(()) qd (d(x)
pu (a)
p((()) log
log q (b)
However, one can also re-write the integral in order to use the easy sampling function thx (z):
J lol (x))) (x)x)
(x)
[x </x (x) (x(x)
log Px(x)
dx
log
dx = Ez-eo,
2x. (x)
q
(x)
For the proposal function, we will use the same class of distributions with parameter A. 2. When À 2 A. due the properties of exponential power distributions, the proposal distribution is concentrated around the mean from target distribution (2) so the variance of estimator is relatively low. Finally, the KL divergence approximated with m samples 21, ...Im from thx_ (x))
(x 14 (x) (x(x)
(x
Pa(x)) d (ax)
PA (xr,)
E R
log
log
m
qA (2c))
In the special case of x = the distributions are multivariate Gaussians and the KL divergence has an analytical form. For nodes u, V represented with (E.,, (4.)) respectively (Z.., pt.)) have
{ ur( E..) (m.. - mmm) Dy"" (Me ue.) - ke + det E..
det Eg
KLa
18


Reviews:
[{"review_id": "SyetJDjTYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an unsupervised method for learning node embeddings of directed graphs into statistical manifolds. Each node in the graph is mapped to a distribution in the space of k-variate power distributions, endowed with the KL divergence as asymetric similarity. The authors propose an optimization method based on a regularized KL divergence objective. They also propose an approximation of this objective based on finite neighborhoods, with a separate treatment of infinite distances based on a topological sorting. They also introduce a natural gradient correction to the gradient descent algorithm in this setting. They validate the fitness of their approach by showing that asymmetric distances in the graph translate into correlated asymetric distances between the node embeddings for various datasets.\n\nThe paper appears to bring a valuable method for directed graph embedding. However, a more thorough experimental study would help validating the improvements and hyperparameter setting of the method. Moreover, I suggest that the authors work on an improved version of the manuscript, as it contains many grammatical and spelling mistakes, some of which listed under.\n\n* Experimental questions *\n1. The hyperparameters and training time seems to have been set using the evaluation metric on the datasets. Could the authors provide a more principled validation approach to their experiments, e.g. using cross-validation?\n2. While the focus on preserving asymetric similarities is understandable, it would be interesting to know how the method performs for conventional evaluation tasks of network embedding, and to show that the gain in correlation can translate into gains for the end task in practice.\n\n* Spelling / grammar / layout *\n- Title: “On the geometry and learning low-dimensional embeddings…” does not make sense.\n- abstract: “is better preserving the global geodesic”\n- Fig 1: The sigma ellipse*s*\n- 2.1 Intuition.: “color codded”\n- Figure 2: “which was reflected the highest mutual information”\n- Figure 2 should visually identify the rows and the columns, rather than relying on the caption.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Sye7nK0ItH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed another graph embedding method. It focuses on directed graphs, and it embedded the graph nodes into exponential power distributions, which include the Gaussian distribution as a special case. The method is implemented by optimizing with respect to the free distributions on a statistical manifold so as to achieve the minimum distortion between the input/output distances.  The method is tested on several directed graph datasets and showed superior performance based on several metrics.\n\nOverall, the submission forms a complete and novel contribution in the area of graph embeddings. A key novelty is that the authors used the asymmetry of KL divergences to model the asymmetry of the distances in directed graphs, and they use the fact that KL is unbounded to model the infinite distances in undirected graphs. The proposed method has three main hyperparameters, \\lambda in eq.(1), \\beta in eq.(2), and the dimensionality of the target embedding. The author showed that \\lambda and \\beta are not sensitive and can be set to the default values, and 2-dimensional distributions already give much better results as compared to alternative embeddings. Moreover, the author proposed a scalable implementation based on sampling. Furthermore, the authored justified their choice of the target embedding space through some minor theoretical analysis given in section 3.\n\nThe writing quality and clarity are good (well above average).\n\nTo further improve this paper (e.g., in the final version), the authors are suggested to incorporate the following comments:\n\nIn the experimental evaluation, it should include some cases when the dimensionality of the target embedding has a large value (e.g., 50). This will make the evaluation more complete.\n\nThere are some typos and unusual expressions.  For example, page 3, what is \"a good proposal function\"?\n\nAfter eq.(1), mention \\lambda is a hyperparameter (that is not to be learned).\n\nTheorem 1 (2), mention the Fisher information matrix is wrt the coordinate system (\\sigma^1, \\cdots,\\sigma^k, \\mu^1, \\cdots, \\mu^k)\n\nIdeally, the experiments can include an undirected graph and show for example that the advantages of the proposed method become smaller in this case.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1lxARc3KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed an embedding method for directed graphs.\nEach node is represented by a normal distribution. \nAccordingly, for each pair of nodes, the authors used the KL divergence between their distributions to fit the observed distance. \nThe asymmetric property of the KL divergence matches well with the nature of directed graphs.\nA scalable algorithm is designed. \nThe property of the learned space is analyzed in detail, which verifies the rationality of using KL divergence. \n\nMy main concerns are about the experiments and the baselines.\n\n1. The baselines are not very representative. Except for APP, the remaining three methods are not motivated by directed graphs. To my knowledge, authors can further consider the following two methods as their baselines.\n\na) The classic method like the Okada-Imaizumi Radius Distance Model in “Okada, Akinori, and Tadashi Imaizumi. \"Nonmetric multidimensional scaling of asymmetric proximities.\" Behaviormetrika 14.21 (1987): 81-96.” This method represents each node in a directed graph as an embedding vector with a radius and proposed a Hausdorff-like distance.\n\nb) The recent work in [35]. This method also embeds nodes by elliptical distributions, but the distance is measured in the Wasserstein space. \n\nThis work will be stronger if the authors discuss the advantages of the proposed model compared with these two methods and add more comparison experiments.\n\n\n2. In practice, node embeddings are always used in down-stream learning tasks. Besides the classic statistical measurements, I would like to see a down-stream application of the proposed method, e.g., node classification/clustering. Adding such an experiment will make the advantage of the proposed method more convincing.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an embedding for nodes in a directed graph, which takes into account the asymmetry. The proposed method learns an embedding of a node as an exponential distribution (e.g. Gaussian), on a statistical manifold. The authors also provide an approximation for large graphs, and show that the method performs well in empirical comparisons.

The authors were very responsive in the discussion phase, providing new experiments in response to the reviews. This is a nice example where a good paper is improved by several extra suggestions by reviewers. I encourage the authors to provide all the software for reproducing their work in the final version.

Overall, this is a great paper which proposes a new graph embedding approach that is scalable and provides nice empirical results.
Decision: Accept (Poster)