PaperlayerView exact revision on arXiv

Source-linked AI summary

Message Passing Does More with Less for In-Context Learning on Graphs

Dooho Lee, Jinmo Lee, Minho Jeong, Kijung Shin, Jaemin Yoo

arXiv:2609.37057v1cs.LGcs.SI

TL;DR

Per-dataset GNN training and tuning are costly, while existing graph ICL uses dense attention and has not established broad competitiveness. Ephris uses sparse message passing and a synthetic graph prior; across both label regimes, it leads aggregate metrics while running substantially faster than GraphPFN.

  • Problem

    GNNs typically require per-dataset training and tuning, while prior graph ICL retains costly dense attention and has been evaluated against limited datasets and baselines.

    Source: §1 · pp. 1–2

  • Method

    Ephris performs graph in-context prediction through sparse message passing and uses a synthetic prior spanning diverse graph structures and relational dynamics.

    Source: §1 · p. 2

  • Results

    Across 51 node-classification datasets, Ephris outperforms 15 extensively tuned GNNs and six recent GFMs on all four aggregate metrics under both label regimes, running 13.1–16.1× faster than GraphPFN.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Ephris demonstrates that strong graph ICL does not require dense cross-node attention and advances the performance-runtime Pareto frontier.

    Source: §5.1 · p. 8

    Ablation conclusions use reduced-budget proxy pretraining and may not fully transfer to full-scale training; the scope is limited to node classification, with robustness under non-IID grouped and temporal splits still important.

    Source: §6 · p. 9

Abstract

from arXiv · show

Achieving strong performance with graph neural networks (GNNs) typically requires training and hyperparameter tuning for each dataset, incurring repeated costs and effort. Graph in-context learning (ICL) avoids this by using a single pretrained model to predict unknown node labels directly from labeled context nodes. Existing approaches, however, rely on dense attention across nodes, making inference increasingly expensive as graphs grow. In this work, we present Ephris, a new graph in-context learner built on sparse message passing, scaling linearly with the number of node-feature entries and graph edges. Ephris is pretrained entirely on synthetic graphs generated from structural causal models with diverse graph structures and relational dynamics, exposing the model to varied dependencies among topology, features, and labels. We evaluate Ephris on 51 node-classification datasets against 15 extensively tuned GNNs and existing graph ICL methods under both high- and low-label train/validation/test splits. Across both settings, Ephris ranks first on all four aggregate measures: Elo, improvability, average rank, and accuracy. Its inference cost remains comparable to training a single GNN once, while being over 10 times faster than previous graph ICL models. Together, these results advance the performance-runtime Pareto frontier, demonstrating that strong graph ICL does not require dense attention. Code and model weights are available at https://github.com/nums-ai/ephris.

1 INTRODUCTION

Dataset-specific GNN training and tuning impose repeated costs, while existing graph ICL retains dense attention and lacks broad evidence of competitiveness. Ephris combines sparse message passing with a synthetic graph prior, and leads aggregate comparisons across both label regimes.

1 INTRODUCTION

  • GNNs typically require per-dataset training and hyperparameter tuning, creating repeated time and effort costs when a new graph is encountered.ICL offers an alternative: predict unseen labels from observed labels without updating model parameters.Source: §1 · p. 1
  • Existing graph ICL retains dense attention over labeled context nodes, so inference scales quadratically with context size and can exceed GNN training and tuning costs.Prior methods combine graph-aware modules with tabular foundation-model backbones.Source: §1 · p. 2
  • Prior graph ICL evaluations were narrower in graph size, feature count, and baseline coverage, and tuned GNNs remain stronger on many datasets in broader testing.The expanded evaluation spans 51 datasets, up to 568,795 nodes and 8,710 features per node, against 15 GNNs.Source: §1 · p. 2
  • Ephris uses sparse message passing with linear scaling in node-feature entries and graph edges, plus a synthetic prior spanning graph structures and relational dynamics.The prior exposes the model to varied dependencies among topology, features, and labels.Source: §1 · p. 2
  • Ephris ranks first in Elo, improvability, average rank, and accuracy under both high- and low-label regimes, at the cost of one GNN training run and over 13× faster than GraphPFN.The evaluation covers 51 node-classification datasets, 15 tuned GNNs, and 6 graph foundation models.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

