Scalable Graph In-Context Learning with Stronger Predictive Performance

Applying graph neural networks (GNNs) typically requires training and hyperparameter tuning for each dataset, incurring repeated costs in time and effort. Graph in-context learning (graph ICL) offers an alternative: a pretrained model predicts missing node labels on unseen graphs through inference alone, using observed labels as context. However, existing graph ICL models rely on dense attention across nodes, limiting inference efficiency and scalability. *We ask whether dense attention is necessary for graph in-context learning.* We introduce Ephris, which realizes graph ICL through sparse message passing, scaling linearly with node-feature entries and graph edges. We pretrain Ephris entirely on synthetic tasks from structural causal models extended with diverse graph structures and relational dynamics, capturing varied dependencies among topology, features, and labels. Across 51 node-classification datasets, we compare Ephris against 15 extensively tuned GNNs and prior graph ICL models under high-label (50/25/25) and low-label (10/10/80) train/validation/test splits. Ephris ranks 1st across all four aggregate metrics, including Elo, improvability, average rank, and accuracy, in both regimes. This strong performance comes at substantially lower adaptation cost, with inference comparable to a single GNN training run. Together, Ephris advances the performance-runtime Pareto frontier, offering a practical alternative to per-dataset training and tuning. Code and model weights are available at https://anonymous.4open.science/r/ephris/.