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

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

Simple Average Normalization

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.

Learn Before

Related