acceptodds
Under review as a conference paper at ICLR 2027

Understanding Graph Neural Network Generalization via Message-Passing Structural Complexity

Abstract

Graph neural networks (GNNs) have become a fundamental paradigm for learning from graph-structured data. Unlike conventional neural networks, their predictions depend not only on learnable parameters but also on the graph structures involved in message passing, making their generalization particularly sensitive to structural variations. However, existing analyses of GNN generalization mainly focus on parameter complexity, while how the complexity of message-passing structures affects generalization remains insufficiently understood. To characterize this effect, we define message-passing structural complexity and derive a structure-aware generalization bound within a transductive Rademacher-complexity framework, theoretically revealing structural complexity as a fundamental factor in GNN generalization. To mitigate the effect of structural complexity on generalization, we develop a graph neural network method with structural entropy regularization, which controls message-passing structural complexity through structural entropy. We theoretically establish an upper-bound relation showing that structural entropy serves as a differentiable surrogate for cross-class information-propagation complexity, thereby enabling principled control of potentially harmful message passing. By incorporating the structural regularization term into several representative GNN architectures, experiments on benchmark datasets show that reducing the structural complexity can consistently improve GNN generalization.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Generalization, Structural Complexity

Reviews

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

This paper studies how message-passing structural complexity affects GNN generalization and derives a structure-aware generalization bound using transductive Rademacher complexity. It further proposes Structural Entropy Regularization (SER) to reduce cross-class message passing, showing improved node classification performance across several GNN architectures and datasets.

Critical strengths
  1. The paper addresses a meaningful problem by examining the role of message-passing structures in GNN generalization.

  2. The paper provides a clear theoretical analysis and proposes a regularization method motivated by its findings.

  3. The experiments cover multiple GNN architectures and datasets, showing consistent improvements over the vanilla models.

Critical weaknesses

1. The theoretical analysis does not fully establish the role of structural complexity in generalization. The paper shows that increasing structural complexity leads to a looser generalization upper bound, but this does not necessarily imply worse generalization in practice. Since the bound relies on potentially loose inequalities, it remains unclear whether structural complexity is a fundamental factor affecting generalization or simply an artifact of the theoretical derivation.

2. The experimental setting does not fully reflect the claimed structural generalization problem. The paper emphasizes that GNN generalization is sensitive to graph structure, but both the theoretical analysis and experiments focus on node classification within a fixed graph. It remains unclear whether the proposed findings hold when graph structures change, such as under graph distribution shifts or on unseen graphs. Such evaluations would better support the broader motivation of the paper.

Questions for authors

See weaknesses.

4 comments

[W1 (1/2): Structural Complexity and the Realized Generalization Gap]

We thank the reviewer for this important observation. We agree that the monotonic dependence of the upper bound on propagation support does not, by itself, imply that the realized generalization gap must increase with structural complexity. To address this concern, we provide complementary theoretical and empirical evidence. Specifically, we develop a lower-bound construction showing that the scale of the structural term can occur in the actual worst-case transductive risk gap, and conduct additional paired training interventions across different GNN architectures and datasets to examine whether changes in propagation structure affect model performance. We first present the lower-bound result in the following proposition.

Proposition R3.1. For any integers q≥1q\geq 1 and 1≤r≤q1\leq r\leq q and any B,R1,R2>0B,R_1,R_2 > 0, there exists a fixed graph on n=2qn=2q nodes and a two-layer ReLU hypothesis class F\mathcal F satisfying Theorem 1, with η(1)=η(2)=qr\eta^{(1)}=\eta^{(2)}=qr. Draw SS uniformly among the m=qm=q element subsets. For the bounded 1/21/2-Lipschitz loss specified below, let G(S)=sup⁡f∈F(ϵS(f)−ϵ^S(f))G(S)=\sup_{f\in\mathcal F}\bigl(\epsilon_S(f)-\hat\epsilon_S(f)\bigr), κ=BR1R2qr\kappa=BR_1R_2qr, a=min⁡κ,1a=\min\\{\kappa,1\\}. Then we have:

\qquad \frac{a}{384\sqrt q}\leq \mathbb E_S G(S)\leq\frac{a}{4\sqrt q}.$$ **Proof.** Take a complete bipartite graph with parts $V_L,V_R$ of size $q$. Fix $T_r\subseteq V_R$ of size $r$ before drawing $S$, and set: $$\Omega_r^{(1)}=\mathbf 1_{T_r}\mathbf 1_{V_L}^{\top}, \qquad \Omega_r^{(2)}=(\Omega_r^{(1)})^\top.$$ Each operator has $qr$ unit entries supported on graph edges. With $X=B\mathbf 1_{V_L}$ and scalar weights $|w_k|\leq R_k$, Eq. (1) gives $f=Bqr(w_1)_+(w_2)_+\mathbf 1_{V_L}$, where $(x)_+=\max\\{x,0\\}$. The attainable predictions are thus $f=t\mathbf 1_{V_L}$ for $0\leq t\leq\kappa$. Assign labels $-1$ on $V_L$ and $+1$ on $V_R$. Use $\ell(z,y)=\operatorname{clip}_{[0,1]}((1-yz)/2)$. The loss is $(1+\min\\{t,1\\})/2$ on $V_L$ and $1/2$ on $V_R$. For $Z=|S\cap V_L|-|S\cap V_R|$, the fraction of left-side nodes in $V\setminus S$ minus that in $S$ is $-Z/q$. Hence, we have: $$\epsilon_S(f)-\hat\epsilon_S(f)=-\frac{\min\\{t,1\\}Z}{2q}, \qquad G(S)=\frac{a(-Z)_+}{2q}.$$ To generate the uniform split, draw a uniform perfect matching of the $2q$ nodes and independently choose one endpoint uniformly from each pair. The resulting $q$-subset is uniform by permutation invariance. Conditional on the matching, the within-side pairs cancel in $Z$, leaving a sum of $K$ independent fair signs, where $K$ is the number of cross-side pairs. Its conditional second and fourth moments are $K$ and $3K^2-2K$. Each left-side node has probability $q/(2q-1)$ of being matched across the partition, so we have: $$\mathbb E Z^2=\frac{q^2}{2q-1}\geq\frac q2, \qquad \mathbb E Z^4\leq 3q^2.$$ For $p=\Pr(Z^2\geq q/4)$, Cauchy–Schwarz gives $q/2\leq\mathbb E Z^2\leq q/4+\sqrt{3q^2p}$, so $p\geq 1/48$. By symmetry, $\Pr(Z\leq-\sqrt q/2)\geq 1/96$, which gives the probability bound and the expectation lower bound. The expectation upper bound follows from symmetry and $\mathbb E|Z|\leq\sqrt{\mathbb E Z^2}\leq\sqrt q$. $\square$

