Inductive Representation Learning on Large Graphs

William L. Hamilton; Rex Ying; Jure Leskovec

Source-linked AI summary

Inductive Representation Learning on Large Graphs

William L. Hamilton, Rex Ying, Jure Leskovec

arXiv:1706.02216v4Jun 7, 2017cs.SIcs.LGstat.ML

TL;DR

Existing graph-embedding methods are largely transductive, limiting natural generation of embeddings for unseen nodes and graphs. GraphSAGE learns an inductive function that samples and aggregates local-neighborhood features, outperforming relevant baselines across three unseen-data node-classification benchmarks, with average supervised F1 improvements of 51% over node features alone.

Problem
Most prior methods embed nodes from a fixed graph, leaving efficient generation of embeddings for unseen nodes or entirely new subgraphs insufficiently addressed.
Method
GraphSAGE learns an inductive embedding function by sampling and aggregating node features from local neighborhoods to generalize representations to unseen nodes.
Results
Across three inductive node-classification benchmarks, supervised GraphSAGE improves F1-scores by an average of 51% over node features alone and consistently outperforms a strong transductive baseline.
Takeaways & Limitations
GraphSAGE efficiently generates useful representations for unseen nodes while trading off performance and runtime through neighborhood sampling.
Takeaways & Limitations
The framework leaves non-uniform neighborhood sampling functions, including learning them during optimization, as future work.

Abstract

from arXiv · show

Low-dimensional embeddings of nodes in large graphs have proved extremely useful in a variety of prediction tasks, from content recommendation to identifying protein functions. However, most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes. Here we present GraphSAGE, a general, inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen data. Instead of training individual embeddings for each node, we learn a function that generates embeddings by sampling and aggregating features from a node's local neighborhood. Our algorithm outperforms strong baselines on three inductive node-classification benchmarks: we classify the category of unseen nodes in evolving information graphs based on citation and Reddit post data, and we show that our algorithm generalizes to completely unseen graphs using a multi-graph dataset of protein-protein interactions.

1 Introduction

GraphSAGE addresses the limitation that conventional node embeddings are transductive and do not naturally generalize to unseen nodes or graphs. It learns feature-based neighborhood aggregation functions to generate embeddings inductively and evaluates them on evolving citation and Reddit graphs and unseen protein-interaction graphs.

Motivation: Inductive embedding is essential for production systems that operate on evolving graphs and continually encounter unseen nodes or entirely new subgraphs.Examples include Reddit posts, YouTube users, and YouTube videos.
GraphSAGE: GraphSAGE learns an embedding function from node features, including text attributes, profile information, and node degrees, rather than training individual node embeddings.The framework jointly captures neighborhood topology and feature information to generalize to unseen nodes.
GraphSAGE: Aggregator functions sample and combine feature information from local neighborhoods at different hop depths, then generate embeddings for unseen nodes during inference.The approach uses learned aggregation functions instead of a distinct embedding vector for each node.
Evaluation: GraphSAGE is evaluated on three unseen-data node-classification benchmarks spanning citation graphs, Reddit post graphs, and protein-protein interaction multi-graphs.The tasks predict paper categories, post categories, and protein functions, respectively.

2 Related work

This section situates GraphSAGE among factorization-based node embeddings, supervised learning over graphs, and graph convolutional networks. It emphasizes prior methods’ relationships to spectral and neural graph-learning approaches, including scalability and task-design limitations.

Factorization-based embedding approaches: Factorization-based methods learn low-dimensional node embeddings from random-walk statistics and matrix-factorization objectives, relating them to spectral clustering, multidimensional scaling, and PageRank.Because these methods directly train embeddings for individual nodes, they differ conceptually from GraphSAGE’s function-based approach.
Supervised learning over graphs: Supervised graph learning includes kernel-based methods that derive graph feature vectors and neural-network approaches designed for graph-structured data.GraphSAGE is conceptually inspired by several of these algorithms.
Graph convolutional networks: Most graph convolutional architectures either do not scale to large graphs or target whole-graph classification, while GraphSAGE is closely related to Kipf and colleagues’ GCN.The original GCN is designed for semi-supervised learning, according to the passage.

3 Proposed method: GraphSAGE

