acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

We study semi-supervised node classification by graph convolutional networks (GCNs) on the symmetric stochastic block model (SBM) with nodes and communities, where and denote the within- and between-community edge probabilities. An fraction of community labels is revealed, while the node features are i.i.d. standard Gaussian vectors in 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 is sufficiently large. In the logarithmic-degree regime with , the estimator achieves exact recovery when , using only a vanishing proportion of labeled nodes. A matching information-theoretic lower bound shows that this threshold is sharp. In the broader regime , under a sufficient condition on and again with only a vanishing proportion of labeled nodes, its expected misclassification rate is at most . 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.

Primary area:
learning theory
Keywords:
Stochastic Block Models, Information-Theoretic Limits, Exact Recovery, Minimax Rate, Graph Convolutions, Graph Neural Network

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_nbi3OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies semi-supervised node classification on a symmetric stochastic block model. For a one-step linearized GCN, the authors derive a sharp exact-recovery threshold and the leading-order error exponent.

Critical strengths
  1. The problem setting is meaningful.

  2. The theoretical analysis is deep.

  3. Experiments show the effectiveness of the proposed method.

Critical weaknesses
  1. Possible mismatch between theorem and method. Theorem 4.1 requires ηlogn→∞\eta logn \rightarrow \infty, but the experiments use η=2/logn\eta = 2 / logn. These experiments do not satisfy the theorem's assumptions.

  2. Possible inconsistency in experiments. Section 5 reports d=nd=n for Figures 1 and 2. However, the actual figure uses d=nd=\sqrt n.

  3. The proposed estimator is just a random-feature approximation of two-hop graph-based label propagation.

  4. The paper does not contain Limitation.

  5. The paper does not contain an AI use statement.

Questions for authors

Please see the above weaknesses

5 comments
AuthorsOpenReview ↗

Response to Reviewer nbi3: Clarifications on Experiments and Theoretical Contributions

Response to Weakness 1

We thank the reviewer for pointing this out. The original experiments use η=2/log⁡n\eta=2/\log n, which does not satisfy the condition ηlog⁡n→∞\eta\log n\to\infty in Theorem 4.1.

However, the original experiments use a smaller labeled proportion, so the estimator has less supervision and faces a harder recovery task. These results show that the method also performs well at finite sample sizes under a more limited label budget. The theorem gives a sufficient condition, so these experimental results do not contradict it.

To address the reviewer's concern, we have run additional experiments with η=1/log⁡n\eta=1/\sqrt{\log n}. This choice satisfies the theorem's condition on the labeled proportion. We again observed exact recovery, consistent with Theorem 4.1.

The experimental code was included in the supplementary material of the original submission at experiments/single_layer/exact_recovery.py. The script supports setting the labeled proportion through the --eta argument. The reviewer can use the above setting to run the additional experiments and check the results independently.

Response to Weakness 2

We thank the reviewer for asking us to clarify the settings of the different panels. These dimensions are used in different experiments. The exact-recovery experiment in Figure 1(b) uses d=nd=n, while the misclassification-rate experiments in Figures 1(d) and 2(b) use d=nlog⁡nd = n\log n and $ d = \sqrt n$, respectively.

Section 5 states these settings separately, and they agree with the labels in the corresponding figures. The first experiment studies how reducing the feature dimension affects exact recovery. The other experiments compare misclassification rates at different feature dimensions. The panels therefore use different parameter settings; there is no mismatch between the text and figures for the same experiment.

Response to Weakness 3

We thank the reviewer for pointing out this connection. Our question is whether GCNs can attain the information-theoretic limits of semi-supervised node classification on the SBM. To answer it, we study a linearized version of a standard GCN. It aggregates node features through graph convolutions and trains the readout using a regularized least-squares loss on the revealed labels. We focus on the recovery performance of this GCN and do not aim to propose a more complex estimator.

