Graph Convolutional Networks Achieve Information-Theoretic Limits under Stochastic Block Models with Non-Informative Node Features

We study semi-supervised node classification by graph convolutional networks (GCNs) on the symmetric stochastic block model (SBM) with $n$ nodes and $K$ communities, where $p$ and $q$ denote the within- and between-community edge probabilities. An $\eta$ fraction of community labels is revealed, while the node features are i.i.d. standard Gaussian vectors in ${\mathbb{R}}^d$ independent of the labels. Despite the absence of feature signal, we show that a single-layer one-step gradient GCN estimator based on regularized least squares can exploit graph structure when $d$ is sufficiently large. In the logarithmic-degree regime $p,q=\Theta (\log n/n)$ with $p>q$, the estimator achieves exact recovery when $(\sqrt{p}-\sqrt{q}{)}^2>K\log n/n$, using only a vanishing proportion $\eta =o(1)$ of labeled nodes. A matching information-theoretic lower bound shows that this threshold is sharp. In the broader regime $1/n\ll p,q\ll 1$, under a sufficient condition on $d$ and again with only a vanishing proportion of labeled nodes, its expected misclassification rate is at most $\exp (-\frac{n}{K}(\sqrt{p}-\sqrt{q}{)}^2(1+o(1)))$. We further establish an information-theoretic lower bound on the expected misclassification rate when the labeled proportion vanishes. In the common regime, this lower bound matches the preceding upper bound and shows that our GCN estimator attains the optimal expected misclassification rate. We also extend the analysis to multi-layer GCNs and reveal a tradeoff between stronger feature concentration and reduced separation between communities under repeated propagation, which helps explain oversmoothing. We conduct numerical experiments on both single-layer and multi-layer GCNs that corroborate our theoretical findings.