How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimation

AI summary

Overview

Research area: Graph neural networks (GNNs), specifically information-theoretic analysis of GNN depth and hidden dimension selection and the phenomenon of over-squashing. The work sits at the intersection of spectral graph theory, information theory (Shannon channel capacity, maximum entropy), and constrained nonlinear optimization for architecture design.

Technical level: Advanced. The paper builds its argument through entropy bounds on matrices, a channel capacity theorem for spectral GNNs, a corollary on a "representation compression ratio," and a constrained nonlinear program. The intuitions are accessible, but the derivations and notation require comfort with probability, linear algebra, and optimization.

Scope: The paper proposes C³E (Channel Capacity Constrained Estimation), a pre-training framework that estimates hidden dimensions and propagation depth for spectral GNNs by treating the network as a communication channel whose capacity must fall inside a principled band, and validates the estimates on nine public datasets with the paper's stated set of spectral GNN models.

What This Paper Is About

GNNs are usually built with hidden dimensions and layer counts picked by heuristic search (16, 32, 64, 128, and so on), and the paper argues this leads to over-squashing — information in node representations being squashed into limited-size vectors as propagation proceeds, causing severe information loss. The goal is to replace trial-and-error with a principled, information-theoretic method that estimates how wide and how deep a spectral GNN should be before training, without changing the propagation mechanism or the graph itself.

Key Contributions

1. An information-theoretic model of information flow in spectral GNNs. The authors model a spectral GNN as a communication channel and derive a channel capacity expression that links hidden dimensions, propagation depth, propagation mechanism, and graph structure directly to the encoded representation matrix.
2. A nonlinear programming formulation for architecture selection. They formulate the choice of hidden dimensions and depth as a constrained nonlinear program, drawing on Shannon's Theorem and the principle of maximum entropy, and solve it with an off-the-shelf solver (SLSQP).
3. A representation compression ratio metric and an analysis of its dual dependence on width and depth. Corollary 2 in the paper characterizes how the compression ratio behaves as a function of the geometric mean of hidden dimensions (the threshold w̄*) and of propagation depth L, identifying distinct failure modes for deep-and-wide versus deep-and-narrow networks.
4. Empirical validation across nine public datasets. The paper reports that C³E-estimated configurations mitigate over-squashing and consistently improve representation learning relative to heuristic baselines, without altering propagation methods or graph structures, and that solutions are produced within seconds rather than hours.

Main Findings

• Over-squashing is cumulative information compression. The paper reports that the representation compression ratio θ rises monotonically as propagation depth L increases, and that model performance falls as θ grows beyond its minimum, which the authors interpret as over-squashing arising from cumulative compression in representation matrices.
• Wider hidden dimensions mitigate compression. Both the analysis and the experiments indicate that increasing hidden dimensions reduces θ and alleviates information compression; the paper also reports that an overly small θ (with relatively larger w̄) makes the encoded representation overly informative and overestimates the latent distribution's complexity, in which case increasing depth is not detrimental.
• Depth plays a conditional, nuanced role. The paper reports a fundamental balance between information compression and representation complexity: for networks with a low representation compression ratio, deeper propagation is beneficial and helps concentrate high-dimensional signals into lower dimensions; for those with a high ratio, the paper reports that it aggravates the problem.
• Architectural bottlenecks matter. The effective channel capacity φ₀ accounts for adjacent-layer constraints: large disparities between the widths of adjacent layers structurally reduce retained information, and deeper layers provide diminishing returns on capacity.
• C³E-estimated models outperform heuristic baselines. On the datasets and models reported, C³E-estimated variants (marked with ⋆) consistently improve on their heuristic counterparts. Examples from the results table include GCN on Cora rising from 0.808 to 0.837, GCN on Squirrel from 0.311 to 0.346, S²GC on Chameleon from 0.398 to 0.435, and GCN on ogbn-papers100M from 0.733 to 0.760.
• A narrow capacity band defines good performance. The paper's constraint is ln(n) ≤ φ₀ ≤ (1/η)·ln(n) with η ∈ (0, 1], and the paper reports that optimal performance is achieved when φ₀ falls inside this band, and that simply scaling up parameters does not guarantee better results.
• Entropy visualization supports the account. In the reported layer-wise entropy plots, C³E-estimated models maintain high representation entropy H(H_l) across layers, while naively stacked baselines show entropy collapsing toward zero well before the final layer. The paper also observes that the representation entropy of baselines using 16 or 64 hidden dimensions is strictly bounded by their dimensionalities.
• A concrete optimal point on Citeseer. Table 3 reports that the C³E-estimated baseline achieves its best result at θ = 0.010 with L = 4, while the plain baseline is at θ = 0.558 when L = 1 and degrades as θ increases.
• Fast estimation. C³E generates solutions in 3.7 seconds to 879.6 seconds across the reported datasets, compared with 2.45 hours to 120 hours for trial-and-error cited from Cai et al. (2021).

Methodology in Plain English

