When a graph model trained on one network is deployed on another, the new graph often contains familiar ingredients in unfamiliar arrangements. Take a model trained on a regional academic graph with papers, authors, venues and topics. In a new region it may meet authors who publish across topics in venue combinations it never saw. Each edge type is familiar, but the small typed neighborhoods those edges form are new. Research on compositional generalization, meaning a model's ability to handle new combinations of known pieces, shows that this is exactly where neural models break. In semantic parsing, failure is predicted by whether an example contains a small sub-structure of 2–4 nodes that never appeared in training. Graph domain adaptation, the task of moving a model from a labeled source graph to an unlabeled target graph, has mostly ignored this. It treats the shift as a mismatch between whole-node embedding distributions, and it has been developed almost entirely on graphs with a single node type and a single edge type.
We propose to make each building block of a heterogeneous graph encoder domain-invariant, rather than its final output. Concretely, we would train one small adversary per relation type. Each adversary tries to tell source from target using only the messages sent along edges of that type. We would leave alone the way those messages are combined. The bet is that if every part looks the same in both domains and the combination rule is shared, then new combinations in the target are assembled from parts the classifier already understands. Alongside the method we build a diagnostic, a typed version of "unobserved local structure", to test the bet directly. Target nodes whose neighborhoods contain typed sub-structures never seen in the source should be where existing methods fail. That failure gap should shrink under part-level alignment, and it should widen under standard whole-embedding alignment.
Core Claim
Our claim has two parts, and both can be falsified. The first part is diagnostic. On heterogeneous graph transfer, target error concentrates on nodes whose local typed neighborhoods contain structures absent from the source. Global adversarial alignment makes this concentration worse than plain source training does, because it pushes away the relation-specific information those nodes need. The second part concerns the method. Making each relation's messages invariant, conditioned on the types of the two nodes the edge connects, closes most of that gap. It does so without target pseudo-labels, which is the step that existing graph adaptation methods depend on and that breaks under schema shift.
Where This Sits in Prior Work
The motivating evidence comes from compositional generalization. Unobserved Local Structures Make Compositional Generalization Hard shows that whether a test program contains a sub-graph of 2–4 nodes unseen in training predicts failure with an AUC between 78.4 and 93.3 across five parsing benchmarks. In the same work, accuracy on COVR falls from 94.6% to 19.7% when specific local structures are held out. We carry this measurement from output programs to input graph neighborhoods with typed nodes and edges, which that paper does not consider. CLOSURE and On the Compositional Generalization Gap of In-Context Learning show that high in-distribution accuracy hides this gap and that scale narrows it without closing it. These results are the reason we do not expect a bigger encoder to make the problem disappear.
The design principle that modularity enables composition comes from relational reasoning. Neural Compositional Rule Learning for Knowledge Graph Reasoning generalizes from 2–3-hop to 10-hop chains by merging relation segments recursively. CLUTRR finds that graph attention networks reach 1.0 on clean kinship reasoning while text models top out at 0.67. Both work on a single static graph with no domain shift, and the first is limited to chain rules. We take their lesson that relation-wise modules compose. We do not adopt their rule-learning machinery.
The closest existing work comes from graph domain adaptation, and it constrains our design. Joint Domain Adaptive Graph Convolutional Network aligns class-level structural fingerprints using random-walk consistency and a distribution distance, and it relies on clustering-based pseudo-labels. Its conclusion names heterogeneous networks as unaddressed. Pairwise Alignment Improves Graph Domain Adaptation splits structural shift into a change in how structure relates to labels and a change in label proportions, then corrects both through edge and loss reweighting estimated from pseudo-labels. It reports gains of over 25% relative to plain training on a country-partitioned academic graph. Both methods assume one edge type and work at the level of single edges or whole classes. Neither asks whether target nodes contain unseen combinations.
Graph-Relational Domain Adaptation is the most important foil. It shows that forcing all domains into one indistinguishable distribution causes negative transfer: DANN and ADDA do worse than source-only training on TPT-48. Its remedy is a discriminator that reconstructs a known domain graph. We share its diagnosis that uniform invariance destroys useful information. Our remedy is different. GRDA relaxes invariance across domains. We relax it across levels of the representation, demanding invariance of the parts while leaving the composite free.
Graph Augmentation for Cross Graph Domain Generalization and IDEA show that structure-aware edge editing and invariance objectives help on homogeneous graphs. Both supply baseline variants for our comparisons. Episodic Training for Domain Generalization reports that naive data pooling is a strong reference point, beaten by 3.3% on PACS, which is why we keep pooling as a baseline.
Research Program
The encoder is a relation-typed message-passing network. Each relation type $r$, for example "author writes paper" or "paper appears in venue", has its own message function $f_r$. A node's representation is updated by summing the messages from each relation type and passing the result through a shared update function. On top of this encoder we attach one domain discriminator $D_r$ per relation type, along with a gradient reversal layer, which flips the sign of the discriminator's gradient so that the encoder learns to fool it. Each discriminator sees the message $m^r_{uv} = f_r(h_u)$ on an edge of type $r$, together with one-hot types of the two endpoint nodes. Conditioning on endpoint types matters when type proportions differ between graphs. Without it, the discriminator could win just by noticing that the target has more author nodes, and the encoder would erase type information to fool it. The training objective is
$$ \min_{f,g}\max_{\{D_r\}} \; \mathcal{L}^{S}_{\text{task}}(g \circ f) \;-\; \lambda \sum_{r} w_r \, \mathcal{L}_{D_r}\big(m^r_{uv}, \tau_u, \tau_v\big), $$
Here $\mathcal{L}^S_{\text{task}}$ is the supervised loss on labeled source nodes, $g$ is the classifier and $f$ the encoder. $\mathcal{L}_{D_r}$ is the cross-entropy of discriminator $D_r$ at predicting the domain of edge $(u,v)$. $\tau_u$ and $\tau_v$ are the endpoint node types, $w_r$ is the inverse share of edges of type $r$, so that rare relations still get aligned, and $\lambda$ is a single trade-off weight. The objective has no global discriminator on final node embeddings and no target pseudo-labels.
The diagnostic is a typed unobserved-local-structure test. For each node, we enumerate the connected sub-graphs of 2–4 nodes inside its 2-hop neighborhood. We encode each one by a canonical form that records node types and edge types, using exact canonicalization for small sizes and sampling for high-degree nodes. A target node is flagged "structurally novel" if any of its typed sub-structures never occurs in the source graph. We then report two quantities. The first is the AUC of this flag for predicting misclassification, which tests whether the semantic-parsing finding carries over to graphs. The second is the compositional transfer gap, the accuracy on unflagged target nodes minus the accuracy on flagged ones. This gap is the quantity our method is meant to shrink.
Baselines
The naive reference is a relation-typed encoder trained on labeled source nodes only. It is identical in architecture to ours, with the discriminators removed. We also include its pooled variant for the multi-source settings. Every method uses the same encoder, the same data, and the same hyperparameter search budget of 30 trials, selected on a small labeled target validation set that is used only for model selection and reported identically for all methods. Results are averaged over five seeds.
The first adversarial baseline is global DANN: the same encoder with a single gradient-reversal discriminator on final node embeddings. It is the obvious answer to the question, and GRDA's evidence suggests it will hurt. Beating it means higher overall target accuracy and a smaller compositional transfer gap.
The strongest existing method is Pair-Align (Pairwise Alignment Improves Graph Domain Adaptation), which we extend in the most favorable way by estimating a separate edge weight for each relation type. On its country-partitioned academic graph it reports over 25% relative accuracy gain over plain training. No absolute accuracy was found in our sources, and no reported result was found on Lacuna for any graph domain adaptation method on a heterogeneous multi-relational benchmark. We will therefore rerun Pair-Align on its original homogeneous split to confirm that our implementation reproduces its reported relative gain before trusting the typed extension. We also run a typed version of JDA-GCN (Joint Domain Adaptive Graph Convolutional Network). On homogeneous citation transfer it reports an average 1.65% improvement over its best baseline. Our method counts as beating these baselines only if it matches them on overall target accuracy and is better on structurally novel target nodes, with a margin larger than two seed standard deviations.
The fourth baseline is structural augmentation, following the suggestion in Unobserved Local Structures Make Compositional Generalization Hard. We rewire source edges, keeping types valid, so that the source contains the typed sub-structures found in the target, and train on the augmented graph. It receives the same tuning budget, including the rewiring rate.
Three ablations isolate the key ingredient. The first removes endpoint-type conditioning from each $D_r$. The second keeps per-relation discriminators and adds a global one. The third shares a single message function across all relations, so that "parts" are no longer separable while the per-relation discriminators remain. If the shared-function ablation does as well as the full model, modularity is not doing the work.
Why not just…?
Why not just apply DANN to a heterogeneous encoder? Global alignment asks the final embedding to hide the domain, and in a heterogeneous graph the easiest domain cue is often relational, such as how often authors bridge topics. Graph-Relational Domain Adaptation shows uniform alignment doing worse than no adaptation on TPT-48, and CDANN trailing GRDA by 12 points on DG-15 (72.44% versus 84.44%). Our diagnostic tests a specific prediction: global DANN should widen the compositional transfer gap relative to source-only training. If it does not, the motivation for part-level alignment weakens considerably, and we will report that.
Why not just extend Pair-Align with one edge weight per relation? This is a real competitor. It corrects shifts in how structure relates to labels, which ours does not model explicitly. It has two weaknesses here. Its weights are estimated from target pseudo-labels, which degrade under severe schema shift. And reweighting can only scale typed edges that already exist, so it cannot teach the model about a typed combination it never saw. The decisive comparison is on structurally novel nodes as the schema shift is made more severe. We expect typed Pair-Align to hold up on unflagged nodes and fall behind on flagged ones. If it does not fall behind, the right conclusion is that reweighting suffices, and we would test the two methods combined.
Why not just augment the source graph with the missing structures? This is the most serious threat, because it attacks the gap head-on. Its weakness is labels. A rewired source node carries a label that was valid for its original neighborhood, so augmentation manufactures exactly the structure–label mismatch that Pair-Align shows to be harmful. On the synthetic benchmark we control whether the labels of novel structures follow the composition of their parts. Augmentation should match our method when they do and fail when they do not, while part-level alignment should degrade more gracefully. If augmentation wins in both regimes, we will say so and reframe the contribution as the diagnostic plus the combination.
Why not just use a larger heterogeneous transformer? On the Compositional Generalization Gap of In-Context Learning finds that scaling narrows the gap without closing it. CLUTRR and Neural Compositional Rule Learning for Knowledge Graph Reasoning both show holistic sequence models degrading on longer compositions while modular ones hold. We will still run a capacity-matched check by doubling the width of the source-only encoder, so that any gain cannot be credited to extra discriminator parameters.
Proposed Experiments
The first experiment is a controlled synthetic study. We extend the contextual stochastic block model, which generates graphs whose features, labels and edges are drawn from known distributions, to typed nodes and edges, following the use of such graphs to separate shift types in Pairwise Alignment Improves Graph Domain Adaptation. Source and target share the per-relation message distributions, but the target allows typed 3-node combinations that the source forbids. We sweep the fraction of structurally novel target nodes from 0 to 60%, and we toggle whether labels of novel combinations follow the composition of their parts. This gives a clean picture of where each method breaks.
The second experiment uses a real heterogeneous graph. We start from the country partitioning of the Microsoft Academic Graph used by Pair-Align and restore the author, venue and topic node types around the papers. This construction is ours: no prior result exists on it, and we will release the splits. We also build an adversarial split in the style of the compositional parsing work, holding chosen typed sub-structures out of the source country graph. The third experiment uses multi-relational knowledge graphs from the NCRL suite, namely Family, Kinship, UMLS and GraphLog, with relation-composition patterns held out between source and target subsets. On CLUTRR we train on 2–3-hop stories drawn from one distribution of relation mixtures and test on longer chains from a shifted mixture, which adds domain shift to the benchmark where GATs already reach 1.0 without shift. As a sanity check, we run the homogeneous ACM/DBLP/Citation transfer tasks. With a single relation type our method reduces to edge-level DANN, and it should stay within noise of JDA-GCN-style baselines there rather than claim gains.
The metrics are target accuracy or Micro-F1 for node classification and mean reciprocal rank for link prediction. For every method we also report the AUC of the typed unobserved-structure flag for predicting errors and the compositional transfer gap.
The decisive check is a single plot, the transfer gap against the fraction of novel structure. The claim survives if three things hold together. Source-only and global DANN must show a gap that grows with novelty, with DANN's gap at least as large as source-only's. The full model must show a gap that grows clearly more slowly. And the shared-message-function ablation must lose most of that advantage. If the flag's AUC for predicting errors is near 0.5 on real graphs, the transfer of the semantic-parsing finding to graphs fails, and with it the premise of the proposal.
References
- Unobserved Local Structures Make Compositional Generalization Hard
- CLOSURE: Assessing Systematic Generalization of CLEVR Models.
- On the Compositional Generalization Gap of In-Context Learning
- Neural Compositional Rule Learning for Knowledge Graph Reasoning
- CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text
- Joint Domain Adaptive Graph Convolutional Network
- Pairwise Alignment Improves Graph Domain Adaptation
- Graph-Relational Domain Adaptation
- Graph Augmentation for Cross Graph Domain Generalization
- IDEA: Invariant defense for graph adversarial robustness
- Episodic Training for Domain Generalization