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

Mohammed Haroon Dupty, Yanfei Dong, Wee Sun Lee

Overview

PF-GNN (Particle Filter Graph Neural Network) overcomes the fundamental expressivity limits of standard Graph Neural Networks (GNNs) by mimicking exact graph isomorphism solvers. It uses a differentiable particle filtering framework to efficiently sample and weight paths through a "search tree" of graph colorings, enabling the model to distinguish complex graph structures that standard models cannot.

The Expressivity Bottleneck of GNNs

Most modern GNNs follow a "message-passing" paradigm. While highly successful in many domains, researchers have proven that these models are fundamentally limited: they are at most as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) color-refinement test. This means there are many pairs of non-isomorphic (structurally different) graphs that a standard GNN will see as identical because of their inherent structural symmetry.

To go beyond the 1-WL limit, researchers have previously proposed $k$-GNNs (based on higher-order WL tests), but these are computationally expensive and struggle to scale to large graphs. Conversely, exact combinatorial algorithms use a technique called Individualization and Refinement (IR) to break symmetry. By picking a node and giving it a unique "color," they can distinguish any graph. However, this process creates an exponentially large search tree of possible colorings, making it traditionally incompatible with deep learning.

The PF-GNN Approach

The authors introduce PF-GNN, which treats the search for a unique graph representation as a sequential state estimation problem.

The search tree of graph colorings generated by Individualization and Refinement. PF-GNN uses particle filtering to sample paths through this tree.
  1. Individualization and Refinement (IR): The model starts with standard 1-WL embeddings. It then "individualizes" a node (assigns it a unique feature) and "refines" the rest of the graph's embeddings using standard message passing.
  2. Differentiable Particle Filtering: Instead of exploring the entire exponential search tree, PF-GNN maintains a set of $K$ "particles." Each particle represents a single path (a sequence of individualized nodes) from the root of the search tree toward a leaf.
  3. Learned Policy & Observation:
    • A transition policy (learned via REINFORCE) decides which nodes are most "useful" to individualize to break symmetry.
  4. An observation function weights each particle based on how discriminative its current refinement is.
  5. Differentiable Resampling: To focus on the most promising paths, the model uses a "soft-resampling" step. This allows the entire pipeline to remain end-to-end differentiable.
  6. Backbone Agnostic: PF-GNN can be wrapped around any existing GNN (like GCN, GAT, or GIN), acting as a "power-up" for its expressivity.

Key Insights

  • Bridging Algorithms and Learning: The core breakthrough is realizing that the search tree used by exact solvers can be approximated using Particle Filtering. This brings the power of exact combinatorial algorithms into the differentiable world of deep learning.
  • Linear Scaling for Higher Power: While $k$-WL tests scale polynomially ($O(n^k)$), PF-GNN's complexity increases only linearly with the depth of the search tree ($T$) and the number of particles ($K$).
  • Learning to Prune: By training the policy and observation functions, the model effectively learns how to prune the search tree, focusing only on the node sequences that best distinguish the graph's unique structure.

Performance Highlights

The authors evaluated PF-GNN across a wide range of tasks, including isomorphism detection, graph classification, and real-world molecular benchmarks.

Performance on the SR25 isomorphism detection benchmark, showing PF-GNN achieving perfect 100% accuracy compared to standard GNNs.
  • Perfect Isomorphism Detection: PF-GNN achieved 100% accuracy on the notoriously difficult SR25 (Strongly Regular graphs) dataset, as well as EXP and CSL datasets. Notably, it outperformed PPGN (a 3-WL equivalent model) on the SR25 benchmark.
  • State-of-the-Art on Molecules: On the ZINC 10K dataset, PF-GNN achieved a Mean Absolute Error (MAE) of 0.122, significantly outperforming strong baselines like PNA (0.187) and DGN (0.168).
  • Fundamental Properties: While standard GIN models failed (near 50-60% accuracy) on connectivity and planarity tests, PF-GNN achieved near-perfect scores (97-99%).
  • Generalization: The model showed a remarkable ability to generalize. For example, on the TRIANGLES dataset, it performed significantly better on larger, unseen graphs compared to standard baselines.

Limitations and Future Directions

While the scaling is linear, running $K$ particles for $T$ steps is still $K \times T$ times more computationally expensive than a single GNN pass. The authors note a runtime increase of roughly 2x to 4x for typical settings. Additionally, as a sampling-based method, the model's performance can depend on the number of particles ($K$). Finding the optimal balance between performance and compute remains a practical challenge.

Future work may explore more sophisticated particle filter variants or apply this framework to even larger-scale graph datasets where structural symmetry is a major hurdle.

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 $\textit{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 $\textit{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