Spectral coarse graining

0th

Percentile

Spectral Coarse Graining

Functions to perform the Spectral Coarse Graining (SCG) of matrices and graphs.

Keywords
graphs
concept

Spectral coarse graining

Introduction

The SCG functions provide a framework, called Spectral Coarse Graining (SCG), for reducing large graphs while preserving their spectral-related features, that is features closely related with the eigenvalues and eigenvectors of a graph matrix (which for now can be the adjacency, the stochastic, or the Laplacian matrix).

Common examples of such features comprise the first-passage-time of random walkers on Markovian graphs, thermodynamic properties of lattice models in statistical physics (e.g. Ising model), and the epidemic threshold of epidemic network models (SIR and SIS models).

SCG differs from traditional clustering schemes by producing a coarse-grained graph (not just a partition of the vertices), representative of the original one. As shown in [1], Principal Component Analysis can be viewed as a particular SCG, called exact SCG, where the matrix to be coarse-grained is the covariance matrix of some data set.

SCG should be of interest to practitioners of various fields dealing with problems where matrix eigenpairs play an important role, as for instance is the case of dynamical processes on networks.

SCG in brief

The main idea of SCG is to operate on a matrix a shrinkage operation specifically designed to preserve some of the matrix eigenpairs while not altering other important matrix features (such as its structure). Mathematically, this idea was expressed as follows. Consider a (complex) $n \times n$ matrix $M$ and form the product $$\widetilde{M} = LMR^*,$$ where $\tilde n < n$ and $L,R \in \mathbf{C}^{\tilde n \times n}$ are such that $LR^*=I_{\tilde n}$ ($R^*$ denotes the conjugate transpose of $R$). Under these assumptions, it can be shown that $P=R^*L$ is an $\tilde n$-rank projector and that, if $(\lambda, v)$ is a (right) eigenpair of $M$ (i.e. $Mv=\lambda v$) and $P$ is orthogonal, there exists an eigenvalue $\tilde \lambda$ of $\widetilde M$ such that $$|\lambda-\tilde{\lambda}| \le \textrm{const} \Vert e_P(v)\Vert [1 + O(\Vert e_P(v)\Vert^2)],$$ where $\Vert e_P(v)\Vert = \Vert v-Pv\Vert$. Hence, if $P$ (or equivalently $L$, $R$) is chosen so as to make $\Vert e_P(v)\Vert$ as small as possible, one can preserve to any desired level the original eigenvalue $\lambda$ in the coarse-grained matrix $\widetilde M$; under extra assumptions on $M$, this result can be generalized to eigenvectors [1]. This leads to the following generic definition of a SCG problem.

Given $M\in\mathbf{C}^{n\times n}$ and $(\lambda,v)$ a (right) eigenpair of $M$ to be preserved by the coarse graining, the problem is to find a projector $\widehat{P}$ solving $$\min_{P\in \Omega} \Vert e_{P}(v)\Vert,$$ where $\Omega$ is a set of projectors in $\mathbf{C}^{n\times n}$ described by some ad hoc constraints $c_{1},\dots c_{r}$ (e.g. $c_{1}:P\in\mathbf{R}^{n\times n}, c_{2}:P=P^{t}, c_{3}:P_{ij}\ge 0$, etc).

Choosing pertinent constraints to solve the SCG problem is of great importance in applications. For instance, in the absence of constraints the SCG problem is solved trivially by $\widehat{P}=vv^*$ ($v$ is assumed normalized). We have designed a particular constraint, called homogeneous mixing, which ensures that vertices belonging to the same group are merged consistently from a physical point of view (see [1] for details). Under this constraint the SCG problem reduces to finding the partition of ${1,\dots,n}$ (labeling the original vertices) minimizing $$\Vert e_P(v)\Vert^{2} = \sum_{\alpha=1}^{\tilde{n}}\sum_{i\in\alpha}[v(i)-(Pv)(i)]^{2},$$ where $\alpha$ denotes a group (i.e. a block) in a partition of ${1,\dots,n}$, and $|\alpha|$ is the number of elements in $\alpha$.

If $M$ is symmetric or stochastic, for instance, then it may be desirable (or mandatory) to choose $L$, $R$ so that $\widetilde M$ is symmetric or stochastic as well. This structural constraint has led to the construction of particular semi-projectors for symmetric [1], stochastic [3] and Laplacian [2] matrices, that are made available.

In short, the coarse graining of matrices and graphs involves:

  1. Retrieving a matrix or a graph matrix$M$from the problem.
  2. Computing the eigenpairs of$M$to be preserved in the coarse-grained graph or matrix.
  3. Setting some problem-specific constraints (e.g. dimension of the coarse-grained object).
  4. Solving the constrained SCG problem, that is finding$\widehat{P}$.
  5. Computing from$\widehat{P}$two semi-projectors$\widehat{L}$and$\widehat{R}$(e.g. following the method proposed in [1]).
  6. Working out the product$\widetilde{M}=\widehat{L} M \widehat{R}^*$and, if needed, defining from$\widetilde{M}$a coarse-grained graph.

Functions for performing SCG

The main function is the all-in-one scg. This function handles all the steps involved in the Spectral Coarse Graining (SCG) of some particular matrices and graphs as described above and in reference [1]. In more details, scg computes some prescribed eigenpairs of a matrix or a graph matrix (for now adjacency, Laplacian and stochastic matrices are available), works out an optimal partition to preserve the eigenpairs, and finally outputs a coarse-grained matrix or graph along with other useful information. These steps can also be carried out independently: (1) Use get.adjacency, graph.laplacian or get.stochastic to compute a matrix $M$. (2) Work out some prescribed eigenpairs of $M$ e.g. by means of eigen or arpack. (3) Invoke one the four algorithms of the function scgGrouping to get a partition that will preserve the eigenpairs in the coarse-grained matrix. (4) Compute the semi-projectors $L$ and $R$ using scgSemiProjectors and from there the coarse-grained matrix $\widetilde{M}=LMR^*$. If necessary, construct a coarse-grained graph from $\widetilde{M}$ (e.g. as in [1]).

References

D. Morton de Lachapelle, D. Gfeller, and P. De Los Rios, Shrinking Matrices while Preserving their Eigenpairs with Application to the Spectral Coarse Graining of Graphs. Submitted to SIAM Journal on Matrix Analysis and Applications, 2008. http://people.epfl.ch/david.morton D. Gfeller, and P. De Los Rios, Spectral Coarse Graining and Synchronization in Oscillator Networks. Physical Review Letters, 100(17), 2008. http://arxiv.org/abs/0708.2055

D. Gfeller, and P. De Los Rios, Spectral Coarse Graining of Complex Networks, Physical Review Letters, 99(3), 2007. http://arxiv.org/abs/0706.0812

Aliases
  • SCG
Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.