acceptodds
Under review as a conference paper at ICLR 2027

Regularization Shapes the Limits of Deep GNNs

Abstract

Depth degradation in graph neural networks (GNNs) can reflect optimization failure, poor generalization, or representation collapse. Distinguishing which mechanisms are active is necessary to determine how they should be addressed. We study this on Minesweeper, one of the few node-classification benchmarks requiring deep GNNs for high performance. We derive a simple mean-field iterative scheme that outperforms GNNs trained from scratch, establishes what is achievable, and highlights low-dimensional communication and recurrence across depth as useful inductive biases for generalization. Explicitly imposing these biases can improve deeper models, but can make training unstable and is motivated by task knowledge. Combining sufficient width with weight decay further allows an unrestricted GCN to match the gain at moderate depths, with weight decay associated with lower-rank message maps. Yet as depth increases, non-regularized models generalize poorly, while strongly regularized ones may fit poorly or train unstably. Improved performance can accompany either increases or decreases in hidden rank and Dirichlet energy, while last-layer measurements need not characterize the whole network. The limits of deep GNNs must instead be understood through the interaction of optimization, regularization, and solution selection.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, depth degradation, over-smoothing, regularization, weight decay, mean-field variational inference, learning mechanics

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_h914OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies depth degradation in GNNs using Minesweeper as a case study. The authors derive a scalar mean-field algorithm from local count constraints and use it to motivate parameter sharing and low-rank message maps. Experiments examine how these constraints, together with width and weight decay, affect fitting, generalization, and training stability.

Critical strengths
  1. I find the mean-field reference algorithm particularly valuable. It demonstrates that simple, repeated, low-dimensional message passing can support effective deep inference, providing a concrete reference for investigating why learned GNNs fall short. The convergence and stability analyses strengthen this contribution.

  2. The intervention experiments connect well to the reference algorithm. They show both improvements and limitations, including poor fitting and unstable training. The layerwise and training-time analyses also provide useful evidence that lower representation rank or Dirichlet energy does not necessarily imply worse predictive performance.

Critical weaknesses
  1. The empirical scope is limited. Most of the analysis focuses on Minesweeper, whose local count constraints directly motivate the reference algorithm and architectural interventions. The City Networks experiments provide additional depth–performance evidence, but do not establish whether the main intervention and diagnostic findings extend beyond this particular task structure.

  2. The source of the improvements is not fully isolated. Parameter sharing and low-rank constraints also change parameter count, normalization sharing, or effective regularization. In addition, using a fixed learning rate and training horizon across models leaves some uncertainty about whether the observed failures in deeper models reflect architectural limitations or optimization choices.

Questions for authors
  1. Do the benefits of parameter sharing and low-rank message maps, as well as the diagnostic findings, hold on tasks without explicit local count constraints?

  2. Which improvements remain after accounting for parameter count and effective regularization? Do the deeper models’ fitting failures and instability persist with adjusted learning rates or training schedules?

2 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer h914

We thank the reviewer for the detailed feedback. We address their concerns below and would be happy to answer additional questions if they come up.

W1/Q1. We now report a broader set of experiments on City Networks highlighting similar mechanisms at play that we also observed for Minesweeper. When the network is narrow, limiting its width already regularizes the model, so adding weight decay makes little difference to performance. At width 128, the stable rank of the final message map is about 10 on every city dataset (Fig. 17). As we increase width, this rank rises, and the best-performing runs use weight decay. For Los Angeles and Shanghai, the rank is still close to 10 in the best wide models, while the other wide models have higher ranks. For Paris, the wide models retain higher ranks even with weight decay and all runs show overfitting. As on Minesweeper, training becomes less stable as we increase network width and depth (Fig. 18). Note that we do not have a reference solution for City Networks, so we do not know what level of performance is achievable on these datasets.

