Canonical Graph Decomposition in Matching

belief propagation;probabilistic relaxation;graph decomposition;graph isomorphism

Yaghi, Haytham H ; Dr. Huaiyu Dai, Committee Member,Dr. Carla Savage, Committee Member,Dr. Hamid Krim, Committee Chair,Yaghi, Haytham H ; Dr. Huaiyu Dai ; Committee Member ; Dr. Carla Savage ; Committee Member ; Dr. Hamid Krim ; Committee Chair

University:North Carolina State University

关键词: belief propagation;    probabilistic relaxation;    graph decomposition;    graph isomorphism;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/1895/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

In the following thesis, we present our proposed probabilistic approach to the graph isomorphism problem. Through a "divide and conquer" approach, a graph is first decomposed into unique subgraphs, termed atoms, that are used to represent a decomposed graph as a bipartite attributed graph. We propose a modified probabilistic relaxation that simulates belief propagation and operates on the generated bipartite graph, yielding a match matrix that maps together isomorphic atoms fromdifferent graphs. Our proposed approach enforces a two way matching constraint thatguarantees a one-to-one match between isomorphic atoms. On average, the approach converges for isomorphic graphs and diverges for non-isomorphic graphs.