[W1 (2/2): Empirical Evidence]

Empirical evidence. Figure 1 reports the absolute train–test classification-error gap as the number of propagation relations varies. To further examine whether changes in propagation around the effective-edge threshold can affect model performance, we conducted additional paired training interventions across three GNN architectures (GCN, GAT, and GT) on seven datasets. We identified target events where the baseline and full SER training trajectories placed the same propagation coefficient on opposite sides of the threshold at the same training step. During training, the targeted intervention kept matched target coefficients on the baseline side of the threshold, while the control applied perturbations of similar magnitude and direction to other relations. Both arms were evaluated with the same frozen full-SER inference operator for each seed. We report Δacc=Accmatched−Accblocked\Delta_{\mathrm{acc}}=\mathrm{Acc}_{\mathrm{matched}}-\mathrm{Acc}_{\mathrm{blocked}} in percentage points (pp), so a positive difference indicates lower accuracy under targeted blocking. The experimental results are summarized in the following table. The results show that, in most model–dataset settings, preventing selected training-time threshold crossings reduces test accuracy relative to the matched control. This provides complementary evidence that changes in propagation around the effective-edge threshold can affect predictive performance.

Table 1. Paired test accuracy differences (Δacc\Delta_{\mathrm{acc}}, pp) under training-time threshold-crossing interventions across seven datasets.

ModelCoraCiteSeerPubMedCSPhysicsComputersPhoto
GCN+0.001+0.120+0.030+0.0043+0.001+0.028+0.097
GAT+0.050+0.080+0.020+0.0045-0.003+0.014+0.290
GT+0.080+0.211+0.310+0.389+1.133+2.947+0.649

Note. Entries report the mean paired test accuracy difference Δacc=Accmatched−Accblocked\Delta_{\mathrm{acc}}=\mathrm{Acc}_{\mathrm{matched}}-\mathrm{Acc}_{\mathrm{blocked}} in percentage points (pp). Within each pair, both arms use the same frozen full-SER inference operator. Positive values indicate lower test accuracy under targeted blocking.

[W2: Generalization Under Graph Distribution Shifts and on Unseen Graphs]

We thank the reviewer for raising this important concern. We agree that the original theoretical analysis and experiments primarily focus on node classification within a fixed graph, and that Theorem 1 does not directly establish generalization guarantees across different graph distributions. To examine the empirical transferability of SER beyond this setting, we have supplemented our evaluation with cross-graph experiments on Twitch-Explicit, Facebook-100, WebKB, and Airport, where the target graphs are held out from both training and validation.

For Twitch-Explicit and Facebook-100, we use the graph splits and metrics of Wu et al. [1]. On Twitch-Explicit, we train on DE, validate on ENGB, and test on five held-out regional graphs. On Facebook-100, we train on Johns Hopkins55, Caltech36, and Amherst41, validate on Cornell5 and Yale4, and test on three held-out school graphs. The Facebook-100 feature encoding is fitted on the source graphs, and accuracy is computed on nodes with known labels. For WebKB and Airport, we use leave-one-graph-out evaluation, rotating the target among Cornell, Texas, and Wisconsin for WebKB and among USA, Brazil, and Europe for Airport. Within each fold, we train on the other two graphs and reserve approximately 20% of the labeled nodes in each source graph for validation using a fixed class-stratified split. We compare SER with its λ=0\lambda=0 baseline and with L0L_0-reg using ten paired seeds per dataset and backbone. For each seed and regularization coefficient, the checkpoint is selected based on validation performance. We then select a single SER coefficient for each dataset and backbone based on the mean validation performance across seeds, and apply it consistently to all held-out target graphs. All model parameters are frozen during target-graph evaluation, and the average test performance is computed by equally weighting the target graphs. The experimental results are summarized in the tables below. Bold marks the highest average for each backbone. The results show that SER improves generalization to unseen graphs in most settings, providing empirical evidence of its effectiveness under cross-domain distribution shifts.

Table 1. Performance comparison on Twitch-Explicit (ROC-AUC ×100\times 100).

BackboneSettingESFRPTBRRUTWAverage
GCNλ=0\lambda=066.77065.23665.28057.57762.13263.399
GCNL0L_0-reg66.17263.17164.86855.95560.13862.061
GCNSER67.33765.09366.28857.20762.32763.650
GATλ=0\lambda=066.61565.54666.21757.38758.61662.876
GATL0L_0-reg66.67265.66566.35157.43758.73862.973
GATSER66.57865.56966.47457.38059.02363.005
GTλ=0\lambda=067.83063.27266.35756.66359.42862.710
GTL0L_0-reg67.83763.27666.37056.66859.43362.717
GTSER67.88463.29966.30956.77459.93962.841

Table 2. Performance comparison on Facebook-100 (accuracy in %).

BackboneSettingPenn94Brown11Texas80Average
GCNλ=0\lambda=050.69351.26749.20150.387
GCNL0L_0-reg51.43153.24350.19551.623
GCNSER50.89353.47050.74151.701
GATλ=0\lambda=052.36849.57448.02549.989
GATL0L_0-reg52.40449.50148.15450.020
GATSER52.47549.53547.79949.936
GTλ=0\lambda=051.91355.00650.66652.528
GTL0L_0-reg51.96454.84350.67452.494
GTSER52.01655.74850.57452.779