W2/Q2 (matching parameters/regularization). We agree that the same weight decay coefficient can regularize the two architectures differently, as we describe in appendix E. The matched runs in Table 2 illustrate how the models behave at the same depth, width, and weight-decay setting in order to study their representation geometry. But to compare how well each architecture can perform, we sweep all three hyperparameters and select weight decay separately by validation. Particularly, the advantage of the tied rank-one GCN at 32 layers persists when we do this. At width 512, the unrestricted GCN reaches 90.9% mean test ROC–AUC with a selected coefficient of 1e-5. The tied rank-one GCN exceeds that score even with weight decay turned off (96.5%) and reaches 98.3% with its selected coefficient of 1e-4. For a similar parameter count, we can also compare to the tied GCN but with rank two (90.5% for no weight decay and 97.8% for the selected one).

W2/Q2 (better training for failing runs). We have added a study of optimization for some failing configurations in appendix G, particularly for configuration C with smaller learning rates and for depth 32 with a cosine scheduler and different initializations. With a smaller learning rate, the run succeeds but still heavily overfits. This supports our main points: 1) When training succeeds, as depth increases, regularization needs to decrease the rank of the message maps, which helps with generalization; 2) As width, depth, and weight decay increase, the runs become harder to train (but the solution is not unreachable); 3) Single representation geometry measures, including ones for over-smoothing, do not mean much when training fails.

Thank you for the rebuttal and the additional experiments. They address my main concerns, and I will keep my score.

Reviewer_Exy8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the mechanisms underlying depth degradation in GNNs, distinguishing among optimization failure, poor generalization, and over-smoothing. Using the Minesweeper node-classification benchmark, the authors construct a task-derived variational mean-field inference procedure that achieves near-perfect predictive performance even after many iterations, demonstrating that accurate deep local inference is achievable.

Critical strengths
  • Important research question and a clear distinction between depth degradation mechanisms.
  • A theoretically grounded reference solver.
  • Systematic experiments on depth, width, and regularization.
  • Clear presentation and reproducibility.
Critical weaknesses
  • The primary mechanistic findings, particularly the relationship between weight decay, low-rank message maps, and generalization, are evaluated almost exclusively on Minesweeper. Although City Networks provides an additional benchmark in Section 4.2, its experiments focus on prediction accuracy across different depths and weight-decay values. They do not examine the representation geometry or architectural restrictions that constitute the paper's central analysis.
  • The comparison between unrestricted GCNs and rank-constrained, parameter-tied architectures is informative, but the same nominal weight-decay coefficient does not necessarily imply equivalent regularization across these parameterizations.
Questions for authors
  • Increasing GCN depth improves test performance on City Networks, while weight decay appears to have relatively little effect within the evaluated range. Have the authors examined message-map stable rank, hidden effective rank, and Dirichlet energy on City Networks? Does weight decay similarly encourage low-dimensional communication, and does this relationship correlate with generalization performance?
  • Can the authors provide additional controlled experiments to distinguish whether improved generalization arises specifically from low-rank message passing or from other effects of weight decay? For example, would applying weight decay only to the message matrices (W_a), rather than both (W_a) and residual matrices (W_r), preserve the observed generalization improvements?
1 comment
AuthorsOpenReview ↗

Rebuttal for Reviewer Exy8

We thank the reviewer for the detailed feedback. We address their concerns below and would be happy to answer additional questions if they come up.

W1/Q1. We have added a broader set of experiments on City Networks highlighting similar mechanisms at play that we also observed for Minesweeper. When the network is narrow, limiting its width already regularizes the model, so adding weight decay makes little difference to performance. At width 128, the stable rank of the final message map is about 10 on every city dataset (Fig. 17). As we increase width, this rank rises, and the best-performing runs use weight decay. For Los Angeles and Shanghai, the rank is still close to 10 in the best wide models, while the other wide models have higher ranks. For Paris, the wide models retain higher ranks even with weight decay and all runs show overfitting. As on Minesweeper, training becomes less stable as we increase network width and depth (Fig. 18). Note that we do not have a reference solution for City Networks, so we do not know what level of performance is achievable on these datasets.

