Graph isomorphisms and automorphisms via spectral signatures.
Where this comes from
- Record sourced from PubMed, PMID 23787348.
- Also identified by DOI 10.1109/TPAMI.2012.260.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
An isomorphism between two graphs is a connectivity preserving bijective mapping between their sets of vertices. Finding isomorphisms between graphs, or between a graph and itself (automorphisms), is of great importance in applied sciences. The inherent computational complexity of this problem is as yet unknown. Here, we introduce an efficient method to compute such mappings using heat kernels associated with the graph Laplacian. While the problem is combinatorial in nature, in practice we experience polynomial runtime in the number of vertices. As we demonstrate, the proposed method can handle a variety of graphs and is competitive with state-of-the-art packages on various important examples.