Pith. sign in

REVIEW 3 major objections 5 minor 51 references

Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper identifies the exact information-theoretic boundary at which all test nodes in a contextual stochastic block model become jointly recoverable, and shows that a PCA spectral estimator, graph ridge regression with an optimal…

desk verdict Genuinely new semi-supervised CSBM threshold and a clean spectral estimator, but the GCN achievability is sunk by a scaling error in Lemma D.5. read the letter →

arxiv 2412.13754 v1 pith:6VNRCDWY submitted 2024-12-18 cs.LG math.PRmath.STstat.MLstat.TH

Hai-Xiao Wang , Zhichao Wang This is my paper · ORCID
classification cs.LGmath.PRmath.STstat.MLstat.TH MSC 05C8060F1062H3068T07
keywords semi-supervisedlearningcontextualstochasticblockmodelexactrecoveryinformation-theoreticthresholdspectralclusteringgraphneuralnetworkslargedeviationsridgeregression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies semi-supervised node classification on the contextual stochastic block model (CSBM): a two-community random graph in which each node also carries a Gaussian feature vector whose mean depends on its label, with only a fraction $\tau$ of labels revealed. It claims to pin down, for the first time, the information-theoretic threshold for exact recovery of all unrevealed test labels: recovery is possible if and only if $I(a_\tau,b_\tau,c_\tau)>1$, where $I=[(\sqrt{a_\tau}-\sqrt{b_\tau})^2+c_\tau]/2$ and $a_\tau,b_\tau,c_\tau$ are rescaled edge probabilities and feature signal-to-noise parameters. It further constructs a spectral PCA-type estimator that provably achieves exact recovery down to this threshold, and shows that graph ridge regression and a gradient-trained graph convolutional network achieve the same threshold when the graph is augmented with the optimal weighted self-loop. If correct, the result gives a benchmark for when any semi-supervised algorithm can perfectly label all test nodes, and shows that simple spectral methods and GCNs can be information-theoretically optimal in this model.

What carries the argument

The rate function $I(a_\tau,b_\tau,c_\tau)=[(\sqrt{a_\tau}-\sqrt{b_\tau})^2+c_\tau]/2$, with $a_\tau=a/(1-\tau)$, $b_\tau=b/(1-\tau)$, and $c_\tau=\theta^4/[q_m(\theta^2+(1-\tau)d/m)]$ in the sparse regime $\alpha=a q_m/m$, $\beta=b q_m/m$, is the object that carries the argument: it is the large-deviation exponent governing whether a single flipped test node or a small cluster can mimic the truth, so the condition $I>1$ is the boundary of exact recoverability. The constructive half of the paper rests on two spectral estimators added together: $\hat{y}_{\mathrm{SBM}}$, which uses the log-ratio of the two largest eigenvalues of the unlabeled adjacency matrix together with $A_{UL}y_L/\sqrt{m}$, and $\hat{y}_{\mathrm{GMM}}$, which uses the leading eigenvector of the Gram matrix together with $G_{UL}y_L/\sqrt{m}$. For the graph-convolution methods, the key mechanism is the weighted self-loop $\rho I_N$ added to the adjacency matrix; choosing $\rho=2c_\tau/\log(a_\tau/b_\tau)\cdot q_m$ makes the graph-convolution operator exactly balance the SBM and GMM information so that the large-deviation rate of the ridge or GCN predictor equals $I(a_\tau,b_\tau,c_\tau)$.

What would settle it

