Graph Learning2017intermediate9 min read

Inductive Representation Learning on Large Graphs

تعلُّم التمثيلات بأسلوب استقرائي على البيانات البيانية الضخمة

Hamilton, W. L. · Ying, Z. · Leskovec, J. — NeurIPS

The problem

Most graph methods before GraphSAGE — DeepWalk, node2vec, LINE — are transductive: they learn a fixed embedding for every node during , and cannot generalize to unseen nodes. If a new user joins a social network or a new protein is discovered, the entire must be retrained from scratch. Real-world graphs grow continuously, making transductive methods impractical at scale.

The contribution

GraphSAGE (SAmple and aggreGatE): an inductive framework that learns how to compute an embedding from a node's local neighborhood, rather than memorizing an embedding per node. At each , a fixed-size sample of neighbors is drawn, their features are aggregated through a learnable function (mean, , or max-), and the result is concatenated with the node's own . Because the aggregation function is what gets trained — not the embeddings — it generalizes to entirely unseen nodes at time.

The impact

GraphSAGE was the first framework to demonstrate scalable inductive learning on graphs with millions of nodes. It directly enabled PinSage at Pinterest — the first industrial-scale GNN — and laid the groundwork for virtually every modern GNN framework. Its sample-and-aggregate paradigm remains the dominant design pattern in graph learning.

Imagine you arrive at a large conference. Previous methods gave every attendee a pre-printed name badge — but if someone new walks in, there's no badge for them. You'd have to reprint the entire batch.

GraphSAGE takes a different approach: instead of badges, it teaches you a recipe — "look at the 5 people this person is talking to, note what they're wearing and what topics they discuss, and from that, describe who this person is." The recipe works for anyone, even someone who just walked through the door.

The problem: transductive embeddings cannot grow

By 2017, graph embedding methods like DeepWalk and node2vec had shown that encoding graph structure into low-dimensional vectors enables powerful downstream predictions — link prediction, , community detection. But they all shared a fundamental limitation:

Transductive. Each node gets its own learned embedding vector, stored in a lookup table. At inference time, if a node wasn't in the training graph, it has no embedding. You must retrain from scratch.
No leverage. These methods ignore node features (text profiles, molecular properties, metadata). They learn purely from graph topology, wasting rich attribute information.
No sharing. The number of parameters scales linearly with the number of nodes — a graph with 100 million nodes needs 100 million embedding vectors. This is neither memory-efficient nor generalizable.

What was needed was a model that learns how to build embeddings from local structure and features — a function, not a table.

Open in Lab

Left: transductive methods store a lookup table — new nodes have no entry. Right: GraphSAGE learns an aggregation function that works on any node.

The demo wakes as you arrive…

The core idea: sample neighbors, aggregate features

GraphSAGE's insight is simple and powerful: a node's identity is largely determined by its neighborhood. Instead of a lookup table, learn a function that takes a node's own features and the features of its sampled neighbors, and produces an embedding. The function — not the embedding — is what gets trained.

The forward pass for one layer works in three steps:

Sample a fixed number of neighbors for each node (e.g., 25 at the first hop, 10 at the second).
Aggregate the sampled neighbors' representations using a learnable aggregator (mean, LSTM, or pooling).
Combine the aggregated neighborhood with the node's own representation, apply a and nonlinearity, then normalize.

Stack $K$ such layers and each node's final embedding encodes information from its $K$ -hop neighborhood — but computed from features and a shared function, not from a memorized table.

Open in Lab

Click on any node to see how GraphSAGE samples neighbors at each hop and aggregates their features step by step.

The demo wakes as you arrive…

The aggregation formula

Before we write the math, let's be clear about what it's doing in words. Each layer takes a node's current representation and the representations of its sampled neighbors, compresses the neighbors into a single summary vector, concatenates that summary with the node's own vector, multiplies by a learnable weight matrix, applies a nonlinearity, and normalizes to unit length. The result is the node's updated representation for the next layer.

\mathbf{h}_v^{(k)} = \sigma\!\left(\mathbf{W}^{(k)} \cdot \text{CONCAT}\!\left(\mathbf{h}_v^{(k-1)},\; \text{AGG}\!\left(\left\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\right\}\right)\right)\right)

