Contribution of directedness in graph spectra

Many real-world datasets are represented by directed graphs. In social networks, the follower-followee relationship defines a directed edge [1]. In nervous systems, a signal transduction between neurons occurs only in one direction [2]. In this way, the directedness renders the relationship between a pair of vertices asymmetric and characterizes many properties on graphs, such as the diffusion [3] and reciprocity [4]. Nevertheless, in the studies of complex networks, the edge directions in graphs are often ignored, and directed graphs are converted to the undirected counterparts. Here, we refer to such simplification as undirectization. While undirectization may affect the result of an analysis only negligibly, it can be critical in some cases. In this study, we investigate the importance of the directedness in graph analyses by focusing on the change in graph spectra using the matrix perturbation theory.

Graphs are typically represented by matrices, such as adjacency matrices, combinatorial and normalized Laplacians [5], and non-backtracking matrices [6]. The associated graph spectra offer important tools for capturing the global properties of graphs, such as module structures [7] and network centralities [8]. For example, in spectral clustering for undirected graphs, the number of clusters is determined by the number of eigenvalues that are isolated from the (asymptotically) continuous spectral band. The eigenvectors corresponding to these isolated eigenvalues provide partitioning of a graph [9, 5]. There have been a number of studies on the spectral properties for variety of matrices in the context of statistical physics and random matrix theory [10, 11, 12]. In spectral graph theory, several bounds for the largest and second-largest eigenvalue for adjacency matrices and Laplacians have been studied [13, 14, 15].

Spectral methods for undirected graphs and directed graphs are not completely analogous to each other. Because the matrices are asymmetric for directed graphs, their spectra contain eigenvalues with non-zero imaginary parts. This is partly a reason that motivates researchers and practitioners to ignore edge directions. To formulate spectral methods for directed graphs, several graph Laplacians for the spectral clustering of directed graphs have been proposed in the literature [17, 18, 19, 20, 21, 22]. Although the choice of Laplacians is an important issue, herein, we focus only on adjacency matrices of directed and undirected graphs. There are several researches on the spectra of directed graphs. For example, in spectral graph theory, bounds of the spectral radius of adjacency matrices for directed graphs have been studied [23, 24]. In random graph theory and statistical physics, spectral densities of adjacency matrices for random directed graphs have been investigated [25, 26]. In contrast, we consider typical spectra of directed graphs based on its undirected counterpart.

Figure 1 (a) shows the eigenvalue distribution of the adjacency matrix of a macaque-cortex network [16], which is partially directed; Fig. 1(b) presents the undirectized counterpart. We note that all eigenvalues are projected onto the real axis, and the scale along the real part is slightly larger in the undirectized graph. Despite these differences, the relative distances among the five largest eigenvalues along the real axis are almost unchanged between Figs. 1(a) and 1(b).

The last observation in this example motivates us to theoretically investigate the relationship between the spectral structures of directed graphs and their undirectized counterparts. To this end, we introduce random directization as an opposite operation of ignoring edge directions. That is, we consider an undirected graph as the original graph and randomly make undirected edges directed. We consider the typical variation of eigenvalues and eigenvectors under random directization. When the fraction of directized edges is sufficiently small compared to the total number of edges, the resulting adjacency matrix can be considered as a perturbed matrix of the original one. We apply the matrix perturbation theory to analytically evaluate variations of eigenvalues and eigenvectors after directization. As shown below, an important prediction of the perturbation theory is that the relative spectral structure along the real axis of the adjacency matrix is approximately conserved when the edges are directized uniformly randomly. This conversely explains our observation in Fig. 1 on undirectization.

There have been many works on perturbative analysis for undirected graph spectra. Let $\bm{A}$ and $\bm{V}$ be real-symmetric $n\times n$ matrices, and we perturb $\bm{A}$ by adding $\bm{V}$. Let $\lambda_{i}$, $\bm{v}_{i}$ respectively denote the $i$th eigenvalue and eigenvector of $\bm{A}$, and $\tilde{\lambda}_{i}$, $\tilde{\bm{v}}_{i}$ respectively denote the $i$th eigenvalue and eigenvector of $\bm{A}+\bm{V}$. The bound for the variation of eigenvalues through this perturbation is known as the Weyl’s theorem [27]:

where $||\bm{V}||$ represents the spectral norm of $\bm{V}$. As for the variation of eigenvectors, the Davis-Kahan theorem [28] explains how the eigenvector can change with the same perturbation: the angle between $\bm{v}_{i}$ and $\tilde{\bm{v}}_{i}$ is bounded as

where the sine of the angle between two vectors is defined by $\sin\angle(\bm{v},\bm{w})=\sqrt{1-\left(\bm{v}\cdot\bm{w}/|\bm{v}||\bm{w}|\right)^{2}}$. In addition, many variants of the Weyl’s and Davis-Kahan theorems, such as the one convenient for application in statistical contexts [29] and the ones which assume low-rank matrices for $\bm{A}$ and random matrices for $\bm{V}$ [30, 31]. Sarkar et al. [32] extended the theorem in order to algorithmically estimate the number of modules in undirected graphs. Karrer and Newman [33] experimentally investigated the effect of adding edges to undirected graphs on their spectra. Note that in these studies, both the unperturbed and perturbed graphs were undirected, whereas in our study, we consider directizing perturbation.

The rest of the paper is organized as follows. In Sec. II, we formally define random directization and conduct a perturbative analysis. Then, we evaluate the variation in the spectra under undirectization in Sec. III. Finally, Sec. IV is devoted to a summary and discussions. The symbols used in this paper are listed in Appendix A.

An undirected graph has a symmetric adjacency matrix $\bm{A}$, in which $A_{ij}=A_{ji}=1$ when vertices $i$ and $j$ are connected, while $A_{ij}=0$ otherwise. The degree, defined by $d_{i}=\sum_{j}A_{ij}=\sum_{j}A_{ji}$, represents the number of the neighbors of vertex $i$. For a directed graph, in contrast, the adjacency matrix is asymmetric, i.e., $A_{ij}=1$ and $A_{ji}=0$ when an edge has a direction from vertex $i$ to vertex $j$ only. Hereafter, we regard an undirected edge in a directed graph as a pair of directed edges in both directions. The in-degree and out-degree, defined by $d_{i}^{(\mathrm{in})}=\sum_{j}A_{ji}$ and $d_{i}^{(\mathrm{out})}=\sum_{j}A_{ij}$, denote the number of in-neighboring vertices (with in-coming edges) and out-neighboring vertices (with out-going edges) of vertex $i$, respectively.

We define uniformly random directization as follows. Let $G(V,E)$ denote an undirected graph that consists of a set of vertices $V$ and edges $E$ and let $\tilde{G}(V,\tilde{E})$ denote a graph randomly directized from the original graph $G(V,E)$. The number of vertices is denoted by $N=|V|$ for both graphs, while the numbers of edges for $G(V,E)$ and $\tilde{G}(V,\tilde{E})$ are respectively denoted by $M=|E|$ and $\tilde{M}=|\tilde{E}|$; note that each undirected edge is doubly counted in the latter, but not in the former. Hereafter, $\bm{A}^{0}$ and $\tilde{\bm{A}}$ denote the adjacency matrices of $G(V,E)$ and $\tilde{G}(V,\tilde{E})$, respectively. On directization, we alter an undirected edge $e_{ij}\in E$ between vertex $i$ and vertex $j$ to a directed edge $e_{i\rightarrow j}\in\tilde{E}$ (from $i$ to $j$) with probability $q/2$, to $e_{i\leftarrow j}\in\tilde{E}$ (from $j$ to $i$) with probability $q/2$, and remain undirected with probability $1-q$, where $0\leq q\leq 1$; see Fig. 2. The number of directed edges after the uniformly random directization becomes $\tilde{M}=qM+2(1-q)M$ on average because we doubly count an undirected edge as a pair of directed edges with two directions. We express the adjacency matrix $\tilde{\bm{A}}$ of the uniformly directized graph as

