Title: The Forward-Backward Embedding of Directed Graphs

Abstract: 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.

1. Introduction:

Learning from data structured as a graph most often requires to embed the nodes of the graph in some Euclidian space (Yan et al. (2007) ; Grover and Leskovec (2016) ; Bronstein et al. (2017) ). The ability to learn then critically depends on this embedding, that must incorporate the "geometry" of the graph in some sense. A classical embedding of undirected graphs is based on the spectral decomposition of the Laplacian (Belkin and Niyogi (2003) ); after proper normalization, the distances between vectors in the embedding space are proportional to the mean commute times of the corresponding nodes by a random walk in the graph, making this embedding meaningful and easy to interpret (Qiu and Hancock (2007) ; Fouss et al. (2007) ). This result is not applicable to directed graphs.

In this paper, we show that, after proper normalization, the embedding derived from the singular value decomposition (SVD) of the normalized adjacency matrix of a directed graph, as considered in (Dhillon (2001) ; Rohe et al. (2012) ), can also be interpreted in terms of a random walk in the graph. This random walk is particular in the sense that edges are followed alternately in forward and backward directions. We call it the forward-backward random walk, and the corresponding embedding as the forward-backward embedding. As for undirected graphs, the distances between vectors in the embedding space are proportional to the mean commute times between the corresponding nodes by the random walk. We show in fact that the forward-backward embedding of a graph is equivalent to the spectral embedding of some co-citation 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.

The rest of the paper is organized as follows. We first present the related work. We then introduce the Laplacian matrix of a directed graph and the notion of co-citation graph. The embedding, and its interpretation in terms of the forward-backward random walk, are presented in Sections 5 and 6, respectively, under the assumption that the co-citation graph is connected; this assumption is relaxed in Section 7. The link between our embedding and the spectral embedding is explained in Section 8. The practically interesting case of bipartite graphs, that may be viewed as particular instances of directed graphs, is considered in Section 9. We conclude the paper by experiments on real datasets in Section 10.

We denote by 1 the vectors of ones of appropriate dimension. For any square matrix M , M + is the Moore-Penrose inverse of M and d(M ) is the diagonal matrix which has the same diagonal as M .

2. Related work:

While the spectral embedding of undirected graphs, and its interpretation in terms of random walks, is very well understood (see Lovász (1993) ; Snell and Doyle (2000) ; Qiu and Hancock (2007) ; Fouss et al. (2007) ; Luxburg (2007) ), the results do not easily extend to directed graphs. The main reason is that the Laplacian matrix is no longer symmetric and thus has complex eigenvalues in general. In (Li and Zhang (2010) ; Boley et al. (2011)) , it is shown that the mean commute times of the random walk can be expressed in terms of the pseudo-inverse of some proper Laplacian matrix, extending the results known for undirected graphs (Qiu and Hancock (2007) ). The considered Laplacian relies on the stationary distribution of the random walk, which is not explicit in general, and on the assumption that the graph is strongly connected. Moreover, no embedding of the graph (e.g., using the SVD of the Laplacian, as suggested in Li and Zhang (2010) ) is known to be directly related to the mean commute times of the random walk, as for undirected graphs.

The embedding of directed graphs proposed in (Dhillon (2001) ; Rohe et al. (2012) ) relies on the SVD of the normalized adjacency matrix. Our main contribution is a proper normalization of the singular vectors so that the distances in the embedding space can be interpreted in terms of mean commute times of the forward-backward random walk. In particular, our embedding is not an extension of the usual spectral embedding of undirected graphs, a point that is addressed specifically in Section 8. The idea of a random walk alternating between forward and backward steps is in the spirit of HITS (Kleinberg et al. (1999) ), an algorithm proposed to rank Web pages in terms of their relative importances as so-called hubs and authorities.

