Effective Resistance Preserving Directed Graph Symmetrization
Katherine Fitch






Effective resistance preserving directed graph symmetrization This work was supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). 
    Katherine Fitch Katherine Fitch is with the Chair of Operations Research, Technical University of Munich, Munich, Germany. katie.fitch@tum.de 
    December 30, 2023
=============================================================================================================================================================================================================




This work presents a new method for symmetrization of directed graphs that constructs an undirected graph with equivalent pairwise effective resistances as a given directed graph. Consequently a graph metric, square root of effective resistance, is preserved between the directed graph and its symmetrized version. It is shown that the preservation of this metric allows for interpretation of algebraic and spectral properties of the symmetrized graph in the context of the directed graph, due to the relationship between effective resistance and the Laplacian spectrum. Additionally, Lyapunov theory is used to demonstrate that the Laplacian matrix of a directed graph can be decomposed into the product of a projection matrix, a skew symmetric matrix, and the Laplacian matrix of the symmetrized graph. The application of effective resistance preserving graph symmetrization is discussed in the context of spectral graph partitioning and Kron reduction of directed graphs. 


graph symmetrization, directed graph analysis, effective resistance, spectral graph theory, Lyapunov equation, graph partitioning, Kron reduction


05C12, 05C50, 05C70, 93D05



§ INTRODUCTION
  
In general, a large number of graph-theoretic problems and applications such as clustering <cit.>, signal processing over graphs <cit.>, and edge sparsification <cit.> are well-studied and understood in the context of undirected graphs, but less so in the context of directed graphs. The solutions to these problems rely on algebraic and spectral graph theory that has been derived for undirected graphs but cannot be immediately applied to directed graphs due to the loss of symmetry in the Laplacian matrix.  A natural solution approach is to symmetrize the Laplacian and solve the problem on the associated symmetrized graph <cit.>.

In <cit.>, the authors provide a comprehensive survey of common symmetrization methods used for clustering directed graphs including bibliometric symmetrization <cit.>, degree-discounted symmetrization <cit.>, or simply ignoring edge direction. These methods have the drawback that there is not always a formal guarantee that the symmetrized Laplacian captures appropriate or desired characteristics, such as distance between nodes, of the original directed Laplacian. Random walk-based symmetrization has been used to define the Cheeger inequality for directed graphs <cit.>,   spectral clustering of directed graphs <cit.>, and other applications. However, the definitions in <cit.> hold only when the graph is strongly connected, or in other words, for every pair of nodes i, j there exists a directed path from i to j.

One property of undirected graphs that has recently been extended to directed graphs is the notion of effective resistance <cit.>. In undirected graphs, effective resistance is commonly known as resistance distiance <cit.> and arises from considering a graph as a network of resistors where each edge is replaced by a resistor with resistance equal to the inverse of the edge weight. The resistance distance between two nodes i,j is simply the net resistance resulting from connecting a voltage source between i, j. As demonstrated in <cit.>, resistance distance can be equivalently computed from the pseudoinverse of the undirected graph Laplacian. Resistance distance in undirected graphs has been shown to be proportional to the expected length of a random walk between two nodes, also known as the commute time <cit.>, and is closely related to concepts in Markov chains and random walks  <cit.>. A drawback of resistance distance is that it becomes less informative of graph structure when the size of the graph is very large, though there are adaptations to resistance distance that seek to compensate for this deficiency <cit.>. Effective resistance in directed graphs is a generalization of undirected resistance distance and its square root is a graph metric <cit.>.

The work presented here builds off of <cit.> and applies Lyapunov theory to define a new graph symmetrization method by calculating the undirected graph that has equivalent effective resistance to that of a given directed graph. In doing so, it follows immediately that the undirected, symmetrized graph preserves a metric of the directed graph, namely, the square root of effective resistance. Moreover, it is shown that the Laplacian matrix of a directed graph can be decomposed into the product of a projection matrix, a skew symmetric matrix, and the Laplacian matrix of the symmetrized graph. This mapping between a directed Laplacian and its symmetrized version, along with the preservation of a metric on graphs, allows certain tools from algebraic and spectral graph theory to be applied to a symmetrized graph with clear interpretation in the context of the original directed graph. Therefore, the proposed symmetrization method provides an improvement upon heuristic symmetrizations where such an interpretation is not possible. 

The paper is organized as follows. Section <ref> provides an overview of relevant notation. In Section <ref>, the generalized notion of effective resistance from <cit.> is reviewed. Section <ref> introduces effective resistance preserving graph symmetrization and the matrix relationship between a directed Laplacian and the symmetrized Laplacian. Relevant spectral properties of the symmetrized Laplacian are given in Section <ref>. Two relevant applications, graph bisection and node sparsification, are discussed in Sections <ref> and <ref>, respectively. Section <ref> briefly discusses analysis of large graphs. The paper is concluded with final remarks in Section <ref>. 






§ NOTATION
 
