Optimal Performance of Graph Convolutional Networks on the Contextual Stochastic Block Model

Guillaume Dalle, Patrick Thiran
Proceedings of the Third Learning on Graphs Conference, PMLR 269:21:1-21:17, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v269-dalle25a, title = {Optimal Performance of Graph Convolutional Networks on the Contextual Stochastic Block Model}, author = {Dalle, Guillaume and Thiran, Patrick}, booktitle = {Proceedings of the Third Learning on Graphs Conference}, pages = {21:1--21:17}, year = {2025}, editor = {Wolf, Guy and Krishnaswamy, Smita}, volume = {269}, series = {Proceedings of Machine Learning Research}, month = {26--29 Nov}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v269/main/assets/dalle25a/dalle25a.pdf}, url = {https://proceedings.mlr.press/v269/dalle25a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Optimal Performance of Graph Convolutional Networks on the Contextual Stochastic Block Model %A Guillaume Dalle %A Patrick Thiran %B Proceedings of the Third Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2025 %E Guy Wolf %E Smita Krishnaswamy %F pmlr-v269-dalle25a %I PMLR %P 21:1--21:17 %U https://proceedings.mlr.press/v269/dalle25a.html %V 269 %X 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.
APA
Dalle, G. & Thiran, P.. (2025). Optimal Performance of Graph Convolutional Networks on the Contextual Stochastic Block Model. Proceedings of the Third Learning on Graphs Conference, in Proceedings of Machine Learning Research 269:21:1-21:17 Available from https://proceedings.mlr.press/v269/dalle25a.html.

Related Material