Table 3. Performance comparison on WebKB (accuracy in %).

BackboneSettingCornellTexasWisconsinAverage
GCNλ=0\lambda=077.37780.43779.44279.085
GCNL0L_0-reg77.70579.78180.08079.189
GCNSER77.92380.98480.71779.875
GATλ=0\lambda=049.18062.73259.32757.080
GATL0L_0-reg54.42662.40457.92858.253
GATSER49.83663.16959.68157.562
GTλ=0\lambda=076.06680.76580.71779.183
GTL0L_0-reg75.08279.34481.09378.506
GTSER77.15881.09382.18680.146

Table 4. Performance comparison on Airport (accuracy in %).

BackboneSettingUSABrazilEuropeAverage
GCNλ=0\lambda=049.12658.16842.35649.883
GCNL0L_0-reg53.64766.71848.37156.245
GCNSER54.18566.41249.02356.540
GATλ=0\lambda=040.72343.51132.48138.905
GATL0L_0-reg41.95043.96932.58139.500
GATSER41.27744.47532.88239.545
GTλ=0\lambda=055.78251.60346.36651.250
GTL0L_0-reg54.90854.19846.46651.857
GTSER56.38754.35147.97052.903

[1] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In Proceedings of the International Conference on Learning Representations, 2022.

Thank you for the detailed rebuttal and additional results, which have largely addressed my concerns. I appreciate the authors' efforts and have raised my rating to 3.

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

This paper argues that the generalization ability of GNNs depends not only on the complexity of learnable parameters but also on the structural relations involved in message passing. The authors first derive a theoretical upper bound on the generalization gap that explicitly incorporates structural complexity. They then introduce cross-class structural complexity and propose Structural Entropy Regularization (SER) to improve node classification performance by suppressing cross-class information propagation.

Critical strengths
  1. The paper is comprehensive and well-structured, presenting a coherent progression from theoretical analysis to method development. The theoretical framework is relatively thorough, and the overall organization is clear and logical.

  2. The central insight that GNN generalization depends not only on learnable parameter complexity but also on the structural relations involved in message passing is intuitive and well aligned with the fundamental characteristics of GNNs. This perspective provides a natural motivation for investigating the role of structural complexity in GNN generalization.

Critical weaknesses
  1. Limited tightness of the generalization bound. The proposed generalization bound appears to be derived from a relatively loose relaxation of existing upper bounds. Could the authors provide a corresponding lower-bound analysis of the generalization gap to further validate the theoretical significance of structural complexity?

  2. Insufficient connection between the generalization theory and SER. The preceding theoretical analysis focuses on total structural complexity, whereas SER optimizes weighted cross-class propagation. These two quantities are not equivalent, and reducing the latter does not necessarily reduce the former. In particular, SER may not change the structural complexity defined in Theorem 1. The authors should further clarify the motivation behind the proposed optimization objective and establish a stronger theoretical connection between SER and the generalization analysis.

  3. Inconsistency between theoretical and empirical measures of structural complexity. Figure 2 uses a threshold to define the effective edge ratio and reports a reduction in the number of effective edges. However, is the thresholded effective edge count used in the experiments equivalent to the exact number of nonzero entries used to define structural complexity in Theorem 1? If not, the authors should clarify how the experimental observations support the theoretical analysis.

Questions for authors

See the weakness.

5 comments

[W1: Tightness of the Generalization Bound and a Corresponding Lower Bound]

We thank the reviewer for this valuable suggestion. To further examine the tightness of the proposed generalization bound, we have added a lower-bound analysis of the worst-case transductive generalization gap, as stated in the following proposition.

Proposition R2.1. For any integers q≥1q\geq 1 and 1≤r≤q1\leq r\leq q and any B,R1,R2>0B,R_1,R_2 > 0, there exists a fixed graph on n=2qn=2q nodes and a two-layer ReLU hypothesis class F\mathcal F satisfying Theorem 1, with η(1)=η(2)=qr\eta^{(1)}=\eta^{(2)}=qr. Draw SS uniformly among the m=qm=q element subsets. For the bounded 1/21/2-Lipschitz loss specified below, let G(S)=sup⁡f∈F(ϵS(f)−ϵ^S(f))G(S)=\sup_{f\in\mathcal F}\bigl(\epsilon_S(f)-\hat\epsilon_S(f)\bigr), κ=BR1R2qr\kappa=BR_1R_2qr, a=min⁡κ,1a=\min\\{\kappa,1\\}. Then we have:

\qquad \frac{a}{384\sqrt q}\leq \mathbb E_S G(S)\leq\frac{a}{4\sqrt q}.$$ **Proof.** Take a complete bipartite graph with parts $V_L,V_R$ of size $q$. Fix $T_r\subseteq V_R$ of size $r$ before drawing $S$, and set: $$\Omega_r^{(1)}=\mathbf 1_{T_r}\mathbf 1_{V_L}^{\top}, \qquad \Omega_r^{(2)}=(\Omega_r^{(1)})^\top.$$ Each operator has $qr$ unit entries supported on graph edges. With $X=B\mathbf 1_{V_L}$ and scalar weights $|w_k|\leq R_k$, Eq. (1) gives $f=Bqr(w_1)_+(w_2)_+\mathbf 1_{V_L}$, where $(x)_+=\max\\{x,0\\}$. The attainable predictions are thus $f=t\mathbf 1_{V_L}$ for $0\leq t\leq\kappa$. Assign labels $-1$ on $V_L$ and $+1$ on $V_R$. Use $\ell(z,y)=\operatorname{clip}_{[0,1]}((1-yz)/2)$. The loss is $(1+\min\\{t,1\\})/2$ on $V_L$ and $1/2$ on $V_R$. For $Z=|S\cap V_L|-|S\cap V_R|$, the fraction of left-side nodes in $V\setminus S$ minus that in $S$ is $-Z/q$. Hence, we have: $$\epsilon_S(f)-\hat\epsilon_S(f)=-\frac{\min\\{t,1\\}Z}{2q}, \qquad G(S)=\frac{a(-Z)_+}{2q}.$$ To generate the uniform split, draw a uniform perfect matching of the $2q$ nodes and independently choose one endpoint uniformly from each pair. The resulting $q$-subset is uniform by permutation invariance. Conditional on the matching, the within-side pairs cancel in $Z$, leaving a sum of $K$ independent fair signs, where $K$ is the number of cross-side pairs. Its conditional second and fourth moments are $K$ and $3K^2-2K$. Each left-side node has probability $q/(2q-1)$ of being matched across the partition, so we have: $$\mathbb E Z^2=\frac{q^2}{2q-1}\geq\frac q2, \qquad \mathbb E Z^4\leq 3q^2.$$ For $p=\Pr(Z^2\geq q/4)$, Cauchy–Schwarz gives $q/2\leq\mathbb E Z^2\leq q/4+\sqrt{3q^2p}$, so $p\geq 1/48$. By symmetry, $\Pr(Z\leq-\sqrt q/2)\geq 1/96$, which gives the probability bound and the expectation lower bound. The expectation upper bound follows from symmetry and $\mathbb E|Z|\leq\sqrt{\mathbb E Z^2}\leq\sqrt q$. $\square$ **Relation to Theorem 1.** Both operators are rank one, with $\\|\Omega_r^{(k)}\\|_2=\\|\Omega_r^{(k)}\\|_F=\sqrt{\eta^{(k)}}$. The norm-to-support relaxation is therefore exact for these operators. With $L=1/2$ and $n=2q$, $m=q$, the structural term in Eq. (3) is: $$LR_1R_2B\sqrt{\frac{2n}{m(n-m)}}\sqrt{\eta^{(1)}\eta^{(2)}} =\frac{\kappa}{\sqrt q}.$$ For $\kappa\leq 1$, the lower bound matches the order of this term. Thus, the structural-complexity term is attainable up to constant factors for the worst-case generalization gap in this fixed, unnormalized family. **[W3: Thresholded Edge Counts in Figure 2 and Exact Support in Theorem 1]** We thank the reviewer for raising this important question. The thresholded effective-edge definition used in Figure 2 follows the convention introduced in Section 3.4, which characterizes structural complexity through effective propagation support rather than exact nonzero support. For GCN, although the normalized adjacency matrix $\hat A$ is fixed by the input graph, SER introduces learnable edge masks $M^{(k)}$ to adjust propagation weights, yielding $\Omega^{(k)}=M^{(k)}\odot\hat A$. Since the sigmoid masks are strictly positive, this adjustment does not change the exact support of $\Omega^{(k)}$. We therefore follow the threshold-based definition in Section 3.4 to measure effective propagation relations. For GAT and GT, thresholding the learned attention coefficients directly follows the same effective-support convention. Figure 2 thus provides empirical evidence that SER reduces the fraction of relations passing the threshold in the evaluated models, rather than directly demonstrating a reduction in the exact nonzero support defined in Theorem 1.

[W2 (1/3): Connection Between SER and Total Structural Complexity]

We thank the reviewer for raising this important concern. We agree that the original manuscript did not sufficiently establish the theoretical connection between the SER objective and the generalization analysis. To address this gap, we have developed a stronger theoretical connection through thresholded propagation support. Specifically, we establish a verifiable sufficient condition under which SER reduces both cross-class and total thresholded structural complexity, and further show how this reduction translates into a smaller complexity penalty in the generalization bound, thereby establishing a theoretical connection between SER and model generalization under the stated assumptions. We additionally provide numerical evaluations to examine how SER training affects the complete risk upper bound. We elaborate on the motivation behind the SER objective and the additional theoretical and numerical results below.

In homophilous node classification, cross-class propagation can introduce potentially harmful messages between nodes belonging to different classes. SER therefore aims to suppress cross-class propagation by minimizing the structural-entropy objective. Theorem 2 provides a theoretical motivation for this choice by establishing the pointwise relation ηcross(k)≤ξ(k)LSE(k)\eta_{\mathrm{cross}}^{(k)}\leq \xi^{(k)}\mathcal L_{\mathrm{SE}}^{(k)}. Thus, structural entropy serves as a surrogate for cross-class structural complexity. To further establish the connection between cross-class and total structural complexity, we provide the following proposition. For GCN, although the original normalized adjacency matrix A^\hat{A} is fixed, SER introduces learnable edge masks M(k)M^{(k)} and defines the propagation weights as Ω(k)=M(k)⊙A^\Omega^{(k)}=M^{(k)}\odot\hat{A}. For GAT and GT, the propagation weights are given by the corresponding learned attention coefficients. Therefore, we use a common threshold τ\tau to define effective propagation relations, enabling a unified threshold-based structural-complexity analysis across different GNN architectures.

Proposition R2.2. Consider a layer and head of two trained models, indexed by t∈0,λt\in\\{0,\lambda\\}, with a common candidate relation set E\mathcal E, a common threshold τ>0\tau > 0, and row-probability assignments PtP_t. Let ωt,e\omega_{t,e} be the actual propagation weight of e=(v,u)e=(v,u), and define St=e∈E:ωt,e≥τS_t=\\{e\in\mathcal E:\omega_{t,e}\ge\tau\\}, st(e)=Pt,v⊤Pt,us_t(e)=P_{t,v}^{\top}P_{t,u}, C(S,P)=∑(v,u)∈S(1−Pv⊤Pu)C(S,P)=\sum_{(v,u)\in S}(1-P_v^\top P_u). Write Nt=∣St∣N_t=|S_t|, Ct=C(St,Pt)C_t=C(S_t,P_t), and It=Nt−CtI_t=N_t-C_t for total, cross-class, and within-class threshold complexity. With D=S0∖SλD=S_0\setminus S_\lambda, A=Sλ∖S0A=S_\lambda\setminus S_0, and R=S0∩SλR=S_0\cap S_\lambda, define WD=∑e∈D(1−s0(e))W_D=\sum_{e\in D}(1-s_0(e)), EP=∑e∈R[s0(e)−sλ(e)]+E_P=\sum_{e\in R}[s_0(e)-s_\lambda(e)]_+. If WD>∣A∣+EPW_D > |A|+E_P, then we have:

N_\lambda < N_0,\qquad I_\lambda-I_0 < C_0-C_\lambda,\qquad C(S_\lambda,P_0) < C(S_0,P_0).$$ **Proof.** Since $D,A,R$ partition the removed, newly effective, and retained relations, respectively, $$\begin{aligned} C_0-C_\lambda &=W_D-\sum_{e\in A}(1-s_\lambda(e)) +\sum_{e\in R}(s_\lambda(e)-s_0(e))\\\\ &\ge W_D-|A|-E_P > 0. \end{aligned}$$ The inequality follows from $0\le s_t(e)\le1$ and the definition of $E_P$. Also $W_D\le |D|$, so $N_0-N_\lambda=|D|-|A|\ge W_D-|A| > 0$. The identity $N_t=I_t+C_t$ then gives $I_\lambda-I_0=(C_0-C_\lambda)-(N_0-N_\lambda) < C_0-C_\lambda$. Finally, using $P_0$ for both supports cancels the contribution of $R$, giving: $$C(S_0,P_0)-C(S_\lambda,P_0) =W_D-\sum_{e\in A}(1-s_0(e)) \ge W_D-|A| > 0.$$ $\square$

[W2 (2/3): Corollary R2.1 and the Generalization Bound]

Having established how changes in cross-class structural complexity affect total thresholded structural complexity, we further investigate how this reduction translates into the generalization analysis. We illustrate the derivation using a two-layer GAT, while analogous arguments can be developed for other GNN architectures under their corresponding assumptions. The resulting bound is formalized in the following corollary.

Corollary R2.1. Consider the two-layer GAT class of Proposition 1. Fix the graph, features, labels, candidate relations Ek\mathcal E_k for each layer, threshold τ\tau, and common norm bounds before sampling a labeled set of size mm uniformly from the nn nodes. Retain the feature bound BB, weight bounds R1,R2R_1,R_2, and 11-Lipschitz activation with σ(0)=0\sigma(0)=0. Let the loss be LL-Lipschitz with values in [0,Mℓ][0,M_\ell]. For Mk=∣Ek∣M_k=|\mathcal E_k|, define Fb=f∈FGAT:N(k)(f)≤bk,k=1,2\mathcal F_{\boldsymbol b} =\\{f\in\mathcal F_{\rm GAT}:N^{(k)}(f)\le b_k,\\ k=1,2\\}, bk∈0,…,Mkb_k\in\\{0,\ldots,M_k\\}. Let J=(M1+1)(M2+1)J=(M_1+1)(M_2+1), and set r1=τdrow,1dcol,1,r2=τM2r_1=\tau\sqrt{d_{\mathrm{row},1}d_{\mathrm{col},1}}, \qquad r_2=\tau\sqrt{M_2}, Φτ(b)=(b1+r1)(b2+r2)\Phi_\tau(\boldsymbol b)=(\sqrt{b_1}+r_1)(\sqrt{b_2}+r_2), where drow,1d_{\mathrm{row},1} and dcol,1d_{\mathrm{col},1} are the maximum row and column candidate counts in the first layer. With probability at least 1−δ1-\delta over the labeled set, simultaneously for all budgets b\boldsymbol b and all f∈Fbf\in\mathcal F_{\boldsymbol b}:

\le LR_1R_2Bn\sqrt{\frac{2}{m(n-m)}}\\,\Phi_\tau(\boldsymbol b) +\mathcal C(\delta/J),$$ where $\epsilon$ is the risk on the complement of the labeled set and $\mathcal C$ is the concentration term in the transductive risk inequality used in Lemma 1. Consequently, under the same positive complexity coefficient and confidence term, the complexity penalty is strictly smaller for $f_\lambda$ whenever $\Phi_\tau\bigl(N^{(1)}(f_\lambda),N^{(2)}(f_\lambda)\bigr) < \Phi_\tau\bigl(N^{(1)}(f_0),N^{(2)}(f_0)\bigr)$. **Proof.** For $f\in\mathcal F_{\boldsymbol b}$, decompose each attention matrix as $A_f^{(k)}=\bar A_f^{(k)}+E_f^{(k)}$, with $\bar A_f^{(k)}$ retaining the entries at or above $\tau$. Since the attention coefficients lie in $[0,1]$, $\\|\bar A_f^{(k)}\\|_F\le\sqrt{b_k}$. Each entry of $E_f^{(k)}$ is below $\tau$. The row and column sum bounds give $\\|E_f^{(1)}\\|_2\le r_1$, and summing the squares of the residual entries gives $\\|E_f^{(2)}\\|_F\le r_2$. Therefore $\\|A_f^{(1)}\\|_2\le\sqrt{b_1}+r_1$ and $\\|A_f^{(2)}\\|_F\le\sqrt{b_2}+r_2$. Eqs. (30)–(35) in the proof of Proposition 1 bound the loss-class transductive Rademacher complexity by: $$LR_1R_2Bn\sqrt{\frac{2}{m(n-m)}}\\, \sup_{f\in\mathcal F_{\boldsymbol b}} \\|A_f^{(1)}\\|_2\\|A_f^{(2)}\\|_F.$$ Substituting the two norm bounds gives the stated complexity term. To obtain a bound that holds simultaneously over all nonempty budget classes, we apply the concentration inequality used in Lemma 1 to each class with confidence parameter $\delta/J$, followed by a union bound over the $J$ budget classes. This yields the same concentration term as in Proposition 1, with $\delta$ replaced by $\delta/J$, denoted by $\mathcal C(\delta/J)$. The resulting event holds simultaneously over all budget classes, allowing the budgets to be selected according to the observed structural counts $b_k=N^{(k)}(f)$ after training. $\square$
Reviewer_pcbQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The article investigates GNN generalisation via structural complexity. The main concept is to consider in generalisation analysis not only the weight norm but also the number of "active" message passing relations used in the model. For this, the authors derive a generalisation bound (for 2-layer GNNs) that grows with the number of such active relations. They specifically discuss the instantiations for GCN, GAT and GT. Motivated by this bound, the authors introduce a regulariser that penalizes message passing between nodes of different classes (assuming homophily in the graphs). In an experimental section, the authors evaluate their approach with GCN, GAT and GT on a range of datasets, showing that the regularisation method leads to some accuracy improvements over ordinary models.

