Introduction to Graph Machine Learning

Graph Machine Learning (GraphML) enables the analysis of data structured as items linked by relations, allowing for predictions at the graph, node, edge, and subgraph levels. This field is critical for applications ranging from drug discovery and molecular toxicity prediction to social network community detection and traffic estimation in itinerary systems.

Fundamental Graph Concepts

A graph consists of nodes (or vertices) and edges (or links). Depending on the nature of the data, graphs are categorized by several characteristics:

Homogeneous vs. Heterogeneous: Homogeneous graphs contain nodes and edges of a single type. Heterogeneous graphs have typed nodes or edges (e.g., a citation network with both authors and papers) and require additional information beyond topology for representation.
Directed vs. Undirected: Directed graphs (e.g., follower networks) have edges with a specific direction, while undirected graphs (e.g., molecules) have bidirectional relations.
Representation: Graphs are typically represented as a set of edges or as an adjacency matrix, a square matrix where a value of 1 indicates a connection between two nodes.

Crucially, graphs differ from sequences (text/audio) or grids (images) because they are not ordered objects. Shuffling the edge list or the columns of an adjacency matrix does not change the underlying graph, a property known as permutation invariance.

Graph Learning Tasks

Machine learning on graphs is applied across four primary levels of granularity:

Graph Level: Includes graph generation (e.g., for drug discovery), graph evolution prediction (e.g., in physics), and graph-level prediction (e.g., predicting molecular toxicity).
Node Level: Focuses on node property prediction, such as AlphaFold's use of node properties to predict the 3D coordinates of atoms in a molecule.
Edge Level: Involves edge property prediction (e.g., drug side effect prediction) or missing edge prediction (e.g., recommendation systems).
Subgraph Level: Focuses on community detection in social networks or subgraph property prediction for estimated times of arrival in systems like Google Maps.

These tasks are performed in either a transductive setting (training and testing on a single graph) or an inductive setting (using separate graphs for training, validation, and testing).

Evolution of Graph Representations

Pre-Neural Approaches

Before the advent of neural networks, graph representations relied on engineered features:

Node-level features: Centrality (importance), degree (number of neighbors), and clustering coefficients (neighbor connectivity).
Edge-level features: Shortest distance between nodes, common neighbors, and the Katz index (number of walks up to a certain length).
Graph-level features: Total graphlet counts and kernel methods that measure similarity via "bag of nodes" approaches.

Walk-based approaches, such as Node2Vec, use random walks to define similarity metrics and compute embeddings via skip-gram models. However, these methods cannot generate embeddings for new nodes and fail to capture fine structural similarities or utilize additional node features.

Graph Neural Networks (GNNs)

To generalize to unseen data, GNNs are designed to be permutation invariant (the output is the same regardless of node ordering) and permutation equivariant (permuting nodes results in a corresponding permutation of their representations).

A GNN layer functions through message passing and aggregation: a node's representation is updated by aggregating the representations of its neighbors and itself from the previous layer.

Notable GNN architectures include:

Graph Convolutional Networks (GCNs): Average the normalized representations of neighbors.
Graph Attention Networks (GATs): Use attention mechanisms to weigh neighbors based on importance.
GraphSAGE: Samples neighbors at different hops and aggregates information using max pooling.
Graph Isomorphism Networks (GINs): Apply an MLP to the sum of neighbor representations.

The Oversmoothing Problem

As GNNs add layers, each node's representation aggregates information from a wider radius. If the number of layers exceeds the graph's diameter, node representations may converge to the same value, a phenomenon called oversmoothing. This is mitigated by limiting layer depth, increasing layer complexity, adding non-message passing layers (like MLPs), or implementing skip-connections.

Graph Transformers

Because Transformers are naturally permutation invariant and scale effectively, they are being adapted for graphs to overcome GNN limitations like oversmoothing and scaling to dense graphs. Key developments include:

Graphormer: Uses node features as query/key/values in attention and incorporates centrality, spatial, and edge encodings.
TokenGT: Represents graphs as a sequence of node and edge embeddings augmented with identifiers, removing the need for positional embeddings.
GraphGPS: A framework that combines message passing networks with linear long-range transformers to create hybrid networks.
Spectral Attention Networks (SANs): Combine node features with learned positional encoding derived from Laplacian eigenvectors/values.

Other notable methods include the Graph Encoder for graph-to-sequence learning and the GRPE (Graph Relative Positional Encoding) Transformer.