The background defines graph in-context prediction using observed labels as context and query nodes as the prediction targets. It situates Ephris among graph foundation models and describes synthetic task generation through structural causal models.

2 BACKGROUND AND RELATED WORK

  • A graph task comprises adjacency, node features, labels, and a partition into context nodes and query nodes, corresponding to training and test nodes.The model is given graph structure, node features, and context labels to predict unobserved query labels.Source: §2 · p. 2
  • Synthetic graph tasks are sampled from a prior, and a shared model learns query-label prediction across tasks before applying that capability to unseen graphs without updating parameters.At inference, the model uses the graph, features, and context labels.Source: §2 · p. 2
  • An SCM specifies a directed acyclic graph of dependencies among intermediate variables, which are generated in topological order.Functions may be drawn from families including MLPs, tree ensembles, and linear or quadratic mappings; transformations can normalize values or inject noise.Source: §2 · p. 3
  • Graph foundation models vary in what they transfer and how they adapt, from feature encoders or graph-derived features to observed-label context for prediction.Ephris follows the graph ICL approach of using observed node labels as context without dataset-specific parameter updates.Source: §2 · p. 3

3 EPHRIS: A SCALABLE GRAPH IN-CONTEXT LEARNER

Ephris replaces dense cross-node attention with an architecture that compresses graph-aware feature tokens into fixed-size node representations and performs in-context learning through message passing. Its MPICL block supports adaptive information aggregation and propagation, while computation scales linearly with node-feature entries and graph edges.

3.1 ARCHITECTURE OVERVIEW

  • Feature tokens are refined across nodes and graph structure, then compressed into fixed-width node representations before stacked MPICL blocks perform graph in-context learning.The compressed width is D = K_N d, independent of feature count; feature refinement integrates distributional and graph context.Source: §3.1 · pp. 3–4, Figure 2 · p. 4

3.2 MESSAGE PASSING BLOCK FOR ICL

  • MPICL dynamically weights neighbors, adjusts attention to neighborhood size, adds learned global nodes, and uses residual depth to expand receptive fields while retaining sparse computation.Global nodes permit communication beyond observed edges, and deeper stacks propagate information over longer graph distances.Source: §3.2 · pp. 4–5

3.3 COMPUTATIONAL COMPLEXITY

  • Each prediction pass costs O(NF + E), linear in node-feature entries and edges rather than quadratic in nodes or features.The analysis assumes fixed hidden dimensions, inducing-token counts, network depths, and context ratio.Source: §3.3 · p. 5, Table 1 · p. 5
  • β = 1.07 for Ephris, versus 1.98 for NodePFN and 1.90 for GraphPFN, showing nearly linear rather than nearly quadratic inference scaling.The measurements use synthetic graphs from 50K to 500K nodes, 32 features, average degree 8, and a 50% context ratio.Source: §3.3 · p. 5, Figure 3 · p. 5

4 PRETRAINING WITH DIVERSE SYNTHETIC GRAPHS

Ephris is pretrained using synthetic graph tasks generated from varied topologies, graph-conditioned feature-label relationships, and feature representations. A two-stage curriculum exposes the model to small graphs first and then broader graph sizes and feature dimensions.

4.1 SYNTHETIC GRAPH PRIOR

  • The synthetic prior mixes group-based, degree-heterogeneous, and ordering-based graph generation to vary connectivity patterns.Mixture weights vary across graphs.Source: §4.1 · p. 6
  • Graph propagation conditions generated features and labels, with diffusion, cascade, and degree-dependent mixing supplying varied relational dynamics.Propagation can aggregate neighbors by mean, max, or min; rule-specific coefficients, steps, and thresholds also vary.Source: §4.1 · p. 6
  • Post-processing samples tabular, embedding, or hybrid feature representations to vary how generated information appears across dimensions.Embedding representations mix all generated features; hybrid representations transform only a subset.Source: §4.1 · p. 6

