A Message-Passing Algorithm for Graph Isomorphism

2017/04/03 by M. Mansour, Mansour, Mohamed
Computer Science · #Advanced Graph Neural Networks #Caching and Content Delivery #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1704.00395

openalex publication_date 2017/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A message-passing procedure for solving the graph isomorphism problem is proposed. The procedure resembles the belief-propagation algorithm in the context of graphical models inference and LDPC decoding. To enable the algorithm, the input graphs are transformed into intermediate canonical representations of bipartite graphs. The matching procedure injects specially designed input patterns to the canonical graphs and runs a message-passing algorithm to generate two output fingerprints that are matched if and only if the input graphs are isomorphic.

Related

• Recent Advances on the Graph Isomorphism Problem
• Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching
• Graph isomorphism and automorphism problems are polynomial
• Practical graph isomorphism, II
• The direct algorithm for solving of the graph isomorphism problem