PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Posterior Predictive Distributions for Node Classification from Synthetic Graph Priors

Jeongwhan Choi, Jongwoo Kim, Woosung Kang, Noseong Park

arXiv:2604.19028v1cs.LG

TL;DR

GNNs require graph-specific training, limiting node-classification generalization across diverse graphs. NodePFN learns posterior predictive distributions from synthetic graph priors and achieves competitive universal classification across 23 real-world benchmarks, including 71.27% average accuracy.

  • Problem

    GNN-based node classification requires separate models trained on labeled nodes for each new graph, limiting generalization across graphs with diverse properties.

  • Method

    NodePFN learns posterior predictive distributions from thousands of synthetic graphs with controlled homophily and community structure, using graph-aware in-context learning.

  • Results

    Across 23 real-world benchmarks, NodePFN achieves competitive performance and surpasses GNN baselines on both homophily and heterophily graphs, including 71.27% average accuracy.

  • Takeaways & Limitations

    The results support learning universal node-classification patterns from synthetic graph priors with a single pre-trained model.

  • Takeaways & Limitations

    Node classification effectiveness remains tied to graph homophily, with GNN success believed to rely on connected nodes sharing class labels.

Abstract

from arXiv · show

One of the most challenging problems in graph machine learning is generalizing across graphs with diverse properties. Graph neural networks (GNNs) face a fundamental limitation: they require separate training for each new graph, preventing universal generalization across diverse graph datasets. A critical challenge facing GNNs lies in their reliance on labeled training data for each individual graph, a requirement that hinders the capacity for universal node classification due to the heterogeneity inherent in graphs -- differences in homophily levels, community structures, and feature distributions across datasets. Inspired by the success of large language models (LLMs) that achieve in-context learning through massive-scale pre-training on diverse datasets, we introduce NodePFN. This universal node classification method generalizes to arbitrary graphs without graph-specific training. NodePFN learns posterior predictive distributions (PPDs) by training only on thousands of synthetic graphs generated from carefully designed priors. Our synthetic graph generation covers real-world graphs through the use of random networks with controllable homophily levels and structural causal models for complex feature-label relationships. We develop a dual-branch architecture combining context-query attention mechanisms with local message passing to enable graph-aware in-context learning. Extensive evaluation on 23 benchmarks demonstrates that a single pre-trained NodePFN achieves 71.27 average accuracy. These results validate that universal graph learning patterns can be effectively learned from synthetic priors, establishing a new paradigm for generalization in node classification.

1 INTRODUCTION

NodePFN addresses graph-specific training by learning posterior predictive distributions from diverse synthetic graph priors, enabling one model to classify nodes across arbitrary graphs. Across 23 benchmarks, it achieves competitive performance, including strong results on heterophily graphs.

  • Motivation: GNN-based node classification traditionally requires a separately trained model for the labeled nodes of each new graph, limiting cross-graph generalization.Graph diversity includes differences in topology, homophily, communities, and features.
  • Method: The model applies learned patterns from labeled context nodes to unlabeled query nodes without dataset-specific training or gradient updates.This extends the PFN in-context learning paradigm to graph node classification.
  • Method: NodePFN learns posterior predictive distributions from thousands of synthetic graphs sampled from priors that control homophily and community structure.The approach is designed to cover network characteristics found in real-world benchmarks without using actual training data.
  • Results: 71.27% average accuracy across 23 real-world benchmarks demonstrates universal node classification with one pre-trained NodePFN.NodePFN also achieves 65.14% on challenging heterophily graphs.
  • Method: A dual-branch architecture combines context-query attention with local message passing to incorporate labeled examples and graph topology.The design targets graph-aware in-context learning.
  • Method: The synthetic prior uses random graph models, including Erdős-Rényi networks and contextual stochastic block models, to represent varied structural regimes.The cSBM-based priors control community structure and homophily, while ER models provide graphs without inherent community structure.

3 NODEPFN: PRIOR-FITTED NETWORKS FOR NODE CLASSIFICATION