Critical strengths

The authors correctly identify a relevant (less explored) aspect of GNN research on the role of the message passing structure in generalisation bounds rather than just the weight norms. This is well motivated and the regularisation method provides a simple approach to make use of this perspective to enhance performance.

The individual theoretical results are sound and the regulariser is evaluated on a broad set of models and datasets.

Critical weaknesses

The main claims are not sufficiently backed up. This concerns two aspects of the paper:

  • The main contribution, i.e. the regulariser in section 4.3, is not shown to directly connect to the theory that precedes it. While the argument chain is reasonable, it is unclear how minimising the regularisation term has an immediate effect on the generalisation bound, since L_SE might just force edges to shift from cross to inner via changes in node predictions.
  • The experimetal evaluation does not investigate some of the claims made in the paper:
    • From the results it is not immediate that reducing structural complexity using SER improves generalisation. The observed improved accuracies might be an indicator, but are not direct experimental evidence.
    • The bounds derived in section 3 and 4 are never evaluated. Thus, it's unclear whether they are at all meaningful in practice.

Overall, while the individual parts of the paper are interesting, the paper feels disconnected and doesn't yet properly support the main claims.

Questions for authors
  • Fig 2 and 3 show that SER barely changes the number of effective edges (or cross-class edges) over vanilla. In case of GCNs there is only up to 2% reduction. However, the accuracy results according to table 1 show gains for SER. Is this difference in performance actually caused by the tiny change in effective edges?
  • In Fig 1, how is the number of effective edges varied? At least in the GCN case, where the number of effective edges should only depend on A, it is unclear to me how this number can be changed at all.
  • Is there a particular reason why the authors didn't include λ=0\lambda=0 in figure 4?
  • Can the authors elaborate more on related work and possibly compare to them? Particularly, GNN generalisation with edge subsampling (e.g. [1]) and empirical methods that remove (or down-weight) cross-class edges (e.g. [2]).

[1] Zhang, S., et al. (2023). Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks. ICLR 2023.

[2] Chatzianastasis, M., et al. (2023). Supervised Attention Using Homophily in Graph Neural Networks. ICANN 2023.

13 comments

[W1 (1/3): Connecting SER to the Generalization Bound]

We thank the reviewer for raising this important concern. We agree that the original manuscript did not sufficiently establish how minimizing the proposed regularization term translates into a reduction in the generalization bound. To address this gap, we have added experiments examining whether the reduction in cross-class propagation could merely result from changes in predicted class assignments, which reclassify existing cross-class relations as within-class ones. By evaluating both models under the same fixed ground-truth class assignments, we show that SER still reduces the aggregate cross-class propagation weight, indicating actual changes in propagation weights rather than merely an effect of class reassignment in the evaluation. Gradient ablations further quantify the incremental contribution of the direct structural gradient. More importantly, under a verifiable sufficient condition on the resulting changes in thresholded propagation support, we theoretically establish that SER reduces the total structural complexity. We further incorporate this reduction into the generalization analysis in Section 3, establishing that SER leads to a tighter structure-dependent generalization bound. The additional experimental evidence and theoretical results are detailed below.

Experiments. All experiments follow the settings of the original manuscript, with matched data splits, random seeds, and propagation parameterizations for paired comparisons. For post-hoc evaluation, we use the same ground-truth labels (Q) and candidate relations for both models, and compute GQ=∑v,uωvu1[Qv≠Qu]G_Q=\sum_{v,u}\omega_{vu}\mathbf{1}[Q_v\ne Q_u], rQ=GQ∑v,uωvur_Q=\frac{G_Q}{\sum_{v,u}\omega_{vu}}. The results are presented in the following table.

Table 1. Paired changes in cross-class propagation and test accuracy with SER.

ModelMetricCoraCiteSeerPubMedCSPhysicsComputersPhoto
GCNΔGQ\Delta G_Q-1.514-1.707-0.153127-1.973-1.483-0.086-0.104
GCNΔrQ\Delta r_Q (pp)-0.0584-0.0479-0.0007828-0.01150-0.00452-0.00086-0.00163
GCNΔ\DeltaAcc. (pp) ↑\uparrow+1.93+4.02+0.47+0.92+0.84+2.38+1.68
GATΔGQ\Delta G_Q-0.244-0.4679-5.576-20.488-44.265-6.621-16.761
GATΔrQ\Delta r_Q (pp)-0.0090-0.0141-0.0283-0.11175-0.12833-0.04815-0.2191
GATΔ\DeltaAcc. (pp) ↑\uparrow+0.46+2.23+0.65+0.66+1.14+1.73+1.93
GTΔGQ\Delta G_Q-20.213-3.107-74.8335-711.744-617.143-478.032-289.729
GTΔrQ\Delta r_Q (pp)-0.746-0.0948-0.379538-3.88231-1.78918-3.54860-3.84511
GTΔ\DeltaAcc. (pp) ↑\uparrow+2.52+4.41+0.53+2.80+2.26+4.56+1.87

Note. Each Δ\Delta is the mean paired difference between full SER and the matched λ=0\lambda=0 baseline (SER minus baseline). Differences are averaged over seeds within each split, then equally across splits. GQG_Q is the total cross-class propagation weight, and rQr_Q is its share of the total propagation weight. Both are evaluated using the same fixed ground-truth labels QQ and candidate relations for both models. Negative differences indicate lower cross-class weight or share under SER. Acc. denotes test accuracy, and pp denotes percentage points.