GraphSAGE forward propagation — the sample-and-aggregate engine — h_v^(k) = node v's representation at layer k · AGG = a learnable aggregator (mean, LSTM, or pooling) · CONCAT = preserves the node's own identity separate from its neighborhood · W^(k) = learnable weight matrix · σ = nonlinearity (ReLU)

Notice the CONCAT — this is a deliberate design choice. GCN-style architectures average a node with its neighbors, which blurs the node's own signal into the neighborhood signal. GraphSAGE keeps them separate: the node's own features always travel through a dedicated pathway, preserving self-identity. After each layer, the representation is $\ell_2$ -normalized to keep embeddings on a unit sphere and prevent instability.

Why sample? Taming the exponential neighborhood

Real-world graph nodes can have hundreds or thousands of neighbors. If we aggregate over the full neighborhood at every layer, the computational cost explodes: for $K$ layers, the grows as $O(d^K)$ where $d$ is the average degree. A two-layer model on a graph with average degree 100 would touch 10,000 nodes per target node.

GraphSAGE solves this by uniform random : at layer $k$ , each node draws exactly $S_k$ neighbors. The paper uses $S_1 = 25$ (first hop) and $S_2 = 10$ (second hop), capping the receptive field at $25 \times 10 = 250$ nodes per training example — regardless of the true degree. This transforms the cost from degree-dependent to constant, enabling mini-batch training on graphs with millions of nodes.

Open in Lab

Drag the sample-size sliders to see how the computational tree grows or shrinks. Notice how fixing S₁ and S₂ caps the total nodes.

The demo wakes as you arrive…

Three aggregator designs

The AGG function is the heart of GraphSAGE — it compresses a variable-size set of neighbor representations into a single fixed-size vector. The paper proposes three options:

Mean aggregator — element-wise mean over all sampled neighbor representations. Simple and fast. If you skip the CONCAT step and instead average the node with its neighbors, you recover something very close to GCN. So the mean aggregator with CONCAT is a strict generalization of GCN — inductive and with the node's self-representation preserved.

LSTM aggregator — an LSTM applied to a random permutation of the neighborhood. LSTMs have more expressive capacity than simple means, but neighborhoods have no natural ordering, so the permutation is random. Empirically it still outperforms mean on some tasks.

Pooling aggregator — each neighbor is passed through a fully-connected layer, then element-wise max-pooling is applied. The linear transform before pooling lets each neighbor "highlight" its most relevant features, and max-pooling captures the strongest signal. This is often the best-performing aggregator.

\text{AGG}_{\text{pool}} = \max\!\left(\left\{\sigma\!\left( \mathbf{W}_{\text{pool}}\,\mathbf{h}_u^{(k-1)} + \mathbf{b}\right) : u \in \mathcal{N}^{S}(v)\right\}\right)

Pooling aggregator — the strongest signal wins — Each neighbor is transformed by a learnable matrix W_pool + bias b, then passed through a nonlinearity σ. Max-pooling captures the highest-activated feature across all neighbors.

Open in Lab

Toggle between the three aggregator types to see how each one compresses neighbor features into a single vector.

The demo wakes as you arrive…

Training: supervised and unsupervised modes

GraphSAGE can be trained in two settings. In supervised mode, the standard cross-entropy on labeled nodes drives training end-to-end. In unsupervised mode, a graph-based loss encourages nearby nodes (co-occurring in random walks) to have similar embeddings and distant nodes to have dissimilar ones — essentially adapting the idea from node2vec to the inductive setting.

J(\mathbf{z}_u) = -\log\sigma(\mathbf{z}_u^\top \mathbf{z}_v) - Q \cdot \mathbb{E}_{v_n \sim P_n}\!\left[\log\sigma( -\mathbf{z}_u^\top \mathbf{z}_{v_n})\right]

Unsupervised loss — proximity from random walks — z_u and z_v are embeddings of nearby nodes (from random walks) · v_n = negative samples from noise distribution P_n · Q = number of negative samples · σ = sigmoid. Pulls nearby nodes together and pushes random nodes apart.

The same idea in code