We agree that, in high dimensions, the single-layer estimator can be viewed as a random-feature approximation of two-hop graph-based label propagation scores. But this approximation alone does not give optimal recovery guarantees. Proving a sharp recovery threshold and an optimal misclassification rate requires keeping the leading constant in the error exponent. Showing only that a high-dimensional approximation holds, or that accuracy tends to one, is not enough. Length-two paths share edges, so their contributions cannot be treated as independent. The error probability caused by random features must also be small enough to leave this exponent unchanged. In the critical exact-recovery regime, we must further handle score gaps close to zero to control errors across all nodes. Through these steps, the upper bounds in Theorems 4.1 and 4.3 match the lower bounds in Theorems 4.2 and 4.4, respectively, under their common conditions. Our theoretical contribution is to prove that one gradient step on the readout, using the supervised loss, enables this simple GCN to attain information-theoretic optimality. This conclusion does not follow from its two-hop form alone.

We also study multi-layer GCNs at fixed depth. Their graph scores involve longer walks, and the analysis must handle dependencies caused by shared and repeated edges. This goes beyond the single-layer two-hop structure. Theorem 4.5 gives an upper bound on the expected misclassification rate and uses it to study the tradeoff between reduced feature noise and weaker community separation as depth increases. This bound helps explain the role of multi-layer propagation.

Response to Weaknesses 4 and 5

We thank the reviewer for raising this issue. We omitted the AI use statement from the initial submission. As soon as we noticed this omission, we emailed the Program Chairs to explain it. We have now added the full AI use statement and Limitation to the revised manuscript.

AuthorsOpenReview ↗

A Gentle Reminder

Dear Reviewer,

With less than a day left in the discussion period, we wanted to follow up on our rebuttal and revised manuscript. We would appreciate hearing whether our responses have addressed your concerns, or if there are any points that still need clarification. We are happy to respond to any remaining questions before the discussion closes. Thank you for your time.

AuthorsOpenReview ↗

Final Reminder Before the Discussion Closes

Dear Reviewer,

With only a few hours left in the discussion period, we wanted to follow up on our earlier responses. For Question 1, the original experiments show that exact recovery is possible with fewer labels (η=2/log⁡n\eta=2/\log n). This is consistent with Theorem 4.1, which gives a sufficient condition for recovery. To address your concern, we also ran experiments with η=1/log⁡n\eta=1/\sqrt{\log n}, which satisfies the theorem’s labeling condition, and again observed exact recovery. The code is available in the supplementary material. For Question 2, we clarified that we used different values of dd to illustrate different theoretical results on exact recovery and misclassification rates. The values shown in each panel match the corresponding settings in Section 5, so there is no inconsistency between the figures and the text. We also addressed the remaining questions in our earlier replies and revised the manuscript accordingly.

We believe these updates address your main concerns, and we hope to hear from you before the discussion closes. If anything remains unclear, we’ll respond as soon as we can.

Reviewer_ofTBOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The authors study the problem of perfect node classification, on a SBM with uninformative features, a fraction of revealed nodes and multiple communities. They derive both the optimal performances and the performances of a simple GCN. They show that when the dimension of the random features is large enough, a one-layer GCN reaches the optimal performances. They show how LL multiple convolution steps help to reduce the noise of the features, while leading to oversmoothing at large LL. Last they compare their predictions to numerical experiments.

Critical strengths

The derivation of bounds on the missclassification rate is relevant and extends well the exact-recovery metric. The part on the extension to the mlti-layer GCN is interesting in the sense that it shows how multiple convolution may help to reduce the noise of the features, in trade-off with oversmoothing. Yet by data-augmentation one can take arbitrary large d, which makes the behaviour independent of the features, and weakens the result.

For me the highly stylised setting (CSBM and simple linear GCN) is not a problem, in the sense it allows for a precise analysis and can give relevant insights. As shown by the literature this simplification is common in this area.

Critical weaknesses

The article is grounded on the counter-intuitive idea that uninformative features are interesting to study. It could be ; but the article is not convincing enough :

i) The authors motivate it as "existing CSBM-based analyses do not apply. Prior works typically assume that node features contain sufficient initial information and study how graph structure can further amplify feature separability." l.112 ; but according to the detailed comparison with existing works given in appendix, at least two other works encompass non-informative features.

