PaperlayerView exact revision on arXiv

Source-linked AI summary

Not too little, not too much: a theoretical analysis of graph (over)smoothing

Nicolas Keriven

arXiv:2205.12156v2stat.MLcs.LG

TL;DR

The paper asks how graph smoothing can be useful before oversmoothing destroys informative variation. It analyzes simplified linear GNNs with mean aggregation on latent-space random graphs and proves finite-step improvements in regression and classification. The results identify two mechanisms: selective shrinkage of feature directions and within-community aggregation before global collapse.

  • Problem

    Existing theory characterized oversmoothing in the infinite-layer limit but did not rigorously model the benefits of finite smoothing before that limit.

  • Method

    The paper studies simplified linear GNNs with mean aggregation on random graphs whose partially observed node features, labels, and graph structure depend on latent variables.

  • Results

    Finite smoothing improves learning before oversmoothing in two representative examples through faster shrinkage of non-principal directions and faster gathering of nodes within communities.

  • Takeaways & Limitations

    Mean aggregation can restore some lost information at finite depth, but continued smoothing eventually collapses node representations and predictions.

  • Takeaways & Limitations

    The theory uses simplified settings, and extending it to practical smoothing-order selection, more complex losses, and nonlinear GNNs remains open.

Abstract

from arXiv · show

We analyze graph smoothing with \emph{mean aggregation}, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject to the oversmoothing phenomenon: by performing too many rounds of MP, the node features tend to converge to a non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, it is intuitively obvious that some MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial ``finite'' smoothing and oversmoothing in the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which a finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider a latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomenon: graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.

1 Introduction

The paper studies when mean aggregation helps learning before repeated message passing causes oversmoothing. Using simplified linear GNNs and latent-space random graphs, it identifies two mechanisms behind this finite benefit.

  • Message passing and mean aggregation: Mean aggregation is studied as a classical message-passing operation that averages representations over neighboring nodes.The aggregation treats neighbors as an unordered set and can be implemented through graph operators such as the random-walk Laplacian.
  • Oversmoothing: Oversmoothing makes node features increasingly similar as message-passing depth grows, limiting the usefulness of deep GNNs.For connected graphs under mean aggregation, the infinite-step limit is constant across nodes.
  • Research gap: Existing theory largely characterized the infinite-layer limit but did not rigorously model the benefits of finite smoothing before oversmoothing.The paper frames this as a gap between showing eventual collapse and showing why some aggregation steps can improve learning.
  • Main results: The paper presents regression and classification examples where performance improves for a finite number of mean-aggregation steps before oversmoothing occurs.The introduction illustrates this behavior on Cora and Citeseer using feature visualizations and linear ridge-regression error.
  • Approach: The paper analyzes simplified linear GNNs on latent-space random graphs whose node features partially observe latent variables linked to labels and graph structure.The framework uses observed features, graph relationships, and labels within one probabilistic model.
  • Main mechanisms: Finite smoothing can improve learning through faster shrinkage of non-principal directions and faster gathering of nodes within communities.These mechanisms are analyzed respectively for regression and classification.

2 Preliminaries

The paper defines learning on partially observed graph data, smooths node features through repeated mean aggregation, and studies when smoothing improves regression risk. Its setup assumes latent-space random graphs and explicitly tracks the finite-versus-infinite smoothing trade-off.

  • Learning setup: The learning setup observes a weighted graph, node features, training labels, and held-out labels for semi-supervised prediction.Training and test nodes are represented as rows of feature and label matrices.
  • Graph smoothing: A linear GNN with k layers is equivalent to applying k rounds of mean aggregation and then learning on the smoothed features.One aggregation round multiplies the feature matrix by the degree-normalized adjacency matrix L.
  • Graph smoothing: The smoothed feature matrix is represented as Z^(k) = L^k Z, with each row containing one node’s features after k rounds.The notation separates training and test rows of the smoothed matrix.
  • Regression objective: The regression analysis uses mean-square error loss with ridge regularization and defines test risk on the smoothed features.The goal is to compare risk across smoothing orders, including no smoothing and the infinite-step limit.
  • Regression objective: The target finite-smoothing behavior is an optimal k⋆ > 0 satisfying R(k⋆) < min(R(0), R(∞)).The paper contrasts this with the common situation in which direct regression has lower risk than the fully smoothed limit.
  • Latent-space model: The graph model links latent variables, features, labels, and edge weights through a connectivity kernel, while observed features are an information-losing projection of the latent variables.The latent-space construction is idealized but intended to capture dependencies among graph structure, features, and labels.

3 Oversmoothing