Compute $(2/(n^2 q_m))\, y_L^\top X_L W^{(1)}a$ under the paper's scaling $n\asymp K\to\infty$, $\theta^2\asymp q_m$, $d=o(q_m^2)$, with $W^{(1)}a$ aligned to $\zeta\mu$: if the result is $o(1)$ rather than $\Theta(1)$, then the estimator $s^{(1)}$ in (D.2) is inconsistent and Theorem 3.9's GCN achievability proof would not hold. Experimentally, run the GCN just above $I=1$ at increasing $m$; if exact-recovery frequency does not tend to 1, the GCN achievability claim is falsified.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a sharp phase transition: in the semi-supervised CSBM with training ratio $\tau$ and test size $m$ growing, all $m$ test-node labels can be recovered exactly, with probability tending to 1, exactly when $I(a_\tau,b_\tau,c_\tau)>1$, with $I$ defined by $I(a_\tau,b_\tau,c_\tau)=[(\sqrt{a_\tau}-\sqrt{b_\tau})^2+c_\tau]/2$. Necessity is proved by an MLE large-deviation argument: when $I<1$, the maximum-likelihood configuration differs from the truth on some flipped pair with probability tending to 1, so every algorithm misclassifies at least two test nodes; the paper also gives an exponential lower bound $\mathbb{E}\psi_m \ge e^{-I q_m}$ on the best possible mismatch ratio. Sufficiency is constructive: the spectral estimator $\hat{y}_{\mathrm{PCA}}$, formed by adding an SBM-based term using the adjacency matrix and labeled nodes and a GMM-based term using the Gram matrix and labeled nodes, recovers all test nodes with probability at least $1-m^{1-I}$ when $I>1$, and matches the optimal error exponent when $I\le 1$. The paper then claims that linear ridge regression on a graph convolution, and a two-layer GCN trained by one large gradient step plus a spectrally estimated self-loop weight, cross the same threshold when the self-loop weight is set to $\rho=2c_\tau/\log(a_\tau/b_\tau)\cdot q_m$.

Load-bearing premise

The GCN achievability claim rests on the assumption that the two-stage estimator $s^{(1)}$ from equation (D.2) is consistent for the oracle self-loop weight $2c_\tau/\log(a_\tau/b_\tau)$; if the scaled quantity $y_L^\top X_L W^{(1)}a/(n^2 q_m)$ does not converge to a positive constant, that proof step would need to be replaced.

Editorial extensions

If this is right

  • When $I(a_\tau,b_\tau,c_\tau)>1$, the spectral PCA estimator $\hat{y}_{\mathrm{PCA}}$ achieves exact recovery with probability at least $1-m^{1-I}$, so the information-theoretic threshold is attained by a polynomial-time spectral algorithm.
  • When $I(a_\tau,b_\tau,c_\tau)<1$, every algorithm misclassifies at least two test nodes with probability tending to 1, and the best achievable expected mismatch ratio decays like $e^{-I q_m}$.
  • Graph ridge regression without self-loops recovers all test nodes only under the weaker threshold $I(a_\tau,b_\tau,0)>1$; adding the optimal self-loop lifts the threshold to $I(a_\tau,b_\tau,c_\tau)>1$.
  • For heterophilic graphs with $a<b$, the optimal self-loop strength is negative, so the analysis predicts that downweighting self-loops is required for optimal graph-convolution performance.
  • A gradient-trained GCN with the estimated self-loop weight reaches exact recovery for $I(a_\tau,b_\tau,c_\tau)>1$; the paper leaves open whether its error rate below the threshold matches the optimal exponent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A scaling check of the proposed self-loop estimator $s^{(1)}$ suggests that $(2/(n^2q_m))\,y_L^\top X_L W^{(1)}a$ may be $o(1)$ rather than a positive constant; if so, Theorem 3.9's consistency claim for $s^{(1)}$ would not hold, while the PCA and ridge-regression results would stand.
  • The predicted exponent $1-I$ for the failure probability suggests a finite-size test: near the boundary, plot $\log P(\text{failure})$ against $\log m$ and check that the slope approaches $1-I$.
  • The same MLE-switching argument should transfer to other attributed random graph models, such as XOR-SBM or random geometric graphs with Gaussian features, yielding analogous thresholds with modified $a_\tau$ and $c_\tau$.
  • The optimal self-loop formula $\rho=2c_\tau/\log(a_\tau/b_\tau)\cdot q_m$ gives a concrete design rule: estimate $a,b,\tau,\theta,d$ from degrees, Gram spectrum, and labeled features, then set the self-loop weight accordingly.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies exact recovery of all unlabeled nodes in a semi-supervised Contextual Stochastic Block Model (CSBM). It derives an information-theoretic threshold I(aτ,bτ,cτ)=[(√aτ−√bτ)^2+cτ]/2, proves an impossibility theorem below that threshold, gives a lower bound on the mismatch exponent, and constructs a spectral estimator claimed to achieve the threshold. It also analyzes linear ridge regression on a graph-convolutional feature map with self-loops and claims that a one-step-gradient-trained two-layer linear GCN with a learned self-loop weight attains the same information-theoretic threshold. The main advertised novelties are the exact-recovery threshold for semi-supervised CSBM and the GCN achievability claim.

