Optimal performance of Graph Convolutional Networks on the Contextual Stochastic Block Model
For Graph Neural Networks, oversmoothing denotes the homogenization of vertex embeddings as the number of layers increases. To better understand this phenomenon, we study community detection with a linearized Graph Convolutional Network on the Contextual Stochastic Block Model. We express the distribution of the embeddings in each community as a Gaussian mixture over a low-dimensional latent space, with explicit formulas in the case of a single layer. This yields tractable estimators for classification accuracy at finite depth. Numerical experiments suggest that modeling with a single Gaussian is insufficient and that the impact of depth may be more complex than previously anticipated.
EPFL
EPFL
2024-11-16
Link to LOG 2024 Conference homepage
Link to software
REVIEWED
EPFL
| Event name | Event acronym | Event place | Event date |
LOG 2024 | Online | 2024-12-02 | |
| Funder | Funding(s) | Grant Number | Grant URL |
Swiss National Science Foundation | Diffusion Processes: Source Localization and Control | 200021-182407 | |
Swiss National Science Foundation | OPtimal Estimation in RAndom Generative mOdelS: Theory, Thresholds, Tractability | 200021-200390 | |