GraphSAGE learns a function that generates node embeddings by aggregating feature information from local neighborhoods, rather than learning a separate embedding for each node. Its forward propagation recursively combines neighborhood representations, supports fixed-size neighborhood sampling for minibatches, and can use different permutation-invariant aggregator architectures.

Core framework: GraphSAGE learns neighborhood aggregation functions and weight matrices that generate node embeddings from local features, enabling representations without a node-specific embedding lookup.The model parameters are learned using stochastic gradient descent with either an unsupervised graph-based loss or a task-specific objective.
Minibatch computation: The minibatch algorithm forward-samples neighborhoods up to depth K and computes only the representations required for the input nodes’ recursive dependencies.This avoids iterating over all nodes when generating a minibatch.
Forward propagation: At each depth, nodes aggregate immediate-neighbor representations, concatenate the result with their current representation, and apply a nonlinear fully connected transformation.The base representations are input node features, and the final depth-K representations are denoted z_v.
Neighborhood sampling: GraphSAGE samples fixed-size neighborhoods uniformly at each iteration to keep per-batch computation bounded and predictable.The approach was reported to perform well with K = 2 and S_1 · S_2 ≤500.
Aggregator architectures: Aggregator functions must be permutation-invariant because graph neighborhoods are unordered, and GraphSAGE considers mean and max-pooling-based architectures.The mean aggregator is nearly equivalent to the propagation rule in transductive GCN, while max pooling applies a nonlinear function before the element-wise maximum.

4 Experiments

GraphSAGE is evaluated on citation, Reddit, and cross-graph protein-function classification tasks designed to test inductive generalization to unseen data. It outperforms baseline approaches, with pooling- and LSTM-based aggregators generally strongest, while pooling offers a speed advantage over LSTM.

Experimental tasks: GraphSAGE is tested on academic-paper classification, Reddit-community classification, and protein-function classification across multiple PPI graphs.The first two tasks involve evolving information graphs, while the PPI task evaluates generalization across completely unseen graphs.
Experimental setup: The experiments compare GraphSAGE against random, logistic-regression, DeepWalk, and raw-feature-plus-DeepWalk baselines, as well as four GraphSAGE aggregator variants.DeepWalk uses online retraining for citation and Reddit data but cannot be applied in the multi-graph setting because independently learned embedding spaces may be arbitrarily rotated.
Evolving information graphs: GraphSAGE outperforms all baselines by a significant margin on the citation and Reddit datasets, with trainable neural aggregators also improving over GCN.Unsupervised GraphSAGE-pool gains 13.8% on citation data and 29.1% on Reddit over concatenated DeepWalk embeddings and raw features; supervised gains are 19.7% and 37.2%, respectively.
Generalization across graphs: GraphSAGE significantly outperforms baseline approaches on the PPI task, with LSTM- and pooling-based aggregators providing substantial gains over mean- and GCN-based aggregators.The PPI experiment classifies 121 gene-ontology protein functions using features from positional gene sets, motif gene sets, and immunological signatures.
Aggregator comparison: LSTM-, pool-, and mean-based aggregators significantly outperform GCN (T = 1.0, p = 0.02), while LSTM and pool do not significantly differ (T = 10.0, p = 0.46).GraphSAGE-LSTM is approximately 2× slower than GraphSAGE-pool, giving pooling a slight overall edge.

5 Theoretical analysis

The theoretical analysis examines whether GraphSAGE can learn local graph structure despite relying on node features. It establishes that, with distinct features and sufficient dimensionality, GraphSAGE can approximate node clustering coefficients arbitrarily precisely.

Expressive capabilities: GraphSAGE is analyzed through its ability to predict a node’s clustering coefficient, the proportion of triangles closed within its 1-hop neighborhood.The clustering coefficient measures how clustered a node’s local neighborhood is.
Expressive capabilities: Theorem 1 states that Algorithm 1 can approximate clustering coefficients to arbitrary precision on any graph when every node has distinct features and the model is sufficiently high-dimensional.The theorem’s full proof appears in the Appendix.
Expressive capabilities: As a corollary, GraphSAGE can learn local graph structure even when node features are sampled from an absolutely continuous random distribution.This follows from Theorem 1’s approximation result under distinct node features.

6 Conclusion

GraphSAGE efficiently generates embeddings for unseen nodes by sampling node neighborhoods, consistently outperforming state-of-the-art baselines while trading off performance and runtime. Theoretical analysis explains how it learns local graph structures, and the paper identifies extensions to directed or multi-modal graphs.