Significance. If correct, the information-theoretic threshold and the matching spectral estimator would provide a useful benchmark for semi-supervised node classification on CSBM, and the ridge-regression analysis would clarify the role of self-loops in graph-convolutional methods. The paper contains a substantial amount of technical apparatus: large-deviation rate functions, leave-one-out arguments, and numerical simulations. However, the GCN achievability theorem, which is a headline contribution of the abstract, rests on several scaling errors in Appendix D; as written, the theorem is not established. The spectral and information-theoretic parts are plausible and could be valuable after repair, but the current manuscript cannot be accepted with the GCN claim in its present form.

major comments (3)
  1. [Appendix D.3, Lemma D.5 and Eq. (D.2)] Lemma D.5 claims that (2/(n^2 q_m)) y_L^T X_L W^(1)a converges to 2cτ, but this is inconsistent with Lemma D.3. Lemma D.3 gives W^(1)a/√K = ζμ + O(η1/K) with ζ = Θ(1) and K ≍ N, while Assumption 3.1 together with d = o(q_m^2) gives θ^2 ≍ q_m. Hence y_L^T X_L W^(1)a has dominant term θ n (√K) ζ = Θ(√q_m · N · √N) = Θ(N^{3/2}√q_m), and dividing by n^2 q_m yields Θ(1/(√N√q_m)) = o(1), not the constant 2cτ. Replacing W^(1)a by its normalized version W^(1)a/√K gives Θ(θ/(n q_m)) = o(1) as well. Therefore s^(1) in Eq. (D.2) is o(1) under the paper's own scalings, and the subsequent application of Proposition D.1 at s = s_opt in the proof of Theorem 3.9 is unsupported.
  2. [Appendix D.3, Lemma D.6 and Eq. (D.2)] Lemma D.6 asserts that (1/n) y_L^T A_L y_L = ((aτ−bτ)/2) q_m + o(q_m). This is off by a factor of τ. With balanced training labels, E[y_L^T A_L y_L | y_L] = α·(# same ordered pairs) − β·(# different ordered pairs) = (n^2/2)(α−β) + O(n). Since α−β = (a−b) q_m/m and m = (1−τ)N, this expectation is τ^2 N(a−b)q_m/(2(1−τ)) + O(n), so dividing by n = τN gives (τ/2)(aτ−bτ) q_m + o(q_m). Consequently the logarithm in Eq. (D.2) does not converge to log(aτ/bτ) = log(a/b) for fixed τ ∈ (0,1); the argument of the logarithm converges to [(aτ+bτ)+τ^2(aτ−bτ)]/[(aτ+bτ)−τ^2(aτ−bτ)], whose logarithm is not log(a/b). Thus even if the numerator scaling in Lemma D.5 were repaired, s^(1) would not be a consistent estimator of the optimal self-loop weight.
  3. [Appendix C, Lemma C.5 and proof of Theorem 3.6] Lemma C.5 contains a scaling mismatch that affects the ridge-regression proof. The signal part of h(X) = (N q_m)^{-1/2} D_ρ^{-1} A_ρ X is θ/(ar d√(N q_m)) (EA_ρ y) μ^T, which equals R θ/(√(N q_m)) y μ^T with R = (aτ−bτ+2s)/(aτ+bτ+2s) for ρ = s q_m. This requires κ_m = R·θ/√q_m in the definition H = κ_m/√N y μ^T. The displayed κ_m := ((α−β+2ρ)/(α+β+2ρ))·θ√q_m is instead O(q_m) and its prefactor tends to 1 rather than R. With the displayed κ_m, the later identification κ_m τ/(κ_m^2 τ + λ) = ζ(1+o(1)) in the proof of Theorem 3.6 is false for θ^2 ≍ q_m. The theorem statement itself defines κ as an O(1) constant, so this appears to be a fixable typo, but the proof as written does not support the theorem.
minor comments (5)
  1. [Appendix A, Lemmas A.5 and A.6] Lemma A.5 and Lemma A.6 contain apparent typographical errors: the ratio in Lemma A.5 should presumably be p_X(X|yi,y−i)/p_X(X|−yi,y−i), and Lemma A.6 writes p_X in the denominator of what should be a graph likelihood ratio.
  2. [Section 3.4, Eq. (3.13) and Eq. (D.2)] The displayed formula for s^(1) in Section 3.4 is typeset ambiguously; the quotient structure is clear only after consulting Eq. (D.2) in Appendix D.
  3. [Section 3.2.4] The heading 'Comparation with unsupervised regime' should read 'Comparison with the unsupervised regime'.
  4. [Theorem 3.6] The estimator is denoted byLLR in Theorem 3.6 but byLRR in the surrounding text and in Eq. (3.9); the notation should be unified.
  5. [Section 4] The simulation plots report the number of independent trials but do not include error bars or standard deviations; given the sharp-threshold claims, some measure of variability would be helpful.

Circularity Check

0 steps flagged · score 2.0 of 10

Minor self-citations, no load-bearing circularity: central threshold and estimator optimality are derived from model likelihoods, not from the paper's own inputs.

full rationale

The paper's central claim, the exact-recovery threshold I(a_tau,b_tau,c_tau), is derived from a large-deviation analysis of the single-node log-likelihood ratio W_{m,u} in Lemma A.1, with the impossibility argument constructed from an explicit label-switching event and the achievability argument for byPCA built on an entrywise comparison to the genie estimator (Lemma B.2). These steps do not presuppose the threshold; they compute it. Likewise, the ridge-regression threshold follows from the LDP in Proposition C.1 and the optimization in Lemma C.2, and the GCN result applies a separate LDP (Proposition D.1) to a test-node statistic. The estimator s(1) is an adaptive estimate of the oracle self-loop weight; even if Lemma D.5's claimed consistency is dimensionally questionable, that is a potential correctness flaw, not circularity, because no fitted quantity is renamed as a prediction. The self-citations [19] and [45] are used only as sources of auxiliary spectral-norm concentration and as proof templates for the MLE-switching argument; the relevant arguments are reproduced in the appendices and do not smuggle in the target result. The paper is therefore self-contained with respect to its main information-theoretic and algorithmic claims, and no reduction of a prediction to its own input is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theoretical analysis treats the CSBM parameters (a,b,cτ,τ) as known inputs; the optimal self-loop ρ is a closed-form function of them, not fitted. The GCN training uses hyperparameters (K,η1,λ1) chosen by scaling assumptions, not fit to data. The main external inputs are the large-deviation and entrywise eigenvector results from [4,3,44] and the self-cited [19,45].

assumptions (5)
  • domain assumption CSBM generative model: balanced labels, uniform μ, SBM edges with probabilities α,β, and GMM features with signal θ.
    The entire analysis is confined to this synthetic model; real graphs depart from it.
  • domain assumption Asymptotic scaling (Assumption 3.1): α=a q_m/m, β=b q_m/m, cτ fixed, and τ fixed as m→∞.
    All thresholds and rates are derived under this sparse-but-diverging-degree regime.
  • standard math Large-deviation and entrywise eigenvector tools from [4], [3], and [44] are valid in the stated parameter regimes.
    Proofs of Theorems 3.2-3.5 and Appendix C rely on these external concentration results; [19] is also used and is self-cited.
  • ad hoc to paper GCN initialization and scaling (Assumption 3.8): K≍N, d=o(q_m^2), W0 scaled N(0,1/K), a uniform ±1, one-step GD with η1=Θ(K/√q_m).
    This assumption is tailored to make the feature-learning analysis work and is substantially narrower than the regimes treated elsewhere in the paper.
  • standard math The row/column norm and operator norm concentration bounds in Lemmas C.3-C.8 hold with the stated high probabilities.
    The ridge-regression proof relies on these bounds to replace the data-dependent degree matrix by its expectation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks." pith.science (2026). https://pith.science/paper/6VNRCDWY

@misc{pith2026241213754,
  author       = {Pith},
  title        = {Pith review of: Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6VNRCDWY}},
  note         = {Machine review of arXiv:2412.13754}
}
read the original abstract