W2. We agree that the same weight decay coefficient can regularize the two architectures differently, as we describe in Appendix E. The matched runs in Table 2 illustrate how the models behave at the same depth, width, and weight-decay setting in order to study their representation geometry. But to compare how well each architecture can perform, we sweep all three hyperparameters and select weight decay separately by validation. Particularly, the advantage of the tied rank-one GCN at 32 layers persists when we do this. At width 512, the unrestricted GCN reaches 90.9% mean test ROC–AUC with a selected coefficient of 1e-5. The tied rank-one GCN exceeds that score even with weight decay turned off (96.5%) and reaches 98.3% with its selected coefficient of 1e-4.

Q2. In the revised manuscript, we report results in Figure 13 for regularizing only WaW_a and observe the same trends as when we regularize the full network. As weight decay increases, training performance worsens and the message-map rank gradually decreases toward 1. Generalization peaks at an intermediate value of weight decay, and this peak becomes more pronounced as depth increases.

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

The paper investigates why deep GNNs can fail to learn useful computation even when the task admits an effective iterative solution. Using Minesweeper as a case study, the authors compare learned GCNs with a reference inference algorithm and show how regularization, width, and architectural constraints shape deep-network performance. They find that weight decay and width can substantially improve unrestricted GCNs, while parameter tying and rank-one message maps can support accurate deep models. The results also show that hidden rank and Dirichlet energy alone are insufficient indicators of over-smoothing or model performance.

Critical strengths

The paper provides a useful perspective on the limitations of deep GNNs by connecting their performance to the structure of the underlying computation. It highlights the role of regularization and architecture in enabling deeper models, and challenges the use of hidden rank and Dirichlet energy as standalone indicators of over-smoothing.

Critical weaknesses
  1. The title attributes the depth limit to regularization, but the experiments don’t isolate that from trainability of the unrestricted GCN. The grid is depth {12, 16, 24, 32} × width {64, 512} × five weight-decay values on Minesweeper, with lr (0.01), dropout and BatchNorm fixed. At depth 32 and width 512, the unrestricted GCN reaches only 79.6 train AUC at wd 1e-4 and 1e-3. This is tightly consistent across seeds, and Fig. 5 shows it stuck near that level throughout training, which looks like an optimization failure or collapse rather than gradual underfitting. At the same depth, width and wd, the tied rank-one model fits (98.7 train). So the failure is not simply that wd 1e-4 makes a good solution unreachable. It depends on the parameterization and the optimization path. The abstract does name the interaction of optimization, regularization and solution selection, but the title and the “limits” framing put the weight on regularization. The only optimization evidence is a brief remark in Appendix D that larger lr destabilizes training and smaller lr did not reach comparable performance within 5000 epochs, with no numbers and no mention of warmup or initialization. City Networks doesn’t fill the gap. It uses width 128 and wd only up to 1e-4, test accuracy is almost flat across wd (e.g. 54.2/54.1/54.1 for Paris at depth 16), and no rank or message-map measurements are reported. It supports “depth helps beyond the label radius”, not “regularization sets the limit”.

  2. The explanations for why wd and the restricted models help are suggestive rather than demonstrated. Weight decay is described only as “associated” with lower-rank message maps. The untied rank-one model, which has low message rank without tying, does not consistently recover the gains. So low message rank alone is not what makes wd work, and the paper doesn’t say what else wd does. The reference-to-GCN link is one fit, for one configuration (depth 16, width 512, wd 1e-4) and at the output only. It explains 83% of the variance (60.5% for the backtracking reference). Without fits for the other configurations, such as the failing C versus the well-generalizing A, B and D, we can’t tell whether the reference explains generalization or only motivates the biases. The authors are upfront that this is not evidence about intermediate dynamics.

