On the Bottleneck of Graph Neural Networks and its Practical Implications

Understand

Since the proposal of the graph neural network (GNN) by Gori et al.

• (2005) and Scarselli et al.
• (2008), one of the major problems in training GNNs was their struggle to propagate information between distant nodes in the graph.
• We propose a new explanation for this problem: GNNs are susceptible to a bottleneck when aggregating messages across a long path.