Let 𝒢 = (𝒱, ℰ, A) be a connected, directed graph, where 𝒱 = {1,2,…, n} is the set of vertices, and ℰ⊆𝒱×𝒱 is the set of m edges.  A ∈ℝ^n × n is the adjacency matrix where element a_i,j is the nonnegative weight on edge (i,j). If (i,j) ∈ℰ, then a_i,j > 0; otherwise a_i,j = 0.  Graphs with self loops, i.e., with an edge from a node to itself, are not considered. The out-degree of node i is calculated as d_i = ∑_j=1^n a_i,j.  The out-degree matrix is a diagonal matrix of node out-degrees, D = diag{d_1, d_2, …,d_n}. The associated directed Laplacian matrix is defined as L=D-A.  In constructing the directed Laplacian matrix the precedent is followed that out-degrees are on the main diagonal and row sums are equal to zero, that is, L1_n = 0. Let the vector of column sums of L be 1_n^TL = Δ_d.  The graphs considered are connected in the sense that there exists at least one globally reachable node, k. In other words, there is a path from every node i in 𝒢 to k. As noted in <cit.>, this notion of connectivity lies in between the classical definitions of strong and weak connectivity. The Moore–Penrose pseudoinverse of L is L^+. 

A graph is said to be undirected if A is symmetric, that is, (i,j) ∈ℰ implies (j,i) ∈ℰ and a_i,j = a_j,i. If an undirected graph has been calculated by the symmetrization method described in this paper, then edge weights a_i,j are permitted to be negative. The Laplacian matrix of an undirected graph is also symmetric. An undirected graph is connected if and only if there is a path between any pair of nodes (i,j). Sets and matrices corresponding to undirected graphs are indexed with u; for example, L_u is the undirected Laplacian associated with undirected graph 𝒢_u. 

The ith eigenvalue of a matrix Z is denoted by λ_i(Z), where the eigenvalues are ordered such that λ_1(Z)≤…≤λ_i(Z) ≤…≤λ_n(Z). The eigenvalues of a directed Laplacian matrix either are 0 or have positive real part <cit.>. The eigenvalues of an undirected Laplacian matrix are all real and nonnegative. If a graph (directed or undirected) is connected as defined above, then the associated Laplacian matrix will have one eigenvalue of 0.
 
Let 𝐞_n^(k) be the kth standard basis vector for ℝ^n. Let P_n = I_n - 1/n1_n1_n^T. Let 1^⊥_n =span{1_n}^⊥ be the subspace of ℝ^n perpendicular to 1_n. Let Q ∈ℝ^(n - 1) × n be a matrix with rows that form an orthonormal basis for 1^⊥_n. Then the following properties hold:

    Q1_n = 0,    QQ^T = I_n-1,    Q^TQ=P_n.


The reduced Laplacian matrix is defined as L̅ = QLQ^T and characterizes the Laplacian matrix on 1^⊥_n. L̅ has the same eigenvalues as L except for a 0 eigenvalue and is therefore invertible if the graph is connected <cit.>. 

Let H ∈ℝ^n × n be a projection matrix onto 1^⊥_n, where H is not necessarily an orthogonal projection matrix and HL = L, that is, the image of L is contained in the kernel of (H-I_n). 

 For a subset 𝒫⊂𝒱, let 𝒫⊂𝒱 be the complementary subset. A directed cut between two subsets (𝒫,𝒫) is defined as the sum of weights of edges directed from 𝒫 toward 𝒫. Equivalently,
 
    cut(𝒫,𝒫) = 1/2 y^T (L+L^T) y,

 where
 
    y_i = 
     1    if  i ∈𝒫, 
    
      0    if   i ∈𝒫.

For undirected graphs, cut(𝒫,𝒫)  = cut(𝒫,𝒫).




§ EFFECTIVE RESISTANCE
 
The notion of effective resistance generalizes resistance distance in undirected graphs such that directed graphs can also be considered. This section provides a brief review of effective resistance as defined in the two-part paper <cit.>. 
  <cit.>: Let 𝒢 be a connected, directed graph with n nodes and Laplacian matrix L. Then the effective resistance between nodes i and j in 𝒢 is defined as

    r_i,j   = ( 𝐞_n^(i) - 𝐞_n^(j))^T X ( 𝐞_n^(i) - 𝐞_n^(j)) 
        = x_i,i + x_j,j - 2x_i,j,

where

    X     = 2Q^T Σ Q, 
    L̅Σ + ΣL̅^T    = I_n-1, 
    L̅    = Q L Q^T,

and Q is a matrix satisfying (<ref>).

The solution, Σ, to (<ref>) has a unique, symmetric, positive definite solution when all eigenvalues of L̅ have positive real part <cit.>. Therefore, Σ is invertible whenever the graph associated with L is connected. For an undirected graph with Laplacian L_u and reduced Laplacian L̅_u = Q L_u Q^T, it can be observed that the solution to (<ref>) is Σ = 1/2L̅_u  ^-1. Thus, X = L_u^+ and r_u_i,j= ( 𝐞_n^(i) - 𝐞_n^(j) )^T L_u^+ ( 𝐞_n^(i) - 𝐞_n^(j) ). Therefore, Definition <ref> is consistent with the classical notion of resistance distance in undirected graphs by Klein and Randíc <cit.>.

The following three properties of effective resistance were proven in <cit.>:


  * Effective resistance is well-defined.

  * Effective resistance depends on connections between nodes.

  * Effective resistance is a distance-like function and its
square root is a metric.





§ UNDIRECTED AND DIRECTED LAPLACIANS WITH EQUIVALENT EFFECTIVE RESISTANCE
 
 The following section demonstrates that for any connected, directed graph with Laplacian matrix L, there exists a symmetric, undirected Laplacian L̂_u on the same set of nodes and possibly admitting negative edge weights, for which the effective resistance between any pair of nodes (i,j) in L is equal to the effective resistance between (i,j) in L̂_u.
 