GraphSAGE forward pass with pooling aggregatorpython

Simplified to show the idea — not the real implementation.

import numpy as np

def relu(x):
    return np.maximum(0, x)

def sample_neighbors(adj, node, S):
    """Sample S neighbors uniformly at random from node's neighborhood."""
    neighbors = adj[node]
    if len(neighbors) >= S:
        return np.random.choice(neighbors, S, replace=False)
    return np.random.choice(neighbors, S, replace=True)  # oversample

def pool_aggregate(neighbor_embeds, W_pool, b_pool):
    """Transform each neighbor, then take element-wise max."""
    transformed = relu(neighbor_embeds @ W_pool + b_pool)  # (S, d')
    return transformed.max(axis=0)                          # (d',)

def graphsage_layer(h, adj, nodes, W, W_pool, b_pool, S):
    """One GraphSAGE layer: sample → aggregate → combine → normalize."""
    new_h = {}
    for v in nodes:
        # 1. SAMPLE neighbors
        sampled = sample_neighbors(adj, v, S)
        neighbor_embeds = np.stack([h[u] for u in sampled])

        # 2. AGGREGATE
        agg = pool_aggregate(neighbor_embeds, W_pool, b_pool)

        # 3. COMBINE: concat self with neighborhood, apply W
        combined = np.concatenate([h[v], agg])
        out = relu(W @ combined)

        # 4. NORMALIZE to unit length
        new_h[v] = out / (np.linalg.norm(out) + 1e-6)
    return new_h

# Stack K layers: each one expands the receptive field by one hop.
# The learned weights W, W_pool are shared across ALL nodes.

Results: inductive learning works

GraphSAGE was evaluated on three tasks:

Citation networks (Cora/Citeseer): Node classification on academic papers. GraphSAGE-pool achieves F1 of 93.0%, competitive with transductive baselines that see all nodes during training.

Reddit posts: Classifying posts into communities. With 232K nodes, GraphSAGE-LSTM achieves F1 of 95.4%, significantly outperforming transductive baselines.

Protein-protein interaction (PPI): The critical inductive benchmark — test graphs contain entirely unseen proteins from different biological contexts. GraphSAGE-pool achieves F1 of 61.2%, versus 50% for transductive baselines that had no mechanism to generalize to new graphs. Feature-only baselines (ignoring graph structure) score around 40%.

Open in Lab

F1 scores across the three benchmarks. Notice how the inductive gap is largest on PPI — where test nodes are entirely unseen.

The demo wakes as you arrive…

Why it mattered

2016
GCN (Kipf & Welling)
Semi-supervised classification on graphs using spectral convolutions. Transductive — all nodes must be present during training.
2017
GraphSAGE
First inductive GNN framework. Sample-and-aggregate paradigm enables mini-batch training and generalization to unseen nodes.
2018
GAT (Veličković et al.)
Graph Attention Networks add learned attention weights to neighbor aggregation — each neighbor gets a different importance, computed from features.
2018
PinSage (Ying et al.)
GraphSAGE at Pinterest scale — 3 billion nodes, 18 billion edges. First industrial-scale GNN deployment, powering recommendations for hundreds of millions of users.
2019
GNN frameworks mature
PyTorch Geometric and DGL both include SAGEConv as a core layer. GraphSAGE becomes the go-to starting point for GNN projects.

GraphSAGE answered a question that GCN left open: how do you make graph learning work when the graph keeps changing? By shifting from lookup tables to learned functions, it opened the door to every production GNN system that followed — from PinSage to modern drug discovery pipelines.

CitationHamilton, Ying, Leskovec. Inductive Representation Learning on Large Graphs. NeurIPS, 2017.

Terms in this paper

Graph Neural Network (GNN)الشبكات العصبية الرسومية (البيانية)
Message Passingتمرير الرسائل
Node Classificationتصنيف العُقد
Inductive Biasالانحياز الاستقرائي المسبق
Representation Learningتعلم التمثيلات الرقمية
Embeddingالتضمين
Adjacency Matrixمصفوفة التجاور
Negative Samplingالتعيين السلبي
Poolingالتجميع المكاني
Samplingاختيار العينات الاحتمالية