ii) I did not went through the proofs but it seems that the assumption on the dimension of the features d=ω(n)d=\omega(n) just means that the features are quasi-orthogonal. As a consequence, they indeed play little role in the behaviour of the GCN, and most of the article is about the graph and the SBM, which has already been studied.

iii) The theorems 4.2, 4.4 on the information-theoretic bounds seem very incremental compared to previous works, as non-informative features trivially do not change anything. The authors improve on the semi-supervision.

Questions for authors

--

5 comments
AuthorsOpenReview ↗

Response to Weakness 1: Motivation for Non-Informative Features and Distinction from Related Work

We thank the reviewer for this question and for acknowledging the potential value of this setting.

We would like to reiterate our central question: Can GCNs fully exploit graph structure to attain the information-theoretic limits of semi-supervised node classification? Standard GCNs take node features as input and aggregate them through message passing between neighboring nodes. Non-informative Gaussian features are therefore a natural choice for isolating the role of graph structure without introducing additional label signal. The two related works cover graphs without external node attributes or models with zero feature signal, but they do not resolve the central question addressed in this paper. The specific differences are as follows.

Comparison with Lu (2022)

Lu (2022) also studies semi-supervised node classification by GCNs on the SBM. There are three main differences:

  1. Construction of node features. Lu directly encodes revealed labels as node features and propagates them through graph convolutions. We use non-informative Gaussian features as input and use revealed labels to compute the supervised loss. This preserves the standard GCN setup of aggregating node features and using labels for supervised training.
  2. No sharp exact-recovery threshold. Lu proves that classification accuracy can approach one in the denser regime p,q=Θ(log⁡3n/n)p,q=\Theta(\log^3 n/n), but does not establish that its method attains the information-theoretic threshold for exact recovery. Our single-layer estimator attains this threshold in the critical logarithmic-degree regime p,q=Θ(log⁡n/n)p,q=\Theta(\log n/n).
  3. No optimal misclassification exponent; guarantees limited to two communities. Lu’s accuracy guarantee also bounds the classification error probability, but does not give an error exponent matching the information-theoretic lower bound. We allow any fixed number of communities K≥2K\ge2, and establish the optimal leading exponent of the expected misclassification rate in a broader sparse regime.

Comparison with Duranthon and Zdeborová (2025)

Duranthon and Zdeborová (2025) focus on asymptotic generalization performance in the high-dimensional CSBM and the effects of depth, residual connections, and regularization. Their model includes non-informative features as a special case, but their results do not establish our optimal recovery guarantees for sparse graphs with multiple communities. Interestingly, the two studies offer complementary findings on the role of depth: they analyze how multi-layer GCNs with suitable residual connections can improve performance and approach Bayes optimality. Under our model and parameter conditions, a single-layer GCN already attains the sharp exact-recovery threshold and the optimal leading exponent of the expected misclassification rate. Whether additional depth is necessary thus depends on the model and parameter regime.

Our sharp recovery guarantees do not follow directly from either prior work. Our proof exploits the length-two path structure of the underlying graph scores. These paths share edges, so their contributions are dependent. By conditioning on the edges incident to the node being classified and regrouping the remaining terms by unordered edges, we obtain a conditional moment-generating-function calculation that preserves the leading constant in the graph’s large-deviation exponent. We then use conditional Gaussian-product tail bounds to make the feature-induced error probability negligible at this exponential scale. The key is to retain the precise exponent throughout both parts of the analysis, allowing us to match the information-theoretic lower bounds for exact recovery and the expected misclassification rate. Our results provide a benchmark for assessing how effectively GCNs exploit graph structure and for studying the additional gains from informative features in the CSBM.

Both prior works also informed our research, and we have added a new paragraph to the appendix of the revised manuscript providing a more detailed comparison. We thank the reviewer for raising this question.

AuthorsOpenReview ↗

Response to Weakness 2: High-Dimensional Random Features and GCN Analysis

