- are essentially identical
- have the same same graph structure

The only differences that can be noted in Isomorphic graphs are that they can have a different ordering of the nodes in their adjacency matrix. This is because the ordering has no bearing on the structure of the graph, it is just an arbitrary decision in representing a graph using algebraic objects

University of Virginia, Charlottesville

The basic GNN can be derived as a neural network variation of the existing Weisfieler-Lehman (WL) isomorphism algorithm

GNNs and Graph Isomorphism

Anjalie Field, Su Lin Blodgett, Zeerak Waseem, and Yulia Tsvetkov. 2021. A Survey of Race, Racism, and Anti-Racism in NLP. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1905–1925, Online. Association for Computational Linguistics.

A Survey of Race, Racism, and Anti-Racism in NLP

Characteristics of Isomorphic Graphs:

Goal of Isomorphism Testing: declare whether or not two graphs are isomorphic

- Testing for graph isomorphism is fundamentally a hard problem
- Referred to as NP-indeterminate, no polynomial-time algorithms are known for the problem

Testing for Graph Isomorphism

1. The key distinction between GNN and WL.
2. The relationship between GNNs and the WL algorithm.

GNNs and the WL Algorithm

Graph isomorphism testing gives us a way to quantify the representational power of different learning approaches

Given 2 learned representations z_g1 and z_g2 for two corresponding graphs:
- a "perfect" algorithm would have z_g1 = z_g2 if and only if g1 is isomorphic to g2

However, there is no "perfect" representation learning algorithm, but there are several ways to connect it to graph isomorphism testing and approximate its power, such as the The Weisfieler-Lehman (WL) Algorithm

Learn Before

Related