Questions for authors
  1. Appendix D says larger lr destabilizes training and smaller lr did not reach comparable performance. Can you report those results for the failing configurations (e.g. C: depth 32, width 512, wd 1e-4, train AUC 79.6), and also test warmup or a different initialization? If C can be made to fit, the depth ceiling is mostly about trainability and the title should say so. If not, what distinguishes C from the tied rank-one model D, which fits at the same depth and wd?

  2. Does the fitted reference explain GCN outputs better for the well-generalizing models (A, B, D) than for the failing model C? Without that comparison, it is hard to tell whether the reference explains generalization or only motivates the inductive biases.

  3. On City Networks, test accuracy is nearly flat across wd. What do you conclude from this about regularization outside Minesweeper? Could you add wd=0 and a wider range, even for one configuration? If wd matters little there, the “regularization shapes the limits” framing should be scoped to Minesweeper.

2 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer 2FAN

We thank the reviewer for the detailed feedback. We address their concerns below and would be happy to answer additional questions if they come up.

W1. We agree that good optimization is a very important part of successful deep GNNs, but it is not the focus of our work. We focus on studying what solutions the GNN tends towards, and how depth, width, and weight decay steer it. We agree that optimization failures are present and that the interplay between optimization and regularization is crucial, as we mention in the abstract and the last paragraph of section 4.3.

We have added a study of optimization for some failing configurations in appendix G, particularly for configuration C with smaller learning rates and for depth 32 with a cosine scheduler and different initializations. With a smaller learning rate, the run succeeds but still heavily overfits. This supports our main points: 1) When training succeeds, as depth increases, regularization needs to decrease the rank of the message maps, which helps with generalization; 2) As width, depth, and weight decay increase, the runs become harder to train (but the solution is not unreachable); 3) Single representation geometry measures, including ones for over-smoothing, do not mean much when training fails.

We also like to note that weight decay is just one of many forms of regularization. Architectural restrictions can also regularize a GCN by constraining which solutions it can learn. We study both because our question is what favors a simple, generalizing solution when many solutions fit the training data equally well. We are happy to clarify our use of terminology in the introduction.

W1/Q3. For City Networks, we now report a broader set of experiments highlighting similar mechanisms at play that we also observed for Minesweeper. When the network is narrow, limiting its width already regularizes the model, so adding weight decay makes little difference to performance. At width 128, the stable rank of the final message map is about 10 on every city dataset (Fig. 17). As we increase width, this rank rises, and the best-performing runs use weight decay. For Los Angeles and Shanghai, the rank is still close to 10 in the best wide models, while the other wide models have higher ranks. For Paris, the wide models retain higher ranks even with weight decay and all runs show overfitting. As on Minesweeper, training becomes less stable as we increase network width and depth (Fig. 18). Note that we do not have a reference solution for City Networks, so we do not know what level of performance is achievable on these datasets.

W2. We show in both Minesweeper and in our newly added City Networks sweeps that, out of the runs that train well, the low-rank ones are the well-generalizing ones and they are the ones with enough weight decay to be properly regularized without destabilizing training. The constrained models do not intend to isolate gains, and, as we mention in the last paragraph of section 3.2, their goal is diagnostic. There are successful solutions with low rank and parameter sharing, and these improve over the unregularized GNN.

The reference shows a landscape of solutions that the GNN can tend towards. It sets a bar for the performance that can be achieved and highlights potentially beneficial properties of some solutions. Particularly, we show that the successful GNNs have similar rank properties, and that the restrictions inspired by the reference make for successful configurations. We also fit the reference to other configurations in appendix H (please refer to Q2).

Q1. As mentioned above, we now show in appendix G different learning rates, schedulers, and initializations, and the results support our main-text conclusions.

