Graph neural networks (GNNs, models that compute each node's representation by repeatedly averaging information from its neighbors) are often trained on one labeled graph and deployed on another, unlabeled one: an older citation network to a newer one, or one country's social network to another's. A growing family of methods handles this shift by editing the graph itself. Some add edges from target nodes to labeled source nodes, some inject edges between nodes believed to share a class, and some explicitly smooth target representations along edges. Every one of these edits makes neighbor averaging stronger or reach further. Neighbor averaging is also the cause of over-smoothing, the well-documented tendency of GNN representations to blur together until nodes can no longer be told apart. A domain-alignment loss, which rewards source and target representations for being indistinguishable, cannot tell useful alignment apart from this kind of blurring. We suspect part of what these structural edits buy is collapse that the alignment loss mistakes for success.
This note proposes measuring that cost directly and building it into the choice of edits. Each candidate edit to the target or joint graph is scored by two quantities computed before any training: how much it reduces the source–target discrepancy, and how much it shrinks the effective rank of propagated target features. Effective rank, roughly the number of independent directions the representations still occupy, is the measure the over-smoothing literature now recommends. Edits are then selected under a fixed rank budget. The claim is falsifiable and practical. If existing structural adaptation methods lose effective rank as depth grows or as edit strength grows, a training-free rank-budgeted edit selector should recover that accuracy, and it should do so at deeper backbones and on hub-heavy or sparse targets where current methods are known to struggle.
Core Claim
Structural graph adaptation and over-smoothing have so far been studied apart. In adaptation work, over-smoothing appears only as a local nuisance to patch: CMPGNN adds cross-domain edges predicted by a link model and then adds a mutual-information loss so that target nodes are not absorbed into source clusters. TDSS deliberately minimizes the embedding differences across target neighbors and avoids collapse only through random-walk sampling. Neither paper measures representational rank, and both test only shallow backbones. On the over-smoothing side, Are we measuring oversmoothing in graph neural networks correctly? shows that Dirichlet energy, the sum of squared differences between neighboring representations, stays flat while accuracy falls. The same paper shows that effective rank tracks accuracy with an average Pearson correlation of 0.91, but it never looks at transfer.
Our claim has three parts. First, the structural edits used in adaptation measurably lower the effective rank of target representations, and this loss explains a share of the failures at depth, on sparse targets, and on hub-dominated targets. Second, discrepancy losses such as Maximum Mean Discrepancy (MMD) partly reward this loss, so comparisons between adaptation methods should report discrepancy at matched rank. Third, choosing edits under an explicit rank budget, with no labels or extra parameters, closes most of the gap.
Raw rank cannot be the budget, because random noise has full rank, a limitation the rank paper itself points out. We therefore budget rank retention relative to the input features, which message passing can only lose. Let $\hat A$ be the normalized adjacency matrix of the (possibly joint) graph after a candidate edit set $E$, $X_t$ the target node features, $L$ a probe depth, $\mathrm{Erank}$ the effective rank, $D$ a source–target discrepancy, and $\rho$ a retention threshold. Edit selection then solves
$$\min_{E} \; D\big(\hat A_E^{L} X_s,\ \hat A_E^{L} X_t\big) \quad \text{s.t.} \quad \frac{\mathrm{Erank}(\hat A_E^{L} X_t)}{\mathrm{Erank}(X_t)} \ge \rho .$$
Because propagation adds no new feature directions, retention below one measures rank lost to mixing alone and is not inflated by noise.
Research Program
The work has a diagnostic stage and a method stage.
Diagnostic stage. We reproduce TDSS, CMPGNN, PSAHS (which reweights and injects intra-class edges to reach a target homophily level) and GRAPHDET (which trains an auxiliary real-versus-fake edge classifier on the target). Each runs with GCN backbones of depth 2, 4, 8 and 16. Layer by layer, we log target accuracy, numerical rank, effective rank, rank retention, Dirichlet energy and MMD.
Two predictions follow from spectral reasoning in Spectral Graph Pruning Against Over-Squashing and Over-Smoothing, which shows that edge edits move the spectral gap and the speed of mixing. Cross-domain bridging should cut graph diameter and cause collapse at shallower depth than on the target graph alone. Homophily injection should help on heterophilic targets only until retention falls below some threshold. The diagnostic also tests the gamed-metric hypothesis: within one method, does lower MMD go together with lower retention?
Method stage. We build the rank-budgeted edit selector. Candidate edits come from existing generators: CMPGNN's filtered cross-domain link candidates, PSAHS-style intra-class additions where its graph model and feature-only model agree, and deletions proposed by PROXYDELETE. We score each candidate by a first-order estimate of its effect on both terms of the objective.
The rank term uses a randomized low-rank sketch of $\hat A^{L} X_t$. Its change under single-edge edits is updated through eigenvalue perturbation, reusing PROXYDELETE's perturbation-based approach. Because that approach degrades on clustered eigenvalues, we check the estimate against exact recomputation every $k$ greedy steps.
Selection is greedy under the budget $\rho$, and $\rho$ is chosen without target labels. We take the largest drop in retention that does not change the source-validation accuracy of a source-only model. The edited graph is then handed unchanged to the downstream adaptation method, so the selector works as a front end for TDSS, CMPGNN or PSAHS rather than as a competitor to them.
Baselines
Naive reference. The do-nothing point is a source-trained GCN of each depth applied to the unedited target with no adaptation, plus the same backbone with plain MMD alignment. These show how much any structural method adds and where collapse appears without edits.
Strongest existing structural method. This is CMPGNN, which inserts link-predicted source–target edges and protects target identity with a mutual-information loss. It is the most directly relevant competitor because it is the method whose edits most aggressively shorten paths. On ACM→DBLP it reports 94.02% accuracy, and on Twitch DE→ES it reports 60.91 AUROC (CMPGNN). We run it from the same candidate-filtering code, with identical splits and an identical hyperparameter search budget (equal trials per method), at every depth. Beating it means two things. At depth 2 we must match its accuracy within seed variance on ACM→DBLP. At depth 4 and beyond, and on Twitch and Airport, the CMPGNN-candidate version of our selector must beat it by more than two seed standard deviations.
Other strong methods. TDSS reports average gains of 3.05% Micro-F1 and 2.04% Macro-F1 over prior methods on the six ArnetMiner pairs. The file gives no absolute per-pair accuracy (no reported result found on Lacuna for TDSS per-pair accuracy), so we reproduce it. PSAHS reports a 21.94% improvement on low-homophily Blog, again with no absolute value in the file. SAGA reports 55.3% on MAG China→US, and we run it from its released code f1shungry/SAGA as the MAG reference.
Ablations. Ablations isolate the key ingredient. Running the selector with the discrepancy term only (no budget) shows whether the budget matters. Running it with the rank term only reduces it to PROXYDELETE on the target and tests whether discrepancy awareness matters. Replacing effective-rank retention with Dirichlet energy as the budgeted quantity tests whether the over-smoothing literature's recommended measure is actually what helps.
Why not just…?
Why not just keep the backbone at two layers, where over-smoothing barely matters? This is the most serious threat, and the diagnostic is built to settle it. If two-layer TDSS and CMPGNN show retention near one and our selector adds nothing at depth 2, the practical claim narrows to deep or long-range settings. Two observations suggest depth is not the only route to collapse. Cross-domain edges shorten paths, so a shallow model on the joint graph reaches the way a deeper model would on the target alone. And DGSDA already reports failure from hub-driven overfitting on the small Brazil airport graph, where hubs mix nearly everything within two hops. The Airport and Twitch experiments at depth 2 are the decisive test.
Why not just add residual or initial-feature connections, the standard fix for over-smoothing? Residuals restore rank, but they do so by passing the target's raw features forward, including the domain-specific signal that adaptation tries to suppress. We expect a trade-off: higher retention but higher discrepancy. We test this by adding initial-residual connections to TDSS and CMPGNN and plotting both quantities. If the residual variants dominate on both axes, the structural selector is unnecessary, and we will report that.
Why not just add an effective-rank regularizer to the training loss? This is a credible simpler alternative. A loss-level penalty works on learned representations and needs no edit search. We run it with the same tuning budget. Our selector has two potential advantages: it is training-free, and it is applied before learning, so collapse never enters the propagation operator. But if the regularizer matches our accuracy at similar cost, the contribution reduces to the diagnostic. We would then reframe the work around the measurement result rather than defend the selector.
Why not just run PROXYDELETE on the target graph as preprocessing? It is cheap and requires no labels. On Roman-Empire it lifts GCN from about 70% to about 78% (Spectral Graph Pruning). But it only deletes edges, and it ignores the source entirely, so it cannot add the bridging edges that drive CMPGNN's gains. It appears as the rank-only ablation. If it ties the full selector, the discrepancy term is doing nothing.
Proposed Experiments
We evaluate on the ArnetMiner pairs (ACMv9, Citationv1, DBLPv7; all six directions), Twitch (DE→ES and further region pairs), BlogCatalog, the USA, Brazil and Europe Airport graphs, MAG regional transfers, and the Arxiv 1950–2007→2014–2018 time shift. Together these cover homophilic, heterophilic, hub-heavy and large sparse targets. We report Micro- and Macro-F1 (AUROC on Twitch), with five seeds per configuration. Every table carries retention, effective rank and MMD alongside accuracy. On the stochastic block model graphs used by PSAHS, with homophily swept from 0.8 to 0.1, we check whether the best $\rho$ varies with target homophily.
Three outcomes decide the proposal. The first is whether, across methods and depths, retention predicts target accuracy better than MMD does, which would extend the 0.91 correlation result to transfer. The second is whether, within a fixed method, sweeping edit strength traces a curve on which discrepancy keeps falling while accuracy falls after a retention threshold. That would be direct evidence that the alignment loss rewards collapse. The third is whether, at depths 4 to 16 and on Airport and Twitch, adding the rank-budgeted selector in front of CMPGNN and PSAHS beats both the unmodified methods and the loss-level rank regularizer. If the first two hold but the third does not, the result is still useful: a measurement standard for graph domain adaptation that separates alignment from collapse.
References
- Bridging Source and Target Domains via Link Prediction for Unsupervised Domain Adaptation on Graphs
- Smoothness Really Matters: A Simple Yet Effective Approach for Unsupervised Graph Domain Adaptation
- Are we measuring oversmoothing in graph neural networks correctly?
- Progressive Graph Structure Adjustment for Homophily Shift Adaptation
- Empowering GNNs for Domain Adaptation via Denoising Target Graph
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
- SAGA: Structural Aggregation Guided Alignment with Dynamic View and Neighborhood Order Selection for Multiview Graph Domain Adaptation
- Disentangled Graph Spectral Domain Adaptation