We thank the reviewer for raising this question. This point is worth discussing, as it concerns the role of high-dimensional random features and how our results relate to classical SBM theory.

We agree that, under our high-dimensional assumptions, the particular feature realization has a negligible effect on the recovery threshold and the leading exponent of the expected misclassification rate. This observation alone does not establish information-theoretic optimality for GCNs or imply that our analysis is already covered by classical SBM results. Our estimator is determined by graph convolution and one gradient step on the linear readout using revealed labels. Classical SBM theory provides an important foundation, but guarantees for other algorithms do not automatically apply to this estimator. Proving its optimality requires the following analysis:

  1. Controlling feature-induced errors at the required exponential scale. In Appendix C.1, we express misclassification in terms of the sign of the score difference between the true class and a competing class after one gradient step. Conditional on the graph, community assignment, and labeled set, this difference is a sum of products of correlated Gaussian variables. Using the moment-generating-function formula in Lemma D.2, we bound the probability that feature randomness reverses a correct graph-based score ordering. Under the dimension condition of Theorem 4.3, this error contribution is bounded by exp⁡[−ω(Λn)]\exp[-\omega(\Lambda_n)]. The feature-induced error must be negligible at the exponential scale of the target misclassification rate. Near-orthogonality, or an approximation that holds with probability tending to one, does not by itself ensure this.

  2. Establishing the optimal error exponent for the GCN’s graph statistic. After controlling feature errors, we still need to analyze misclassification caused by graph randomness. The graph scores in Appendix C.1 involve length-two paths that share edges, so their contributions cannot be treated as independent. We condition on the edges incident to the node being classified and regroup the sum by unordered edges to obtain a factorized conditional moment-generating function. We then choose a suitable exponential tilting parameter and control community-size fluctuations, rounding in labeled counts, and expansion remainders to obtain P(Δˉi(k)≥0)≤exp⁡[−nK(p−q)2(1+o(1))]\mathbb P \left(\bar{\Delta}_i^{(k)}\ge0\right) \le \exp \left[-\frac{n}{K}(\sqrt{p}-\sqrt{q})^2(1+o(1))\right]. Retaining the leading constant in this exponent is essential for the optimal misclassification rate. Neither accuracy tending to one nor an exponential bound with a suboptimal constant establishes this result.

  3. Handling small score margins in the critical exact-recovery regime. Even when the graph scores correctly rank the classes, a small feature perturbation can change the prediction if the margin is close to zero. Appendix C.1 therefore uses a shifted-margin decomposition for exact recovery. It includes weakly negative margins in the graph-tail event and shows that the shift leaves the leading exponent governing the recovery threshold unchanged. We combine this decomposition with the uniform variance bounds in Lemma D.3. On the resulting good event, the dimension condition of Theorem 4.1 gives a conditional feature-error bound of n−ω(1)n^{-\omega(1)}. This is strong enough to take a union bound over all nodes and obtain the sharp exact-recovery guarantee.

These steps establish the GCN upper bounds in Theorems 4.1 and 4.3. Matching them with the information-theoretic lower bounds in Theorems 4.2 and 4.4, respectively, in their common regimes establishes optimality. Near-orthogonality provides intuition, but it does not supply these arguments linking GCN scores to misclassification probabilities and information-theoretic optimality. Our contribution is to establish these optimal recovery guarantees for this simple GCN.

AuthorsOpenReview ↗

Response to Weakness 3:Semi-Supervised Lower Bounds and GCN Optimality

We thank the reviewer for noting our extension to the semi-supervised setting. We would like to clarify the contributions of Theorems 4.2 and 4.4, both in establishing statistical limits for this setting and in providing lower bounds that match our GCN upper bounds.

We agree that non-informative features do not add label information. However, this does not make the semi-supervised lower bounds obvious, because the revealed labels give the estimator additional information. Theorems 4.2 and 4.4 establish, respectively, a necessary condition for exact recovery and an information-theoretic lower bound on the expected misclassification rate in our semi-supervised, multi-community model. In particular, under its stated conditions, Theorem 4.4 gives a lower bound with the same leading exponent as in the unsupervised case, even when a vanishing fraction of labels is revealed. This conclusion requires a proof that takes the additional label information into account.

