PISA: Prioritized Invariant Subgraph Aggregation for Out-of-Distribution Generalization on Graphs

Invariant learning on graphs aims to build predictors that rely on causal substructures rather than on environment-specific shortcuts. Current methods extract either a single invariant subgraph (CIGA) or, more recently, a set of diverse invariant subgraphs (SuGAr). We observe that the second half of the multi-subgraph pipeline, "how the extracted subgraphs are combined" has gone essentially unexamined; existing methods average branch predictions uniformly or select one greedily. We show that this is precisely where accuracy is lost. A minimum-variance combination argument establishes that uniform averaging is optimal only when every branch carries the same total error covariance with the ensemble---a knife edge balance that second order exchangeability guarantees and that the diversity regularizer used to obtain multiple subgraphs is explicitly designed to break. We then show that invariance is closed under post composition; because the branches are frozen and read the graph only through their invariant subgraphs, any measurable aggregator of their outputs remains invariant, and the aggregate's environment gap is bounded by the branches' residual invariance violation uniformly over aggregators. Learning the combination rule by plain empirical risk minimization is therefore safe, and aggregator capacity trades off against estimation error rather than robustness. PISA instantiates this with a lightweight instance-conditional MLP over stacked branch logits, trained on frozen branches at negligible cost. Across 15 synthetic and real benchmarks, PISA improves the average over the strongest prior method by 2.96 points on synthetic shifts and 1.74 points on realistic shifts, with per-dataset gains up to 5.90 points, and nearly doubles SuGAr's improvement over ERM on the six DrugOOD tasks (from +2.76 to +5.07 ROC-AUC).