# Unraveling the Expressive Nature of Graph Neural Networks
Written on
Graph Neural Networks (GNNs) have emerged as a vital tool for applying learning algorithms to data structured as graphs. This series endeavors to elucidate the theoretical underpinnings of how GNNs effectively model the relational information inherent in network structures.
Introduction
Graphs serve as universal representations for modeling interactions among elements, and GNNs play a crucial role in processing graph-structured data. The primary framework for GNNs is grounded in the Message Passing Neural Network (MPNN) paradigm. Here, features from neighboring nodes are transmitted to a target node as messages via edges. Subsequently, the representation of the target node is refined using the aggregated features from its neighboring nodes.
This method allows the updated node representation to encapsulate information about its local structure. The message-passing mechanism is depicted in Figure 1.
Figure 1 illustrates how the orange node's representation is enhanced through the aggregation of its neighbors' features. Specifically, a single MPNN layer updates the orange node with the representations of the blue nodes, while adding another layer incorporates features from both blue and green nodes.
For simplicity, we focus solely on the orange node's aggregation, though this computation is performed simultaneously across all nodes, including blue and green nodes, whose representations are also updated with features from their neighbors.
The key variations among different MPNN models arise from the methods used to aggregate features for updating node representations. For instance, neighbor features can be combined using sum or average operations, as seen in Graph Convolutional Networks (GCNs) and GraphSage. Conversely, in Graph Attention Networks (GATs), an additional step involves weighting the contributions of each neighbor based on their significance.
Further insights into these updating and aggregation methods can be found in the following articles, which include practical Python code examples:
- Understanding the Building Blocks of Graph Neural Networks (Intro): An intuitive overview with running code to analyze and learn graph data using neural architectures.
- Graph Attention Networks Under the Hood: A detailed guide that transitions from mathematical concepts to implementation in NumPy.
Article Series Overview
A GNN model must possess the capability to generate distinct representations for graphs with varying structures while also encoding identical representations for graphs sharing the same relational structure. This series aims to elucidate this capability by providing foundational knowledge and showcasing practical code examples.
The series is structured as follows:
- The introductory article lays the groundwork, detailing how to represent graphs and discussing the fundamental concept of graph isomorphism, critical for understanding distinct versus equivalent relational structures.
- The second article explores the notions of equivariance and invariance, initially using image data and subsequently applying these concepts to graphs. Grasping these ideas will enhance our understanding of GNN model functionality from this viewpoint.
- The third article presents the Weisfeiler-Leman (WL) algorithm, a color refinement technique for testing graph isomorphism, and demonstrates its connection to the expressive capacity of GNNs.
- The fourth article conducts experiments to assess the expressiveness of various GNN models in graph classification tasks, synthesizing insights from the previous three articles.
Our journey begins with foundational concepts, focusing on graph representation through vectors, matrices, and tensors. We will then build intuition around graph isomorphism, transitioning from conceptual diagrams to formal definitions. Lastly, we will connect these concepts, explaining graph isomorphism concerning adjacency and permutation matrices.
Graph Representation
Graphs can be introduced as mathematical constructs for modeling relational data. Typically, a graph is defined as G = (V, E), where V denotes the set of vertices (or nodes), and E represents the set of edges.
For this series, we will introduce an additional dimension related to node features, leading to the notation G = (V, E, X), where X encompasses the numerical representation of node attributes. Figure 2 summarizes these components (colors are utilized to denote features):
In preparing graphs for GNN models, we can utilize various representations, such as an adjacency matrix that captures connectivity information alongside a feature matrix that describes node characteristics.
Additionally, these two representations can be integrated into a tensor, wherein features are allocated to the diagonal, while off-diagonal elements provide connectivity information. Further details can be found in Figure 3.
Graph Isomorphism
Graph isomorphism enables us to formally determine when two graphs exhibit identical structures. To illustrate this concept, consider the following image depicting two graphs, G and H.
> Are these two graphs, G and H, identical?
The answer is negative: the nodes do not share identical labels. Moreover, G resembles a path, while H appears as a bipartite graph.
> Do they share the same structure?
To address this query, we will pinpoint the essential characteristics that distinct graphs with the same structure share. Subsequently, we will illustrate how the definition of graph isomorphism captures these attributes.
Building Intuition Around Graph Isomorphism
We presume that two graphs are structurally identical if we can match each node of G to a node of H. Figure 5 clarifies this matching process, where a is paired with x, b with y, and c with z:
Next, the matched nodes must fulfill the same role within both graphs. To illustrate this point, let’s color the matched nodes consistently. The outcome is depicted in Figure 6.
Figure 6 clarifies how corresponding nodes assume identical roles in both graphs based on their connections (and non-connections) with other nodes. Specifically:
- The blue node has two neighbors: the yellow node and the green node.
- The yellow node has one neighbor: the blue node.
- The yellow and green nodes are not neighbors.
In summary, if two nodes are connected in graph G, their corresponding nodes in graph H should also be connected. Conversely, if nodes in G lack a connection, their counterparts in H should not be connected either.
A Touch of Formalism
The formal concept of isomorphism encapsulates the idea that certain objects share the same structure while disregarding the individual distinctions of their atomic components (the nodes, in this case). More specifically, the notion of graph isomorphism must encompass the following two characteristics:
- The one-to-one mapping of nodes between the two distinct graphs.
- The preservation of connections and non-connections for the corresponding nodes.
We can formalize this idea by stating that two graphs are isomorphic if a function ? maps the nodes from graph G to those of graph H. Figure 7 illustrates the details of this function in our specific example.
Next, we should analyze the unique properties of the function ?.
Initially, as depicted in Figures 8 and 9, two nodes in G cannot be mapped to the same node in H if we aim to maintain the same structure across two distinct graphs.
To enhance our understanding, we can view the process from an alternative angle: the function ? should inform us how to relabel the nodes of H to reconstruct graph G. Consequently, ? must map each distinct node of G to a different node of H. This property classifies ? as an injective function. According to Wikipedia:
> An injective function (also known as injection, or one-to-one function) maps distinct elements of its domain to distinct elements; that is, if x1 ? x2, then f(x1) ? f(x2).
Another essential characteristic of ? is that every node in H must correspond to a node in G. If a node in H lacks a corresponding node in G, then the two graphs cannot possess the same structure. This scenario is illustrated in Figure 10, where all nodes in G map to nodes in H, but the red node in H lacks a counterpart in G.
As Figure 10 illustrates, H contains one more node than G, indicating that the two graphs cannot share the same structure. The requirement that every node in H, or more broadly any element in the codomain, must be mapped makes ? a surjective function. Wikipedia defines surjective functions as follows:
> A surjective function (also known as surjection, or onto function) is one where every element y in the codomain has at least one element x in the domain such that f(x) = y.
Understanding the Complementary Nature of Properties
As previously mentioned, ? must be an injective function: each node in G should correspond to a distinct vertex in H. However, this does not automatically guarantee that every node in H is mapped to G (as seen in Figure 7). Therefore, ? must also be a surjective function, ensuring that every node in H is matched to a node in G. Surjectivity could allow for the mapping of one or more elements of G to the same node in H; however, as indicated in Figure 6, the injectivity property of ? prevents this situation.
The combination of these two properties results in a one-to-one correspondence between the nodes in both graphs, making ? a bijective function. Below is the definition from Wikipedia:
> A bijection, bijective function, or one-to-one correspondence between two sets is a function such that each element of the second set is paired with exactly one element of the first set.
Final Considerations Before Programming
Our discussion thus far has centered on the nodes of the graph.
> But what about the edges?
In our introductory remarks on the graph isomorphism problem, we also highlighted the significance of preserving the same connections (and the absence thereof) between matched nodes. More formally, our primary objective is to maintain adjacencies and non-adjacencies throughout this mapping process.
Interestingly, we can articulate this property using our function ?, as depicted in Figure 11.
According to this representation, any pair of nodes in graph G should be connected by an edge if and only if their corresponding nodes (obtained through applying ?) are also connected by an edge in graph H.
Let's compile all the elements related to nodes and edges in Figure 12.
If a function ? with the characteristics outlined in Figure 12 exists, then G and H are isomorphic graphs, and ? is an isomorphism. Formally:
> Two graphs, G and H, are isomorphic if there exists a bijection ?:V(G) ? V(H) such that uv ? E(G) if and only if ?(u), ?(v) ? E(H). In this scenario, we can denote: G ? H.
Graph Isomorphism Through Adjacency Matrices
In the preceding section, we emphasized that the concept of graph isomorphism necessitates the preservation of adjacencies and non-adjacencies among corresponding nodes. This implies that the adjacency matrix introduced at the beginning of this article plays a pivotal role.
To further clarify this concept, let's explicitly display the adjacency matrices for G and H, as shown in Figure 13.
We have relabeled our nodes using digits (1, 2, 3) in place of letters (a, b, c, or x, y, z) to simplify the matrix representation. This straightforward modification aids in linking the digit labels to their corresponding rows in the adjacency matrices.
From this example, it is evident that the two adjacency matrices differ, just as the graphs G and H do. Thus, the critical inquiry is:
> How can we define ? as a matrix?
Let’s explore this further. Figure 14 summarizes our mapping function using digits instead of letters.
Figure 15 delineates this mapping utilizing a matrix:
The matrix showcased in Figure 15 describes the mapping performed by ?, from the nodes of G to those of H. More specifically:
- The 1st row of the matrix represents node 1 in G. The 3rd element of this row is set to 1, indicating that node 1 of G corresponds to node 3 of H. The orange color illustrates this matching.
- The 2nd row represents node 2 in G. The 1st element of this row is set to 1, indicating that node 2 of G corresponds to node 1 of H. The blue color depicts this correspondence.
- The 3rd row signifies node 3 in G. The 2nd element of this row is set to 1, indicating that node 3 of G corresponds to node 2 of H. The green color reflects this mapping.
The matrix representing this transformation is also referred to as a Permutation matrix. As defined by Wikipedia:
> A permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column, with all other entries being 0. An n × n permutation matrix can represent a permutation of n elements.
We can describe the relationship between two isomorphic graphs in terms of adjacency and permutation matrices. This relationship is illustrated in Figure 16.
According to the formula, a graph G is isomorphic to H if and only if there exists a permutation matrix P such that the adjacency matrix of G can be derived by multiplying the permutation matrix P, the adjacency matrix of H, and the transpose of the permutation matrix P.
We can implement our findings using NumPy to solidify our understanding. First, we establish the adjacency matrices for G and H, along with our permutation matrix P:
A_G = np.array([[0, 1, 0], # Node 1
[1, 0, 1], # Node 2
[0, 1, 0]]) # Node 3
A_H = np.array([[0, 1, 1], # Node 1
[1, 0, 0], # Node 2
[1, 0, 0]]) # Node 3
P = np.array([[0, 0, 1], # From Node 1 to Node 3
[1, 0, 0], # From Node 2 to Node 1
[0, 1, 0]]) # From Node 3 to Node 2
Next, we will transpose the matrix P and perform the operations described in Figure 16.
P_t = np.transpose(P)
print(P_t) # Output: # array([[0, 1, 0], # [0, 0, 1], # [1, 0, 0]])
X = np.dot(np.dot(P, A_H), P_t)
print(X) # Output: # array([[0, 1, 0], # [1, 0, 1], # [0, 1, 0]])
np.array_equal(X, A_G) # Output: True
Our straightforward code demonstrates that G is isomorphic to H, with this isomorphism being described through the permutation matrix P and the adjacency matrices A_G and A_H.
Conclusion
This article has outlined how to ascertain that two graphs exhibit the same structure. This definition, termed graph isomorphism, is essential for developing GNN models capable of recognizing such cases and delivering identical representations for the two graphs. Conversely, it is equally vital for these models to provide distinct representations for non-isomorphic graphs.
In the subsequent article of this series, we will delve deeper into GNN architectures, focusing on permutation equivariance and invariance. Understanding these concepts will enable us to analyze the functioning of GNNs from this perspective and identify the principles necessary for developing more robust models.
References
- What are Isomorphic Graphs? | Graph Isomorphism, Graph Theory, video from Wrath of Math.
- Graph Theory FAQs: 03. Isomorphism Using Adjacency Matrix, video from Sarada Herke.
- Tutorial: Exploring the practical and theoretical landscape of expressive graph neural networks from Fabrizio Frasca, Beatrice Bevilacqua, and Haggai Maron at Learning on Graphs Conference 2022.
If you are interested in further exploring the intricacies of Graph Neural Networks, check out the following series on Graph Representation Learning: https://towardsdatascience.com/tagged/graphedm-series.
The author created all images featured in this article.