4.2 TRAINING SCHEDULE AND OPTIMIZATION

  • A two-stage curriculum trains for 50,000 steps on relatively small graphs, then 10,000 more steps across broader graph sizes and feature dimensions.Each step uses 64 freshly generated graphs, for 3.84 million graphs total.Source: §4.2 · p. 6, Table 2 · p. 6
  • Ephris achieves the highest Elo in both label regimes.Figure 4 orders methods by mean Elo across regimes; bars nest default GNNs within tuned counterparts, with OOM results imputed using GCN (Default).Source: Figure 4 · p. 7

5 EXPERIMENTS

Across broad node-classification benchmarks, Ephris leads predictive-performance measures while reducing the runtime cost of graph in-context learning. The experiments also examine subgroup performance, transfer beyond ordinary graph splits, and the contributions of its architecture and synthetic prior.

5 EXPERIMENTS

  • The evaluation covers 51 datasets, two label regimes, and five splits per regime; tuned GNNs use the best of 200 configurations.Ablations use 10% of Stage 1 pretraining scale; full pretraining uses 3.84M synthetic graphs and requires 16 GPU-days in the reported environment.Source: §5 · p. 7, §5.3 · p. 9

5.1 MAIN RESULTS

  • Existing graph foundation models do not outperform tuned GNNs overall in the broader evaluation; GCNII and GPRGNN lead under both label regimes.GraphPFN is the strongest existing graph foundation model, but does not outperform either overall.Source: §5.1 · p. 8
  • Ephris ranks first in Elo, improvability, average rank, and average accuracy under both label regimes, beating tuned GCNII in 67% and 54% of comparisons and GraphPFN in 71% of both-regime comparisons.Supervised baselines use validation labels for early stopping and hyperparameter selection; Ephris does not.Source: §5.1 · p. 8
  • Ephris inference costs 1.33–1.84× a single GCN training run and is 13.1–16.1× faster than GraphPFN; it is the only graph foundation model on the Pareto frontier across all metrics.Figure 5 compares mean improvability and runtime overhead in high- and low-label regimes; lower is better on both axes.Source: §5.1 · p. 8, Figure 5 · p. 8
  • Ephris outperforms GraphPFN in nearly all subgroups, but trails tuned GCNII on datasets with more than 5,000 features or ten classes.Figure 6 reports average ranks across subgroups in the high-label regime; both challenging ranges exceed those seen during pretraining.Source: §5.1 · p. 8, Figure 6 · p. 8

5.2 BEYOND ORDINARY GRAPHS AND RANDOM SPLITS

  • Ephris ranks first or second on eight of ten hypergraph datasets and in 13 of 20 GOOD distribution-shift settings, but drops substantially in several other GOOD settings.The hypergraph evaluation uses simple clique or incidence representations; the remaining GOOD results point to robustness under distribution shift as future work.Source: §5.2 · p. 9

5.3 ABLATION STUDIES

  • In a 3×3 factorial study, Ephris’s architecture achieves the highest mean accuracy under every prior, while its prior performs best across all architectures.The authors conclude that the architecture and prior contribute independently, not only through their combination.Source: §5.3 · p. 9
  • Removing SCM propagation reduces mean accuracy by roughly 20%, while removing other tested architecture and prior components also reduces accuracy or win rate.Restricting the prior to a single relational dynamic underperforms the mixture.Source: §5.3 · p. 9

6 CONCLUSION

Ephris achieves strong graph in-context learning performance through sparse message passing and synthetic pretraining, and the authors present graph ICL as a practical alternative to per-dataset GNN training and tuning. They identify robustness under distribution shift and extension beyond node classification as important remaining work.

6 CONCLUSION

  • Across 51 node-classification datasets, Ephris outperforms 15 tuned GNNs and six recent graph foundation models on all four aggregate metrics in both label regimes, at roughly the cost of one GNN training run.It runs 13.1–16.1× faster than GraphPFN and advances the performance-runtime Pareto frontier.Source: §6 · p. 9
  • The scope is limited to node classification; improving robustness under non-IID grouped and temporal distribution shifts remains important for real-world applicability.The authors identify link prediction and graph-level tasks as extensions toward general-purpose graph foundation models.Source: §6 · p. 9
  • The work uses synthetic graph tasks and open node-classification benchmarks, and reports following dataset and method licenses and intended research use.Source: ETHICS STATEMENT · p. 10
  • The paper documents model specifications, evaluation procedures, and ablation results, and releases code and a checkpoint for direct evaluation without repeating full pretraining.The authors state that generative AI assisted code development and manuscript editing, but not experimental results or research decisions.Source: REPRODUCIBILITY STATEMENT · p. 10, AI USE STATEMENT · p. 10

