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)$$

Normalized Aggregation in Graph Convolutional Network (GCN)

To normalize neighborhood aggregation based on the degrees of both the target and neighbor nodes, researchers have suggested using symmetric normalization:

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

This approach divides each neighbor's representation by the geometric mean of their degrees, reducing the influence of extremely high-degree nodes.

University of Notre Dame

Google

The most basic neighborhood aggregator takes a sum of a node’s neighbors. One drawback of this is that it’s highly sensitive to the node degrees. So there’s several ways of normalizing the aggregator.

Although it solves the degree sensitivity problem, it also caused loss of information. Indeed, it has been proven that an normalized GNN is less powerful than an not normalized GNN.


Neighborhood Normalization

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

The simplest approach to overcome node degree sensitivity is to take the average of neighbor representations:

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

Learn Before

Related

Learn After