Graph machine learning is a powerful approach for analyzing data structured as networks, from social connections to molecular structures. This guide covers the fundamentals, including what graphs are, how to represent them, and the machine learning techniques used to extract insights.
What is a Graph?
A graph is a collection of items, called nodes (or vertices), connected by links, called edges. Examples include social networks (users connected by friendships), molecules (atoms joined by bonds), and knowledge graphs (entities linked by relationships). Graphs can be homogeneous (same type of nodes and edges) or heterogeneous (different types). They can also be directed (e.g., Twitter follows) or undirected (e.g., chemical bonds).
Why Use Graphs?
Graphs model relationships and structures in many domains. Common tasks include:
- Graph-level: generating new molecules, predicting toxicity, or modeling system evolution.
- Node-level: predicting properties of individual nodes, such as in AlphaFold's 3D structure prediction.
- Edge-level: predicting missing links (recommendation systems) or edge properties (drug side effects).
- Subgraph-level: detecting communities in social networks or predicting traffic in navigation apps.
Tasks can be transductive (predict on the same graph used for training) or inductive (predict on new, unseen graphs).
Graph Representations
Graphs are typically stored as an edge list or an adjacency matrix. Importantly, graphs are permutation-invariant: shuffling the order of nodes or edges does not change the graph. This property is key to designing machine learning models that respect graph structure.
Graph Representations Through ML
Early methods relied on hand-crafted features, like node degrees or clustering coefficients. Later, walk-based approaches (e.g., DeepWalk, Node2Vec) learned node embeddings by simulating random walks and applying word2vec-like techniques. These methods capture local and global graph structure but are not easily transferable to new graphs.
Graph Neural Networks (GNNs)
GNNs learn node representations through message passing and aggregation. Each node updates its representation by combining its own features with those of its neighbors. Common steps:
- Message: each neighbor sends its feature vector.
- Aggregate: combine incoming messages (e.g., sum, mean, max).
- Update: combine the aggregated message with the node's current features.
GNNs can be shallow (few layers) to avoid over-smoothing, where node representations become too similar. Popular architectures include Graph Convolutional Networks (GCN), Graph Attention Networks (GAT), and GraphSAGE.
Graph Transformers
Inspired by Transformers in NLP, Graph Transformers apply attention mechanisms to graph nodes. They often require positional encodings to capture graph structure and can handle long-range dependencies better than GNNs. Examples include the Graph Transformer and SAN (Spectral Attention Network).
Further Learning
This overview scratches the surface. For deeper study, explore resources on spectral methods, graph pooling, and scalable GNNs. Graphs are everywhere—understanding them opens doors to countless applications.