Department of Computer Science, Technion-Israel Institute of Technology, Taub Building, Haifa 32000, Israel.
IEEE Trans Pattern Anal Mach Intell. 2013 Aug;35(8):1985-93. doi: 10.1109/TPAMI.2012.260.
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.
在两个图之间的同构是它们的顶点集之间保持连通性的双射映射。在应用科学中，发现图之间或图与其自身之间（自同构）的同构非常重要。这个问题的内在计算复杂性尚不清楚。在这里，我们引入了一种使用与图拉普拉斯相关的热核来计算这种映射的有效方法。虽然这个问题本质上是组合性的，但在实践中，我们在顶点数量方面的运行时间是多项式的。正如我们所展示的，所提出的方法可以处理各种类型的图，并且在各种重要的示例上与最先进的软件包具有竞争力。