Various other embedding techniques rely on random walks in the graph (see Perrault-Joncas and Meila (2011); Cai et al. (2018) ; Goyal and Ferrara (2018) ; Qiu et al. (2018) and references therein). These include DeepWalk (Perozzi et al. (2014) ) and node2vec (Grover and Leskovec (2016) ), inspired by Natural Language Processing techniques, where the representation of the graph is learned from (simulated) random walks in the graph. Unlike the embedding proposed in the present paper, there is no direct interpretation of the distances in the embedding space in terms of random walk in the graph.

3. Laplacian matrix:

Let G be some directed graph and A its adjacency matrix. For convenience, we present the results for unweighted graphs (binary matrices A), but the results readily apply to weighted graphs (non-negative matrices A). We denote by n the number of nodes and by m = 1 T A1 the number of edges (the total weight of edges for a weighted graph). Unless otherwise specified, we assume that there are neither sources nor sinks in the graph, i.e., each node has a positive indegree and a positive outdegree. The extension to general graphs is considered in Section 7. We refer to the (normalized) Laplacian as:

EQUATION

)

where D out = diag(A1) and D in = diag(A T 1) are the diagonal matrices of outdegrees and indegrees, respectively. We refer to the matrix

D -1 2 out AD -1 2 in

as the normalized adjacency matrix. Observe that the matrix L T is the Laplacian of the reverse graph G -(same graph as G but with reverse edges), with adjacency matrix A T . In particular, the Laplacian L is symmetric if and only if A is symmetric, in which case we recover the usual normalized Laplacian of undirected graphs, namely

L = I -D -1 2 AD -1 4 Co-

citation graph:

The co-citation graph associated with G is the graph with adjacency matrix AA T . This is a weighted, undirected graph where the weight between nodes i and j is the number of common successors of i and j.

We refer to the normalized co-citation graph associated with G as the graph with adjacency matrix Ā = AD -1 in A T . This undirected graph has the same edges as the co-citation graph but the weight associated to any common successor of i and j is now normalized by its indegree. For instance, two articles of Wikipedia, say i, j, pointing to the same other article, say k, will be all the more similar (higher weight) in the corresponding normalized co-citation graph as article k is referenced by fewer other articles (lower in-degree) in the original graph. The node weights in the normalized co-citation graph (total weights of incident edges) are equal to the out-degrees in the graph G:

EQUATION

)

The normalized Laplacian of the normalized co-citation graph is:

L = I -D-1 2 Ā D-1 2

, where D = diag( Ā1) is the diagonal matrix of node weights in the normalized co-citation graph. Observe that D = D out in view of (2).

Proposition 1 We have:

I -L = (I -L)(I -L) T . Proof. This follows from I -L = D-1 2 Ā D-1 2 = D -1 2 out AD -1 in A T D -1 2 out = (I -L)(I -L) T .

5. Forward-backward embedding:

Consider a singular value decomposition (SVD) of the normalized adjacency matrix 1 ,

EQUATION

)

where Σ = diag(σ 1 , . . . , σ n ) with σ 1 ≥ . . . ≥ σ n ≥ 0 and U T U = V T V = I. We get

L = I -U ΣV T ,

and by Proposition 1, L = U (I -Σ 2 )U T .

(4) Thus the normalized Laplacian of the normalized co-citation graph has eigenvalues 1 -σ 2 1 ≤ . . . ≤ 1 -σ 2 n with corresponding unitary matrix of eigenvectors U . These eigenvalues are non-negative, the multiplicity of the eigenvalue 0 being the number of connected components of this graph (Luxburg (2007) ). We deduce that σ 1 = . . . = σ K = 1 > σ K+1 , where K is the number of connected components of the co-citation graph.

Assume that the co-citation graph is connected. The general case is considered in Section 7.

Then

σ 1 = 1 > σ 2 . Let Γ = (I -Σ 2 )

1 2 and define:

X = Γ + U T D -1 2 out .

(5)