We delve into the challenge of semi-supervised node classification on the Contextual Stochastic Block Model (CSBM) dataset. Here, nodes from the two-cluster Stochastic Block Model (SBM) are coupled with feature vectors, which are derived from a Gaussian Mixture Model (GMM) that corresponds to their respective node labels. With only a subset of the CSBM node labels accessible for training, our primary objective becomes the accurate classification of the remaining nodes. Venturing into the transductive learning landscape, we, for the first time, pinpoint the information-theoretical threshold for the exact recovery of all test nodes in CSBM. Concurrently, we design an optimal spectral estimator inspired by Principal Component Analysis (PCA) with the training labels and essential data from both the adjacency matrix and feature vectors. We also evaluate the efficacy of graph ridge regression and Graph Convolutional Networks (GCN) on this synthetic dataset. Our findings underscore that graph ridge regression and GCN possess the ability to achieve the information threshold of exact recovery in a manner akin to the optimal estimator when using the optimal weighted self-loops. This highlights the potential role of feature learning in augmenting the proficiency of GCN, especially in the realm of semi-supervised learning.

Figures

Figures reproduced from arXiv: 2412.13754 by the authors.

Figure 1
Figure 1. An example of SBM under semi-supervised learning. Red: VL,+; blue: VL,−; yellow: VU,+; and orange VU,−. Definition 2.5 (Semisupervised CSBM). Suppose that yL , yU are uniformly sampled from {±1} n, {±1} m respectively, satisfying 1 ⊤ n yL = 1 ⊤ myU = 0. After concatenating y = [y ⊤ L , y ⊤ U ] ⊤, we have (A, {xi} N i=1) sampled from CSBM(y, µ, α, β, θ) in Definition 2.4. Remark 2.6. It reduces to the unsupervised re… view at source ↗
Figure 2
Figure 2. Performance of ybPCA in (3.5): fix N = 800, τ = 0.25 and vary a (y-axis) and b (x￾axis) from 1 to 10.5. For each parameter configuration (aτ , bτ , cτ ), we compute the frequency of exact recovery over 20 independent runs. Light color represents a high chance of success. Phase transitions occurs at the red curve I(aτ , bτ , cτ ) = 1, as proved by Theorems 3.2 and 3.4. 3.2.3. The regime 1 ≪ qm ≪ log(m). When the grap… view at source ↗
Figure 3
Figure 3. The y-axis is q −1 m log(Eψm), the average mismatch ratio on the logarithmic scale. The x-axis is a, varying from 0 to 10.5. Fix b = 5, τ = 0.25, cτ = 0.5. The red curve is −I(aτ , bτ , cτ ), the lower bound predicted by Theorem 3.3. The experiments over different N shows that ybPCA achieves the information-theoretical limits, as proved in Theorems 3.4 and 3.5. 3.2.4. Comparation with unsupervised regime. When only … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Performance of ybLRR in (3.9). Fix N = 800, τ = 0.25, cτ = 0.5. Compute the frequency of exact recovery over 20 independent runs. When I(aτ , bτ , cτ ) > 1, ybLRR achieves exact recovery, as proved in Theorem 3.6 (a) and (b). Consequently, ρ = 2cτ log(a/b) qm is the op…
Figure 5
Figure 5. Figure 5: The y-axis is Eψm , the average mismatch ratio over 20 independent runs. The x-axis is a, varying from 0 to 10.5. Fix b = 4, τ = 0.25, cτ = 0.5, N = 400. The red curve is m−I(aτ ,bτ ,cτ ) , the lower bound predicted by Theorem 3.3 with qm = log(m). This experiment show…
Figure 6
Figure 6. Figure 6: Mismatch ratio difference of ybGCN when with or without self-loop for fixed b = 4, cτ = 0.5, N = 400. Theorem 3.9. Under Assumptions 3.1 and 3.8, suppose that learning rate η1 = Θ(K/√qm) and weight decay rate λ1 = η −1 1 . Then, estimator ybGCN = SUf(X) with W = W(1) a…
Figure 7
Figure 7. Figure 7: Performance of ybGCN when N = 400, τ = 0.25, cτ = 0.5. 4. Numerical simulations In this section, we present numerical simulations for the algorithms we investigated above. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 43 canonical work pages

  1. [1]

    E. Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2018. URL http://jmlr.org/papers/v18/16-480.html. 12

    work page 2018

  2. [2]

    E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions on information theory , 62(1):471–487, 2015

    work page 2015

  3. [3]

    E. Abbe, J. Fan, K. Wang, and Y. Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics , 48(3):1452, 2020

    work page 2020

  4. [4]

    E. Abbe, J. Fan, and K. Wang. An ℓp theory of pca and spectral clustering. The Annals of Statistics , 50(4):2359–2385, 2022

    work page 2022

  5. [5]

    J. Alt, R. Ducatez, and A. Knowles. Extremal eigenvalues of critical Erd˝ os–R´ enyi graphs.The Annals of Probability, 49(3):1347–1401, 2021

    work page 2021

  6. [6]

    Aminian, M

    G. Aminian, M. Abroshan, M. M. Khalili, L. Toni, and M. Rodrigues. An information-theoretical approach to semi-supervised learning under covariate-shift. In International Conference on Artificial Intelligence and Statistics , pages 7433–7449. PMLR, 2022

    work page 2022

  7. [7]

    Azriel, L

    D. Azriel, L. D. Brown, M. Sklar, R. Berk, A. Buja, and L. Zhao. Semi-supervised linear regression. Journal of the American Statistical Association , 117(540):2238–2251, 2022

    work page 2022

  8. [8]

    J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu, and G. Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932–37946, 2022

    work page 2022

