Bingheng Li, Zhikai Chen, Haoyu Han, Shenglai Zeng, Jingzhe Liu and Jiliang Tang (2025), arXiv preprint — ARXIV-2502.12608
Key takeaways
- Connected, but not linearly. For GCNs trained for node classification from different seeds or data orders, the straight line between solutions often shows a clear loss barrier: small on Cora and Citeseer, large on Coauthor-CS and Squirrel. A quadratic Bezier curve fitted as in Garipov et al. removes most of it (§3.1, Figs. 1–2). Graphs from similar domains give similar interpolation curves (Observation 2).
- The graph, not the architecture. Barriers for GCN, GraphSAGE and GAT are similar, while an MLP on the same features differs markedly (Observation 3, Fig. 4). On CSBM graphs, barriers fall as density and feature separability rise, and are highest at middling homophily, with both strongly homophilous and strongly heterophilous graphs better connected (Observation 4, Fig. 5).
- Theory and uses, stated without proofs. Theorem 3.2 bounds the barrier by layer-wise weight differences, weight norms and an effective propagation factor tied to the spectral gap; Proposition 3.5 gives a CSBM version in which the bound falls with density and with (h − ½)². Theorem 4.1 bounds the generalisation gap by the barrier. A Wasserstein-1 distance between two graphs’ interpolation-loss curves is claimed to bound the domain-adaptation gap and to correlate with it empirically (Fig. 7).
Standing in the record
Filed with the owner’s batch on mode connectivity and model merging, under
loss-landscapes (ADR-027). network-science because its explanatory
variables are graph properties (density, homophily, spectral gap, the
stochastic block model). learning-theory because it proposes a
generalisation bound in terms of the loss barrier.
Proposed, not Active. The empirical observations are plausible and
interesting; the theoretical half cannot be checked. Every proof is referred
to “Appendix” with no section, and the appendix holds only figures, settings
and datasets. §3.2 still reads “[add more experimental details here]”. The
barrier values behind Figs. 4–5 are not given as numbers.
It extends Garipov et al. (LIT-673): its central finding, non-linear connectivity, is established by fitting their quadratic Bezier curve between GNN solutions, “following Garipov et al. (2018)” (§3.1), and its loss-barrier definition is applied along their curve as well as the line. It cites Frankle et al. (LIT-654) for linear connectivity in fully connected networks, and argues from its own results that their pruning-connectivity link may not carry to heterophilous graphs.
Within the batch, it is one of three works testing connectivity outside image classifiers, with LIT-660 (diffusion and CLIP models) and LIT-677 (the ELBO of LDA). Like Zhou et al. on federated learning (LIT-666), it makes the barrier a function of data structure.