The classic Graph Convolutional Network (GCN) model employs both symmetric normalization and a self-loop approach. Specifically, the node-wise update equation is:

$$\mathbf{h}_{u}^{(k)} = \sigma \left( \mathbf{W}^{(k)} \sum_{v \in \mathcal{N}(u) \cup \{u\}} \frac{\mathbf{h}_v^{(k-1)}}{\sqrt{|\mathcal{N}(u) \cup \{u\}| |\mathcal{N}(v) \cup \{v\}|}} \right)$$

University of Notre Dame

Google

Information from very high degree nodes might not be useful, so researchers has suggested the following normalization:

$\mathbf{m}_{\mathcal{N}(u)}=\sum_{v\in \mathcal{N}(u)} \frac {\mathbf{h}_v}{\sqrt{|\mathcal{N}(u)\mathcal{N}(v)|}}$

Symmetric Normalization

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

Normalized Aggregation in Graph Convolutional Network (GCN)

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. 


Connection Between GCN And Message Passing

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.

Learn Before

Related