The columns x 1 , . . . , x n of X define a representation of the graph in R n . Specifically, each node i is represented by the vector x i ∈ R n . Observe that the first coordinate of each vector x i is null so that at most n -1 coordinates are informative. The Euclidian distances between these vectors are entirely defined by the Gram matrix of X, which is related to the pseudo-inverse of the normalized Laplacian of the normalized co-citation graph,

L+ = U (I -Σ 2 ) + U T .

In view of (5),

X T X = D -1 2 out L+ D -1 2 out .

We show in the following section that the square distance between x i and x j is proportional to the mean commute time between nodes i and j of the forward-backward random walk in the graph G.

In practice, the graph is embedded in some vector space of dimension d, chosen much lower than n. In this case, only the d leading singular vectors are considered, i.e., those associated with the singular values σ 1 , . . . , σ d (or the d + 1 leading singular vectors is the first vector, which is not informative, is skipped).

6 Forward-backward random walk

Consider a random walk in the original graph G where edges are followed in forward and backward directions alternately. Specifically, from node i, a successor of i is chosen uniformly at random, say node j; then a predecessor of j (possibly i) is chosen uniformly at random, say k. Thus each jump of the random walk, here from i to k, involves two moves, here from i to j (forward) then from j to k (backward). The successive nodes X 0 , X 1 , . . . visited by this forward-backward random walk form a Markov chain on the set of nodes with transition matrix P = D -1 out AD -1 in A T , that is, the probability of a jump from i to j is:

Pij = n k=1 A ik A jk (D out 1) i (D in 1) k .

Equivalently, this Markov chain corresponds to a standard random walk in the normalized co-citation graph, in view of the equality P = D-1 Ā.

Let H be the matrix of mean hitting times, i.e., H ij is the mean hitting time of node j from node i. We have H ii = 0 and for all i = j,

H ij = 1 + n k=1

Pik H kj , so that the matrix (I -P )H -11 T is diagonal. The following result shows that H is directly related to the Gram matrix of X. This is a consequence of the fact that the forward-backward random walk in the graph G corresponds to a regular random walk in the normalized co-citation graph. A proof is provided for the sake of completeness.

Proposition 2:

We have:

EQUATION

)

Proof. Since the matrix P is stochastic, the matrix H defined by (6) satisfies:

(I -P )H = -m(I -P )X T X.

Since I -P = D-1 2 L D 1 2 , we get:

(I -P )H = -m D-1 2 L L+ D-1 2 , = -m D-1 2 (I - D 1 2 11 T m D 1 2 ) D-1 2 , = -m D-1 + 11 T ,

where the second equality comes from the fact that D 1 2 1/ √ m is the unitary eigenvector of the normalized Laplacian L for the eigenvalue 0. In particular, the matrix (I -P )H -11 T is diagonal. Moreover, the matrix H is zero-diagonal. The proof follows from the fact that the matrix of mean hitting times is uniquely defined by these two properties.

Let C = H + H T be the matrix of mean commute times, i.e., C ij is the mean commute time between nodes i and j. It follows directly from Proposition 2 that H ij = m(x j -x i ) T x j and H ji = m(x i -x j ) T x i , so that C ij = m||x i -x j || 2 , i.e., the mean commute time between nodes i and j is proportional to the square Euclidian distances between x i and x j in the embedding space. Now let π be the stationary distribution of the random walk. The mean hitting time of node i in steady state is given by:

h i = n i=1 π j H ji .

Since π = D1/m, we have Xπ = 0 and, in view of Proposition 2, h i = m||x i || 2 : the mean hitting time of node i is proportional to the square norm x i in the embedding space.

Finally, we have mx:

T i x j = h j -H ij = h i -H ji so that: cos(x i , x j ) = h i + h j -C ij 2 h i h j .

The cosine similarity between x i and x j can thus be interpreted in terms of mean commute times between nodes i and j relative to the mean hitting times h i , h j . In particular, the vectors x i and x j are close in terms of cosine similarity if the mean commute time C ij is small compared to h i + h j . This is equivalent to consider the embedding where each vector x i is normalized by its Euclidian norm ||x i ||.

