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

**Authors:** Mohammed Haroon Dupty, Yanfei Dong, Wee Sun Lee  
**arXiv:** [2401.17752](https://arxiv.org/abs/2401.17752)  
**Date:** 2024-01-31  
**Summary page:** https://www.summarizepaper.com/en/paper/2401.17752v1/

## Key points

- Message passing Graph Neural Networks (GNNs) have limitations in expressive power for graph isomorphism due to constraints of 1-WL color-refinement test
- Authors propose enhancing GNN universality by incorporating exact isomorphism solver techniques based on Individualization and Refinement (IR) principles
- Isomorphism solvers generate a search tree of colorings, but exponential growth necessitates hand-crafted pruning techniques
- Authors adopt a probabilistic viewpoint, approximating the search tree by sampling multiple paths guided by particle filter updates
- Algorithm is end-to-end differentiable, seamlessly integrated with any GNN backbone for richer graph representations with linear increase in runtime
- Experimental evaluations show their approach consistently outperforms leading GNN models on synthetic benchmarks and real-world datasets

## Summary

In their paper titled "PF-GNN: Differentiable particle filtering based approximation of universal graph representations," authors Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee address the limitations of message passing Graph Neural Networks (GNNs) in terms of expressive power when it comes to graph isomorphism. GNNs are often constrained by the 1-WL color-refinement test for graph isomorphism, while other more expressive models either require significant computational resources or preprocessing to extract structural features from graphs. To overcome these limitations, the authors propose a novel approach to enhance the universality of GNNs by incorporating exact isomorphism solver techniques. These techniques operate on the principles of Individualization and Refinement (IR), which involve artificially introducing asymmetry and refining coloring beyond the constraints of 1-WL. Isomorphism solvers generate a search tree of colorings that uniquely identify graphs; however, the exponential growth of this tree necessitates hand-crafted pruning techniques that may not be ideal from a learning perspective. In their work, the authors adopt a probabilistic viewpoint and approximate the search tree of colorings (or embeddings) by sampling multiple paths from the root to leaves of the tree. To further enhance discriminative representations, they guide this sampling process using particle filter updates—a principled method for sequential state estimation. Importantly, their algorithm is end-to-end differentiable and can be seamlessly integrated with any GNN as a backbone, resulting in richer graph representations with only a linear increase in runtime. Experimental evaluations demonstrate that their approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection and real-world datasets. The paper was published as a conference paper at ICLR 2022, showcasing its significance in advancing the field of graph representation learning and isomorphism detection.