Let 𝒢 = (𝒱,ℰ,A) be a directed, connected graph of order n. Then, there exists an undirected graph Ĝ_u= (𝒱,Ê_u,Â_u),  possibly admitting negative edge weights, for which effective resistance in 𝒢 is equivalent to effective resistance in Ĝ_u for all i,j ∈𝒱.


It can be observed that the unique solution to (<ref>), Σ, also satisfies the following trivial Lyapunov equation with its inverse:

    1/2Σ^-1Σ + 1/2ΣΣ^-1 = I_n-1.

Additionally, the pseudoinverse of X can be expressed as X^+ = (2Q^T Σ Q)^+ = 1/2 Q^T Σ^-1 Q. The matrix X^+, therefore, is an n × n symmetric, positive semidefinite matrix with zero row and column sums. Therefore, X^+ can be interpreted as an undirected Laplacian matrix, L̂_u = X^+, where L̂_u potentially admits negative edge weights and is associated with an undirected graph, Ĝ_u= (𝒱,Ê_u,Â_u), on the same set of nodes as 𝒢. Since L, the Laplacian associated with 𝒢,  and L̂_u have the same solution to the Lyapunov equation, (<ref>), it follows immediately that effective resistance 𝒢 is equivalent to effective resistance in Ĝ_u for all i,j ∈𝒱. 

It follows from Proposition <ref> calculating an undirected Laplacian L̂_u with equivalent effective resistance to a directed Laplacian, L can be accomplished by the following steps:


  * Calculate the reduced Laplacian, L̅ = QLQ^T.

  * Solve the Lyapunov equation L̅Σ + ΣL̅^T = I_n-1.

  * Project from ℝ^(n-1)× (n-1) to ℝ^n × n by X  = 2Q^T Σ Q.

  * Calculate the pseudoinverse L̂_u = X^+.

The resulting undirected Laplacian can be thought of as a symmetrization of a directed Laplacian where a metric on graphs, square root of effective resistance, has been preserved. This is in contrast with heuristic symmetrization methods where there is no guarantee that the symmetrized Laplacian provides a meaningful representation of the original directed Laplacian. 
To illustrate, Figure <ref> shows four simple directed graphs and the corresponding undirected graphs with equivalent effective resistance.



















In statistics, the inverse of an observed covariance matrix is known as a precision matrix, which can be used to define an undirected Laplacian (often with a sparsification step)  <cit.>. The work here follows similar logic by connecting the steady-state covariance matrix from an directed graph to the undirected graph that generates the same steady-state covariance matrix. 

From a dynamics systems perspective this means that if each node in L and L̂_u were subject to independent white noise of constant covariance, the expected steady-state covariance between any pair of nodes in L is equivalent to the expected steady-state covariance between that pair of nodes in L̂_u.  

Remark 1. When studying graphs that admit negative edge weights, it is common to employ  the signed Laplacian. The signed Laplacian is defined similarly to the combinatorial Laplacian, with the adjustment that the degree of each node is the sum of the absolute values of all adjacent edges <cit.>. The primary motivations for this definition are to ensure that the signed Laplacian is at least positive semidefinite and that there are no zero entries along the main diagonal.  Drawbacks to working with the signed Laplacian are that row and column sums are no longer guaranteed to be zero, and interpretation of spectral properties is less straightforward. A Laplacian as defined by L̂_u=X^+ is guaranteed to be positive semidefinite despite the presence of negative edge weights because Σ is positive definite and the multiplications with Q^T and Q add an eigenvalue at zero.  Due to the guaranteed positive semidefiniteness of L̂_u the signed Laplacian is not used  in this work. 



 §.§ Exploring the relationship between L and L̂_u
 
The previous section demonstrates how one can use the inverse of the solution to the Lyapunov equation to derive an undirected graph with equivalent resistance distances. It is noted that though two nonisomorphic undirected graphs can have the same multiset of resistance distances, the resistance distance matrix R with elements r_i,j uniquely determines an undirected graph up to an isomorphism. This is a result of the one-to-one relationship between elements of R and L_u^+ <cit.> in combination with the uniqueness property of Moore–Penrose pseudoinverses. Subsequently, each directed graph L has the same effective resistances as exactly one undirected graph L̂_u. However, the reverse is not true and one undirected graph L̂_u can have equivalent effective resistances to many directed graphs. The following illustrates this property and describes the algebraic relationship required between L and L̂_u such that the two graphs have equivalent resistance distances between nodes. 

It is shown above that L and L̂_u have the same solution to the Lyapunov equation on 1^⊥_n. From a linear algebra perspective, in order for equations (<ref>) and (<ref>) to hold, the following relation must be true (see <cit.>):

    L̅   = (K̅ + 1/2 I_n-1) Σ^-1, 
    L̅   = (K̅ + 1/2 I_n-1) 2QL̂_uQ^T,

where K̅ is a skew symmetric (n-1) × (n-1) matrix satisfying

    L̅K̅ + K̅L̅^T = 1/2(L̅-L̅^T) .

Pre- and postmultiplying by Q^T and Q, respectively, and recalling that Q^TQ = P_n and P_nL̂_u = L̂_uP_n = L̂_u, yields

    Q^T L̅ Q = 2KL̂_u + L̂_u,

where K = Q^T K̅ Q. It follows from the construction that K is a skew symmetric matrix with one eigenvalue at zero, and row and column sums are equal to the zero vector.  Furthermore, note that Q^T L̅ Q = Q^TQLQ^TQ = P_nLP_n = P_nL. Thus,

    P_nL = 2KL̂_u + L̂_u.

