{'fraction_non_alphanumeric': 0.03559172467889009, 'fraction_numerical': 0.008007320979180966, 'mean_word_length': 4.461977865048197, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effective Resistance Preserving Directed Graph Symmetrization

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.

methods used for clustering directed graphs including bibliometric symmetrization [25], degree-discounted symmetrization [16], 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 [7], spectral clustering of directed graphs [41], and other applications. However, the definitions in [7] 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 [39,40]. In undirected graphs, effective resistance is commonly known as resistance distiance [17] 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 [17], 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 [5], and is closely related to concepts in Markov chains and random walks [13,30]. 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 [34]. Effective resistance in directed graphs is a generalization of undirected resistance distance and its square root is a graph metric [39,40].
The work presented here builds off of [39,40] 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 2 provides an overview of relevant notation. In Section 3, the generalized notion of effective resistance from [39,40] is reviewed. Section 4 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 5. Two relevant applications, graph bisection and node sparsification, are discussed in Sections 6 and 7, respectively. Section 8 briefly discusses analysis of large graphs.
The paper is concluded with final remarks in Section 9.
2. Notation. Let G = (V, E, A) be a connected, directed graph, where V = {1, 2, . . . , n} is the set of vertices, and E ⊆ V × V is the set of m edges. A ∈ R n×n is the adjacency matrix where element a i,j is the nonnegative weight on edge (i, j).
If (i, j) ∈ E, 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 = n j=1 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 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 T n L = ∆ 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 G to k. As noted in [39], 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) ∈ E implies (j, i) ∈ E 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 G 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 [1]. 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 e (k) n be the kth standard basis vector for R n . Let P n = I n − 1 n 1 n 1 T n . Let 1 ⊥ n =span{1 n } ⊥ be the subspace of R n perpendicular to 1 n . Let Q ∈ R (n−1)×n be a matrix with rows that form an orthonormal basis for 1 ⊥ n . Then the following properties hold: The reduced Laplacian matrix is defined asL = 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 [38].
Let H ∈ R 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 P ⊂ V, let P ⊂ V be the complementary subset. A directed cut between two subsets (P, P) is defined as the sum of weights of edges directed from P toward P. Equivalently, (2.2) For undirected graphs, cut(P, P) = cut(P, P).
3. 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 [39,40].
Definition 1. [39]: Let G be a connected, directed graph with n nodes and Laplacian matrix L. Then the effective resistance between nodes i and j in G is defined as
The solution, Σ, to (3.3) has a unique, symmetric, positive definite solution when all eigenvalues ofL have positive real part [9]. Therefore, Σ is invertible whenever the graph associated with L is connected. For an undirected graph with Laplacian L u and reduced LaplacianL u = QL u Q T , it can be observed that the solution to (3.3) n ). Therefore, Definition 1 is consistent with the classical notion of resistance distance in undirected graphs by Klein and Randíc [17].
The following three properties of effective resistance were proven in [39]: 1. Effective resistance is well-defined.
2. Effective resistance depends on connections between nodes.
3. Effective resistance is a distance-like function and its square root is a metric.  Then, there exists an undirected graphĜ u = (V,Ê u ,Â u ), possibly admitting negative edge weights, for which effective resistance in G is equivalent to effective resistance in Proof. It can be observed that the unique solution to (3.3), Σ, also satisfies the following trivial Lyapunov equation with its inverse: 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 + , whereL u potentially admits negative edge weights and is associated with an undirected graph,Ĝ u = (V,Ê u ,Â u ), on the same set of nodes as G. Since L, the Laplacian associated with G, andL u have the same solution to the Lyapunov equation, (3.3), it follows immediately that effective resistance G is equivalent to effective resistance inĜ u for all i, j ∈ V.
It follows from Proposition 4.1 calculating an undirected LaplacianL u with equivalent effective resistance to a directed Laplacian, L can be accomplished by the following steps: 1. Calculate the reduced Laplacian,L = QLQ T .

Solve the Lyapunov equationLΣ + ΣL
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 4.1 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) [21]. 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 andL 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 inL 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 [20]. 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 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 [40] in combination with the uniqueness property of Moore-Penrose pseudoinverses. Subsequently, each directed graph L has the same effective resistances as exactly one undirected graphL u . However, the reverse is not true and one undirected graphL u can have equivalent effective resistances to many directed graphs. The following illustrates this property and describes the algebraic relationship required between L andL u such that the two graphs have equivalent resistance distances between nodes.
It is shown above that L andL u have the same solution to the Lyapunov equation From a linear algebra perspective, in order for equations (3.3) and (4.1) to hold, the following relation must be true (see [4]): Pre-and postmultiplying by Q T and Q, respectively, and recalling that Q T Q = P n and P nLu =L u P n =L u , yields where K = Q TK 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 TL Q = Q T QLQ T Q = P n LP n = P n L. Thus, The matrix P n is an orthogonal projection matrix onto 1 ⊥ n . Therefore, P n L 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 n L are equal to the zero vector. Premultiplying both sides by H = L(P n L) + yields 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 G. 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 If the graph is an unweighted, directed cycle then H = P , that is, H is the orthogonal projection matrix onto 1 ⊥ n .
where Y is a k × n matrix where each row is a vector, y, corresponding to a partition as in (2.2). Applying the property that the trace of the product of three matrices is invariant under cyclic permutations gives In addition to the property that the sum of eigenvalues of L is equal to the sum of eigenvalues ofL u , it is shown in [32] that the eigenvalues of Σ −1 bound those ofL. Therefore,