Our main contribution is to prove that a simple GCN can attain these information-theoretic limits. Under the corresponding conditions, Theorems 4.1 and 4.2 give matching exact-recovery thresholds, while Theorems 4.3 and 4.4 give matching leading exponents for the expected misclassification rate. The lower bounds apply to all estimators using the same observations. The upper bounds show that a single-layer GCN reaches these limits with only one gradient step on the linear readout. Together, these results answer our central question: can GCNs fully use graph structure to attain the information-theoretic limits of semi-supervised node classification?

In addition, Theorem 4.5 analyzes the tradeoff between reduced feature noise and weaker separation between communities as propagation depth increases. This provides further insight into the role of depth.

Our theoretical contributions thus include sharp exact-recovery guarantees, the optimal leading exponent of the expected misclassification rate, and an analysis of multi-layer propagation. Theorems 4.2 and 4.4 provide the matching lower bounds for Theorems 4.1 and 4.3, completing the proof of the single-layer GCN’s information-theoretic optimality under the stated conditions.

Reviewer_ehk8OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies semi-supervised node classification on the symmetric Stochastic Block Model (SBM) with independent Gaussian node features carrying no label information. It asks whether a linearized GCN, using one gradient step from zero for its least-squares readout, can attain the statistical limits of community recovery.

For p=alog⁡n/np=a\log n/n and q=blog⁡n/nq=b\log n/n with fixed a>b>0a>b>0 and fixed KK, the estimator achieves exact recovery when (a−b)2>K(\sqrt{a}-\sqrt{b})^2>K, d=ω(n)d=\omega(n), and η≫1/log⁡n\eta\gg 1/\log n proportion of labeled nodes. An Information-Theoretic lower bound below the threshold establishes optimality. In a broader sparse regime, when further assume conditions on feature dimension and labeling, the authors proved that one-step gradient GCN estimator achieve exact and optimal recovery. A weaker error bound on mismatch ratio was later obtained and credit to a-multi-layer extension analysis. The theoretical findings are supported by numerical experiments.

Critical strengths
  • The non-informative-feature setting isolates a clear theoretical question about how GCNs use graph structure and revealed labels.
  • The IT lower bounds provide best possible error rate for any estimators, serving as baselines.
  • The theoretical analysis provide a sharp characterization of single-layer recovery in the stated regimes.
  • The multi-layer analysis and synthetic experiments offer useful insight into the competing effects of propagation depth.
Critical weaknesses
  • Theorem 4.3's dimension condition remains implicit and depends on a random minimum margin, i.e., R∗(A)R^*(A) is a random quantity.
  • The upper bound for expected mismatch ratio in Theorem 4.5 doesn't match the lower bound established in Theorem 4.4. Its variance term prevents the stated sufficient condition from accomplishing exact recovery in the logarithmic-degree regime.
  • The fixed-depth upper bound in Theorem 4.5 does not establish an actual oversmoothing theorem or identify an optimal depth for GCN. Together with experiments in Figure 2, they provide only qualitative rather than quantitative result.
  • Some typos. See detailed below.
Questions for authors
  1. Provide an interpretable feature dimension condition for Theorem 4.3.

The theorem assumes d>=2ζnΛn/log⁡(1+R∗(A))d>= 2\zeta_n \Lambda_n /\log (1+R^{*}(A)) with very high probability.

Here, R∗(A)R^{*}(A) is a random quantity, depending on the sampled graph.

Hence theoretical result is weak, and understanding of the algorithm is limited. Usually, for a theoretical paper, the key assumptions in Theorems should be only involving deterministic model parameters, which would clarify the roles of different parameters. Please clarify the relationship between the assumption d=ω(n)d = \omega(n) in Theorem 4.1 and the assumption here. The result of this paper will be greatly improved if the condition d>=2ζnΛn/log⁡(1+R∗(A))d>= 2\zeta_n \Lambda_n /\log (1+R^*(A)) can be relaxed to some relationship between deterministic model parameters.

