Graph Neural Networks (GNNs) are at the forefront of AI innovation, helping us understand and generate complex relational data. This post dives into three fundamental concepts defining the power and utility of GNNs: Expressiveness, Link Prediction, and Graph Generation.
1. Defining GNN Expressiveness: The WL Test Limit
Expressiveness is the metric that measures how well a GNN can distinguish between different graph structures. The primary goal of a GNN is to generate similar embeddings for similar nodes and different embeddings for different nodes.
The gold standard for determining a GNN’s distinguishing power is its connection to the Graph Isomorphism Problem , which asks whether two graphs have the same connectivity structure.
The Weisfeiler-Leman (WL) Test
The Weisfeiler-Leman (WL) Test is an algorithm designed to address the graph isomorphism problem and is considered the theoretical upper bound for the expressive power of many GNNs.
How the WL Test Works:
Initial Coloring: All nodes are initially assigned the same color.
Color Aggregation: Each node collects and aggregates the colors of itself and its neighbors (e.g., using a Sum Aggregator).
New Color Generation: The aggregated result is input into a hash function to generate a new color.
Iteration: Steps 2 and 3 are repeated until the node colors no longer change.
If two graphs do not share the same final set of colors, they are considered non-isomorphic. The WL test can distinguish more graph structures than other methods.
Graph Isomorphism Network (GIN)
The Graph Isomorphism Network (GIN) is a GNN architecture designed to have the same expressive power as the WL test. Its aggregation and combination steps mimic the iterative coloring of the WL test:
Graph Classification and Readout
Graph Classification is the task of predicting a property of an entire graph by transforming the node embeddings produced by a GNN into a single graph embedding. This is done using a Global Pooling or Readout function.
2. Link Prediction: Forecasting Future Connections
Link Prediction is the problem of predicting whether a link (edge) exists or will exist between two nodes.
Traditional Link Prediction Methods
Traditional approaches rely on heuristics and matrix decomposition:
Heuristic Methods
Local Heuristics (1-hop or 2-hop):
Common Neighbors: Measures the number of neighbors shared by two nodes.
Jaccard’s Coefficient: Measures the proportion of common neighbors.
Adamic-Adar Index: Sums the inverse of the log of the degree of common neighbors, assigning less importance to common neighbors with many connections.
Global Heuristics:
Katz Index: Calculates the weighted sum of all possible paths between two nodes, penalizing longer paths.
Matrix Factorization (MF)
This method learns node embeddings Z to approximate the entire adjacency matrix A. The goal is to maximize the inner product of embeddings for similar nodes and minimize it for dissimilar node.
GNN-based Link Prediction Models
Graph Autoencoder (GAE)
The GAE uses a GNN (e.g., a two-layer GCN) as an Encoder to generate node embeddings .
A Decoder then approximates the adjacency matrix A hat using a sigmoid function on the inner product of the embeddings:
Variational Graph Autoencoder (VGAE)
VGAE is a probabilistic variant of GAE. Instead of learning Z directly, it learns the parameters (mean and variance) of a latent normal distribution that Z follows. Embeddings are sampled from this learned distribution, and the loss function includes the Kullback-Leibler (KL) Divergence term to ensure the output distribution is close to a prior distribution.
SEAL (Subgraphs, Embeddings, and Attributes for Link prediction)
SEAL focuses on local connectivity by using enclosing subgraphs as input instead of the entire graph. This approach automatically learns local heuristics.
Enclosing Subgraph Extraction: Lists the target nodes and their k-hop neighbors and extracts their edges and features.
Node Labeling (DRNL): The Double-Radius Node Labeling (DRNL) algorithm generates a single integer label that captures the structural importance of each node by encoding its distances from both target nodes x and y.
3. Graph Generation: Creating New Network Structures
Graph Generation models are crucial for applications like data augmentation, anomaly detection, and drug discovery. They can be categorized into realistic generation (mimicking existing graphs) and goal-directed generation (optimizing a specific metric).
Traditional Graph Generation Methods
Erdos-Renyi Model (G(n, p) or G(n, M)): Assumes each edge exists independently with probability p or chooses a graph with M edges randomly. A limitation is the difficulty in mimicking real-world graphs with clusters or communities due to the independence assumption.
Small-World Model (Watts-Strogatz Model): Captures the real-world features of short path length and high clustering coefficient. It starts with a regular lattice and randomly rewires some edges with probability p to introduce shortcuts. Its limitations include a fixed number of nodes and difficulty creating realistic degree distributions.
GNN-based Deep Graph Generation Models
Variational Autoencoder (VAE) Models
VGAE can be used for generation: it stores the structural information of the original graph in a probabilistic distribution45. A new graph is created by sampling from this distribution and setting a threshold to create a binary adjacency matrix.
Constrained Graph Variational Autoencoder (CGVAE): Extends VGAE to learn more complex graphs G=(A, E, F) that include the adjacency tensor A, edge attribute tensor E, and node feature matrix F. It can generate graphs with specific conditions (e.g., valid molecular structures) by adding constraints or regularization.
Autoregressive Models
These models view graph generation as a sequential decision-making process. At each step, the model creates a new node or link, and the resulting partial graph becomes the input for the next step.
GraphRNN: Uses two Recurrent Neural Networks (RNNs):
Graph-level RNN: Generates a new node and sets its initial state52.
Edge-level RNN: Predicts the probability of the new node connecting to existing nodes, filling in the adjacency matrix row by row53.
Generative Adversarial Networks (GANs)
GANs use a zero-sum game framework where a Generator and a Discriminator compete.
Generator: Creates new graph data that resembles the training data.
Discriminator: Distinguishes whether a sample is a real graph or a fake one created by the generator.
MoIGAN (molecular GAN): Combines the Wasserstein GAN (WGAN), which improves training stability, with a Reinforcement Learning (RL) objective to generate molecules with desired chemical properties.
Generator: Outputs the Adjacency tensor (A, edge/bond types) and the Annotation matrix (X, node/atom types).
Reward Network: Scores each generated graph based on a real-world score (e.g., from RDKit), providing a reward for generating a molecule that meets the desired chemical characteristics.