NodePFN is a prior-fitted network that learns posterior predictive distributions for node classification from synthetic graph data, enabling in-context prediction on arbitrary graphs without task-specific training. Its architecture combines context-query attention with local message passing, and inference produces predictions in one forward pass without gradient updates or fine-tuning.

  • NodePFN learns posterior predictive distributions from synthetic graph priors and performs in-context node classification on arbitrary graphs in a single forward pass.Training samples synthetic graphs and uses labeled context nodes to predict labels for query nodes.
  • 3.2 SYNTHETIC GRAPH PRIORS: Synthetic priors combine diverse random graph structures with controllable homophily, community patterns, densities, and causal feature-label relationships.The approach uses cSBMs and Erdős–Rényi networks, while structural causal models generate complex nonlinear feature-label dependencies.
  • 3.3 MODEL ARCHITECTURE: Each NodePFN layer has parallel context-query attention and local message-passing branches that learn from labeled examples and neighborhood structure.The attention branch lets test nodes use training information without influencing one another, while the message-passing branch captures local topology.
  • 3.3 MODEL ARCHITECTURE: The local MPNN branch uses normalized adjacency to aggregate neighborhood information and capture structural patterns across train/test splits.The implementation uses a GCN for this branch, with ˜A = D^-1/2AD^-1/2.
  • 3.4 HOW TO TRAIN: NodePFN is trained by minimizing expected cross-entropy on randomly partitioned synthetic graphs, then outputs posterior predictive distributions for unlabeled nodes.At inference, labeled nodes provide features and labels while test nodes provide features only; no gradient updates or fine-tuning are required.

4 EXPERIMENTS

Experiments across synthetic, real-world, training-free, structural, and ablation settings show that NodePFN generalizes across graph characteristics without dataset-specific training.

  • 4.1 (RQ1.) CONTROLLED SYNTHETIC GRAPHS: NodePFN maintains the best overall accuracy trend across controlled homophily rates, avoiding the low-homophily drops observed for GCN and GAT.Its prior data support stable performance in both homophily and heterophily settings.
  • 4.2 (RQ2.) EXPERIMENTS ON REAL-WORLD GRAPH BENCHMARKS: 71.27% average accuracy across 23 real-world benchmarks makes a single pre-trained NodePFN the best overall performer, including on homophily and heterophily datasets.GraphAny requires dataset-specific training yet underperforms and varies with the training dataset.
  • 4.3 (RQ3.) COMPARISON WITH TRAINING-FREE METHODS: NodePFN consistently outperforms training-free baselines on all evaluated datasets using a single pre-trained model.The comparison includes closed-form methods, label propagation, and TF-GNNs.
  • 4.4 (RQ4.) STRUCTURAL NODE CLASSIFICATION: NodePFN outperforms all baselines for structural node classification when node features are one-hot identifiers and topology supplies the primary signal.The Airport setting tests structural-role prediction without informative node features.
  • 4.5 (RQ5.) ABLATION STUDIES: Removing ER Networks or cSBM causes minimal degradation, whereas reducing capacity from 29.01M to 14.80M parameters lowers performance on Cora.NodePFN-L6 demonstrates that sufficient model capacity matters for at least some datasets.
  • 4.5 (RQ5.) ABLATION STUDIES: NodePFN outperforms TabPFN on all datasets, while TabPFN has wider accuracy variance and lower overall accuracy.This comparison supports graph-aware modeling rather than treating nodes as independent tabular examples.

5 RELATED WORK

Related work spans prior-fitted networks, graph foundation models built around language models, and GNNs for node classification.

  • Prior-data Fitted Networks: PFNs approximate posterior predictive distributions from synthetic-prior tasks and in-context examples, with TabPFN extending this paradigm to small tabular datasets.Related adaptations include time-series forecasting and graph-to-tabular approaches.
  • Graph Foundation Models: Graph foundation models commonly convert graphs or node features into text for LLM-based zero-shot or joint learning.Examples include GraphGPT, GraphLLM, LLAGA, OFA, GOFA, Graph-R1, and ZeroG.
  • GNNs for Node Classification: GNNs established strong node-classification performance on homophily graphs, but neighborhood aggregation struggles on heterophily graphs.Training-free GNNs remain suboptimal or inapplicable to some heterophily settings.

6 DISCUSSION

