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.

通过引导学习过程的精确同构求解器技术，我们的算法使消息传递图神经网络具有通用性，通过从根到叶子节点的搜索树中采样多个路径，并结合粒子滤波更新来学习更具辨别性的表示，从而在运行时间仅线性增加的情况下，在同构检测的合成基准和真实世界数据集上始终优于领先的图神经网络模型。