Reproduce “Graph Neural Networks Exponentially Lose Expressive Power for Node Classification” on OpenResearch

About this paper

Kenta Oono, Taiji Suzuki

This paper provides a theoretical explanation for the over-smoothing problem in deep Graph Neural Networks (GNNs) with ReLU activations, demonstrating that node representations can exponentially lose discriminative information. The work quantifies this information loss by linking it to the product of the weight matrix's maximum singular value and the graph's spectral properties, showing that node representations converge to an invariant subspace carrying only high-level topological information when specific conditions are met.

Key insights

• Deep Graph Neural Networks (GNNs) with ReLU activations can suffer from an exponential loss of discriminative information, causing node representations to converge to an 'information-less' subspace.
• This information loss is quantitatively linked to the maximum singular value of the weight matrices ($s$) and the spectral gap of the graph Laplacian ($\lambda$), occurring when $s\lambda < 1$.
• The over-smoothing phenomenon is strongly influenced by graph topology; denser graphs, with smaller $\lambda^{-1}$, are more prone to information loss, making it harder to maintain discriminative power across layers.

Summary by alphaXiv.