The discussion identifies scope and computational limitations while arguing that synthetic-prior pre-training can amortize costs across later inference tasks.

  • Limitations: NodePFN is limited to fixed maximum class numbers and feature dimensions used during training, and quadratic attention restricts large-scale graph applicability.The paper reports testing up to 20 classes and leaves these constraints for future work.
  • Advantages: Pre-training on approximately 250,000 synthetic graphs requires substantial computation, but that cost is amortized across subsequent inference tasks.This contrasts with conventional GNNs, which require retraining for each new dataset.
  • Scope: NodePFN targets structural patterns and accepts arbitrary numerical features without requiring semantic understanding from text-attributed graphs.This distinguishes its operating scope from graph foundation models relying on LLMs and text.

7 CONCLUDING REMARKS

The paper concludes that synthetic graph priors support universal node classification with a single model, while identifying efficient attention and semantic integration as future directions.

  • Conclusion: 71.27% average accuracy on 23 benchmarks supports universal node classification from synthetic graph priors, particularly against standard GNNs on heterophily graphs.The conclusion frames this as learning universal patterns without real-world training data.
  • Future Work: Future work should explore efficient attention for massive graphs and hybrid methods combining structural pattern learning with semantic processing.These directions address the stated limitations and text-attributed graph setting.
  • Reproducibility: The paper reports code, architecture, hyperparameters, hardware specifications, and synthetic-prior generation details to support reproducibility.The source code is provided through the project repository.

A DETAILS OF DATASETS

The dataset suite combines synthetic and real-world graph priors spanning homophily, heterophily, community structure, random connectivity, and nonlinear feature-label relationships. NodePFN is trained and evaluated across 23 benchmark datasets using these varied graph-generation mechanisms.

  • The Synthetic Cora Network: The synthetic Cora networks preserve 1,433 features, 1,480 nodes, 5,936 edges, and 5 classes across all homophily levels.
  • Real-world Graph Datasets: NodePFN evaluation covers 23 benchmarks, including 13 homophily graphs and 10 heterophilous graphs.Examples include Cora, Citeseer, Pubmed, WikiCS, Cornell, Texas, Squirrel, and Actor.
  • Implementation: The implementation contains approximately 29.1M trainable parameters and required 30 epochs, totaling 245,760 training steps and about six GPU hours.
  • Structural Causal Models (SCM): Structural causal models generate nonlinear feature-label dependencies by sampling random MLP architectures, layered DAGs, activations, noise, and dropout.Features and labels are selected from the causal graph, preserving causal structure for synthetic tabular-style relationships.
  • Contextual SBM and ER Network: Contextual SBMs connect labels and graph structure through controllable homophily, while ER networks provide graphs without inherent community structure.The training prior uses cSBMs and ER networks equally to cover community-based and random connectivity patterns.

B.4 FLEXIBLE ENCODER FOR VARIABLE NODE FEATURE DIMENSIONS

NodePFN standardizes graphs with different feature dimensionalities by padding smaller feature vectors to a shared maximum dimension and applying normalization before processing.

  • Flexible Encoder: NodePFN uses a flexible input encoder to handle node feature dimensionalities up to a predefined maximum capacity.
  • Padding and Normalization: Features with dimension d below dmax are zero-padded and rescaled with a normalization factor before entering the model.The normalization is intended to prevent padding from changing input scale or introducing bias.

B.5 FEATURE AND LABEL EMBEDDINGS IN IMPLEMENTATION

The implementation preprocesses graph structure and features, embeds observed labels with features, and evaluates using standardized dataset-specific splits and fixed ensemble settings.

  • Feature and Label Embeddings: Learnable projections map features and labels into the embedding dimension, where training-node feature and label embeddings are combined additively.Element-wise addition preserves constant dimensionality and supports complementary representations in different embedding subspaces.
  • Inference Preprocessing: Inference preprocessing normalizes adjacency matrices, ensembles 32 altered feature inputs, and optionally reduces oversized feature dimensions with truncated SVD.Feature smoothing may also be applied during preprocessing.
  • Evaluation Protocol: Evaluation uses semi-supervised splits for major homophily datasets and predefined split masks for heterophily datasets.Cora, Citeseer, and Pubmed use 20 training nodes per class, 500 validation nodes, and 1,000 test nodes.
  • Hyperparameters: The reported experiments use separate hyperparameter tables for homophily and heterophily datasets, with no truncated SVD on Tolokers and Minesweeper.