The matrix P_n is an orthogonal projection matrix onto 1^⊥_n. Therefore, P_nL has the property that the vector 1_N is in the left and right null spaces. In other words, the row and column sums of P_nL are equal to the zero vector. Premultiplying both sides by H= L(P_nL)^+ yields

    L = H(I_n + 2K )L̂_u,

where the properties from the definition of H that HP_n = H and HL = L have been applied. The intuition behind the matrix H is that it determines a node, or a set of nodes, that is globally reachable, as tr(H) = n-1 and the diagonal entries of H that satisfy H_i,i  <1 give the set of nodes which can be set as a root for a spanning tree of 𝒢. For example, if there is only one globally reachable node, k, and without loss of generality let k be indexed as the nth node, then H is of the form

    H = [ [              ⋱                                           -1;                I_(n-1)× (n-1)                             ⋮;                                            ⋱             -1;              0              ⋯              0              0 ]].

If the graph is an unweighted, directed cycle then H=P, that is, H is the orthogonal projection matrix onto 1^⊥_n. 






§ SPECTRAL PROPERTIES
 
As demonstrated in Section <ref>, one can always decompose a directed, connected Laplacian as L = H(I_N+2K)L̂_u, where L̂_u is an undirected, connected Laplacian matrix defined on the same set of nodes where effective resistance between any two nodes, i,j in L̂_u is equivalent to effective resistance between i,j in L.  This section presents additional properties of L̂_u and demonstrates that the spectra of L̂_u characterizes features of L, thus further motivating the use of L̂_u as a meaningful symmetrization of L.



 §.§ Rate of convergence to consensus

 The second smallest eigenvalue of an undirected Laplacian matrix is well known as a measure of algebraic connectivity of a graph <cit.>. Additionally, if one considers simple consensus dynamics on an undirected graph, the second smallest eigenvalue determines the rate of convergence to consensus. In other words, if each vertex in the graph is assigned a different state value and over time, updates this state as an average with its neighbors, the second smallest eigenvalue determines the rate at which the state values of each vertex become approximately equal. This notion can be extended to connected directed graphs using basic results from Lyapunov theory <cit.>. The following demonstrates that for a directed graph L and simple consensus dynamics, the rate of convergence is determined by the second smallest eigenvalue of L̂_u and is independent of H and K. 
Consider the following linear system representing noisy consensus dynamics, where d𝐖_n-1  represents a vector of increments drawn from an independent Wiener processes with standard deviation of 1,   

    ż = -L̅𝐳 +  d𝐖_n-1,

with the Lyapunov function V(𝐳) = 𝐳^T Σ𝐳 where Σ is the solution to L̅Σ + ΣL̅^T = I_n-1. Then 

    V̇(𝐳)    = 𝐳^T L̅Σ𝐳 +𝐳^T ΣL̅^T𝐳 = 𝐳^T I_n-1𝐳, 
       ≤𝐳^T𝐳≤1/λ_n-1(Σ)𝐳^TΣ𝐳 = λ_1(Σ ^-1) V(𝐳), 
        = λ_2(L̂_u) V(𝐳).

 Therefore, the transient behavior of (<ref>), or in other words the speed with which consensus is reached, can be estimated by the second smallest eigenvalue of L̂_u. This further implies that L and L̂_u have similar connectivity properties.









 §.§ Trace preservation, average cuts, and eigenvalue bounds

 The following subsection introduces preserved quantities between L and L̂_u and demonstrates that the eigenspectrum of L is bounded by the eigenspectrum of L̂_u.  

Let 𝒢 = (𝒱,ℰ,A) be a directed, connected graph of order n. Let  Ĝ_u= (𝒱,Ê_u,Â_u) be the associated undirected graph with equivalent effective resistance to 𝒢. Then the mean value of all  graph cuts in 𝒢 is equivalent to the mean value of all  cuts in  Ĝ_u.


It is clear from the decomposition L̅ = (K̅ + 1/2 I_n-1)Σ^-1 that tr(L̅) = 1/2tr(Σ^-1). Applying (<ref>) then yields tr(L) = tr(L̂_u). Since the trace of L (L̂_u) is equal to the negative sum of off-diagonal elements of L (L̂_u, respectively) it holds that the total sum of edge weights in L is equal to the total sum of edge weights in L̂_u.
Letting k = 2^n - 2 be the total number of possible bipartitions of the graph, the mean value of all graph cuts in L and L̂_u, respectively, can be written as

    C̅_L = 1/ktr(Y (L+L^T) Y^T),      C̅_L̂_u = 1/1/2ktr(Y L̂_u Y^T),

where Y is a k × n matrix where each row is a vector, y, corresponding to a partition as in (<ref>). Applying the property  that the trace of the product of three matrices is invariant under cyclic permutations gives

    C̅_L    = 1/ktr( (L+L^T) Y^TY)  
       = 1/ktr( (L+L^T) (2^n-1I + 2^n-21_n 1_n^T)) 
       = 1/ktr (L+L^T) + 1/2ktr (2^n-2Δ_d^T 1_n^T) =  1/ktr (L+L^T) 
        = 2/ktr(L̂_u) = 1/1/2ktr(Y L̂_u Y^T) = C̅_L̂_u.



In addition to the property that the sum of eigenvalues of L is equal to the sum of eigenvalues of L̂_u, it is shown in <cit.> that the eigenvalues of Σ^-1 bound those of L̅. Therefore,

    λ_2(L̂_u) ≤λ_2(L),    λ_n(L) ≤λ_n(L̂_u).




 §.§ Relationship between effective resistance and eigenvectors of L̂_u
 
