Population graphs are graphs in which each patient is a node carrying that patient's imaging features, and edges link patients judged to be similar. A graph neural network (GNN), a model that updates each node by averaging information from its neighbors, then predicts each patient's diagnosis. These models outperform per-patient classifiers on multi-site neuroimaging cohorts. They also carry a hidden flaw. Patients scanned on the same machine look alike, so edges built from feature similarity, or from metadata that includes acquisition site, mostly connect patients from the same scanner. Neighbor averaging then smooths along the scanner axis rather than the disease axis. When a new hospital's patients arrive, they connect mainly to each other or to the wrong source patients.
We propose to rewire the graph instead of changing the features. The rewiring keeps edges between patients who probably share a diagnosis and deliberately connect across different sites. Averaging over neighbors from many scanners then cancels scanner offsets, while each patient's own features keep their full diagnostic detail. This sidesteps the information loss that scanner-invariant feature learning is known to cause. It can also be applied at test time to an unseen hospital without retraining the diagnostic model.
Core Claim
Homophily-driven structure refinement rewrites a graph's edges so that connected nodes share labels. It has so far optimized one quantity, label homophily: the fraction of edges joining same-class nodes. In multi-site medical graphs, a second quantity matters just as much. Let $h_y$ be the fraction of edges joining patients with the same diagnosis, and $h_s$ the fraction joining patients from the same site. Let $\pi_s$ be the share of patients from site $s$, so that $\sum_s \pi_s^2$ is the value of $h_s$ expected if edges ignored site. Our claim is that a population graph should be rewired toward high $h_y$ while pushing $h_s$ down to that chance level $\sum_s \pi_s^2$.
The reason is a short calculation. Suppose a patient's feature decomposes as $x_i = \mu_{y_i} + b_{s_i} + \epsilon_i$. Here $\mu_y$ is the class signal, $b_s$ is an additive site offset with variance $\sigma_b^2$, and $\epsilon_i$ is noise. Averaging over $k$ same-class neighbors drawn from $k$ distinct, independently offset sites leaves $\mu_y$ intact and shrinks the site term's variance to $\sigma_b^2/k$. Averaging over same-site neighbors leaves it at $\sigma_b^2$ no matter how many neighbors there are.
Feature-invariance methods remove $b_s$ from every patient's representation and pay the price that Harmonization and the Worst Scanner Syndrome proves. That paper shows any invariance enforced by processing the data caps diagnostic information at the least informative scanner, $I(y,\hat y) \le \min_s I(y, x \mid s)$. Cross-site rewiring never requires a node's own embedding to be site-invariant, so this bound does not apply to it. Whether that escape is real in practice is something we test, not assume.
Relation to Prior Work
Three works define the closest territory. Progressive Graph Structure Adjustment for Homophily Shift Adaptation (PSAHS) adjusts an unlabeled target graph's edges toward a target label-homophily level. It selects reliable target nodes where a GNN and a structure-blind MLP agree, and reports a 21.94% gain on the low-homophily Blog graph. It supplies our pseudo-labeling mechanism. However, it controls only label homophily, uses adversarial representation alignment (exactly the invariance step we avoid), and has never been run on medical graphs.
Homophily Enhanced Graph Domain Adaptation separates homophilic and heterophilic signal channels and aligns each across domains. It leaves the topology fixed. It Takes a Graph to Know a Graph (REFine) rewires using a reference graph built from feature affinity and label propagation, with a guarantee that homophily rises if the reference is more homophilous. It supplies our edge add/delete step and its fast clustering-based implementation, but it is single-graph and site-blind.
The medical side motivates the work. Spectral Graph Convolutions for Population-based Disease Prediction introduced population graphs on ABIDE and ADNI with edges partly defined by acquisition site. In our terms this maximizes $h_s$ by construction. It is also evaluated transductively, with test patients inside the training graph, so it never faces an unseen site. Graph-Relational Domain Adaptation models relations among domains rather than among patients, and needs the domain graph given in advance. Fader networks for domain adaptation on fMRI shows empirically what the Worst Scanner result predicts: stronger adversarial site removal hurts autism classification more than slight removal. Finally, Adapt the Data, Not the Model motivates our deployment constraint that the validated diagnostic model stays frozen at the new hospital.
Research Program
The system has three parts.
Source graph. During training on source sites, we build a reference graph whose candidate edges come only from a site-stratified similarity. For each patient, neighbors are ranked within each other site after per-site standardization, and the top matches are taken from several different sites. REFine-style rewiring with training labels then deletes cross-class edges and adds same-class cross-site edges, until $h_y$ is high and $h_s$ sits at chance. The GNN is trained on this graph.
Target graph at test time. For an unseen target site, we receive a batch of its unlabeled patients and freeze all weights. Target patients are standardized against their own batch statistics. They are then connected only to source patients, never to each other at first, using the same stratified ranking. PSAHS-style agreement between the frozen GNN and a frozen MLP head marks reliable target nodes. For those nodes, edges to disagreeing-class source neighbors are pruned and further same-class cross-site edges are added, over a few progressive rounds. The rewiring has no learned parameters, so a hospital can run it without training infrastructure.
Analysis. We probe the calculation above directly. On real data we inject synthetic site offsets of controlled magnitude and check whether the site-term variance in aggregated embeddings falls roughly as $1/k$ in the number of distinct neighbor sites. We also measure how much site information remains in each node's own embedding, using a linear site probe. We expect it to remain high: the method is not supposed to erase site. The risk we must track is the one raised by Memorization in Graph Neural Networks: wrong pseudo-labels could produce confident but spurious homophily. We therefore log true target $h_y$, computed from held-out labels and used only for analysis, after each rewiring round.
Baselines
The naive reference point is a structure-free MLP on the same per-patient features, trained with standard empirical risk minimization and evaluated leave-one-site-out. WILDS found that plain empirical risk minimization is rarely beaten by specialized robust objectives such as IRM or CORAL, so this is a serious floor, not a strawman. The second reference is the original population-graph GCN of Spectral Graph Convolutions for Population-based Disease Prediction, with its phenotype-and-site edges, rerun under leave-one-site-out so that target patients join the graph only at test time. It reports 69.5% accuracy on ABIDE, but transductively, so that figure is not comparable to our protocol and we rerun it.
The strongest imaging-side competitor on ABIDE-II is the Fader network. Fader networks for domain adaptation on fMRI reports a leave-one-site-out ROC AUC of 0.652 for slight site elimination, against 0.541 for a ConvGRU. Beating it means exceeding 0.652 mean AUC on the same four-site protocol, without lowering the best site's AUC relative to the MLP.
The strongest graph-side competitor is PSAHS applied as published, with label-homophily adjustment plus adversarial alignment, on our population graph. HGDA is a second graph-side baseline. For both there is no reported result found on Lacuna for medical population graphs, so we run them ourselves.
All methods share the same per-patient feature extractor, the same GCN backbone where applicable, and the same random search budget over hyperparameters, tuned on held-out source sites only. Results cover five seeds.
Two ablations isolate the key ingredient. The first is site-stratified neighbor selection with no label-driven rewiring. The second is label-driven rewiring with no site constraint, which is essentially REFine/PSAHS rewiring. An oracle that rewires the target graph with true labels gives an upper bound.
Why not just…?
Why not just build the graph without the site field and standardize features per site? This is the most serious threat. It may capture much of the $h_s$ reduction for free. Our first ablation (stratified neighbors, no rewiring) is a stronger version of this baseline. If it matches the full method within seed variance on both testbeds, we will report that the gain comes from cross-site connectivity alone. The proposal then reduces to a graph-construction recommendation, which would still be a useful negative result about rewiring.
Why not just drop the graph and use an MLP? Graph homophily booster found that 23 specialized heterophily GNNs fail to beat an MLP on ACTOR, yet a plain GCN wins once the graph is rewired toward homophily. On ADNI, the population graph gave 77% against roughly 67% for a linear per-subject model (Spectral Graph Convolutions). Neither result was measured on unseen sites, which is why the MLP is our floor, and why losing to it would falsify the claim.
Why not just make features scanner-invariant with adversarial training? The Worst Scanner bound and the Fader strong-versus-slight result say this trades away diagnostic detail. We test that directly. We compare per-site AUC on the highest-quality source site, and add a confounded split in which one diagnosis is concentrated at one site. Invariance should fail on that split, while rewiring, which leaves node features untouched, should not.
Why not just use targeted augmentation such as stain jitter? On Camelyon17-WILDS, Out-of-Distribution Robustness via Targeted Augmentations raises out-of-distribution accuracy from 75.3% to 90.5%. Model-Based Domain Generalization reaches 94.8%. Augmentation needs a known physical nuisance, which exists for stain but not for fMRI site effects. We therefore treat augmentation as complementary: on Camelyon17 we apply rewiring on top of stain-jittered features and ask only whether it adds accuracy.
Proposed Experiments
Testbed 1: neuroimaging. We use ABIDE-II under the four-site leave-one-site-out protocol of the Fader study, so the 0.652 AUC is directly comparable. We also use ABIDE and ADNI under leave-one-site-out. Metrics are mean and worst-site AUC and accuracy, the true $h_y$ and $h_s$ of target edges, and the site-probe accuracy on node embeddings.
Testbed 2: histopathology. We use Camelyon17-WILDS, with patches as nodes and pretrained patch embeddings as features, which gives five hospitals with strong stain-driven site homophily. This tests whether the approach generalizes beyond fMRI, and whether it adds to the 90.5% targeted-augmentation baseline under the WILDS split.
Decisive checks. Four results settle the claim. First, the full method must beat the stratified-neighbors-only ablation; otherwise rewiring is unnecessary. Second, it must beat unconstrained label rewiring; otherwise the site term is unnecessary. Third, on the confounded split it must keep its best-site AUC while the adversarial baselines lose theirs. Fourth, in the offset-injection study, site-term variance should fall roughly as $1/k$. If true target $h_y$ drops across rewiring rounds while confidence rises, that is the pseudo-label cascade, and we would report it as the method's failure mode.
References
- Harmonization and the Worst Scanner Syndrome
- Progressive Graph Structure Adjustment for Homophily Shift Adaptation
- Homophily Enhanced Graph Domain Adaptation
- It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
- Spectral Graph Convolutions for Population-Based Disease Prediction
- Graph-Relational Domain Adaptation
- Fader networks for domain adaptation on fMRI: ABIDE-II study
- Adapt the Data, Not the Model: Input-Space Adaptation for Frozen Time-Series Predictors
- Memorization in Graph Neural Networks
- WILDS: A Benchmark of in-the-Wild Distribution Shifts
- Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning
- Out-of-Distribution Robustness via Targeted Augmentations
- Model-Based Domain Generalization