The comparison between C and D is in the section where we study representation geometry measures. So the conclusions relate to this topic and not to generalization or fit. “Low-dimensional communication can coexist with richer hidden representations”, and “Rank and Dirichlet energy can help identify collapse-like behavior, but when this accompanies poor fitting, the failure is already apparent in training performance”. The difference between C and D is that D restricts the parameter space. This is not meant to be an isolated mechanism, as it affects both trainability and solution steering. It is a comparison of geometry measurements. We have added an explanation in the main text to better explain the goal of this comparison.

Q2. We have added a fitting experiment for the four configurations in Appendix H. The fitted reference does explain the GCN outputs better for the well-generalizing models. Particularly, the reference cannot explain a failing run if it doesn’t fit the labels, as the reference is constructed in order to explain possible interpolating solutions.

Thanks for the rebuttal and experiments. These largely resolve my concerns. I'd like to increase my score to 3.

Reviewer_c2umOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the phenomenon of depth-degradation (i.e. GNN performance decreasing as more layers are added). It focuses on the minesweeper dataset, for which it introduces a non-ML belief-propagation approach that has interesting regularization mechanisms. This reference performs well, showing that for this dataset, these constraints make sense. Those constraints are also enforced on the GNNs that are trained for comparison. The authors explore the tradeoff between width, depth and weight decay, and compare them to enforcing the rank-one and parameter recurrence constraints.

Critical strengths

The approached problem is relevant. Properly establishing the tradeoff between regularization, depth and width in GNN is an interesting question, especially if it comes with practical steps to diagnose and counter depth degradation.

The paper introduces a "non-learning" reference to act as a comparison baseline. The method is interesting since the baseline is naturally regularized by its structure (no learned parameters, low rank). The GCN trained afterwards also enforces both of those (through reusing weights every two layers, and forcing rank one through the outer product of two learned vectors). This is reinforced by theoretical and empirical results that support the approach and provide a relevant baseline for comparing against GNNs.

Critical weaknesses

Abstract

The abstract is not self-contained and is missing some key information to be read as a standalone. "Depth degradation" is mentioned but never explained (a few words would be enough). The approach is stated as a "simple mean-field iterative scheme that outperforms GNNs" which does not say much (it should be stated that it is applied to label distribution). The second half of the abstract (from "Explicitly imposing" to the end) is very general and does not bring anything other than "regularizing makes training harder but generalizes better unless there is too much of it". The abstract should be rewritten to clearly explain the motivation, problem, method (succinctly) and conclusion so that a reader can judge whether the paper is of interest to their specific work.

Related work

The related works is more of a list of name-dropping a list of papers and concepts without explaining why they are relevant to the paper at hand. Each paper should have a takeaway that motivates the current approach, rather than a vague statement. For instance: "Existing deep GNN analyses distinguish among expressivity, optimization, generalization, propagation scope, and representation collapse. Cong et al. (2021) separate expressivity, optimization, and generalization; Deng et al. (2025) model variation in propagation scope across nodes; Zhang et al. (2026a) compare energy- and rank-based measurements of over-smoothing; and Arnaiz-Rodriguez & Errica (2026) separate representation collapse from predictive performance.". This does not state how the results of those papers connect to the current one, which should appear in the main text rather than in the appendix as is currently done; otherwise, the scope and the positioning of the work remain unclear. This issue is true at different degrees for the four paragraphs of the section, which should be overhauled to properly motivate the current work.

Unclear positioning

The main goal of the paper is unclear; if the paper intends to give general diagnostics and remedies for depth degradation, then the study is arguably insufficient. Experiments are carried over a single dataset (then other experiments are run on the City dataset), and a single architecture (GCN). The results are compared to a very minesweeper-specific baseline, but the GCN results are not convincingly related to those. While GCNs and belief-propagation approaches share the same constraints, how do they align with each other in terms of update dynamics?

Regarding minesweeper in particular, "Nearly independent neighboring labels" is a strong claim for minesweeper; the labels are quite strongly dependent conditioned on the clues, and the GNNs learns that conditional distribution.