The eigenvectors of L̂_u are closely related to effective resistance. More specifically, the space of the eigenvalue-scaled eigenvectors of L̂_u is a Euclidean space that preserves effective resistance in L̂_u <cit.> and therefore also in L. This can be observed by the following equation:

    r_i,j   = (𝐞_n^(i) - 𝐞_n^(j))^T X (𝐞_n^(i) - 𝐞_n^(j)) 
       = (𝐞_n^(i) - 𝐞_n^(j))^T L̂_u^+ (𝐞_n^(i) - 𝐞_n^(j)) 
       = (𝐱_i - 𝐱_j )^T U^T L̂_u^+ U (𝐱_i - 𝐱_j ) 
       = (𝐱_i - 𝐱_j )^T (Λ^1/2)^T Λ^1/2(𝐱_i - 𝐱_j) 
       = (𝐲_i - 𝐲_j )^T (𝐲_i - 𝐲_j ),

where 𝐱_i = U^T 𝐞_i and 𝐲_i = Λ^1/2𝐱_i. Thus the square root of effective resistance between two nodes is equivalent to the Euclidean distance between the corresponding elements in the transformed space.   Furthermore, as shown in <cit.>, the space of eigenvectors corresponding to the l largest eigenvalues of L̂_u^+ (l smallest nonzero eigenvalues of L̂_u) approximately preserves effective resistance. Let 𝐮_k denote the eigenvector corresponding to the kth largest  eigenvector of L̂_u^+. Let Ũ =[0,  , 0, 𝐮_l, 𝐮_l+1, , 𝐮_n],  Λ̃ = diag[0, , 0, λ_l, λ_l+1,,λ_n].  Then an approximation of effective resistance can be calculated as

    r̃_i,j= (𝐲̃_i - 𝐲̃_j )^T (𝐲̃_i - 𝐲̃_j ),

where 𝐱̃_i =Ũ𝐞_i and 𝐲̃_i = Λ̃𝐱̃_i. This approximation is bounded by the sum of the l-1 smallest eigenvalues of L̂_u^+ <cit.>:  

    r_i,j - r̃_i,j≤∑_k = 1^l-1λ_k(L̂_u^+).
 
The relationship between effective resistance and the eigenspectrum of L̂_u implies that the scaled eigenvectors of L̂_u contain information about a graph metric on L. This further motivates the use of L̂_u as a proxy for L for spectral graph analysis applications.




§ APPLICATION: GRAPH BISECTION
 
In this section, graph bisection is investigated as an application for effective resistance preserving graph symmetrization. First, undirected graph bisection and the Fiedler vector corresponding to the undirected graph Laplacian are reviewed.  Then, directed graph bisection based on the Fiedler vector of the symmetrized Laplacian L̂_u is introduced. Finally, bounds on the value of an undirected ratio cut in L̂_u in terms of cuts in L are provided. 



 §.§ Undirected Graph Bisection

In <cit.>, Fiedler demonstrated that a valid bisection of an undirected graph can be obtained by applying the eigenvector corresponding to the first nonzero eigenvalue of an undirected Laplacian as an indicator vector. That is, partitioning such that all nodes corresponding to a negative eigenvector component nodes are in one set and all nodes with a positive component are in the complementary set. Criteria for connectedness of the resulting node sets were provided in <cit.> and later generalized in <cit.>. Because of this work, the eigenvector corresponding to the first nonzero eigenvalue of an undirected Laplacian is more commonly known as the Fiedler vector.  

From a graph cut perspective, the Fiedler vector can also be shown to be the solution to the relaxed version of the undirected ratio cut problem <cit.> for which the number of clusters, k, is k=2.   Letting the value of an undirected cut be equal to the sum of the weights of edges crossed by the cut, the undirected ratio cut problem seeks to find the minimal cut(s) for which the number of nodes in each resulting subset is approximately equal. This problem is relevant to applications such as image segmentation <cit.>. Mathematically, the value of an undirected ratio cut for k=2 is defined as

    URC(𝒫_u,𝒫_u) = cut(𝒫_u,𝒫_u)/|𝒫_u |  + cut(𝒫_u,𝒫_u)/|𝒫_u | .

By defining the vector f relative to a subset 𝒫_u ∈𝒱 as

    f_i = √(|𝒫_u|/ |𝒫_u|)   if  i ∈𝒫_u, 
    
      -√(|𝒫_u|/ |𝒫_u|)   if  i ∈𝒫_u,
	
it can be shown that (see <cit.> for discussion)

    URC(𝒫_u,𝒫_u) = f^T L_u f/2n .

This allows for the following discrete optimization problem for minimizing undirected ratio cut (<ref>):

    min_𝒫_u ⊂𝒱 f^T L_u f   subject to  f ⊥1_n,   f_i  as defined in (<ref>),  f  = √(n).

The optimization problem (<ref>) is NP-hard <cit.> and can be relaxed by allowing f ∈ℝ^n, rather than discrete values. This results in 

    min_f ∈ℝ^n f^T L_u f   subject to  f ⊥1_n,   f  = √(n),

which, by the Rayleigh–Ritz theorem, can be solved by letting f be the Fiedler vector of L_u. To obtain a valid partition that serves as an approximate solution to (<ref>), the sign of f is used as an indicator function where all nodes with a corresponding positive entry in f are assigned to 𝒫_u and all nodes with a negative entry are assigned to 𝒫_u. 



 §.§ Directed Graph Bisection
 