1. Treat the network as a communication channel. Rather than reasoning about graph structure alone, the authors define the entropy of a representation matrix and use the maximum entropy principle to bound how much information a spectral GNN can carry. Because spectral GNNs collapse propagation into a single matrix operator (S_l), their layered computation H_l = Δ(S_l H_{l−1} W_l) can be analyzed in closed form.
2. Derive a channel capacity formula. Theorem 1 expresses the channel capacity of a spectral GNN as a function of hidden dimensions w_{l−1}, the number of propagation layers L, the graph size n, and the variance of the propagation operator σ²_{S_l}. This makes width and depth explicit knobs in the capacity expression.
3. Define a compression metric. The representation compression ratio θ = φ / w̄ divides capacity by the geometric mean of hidden dimensions w̄, giving a per-dimension measure of how hard the representation is being squeezed. Analyzing θ gives a threshold w̄* below which increasing width reduces compression, and shows the effect of adding layers depends on whether ln(w̄) exceeds −K̄, where K̄ is the average log propagation variance.
4. Account for adjacent-layer bottlenecks. Because a narrow layer after a wide one caps information flow regardless of global capacity, the authors introduce an effective channel capacity φ₀ that penalizes sharp changes in width between neighboring layers and accounts for cumulative attenuation from earlier layers.
5. Constrain the optimization. Two conditions are imposed: capacity must be at least ln(n) so that transmission is reliable (Shannon's Theorem, using the maximum graph entropy ln(n) as a safe lower bound since the target is unknown), and capacity must not exceed (1/η)·ln(n), which uses the tunable regularizer η ∈ (0, 1] to prevent runaway compression. These two bounds form the constraint band in Eq. (12).
6. Solve. The objective (maximize theoretical channel capacity) plus the constraints from Corollary 2 and Eq. (12) form a constrained nonlinear program, solved with SLSQP. Hidden dimensions are treated as continuous and rounded afterward, and σ²_{S_l} is precomputed sparsely using population variance.
7. Evaluate. The estimated configurations are applied to GCN, APPNP, GDC_HK, GDC_PPR, SGC, S²GC, JacobiConv, GPRGNN, and ChebNetII and compared against their heuristic counterparts, using semi-supervised node classification on seven public graphs (random splits, averaged over 10 runs) and node property prediction on two large-scale graphs (public splits, averaged over 10 runs), with bold marking better average performance and underlines marking statistical significance at p < 0.05 by t-test.

Why This Matters

Impact on research. The paper reframes over-squashing as measurable information loss in the learned representation matrix rather than something inferred indirectly from graph topology, and it argues that existing remedies focused on rewiring graphs or modifying features overlook architecture. Prior theory cited in the paper (Loukas; Di Giovanni et al.) showed that width and depth matter but provided no method to obtain suitable values; this work supplies a pre-training procedure to do so. It also provides a diagnostic (the representation compression ratio and layer-wise entropy) that other researchers can use to compare propagation mechanisms.

Real-world applications:

• Citation and academic knowledge graphs — the paper evaluates on ogbn-arxiv and ogbn-papers100M, which are citation networks used for topic and venue prediction.
• E-commerce and product co-purchase graphs — the AmazonPhoto and AmazonComputers datasets used in the paper are co-purchase networks.
• Web and social networks — the Chameleon and Squirrel datasets are Wikipedia-based networks, representative of entity and relation graphs.
• General node property prediction at scale — ogbn-papers100M contains 111,059,956 nodes, 128 features, 1,615,685,872 edges and 172 classes, illustrating the regime where architecture choices become practically expensive to tune by hand.

Industry relevance. Choosing width and depth is one of the most expensive parts of deploying a GNN, because a full sweep can consume large compute budgets. C³E reports producing solutions in seconds to minutes (3.7 seconds to 879.6 seconds) instead of the 2.45 to 120 hours cited for trial-and-error, and the code is released at https://github.com/pixelhero98/C3E. If the reported improvements hold in deployment settings, the method offers a cheap, principled step in an AutoML or architecture-search pipeline for graph learning.

Future Directions

• Extension beyond spectral GNNs. The framework relies on spectral models whose propagation can be collapsed into a single matrix operator. Whether it transfers to purely spatial or attention-based GNNs, whose propagation is less analytically tractable, is not addressed in the paper.
• Handling of unknown target information. Because the downstream target 𝒢′ is unknown before training, the method uses the maximum graph entropy ln(n) as a proxy lower bound; sharper or task-aware bounds could change the estimated architectures.
• Tuning and automating the regularizer η. The paper treats η as a tunable hyperparameter, reports robustness across a wide range of values in Appendix F, and notes that raising η speeds up solutions by reducing candidate solutions. Automatic selection of η remains open in the reported content.
• Transfer to other tasks and settings. The reported experiments cover semi-supervised node classification and node property prediction; whether the estimated widths and depths carry over to link prediction, graph-level tasks, heterogeneous or dynamic graphs, or inductive deployment settings is not reported.
• Refining the variance estimation. The implementation precomputes σ²_{S_l} sparsely via population variance; whether alternative estimators or per-layer refinements change the estimates is not reported.

Target Audience

Researchers and practitioners working on graph neural networks who need to decide or justify architecture choices, particularly those interested in over-squashing, over-smoothing, and information-theoretic analyses of deep networks. It is also relevant to applied machine learning engineers who train GNNs on large graphs and want a low-cost alternative to hyperparameter sweeps, and to theoretically inclined readers interested in channel capacity, maximum entropy arguments, and constrained optimization as tools for network design. Readers without a background in information theory or spectral graph methods will find the derivations demanding, though the experimental results and the compression ratio metric are interpretable on their own.

Authors’ abstract

Existing graph neural networks typically rely on heuristic choices for hidden dimensions and propagation depths, which often lead to severe information loss during propagation, known as over-squashing. To address this issue, we propose Channel Capacity Constrained Estimation (C3E), a novel framework that formulates the selection of hidden dimensions and depth as a nonlinear programming problem grounded in information theory. Through modeling spectral graph neural networks as communication channels, our approach directly connects channel capacity to hidden dimensions, propagation depth, propagation mechanism, and graph structure. Extensive experiments on nine public datasets demonstrate that hidden dimensions and depths estimated by C3E can mitigate over-squashing and consistently improve representation learning. Experimental results show that over-squashing occurs due to the cumulative compression of information in representation matrices. Furthermore, our findings show that increasing hidden dimensions indeed mitigate information compression, while the role of propagation depth is more nuanced, uncovering a fundamental balance between information compression and representation complexity.