Relationship between effective resistance and eigenvectors ofL u .
The eigenvectors ofL u are closely related to effective resistance. More specifically, the space of the eigenvalue-scaled eigenvectors ofL u is a Euclidean space that preserves effective resistance inL u [24] and therefore also in L. This can be observed by the following equation: where x i = U T e i and y i = Λ 1/2 x 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 [12], the space of eigen- wherex i =Ũ e i andỹ i =Λx i . This approximation is bounded by the sum of the l − 1 smallest eigenvalues ofL + u [12]: The relationship between effective resistance and the eigenspectrum ofL u implies that the scaled eigenvectors ofL u contain information about a graph metric on L.
This further motivates the use ofL u as a proxy for L for spectral graph analysis applications.
6. Application: Graph Bisection. In this section, graph bisection is investigated as an application for effective resistance preserving graph symmetrization.  [11] and later generalized in [31]. 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 [15] 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 [37]. Mathematically, the value of an undirected ratio cut for k = 2 is defined as By defining the vector f relative to a subset P u ∈ V as it can be shown that (see [33] for discussion) This allows for the following discrete optimization problem for minimizing undirected ratio cut (6.1): The optimization problem (6.4) is NP-hard [35] and can be relaxed by allowing f ∈ R n , rather than discrete values. This results in  implicitly accounts for directionality in the graph. It follows that the resulting graph partition is also reflective of edge directionality. To illustrate, consider the fournode graph in Figure 6.1, where, from left to right, the images show the original directed graph L, the undirected graph with equivalent effective resistanceL u , spectral partitioning by the Fiedler vector ofL 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 [11,31]. The Fiedler vector partitions are no longer unique and correspond to isolating a leaf node (a b, or d), as shown in Figure 6.2.
The partitioning of L shown in Figure 6.1 is more reflective of the underlying graph structure and yields partitions with more structural homogeneity [22] than the  partitioning in Figure 6.2. 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 6 As an additional example, consider the directed graph in Figure 6 increases [14].
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 LaplacianL u is structurally different from the Laplacian obtained by ignoring edge directionality. where, in contrast to the undirected case, cut(P, P) is no longer by definition equal to cut(P, P).
The term f TL u f can be rewritten in terms of L as 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: The final equality of Equation (6.6) is included to demonstrate that if S = I n (alter-natively, K = 0), then f TL u f = f T Lf and URC(P, P) = 1 2 DRC(P, P). Thus, The term i∈P S i,k can be easily bounded as − |P| ≤ i∈P S i,k ≤ |P| by applying the Cauchy-Schwarz inequality and the orthogonality of S. Similarly, − |P| ≤ j∈P S j,k ≤ |P|. Therefore, Furthermore, the elements of the vector Lf can be expressed as (6.8) Consequently, upper and lower bounds on f T SLf can be obtained by combining Equations (6.7) and (6.8), |P| cut(P, P) + cut(P, P) , |P| cut(P, P) + cut(P, P) .
This leads to the following bounds on an undirected ratio cut inL u in terms of cuts in L: f TL u f 2n ≥ cut(P, P) |P| + cut(P, P) |P| cut(P, P) + cut(P, P) , f TL u f 2n ≤ cut(P, P) |P| + cut(P, P) |P| cut(P, P) + cut(P, P) .
Though these bounds are loose, they establish that undirected ratio cuts inL u are indeed bounded with respect to the value of directed ratio cuts in L. More specifically, Equation (6.9) implies that letting the total cut, cut t (P, P) = cut(P, P) + cut(P, P), and without loss of generality assuming |P| ≤ |P|, 0 ≤ URC(P, P) ≤ (1 + 2 |P|) cut t (P, P) |P| . (6.10) Therefore, given a directed graph L and its symmetrizationL u , any approximation or solution to the optimization problem (6.4) forL u will give a partitioning in the associated directed graph L that is at most (1 + 2 |P|) 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 [2]. 7. 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 [19]. In [8], 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 V k-r ⊂ V and the comple- Then the Kron-reduced Laplacian, L k-r u , on the subset V k-r is defined by the Schur A thorough survey of properties of the Kron-reduced, undirected Laplacian can be found in [8]. In general, it is assumed that the subset of nodes that is of interest, V k-r , has been determine a priori. For electrical applications, V k-r 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 [27]. 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 (7.2). This can lead to computational difficulties when L −1 V k-r ,V k-r is singular, which occurs when the set V k-r 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 inL u is equivalent to effective resistance in L, the aforementioned issues can be circumvented by calculating the Schur complement (7.2) usingL u , such that an undirected graph on a subset of nodes,L k-r u , is obtained. Then, after computing H k-r = H V k-r ,V k-r P m and K k-r = K V k-r ,V k-r P m , the reduced graph can be mapped from an undirected to a directed graph by A schematic drawing of this procedure is shown in Figure 7 It is noted that the resulting directed, reduced Laplacian is not unique since H k-r and K k-r could be alternatively defined as any projection matrix and skew symmetric matrix, respectively, that meet the descriptions from Section 4.1. The projection of the submatrices of H and K associated with V k-r onto 1 ⊥ n provides an intuitive choice for the definitions of H k-r and K k-r . 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 V k-r 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 V k-r 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 [34]. 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 4, 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 LaplacianL u are those induced by the amplified commute kernel [34] and the heat kernel [3]. 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 [6] and the communicability distance [10]. However, these distances are not yet welldefined 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.
9. 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 ofL 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 ofL u . Additionally, the trace of L and its symmetrizationL 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 ofL u form a Euclidean space that preserves effective resistance in L.
The clear relationship between the spectrum ofL u and properties of L motivate the application ofL 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 ofL 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 inL 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 ofL u is node sparsification, and it has been demonstrated that the Schur complement ofL 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 undirectedL u , one can generate a directed Laplacian, L, by choosing H and K. However, the resulting L is not neces-sarily 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), andL 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.