In this subsection, bisection of a directed graph is considered, and motivation is provided for applying the Fiedler vector of the associated symmetrized Laplacian L̂_u  as an indicator function to partition the corresponding directed graph L. As demonstrated in Section <ref>, the eigenvectors of L̂_u are closely related to the effective resistance of L. Specifically, the absolute value of the difference between entries i and j in the Fiedler vector provides an approximation of the effective resistance between nodes i and j. Consequently, applying the Fiedler vector of L̂_u  as an indicator function to split L yields a division where nodes have, on average,  smaller effective resistances to other nodes within the same partition than to nodes on the other side of the split. Therefore, nodes in either partition are close to one another with respect to a graph metric. 

This is significant because the graph metric, square root of effective resistance, implicitly accounts for directionality in the graph.  It follows that the resulting graph partition is also reflective of edge directionality. To illustrate, consider the four-node graph in Figure <ref>, where, from left to right, the images show the original directed graph L, the undirected graph with equivalent effective resistance L̂_u, spectral partitioning by the Fiedler vector of L̂_u, and the partitioning applied to L. 


In contrast, consider the undirected graph on the same set of nodes where edge directionality has been discarded, as is commonly done to bypass the difficulty of working with directed graphs. The result is a star graph where node c is at the center and nodes a, b, and d are identical in that their labels can be swapped without changing the graph structure. Due to this symmetry, the second smallest eigenvalue of the undirected graph Laplacian is repeated and the Fiedler vectors corresponding to these eigenvalues have a zero entry in the row corresponding to node c, which is treated as belonging to the positive side of the partition following the precident in <cit.>. The Fiedler vector partitions are no longer unique and correspond to isolating a leaf node (a b, or d), as shown in Figure <ref>.


The partitioning of L shown in Figure <ref>   is  more reflective of the underlying graph structure and yields partitions with more structural homogeneity <cit.> than the partitioning in Figure <ref>. Nodes a and b are similar in that they share a common destination, c; therefore it is expected that nodes a and b belong to the same partition. In Figure <ref>, the partition = {a}, = {b,c,d} is equally likely as = {d}, = {a,b,c}. However, those partitions are structurally different in the context of the directed graph and would likely yield very different outcomes in graph analysis applications. 

As an additional example, consider the directed graph in Figure <ref>, where the partitions obtained by the Fiedler vector of L̂_u are indicated by the colored ovals. It is easy to check that in this example, the Fiedler vector partitioning cuts the minimum number of edges needed to split the graph into two equal sized groups. 


 Ignoring edge directionality yields the undirected roach graph <cit.>, shown in Figure <ref> with three vertical edges. For this family of graphs, it has been shown that Fiedler vector partitioning corresponds to cutting across the vertical edges connecting the upper and lower long paths, resulting in poor performance with respect to the value of the undirected ration cut as the graph size and number of vertical edges increases <cit.>. 


The comparison of Fiedler vector partitionings of the directed and undirected roach graphs is particularly interesting because the introduction of directionality improves the performance of spectral partitioning with respect to the number of cut edges. In general, this suggests that the performance of Fiedler vector partitioning of an undirected graph is not necessarily indicative of performance of Fiedler vector partitioning of a graph on the same set of nodes with some directed edges. Furthermore, the example reinforces that given a directed Laplacian, the symmetrized Laplacian L̂_u is structurally different from the Laplacian obtained by ignoring edge directionality. 



 §.§ Relating Undirected and Directed Ratio Cuts

  As discussed in Section <ref>, Fiedler vector partitioning of a symmetrized Laplacian L̂_u corresponds to approximating the minimum undirected ratio cut of L̂_u. While Section <ref>  demonstrated  that since L̂_u preserves a metric on L, the Fiedler vector partitioning of L̂_u yields a structurally meaningful partition when applied to L, it remains to be shown that there is a relationship between ratio cuts in L̂_u and in L.  To better understand what approximating the minimum of f^T L̂_uf means in terms of cuts in L, the directed ratio cut is first defined as
  
    DRC(,) =  f^T Lf/n = cut(𝒫,𝒫)/|𝒫 |  + cut(,𝒫)/|𝒫 | ,

 where, in contrast to the undirected case, cut(𝒫,𝒫) is no longer by definition equal to cut(,𝒫). 
 
 The term f^T L̂_uf can be rewritten in terms of L as 
 
    f^T L̂_uf = f^T (I_n + 2K)^-1P Lf = 1/2 f^T (I_n +S) PL f,

 where S is an orthogonal matrix, that is, S^T = S^-1, defined by the Cayley transform S = (I_n - 2K)(I_n + 2K)^-1. Since f ⊥1_n and vector multiplication with an orthogonal matrix preserves length, the following holds:
  
    1/2 f^T (I_n +S) PL f  = 1/2 f^T (I_n +S) L f = f^T L f + 1/2 f^T (S-I_n)L f.

The final equality of Equation (<ref>) is included to demonstrate that if S = I_n (alternatively, K = 0), then f^T L̂_uf = f^TLf and URC(,) = 1/2DRC(,). Thus,
   
    f^T L̂_uf     =1/2 f^T L f + 1/2 f^T SL f = 1/2 f^T L f + 1/2f̃^T L f,

where

    f̃_k    =   √(|𝒫|/ |𝒫|)∑_i ∈𝒫 S_i,k - √(|𝒫|/ |𝒫|)∑_j ∈𝒫 S_j,k.