Overall, the conclusion seems to be that "there is a tradeoff between regularization and model size", with the additional result that you can learn minesweeper with a rank-one, recurrent approach, and that enforcing those constraints on a GCN works well, without any indication that this works beyond that very specific, noiseless dataset.

Paper Clarity

The paper lacks a lot of clarity, and over-relies on the appendices as "extra main paper space", making several claims that are not even understandable without reading the appendix.

  • the mean-field scheme is evoked several times in part 1 and 2 without being described. When it is finally introduced in part 3, the fact that this is the mean-field scheme is written nowhere explicitly. It should be clear from the start what the approach is doing so that the rest can be read with that information.
  • In table 1, the numbers in the first row should be explained (number of iterations?)
  • "Jointly increasing width and weight decay produces a deeper GCN": why does increasing width and WD increase depth?
  • the notion of "rank-one" message passing is evoked many times but only explained late in the experimental section.
  • Unclear sentence: "Deep GNNs can instead fail through optimization or generalization"
  • "Minesweeper is an unusual benchmark as found by Rubio-Madrigal & Burkholz (2026): simple, task-agnostic aggregated features, followed by a graph-agnostic learned MLP, match learned GNNs on most standard node classification datasets—but fall substantially behind on Minesweeper, most likely due to depth-related task dependencies": This sentence should be rewritten as it is quite ambiguous.
  • A lot of the relevant information is buried in the Appendix. While the size constraints force understandable tradeoffs, the main takeaway and ideas should be present in the main text. For instance: ** proper positioning with regards to the existing literature ** The theoretical part just lists vague principles and refers to the appendix. It should be self contained; while proofs can remain in appendix, the relevant lemmas and theorems should be written explicitly and rigorously. Otherwise this entire section provides neither insight nor definitive results. ** the dataset should be properly described in one place (features, classes, clues format, how they are treated by the GCN), especially since there is only a single benchmark for the paper. Paragraph 3 states that the features "encode neighboring mine counts", then 3.1 states xix_i indicates whether cell ii contains a mine (which is the label if I follow correctly?). ** "To compare the reference with learned predictions, we fit effective (α, β) pairs to a GCN’s output probabilities at recurring training checkpoints (Fig. 7 in the appendix)." This is not understandable without the appendix, and should either be explained in the main text or entirely in the appendix.
Questions for authors
  • What is the proper positioning of the paper? A general study of the depth degradation phenomenon or a minesweeper-specific approach?

  • What is the "local stability check" that appears several times that appears throughout the experiments?

  • What is the specific point of the mean-field scheme? Does it act as a general regularizer or is it specific to Minesweeper only? More generally, the approach is specifically tailored to a single dataset: does this generalize? If so, to which settings (heterophilic/homophilic graphs?) The rank restrictions sound like they function here specifically due to low-rank features, but what about more complex datasets?

  • What is the role of the City Networks experiments? What is the task at hand (node classification?) and what do they show beyond a depth/decay tradeoff?

5 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer c2um (1)

We thank the reviewer for the detailed feedback. We address their concerns below and would be happy to answer additional questions if they come up.

W1. Abstract clarity: We thank the reviewer for these suggestions in the abstract. We now define depth degradation in the abstract and explain that the mean-field scheme updates node label probabilities. We also added transitions to make each of our three contributions easier to identify. We welcome further suggestions on the abstract’s clarity.

W2. Related work clarity: We respectfully disagree that we have inadequately explained how our study relates to prior work. In each paragraph, we discuss the cited papers individually and then close it by explaining how they relate to our study. We chose this structure because most of these papers ask different questions than ours. For instance, the studies we cite on GNN depth and parameter tying do not examine the learning dynamics of these systems. Conversely, those on learning dynamics and late generalization do not consider graph-based tasks with deep solutions.

