We introduce a novel embedding of directed graphs derived from the singular value decomposition (SVD) of the normalized adjacency matrix. Specifically, we show that, after proper normalization of the singular vectors, the distances between vectors in the embedding space are proportional to the mean commute times between the corresponding nodes by a forward-backward random walk in the graph, which follows the edges alternately in forward and backward directions. In particular, two nodes having many common successors in the graph tend to be represented by close vectors in the embedding space. More formally, we prove that our representation of the graph is equivalent to the spectral embedding of some co-citation graph, where nodes are linked with respect to their common set of successors in the original graph. The interest of our approach is that it does not require to build this co-citation graph, which is typically much denser than the original graph. Experiments on real datasets show the efficiency of the approach.
# Summary of the paper
This paper proposes an embedding of directed graphs based on the SVD of a normalized adjacency matrix. This embedding is shown to be equivalent to the spectral embedding of a co-citation graph, which is more complex to calculate. Interestingly, the proposed approach does not require the *explicit* representation of this graph. Moreover, the paper also shows that distances of the embedded vectors are proportional to mean commute times of a forward--backward random walk in the original graph. A suite of experiments is run on graphs from KONECT.
# Review
This is a well-written paper, which I enjoyed reading. The extension of embeddings to the case of directed graphs is significant and warrants a detailed exploration.
The principal issues I see with this paper are as follows:
- The originality or scope of the contribution is not clear
- The experimental section is uncompelling
- Several relevant works appear to have been ignored
Overall, I like the way the paper treats the subject. In particular, I appreciate the fact that proofs are explained well; additionally, code is provided, which will increase reproducibility. This is uncommon and praiseworthy!
As for the originality of the paper, I find it hard to judge the scope of the contribution. The paper is extremely well written and employs a very pedagogical treatment of the subject, which I appreciate. Yet, it is hard for me to judge the utility and novelty of the proposed method in light of Section 8, where the paper shows that a spectral embedding of the undirected variant of the graph leads to essentially the *same* eigenvectors (up to renormalization and permutations). To prove that a new method is more effective, this point should be emphasized more:
1. In a sense, I would see the results from Section 8 as the equal to what 'Laplacian Eigenmaps' (LE) yields. This needs to be stressed, and analysed in an experimental section.
2. I understand that the order of the singular vectors is different, so embeddings that use only parts of them will be different. However, a convincing experiment should assess the differences. For example, in which regime for $d$ (number of used vectors) will the new method be surpassed by the old one? Is there such a regime? Ideally, this will be answered in the form of an asymptotic theorem; it could also be a larger experiment, though (to simulate the conditions in practice).
3. I understand that the new approach has a lower run-time, because the SVD is more efficient than eigendecomposition. However, what about a simple baseline algorithm that uses SVD for the *undirected* graph of the input data? This should be simple to accomplish, and would be a way to ascertain the benefit of using edge directions.
  To my understanding, LE should be this embedding, but from the table, I can see that its runtime is a lot worse than the novel method. What causes this? The fact that eigendecomposition is used instead of SVD?  If so, an additional SVD-based approach should be implemented.
This brings me to the experimental section. Here, the paper demonstrates the superiority of the new embedding based on evaluating modularity of a set of different clusterings of larger graphs, obtained using $k$-means. I have several concerns about this:
1. Modularity has problems with larger networks because only a small part of the network will be used in its configuration.
2. Since the embeddings cannot be easily compared due to missing ground truth information, other metrics should be employed. Here are a few, which are often used  by the community. See 'Is there a best quality metric for graph clusters?' by Almeida et al. for more details and a description of their shortcomings:
    - Silhouette coefficient
    - Coverage
    - Conductance
  Different ones should be evaluated here in order to show the behaviour of the new embedding. Do the embeddings differ if the modularities are similar?
3. How do the results change for different values of $d$? I find it hard to disentangle such a discussion from instabilities in $k$-means, but to my understanding of the method, tuning $d$ means that more or less information is used from the singular vectors.
   This could also be quantified in a proof (about asymptotic behaviour) but an experiment would be equally fine.
Concerning the bibliography, or the treatment of prior works, there are some issues:
- There appear to be some missing references of earlier works that used SVD or variants in order to cluster graphs or embed them:
  - Drineas et al.: 'Clustering Large Graphs via the Singular Value Decomposition'
  - Malliaros and Vazirgiannis: 'Clustering and Community Detection in Directed Networks: A Survey'
- Likewise, the use of pseudo-inverse Laplacians has a lot more papers attached to it (these are only a few that are relevant):
  - Ho and Dooren: 'On the pseudo-inverse of the Laplacian of a bipartite graph'
  - Gutman and Xia: 'Generalized inverse of the Laplacian matrix and some applications'
# Suggestions for improvement
- In some sense, this work can be seen as an extension of Laplacian eigenmaps to the directed case. The paper needs to be more clear about these extensions with respect to prior work. In Section 2, it is claimed that 'our main contribution is a proper normalization'. This strikes me as a rather small contribution in light of the experimental section, as outlined above.
- I am also hesitant to speak about a better interpretability of the mean commute time. I agree that it is nice to know that the distance permits such an interpretation in terms of random walks, but what is the impact of knowing the MCT? It is not only used in the embedding insofar as one obtains a vector representation.
- Section 5 is then the standard way of defining random walks based on a Laplacian matrix, and the correspondence to the pseudo-inverse of the Laplacian is shown. This is mathematically interesting, but appears to me to be in line with previous research.
- The section about co-citation graphs should make it more clear that 'successors' are to be taken in terms of the original graph and the directionality of edges. Since this is a standard definition in the domain of network analysis I would suggest citing a textbook here.
- In Section 6, the paper could give more details about random walk concepts such as 'stochastic', 'stationary distribution' etc., as it would make the paper more accessible (I am familiar with these concepts but since the writing of the paper is of high quality in the other sections, I am convinced this would improve its impact, and attract more readers).
Typos & grammar issues:
- 'in terms of random walk' --> 'in terms of random walks'
- 'equivalent to build' --> 'equivalent to building'
- 'with corresponding unitary matrix' --> 'with a corresponding unitary
  matrix'
- 'square Euclidean distance' --> 'squared Euclidean distance'
- 'equivalent to consider' --> 'equivalent to considering'
- 'irreductible' --> 'irreducible'
- 'and provide generally' --> 'and provides generally'
- 'in low dimension' --> 'in a lower dimension'
Furthermore, the bibliography should employ consistent capitalization and journal names for articles.