2. Recovery guarantee in Theorem 4.5 doesn't cover the critical sparsity regime $Theta(\log n/n)$.

Since Vn,L≤δn1/2V_{n,L}\le\delta_n^{1/2}, the stated sufficient condition Vn,L≫log⁡nV_{n,L}\gg\log n requires δn≫(log⁡n)2\delta_n\gg(\log n)^2. It therefore cannot guarantee exact recovery when p,q=Θ(log⁡n/n)p,q=\Theta(\log n/n), even at L=1L=1, where Theorem 4.1 gives the sharp threshold. The authors acknowledge this loss of sharpness. The proof legitimately uses Schudy--Sviridenko concentration through Lemma D.4, but the resulting closed-walk estimate creates a bottleneck that can also hide the proposed balance between Wn,LW_{n,L} and Fn,LF_{n,L}. Please exhibit a concrete parameter regime where the variance term permits that balance to control the bound, and clarify which multi-layer recovery conclusions the theorem can support.

3. Theorem 4.5 does not establish actual error decrease or increase with network depth.

Theorem 4.5 bounds error from above for each fixed LL, with constants depending on LL. A worsening upper bound does not prove that the actual error increases, and comparing selected exponent terms does not provide a uniform comparison of the complete bounds across depths. In addition, the theorem does not cover depth growing with nn. Please distinguish the tradeoff suggested by the bound from a proved oversmoothing phenomenon or an optimal-depth characterization. If a formal claim of deterioration is intended, it needs a suitable lower bound or failure result; otherwise the interpretation should remain qualitative and explicitly account for Vn,LV_{n,L}.

4. The depth experiment does not directly demonstrate the proposed exponent tradeoff.

The explanation after Theorem 4.5 attributes the initial benefit of depth to an improving feature-noise exponent. However, panel (a) in Figure 2 is too coarse. The authors should consider a finer assignment for each pixel. Also, the authors should consider plot Wn,L\mathcal W_{n,L}, Vn,L\mathcal V_{n,L}, and Fn,L\mathcal F_{n,L} for the tested settings, or include a regime where feature concentration improves the bound as depth increases.

5. Typos.
  • Line 165: remove the repeated words in ``an estimator an estimator''.
7 comments
AuthorsOpenReview ↗

Response to Question 1 and a New Result on Feature Dimension

We thank the reviewer for raising this question. Following your suggestion, we have added Proposition 4.1, building on our original single-layer analysis to give a sufficient condition on the feature dimension that depends only on the model parameters. Under the model and labeling assumptions of Theorem 4.3, the condition d=ω(nΛn3ηδn3)d=\omega\left(\frac{n\Lambda_n^3}{\eta\delta_n^3}\right) yields the same upper bound on the expected misclassification rate. Here, δn\delta_n and Λn\Lambda_n retain their definitions in the main text and do not depend on the sampled graph.

The proof uses the graph margin analysis and conditional Gaussian concentration bound from the original proof. The original condition expresses the dimension needed to control feature noise for a given graph through R∗(A)R^*(\mathbf A). To obtain a condition involving only model parameters, we use degree concentration to bound the variance term in the feature error and treat small and large classification margins separately. For small margins, the existing graph large deviation analysis provides the required exponential bound. For large margins, the stated dimension condition ensures that errors caused by feature noise have a faster decay rate and therefore do not affect the leading misclassification exponent.

This addition addresses the reviewer’s concern about the dependence of the dimension condition on the sampled graph. The resulting upper bound still matches the information-theoretic lower bound in Theorem 4.4 within their common regime of applicability. Proposition 4.1 now appears immediately after Theorem 4.3, with its proof in Appendix E and a corresponding discussion at the end of Section 4.2.

AuthorsOpenReview ↗

Response to Question 2

We clarify two points in response to Question 2.

