Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

The 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.

* Experimental questions *
1. 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?
2. 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.

* Spelling / grammar / layout *
- Title: “On the geometry and learning low-dimensional embeddings…” does not make sense.
- abstract: “is better preserving the global geodesic”
- Fig 1: The sigma ellipse*s*
- 2.1 Intuition.: “color codded”
- Figure 2: “which was reflected the highest mutual information”
- Figure 2 should visually identify the rows and the columns, rather than relying on the caption.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors proposed an embedding method for directed graphs.
Each node is represented by a normal distribution. 
Accordingly, for each pair of nodes, the authors used the KL divergence between their distributions to fit the observed distance. 
The asymmetric property of the KL divergence matches well with the nature of directed graphs.
A scalable algorithm is designed. 
The property of the learned space is analyzed in detail, which verifies the rationality of using KL divergence. 

My main concerns are about the experiments and the baselines.

1. 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.

a) 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.

b) The recent work in [35]. This method also embeds nodes by elliptical distributions, but the distance is measured in the Wasserstein space. 

This work will be stronger if the authors discuss the advantages of the proposed model compared with these two methods and add more comparison experiments.


2. 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.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 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.

Overall, 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.

The writing quality and clarity are good (well above average).

To further improve this paper (e.g., in the final version), the authors are suggested to incorporate the following comments:

In 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.

There are some typos and unusual expressions.  For example, page 3, what is "a good proposal function"?

After eq.(1), mention \lambda is a hyperparameter (that is not to be learned).

Theorem 1 (2), mention the Fisher information matrix is wrt the coordinate system (\sigma^1, \cdots,\sigma^k, \mu^1, \cdots, \mu^k)

Ideally, the experiments can include an undirected graph and show for example that the advantages of the proposed method become smaller in this case.
review_title: Official Blind Review #3

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)