The term ∑_i ∈𝒫 S_i,k can be easily bounded as - √(|𝒫|)≤∑_i ∈𝒫 S_i,k≤√(| 𝒫|) by applying the Cauchy–Schwarz inequality and the orthogonality of S. Similarly,  - √(|𝒫|)≤∑_j ∈𝒫 S_j,k≤√(|𝒫|). Therefore, 

    - √(|𝒫|) -  √(|𝒫|)≤f̃_k ≤√(|𝒫|) + √(|𝒫|).

   Furthermore, the elements of the vector Lf can be expressed as
 
    Lf_i = n/√(|𝒫|| 𝒫|)∑_k ∈𝒫 a_i,k   if  v_i ∈𝒫, 
    
      -n/√(|𝒫|| 𝒫|)∑_j ∈𝒫 a_i,j   if  v_i ∈𝒫.

 Consequently, upper and lower bounds on f^TSLf can be obtained by combining Equations (<ref>) and (<ref>),
 
    f^TSLf    ≥ -n (1/√(||) +1/√(||)) (cut(𝒫,𝒫) +  cut(𝒫,𝒫) ),  
    
     f^TSLf    ≤ n (1/√(||) +1/√(||)) (cut(𝒫,𝒫) +  cut(𝒫,𝒫) ).

 This leads to the following bounds on an undirected ratio cut in L̂_u in terms of cuts in L:
 
    f^T L̂_uf/2n   ≥cut(𝒫,𝒫)/|𝒫 |  + cut(𝒫,𝒫)/|𝒫 | -(1/√(||) +1/√(||)) (cut(𝒫,𝒫)+cut(𝒫,𝒫)), 
    f^T L̂_uf/2n   ≤cut(𝒫,𝒫)/|𝒫 |  + cut(𝒫,𝒫)/|𝒫 |  + (1/√(||) +1/√(||)) (cut(𝒫,𝒫)+cut(𝒫,𝒫)).


Though these bounds are loose, they establish that undirected ratio cuts in L̂_u are indeed bounded with respect to the value of directed ratio cuts in L. More specifically, Equation (<ref>) implies that letting the total cut, cut_t(𝒫,𝒫) = cut(𝒫,𝒫) +  cut(𝒫,𝒫 ), and without loss of generality assuming || ≤ ||,  

    0 ≤URC(,) ≤ (1+2√(||)) cut_t(𝒫,𝒫)/|| .

Therefore, given a directed graph L and its symmetrization L̂_u,  any approximation or solution to the optimization problem (<ref>) for  L̂_u will give a partitioning in the associated directed graph L that is at most (1 + 2√(||)) times the ratio between the total sum of directed cut edges and the cardinality of the smaller partition. The minimum of this ratio is often referred to as the edge expansion or sparsest cut of the graph <cit.>.






§ APPLICATION: NODE SPARSIFICATION
 
Kron reduction is a node (equivalently, vertex) sparsification method originating from circuit theory where the Schur complement of a subset of circuit elements is used to define an electrically equivalent circuit <cit.>. In <cit.>, the authors provide a graph-theoretic analysis of the Kron reduction process and demonstrate, among other results, that  effective resistance is preserved among nodes in a Kron-reduced graph. This property motivates an extension of Kron reduction to directed graphs, which will be discussed in the following subsection. 

The objective of extending Kron reduction to directed graphs is to construct a directed graph on a limited subset of nodes where the effective resistance between nodes in the reduced graph is equivalent to the effective resistance between those nodes in the original graph. Such a reduction is relevant to many large directed graph analysis problems where only a limited number of nodes are of interest. For example, consider a social network in which there is a small subset of users with a large number of followers. To better understand the influence of these “important” users on each other, one could construct a reduced graph with only those users. By preserving a metric, square root of effective resistance, on graphs it is ensured that if two users are at a large distance from one another in the original graph, the edge weighting in the reduced graph will be such that this distance remains the same. As a result, one can simulate interactions between these important users or how information diffuses between them without considering the entire, very large, social network. 

Before discussing the directed graph node sparsification,  Kron reduction in undirected graphs is first reviewed. Consider a subset of nodes 𝒱^⊂𝒱 and the complementary subset 𝒱^⊂𝒱 in an undirected graph with Laplacian matrix L_u partitioned as

    L_u = [ [ L_u_𝒱^,𝒱^ L_u_𝒱^,𝒱^; L_u_𝒱^,𝒱^ L_u_𝒱^,𝒱^ ]].

Then the Kron-reduced Laplacian, L_u^, on the subset 𝒱^ is defined by the Schur complement 

    L_u^ L_u_𝒱^,𝒱^ - L_u_𝒱^,𝒱^L^-1_u_𝒱^,𝒱^L_u_𝒱^,𝒱^.
 
A thorough survey of properties of the  Kron-reduced, undirected Laplacian can be found in  <cit.>. In general, it is assumed that the subset of nodes that is of interest, 𝒱^, has been determine a priori. For electrical applications, 𝒱^ typically contains external nodes, or in other words the critical electric components on the network periphery. The subset could also be determine by taking only those with certain properties, such as high degree in the social network example. Alternatively, if one wants to cut the size of the network approximately in half, the eigenvector associated with the largest eigenvalue of L_u could be applied as an indicator vector <cit.>. This gives a generalization of selecting every other node in the network. 

One straightforward approach for node sparsification of directed graphs is to replace L_u with a directed graph Laplacian, L, in Equation (<ref>). This can lead to computational difficulties when L^-1_𝒱^,𝒱^ is singular, which occurs when the set 𝒱^ contains a node with no outgoing edges. Additionally, the resulting reduced Laplacian could contain new self loops  and effective resistance between remaining nodes is typically no longer equivalent to their effective resistance in the original graph. As a result, there is in general no clear interpretation of the reduced graph Laplacian.  

