Suppose we have a simplified GNN: $\mathbf{H}^{(k)} = \mathbf{A}_{sym} \mathbf{H}^{(k-1)} \mathbf{W}^{(k)} = \mathbf{A}_{sym}^k \mathbf{X} \mathbf{W} $

If k is big enough such that we reach an fix point, then we’ll have $\mathbf{A}_{sym} \mathbf{H}^k = \mathbf{H}^k$. At this fixed point, all nodes will converge to be defined by the dominant eigenvector of $\mathbf{A}_{sym}$. 

So we can see that stacking many rounds of message passing leads to low-pass convolutional filter, and all nodes can  become to be identical and uninformative.

University of Notre Dame

Kipf and Welling built the GCN in their work. The idea of GCN is that the model can be powerful by stacking simple convolutional layer and using a normalized variant of adjacency matrix with self-loops.:

$\mathbf{H}^{(k)}=\sigma(\tilde{\mathbf{A}} \mathbf{H}^{(k-1)} \mathbf{W}^{(k)})$

Where $\tilde{\mathbf{A}} = (\mathbf{D}+\mathbf{I})^{-\frac{1}{2}} (\mathbf{I}+\mathbf{A}) (\mathbf{D}+\mathbf{I})^{-\frac{1}{2}}$

Graph Convolutional Networks (GCN) 

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

GCN can be viewed as a more complex form of message passing with additional trainable weights and non-linearities. Suppose we combine a simple graph convolution via polynomial $\mathbf{A}+\mathbf{I}$, then we can have:

$\mathbf{H}^{(k)}=\sigma(\mathbf{A} \mathbf{H}^{(k-1)} \mathbf{W}_{neigh}^{(k)} + \mathbf{H}^{(k-1)} \mathbf{W}_{self}^{k})$

We can see that a graph convolution based on $\mathbf{I}+\mathbf{A}$ is equivalent to first aggregate neighborhood information and then combining it with information of the node-self. 


Learn Before

Related