Show all 51 references
  1. [9]

    Baranwal, K

    A. Baranwal, K. Fountoulakis, and A. Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning , ...

    2021

  2. [10]

    Baranwal, K

    A. Baranwal, K. Fountoulakis, and A. Jagannath. Effects of graph convolutions in multi-layer net- works. In The Eleventh International Conference on Learning Representations , 2023. URL https: //openreview.net/forum?id=P-73JPgRs0R

    2023

  3. [11]

    Baranwal, K

    A. Baranwal, K. Fountoulakis, and A. Jagannath. Optimality of message-passing architectures for sparse graphs. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. URL https://openreview.net/forum?id=d1knqWjmNt

    2023

  4. [12]

    Belkin, I

    M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi-supervised learning on large graphs. In Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4,

    2004

  5. [13]

    Bojchevski and S

    A. Bojchevski and S. G¨ unnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Representations , 2018. URL https: //openreview.net/forum?id=r1ZdKJ-0W

    2018

  6. [14]

    Bruna and X

    J. Bruna and X. Li. Community detection with graph neural networks. stat, 1050:27, 2017

    2017

  7. [15]

    Chakrabortty and T

    A. Chakrabortty and T. Cai. Efficient and adaptive linear regression in semi-supervised settings. The Annals of Statistics , pages 1541–1572, 2018

    2018

  8. [16]

    Z. Chen, L. Li, and J. Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations , 2019. URL https://openreview.net/forum? id=H1g0Z3A9Fm

    2019

  9. [17]

    Damian, J

    A. Damian, J. Lee, and M. Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413–5452. PMLR, 2022

    2022

  10. [18]

    Deshpande, S

    Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual stochastic block mod- els. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett, editors, Advances in Neural Information Processing Systems , volume 31. Curran As- sociates, Inc., 2...

    2018

  11. [19]

    Dumitriu and H.-X

    I. Dumitriu and H.-X. Wang. Optimal and exact recovery on general non-uniform hypergraph stochastic block model. arXiv preprint arXiv:2304.13139 , 2023

    2023 arXiv

  12. [20]

    Duranthon and L

    O. Duranthon and L. Zdeborov´ a. Optimal inference in contextual stochastic block models. arXiv preprint arXiv:2306.07948, 2023

    2023 arXiv

  13. [21]

    Duranthon and L

    O. Duranthon and L. Zdeborov´ a. Asymptotic generalization error of a single-layer graph convolutional network. arXiv preprint arXiv:2402.03818 , 2024. 13

    2024 arXiv

  14. [22]

    Esser, L

    P. Esser, L. Chennuru Vankadara, and D. Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34:27043– 27056, 2021

    2021

  15. [23]

    Feige and E

    U. Feige and E. O. Ofek. Spectral techniques applied to sparse random graphs. Random Structures & Algorithms, 27, 2005. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20089

    2005 doi

  16. [24]

    Fountoulakis, D

    K. Fountoulakis, D. He, S. Lattanzi, B. Perozzi, A. Tsitsulin, and S. Yang. On classification thresholds for graph attention with edge features. arXiv preprint arXiv:2210.10014 , 2022

    2022 arXiv

  17. [25]

    Fountoulakis, A

    K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, and A. Jagannath. Graph attention retrospective. Journal of Machine Learning Research , 24(246):1–52, 2023

    2023

  18. [26]

    H. He, H. Yan, and V. Y. Tan. Information-theoretic characterization of the generalization error for iterative semi-supervised learning. The Journal of Machine Learning Research, 23(1):13041–13092, 2022

    2022

  19. [27]

    X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. Lightgcn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval , pages 639–648, 2020

    2020

  20. [28]

    Huang, Y

    W. Huang, Y. Cao, H. Wang, X. Cao, and T. Suzuki. Graph neural networks provably benefit from structural information: A feature learning perspective. arXiv preprint arXiv:2306.13926 , 2023

    2023 arXiv

  21. [29]

    C. Kim, A. S. Bandeira, and M. X. Goemans. Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach. arXiv preprint arXiv:1807.02884 , 2018

    2018 arXiv

  22. [30]

    T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017. URL https://openreview.net/forum? id=SJU4ayYgl

    2017

  23. [31]

    Lampert and I

    M. Lampert and I. Scholtes. The self-loop paradox: Investigating the impact of self-loops on graph neural networks. arXiv preprint arXiv:2312.01721 , 2023

    2023 arXiv

  24. [32]

    Lelarge and L

    M. Lelarge and L. Miolane. Asymptotic bayes risk for gaussian mixture in a semi-supervised setting. In 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Pro- cessing (CAMSAP), pages 639–643. IEEE, 2019

    2019

  25. [33]

    Lu and S

    C. Lu and S. Sen. Contextual stochastic block model: Sharp thresholds and contiguity. Journal of Machine Learning Research, 24(54):1–34, 2023

    2023

  26. [34]

    W. Lu. LEARNING GUARANTEES FOR GRAPH CONVOLUTIONAL NETWORKS ON THE STOCHASTIC BLOCK MODEL. In International Conference on Learning Representations , 2022. URL https://openreview.net/forum?id=dpXL6lz4mOQ

    2022

  27. [35]

    Y. Ma, X. Liu, N. Shah, and J. Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations , 2022. URL https://openreview.net/forum? id=ucASPPD9GKN

    2022

  28. [36]

    Nguyen and R

    M.-T. Nguyen and R. Couillet. Asymptotic bayes risk of semi-supervised multitask learning on gaussian mixture. In International Conference on Artificial Intelligence and Statistics , pages 5063–5078. PMLR, 2023

    2023

  29. [37]

    Oono and T

    K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classifica- tion. arXiv preprint arXiv:1905.10947 , 2019

    1905 arXiv

  30. [38]

    Oymak and T

    S. Oymak and T. Cihad Gulcu. A theoretical characterization of semi-supervised learning with self- training for gaussian mixture models. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , volume...

    2021

  31. [39]

    K. J. Ryan and M. V. Culp. On semi-supervised linear regression in covariate shift problems. The Journal of Machine Learning Research , 16(1):3183–3217, 2015

    2015

  32. [40]

    Shchur, M

    O. Shchur, M. Mumme, A. Bojchevski, and S. G¨ unnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 , 2018

    2018 arXiv

  33. [41]

    C. Shi, L. Pan, H. Hu, and I. Dokmani´ c. Homophily modulates double descent generalization in graph convolution networks. Proceedings of the National Academy of Sciences , 121(8):e2309504121, 2024

    2024

  34. [42]

    Tang and Y

    H. Tang and Y. Liu. Towards understanding generalization of graph neural networks. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machi...

    2023

  35. [43]

    Tony Cai and Z

    T. Tony Cai and Z. Guo. Semisupervised inference for explained variance in high dimensional linear regression and its applications. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(2):391–419, 2020

    2020

  36. [44]

    Vershynin

    R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science . Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018

    2018

  37. [45]

    H.-X. Wang. Information-theoretic limits and strong consistency on binary non-uniform hypergraph stochastic block models. arXiv preprint arXiv:2306.06845 , 2023

    2023

  38. [46]

    R. Wei, H. Yin, J. Jia, A. R. Benson, and P. Li. Understanding non-linearity in graph neural networks from the bayesian-inference perspective. Advances in Neural Information Processing Systems, 35:34024– 34038, 2022

    2022

  39. [47]

    F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning , pages 6861–6871. PMLR, 2019

    2019

  40. [48]

    X. Wu, Z. Chen, W. Wang, and A. Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. arXiv preprint arXiv:2212.10701 , 2022

    2022 arXiv

  41. [49]

    Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning , pages 40–48. PMLR, 2016

    2016

  42. [50]

    Zhu and P

    H. Zhu and P. Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=CYO5T-YjWZV. 15 Appendix A. Information-theoretic limits In this section, we will provide the proofs for Theorem 3.2 and...

    2021

  43. [2004]

    Springer, 2004

    Proceedings 17, pages 624–638. Springer, 2004

    2004

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.