PF-GNN: Differentiable particle filtering based approximation of
  universal graph representations
Mohammed Haroon Dupty Yanfei Dong Wee Sun Lee
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.