The Forward-Backward Embedding of Directed Graphs
Year: 2018

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.

heading: 1 Introduction
text: 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 .

heading: 2 Related work
text: 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.

heading: 3 Laplacian matrix
text: 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 = 1TA1 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:
L = I −D− 1 2 outAD − 12 in , (1)
where Dout = diag(A1) and Din = diag(AT 1) are the diagonal matrices of outdegrees and indegrees, respectively. We refer to the matrix
D − 12 outAD − 12 in
as the normalized adjacency matrix. Observe that the matrix LT is the Laplacian of the reverse graph G− (same graph as G but with reverse edges), with adjacency matrix AT . 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− 12AD− 12 with D = Dout = Din.

heading: 4 Co-citation graph
text: The co-citation graph associated with G is the graph with adjacency matrix AAT . 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 Ā = AD−1in AT . 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:
Ā1 = AD−1in AT 1 = A1. (2)
The normalized Laplacian of the normalized co-citation graph is:
L̄ = I − D̄− 12 ĀD̄− 12 , where D̄ = diag(Ā1) is the diagonal matrix of node weights in the normalized co-citation graph. Observe that D̄ = Dout in view of (2).
Proposition 1 We have I − L̄ = (I − L)(I − L)T .
Proof. This follows from I − L̄ = D̄− 12 ĀD̄− 12 = D− 1 2
outAD −1 in A TD − 12 out = (I − L)(I − L)T .

heading: 5 Forward-backward embedding
text: Consider a singular value decomposition (SVD) of the normalized adjacency matrix1,
D − 12 outAD − 12 in = UΣV T , (3)
where Σ = diag(σ1, . . . , σn) with σ1 ≥ . . . ≥ σn ≥ 0 and UTU = V TV = I. We get
L = I − UΣV T , and by Proposition 1, L̄ = U(I − Σ2)UT . (4) Thus the normalized Laplacian of the normalized co-citation graph has eigenvalues 1− σ21 ≤ . . . ≤ 1 − σ2n 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 = Γ+UTD− 1 2
out . (5) The columns x1, . . . , xn of X define a representation of the graph in Rn. Specifically, each node i is represented by the vector xi ∈ Rn. Observe that the first coordinate of each vector xi 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)+UT . 1A naive approach to the SVD of a matrix M is based on the spectral decomposition of the matrix MMT ; 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 , see Halko et al. (2011).
In view of (5), XTX = D− 1 2
out L̄ +D − 12 out .
We show in the following section that the square distance between xi and xj 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).

heading: 6 Forward-backward random walk
text: 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 X0, X1, . . . visited by this forward-backward random walk form a Markov chain on the set of nodes with transition matrix P̄ = D−1outAD−1in AT , that is, the probability of a jump from i to j is:
P̄ij = n∑ k=1 AikAjk (Dout1)i(Din1)k .
Equivalently, this Markov chain corresponds to a standard random walk in the normalized co-citation graph, in view of the equality P̄ = D̄−1Ā. Let H be the matrix of mean hitting times, i.e., Hij is the mean hitting time of node j from node i. We have Hii = 0 and for all i 6= j,
Hij = 1 + n∑ k=1 P̄ikHkj ,
so that the matrix (I − P̄ )H − 11T 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:
H = m(11T d(XTX)−XTX). (6)
Proof. Since the matrix P̄ is stochastic, the matrix H defined by (6) satisfies:
(I − P̄ )H = −m(I − P̄ )XTX.
Since I − P̄ = D̄− 12 L̄D̄ 12 , we get:
(I − P̄ )H = −mD̄− 12 L̄L̄+D̄− 12 ,
= −mD̄− 12 (I − D̄ 12 11 T
m D̄
1 2 )D̄− 12 ,
= −mD̄−1 + 11T ,
where the second equality comes from the fact that D̄ 12 1/ √ m is the unitary eigenvector of
the normalized Laplacian L̄ for the eigenvalue 0. In particular, the matrix (I − P̄ )H − 11T 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 +HT be the matrix of mean commute times, i.e., Cij is the mean commute time between nodes i and j. It follows directly from Proposition 2 that Hij = m(xj − xi)Txj and Hji = m(xi − xj)Txi, so that Cij = m||xi − xj ||2, i.e., the mean commute time between nodes i and j is proportional to the square Euclidian distances between xi and xj 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:
hi = n∑ i=1 πjHji.
Since π = D̄1/m, we have Xπ = 0 and, in view of Proposition 2, hi = m||xi||2: the mean hitting time of node i is proportional to the square norm xi in the embedding space. Finally, we have mxTi xj = hj −Hij = hi −Hji so that:
cos(xi, xj) = hi + hj − Cij 2 √ hihj .
The cosine similarity between xi and xj can thus be interpreted in terms of mean commute times between nodes i and j relative to the mean hitting times hi, hj . In particular, the vectors xi and xj are close in terms of cosine similarity if the mean commute time Cij is small compared to hi + hj . This is equivalent to consider the embedding where each vector xi is normalized by its Euclidian norm ||xi||.

