PF-GNN: Differentiable particle filtering based approximation of universal graph representations

Mohammed Haroon Dupty, Yanfei Dong, Wee Sun Lee

Abstract

Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. Other more expressive models either are computationally expensive or need preprocessing to extract structural features from the graph. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of Individualization and Refinement (IR), a method to artificially introduce asymmetry and further refine the coloring when 1-WL stops. Isomorphism solvers generate a search tree of colorings whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective. We take a probabilistic view and approximate the search tree of colorings (i.e. embeddings) by sampling multiple paths from root to leaves of the search tree. To learn more discriminative representations, we guide the sampling process with particle filter updates, a principled approach for sequential state estimation. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime. Experimental evaluation shows that our approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.

Introduction: Breaking the 1-WL Ceiling

Most modern Graph Neural Networks (GNNs) rely on a message-passing paradigm that is theoretically limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. This limitation means that standard GNNs cannot distinguish between certain pairs of non-isomorphic graphs because their local neighborhoods appear identical. While higher-order models like $k$-GNNs can overcome this, they suffer from a "curse of dimensionality," requiring exponential increases in memory and computation. PF-GNN addresses this challenge by bridging the gap between efficient message-passing and computationally expensive exact graph isomorphism solvers.

Methodology: Individualization, Refinement, and Particle Filtering

To achieve near-universal expressive power, PF-GNN draws inspiration from classical graph theory, specifically the Individualization and Refinement (IR) paradigm. This process involves:

  1. Individualization: Artificially breaking symmetry by assigning a unique label (color) to a specific node.
  2. Refinement: Running a standard 1-WL process (or GNN pass) to propagate this new information across the graph.
  3. Search Tree Generation: Repeatedly applying these steps creates a search tree where the leaves uniquely identify any graph.

Because the full search tree grows exponentially, PF-GNN treats the exploration as a sequential state estimation problem. Instead of exploring every branch, the model maintains $K$ "particles," each representing a specific path down the search tree (a sequence of individualized nodes).

The PF-GNN framework approximates the exponential search tree of colorings by sampling paths using a differentiable particle filter.

This framework uses a learnable policy to sample which nodes to individualize and an observation function to weight these particles, focusing the model's attention on the most discriminative paths. Crucially, the entire process—sampling, weighting, and refinement—is end-to-end differentiable, allowing the model to learn which nodes are most critical to individualize for a given task.

Experimental Evaluation

PF-GNN was evaluated across synthetic isomorphism benchmarks (SR25, EXP, CSL), graph property tasks (triangle counting), and real-world molecular datasets (ZINC, QM9, OGBG-MOLHIV).

The model demonstrated perfect isomorphism detection, achieving 100% accuracy on the SR25 and EXP datasets where standard backbones like GCN and GIN fail completely. Notably, on the SR25 dataset, PF-GNN outperformed PPGN (a 3-WL equivalent model), proving its ability to distinguish graphs that even some higher-order models cannot.

Performance comparison on SR25 and EXP datasets, showing PF-GNN achieving perfect accuracy where standard backbones fail.

In real-world applications, PF-GNN achieved a Mean Absolute Error (MAE) of 0.122 on the ZINC 10K benchmark, significantly outperforming standard GNNs and remaining competitive with specialized architectures like PNA and DGN.

Key Insights and Discussion

  • Probabilistic Pruning: By replacing hand-crafted heuristics with a data-driven "belief" distribution, the particle filter naturally down-weights paths that do not help distinguish graphs for the specific task.
  • Linear Scaling: Unlike $k$-GNNs, PF-GNN scales linearly with the number of refinement steps ($T$) and particles ($K$), making it practical for larger graphs.
  • Backbone Agnostic: PF-GNN acts as a wrapper that can enhance any standard GNN architecture (e.g., GIN, GAT) by serving as its refinement engine.

While the sampling-based approach introduces some variance and computational overhead (proportional to $K$), the results suggest that learned symmetry breaking is far more effective than simply increasing model depth or using random noise. Future work may explore more sophisticated resampling strategies and applications to even larger-scale relational datasets.

Summary updated

Abstract

Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. Other more expressive models either are computationally expensive or need preprocessing to extract structural features from the graph. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of Individualization and Refinement (IR), a method to artificially introduce asymmetry and further refine the coloring when 1-WL stops. Isomorphism solvers generate a search tree of colorings whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective. We take a probabilistic view and approximate the search tree of colorings (i.e. embeddings) by sampling multiple paths from root to leaves of the search tree. To learn more discriminative representations, we guide the sampling process with particle filter updates, a principled approach for sequential state estimation. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime. Experimental evaluation shows that our approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.
BibTeX
@inproceedings{dupty2022pf,
  author = {Mohammed Haroon Dupty and Yanfei Dong and Wee Sun Lee},
  title = {{PF-GNN: Differentiable particle filtering based approximation of universal graph representations}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=oh4TirnfSem},
}
Figure