# Spectral coarse graining

##### 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:

- Retrieving a matrix or a graph matrix$M$from the problem.
- Computing the eigenpairs of$M$to be preserved in the coarse-grained graph or matrix.
- Setting some problem-specific constraints (e.g. dimension of the coarse-grained object).
- Solving the constrained SCG problem, that is finding$\widehat{P}$.
- Computing from$\widehat{P}$two semi-projectors$\widehat{L}$and$\widehat{R}$(e.g. following the method proposed in [1]).
- 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 `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.
*Physical Review
Letters*, **100**(17), 2008.

D. Gfeller, and P. De Los Rios, Spectral Coarse Graining of Complex
Networks, *Physical Review Letters*, **99**(3), 2007.

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