Network Deconvolution

Network deconvolution as a general method to distinguish direct dependencies in networks

Assumptions

定义一个观测到的相似度矩阵，矩阵里的值可以是变量$i,j$的关系，也可以是其他的相似度值

$g_{i,j}^{obs}$ represents the similarity value between the observed patterns of variables i and j in the network.

We assume that the observed dependency matrix, $G_{obs}$, comprises both direct and indirect dependency effects

$$G_{obs}=G_{dir}+G_{indir}$$

观测矩阵包含直接和间接依赖效应

Indirect contributions

• Can be length 2 or higher
• Can be multiple effects along varying paths
• Not included Self-loops

间接影响可以是长度为2或更高,可以是沿着不同路径的多个效应,不包括自环

$$G_{indir}=G_{idr}^2+G_{dir}^3+...$$

The power associated with each term in $G_{indir}$ corresponds to the level of indirection contributed by that term. 幂次指的是间接程度

Derivation

$$G_{obs}=G_{dir}+G_{indir}$$

By using the eigen decomposition principle, we have

$$G_{dir}=U{\mathrm{\Sigma }}_{dir}{U}^{-1}$$$$\begin{array}{rl}{G}_{dir}+G_{indir}\stackrel{(a)}{=}& G_{dir}+G_{dir}^2+\cdots \\ \stackrel{(b)}{=}& \left(U{\mathrm{\Sigma }}_{dir}{U}^{-1}\right)+\left(U{\mathrm{\Sigma }}_{dir}^2{U}^{-1}\right)+\cdots \\ =& U({\mathrm{\Sigma }}_{dir}+{\mathrm{\Sigma }}_{dir}^2+\cdots )U^{-1}\\ =& U\left(\begin{array}{cccc}\sum _{i\ge 1}({\lambda }_1^{dir}{)}^i& 0& \cdots & 0\\ 0& \ddots & & ⋮\\ ⋮& & \ddots & 0\\ 0& \cdots & 0& \sum _{i\ge 1}({\lambda }_n^{dir}{)}^i\end{array}\right)U^{-1}\stackrel{(c)}{=}U\left(\begin{array}{cccc}\frac{{\lambda }_1^{dir}}{1-{\lambda }_1^{dir}}& 0& \cdots & 0\\ 0& \ddots & & ⋮\\ ⋮& & \ddots & 0\\ 0& \cdots & 0& \frac{{\lambda }_n^{dir}}{1-{\lambda }_n^{dir}}\end{array}\right)U^{-1}.\end{array}$$

By using the eigen decomposition of the observed network $G_{obs}$, we have $G_{obs}=U{\mathrm{\Sigma }}_{obs}{U}^{-1}$, where

$${\mathrm{\Sigma }}_{obs}=\left(\begin{array}{ccc}{\lambda }_1^{obs}& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & {\lambda }_n^{obs}\end{array}\right).$$$$\frac{{\lambda }_i^{dir}}{1-{\lambda }_i^{dir}}={\lambda }_i^{obs}\mathrm{\forall }1\le i\le n$$$${\lambda }_i^{dir}=\frac{{\lambda }_i^{obs}}{{\lambda }_i^{obs}+1}\mathrm{\forall }1\le i\le n$$$$G_{dir}=U{\mathrm{\Sigma }}_{dir}{U}^{-1}$$

Network deconvolution Methods

Linear Scaling Step

The observed dependency matrix is scaled linearly so that all eigenvalues of the direct dependency matrix are between −1 and 1.

线性缩放使所有特征值在 -1～1 之间

Decomposition Step

The observed dependency matrix Gobs is decomposed to its eigenvalues and eigenvectors such that

$$G_{\text{obs}}=U{\mathrm{\Sigma }}_{\text{obs}}{U}^{-1}$$

Where:

• $U$ is the matrix of eigenvectors,
• ${\mathrm{\Sigma }}_{\text{obs}}$ is a diagonal matrix containing the eigenvalues of $G_{\text{obs}}$,
• $U^{-1}$ is the inverse of the eigenvector matrix $U$.

将观察到的依赖矩阵分解为特征值和特征向量

Deconvolution Step

A diagonal eigenvalue matrix $\mathrm{\Sigma }dir$ is formed whose $i-th$ component is

$${\lambda }_i^{\text{dir}}=\frac{{\lambda }_i^{\text{obs}}}{{\lambda }_i^{\text{obs}}+1}$$

Then, the output direct dependency matrix $G_{\text{dir}}$ is obtained as

$$G_{dir}=U{\mathrm{\Sigma }}_{dir}{U}^{-1}$$

根据公式计算 ${\lambda }_i^{dir}$ ，在把其放入对角矩阵中，最后得到直接依赖矩阵

$$G_{dir}=U{\mathrm{\Sigma }}_{dir}{U}^{-1}$$

Experiments

Several network applications

• Distinguishing direct targets in gene expression regulatory networks
  • 区分基因表达调控网络中的直接目标
• Recognizing directly interacting amino-acid residues for protein structure prediction from sequence alignments
  • 通过序列比对识别直接相互作用的氨基酸残基以预测蛋白质结构
• Distinguishing strong collaborations in co-authorship social networks using connectivity information alone.
  • 仅使用连接信息来区分共同创作社交网络中的强协作。

Gene expression regulatory networks

Distinguishing direct targets in gene expression regulatory networks

Social Network

Distinguishing strong collaborations in co-authorship social networks using connectivity information alone.