We devote three pages of Appendix D to prior work on depth in GNNs, explaining for each paper why its setting does not cover ours and which assumptions do not hold in our case. Including this comparison in the main text would take considerable space without necessarily advancing the argument we want to make. We have revised the wording in the main text to make this distinction clearer and marked the changes in blue. We welcome further suggestions on the clarity of this description under our current space constraints.

“{\color{blue}Our work differs from others in its study of learning dynamics and deep nonlinearities, as well as the construction of an inference solution for representation geometry to have a grounded comparison. We also use this controlled environment as a counterexample to the previously stated inability of GCNs to learn deep solutions.} A longer discussion of the relation to existing depth analyses is included in § D.”

W3.1 Goal: Our paper does not intend to give general diagnostics and remedies. It warns against prescribing general diagnostics and remedies, and gives concrete reasons to examine the interplay between optimization and generalization on a case-by-case basis. We show why a single measure of the learned representations can be insufficient to characterize a depth-related failure, why reducing network width is not enough as a regularization mechanism, and when shallower networks provide an incomplete baseline. In fact, we can precisely study these mechanisms because we construct a reference inference solution against which we can compare both the accuracy and the learned representations of our trained networks. Moreover, we have now translated our low-rank insights to the large-scale City-Networks benchmarks that also require deep GNNs (please refer to Q4).

W3.2 Alignment between GCN and iterative inference: A two-layer GCN with rank-one message maps can mirror the two rounds of the iterative reference. In the cell-to-clue round, cell ii sends its mine probability pitp_i^t to each neighboring cell jj with an observed clue. Analogously, the first GCN layer sends a scalar projection of each node’s hidden state to its graph neighbors. In the clue-to-cell round, each clue cell jj sends a count correction specific to each neighboring cell ii, which aggregates these corrections and damps its probability update. In the second GCN layer, each neighbor jj sends the same scalar hju2h_j u_2 to its neighbors, and cell ii combines the weighted sum of the scalars it receives with its residual state: zi=(∑jPij hju2)v2⊤+hiWr,2z_i= \left(\sum_j P_{ij}\,{h_j u_2}\right)v_2^\top +{h_iW_{r,2}}. Because the GCN is overparameterized, it need not learn this particular representation exactly, which is why we measure rank and endpoint matching as reference comparisons. We now fit our reference to the four GCN configurations A, B, C, and D in appendix H, which further illustrates its usefulness.

W3.3 Independence of labels: Our claim is that neighboring labels are nearly independent before conditioning on the clues. In fact, the benchmark authors report that adjusted homophily and label informativeness are close to zero. We agree that conditioning on a clue couples the labels of the cells it counts, and our reference exploits precisely this dependence.

AuthorsOpenReview ↗

Rebuttal for Reviewer c2um (2)

W3.4/Q1. Conclusions: Our work is a study of the learning dynamics of deep GNNs in a nonlinear inference setting for which we construct a reference solution. We can analyze this solution theoretically and compare its representations directly with those learned by the GNNs. This allows us to study how common measures of representation geometry, including rank, behave as we vary depth, width, and regularization. In doing so, we call into question several practices in previous benchmarks. We show why making a GNN narrow is not the appropriate way to regularize the network, and why comparing only shallow networks gives an incomplete picture of what a deep GNN can learn. We also show why a single measure of representation geometry is insufficient to conclude that over-smoothing is responsible for poor training performance, and that higher ranks in message map parameters lead to overfitting, a phenomenon we now also highlight for the larger-scale City-Networks datasets (please refer to Q4).

