I'm trying to refresh my memory on diffusion kernels, and am reading this paper. I don't understand the derivation of equation 11 on page 3.
EDIT: I don't understand how the two equations:
- $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$
- $Z(t)=\left(1+\alpha H\right)^tZ(0)$
are equivalent. I actually thought I had proven them unequal (false proof included below for posterity) but Didier pointed out I made a mistake and I'm really interested in the more general question anyway.
They define $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$. One property graph-invariant property of this is that if all $Z_k$ are equal, $Z_k(t+1)=Z_k(t)$.
Now it claims $Z(t)=\left(1+\alpha H\right)^tZ(0)$. I don't see how this maintains my observation, i.e. for some matrices $H$ it seems that $Z_i(t+1)\not=Z_i(t)$ even if all $Z_i(0)$ are equal.
I tried this out with a simple (directed) graph: $V=\{a,b,c\}$, $E=\left\{(a,b),(a,c),(c,b)\right\}$. From their definition, I think
$ H=\left( \begin{array}{ccc} -2 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & -1 \end{array} \right) $
Setting $Z(0)=(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ I get that $Z(1)=(\begin{array}{ccc}3 & 0 & 2\end{array})^T$ using the definition of Z involving H, but $(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ with the summation version.
Can anyone help me figure out what's going on?