- 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
-
The paper addresses a meaningful problem by examining the role of message-passing structures in GNN generalization.
-
The paper provides a clear theoretical analysis and proposes a regularization method motivated by its findings.
-
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 (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 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 (, pp) under training-time threshold-crossing interventions across seven datasets.
| Model | Cora | CiteSeer | PubMed | CS | Physics | Computers | Photo |
|---|---|---|---|---|---|---|---|
| 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 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 baseline and with -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 ).
| Backbone | Setting | ES | FR | PTBR | RU | TW | Average |
|---|---|---|---|---|---|---|---|
| GCN | 66.770 | 65.236 | 65.280 | 57.577 | 62.132 | 63.399 | |
| GCN | -reg | 66.172 | 63.171 | 64.868 | 55.955 | 60.138 | 62.061 |
| GCN | SER | 67.337 | 65.093 | 66.288 | 57.207 | 62.327 | 63.650 |
| GAT | 66.615 | 65.546 | 66.217 | 57.387 | 58.616 | 62.876 | |
| GAT | -reg | 66.672 | 65.665 | 66.351 | 57.437 | 58.738 | 62.973 |
| GAT | SER | 66.578 | 65.569 | 66.474 | 57.380 | 59.023 | 63.005 |
| GT | 67.830 | 63.272 | 66.357 | 56.663 | 59.428 | 62.710 | |
| GT | -reg | 67.837 | 63.276 | 66.370 | 56.668 | 59.433 | 62.717 |
| GT | SER | 67.884 | 63.299 | 66.309 | 56.774 | 59.939 | 62.841 |
Table 2. Performance comparison on Facebook-100 (accuracy in %).
| Backbone | Setting | Penn94 | Brown11 | Texas80 | Average |
|---|---|---|---|---|---|
| GCN | 50.693 | 51.267 | 49.201 | 50.387 | |
| GCN | -reg | 51.431 | 53.243 | 50.195 | 51.623 |
| GCN | SER | 50.893 | 53.470 | 50.741 | 51.701 |
| GAT | 52.368 | 49.574 | 48.025 | 49.989 | |
| GAT | -reg | 52.404 | 49.501 | 48.154 | 50.020 |
| GAT | SER | 52.475 | 49.535 | 47.799 | 49.936 |
| GT | 51.913 | 55.006 | 50.666 | 52.528 | |
| GT | -reg | 51.964 | 54.843 | 50.674 | 52.494 |
| GT | SER | 52.016 | 55.748 | 50.574 | 52.779 |
Table 3. Performance comparison on WebKB (accuracy in %).
| Backbone | Setting | Cornell | Texas | Wisconsin | Average |
|---|---|---|---|---|---|
| GCN | 77.377 | 80.437 | 79.442 | 79.085 | |
| GCN | -reg | 77.705 | 79.781 | 80.080 | 79.189 |
| GCN | SER | 77.923 | 80.984 | 80.717 | 79.875 |
| GAT | 49.180 | 62.732 | 59.327 | 57.080 | |
| GAT | -reg | 54.426 | 62.404 | 57.928 | 58.253 |
| GAT | SER | 49.836 | 63.169 | 59.681 | 57.562 |
| GT | 76.066 | 80.765 | 80.717 | 79.183 | |
| GT | -reg | 75.082 | 79.344 | 81.093 | 78.506 |
| GT | SER | 77.158 | 81.093 | 82.186 | 80.146 |
Table 4. Performance comparison on Airport (accuracy in %).
| Backbone | Setting | USA | Brazil | Europe | Average |
|---|---|---|---|---|---|
| GCN | 49.126 | 58.168 | 42.356 | 49.883 | |
| GCN | -reg | 53.647 | 66.718 | 48.371 | 56.245 |
| GCN | SER | 54.185 | 66.412 | 49.023 | 56.540 |
| GAT | 40.723 | 43.511 | 32.481 | 38.905 | |
| GAT | -reg | 41.950 | 43.969 | 32.581 | 39.500 |
| GAT | SER | 41.277 | 44.475 | 32.882 | 39.545 |
| GT | 55.782 | 51.603 | 46.366 | 51.250 | |
| GT | -reg | 54.908 | 54.198 | 46.466 | 51.857 |
| GT | SER | 56.387 | 54.351 | 47.970 | 52.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.
[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≥1 and 1≤r≤q and any B,R1,R2>0, there exists a fixed graph on n=2q nodes and a two-layer ReLU hypothesis class F satisfying Theorem 1, with η(1)=η(2)=qr. Draw S uniformly among the m=q element subsets. For the bounded 1/2-Lipschitz loss specified below, let G(S)=supf∈F(ϵS(f)−ϵ^S(f)), κ=BR1R2qr, a=minκ,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$