A EVALUATION METRICS

The evaluation compares methods within each dataset-split and aggregates performance and adaptation cost across datasets. Its metrics capture pairwise standing, rank, distance from the best configuration, accuracy, and runtime.

A EVALUATION METRICS

  • Elo compares methods pairwise within each dataset-split, weights the five splits equally, and sets default GCN to 1000 as its reference rating.Each dataset contributes equally to the Bradley-Terry ratings.Source: A EVALUATION METRICS · p. 16
  • Average rank averages within-split configuration ranks across five splits and 51 datasets; lower values indicate better standing.Ties receive the average of their occupied ranks; predictive scores are not averaged before ranking.Source: A EVALUATION METRICS · p. 16
  • Improvability measures the fraction of the remaining gap to a perfect score that could be closed by matching the best evaluated configuration; lower mean values are better.The method’s and best configuration’s scores are compared separately for each dataset-split.Source: A EVALUATION METRICS · p. 16
  • Average accuracy uses accuracy for binary and multiclass tasks, while runtime measures adaptation cost and aggregates multiplicative differences with a geometric mean.Runtime includes training and full hyperparameter search for tuned GNNs, or the adaptation procedure for GFMs.Source: A EVALUATION METRICS · p. 16

B ARCHITECTURE DETAILS

Ephris refines feature and node representations before graph in-context learning, while its synthetic prior varies graph structure, relational propagation, and feature representation. The implementation details cover both the architecture and these synthetic-task components.

B ARCHITECTURE DETAILS

  • The architecture uses 128-wide feature tokens, three graph-aware refinement blocks, four per-node inducing tokens, and ten further message-passing blocks for graph in-context learning.Refinement first gathers information across nodes for each feature, then gathers across features within each node; the graph-ICL stage retains the original nodes’ representations.Source: B ARCHITECTURE DETAILS · pp. 16–18
  • Per-node compression forms a fixed-width representation from four summary tokens, then adds context-label embeddings and layer normalization before graph in-context learning.Query nodes receive no context-label embedding; the resulting representation is label-conditioned.Source: B ARCHITECTURE DETAILS · p. 17

C.1 GRAPH SAMPLING

  • Synthetic graphs mix group-based, degree-heterogeneous, and ordering-based connectivity, with edge proposals followed by self-edge and duplicate removal and probabilistic reverse edges.The sampled graph may contain fewer than the target number of edges, and isolated nodes are allowed.Source: §C.1 · pp. 18–19

C.2 RELATIONAL DYNAMICS

  • Relational dynamics select SCM variables for propagation and sample each variable’s rule, aggregation, and edge direction; cascade, degree-dependent mixing, and diffusion provide distinct update patterns.Cascade updates activated nodes conditionally, degree and disagreement affect mixing strength, and repeated diffusion accumulates neighbor influence.Source: §C.2 · pp. 19–20

C.3 POST-PROCESSING

  • Feature post-processing samples tabular, embedding, or hybrid representations, varying whether source columns remain individually accessible or are mixed into an embedding.The hybrid representation concatenates an embedding with retained source columns and permutes the resulting columns.Source: §C.3 · pp. 20–21

D.1 EXPERIMENT ENVIRONMENT

The implementation uses a two-stage synthetic-task curriculum and a fixed inference checkpoint. Its setup specifies the model configuration, optimization, and how inference handles datasets and class counts.

D.1 EXPERIMENT ENVIRONMENT

  • Experiments ran on NVIDIA H200 GPUs with two Intel Xeon Platinum 8462Y+ CPUs and approximately 2 TiB of RAM.The environment used Ubuntu 22.04.5 LTS, Python 3.11.9, and PyTorch 2.11.0 with CUDA 13.0.Source: §D.1 · p. 21