7. General graphs:

In this section, we relax the assumptions that the out-degrees and in-degrees are positive and that the co-citation graph is connected. Let C (1) , . . . , C (K) be the connected components of the co-citation graph. These sets form a partition of the set of nodes of the original graph G. Observe that each sink of the graph G is isolated in the co-citation graph so that the forward-backward random walk starting from such a node is not defined. In the following, we consider any connected component C (k) not reduced to a single node. The forward-backward random walk starting from any node in C (k) is well defined and corresponds to an irreductible Markov chain on C (k) . Let A (k) be the restriction of A to its rows indexed by C (k) , that is, k) and any j and equal to A ij . This is a matrix of dimension n (k) × n where n (k) is the number of nodes in the connected component C (k) . Consider a singular value decomposition of the matrix :

A (k) ij is defined for each i ∈ C (

D (k) out -1 2 A (k) (D + in ) 1 2 = U (k) Σ (k) V (k) T ,

where

D (k) out = diag(A (k) 1). Observe that the diagonal entries of D (k) out are positive. Let Γ (k) = (I -Σ (k) 2 )

1 2 and define:

X (k) = Γ (k) + U (k) T D (k) out -1 2 .

This is the forward-backward embedding of the nodes of

C (k) in R n (k)

. By the same argument as before, the square Euclidian distances between vectors in the embedding space are proportional to the mean commute times of the forward-backward random walk in the graph G, starting from any node in C (k) .

8. Link with spectral embedding:

Any undirected graph G can be viewed as a directed graph with edges in both directions.

The square Euclidian distances between vectors in the embedding space then correspond to mean commute times of a two-hop random walk in the graph G. In particular, the proposed embedding differs from the usual spectral embedding whose geometry is related to a regular one-hop random walk in the graph G (Qiu and Hancock (2007) ).

Specifically, the normalized Laplacian L = I -D -1 2 AD -1 2 , with D = D out = D in , is symmetric and thus admits a spectral decomposition of the form: L = W ΛW T , (7) where Λ = diag(λ 1 , . . . , λ n ), with λ 1 ≤ . . . ≤ λ n and W T W = I. Since I -L has the same eigenvalues as P = D -1 A, the transition matrix of the regular random walk in graph G, we have 0 ≤ λ 1 ≤ . . . ≤ λ n ≤ 2, with λ n = 2 if and only if the graph G is bipartite. Define:

Z = (Λ 1 2 ) + W T D -1 2 .

(8) The columns z 1 , . . . , z n of Z provide a spectral embedding of the graph G, such that the square distance between z i and z j is proportional to the mean commute time between nodes i and j of a regular random walk in the graph G.

Now it follows from Proposition 1 that:

I -L = (I -L) 2 = W (I -Λ) 2 W T .

Let φ be a permutation of {1, . . . , n} such that:

(1

-λ φ(1) ) 2 ≥ . . . ≥ (1 -λ φ(n) ) 2 . Since I -L = U Σ 2 U T , we get σ 2 1 = (1 -λ φ(1) ) 2 , . . . , σ 2 n = (1 -λ φ(n) )

2 , and U = W φ (permutation φ of the columns of W ) whenever all singular values of I -L are distinct (otherwise, the equality holds up to a rotation of the singular vectors associated with the same singular values). We deduce that the spectral embedding Z is the same as the forward-backward embedding X, up to a permutation, possible rotations, and a renormalization (k-th column of U normalized by

√ λ k instead of 1 -(1 -λ k ) 2 = λ k (2 -λ k ))

. Observe that the difference may be significant in the presence of eigenvalues close to 2, where the graph tends to have a bipartite structure. Moreover, the permutation φ implies that the order of the singular vectors of I -L (used in the forward-backward embedding X) is not that of the eigenvectors of L (used in the spectral embedding Z), so that the corresponding embeddings induced by the d leading singular vectors for some d << n may be very different.

9. Bipartite graphs:

A bipartite graph G with two sets of nodes N 1 and N 2 can be viewed as a directed graph with an edge from i 1 ∈ N 1 and i 2 ∈ N 2 for any edge between i 1 and i 2 in G. The forward-backward embedding of this directed graph provides a representation of the nodes N 1 in R n1 , where n 1 = |N 1 | is the numbers of nodes in N 1 (the embedding of the nodes N 2 is obtained by reversing the edges).

It is then more convenient to work with the biadjacency matrix B of G, of dimension

n 1 × n 2 with n 1 = |N 1 | and n 2 = |N 2 |: B i1,i2 = 1 if

and only if there is an edge between node i 1 ∈ N 1 and i 2 ∈ N 2 . Let D 1 = diag(B1) and D 2 = diag(B T 1) be the diagonal matrices of the degrees of each part. We assume that the diagonal entries of D 1 and D 2 are positive (equivalently, there is no node of null degree in G). Consider a singular value decomposition of the form:

D -1 2 1 BD -1 2 2 = U 1 ΣU T 2 , where Σ is a n × n non-negative diagonal matrix, with n = min(n 1 , n 2 ). Let Γ = (I -Σ 2 ) 1 2 .

The forward-backward embeddings of N 1 and N 2 are then given by:

X 1 = Γ + U T 1 D -1 2 1 and X 2 = Γ + U T 2 D -1 2 2 .

10 Experiments

In this section, we assess the quality of the forward-backward embedding on a standard clustering task. Specifically, we apply k-means clustering to various embeddings of graphs of the Koblenz Network Collection 1 , a rich collection of more than 250 graphs (Kunegis (2013) ).

Due to the absence of ground-truth clusters, we measure the quality of the clustering through its modularity in the normalized co-citation graph:

Q = 1 m n i,j=1 Āij - di dj m δ ci,cj ,

where d = Ā1 is the vector of degrees in the normalized co-citation graph, c i , c j are the clusters of nodes i, j and δ is the Kronecker delta (Newman and Girvan (2004) ). This quantity lies in the interval [-1, 1], the value Q = 0 corresponding to the trivial clustering with a single cluster; the higher the modularity Q, the better the clustering. The modularity can be written with respect to the adjacency matrix of the original graph as:

Q = 1 m n i,j=1 1 T i A D -1 in - 11 T m A T 1 j δ ci,cj ,

where 1 i , 1 j are the unit vectors on components i, j. In particular, the computation of the modularity does not require that of Ā, the adjacency matrix of the normalized co-citation graph; it can be directly evaluated in O(m) operations by matrix-vector multiplications from the adjacency matrix A.

The considered embeddings are the following:

• Identity embedding (Id): a baseline where the k-means algorithm is directly applied to the adjacency matrix A (or to the biadjacency matrix B for bipartite graphs);

• Dhillon co-clustering (Dh), for bipartite graphs only, based on the SVD of the normalized adjacency matrix, without normalization (Dhillon (2001) );

• Laplacian Eigenmaps (LE): the spectral decomposition of the graph, considered as undirected, as described in Belkin and Niyogi (2003) ;

• Forward-Backward embedding (FB): the embedding (5), normalized to get unitary vectors, as described at the end of Section 6.

The Python code used for the experiments is available as a Jupyter notebook2 , making the experiments fully reproducible.

Tables 1 and 2 show the modularity scores and running times of each embedding for 30 directed graphs and 20 bipartite graphs of the Konect collection 1 , each graph being identified through its code in the collection. We have selected these representative sets of graphs because of space constraints but the Jupyter notebook available online 2 can be run on all graphs of the Konect collection. The graphs are considered as simple and unweighted. We give in Tables 1 and 2 the size of each graph, which may be lower than that announced in the Konect collection if the original graph is a multi-graph, as we count each edge only once. The running times are for a PC equipped with a AMD Ryzen Threadripper 1950X processor and a RAM of 32GB. Running times exceeding 1000s trigger a time-out 2 . The dimension of the embedding is d = 10 for all embeddings except Id where we take the full matrix. The clustering algorithm is k-means++ with 10 clusters Arthur and Vassilvitskii (2007) .

The results show that FB is extremely fast and provide generally a much better embedding than Dh and LE with respect to the considered clustering task. They confirm experimentally the relevance of the theoretical results shown in this paper, namely the interpretation of distances in the embedding space in terms of a forward-backward random walk in the graph, or a regular random walk in the normalized co-citation graph. Although these theoretical results apply in principle to the full embedding only, i.e., d = n, the experimental results tend to show that the FB embedding also captures the "geometry" of the normalized co-citation graph in low dimension, here d = 10. Again, our approach does not require the construction of this graph, whose structure is directly captured by the SVD. 

:

with D = D out = D in .

A naive approach to the SVD of a matrix M is based on the spectral decomposition of the matrix M M T ; in our case, this would be equivalent to build the co-citation graph, which is typically much denser than the original graph. This is why we use a proper implementation of the SVD that works directly on the matrix M , seeHalko et al. (2011).

http://konect.uni-koblenz.de

https://github.com/tbonald/directed 2 We have also tested the Node2Vec embeddingGrover and Leskovec (2016), available on the Jupyter notebook, but this leads to a timeout for almost all graphs of the Konect collection on the PC used in the experiments.

Figures and Tables:

Modularity scores of Id, LE and FB on 30 directed graphs (TO = Time Out).

Table content: <table><tr><td colspan="3">Dataset Size (#edges)</td><td>Id</td><td/><td>LE</td><td>FB</td></tr><tr><td>MS</td><td>6 207</td><td/><td colspan="2">0.26 (&lt; 1s)</td><td colspan="2">0.01 (3s)</td><td>0.37 (&lt; 1s)</td></tr><tr><td>Mg</td><td>19 025</td><td/><td colspan="4">0.17 (&lt; 1s) 0.00 (&lt; 1s) 0.49 (&lt; 1s)</td></tr><tr><td>AD</td><td>51 127</td><td/><td colspan="2">0.16 (&lt; 1s)</td><td colspan="2">0.04 (5s)</td><td>0.08 (&lt; 1s)</td></tr><tr><td>CH</td><td>65 053</td><td/><td colspan="2">0.07 (&lt; 1s)</td><td colspan="2">0.00 (6s)</td><td>0.25 (&lt; 1s)</td></tr><tr><td>DG</td><td>87 627</td><td/><td colspan="2">0.13 (&lt; 1s)</td><td colspan="2">0.01 (4s)</td><td>0.26 (1s)</td></tr><tr><td>CC</td><td>91 500</td><td/><td colspan="2">0.09 (&lt; 1s)</td><td colspan="2">0.45 (4s)</td><td>0.60 (2s)</td></tr><tr><td>SD</td><td>140 778</td><td/><td colspan="2">0.09 (&lt; 1s)</td><td colspan="2">0.00 (15s)</td><td>0.27 (2s)</td></tr><tr><td>GN</td><td>147 892</td><td/><td colspan="2">0.00 (&lt; 1s)</td><td colspan="2">0.00 (15s)</td><td>0.46 (2s)</td></tr><tr><td>DJ</td><td>150 985</td><td/><td colspan="2">0.30 (&lt; 1s)</td><td colspan="2">0.37 (1s)</td><td>0.11</td></tr><tr><td>LX</td><td>213 954</td><td/><td colspan="2">0.20 (&lt; 1s)</td><td colspan="2">0.00 (9s)</td><td>0.17</td></tr><tr><td>EA</td><td>312 342</td><td/><td colspan="2">0.00 (&lt; 1s)</td><td colspan="2">0.18 (3s)</td><td>0.19 (2s)</td></tr><tr><td>PHc</td><td>421 578</td><td/><td colspan="2">0.07 (&lt; 1s)</td><td colspan="2">0.00 (33s)</td><td>0.60 (2s)</td></tr><tr><td>ES</td><td>508 837</td><td/><td colspan="2">0.13 (1s)</td><td colspan="2">0.00 (14s)</td><td>0.14 (3s)</td></tr><tr><td>Ow</td><td>876 933</td><td/><td colspan="4">0.01 (&lt; 1s) 0.01 (202s)</td><td>0.51 (2s)</td></tr><tr><td>EN</td><td colspan="2">1 148 072</td><td colspan="4">0.11 (&lt; 1s) 0.00 (107s)</td><td>0.44 (2s)</td></tr><tr><td>ND</td><td colspan="2">1 497 134</td><td colspan="2">0.38 (1s)</td><td>TO</td><td>0.79 (5s)</td></tr><tr><td>DF</td><td colspan="2">1 731 653</td><td colspan="2">0.19 (1s)</td><td colspan="2">0.01 (161s)</td><td>0.14 (5s)</td></tr><tr><td>CS</td><td colspan="2">1 751 463</td><td colspan="2">0.21 (2s)</td><td colspan="2">0.01 (295s)</td><td>0.55 (7s)</td></tr><tr><td>SF</td><td colspan="2">2 312 497</td><td colspan="2">0.45 (3s)</td><td>TO</td><td>0.79 (6s)</td></tr><tr><td>BAr</td><td colspan="2">3 284 387</td><td colspan="2">0.52 (3s)</td><td>TO</td><td>0.68 (7s)</td></tr><tr><td>Am</td><td colspan="2">3 387 388</td><td colspan="2">0.00 (3s)</td><td colspan="2">0.65 (417s)</td><td>0.59 (8s)</td></tr><tr><td>GO</td><td colspan="2">5 105 039</td><td colspan="2">0.02 (4s)</td><td>TO</td><td>0.72 (12s)</td></tr><tr><td>BS</td><td colspan="2">7 600 595</td><td colspan="2">0.53 (4s)</td><td>TO</td><td>0.79 (10s)</td></tr><tr><td>DB</td><td colspan="2">13 820 853</td><td colspan="2">0.51 (15s)</td><td>TO</td><td>0.45 (44s)</td></tr><tr><td>PC</td><td colspan="2">16 518 947</td><td colspan="2">0.22 (15s)</td><td>TO</td><td>0.45 (64s)</td></tr><tr><td>LI</td><td colspan="2">17 359 346</td><td colspan="2">0.12 (18s)</td><td colspan="2">0.24 (26s)</td><td>0.37 (19s)</td></tr><tr><td>HUr</td><td colspan="2">18 854 882</td><td colspan="2">0.25 (11s)</td><td>TO</td><td>0.31 (42s)</td></tr><tr><td>PL</td><td colspan="2">30 622 564</td><td colspan="2">0.00 (15s)</td><td colspan="2">0.39 (229s)</td><td>0.51 (56s)</td></tr><tr><td>FL</td><td colspan="2">33 140 017</td><td colspan="2">0.18 (14s)</td><td>TO</td><td>0.45 (47s)</td></tr><tr><td>LJ</td><td colspan="2">68 475 391</td><td colspan="2">0.00 (43s)</td><td>TO</td><td>0.25 (119s)</td></tr><tr><td colspan="2">Dataset Size (#edges)</td><td/><td>Id</td><td/><td>Dh</td><td>LE</td><td>FB</td></tr><tr><td>AC</td><td>58 595</td><td colspan="2">0.01 (&lt; 1s)</td><td colspan="2">0.46 (2s)</td><td>0.07 (31s)</td><td>0.72 (1s)</td></tr><tr><td>YG</td><td>293 360</td><td colspan="2">0.15 (&lt; 1s)</td><td colspan="2">0.03 (5s)</td><td>0.03 (98s)</td><td>0.51 (2s)</td></tr><tr><td>GH</td><td>440 237</td><td colspan="2">0.21 (1s)</td><td colspan="3">0.07 (13s) 0.07 (118s) 0.33 (2s)</td></tr><tr><td>BX</td><td>1 149 739</td><td colspan="2">0.19 (3s)</td><td colspan="3">0.02 (28s) 0.02 (893s) 0.21 (5s)</td></tr><tr><td>ben</td><td>1 164 576</td><td colspan="2">0.02 (1s)</td><td/><td>VE</td><td>0.01 (319s) 0.55 (2s)</td></tr><tr><td>SO</td><td>1 301 942</td><td colspan="2">0.02 (&lt; 1s)</td><td/><td>VE</td><td>0.02 (502s) 0.32 (6s)</td></tr><tr><td>TM</td><td>1 366 466</td><td colspan="2">0.04 (&lt; 1s)</td><td/><td>VE</td><td>TO</td><td>0.61 (7s)</td></tr><tr><td>AM</td><td>1 470 404</td><td colspan="2">0.00 (3s)</td><td colspan="3">0.01 (18s) 0.01 (184s) 0.66 (5s)</td></tr><tr><td>Vut</td><td>2 298 816</td><td colspan="2">0.12 (1s)</td><td colspan="2">0.00 (1s)</td><td>0.00 (15s)</td><td>0.27 (1s)</td></tr><tr><td>Cut</td><td>2 411 819</td><td colspan="2">0.19 (1s)</td><td colspan="2">0.00 (3s)</td><td>0.00 (96s)</td><td>0.20 (2s)</td></tr><tr><td>But</td><td>2 555 080</td><td colspan="2">0.45 (1s)</td><td colspan="2">0.00 (2s)</td><td>0.46 (34s)</td><td>0.49 (1s)</td></tr><tr><td>DV</td><td>3 018 197</td><td colspan="2">0.02 (2s)</td><td colspan="2">0.10 (2s)</td><td>0.02 (4s)</td><td>0.08 (3s)</td></tr><tr><td>DBT</td><td>3 232 134</td><td colspan="2">0.04 (6s)</td><td colspan="2">0.01 (9s)</td><td>0.01 (23s)</td><td>0.01 (3s)</td></tr><tr><td>Wut</td><td>4 664 605</td><td colspan="2">0.04 (3s)</td><td colspan="3">0.00 (33s) 0.00 (490s) 0.45 (7s)</td></tr><tr><td>AR</td><td>5 838 041</td><td colspan="2">0.00 (4s)</td><td colspan="2">0.07 (516s)</td><td>TO</td><td>0.39 (25s)</td></tr><tr><td>FG</td><td>8 545 307</td><td colspan="2">0.10 (3s)</td><td colspan="2">0.00 (28s)</td><td>TO</td><td>0.20 (6s)</td></tr><tr><td>M3</td><td>10 000 054</td><td colspan="2">0.06 (17s)</td><td colspan="2">0.09 (5s)</td><td>0.11 (9s)</td><td>0.09 (4s)</td></tr><tr><td>DI</td><td>14 414 659</td><td colspan="2">0.05 (2s)</td><td colspan="2">0.01 (177s)</td><td>TO</td><td>0.32 (16s)</td></tr><tr><td>Ls</td><td>19 150 868</td><td colspan="4">0.12 (170s) 0.05 (16s)</td><td>0.03 (37s)</td><td>0.04 (8s)</td></tr><tr><td>RE</td><td>60 569 726</td><td colspan="2">0.08 (19s)</td><td colspan="3">0.00 (25s) 0.08 (141s) 0.09 (22s)</td></tr></table>

Modularity scores of Id, DE, LE, FB on 20 bipartite graphs (VE = Value Error, TO = Time Out).

Table content: <table/>

Peer review (iclr2019):
 # 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 (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 -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 ? I find it hard to disentangle such a discussion from instabilities in -means, but to my understanding of the method, tuning 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.