W4.1 Clarity: We thank the reviewer for these clarifying suggestions.

  • We have added “mean-field” to the title and opening of §3 to clarify the rule’s origin. The introduction already describes the update in words, and we think this level of detail is appropriate for both the introduction and the related work.
  • We are happy to add the word “iterations” in Table 1.
  • We have added the missing words “more successful” to clarify that jointly increasing width and weight decay improves the performance of a deeper GCN.
  • We introduce the message-map restriction in the introduction and define it in §3.2. To make the intervention clearer at first mention, instead of “we impose low-rank message maps” we now write “we impose rank-one message maps by bottlenecking the learnable weights.”
  • We have revised the sentence in the opening paragraph to a longer one: “Prior work has shown that deeper GNNs can be harder to train, and that, even when they fit the training data as well as shallower models, they can generalize more poorly”.
  • We have rephrased the sentence about Minesweeper and prior work on fixed aggregation in the introduction.

W4.2 Contents from the appendix into the main text.

  • Related work: Please refer to our response to W2.
  • Theory notation: We have copied two main result statements in section 3.1 to guide interested readers to the full analysis in appendix B.
  • Minesweeper description: We have added a description of Minesweeper in Appendix A. The reviewer is correct that xix_i in §3.1 denotes the label of cell ii, indicating whether that cell contains a mine. The node feature encodes the clue cic_i, when observed, about the number of mines in neighboring cells.
  • Fitting experiment: We are happy to further clarify the paragraph on the fitting experiment in the main text.

Q2. Local stability check: The local stability check asks whether the reference returns to a fixed point after a small perturbation of the mine probabilities. For each (α,β)(\alpha,\beta) and each split, we evaluate the Jacobian of one parallel reference update at a numerically computed fixed point. The check passes if every eigenvalue has magnitude strictly below one, which guarantees convergence back to that point from sufficiently close initial probabilities. For the GCN, this corresponds to a stability measure of the forward pass with fixed weights. We have added the following clarification in the main text:

{\color{blue}If a GCN follows the reference dynamics near an unstable fixed point, a small perturbation to an intermediate representation can grow over the remaining layers and alter the final prediction. If later layers repeatedly amplify the effect of small weight updates in earlier layers, predictions can change sharply from one training step to the next, and the training loss may fluctuate.}

AuthorsOpenReview ↗

Rebuttal for Reviewer c2um (3)

Q3: Point of the reference: The reference describes a family of interpolating solutions to Minesweeper. These solutions agree on the training labels by construction and can differ in their predictions on the remaining nodes. The reference shows that repeatedly updating a single scalar per node can yield accurate predictions. We train the GCN independently and ask whether it learns a similar representation. In particular, does weight decay favor low-rank message maps even when the architecture leaves their rank unrestricted? Based on the constructed reference, we know that for Minesweeper, scalar inference suffices. We now also observe low-rank message maps associated with good generalization on the City-Networks datasets, which are recent large-scale node-classification benchmark that require depth (please refer to Q4).

We note that, in our calculations, adjusted homophily is close to zero on Minesweeper and ranges from 0.56 to 0.62 across the City-Networks datasets. For comparison, Wiki-CS has a score of 0.58. Homophily describes the relationship between the labels of immediate neighbors, while our insights concern the nonlinear computations a GCN performs over many layers. Moreover, feature rank and message-map rank need not coincide. For instance, for our tied model with rank-one message maps, the effective rank of its hidden activations exceeds 150 in several intermediate layers (Fig. 10, top).

Q4: City Networks: We now report a broader set of experiments on City Networks (a set of four large-scale node classification benchmarks that require depth) highlighting similar mechanisms at play that we also observed for Minesweeper. When the network is narrow, limiting its width already regularizes the model, so adding weight decay makes little difference to performance. At width 128, the stable rank of the final message map is about 10 on every city dataset (Fig. 17). As we increase width, this rank rises, and the best-performing runs use weight decay. For Los Angeles and Shanghai, the rank is still close to 10 in the best wide models, while the other wide models have higher ranks. For Paris, the wide models retain higher ranks even with weight decay and all runs show overfitting. As on Minesweeper, training becomes less stable as we increase network width and depth (Fig. 18). Note that we do not have a reference solution for City Networks, so we do not know what level of performance is achievable on these datasets.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.