GraphSAGE efficiently generates embeddings for unseen nodes.
GraphSAGE consistently outperforms state-of-the-art baselines while trading off performance and runtime through neighborhood sampling.
Theoretical analysis provides insight into how GraphSAGE learns local graph structures.
Potential extensions include incorporating directed or multi-modal graphs.

Appendices · A Minibatch pseudocode · 15 end

The appendix presents GraphSAGE’s minibatch forward-propagation procedure, which first samples all nodes needed for computation and then aggregates representations. Its reversed sampling order determines how layer-specific sample sizes translate into neighborhood coverage.

A Minibatch pseudocode: GraphSAGE’s minibatch forward propagation generates representations for a target node set B using sampled neighborhoods, depth K, learned weight matrices, nonlinearities, and differentiable aggregators.The algorithm takes graph structure and input features for nodes in B and outputs vector representations z_v for every v ∈ B.
Appendices: The appendices provide the minibatch pseudocode and explanatory notes needed to interpret GraphSAGE’s implementation-level sampling and aggregation procedure.These materials cover the algorithm’s inputs, outputs, staged computation, and reversed sampling semantics.
A Minibatch pseudocode: The minibatch algorithm separates computation into a sampling stage followed by an aggregation stage.Lines 2–7 sample the required node sets, while Lines 9–15 aggregate representations similarly to batch inference.
A Minibatch pseudocode: Each set B_k contains the nodes required to compute representations for nodes in B_{k+1}, linking sampled computation sets across successive layers.The sets B_k correspond to nodes needed in the (k + 1)-st iteration or layer of the original algorithm.
15 end: The minibatch sampling process runs in reverse layer order: it starts with target nodes in B and progressively samples their neighbors toward earlier layers.This order is conceptually reversed relative to the iterations over k in Algorithm 1.
15 end: Neighborhood sample-size definitions can therefore appear counterintuitive because sampling sizes are indexed by the reversed computation process.The appendix highlights this consequence specifically for minibatch neighborhood sampling.
15 end: With K = 2, sampling S1 at k = 1 and S2 at k = 2 yields S2 immediate neighbors and S1 · S2 two-hop neighbors for target nodes in B.The latter counts the sampled two-hop neighborhood from the perspective of the target nodes after iteration k = 2.

B Additional Dataset Details

The datasets were constructed by selecting connected components and reserving distinct development, validation, and test subsets. Reddit community filtering, WoS field selection, and PPI network sampling defined the evaluation data, with sparse protein features making neighborhood information important.

Dataset availability: The full PPI and Reddit datasets are publicly available, whereas WoS data requires a valid Thomson Reuters license.The passage provides URLs for the PPI and Reddit datasets and states that WoS can be shared with licensed groups.
Reddit data: Reddit communities ranked 11–50 by 2014 comment volume were used, excluding the largest generic communities before taking their union’s largest connected component.Early validation and model development used October and November 2014 data.
WoS data: WoS experiments used six manually selected, similarly sized biology-related subfields and the largest connected component of their union.Neuroscience supported early validation and model development but was excluded from the final set; no other WoS subsets were tested.
PPI Tissue Data: PPI training used 20 networks with at least 15,000 edges, while validation and testing used four networks with at least 35,000 edges.Two networks served validation and two testing; model development used the same validation networks and random training set throughout.
PPI Tissue Data: 42% of PPI nodes had no non-zero feature values, making neighborhood information critical for leveraging the sparse feature data.Selected features appeared in at least 10% of proteins across the PPI graphs.

C Details on the Experimental Setup and Hyperparameter Tuning

The experiments used fixed random-walk and neighborhood-sampling procedures, with model dimensions, learning rates, and training variants selected through systematic tuning. DeepWalk received separate implementation and training treatment because of its convergence and runtime characteristics.