First, Theorem 4.5 covers both the critical regime of logarithmic degree and sparser graphs. The statement in the title of Question 2 that the theorem does not cover the critical sparsity regime is therefore inaccurate as a description of its scope. For fixed depth LL, Theorem 4.5 assumes 1/n≪p,q≪n−1+1/(2L)1/n\ll p,q\ll n^{-1+1/(2L)}. Subject to the remaining signal and labeling conditions, this range includes p,q=Θ(log⁡n/n)p,q=\Theta(\log n/n) as well as sparser settings such as p=alog⁡n/np=a\sqrt{\log n}/n and q=blog⁡n/nq=b\sqrt{\log n}/n, where a>b>0a>b>0 are fixed constants. Figure 2(b) examines the effect of propagation depth on the misclassification rate in precisely this sparser regime.

Second, if the reviewer means that Theorem 4.5 does not provide a sharp exact recovery guarantee in the logarithmic-degree regime, that guarantee is established by Theorem 4.1. The distinction follows from the roles of the different theorems in the paper.

Theorems 4.1 and 4.2 give matching achievability and impossibility results for exact recovery. For p=alog⁡n/np=a\log n/n and q=blog⁡n/nq=b\log n/n, under d=ω(n)d=\omega(n) and 1/log⁡n≪η≪11/\log n\ll\eta\ll1, Theorem 4.1 proves that a single-layer GCN achieves exact recovery when (a−b)2>K(\sqrt a-\sqrt b)^2>K. Theorem 4.2 proves that no estimator can achieve exact recovery when (a−b)2<K(\sqrt a-\sqrt b)^2<K. Together, these results establish that a single-layer GCN attains the information-theoretic limit, as claimed in our contributions. Under the same model and available observations, increasing depth cannot lower this optimal threshold. For the expected misclassification rate, Theorems 4.3 and 4.4 likewise provide matching upper and lower bounds in their common regime of applicability.

Theorem 4.5 extends the analysis to multiple layers. Its purpose is to examine two competing effects of adding layers through an upper bound on the misclassification rate. In suitable parameter regimes, adding layers reduces feature noise and increases the feature-noise exponent Fn,L\mathcal F_{n,L}. However, it also reduces the separation between communities, so the graph-margin exponent Wn,L\mathcal W_{n,L} decreases by a factor of γn4<1\gamma_n^4<1 with each additional layer. When the variance term Vn,L\mathcal V_{n,L} does not mask these changes, the bound reflects a tradeoff between the two effects. This helps explain why a few layers can improve performance, while too many layers may hurt it.

The discussion following Theorem 4.5 already states that the general multilayer bound does not attain the precision of the dedicated single-layer analysis and explains the technical reason. This difference does not affect the single-layer optimality results. The multilayer extension provides error guarantees and an analysis of the effects of propagation depth.

AuthorsOpenReview ↗

Response to Question 3

We consider a fixed depth LL because the classical GCNs studied in our paper can already suffer performance degradation related to oversmoothing with fewer than 10 layers. Zhao and Akoglu [1] report that models such as GCNs can show a marked drop in performance beyond about 2 to 4 layers, with oversmoothing being one of the causes. Yet real graphs used for semi-supervised node classification often contain thousands or tens of thousands of nodes. For example, the Pubmed and CoauthorCS datasets considered in [1] contain 19,717 and 18,333 nodes, respectively. Thus, the relevant depth is only a few layers, even for graphs with nearly twenty thousand nodes. Treating LL as a constant independent of nn directly addresses this separation in scale and covers the depths at which the oversmoothing phenomenon is observed. Allowing LL to grow without bound with nn is a separate theoretical question, not a requirement for explaining performance degradation that already occurs within a few layers.

We agree that allowing LL to grow with nn and determining the optimal number of layers are worthwhile research questions. The latter is already listed as an open direction in our Conclusion. A full treatment of these questions requires further theoretical analysis and, in our view, is substantial enough to form a separate paper.

[1] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling Oversmoothing in GNNs. ICLR 2020.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.