C PRIOR DATA SCALE ANALYSIS

The prior-data analysis examines how synthetic-graph scale affects NodePFN performance and computational efficiency. More prior data substantially improves Texas accuracy, while one-time synthetic pretraining supports immediate inference across future graphs.

  • Analysis Goal: The prior-scale study evaluates the trade-off between computational cost and performance gains when increasing the number of synthetic training graphs.
  • Prior Data Scale Results: Texas accuracy rises from approximately 53% to 76% as the amount of synthetic prior data increases.Cora shows more modest gains, indicating that higher-homophily patterns are learned more readily.
  • Computational Trade-off: Synthetic prior generation incurs an initial computational cost that is amortized across future inference tasks without graph-specific retraining.The analysis contrasts NodePFN’s one-time synthetic pretraining with traditional GNN retraining for each new graph.
  • Comparison Setup: TabPFN comparisons use a pretrained model with the same number of prior data points and default 32-ensemble feature preprocessing for fairness.
  • Theoretical Discussion: PFN theory states that prior-data negative log-likelihood training can approximate posterior predictive distributions and converge to the exact posterior under infinite capacity.The MPNN branch is described as adding structural information while preserving PFN’s Bayesian convergence properties.

F COMPARISON WITH HETEROPHILY-SPECIFIC GNNS

NodePFN generalizes across heterophilic graphs without real-world training data, outperforming specialized heterophily GNNs on most evaluated datasets. Additional comparisons show advantages over language-model-based and feature-smoothing baselines, while graph-prior mixtures affect performance.

  • Heterophily-specific GNNs: NodePFN achieves the best performance on 7 of 9 heterophily datasets despite using no real-world training data.H2GCN, GPRGNN, and FAGCN require dataset-specific training and heterophily-oriented aggregation schemes.
  • Heterophily-specific GNNs: NodePFN improves on Chameleon and Squirrel, while matching the best methods within 1% on Texas and Actor.The results support generalization across the heterophily spectrum without architectural modifications or dataset-specific tuning.
  • LLM-based graph methods: NodePFN achieves competitive or superior performance to LLM-based graph foundation models without text descriptions or language-model dependencies.NodePFN instead uses patterns learned from massive synthetic prior data.
  • Feature-smoothing baseline: NodePFN consistently improves over TabPFN-v1 with smoothed features on homophily datasets and substantially outperforms it on Cornell, Texas, and Wisconsin.The comparison attributes these gains to explicit graph-topology modeling through NodePFN’s dual-branch architecture; TabPFN-v1 is limited to 10 classes.
  • Synthetic graph-prior ablations: A balanced 50/50 mixture of ER and cSBM graphs consistently achieves optimal or near-optimal performance across homophily regimes.Heterophilic Wisconsin benefits from higher ER proportions in the 80–50% range, likely because ER topology adds structural diversity.

J ARCHITECTURAL ABLATIONS

Architectural ablations show that NodePFN depends on its parallel message-passing and attention design, sufficient depth, and computationally manageable graph processing. Removing message passing or reducing depth substantially harms performance, while deployment remains efficient across benchmarks.

  • Architectural components: Removing the MPNN branch substantially degrades performance on both homophilic Cora and heterophilic Wisconsin.The ablation indicates that message passing supplies structural inductive biases that pure attention does not capture.
  • Architectural components: NodePFN-Seq underperforms the parallel architecture, showing that combining the branches in parallel is important for their integration.The comparison is part of the dual-branch architectural ablation against the full NodePFN model.
  • Model capacity: Reducing the model to six layers causes failure on Cora, indicating that sufficient depth is needed to learn diverse patterns from synthetic priors.The result comes from the NodePFN-L6 architectural variant.
  • Computational analysis: NodePFN’s per-graph complexity is O(LEd + N^2d), combining MPNN message passing with all-node Transformer attention.The MPNN term matches standard GCN message-passing complexity, while the Transformer adds quadratic dependence on node count.
  • Runtime efficiency: Across 23 benchmark datasets, NodePFN achieves superior average accuracy and ranking while GCN requires 188 seconds of cumulative training plus 12.35 seconds of inference.The runtime comparison concerns total deployment cost and notes that GCN training is performed separately for each dataset.
Loading 2604.19028v1…