Random-walk generation: 50 random walks of length 5 were launched from each node to generate pairs for the unsupervised loss.The walks were implemented in pure Python based directly on code from Perozzi et al.
Hyperparameter selection: Hyperparameter selection swept learning rates and model dimensions across supervised and unsupervised settings, with separate learning-rate values for DeepWalk.Supervised rates were {0.01, 0.001, 0.0001}, unsupervised rates were {2 × 10−6, 2 × 10−7, 2 × 10−8}, and DeepWalk rates were {0.2, 0.4, 0.8}.
Model configuration: All models used 256-dimensional hidden representations at every recursion depth and rectified linear units, while unsupervised GraphSAGE and DeepWalk used 20 negative samples with smoothing parameter 0.75.The negative-sampling context distribution was smoothed over node degrees.
DeepWalk treatment: DeepWalk was reimplemented in pure TensorFlow, trained for 5 passes over random-walk data, and evaluated with both restricted and unrestricted context-node variants.The two variants differed in whether sampled context nodes had to come from already trained nodes, and the better-performing variant was selected.
Neighborhood sampling: Edges were downsampled so no node exceeded degree 128, while neighborhood sampling used at most 25 neighbors per node to improve computational efficiency.The downsampled graphs enabled dense adjacency lists; all experiments used the downsampled Reddit graph, whose original graph was extremely dense.

D Alignment Issues and Orthogonal Invariance for DeepWalk and Related Approaches

DeepWalk, node2vec, and related embeddings optimize representations through objectives equivalent to stochastic matrix factorization, but orthogonal invariance leaves their embedding spaces freely rotatable. This creates alignment and statistical-drift problems across graphs and graph updates, although pairwise-distance tasks remain unaffected.

Objective structure: DeepWalk, node2vec, and related node-embedding methods use objectives that directly optimize node representations and can be viewed as stochastic, implicit matrix factorizations.The factorized matrix contains random-walk statistics.
Orthogonal invariance: Orthogonal invariance allows embeddings to be rotated by any orthogonal matrix without changing the objective, leaving the embedding space free to rotate during training.The rotation is represented by Q ∈ R^d×d.
Cross-graph alignment: Without an explicit alignment penalty, embeddings learned separately on two graphs are arbitrarily rotated, making classifiers trained on one graph’s embeddings perform essentially randomly on the other’s.This applies when the graphs use the same output dimension.
Temporal updates: When new nodes are added and all embeddings are updated, sparse connections to old nodes can rotate new-node embeddings relative to the original space and cause statistical drift.The passage identifies two issues arising during graph updates; the supplied text specifies the rotation issue.
Mitigations and unaffected tasks: Rotational invariance does not harm tasks based only on pairwise node distances, while freezing old embeddings or restricting context nodes can mitigate drift.The suggested approaches respectively avoid updating trained embeddings and use only existing nodes as context nodes in sampled random walks.
Empirical consequence: 96% of the 2005 citation links connect test nodes to 2000–2004 data, versus 73% of Reddit test-set edges connecting to training data, where greater drift hurts DeepWalk more.The passage reports better DeepWalk performance on citation data than Reddit data because Reddit has fewer test-to-train edges.

E Proof of Theorem 1

The proof establishes that GraphSAGE can approximate node clustering coefficients under separated feature inputs, using pooling-based identifiability and a four-iteration construction. It further extends this guarantee to almost-surely distinct random features and graph classes whose nodes become uniquely identifiable.

Supporting lemmas: Lemma 1 constructs a continuous detector for finite node-feature subsets, and Lemma 2 shows a one-hidden-layer MLP can approximate it arbitrarily well.The detector is positive at selected feature vectors and negative when all inputs lie farther than C.
Proof interpretation: The proof is an identifiability argument, and its efficient learnability is left for future work; the iteration requirements may be conservative.The authors note clustering coefficients might be identifiable with fewer iterations.
Supporting lemmas: Lemma 3 uses separated features and a pooling aggregator with at least two hidden layers to map nodes to χ(G4)-dimensional one-hot indicators.Nodes co-occurring within any node’s 2-hop neighborhood receive different indicators.
Theorem 1: Under pairwise feature separation greater than C, Algorithm 1 has parameters that approximate node clustering coefficients to arbitrary ε after K = 4 iterations.The construction uses pooling aggregators at all depths.
Corollaries: Corollary 2 states that absolutely continuous feature distributions satisfy Theorem 1’s separation condition almost surely.The argument uses the zero probability of sampling two identical feature points.
Corollaries: If nodes become uniquely identifiable after k iterations for a graph class, clustering coefficients can be approximated to arbitrary precision after K = k + 4 iterations.This is the content of Corollary 3.