D.2 ARCHITECTURE SETUP

  • The instantiated model embeds scalar features into 128-dimensional tokens, compresses each node into four tokens, and applies ten MPICL layers before a head supporting up to ten classes.The four tokens concatenate into a 512-dimensional representation.Source: §D.2 · p. 21

D.3 PRETRAINING SETUP

  • Pretraining uses a two-stage curriculum, expanding from graphs with up to 128 features to tasks spanning 128–16,384 nodes and 2–1,024 features.The curriculum comprises 50,000 Stage 1 updates and 10,000 Stage 2 updates, totaling 3.84 million generated tasks.Source: §D.3 · p. 22

D.4 OPTIMIZATION

  • Eligible matrix parameters use Muon, while remaining parameters use AdamW, with stage-specific warmup and cosine-decay schedules.In Stage 2, AdamW stays at 10^-5 after warmup while Muon decays from 4 × 10^-5 to 10^-5.Source: §D.4 · p. 23

D.5 INFERENCE

  • Inference uses the final Stage 2 checkpoint without dataset-specific gradient updates; for datasets with more than ten classes, ECOC evaluates multiple code problems with the same weights.The paper does not use test-time permutation ensembling; class-label permutations can change predictions after remapping, and potential benefits of class-permutation ensembling remain for future work.Source: §D.5 · p. 23

E.1 DATASETS

The evaluation spans diverse node-classification datasets, establishes tuned supervised GNN baselines, and counts target-time procedures as part of GFM adaptation. Ephris uses a fixed procedure without validation-label use or dataset-specific configuration search.

E.1 DATASETS

  • The 51 datasets span six application domains and range from 183 to 568,795 nodes, 12 to 8,710 features, and 2 to 70 classes.Adjusted label homophily ranges from −0.30 to 0.94; Table 7 reports each dataset’s domain and key characteristics.Source: §E.1 · p. 23, Table 7 · p. 26

E.2 GNN TRAINING AND HYPERPARAMETER TUNING

  • All 15 supervised GNNs are tuned using 200 sampled configurations per method and dataset split, with final selection based solely on validation performance.Search spaces follow the original work where specified and otherwise include reported choices; conventional GNN tuning also covers several consequential architectural choices.Source: §E.2 · p. 24, Table 8 · p. 27

E.3 GFM ADAPTATION PROTOCOLS

  • GFM adaptation includes target-time computation and selection: some methods fit predictors or select depth, while GraphPFN and NodePFN require dataset-specific choices in this evaluation.GVT selects predictor checkpoints and depth; Node4All fits a predictor, and NodePFN searches preprocessing and inference settings. Ephris instead uses fixed inference without validation labels or dataset-specific search.Source: §E.3 · pp. 24–25

F BEYOND STANDARD NODE CLASSIFICATION

Ephris is tested beyond random node classification on distribution-shift and hypergraph tasks, using the same pretrained checkpoint for inference. It remains competitive under shifts and transfers to hypergraphs through graph representations, with performance varying by setting and representation.

Robustness under distribution shift

  • The distribution-shift evaluation covers six dataset-attribute settings across four GOOD datasets, with no-shift, covariate-shift, and concept-shift splits and ID- or OOD-selected baselines.Ephris uses training-node labels as context and does not access validation data.Source: F BEYOND STANDARD NODE CLASSIFICATION · p. 28
  • Under distribution shift, degradation is localized to degree-based covariate shift and time-based concept shift on Arxiv, university-based covariate shift on WebKB, and language-based concept shift on Twitch.The results suggest robustness is case-dependent; adding shift scenarios to the synthetic prior is proposed as a direction for future work.Source: F BEYOND STANDARD NODE CLASSIFICATION · p. 28

Hypergraph transfer

  • Hypergraph evaluation uses ten AllSet datasets and converts each to a graph by clique expansion or an incidence representation, comparing inference-only Ephris with separately trained published baselines.The evaluation uses random 50/25/25 splits over 20 runs.Source: F BEYOND STANDARD NODE CLASSIFICATION · p. 28, Table 11 · p. 31
  • Ephris achieves or ties the highest reported accuracy on six of ten hypergraph datasets, while neither clique expansion nor incidence representation consistently dominates.Both representations use the same frozen checkpoint and inference from 50% labeled context, without hypergraph-specific training or validation-based selection.Source: F BEYOND STANDARD NODE CLASSIFICATION · p. 28, Table 11 · p. 31

