Graph Isomorphism

#Graph #Basics

For two graphs, $\mathcal G$ and $\mathcal H$, the two graphs are isomorphism on the following condition

$$ u, v \text{ adjacent in } G \iff u, v \text{ adjacent in } H. $$

An algorithm to find approximate isomorphism is the Weisfeiler Lehman Method Weisfeiler-Lehman Kernel The Weisfeiler-Lehman kernel is an iterative integration of neighborhood information. We initialize the labels for each node using its own node degree. At each step, we take the neighboring node degrees to form a multiset. At step $K$, we have the multisets for each node. Those multisets at each node can be processed to form an representation of the graph which is in turn used to calculate statistics of the graph. Iterate $k$ steps This iteration can be used to test if two graphs are … .

Published: by ;

L Ma (2021). 'Graph Isomorphism', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-isomorphism/.

Current Ref:

  • cards/graph/graph-isomorphism.md