For the gradient ablations, we consider two variants: one blocks the gradient path from LSEL_{\mathrm{SE}} to the propagation weights Ω(k)\Omega^{(k)} while retaining the gradient path to the class assignments PP, and the other blocks the gradient path to PP while retaining the gradient path to Ω(k)\Omega^{(k)}. We report the difference in cross-class propagation ratio between full SER and each ablation, where ΔrQ\Delta r_Q is calculated by subtracting the cross-class propagation ratio of the corresponding ablation from that of full SER. Accordingly, prop\mathrm{prop} and assign\mathrm{assign} denote the two respective gradient-blocking operations.

[W1 (2/3): Gradient Ablation Results and Proposition R1.1]

Table 2. SER gradient-path ablations for cross-class propagation under fixed labels.

ModelMetricCoraCiteSeerPubMedCSPhysicsComputersPhoto
GCNΔrQprop\Delta r_Q^{\mathrm{prop}} (pp)-0.0365-0.0515-0.0005124-0.00475-0.00294-0.00009-0.00039
GCNΔrQassign\Delta r_Q^{\mathrm{assign}} (pp)-0.0334-0.0314-0.0003368-0.00857-0.00241-0.00084-0.00130
GATΔrQprop\Delta r_Q^{\mathrm{prop}} (pp)-0.0183-0.0127-0.0263-0.08521-0.02820+0.03743-0.10894
GATΔrQassign\Delta r_Q^{\mathrm{assign}} (pp)+0.000071-0.0096-0.0034-0.01289-0.14424-0.02440-0.23056
GTΔrQprop\Delta r_Q^{\mathrm{prop}} (pp)-0.193-0.0098-0.163060-2.32508-0.75977-2.74934-3.34698
GTΔrQassign\Delta r_Q^{\mathrm{assign}} (pp)-0.075-0.0189-0.396074-0.31399-0.07394-0.42886-0.07536

Note. Each entry is the mean paired difference in rQr_Q between full SER and the indicated ablation (full SER minus ablation), in percentage points (pp). The prop\mathrm{prop} ablation blocks the direct SER gradient through its structural input, and the assign\mathrm{assign} ablation blocks the SER gradient through the soft class assignments PP. Each ablation retains the other SER gradient path. The cross-class share of propagation weight rQr_Q is evaluated using the same fixed ground-truth labels QQ and candidate relations for both models. Negative values indicate a lower share under full SER.

Taken together, these results address the concern that SER may reduce cross-class propagation merely by changing predicted class assignments. In the fixed-label experiments, both models are evaluated using the same ground-truth assignments QQ. The reductions in GQG_Q and rQr_Q across all 21 model–dataset settings therefore reflect actual changes in propagation weights over the same set of ground-truth cross-class relations, rather than merely reclassifying existing relations during evaluation. The gradient ablations further show that retaining the gradient path through the propagation weights yields a lower mean rQr_Q than blocking this path in 20 settings, even when the gradient through PP is retained in both variants. Similarly, retaining the gradient through PP also yields a lower mean rQr_Q in 20 settings when the propagation-weight gradient is retained. These results indicate that both gradient pathways contribute to reducing cross-class propagation, and, importantly, that the direct gradient through the propagation weights provides an additional contribution beyond changes mediated by class assignments.

Theory. To establish a unified analysis across different GNN architectures, for GCN, although the original normalized adjacency matrix A^\hat{A} is fixed, SER introduces learnable edge masks M(k)M^{(k)} and defines the propagation weights as Ω(k)=M(k)⊙A^\Omega^{(k)}=M^{(k)}\odot \hat{A}. For GAT and GT, the propagation weights are given by the corresponding learned attention coefficients. We use a common threshold τ\tau to define effective propagation relations for structural-complexity analysis.

Proposition R1.1. Consider a layer and head of two trained models, indexed by t∈0,λt\in\\{0,\lambda\\}, with a common candidate relation set E\mathcal E, a common threshold τ>0\tau > 0, and row-probability assignments PtP_t. Let ωt,e\omega_{t,e} be the actual propagation weight of e=(v,u)e=(v,u), and define St=e∈E:ωt,e≥τS_t=\\{e\in\mathcal E:\omega_{t,e}\ge\tau\\}, st(e)=Pt,v⊤Pt,us_t(e)=P_{t,v}^{\top}P_{t,u}, C(S,P)=∑(v,u)∈S(1−Pv⊤Pu)C(S,P)=\sum_{(v,u)\in S}(1-P_v^\top P_u). Write Nt=∣St∣N_t=|S_t|, Ct=C(St,Pt)C_t=C(S_t,P_t), and It=Nt−CtI_t=N_t-C_t for total, cross-class, and within-class threshold complexity. With D=S0∖SλD=S_0\setminus S_\lambda, A=Sλ∖S0A=S_\lambda\setminus S_0, and R=S0∩SλR=S_0\cap S_\lambda, define WD=∑e∈D(1−s0(e))W_D=\sum_{e\in D}(1-s_0(e)), EP=∑e∈R[s0(e)−sλ(e)]+E_P=\sum_{e\in R}[s_0(e)-s_\lambda(e)]_+. If WD>∣A∣+EPW_D > |A|+E_P, then we have:

N_\lambda < N_0,\qquad I_\lambda-I_0 < C_0-C_\lambda,\qquad C(S_\lambda,P_0) < C(S_0,P_0).$$ **Proof.** Since $D,A,R$ partition the removed, newly effective, and retained relations, respectively, $$\begin{aligned} C_0-C_\lambda &=W_D-\sum_{e\in A}(1-s_\lambda(e)) +\sum_{e\in R}(s_\lambda(e)-s_0(e))\\\\ &\ge W_D-|A|-E_P > 0. \end{aligned}$$ The inequality follows from $0\le s_t(e)\le1$ and the definition of $E_P$. Also $W_D\le |D|$, so $N_0-N_\lambda=|D|-|A|\ge W_D-|A| > 0$. The identity $N_t=I_t+C_t$ then gives $I_\lambda-I_0=(C_0-C_\lambda)-(N_0-N_\lambda) < C_0-C_\lambda$. Finally, using $P_0$ for both supports cancels the contribution of $R$, giving: $$C(S_0,P_0)-C(S_\lambda,P_0) =W_D-\sum_{e\in A}(1-s_0(e)) \ge W_D-|A| > 0.$$ $\square$

[W1 (3/3): Corollary R1.1 and the Generalization Bound]

Having established how changes in cross-class structural complexity affect total thresholded structural complexity, we further connect this reduction to the generalization analysis. We illustrate the derivation using a two-layer GAT, while the same proof strategy can be adapted to other GNN architectures under their corresponding assumptions. The resulting bound is formalized in the following corollary.

Corollary R1.1. Consider the two-layer GAT class of Proposition 1. Fix the graph, features, labels, candidate relations Ek\mathcal E_k for each layer, threshold τ\tau, and common norm bounds before sampling a labeled set of size mm uniformly from the nn nodes. Retain the feature bound BB, weight bounds R1,R2R_1,R_2, and 11-Lipschitz activation with σ(0)=0\sigma(0)=0. Let the loss be LL-Lipschitz with values in [0,Mℓ][0,M_\ell]. For Mk=∣Ek∣M_k=|\mathcal E_k|, define Fb=f∈FGAT:N(k)(f)≤bk,k=1,2\mathcal F_{\boldsymbol b} =\\{f\in\mathcal F_{\rm GAT}:N^{(k)}(f)\le b_k,\\ k=1,2\\}, bk∈0,…,Mkb_k\in\\{0,\ldots,M_k\\}. Let J=(M1+1)(M2+1)J=(M_1+1)(M_2+1), and set r1=τdrow,1dcol,1,r2=τM2r_1=\tau\sqrt{d_{\mathrm{row},1}d_{\mathrm{col},1}}, \qquad r_2=\tau\sqrt{M_2}, Φτ(b)=(b1+r1)(b2+r2)\Phi_\tau(\boldsymbol b)=(\sqrt{b_1}+r_1)(\sqrt{b_2}+r_2), where drow,1d_{\mathrm{row},1} and dcol,1d_{\mathrm{col},1} are the maximum row and column candidate counts in the first layer. With probability at least 1−δ1-\delta over the labeled set, simultaneously for all budgets b\boldsymbol b and all f∈Fbf\in\mathcal F_{\boldsymbol b}:

\le LR_1R_2Bn\sqrt{\frac{2}{m(n-m)}}\\,\Phi_\tau(\boldsymbol b) +\mathcal C(\delta/J),$$ where $\epsilon$ is the risk on the complement of the labeled set and $\mathcal C$ is the concentration term in the transductive risk inequality used in Lemma 1. Consequently, under the same positive complexity coefficient and confidence term, the complexity penalty is strictly smaller for $f_\lambda$ whenever $\Phi_\tau\bigl(N^{(1)}(f_\lambda),N^{(2)}(f_\lambda)\bigr) < \Phi_\tau\bigl(N^{(1)}(f_0),N^{(2)}(f_0)\bigr)$. **Proof.** For $f\in\mathcal F_{\boldsymbol b}$, decompose each attention matrix as $A_f^{(k)}=\bar A_f^{(k)}+E_f^{(k)}$, with $\bar A_f^{(k)}$ retaining the entries at or above $\tau$. Since the attention coefficients lie in $[0,1]$, $\\|\bar A_f^{(k)}\\|_F\le\sqrt{b_k}$. Each entry of $E_f^{(k)}$ is below $\tau$. The row and column sum bounds give $\\|E_f^{(1)}\\|_2\le r_1$, and summing the squares of the residual entries gives $\\|E_f^{(2)}\\|_F\le r_2$. Therefore $\\|A_f^{(1)}\\|_2\le\sqrt{b_1}+r_1$ and $\\|A_f^{(2)}\\|_F\le\sqrt{b_2}+r_2$. Eqs. (30)–(35) in the proof of Proposition 1 bound the loss-class transductive Rademacher complexity by: $$LR_1R_2Bn\sqrt{\frac{2}{m(n-m)}}\\, \sup_{f\in\mathcal F_{\boldsymbol b}} \\|A_f^{(1)}\\|_2\\|A_f^{(2)}\\|_F.$$ Substituting the two norm bounds gives the stated complexity term. To obtain a bound that holds simultaneously over all nonempty budget classes, we apply the concentration inequality used in Lemma 1 to each class with confidence parameter $\delta/J$, followed by a union bound over the $J$ budget classes. This yields the same concentration term as in Proposition 1, with $\delta$ replaced by $\delta/J$, denoted by $\mathcal C(\delta/J)$. The resulting event holds simultaneously over all budget classes, allowing the budgets to be selected according to the observed structural counts $b_k=N^{(k)}(f)$ after training. $\square$ **Relation to Sections 3 and 4.** The SER objective in Eqs. (7)–(8) uses continuous weights and soft assignments. In the supplement, thresholding defines the effective relations in the actual propagation operator, with weights below $\tau$ retained in the residual terms of the bound. For a fixed operator and assignment satisfying the volume assumptions of Theorem 2, $\tau C_\tau\le G_{\mathrm{cross}}$ and Eq. (54) yield: $$C_\tau\le \frac{\operatorname{vol}(V)}{\tau\log(1/p_{\max})}L_{\mathrm{SE}}.$$ This extends the pointwise cross-class proxy to the threshold convention of Section 3.4. Proposition R1.1 then gives a paired sufficient condition under which changes in threshold support reduce both cross-class and total complexity, even allowing within-class complexity to increase. Corollary R1.1 connects the total count to the complexity penalty through simultaneous budget classes.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.