Graph Convolution Neural Nets? Are you out of your mind? How can you do this on a graph?

Recently I am working on reproducing the paper Graph Convolutional Matrix Completion . A natural question to ask is what is convolution on graph.

Convolution at first is defined for continuous space, later maybe signal processing guy has extended this idea to discrete space(say image processing, the convolutional kernel you used in convolutional neural network). But what about graphs?

The first idea may appeared in Joan Bruna's this paper. Then extended by Defferrard et al(2016).
The version I encountered is Thomas N. Kipf et al.(2017), which I will introduce here.

The basic setting is here:

• $x\in R^N$ is a feature vector of the nodes of a graph 
• Convolutional kernel/filter $g_\theta=diag(\theta), \theta\in R^N$ lies in the Fourier domain

$g_\theta * x = Ug_\theta U^T x$
where $U$ is the matrix of eigenvectors of the normalized graph Laplacian $L=I_N-D^{-1/2}AD^{-1/2}=U \Lambda U^T$ , where $D_{i, i}=\sum_j {A_{i, j }}$

Note:

1. In spectral-based models, graph are assumed to be undirected. Normalized graph Laplacian matrix is one representation.  
2. Graph Fourier Transform: $\mathcal{F}(x)= U^T x$
3. Inverse Graph Fourier Transform: $\mathcal{F}^{-1}(\hat{x})= U \hat{x}$
4. Derivation: 

\begin{align}
g_\theta * x & = \mathcal{F}^{-1} (\mathcal{F}(x)  \odot \mathcal{F}(g)) \\
& = Ug_\theta U^T x
\end{align}

They are not satisfied, yet. Computing $g_\theta$ is expensive, so they use an approximation derived in Hammond et al.(2011), where:
$g_\theta'(\Lambda) \approx \sum_{k=0}^K \theta_k^{'}T_k(\tilde{\Lambda})$
where $T_k(x)$ is the Chebyshev polynomials. $T_0(x)=1, T_1(x)=x, T_k(x)=2xT_{k-1}(x)-T_{k-2}(x) $
$\tilde{\Lambda}=\frac{2}{\lambda_{max}} \Lambda - I_N$, $\lambda_{max}$ is the largest eigenvalue of $L$

They limit the $K=1$, and assume $\lambda_{max}\approx2$

Now:
$g_{\theta'}*x\approx \theta_0'x+\theta_1^{'}(L-I_N)x=\theta_0^{'}x-\theta_1^{'}D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x$

Further, they assume $\theta=\theta_0^{'}=-\theta_1^{'}$

Apply re-normalization trick to prevent exploding/vanishing gradients problem:

1. $\tilde{A}=A+I_N$
2. $\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}$
3. $I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$

Matrix representation:

Suppose $X\in R^{N \times C} $  is the signal/input, where C is the dim of input channels/features. $\Theta\in R^{C \times F }$ a matrix of filter parameters. $Z \in R^{N \times F}$ is the convolved 

input matrix.

$Z=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta $

Ref:

1.