Practical graph isomorphism, II

By Brendan D. McKay, Adolfo Piperno. 2013

1,785 citations recorded by the source corpus.

We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and pro ving its validity, we explain how it is implemented in several of the key implementations. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Graph Learning

Citations in the corpus

Learning Convolutional Neural Networks for Graphs (2016, methodology): “To do so, we use N AUTY (McKay & Piperno, 2014).”
An End-to-End Deep Learning Architecture for Graph Classification (2018, methodology): “To ensure that isomorphic graphs are preprocessed to the same tensor, PATCHY-SAN first uses the WL algorithm and then leverages NAUTY, a graph canonization tool (McKay and Piperno 2014).”
GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders (2018, methodology): “The proposed method is formulated in the framework of variational au-toencoders (VAE) by Kingma & Welling (2013), although other forms of regularized autoencoders would be equally suitable (Makhzani et al., 2015; Li et al., 2015a).”
Probabilistic Symmetries and Invariant Neural Networks (2020, methodology): “In practice, some graph automorphism tools rely on canonical labeling algorithms, of which Nauty and Traces (McKay and Piperno, 2014) have demonstrated remarkably good performance.”
Weisfeiler-Lehman Neural Machine for Link Prediction (2017, methodology): “If there are vertices with the same color, we use Nauty, a graph canonization tool, to break the ties [20].”
Graphs Identified by Logics with Counting (2015, background): “In practice, due to its strength and the fact that it can be evaluated in almost linear time, the logic C(2) (more specifically, the corresponding 1-dimensional Weisfeiler-Lehman algorithm) is an essential subroutine in all competitive canonical labeling tools (see [20]).”
Deep Learning on Graphs: A Survey (2018, neutral): “Whether these methods can preserve order invariance depends on how the order is imposed, which is another research field that we refer readers to [87] for a survey.”
Efficient probabilistic grammar induction for design (2018, neutral): “In other domains, this problem is known as a subgraph isomorphism problem (McKay & Piperno, 2014), in which the task is to efficiently compare two subgraphs and determine if they are the same graph.”