where $\bm{V}$ is the perturbation matrix defined as follows: when $A^{0}_{ij}\equiv A^{0}_{ji}=1$, the set of matrix elements $\left\{V_{ij},V_{ji}\right\}$ takes $\left\{0,1\right\}$, $\left\{1,0\right\}$, or $\left\{0,0\right\}$ with probabilities $q/2$, $q/2$, and $1-q$, respectively; otherwise, $V_{ij}=V_{ji}=0$. We express the $i$th eigenvalue of $\bm{A^{0}}$ as $\lambda_{i}$ and its eigenvector as $\bm{v}_{i}$. The corresponding eigenvalue and eigenvector for $\tilde{\bm{A}}$ are denoted by $\tilde{\lambda}_{i}$ and $\tilde{\bm{v}}_{i}$, respectively. We express the ensemble of perturbation matrices $\bm{V}$ for a given adjacency matrix $\bm{A}^{0}$ as $\mathcal{S}(\bm{A}^{0})$. Throughout this paper, the norm of each eigenvector is normalized to unity.

We return to our original motivation of clarifying how the graph spectra are varied by ignoring edge directions, namely undirectization. Let $G^{\mathrm{D}}(V,E^{\mathrm{D}})$ denote a directed graph and let $G^{\mathrm{U}}(V,E^{\mathrm{U}})$ denote its undirectized graph. The numbers of edges for $G^{\mathrm{D}}$ and $G^{\mathrm{U}}$ are respectively denoted by $M^{\mathrm{D}}=|E^{\mathrm{D}}|$ and $M^{\mathrm{U}}=|E^{\mathrm{U}}|$. The fraction of directed edges, $\hat{q}$, which corresponds to the probability of directization in random directization, should satisfy $M^{\textrm{D}}=\hat{q}M^{\textrm{U}}+2(1-\hat{q})M^{\textrm{U}}$, and hence is given by $\hat{q}=2-M^{\mathrm{D}}/M^{\mathrm{U}}$. The adjacency matrices for $G^{\mathrm{D}}$ and $G^{\mathrm{U}}$ are respectively denoted by $\bm{A}^{\mathrm{D}}$ and $\bm{A}^{\mathrm{U}}$.

The result from random directization implies that the relative spectral structure along the real axis is typically maintained under undirectization when the fraction $\hat{q}$ is sufficiently small. The result of directization, Eq. (10), conversely implies that, after ignoring the edge directions, the real part of the $i$th eigenvalue $\lambda_{i}^{\textrm{D}}$ of $\bm{A}^{\mathrm{D}}$ is altered to the corresponding eigenvalue $\lambda_{i}^{\textrm{U}}$ of $\bm{A}^{\mathrm{U}}$ as in

where $\mathrm{Re}\left[\cdots\right]$ denotes the real part of a complex value.

The perturbative analysis explains why the two spectra shown in Fig. 1 share almost the same relative spectral structure for the real parts. In Fig. 7, we compare the spectra of the macaque-cortex network, in which $\hat{q}=0.30$, with the theoretical estimates. The top panel shows the resulting spectrum after random directization in Eq. (10), and the bottom panel shows the resulting spectrum after undirectization in Eq. (28). Both panels show that the perturbative analysis is moderately accurate, particularly for isolated eigenvalues.

Apart from the accuracy of the perturbation theory, we can assess, using Eq. (27), to what degree a directed graph is regarded as a uniformly randomly directized one. Figure 8 compares the directed in-degree distribution of the original (directed) macaque-cortex network and the theoretical prediction [Eq. (27)] for a uniformly randomly directed graph. We assess the null hypothesis that the edges are directized uniformly randomly, by the $\chi^{2}$ goodness-of-fit test for the distributions in the range $k^{\mathrm{in}}\leq 11$. As a result, we find that the $p$-value of the empirical distribution is less than $0.01$, which implies that the macaque-cortex network may not be regarded as a uniformly randomly directed graph, despite the accuracy of the perturbative analysis.

Note that the uniformity in random directization is not a necessary condition for the conservation of the relative spectral structure. Thus, the $\chi^{2}$ goodness-of-fit test of the in-degree distribution itself is not a criterion for the validity of our perturbative analysis. Nonetheless, this test partly explains why our analysis is plausible when the null hypothesis is not rejected.