The oversmoothing analysis uses the ergodic behavior of the mean-aggregation operator. As the number of steps tends to infinity, node predictions become equal and the limiting risk is generally close to label variance.

  • Infinite-step limit: For k → ∞, the stochastic mean-aggregation operator converges according to an ergodic theorem.This provides the mathematical basis for analyzing the infinite-smoothing limit.
  • Infinite-step limit: In the oversmoothing limit, the predicted labels become equal across all nodes.With weak ridge regularization, the common prediction is approximately the average training label.
  • Limiting risk: The limiting regression risk is generally R(∞) ≈ Var(y) + O(1/√n).This reflects the loss of useful node-level variation under complete smoothing.
  • Limiting risk: In many cases, direct regression on the original features outperforms the fully smoothed representation, so R(0) < R(∞).The paper then studies examples where an intermediate amount of smoothing improves on both endpoints.

4 Finite smoothing: Linear Regression

The regression analysis shows that finite mean-aggregation smoothing can improve prediction when it suppresses low-variance directions faster than high-variance ones, although this benefit depends on the data geometry and can fail under heterophily.

  • Setup: The paper models linear regression with Gaussian latent variables, partially observed node features, and a latent-space random graph.Labels are noiseless linear functions of latent variables, while observed features are projections of those variables.
  • Main result: Theorem 2 establishes that, under Assumption 1, one smoothing step improves regression performance with high probability for sufficiently small ε and sufficiently large n.The result implies an optimal finite smoothing order k⋆≥1 because unsmoothed risk is already below the infinite-smoothing risk.
  • Proof mechanism: One-step smoothing transforms the effective covariance to Σ(1) = (Id + Σ−1)−2Σ, up to finite-sample and kernel-approximation errors.The smoothed latent variables behave approximately like (Id + Σ−1)−1x, yielding the covariance Σ(1).
  • Spectral interpretation: Repeated smoothing shrinks small-eigenvalue directions faster than large-eigenvalue directions, which can remove projection noise when the regression vector aligns with principal directions.The same mechanism predicts R(k) ≈ Rreg.(Σ(k)) for repeated smoothing, although the rigorous proof becomes increasingly difficult.
  • Illustration: In the two-dimensional example with λ1 = 2 and λ2 = 1/2, empirical risk reaches a finite minimum consistent with the theoretical prediction.The example uses d = 2, p = 1, and a regression vector aligned with the leading eigenvector.
  • Failure case: When the regression direction corresponds to a low eigenvalue, smoothing can strictly worsen mean squared error because information vanishes faster than noise.This provides a simple heterophilic failure case; if all covariance eigenvalues are equal, smoothing does not help.

5 Finite smoothing: classification

The classification example uses two balanced Gaussian communities whose observed features may retain little class information. The paper proves that one or more mean-aggregation steps can improve risk before oversmoothing, because within-community variance shrinks faster than the communities converge.

  • Problem: The task uses two balanced Gaussian classes with identity covariance, latent means ±µ, and observed class separation ν = Mᵀµ.The observed problem can be difficult when M projects nearly orthogonally to µ, even if the latent separation is large.
  • Problem: Linear regression with MSE is used to illustrate smoothing, although binary cross-entropy and graph-only spectral clustering may be better suited to classification.The authors explicitly frame this as a controlled illustration rather than a preferred classification method.
  • Theoretical result: With sufficiently small ε and sufficiently large ∥µ∥ and n, there is k⋆ > 0 such that R(k⋆) < min(R(0), R(∞)).Thus finite smoothing improves over both no smoothing and the oversmoothed limit with probability 1 − ρ.
  • Risk behavior: For large projected separation ∥ν∥, the unsmoothed risk tends to 0, whereas for ∥ν∥ → 0 it tends to 1, the random-guessing value.The latter regime arises when the latent signal is weak or the observation map is nearly orthogonal to the class direction.
  • Mechanism: After one smoothing step, each community keeps its mean while its latent-feature variance is reduced to Id/4, yielding the limiting risk Rcl.(1/4).The improvement occurs because communities shrink faster than they move together.
  • Numerical illustration: Figure 3 compares latent and observed feature densities for k = 0, 1, 2 and empirical versus theoretical MSE, showing improved learning for low k.The approximation is reasonably accurate for small k, while the oversmoothing error is expected to worsen as k increases.

6 Conclusion and outlooks

The paper identifies finite smoothing benefits alongside eventual oversmoothing, while highlighting practical and theoretical extensions needed beyond its simplified setting.

  • Mean aggregation exhibits two co-existing phenomena: finite smoothing can help learning, while excessive smoothing causes oversmoothing.The paper studies these effects in simplified linear GNNs with random graphs and partially observed latent variables.
  • The identified mechanisms motivate future methods for choosing the smoothing order in practical applications.The relevant risks contain quantities that need to be estimated.
  • Extending the theory to more complex loss functions, especially classification, and nonlinear GNNs remains crucial.
  • A more general theory with more realistic random-graph models remains an open question.

