Inductive Representation Learning on Large Graphs

William L. Hamilton, Rex Ying, Jure Leskovec

2017 · NeurIPS

hamiltonGraphSAGE2017

Problem

Framing

Most node-embedding methods were transductive: they optimized one vector per node and could not infer embeddings for unseen nodes or new graphs. GraphSAGE closes this gap by learning neighborhood aggregation functions over node features, then applying them inductively at test time. On unseen-node classification, it reports up to 0.954 micro-F1 on Reddit.

Currently Used Methods

Foundational

@kipfGCN2017 — graph convolutions for semi-supervised node prediction on fixed graphs.
- Limitation in context: tied to transductive training and simple neighborhood averaging.
DeepWalk — random-walk embeddings with per-node latent vectors.
- Limitation in context: unseen nodes need fresh optimization and cannot align across graphs.
node2vec — biased random walks for flexible neighborhood similarity.
- Limitation in context: still learns node identities, not an inductive embedding function.
LINE: Large-scale Information Network Embedding — scalable proximity-preserving graph embeddings.
- Limitation in context: depends on fixed-node embeddings and misses feature-based generalization.
Planetoid — neural prediction with graph context and node features.
- Limitation in context: adaptations to unseen nodes remain computationally expensive.

Proposed Method

Architecture

GraphSAGE learns $K$ hop-specific aggregators. At layer $k$ , node $v$ samples neighbors, aggregates their previous-layer states, concatenates that summary with its own state, then applies a shared linear map and nonlinearity. The paper studies mean, GCN-style, LSTM, and max-pooling aggregators.

GraphSAGE pipeline: sample a k-hop neighborhood, aggregate neighbor features with hop-specific aggregators, then predict context and labels from the resulting node embedding.

Loss / Objective

The unsupervised objective pulls random-walk neighbors together and pushes sampled negatives apart.

J_G(\mathbf{z}_u) = -\log\left(\sigma\left(\mathbf{z}_u^\top \mathbf{z}_v\right)\right) - Q\,\mathbb{E}_{v_n \sim P_n(v)} \log\left(\sigma\left(-\mathbf{z}_u^\top \mathbf{z}_{v_n}\right)\right)

Algorithm

Forward propagation alternates neighbor aggregation and node-state updates, then $L_2$ -normalizes the result.

\mathbf{h}_{\mathcal{N}(v)}^k \leftarrow \mathrm{AGGREGATE}_k\left(\left\{ \mathbf{h}_u^{k-1},\; \forall u \in \mathcal{N}(v) \right\}\right)

\mathbf{h}_v^k \leftarrow \sigma\left(\mathbf{W}^k \cdot \mathrm{CONCAT}\left(\mathbf{h}_v^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^k\right)\right), \qquad \mathbf{z}_v \leftarrow \frac{\mathbf{h}_v^K}{\|\mathbf{h}_v^K\|_2}

Training Procedure

Depth: $K=2$ .
Neighborhood samples: $S_1=25$ , $S_2=10$ .
Nonlinearity: ReLU.
Optimizer: Adam.
Training batch size in runtime study: 512.
Unsupervised context pairs: 50 random walks per node, walk length 5.
Learning-rate sweep, supervised: $\{0.01, 0.001, 0.0001\}$ .
Learning-rate sweep, unsupervised: $\{2 \times 10^{-6}, 2 \times 10^{-7}, 2 \times 10^{-8}\}$ .

Evaluation

Datasets

Citation: Web of Science, 302,424 nodes, average degree 9.15, six biology fields.
Reddit: 232,965 posts, average degree 492, 50 subreddits.
PPI: 24 tissue graphs, average 2,373 nodes per graph, average degree 28.8, 121 labels.

Metrics

Micro-averaged F1.
Macro-averaged F1 in supplement.
Runtime in seconds for training batches and full-test inference.

Headline results

Citation, supervised: GraphSAGE-pool 0.839 micro-F1; best baseline 0.701.
Citation, unsupervised: GraphSAGE-pool 0.798 micro-F1; best baseline 0.701.
Reddit, supervised: GraphSAGE-LSTM 0.954 micro-F1; GraphSAGE-mean 0.950.
Reddit, unsupervised: GraphSAGE-GCN 0.908 micro-F1; DeepWalk + features 0.691.
PPI, supervised: GraphSAGE-LSTM 0.612 micro-F1; GraphSAGE-pool 0.600.

Ablations

Aggregator choice: LSTM and pooling beat mean and GCN across most settings.
Hop count $K$ : moving from $K=1$ to $K=2$ adds about 10–15% accuracy.
Larger $K$ : gains shrink to 0–5% while runtime rises by 10–100 $\times$ .
Neighborhood size: larger samples show diminishing returns.

Results figure

DeepWalk has similar training cost but far slower inductive inference because unseen nodes require new random walks and SGD.

Runtime bar chart on Reddit: GraphSAGE variants have similar per-batch training times, while DeepWalk has dramatically higher full-test inference time than GS-GCN, GS-mean, GS-pool, and GS-LSTM.

Method Strengths and Weaknesses

Strengths

Solves unseen-node inference directly by learning an embedding function, not per-node parameters.
Beats DeepWalk + features on Citation and Reddit by large F1 margins.
Generalizes across disjoint PPI graphs, where transductive embeddings cannot align.
Sampling keeps computation bounded while preserving strong accuracy at $K=2$ .

Weaknesses

Performance depends on informative node or structural features.
Larger hop depth raises runtime sharply, with only marginal gains beyond $K=2$ .
LSTM aggregator is about $2\times$ slower than pooling.
Unsupervised PPI gains are modest: 0.502 micro-F1 with pooling.

Suggestions from the authors

Design stronger trainable aggregators beyond mean, GCN, LSTM, and pooling.
Improve scalability with better neighborhood sampling and minibatch schemes.
Study richer structural-role learning beyond clustering-coefficient-style motifs.
Optimize GraphSAGE variants for domain-specific tasks such as PPI.