In this study, we investigated the contribution of directedness in graph spectra. We introduced random directization as the inverse operation of ignoring the edge directions. We revealed that, in the perturbative regime, uniformly random directization does not destroy the relative spectral structure along the real axis of the undirected graphs. Additionally, we observed that the relative spectral structure along the real axis was also conserved for real-world datasets. Although the effects of directization and undirectization on the graph spectra are generally not symmetric, we showed that the results of random directization can be used to explain the behavior of the undirectization.

Several comments are in order. In Sec. II, we analyzed up to the first-order term in the perturbative expansion. However, it is not obvious whether the contributions from higher-order terms are negligible. In our formulation of perturbative random directization in Eq. (3), $q$ is not a perturbative expansion parameter, but simply defines the fraction of non-zero elements. Instead, we carry out the perturbative expansion with respect to the matrix $\bm{V}$, which does not consist of infinitesimally small elements. Here, let us consider the contribution from higher-order terms, especially the second-order term. The second-order terms in the perturbative expansion of the $i$th eigenvalue $\lambda_{i}$ along the real axis [34, 35] is given by

We numerically calculate the average of this second-order contribution $\delta\lambda_{i}^{(2)}$ over randomly directized graphs and show the result in Fig. 9 as solid lines. We also show the real part of the deviation from the first-order approximation $\delta\lambda_{i}-\left[\delta\lambda_{i}^{(1)}\right]_{\bm{V}|\bm{A}^{0}}$ in Fig. 9 as points. We observe that the second-order contribution is smaller when $q$ is sufficiently small, and the first-order approximation is indeed valid in that region. In addition, the average of the second-order term is not proportional to the original eigenvalues while that of the first-order term is. Therefore, the spectral structure can be much more complicated when higher-order contributions are dominant. In Appendix B, we analytically calculated the second-order perturbation expansion up to the first order in $q$. As an exceptional case, we can analytically obtain the random average of the variation for random graphs when $q=1$ using the cavity method. We show the result for the stochastic block model in Appendix C.

Second, we can easily show that the conservation property of the relative spectral structure cannot be generalized to arbitrary directizations. For example, let us consider non-uniform directization on a graph with a module structure with two blocks. When a specific edge $e_{ij}$ is altered to be directed as $e_{i\rightarrow j}$, the variation of each eigenvalue is expressed as

The largest eigenvalue $\lambda_{1}$ varies negatively, regardless of the choice of the edges $e_{ij}$ because $v_{1i}$ and $v_{1j}$ always have the same sign thanks to the Perron-Frobenius theorem. On the other hand, the variation of the second-largest eigenvalue $\lambda_{2}$, which is related to the module structure, depends on which edge is altered. When the edge $e_{ij}$ functions as a bridge between the two blocks, $\delta\lambda_{2}$ is expected to be positive because the eigenvector elements $v_{2i}$ and $v_{2j}$ typically have different signs. In contrast, when both ends of the edge $e_{ij}$ are located inside a common block, $\delta\lambda_{2}$ is expected to be negative because $v_{2i}$ and $v_{2j}$ typically have the same sign. Thus, the relative spectral structure is not conserved when the random directization is not uniformly random.

In this study, we evaluate the spectral variation only along the real axis. In the perturbative regime, all eigengaps along the real axis remain finite; thus, complex conjugate pairs never appear. As we further asymmetrize the adjacency matrix, some of the neighboring eigenvalues may collide at an exceptional point [35] and turn into a pair of complex conjugate eigenvalues. At the exceptional point, the corresponding eigenvectors become parallel to each other, and hence the matrix becomes undiagonalizable. The perturbation theory would no longer be valid because the matrices are assumed to be diagonalizable.

Random directization presented in this paper is applicable to resampling of graphs. Many complex systems have only one network data at one time, which makes it difficult to statistically analyze its properties, including the spectrum. To address this problem, there have been several resampling methods to duplicate similar undirected graphs from the original graph [38, 39]. The present study implies that we can utilize random directization for the purpose of resampling directed graphs with the same configuration of edges, whose relative spectral structure is typically close to the original undirected graphs.