Checklist

The checklist records affirmative coverage of contributions, limitations, theoretical assumptions, proofs, and reproducibility materials, with several ethics items marked not applicable.

  • The paper reports that it described its contributions and limitations.
  • The theoretical-results checklist marks the full assumptions as stated and complete proofs as included in the appendix.
  • The experimental checklist marks code, data, and reproduction instructions as included.
  • The authors report no error bars because the toy experiments have insignificantly low variance.
  • Consent, personally identifiable information, participant risks, compensation, and existing-asset licensing are marked not applicable.
  • The appendix states that the proofs combine concentration inequalities for subgaussian variables with Gaussian-distribution derivations.

A.1 Proof of Theorem 3

The proof of Theorem 3 proceeds through concentration arguments for the regression estimator and covariance quantities, then evaluates the limiting test risk.

  • The proof begins by concentrating the optimal regression coefficient estimator.
  • A subgaussian covariance-estimation inequality provides a high-probability bound used in the proof.
  • For sufficiently large n, the argument obtains a lower bound involving the minimum eigenvalue of the covariance estimate.
  • The proof applies analogous concentration to the covariance of X and then derives the test-risk limit.
  • The remaining bound uses an SVD-based inequality before a union bound concludes the proof.

A.2 Proof of Theorem 4

Theorem 4 is proved by replacing smoothed features with their regression transforms, concentrating the transformed data, and applying spectral and risk bounds.

  • The proof relies on concentration inequalities for subgaussian variables and properties of Gaussian distributions.
  • The argument bounds Gaussian-weight expectations and Lipschitz deviations to control the regression transform.
  • The proof introduces an auxiliary lemma to bound the deviation caused by ε in the regression-transform expression.
  • Theorem 4 first replaces x^(1) with ϕ_reg.(x_i) in the risk calculation, then concentrates the transformed features around their expectations.
  • Spectral concentration relates the transformed covariance to M^⊤Σ^(1)M and bounds its minimum eigenvalue.
  • The proof completes the result using further concentration bounds and the covariance quantities Σ_ϕ and Σ_ϕ,x.

B.1 Proof of Theorem 6

The proof of Theorem 6 combines community-wise concentration arguments with Gaussian norm bounds and concludes by identifying the limiting operator and test risk.

  • The proof separates training nodes into two communities, indexed by I1 and I−1, with corresponding community sizes n1 and n−1.
  • Balanced communities imply that the empirical proportion n1/ntr concentrates around 1/2 via Hoeffding’s inequality.
  • The argument applies concentration bounds separately to both communities and combines the resulting inequalities with a union bound.
  • The proof identifies ν as an eigenvector of (λ + 1)Id + νν⊤, which determines the limiting expression.
  • After deriving the limit, the proof proceeds to compute the corresponding test risk.

B.2 Proof of Theorem 7

The proof of Theorem 7 adapts earlier concentration arguments to smoothed features, establishes their limiting covariance structure, and derives the corresponding limiting estimator and risk expressions.

  • Community decomposition: The proof first analyzes balanced community samples using the same decomposition strategy as the earlier lemma.The community sizes are approximately n/2 with high probability.
  • Smoothed features: The smoothed-feature matrix is formed by replacing Z(k) with Zϕ = XϕM, whose rows are the transformed node features ϕcl.(xi).
  • Risk derivation: The proof concludes by applying analogous concentration bounds and computing the resulting risk with Gaussian-kernel estimates.
  • Covariance control: For sufficiently small ε and sufficiently large ∥µ∥ and n, the normalized covariance is close to Id/4 + νν⊤.
  • Limiting estimator: The limiting estimator is βϕ lim = (λId + Ezϕ(zϕ)⊤)−1(Eyzϕ).

C.2 Chaining and subgaussian variables

This section introduces Gaussian and subgaussian tools used in the proofs, including chaining bounds for kernel-indexed random processes.

  • Subgaussian variables: A subgaussian random variable is introduced as a foundational concentration concept for the technical arguments.
  • Chaining lemma: Lemma 6 gives a chaining concentration result for functions that are uniformly subgaussian over a metric ball.
  • Concentration proof: The proof combines generalized Hoeffding bounds with Dudley’s inequality to control the relevant random processes.
  • Gaussian-kernel application: Lemma 7 applies these ideas to iid Gaussian inputs and bounded Lipschitz kernels.
  • Applications: The resulting bounds are used for kernel averages and weighted Gaussian terms appearing in the main proofs.
Loading 2205.12156v2…