Robustness under distribution shift

G ABLATION STUDIES

Controlled proxy ablations separate Ephris’s architecture and synthetic prior, then examine their component choices. Both contribute across different pairings, while early-training results are not full-scale effect estimates.

Ablation setup

  • Variants use a common reduced budget of 5,000 steps over 320,000 synthetic graphs on the same 51 datasets; their absolute performance is below the fully pretrained model, and relative effects may change with more training.The proxy runs use 10% of Stage 1 training because full pretraining takes approximately 16 GPU-days.Source: G ABLATION STUDIES · p. 32

Disentangling architecture and prior

  • Holding the prior fixed, the Ephris architecture achieves the highest mean accuracy under all three priors, and holding architecture fixed, the Ephris prior performs best across all three architectures.The factorial study indicates that each component’s gains transfer across substantially different choices of the other.Source: G ABLATION STUDIES · p. 32
  • The prior comparison suggests that topology sampling alone is insufficient: graph structure must also shape feature and label generation, with diverse relational dynamics and feature representations supporting performance.Ephris consistently improves over GraphPFN despite sharing its structure-first formulation; the study does not establish that structure-first generation is inherently preferable to feature-first generation.Source: G ABLATION STUDIES · pp. 32–33

Architecture Ablations

  • All five architectural variants degrade downstream performance; uniform aggregation and removing broadcast raise training cross-entropy, while other variants can have comparable or lower loss.The contrast suggests architectural choices contribute to transfer to real-world graphs, not only fitting synthetic pretraining tasks.Source: G ABLATION STUDIES · p. 32, Figure 8 · p. 33

Prior Ablations

  • Removing relational propagation reduces mean accuracy from 78.91% to 60.61%, the largest degradation among prior ablations.Restricting propagation to any single dynamic underperforms their mixture, and removing embedding-like post-processing further reduces performance.Source: G ABLATION STUDIES · pp. 32–33, Figure 8 · p. 33

H FULL EXPERIMENTAL RESULTS

Across 51 datasets, Ephris leads all four aggregate predictive metrics in both label regimes. It combines that performance with lower adaptation runtime, while subgroup results show stronger comparisons against prior graph ICL methods than against tuned GNNs in low-label cases.

Performance and runtime

  • Compared with GraphPFN, Ephris is approximately 16.1× and 13.1× faster in high-label and low-label regimes while achieving stronger performance across all four aggregate metrics.It is also approximately 739× and 584× faster than GCNII and 161× and 103× faster than GPRGNN in the respective regimes.Source: H FULL EXPERIMENTAL RESULTS · p. 34, Figure 10 · p. 37

Performance across dataset characteristics

  • Against GCNII and GPRGNN, Ephris leads across nearly all subgroups with high labels, but methods are comparable and tuned GNNs lead in several low-label cases.The authors suggest dataset-specific validation selection among 200 configurations may be particularly valuable when labeled context is low; this is presented as a possible explanation.Source: H FULL EXPERIMENTAL RESULTS · p. 34
  • High-dimensional datasets (F ≥ 5K) and tasks with more than ten classes (C > 10) are clear high-label exceptions, outside the feature and class counts directly observed during pretraining.The passage notes that larger label spaces are handled indirectly through ECOC and that GraphPFN shows the same subgroup failure pattern.Source: H FULL EXPERIMENTAL RESULTS · p. 34

Aggregate performance

  • Ephris ranks first in Elo, improvability, average rank, and average accuracy under both high-label and low-label regimes.High-label Elo is 1521 versus 1388 for tuned GCNII; low-label Elo is 1381 versus 1371 for tuned GCNII. Average accuracy is 81.27% and 74.23%, respectively.Source: H FULL EXPERIMENTAL RESULTS · p. 34, Table 13 · p. 35

Performance across dataset characteristics

Related papers

Loading 2609.37057v1…