heading: 7 General graphs
text: 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, A
(k) ij is defined for each i ∈ C(k) and any j and equal to Aij . 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 :
D (k) out − 12 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) 12 and define:
X(k) = Γ(k) + U (k) T D (k) out − 12 .
This is the forward-backward embedding of the nodes of C(k) in Rn(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).

heading: 8 Link with spectral embedding
text: 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− 12AD− 12 , with D = Dout = Din, is symmetric and thus admits a spectral decomposition of the form:
L = WΛWT , (7) where Λ = diag(λ1, . . . , λn), with λ1 ≤ . . . ≤ λn and WTW = I. Since I − L has the same eigenvalues as P = D−1A, 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 = (Λ 12 )+WTD− 12 . (8) The columns z1, . . . , zn of Z provide a spectral embedding of the graph G, such that the square distance between zi and zj 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 − Λ)2WT . Let φ be a permutation of {1, . . . , n} such that:
(1− λφ(1))2 ≥ . . . ≥ (1− λφ(n))2. Since I − L̄ = UΣ2UT , we get σ21 = (1− λφ(1))2, . . . , σ2n = (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.

heading: 9 Bipartite graphs
text: A bipartite graph G with two sets of nodes N1 and N2 can be viewed as a directed graph with an edge from i1 ∈ N1 and i2 ∈ N2 for any edge between i1 and i2 in G. The forward-backward embedding of this directed graph provides a representation of the nodes N1 in Rn1 , where n1 = |N1| is the numbers of nodes in N1 (the embedding of the nodes N2 is obtained by reversing the edges). It is then more convenient to work with the biadjacency matrix B of G, of dimension n1×n2 with n1 = |N1| and n2 = |N2|: Bi1,i2 = 1 if and only if there is an edge between node i1 ∈ N1 and i2 ∈ N2. Let D1 = diag(B1) and D2 = diag(BT 1) be the diagonal matrices of the degrees of each part. We assume that the diagonal entries of D1 and D2 are positive (equivalently, there is no node of null degree in G). Consider a singular value decomposition of the form:
D − 12 1 BD − 12 2 = U1ΣUT2 ,
where Σ is a n× n non-negative diagonal matrix, with n = min(n1, n2). Let Γ = (I − Σ2) 1 2 . The forward-backward embeddings of N1 and N2 are then given by: X1 = Γ+UT1 D − 12 1 and X2 = Γ+UT2 D − 12 2 .

heading: 10 Experiments
text: 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 Collection1, a rich collection of more than 250 graphs (Kunegis (2013)).
1http://konect.uni-koblenz.de
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 ( Āij − d̄id̄j m ) δci,cj ,
where d̄ = Ā1 is the vector of degrees in the normalized co-citation graph, ci, cj 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 1Ti A ( D−1in − 11T m ) AT 1jδci,cj ,
where 1i, 1j are the unit vectors on components i, j. In particular, the computation of the modularity does not require that of Ā, 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 collection1, 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 online2 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-out2. 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.
2https://github.com/tbonald/directed 2We have also tested the Node2Vec embedding Grover 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.

Review summaries:
The paper studies embeddings of directed graphs based on SVD. It proposes an interpretation of the embedding obtained from the normalized adjacency matrix in terms of the forward-backward random walk on the graph. In such random walk odd steps are taken using the edges of the graph while even steps are taken using reverse edges. Such an interpretation seems to be a trivial extension of the work for undirected graphs.