Due to the fact that the effective resistance in L̂_u is equivalent to effective resistance in L, the aforementioned issues can be circumvented by calculating the Schur complement (<ref>) using L̂_u, such that an undirected graph on a subset of nodes, L̂_u^, is obtained. Then, after computing H^ = H_𝒱^,𝒱^P_m and K^ = K_𝒱^,𝒱^P_m, the reduced graph can be mapped from an undirected  to a directed graph by 

    L^ = H^ (I_m +2 K^) L̂_u^.
 A schematic drawing of this procedure is shown in Figure <ref>.
 
 

It is noted that the resulting directed, reduced Laplacian is not unique since  H^ and K^ could be alternatively defined as any projection matrix and skew symmetric matrix, respectively, that meet the descriptions from Section <ref>. The projection of the submatrices of H and K associated with 𝒱^ onto 1_n^⊥ provides an intuitive choice for the definitions of H^ and K^. Consider first the matrix H, which from a dynamical systems perspective represents damping or absorption of a dynamic process. If 1/n units of information (1 unit total over the graph) is given to each node and passed around the network through the directed edges, then the diagonal entries of the matrix I_n - H represent how much information settles, or is absorbed, at each node when the dynamic process becomes stationary. By projecting the submatrix of H associated with 𝒱^ onto 1_n^⊥, it is ensured that the damping or absorption properties of a node are preserved in the reduced graph. A similar argument can be made for the skew symmetric matrix K, which accounts for rotation and subsequently directionality in the graph. The simple projection of the submatrix of K associated with 𝒱^ onto 1_n^⊥ preserves a notion of directionality of the connections between two nodes in the reduced graph. 



§ ANALYSIS OF LARGE GRAPHS
 
It has been demonstrated that in large undirected graphs (n > 2000), effective resistance between two nodes, i and j, becomes proportional to the node degrees and structural information in r_i,j is overshadowed by these terms. That is, r_i,j 1/d_i + 1/d_j, with a small remainder reflecting graph structure <cit.>. Consequently, while all statements in this paper hold for any graph size, they are most meaningful with respect to the underlying structure when the graph is not too large. Nevertheless, if one has a distance-based problem such as clustering and chooses to symmetrize a large, directed graph using the approach from Section <ref>, it is important to analyze the resulting undirected graph with a meaningful distance measure. Two examples of distance measures applicable for the analysis of a large symmetrized Laplacian L̂_u are those induced by the amplified commute kernel <cit.> and the heat kernel <cit.>. Recall that a distance measure d_κ_i,j, between two nodes i, j, induced by a kernel κ is  d_κ_i,j = κ_i,i + κ_j,j - 2 κ_i,j. 


















A more rigorous and complete approach to studying large directed graphs would be to develop symmetrization methods that preserve distances that are strucurally representative even in large graphs. These include the distance measures induced by the aforementioned kernels as well as the class of graph-geodetic distances proposed in <cit.> and the communicability distance <cit.>. However, these distances are not yet well-defined on directed graphs. Therefore, extending these distance measures to directed graphs and establishing existence of distance preserving symmetrized graphs are areas of important future research. 



§ FINAL REMARKS
 
In this paper a new approach for directed graph symmetrization that preserves a graph metric is presented. It is shown that any connected, directed Laplacian matrix, L,  can be decomposed into the product of a projection matrix, a skew symmetric matrix, and the corresponding symmetrized Laplacian. The decomposition can be interpreted as the product of a damping (or absorption) matrix, a rotational matrix, and a symmetric positive semidefinite stability matrix.  The symmetrized Laplacian, L̂_u preserves a graph metric, the square root of effective resistance, of the original directed Laplacian. Many spectral properties of  L̂_u are shown to be reflective of properties of the L. For example, the rate of convergence to consensus for a directed graph with Laplacian L in a simple dynamic process is dominated by the second smallest eigenvalue of L̂_u. Additionally, the trace of L and its symmetrization L̂_u are equivalent and the eigenvalues of the symmetrized Laplacian bound those of the directed Laplacian. These relationships stem from the fact that the eigenvalue-scaled eigenvectors of L̂_u form a Euclidean space that preserves effective resistance in L. 

The clear relationship between the spectrum of L̂_u and properties of L motivate the application of L̂_u as a proxy for L in graph analysis methods which require symmetry. One example is graph bisection, where it is shown that taking the sign of the Fiedler vector of L̂_u as an indicator vector yields a partition that is reflective of the structure of the directed graph L. Furthermore, the value of the cut in L̂_u generated by the partition is bounded relative to the cut generated by applying the same partition to L. A second example for the application of L̂_u is node sparsification, and it has been demonstrated that the Schur complement of L̂_u corresponding to a reduced subset of nodes can be used to define a graph on the reduced subset for which effective resistance is preserved.

The symmetrization method and directed Laplacian decomposition present a number of courses for future study. Given an undirected L̂_u, one can generate a directed Laplacian, L, by choosing H and K. However, the resulting L is not necessarily insightful and could be dense. Therefore an interesting problem is to determine the matrix K that results in a directed Laplacian that is as sparse as possible,  assuming the desired set of globally reachable nodes (and therefore H), and L̂_u are known. Additionally, there are many applications for which effective resistance preserving symmetrization could be applicable, such as edge sparsification and signal processing on directed graphs.

siamplain 
 

