Member-only story
Weisfeiler Leman Graph Isomorphism with Molecular Graphs
Graph Neural Networks (GNNs) represent a significant advancement in neural network architectures, specifically tailored to learn vector representations of nodes and entire graphs within a supervised, end-to-end learning framework. However, after careful studies from several authors it has been shown that capabilities of GNNs are in relation to the one-dimensional Weisfeiler-Leman (1-WL) graph isomorphism heuristic. GNNs exhibit an expressive power equivalent to that of the 1-WL heuristic in discerning non-isomorphic subgraphs.
Before diving deep first lets understand what is Graph Isomorphism
Two graphs G and G’ are isomorphic if there exists a matching between their vertices so that two vertices are connected by an edge in G if and only if corresponding vertices are connected by an edge in G’. The graph isomorphism problem asks whether two graphs are topologically identical. This is a challenging problem: no polynomial-time algorithm is known for it yet been. The following diagram makes it much more simple — both these graphs are isomorphic.
What about this ?
