GraphSAGE: Inductive Representation Learning on Large Graphs

Train a function that builds a node’s vector from a fixed-size sample of its neighbors’ features, and it also works on nodes added after training.

Earlier node embeddings stored one trained vector per node. GraphSAGE stores only weight matrices: it computes each node’s vector by sampling a few neighbors, combining their features with a mean, a max or an LSTM, and repeating that for two hops.

Tested on papers published after the training years, Reddit posts written after the training days, and two protein networks held out entirely, the supervised model beats a features-only classifier by 51% in F1 on average, as a relative gain.

Embedding nodes that did not exist at training time

A node embedding is a vector, typically a few hundred numbers, assigned to each node of a graph so that nodes close in the graph get vectors with a large dot product. Downstream code treats the vectors as ordinary features: a logistic regression on them classifies nodes, a dot product between two of them scores a possible link. The Reddit graph in this paper has 232,965 posts from September 2014, with an edge between two posts when the same user commented on both, and the task is to predict which of 50 communities a post belongs to.

Methods before GraphSAGE were transductive: every node that would ever be classified had to be in the graph during training, even if its label was hidden. Reddit receives new posts every minute, and a model trained on Monday has to embed Tuesday’s posts. The paper evaluates exactly this inductive setting: it trains on the posts of the first 20 days and tests on posts from the remaining days, which training never saw. On a citation graph it trains on papers from 2000 to 2004 and tests on 2005. On protein interaction graphs it goes further and tests on two whole graphs that were held out.

A few ideas explain the method: replace the per-node table of vectors with a function of a node’s features and its neighbors’ features; cap the cost of that function by sampling a fixed number of neighbors; choose an aggregator that ignores neighbor order; train it with a loss that needs no labels. The paper closes with a theorem about what such a function can learn about graph structure.

Why a per-node lookup table cannot embed a new node

DeepWalk (Perozzi, Al-Rfou and Skiena, 2014) is the representative earlier method and the paper’s main baseline. It runs short random walks on the graph, treats each walk as a sentence of node ids, and trains a skip-gram model on those sentences (a model that learns one vector per id by predicting which ids occur near each other), the same training that word2vec uses for words. The trainable parameters are a matrix $Z \in \mathbb{R}^{|\mathcal V| \times d}$, one row per node. A post written after training has no row. DeepWalk’s remedy is to run new walks from the new nodes and new rounds of gradient descent on their rows while the old rows stay fixed. In the paper’s experiments that is 50 walks of length 5 per new node followed by SGD, and the paper reports it as 100 to 500 times slower at test time than a GraphSAGE forward pass.

Appendix D identifies a second problem. DeepWalk, node2vec and similar methods optimize objectives of the form

where $\mathcal A$ and $\mathcal B$ are sets of node pairs (say, pairs seen together on a walk and random pairs). The objective depends on the embeddings only through their dot products, which makes it an implicit factorization $ZZ^{\top} \approx M$ of some matrix $M$ of random-walk statistics, equation (5). Multiply every embedding by an orthogonal matrix $Q$ (a rotation or reflection) and every dot product survives:

So the objective cannot prefer one orientation of the embedding space over another. Train on graph A and separately on graph B, or retrain on graph A after new nodes arrive, and the two runs may land in rotated copies of each other. A classifier fitted to the coordinates of the first run then receives coordinates it was not trained on. Figure 1 lets you apply the rotation and check both halves of the argument: the largest change in any dot product stays at zero while the accuracy of the fixed classifier falls.

Rotation is the extreme case. With new nodes attached by only a few edges to the old ones, the new rows are free to settle into an orientation of their own. The paper ties DeepWalk’s weak Reddit result to this: 96% of the 2005 citation links point back to the 2000 to 2004 training papers, but only 73% of the Reddit test edges connect to training posts, and DeepWalk’s unsupervised F1 is 0.565 on citations against 0.324 on Reddit. On the protein graphs, which share no nodes, DeepWalk cannot be applied at all.

GraphSAGE replaces the table with a function. A lookup table answers only for the keys it stored; a function answers for any input of the right type. The analogy stops short in one place: the function still needs inputs, namely the new node’s own features and its edges. A node with no features and no edges gets nothing useful from GraphSAGE either.

How GraphSAGE computes a node’s embedding

Every node $v$ starts with a feature vector $\mathbf x_v$. On Reddit that is 602 numbers: the average 300-dimensional GloVe word vector of the post title, the average over its comments, the post’s score and its comment count. GraphSAGE sets $\mathbf h^0_v = \mathbf x_v$ and runs $K$ rounds, called depths. At depth $k$, every node first summarizes its neighbors’ vectors from the previous depth (line 4 of Algorithm 1):

then concatenates the summary with its own previous vector, multiplies by a weight matrix, applies a nonlinearity $\sigma$ (ReLU in every experiment), and rescales the result to unit length (lines 5 and 7):

After $K$ depths the embedding is $\mathbf z_v = \mathbf h^K_v$. Depth 1 mixes in the features of direct neighbors; depth 2 mixes in the depth-1 vectors of the neighbors, which already contain their own neighbors, so $\mathbf z_v$ depends on everything within $K$ hops.

Take a worked example with the mean aggregator and 2-dimensional features. Node $v$ has $\mathbf x_v = (1, 0)$ and three neighbors with features $(0, 1)$, $(1, 1)$ and $(0, 1)$. Their mean is $(0.333, 1)$, and the concatenation is $(1, 0, 0.333, 1)$. With

the product is

ReLU leaves it unchanged, and dividing by its length 0.471 gives $\mathbf h^1_v = (0.707, 0.707)$. A post that appears tomorrow with the same features and neighbors would get the same vector, because $\mathbf W^1$ is the only thing that was learned.

The parameters are $K$ weight matrices plus whatever parameters the aggregator has, and their sizes depend on the feature dimension, not on the number of nodes. In the official code with the mean aggregator on Reddit, depth 1 has two $602 \times 128$ matrices and depth 2 two $256 \times 128$ matrices: 219,648 weights for a graph of 232,965 nodes, against 59.6 million for a 256-dimensional DeepWalk table. To embed a new post, compute its 602 features, look up its edges, and run the two depths.

Why concatenate the node with its neighborhood instead of averaging the node in with its neighbors? Averaging dilutes the node’s own features by its degree: a post with 400 neighbors would contribute 1/401 of the input. Concatenation keeps the node’s own signal in its own coordinates, and the paper describes it as a skip connection between depths, the idea behind ResNet. The variant that averages instead, equation (2) in the next section but one, scores lowest of the four GraphSAGE variants in five of the six experimental settings.

The official code implements line 5 with two matrices, a self matrix applied to $\mathbf h^{k-1}_v$ and a neighbor matrix applied to the aggregate, and concatenates the two 128-dimensional products into a 256-dimensional output. That is $\mathbf W^k$ restricted to a block-diagonal shape, so self and neighbor features are combined only at the next depth. The code also skips the ReLU on the last depth and normalizes only the final output, not every depth. The algorithm on the page and the model that produced Table 1 therefore differ in these three places; the Provenance panel cites the lines.

With $K$ set to the number of nodes, every $\mathbf W^k$ set to the identity, and the aggregator replaced by a hash of the multiset of neighbor labels, Algorithm 1 becomes the Weisfeiler-Lehman (WL) graph isomorphism test, a classic procedure that repeatedly relabels each node by hashing its own label together with its neighbors’ labels. The paper calls GraphSAGE a continuous approximation of WL with a trainable aggregator in place of the hash. The theorem section returns to how far that approximation goes.

Fixed-size neighbor sampling

Degrees in real graphs are heavy-tailed. Reddit posts have 492 neighbors on average, and the authors downsampled Reddit’s edges before any experiment because the original graph is extremely dense. With full neighborhoods, the two-depth embedding of one post needs the features of every neighbor of every neighbor, which can be a large fraction of the graph, and a minibatch has unpredictable memory and in the worst case $O(|\mathcal V|)$ cost. GraphSAGE instead redefines $\mathcal N(v)$ as a uniform sample of fixed size from the true neighbors, drawn again at every depth and for every minibatch. When a node has fewer neighbors than the sample size, the sample is drawn with replacement, so some neighbors appear twice.

With sample size $S_k$ at depth $k$, the work per target node is fixed at $O(\prod_{k=1}^{K} S_k)$ whatever the degrees. The paper uses $K = 2$, $S_1 = 25$ and $S_2 = 10$. The indices count depths, not hops: $S_k$ is the number of neighbors aggregated at depth $k$, and depth 2 is the last one, the one that aggregates the target’s direct neighbors. So the minibatch samples first from the target outward, 10 one-hop neighbors (for depth 2) and then 25 neighbors of each of those (for depth 1), and computes from the leaves back up. Appendix A spells this out: from the target’s point of view, $S_2$ immediate neighbors and $S_1 \cdot S_2$ two-hop neighbors.

In numbers, one target needs 1 + 10 + 250 = 261 feature rows. A training batch of 512 targets gathers 512 + 5,120 + 128,000 = 133,632 rows of 602 floats, about 322 MB in float32, the same for every batch. The code prepares for this once: it subsamples every node’s adjacency list to at most 128 entries (padding shorter lists by drawing with replacement) and stores the result as a dense table with 128 columns, so a sample is a column shuffle and a slice.

The first readout in Figure 2 depends only on the two sliders, $1 + S_2 + S_2 S_1$, whatever target you click. The second shows the cost of that guarantee: on a low-degree node most of the 261 rows are repeats of a handful of nodes, and on the high-degree node in the middle a sample of 10 skips some of its neighbors. The figure follows the code, in which the target’s own depth-1 vector reuses its 10 one-hop draws. Algorithm 2 in the paper draws a separate set of $S_1$ neighbors for that, which would add 25 rows.

The paper measured how much the samples cost in accuracy. On the citation data with the mean aggregator and $S_1 = S_2$, its Figure 2B rises from a micro-F1 of about 0.78 at 4 neighbors per depth to about 0.82 at 16 and about 0.83 at 64, while the time per batch grows from under 0.01 to about 0.06 seconds (values read off the plot). Depth showed the same pattern: $K = 2$ beat $K = 1$ by about 10 to 15% on average, and going past 2 added 0 to 5% for 10 to 100 times the runtime.

The four aggregators

A node’s neighbors have no natural order, unlike the words of a sentence or the pixels of an image. An aggregator that gave a different answer for a different listing of the same neighbors would make the embedding depend on how the adjacency list happened to be stored. The paper therefore wants a symmetric function (one that ignores input order) that is still trainable, and tries four.

Mean. The elementwise mean of $\{\mathbf h^{k-1}_u : u \in \mathcal N(v)\}$, then the concatenation and matrix of line 5. It has no parameters of its own.

GCN. Replace lines 4 and 5 with one average that includes the node itself:

This is the propagation rule of the graph convolutional network (GCN) of Kipf and Welling, made inductive by sampling and minibatching. The paper says it differs from Kipf and Welling’s rule by a minor normalization constant. The difference is per edge: the mean weights every member of the closed neighborhood by $1/(d_v + 1)$, while Kipf and Welling weight edge $(v, u)$ by $1/\sqrt{(d_v + 1)(d_u + 1)}$, which also depends on the neighbor’s degree. The experiments name this variant GraphSAGE-GCN.

LSTM. An LSTM, the recurrent network that reads a sequence one element at a time (the Seq2Seq explainer covers it), run over the neighbor vectors. An LSTM is not symmetric, so the paper feeds it a random permutation of the neighbors each time. Its hidden size was 128 or 256, and it is the slowest variant, about twice the time of the pooling aggregator.

Pooling. Pass every neighbor’s vector through its own copy of a dense layer, then take the elementwise maximum across neighbors:

Each of the 512 (or 1,024) units of the dense layer computes one feature per neighbor, and the max reports the largest value any neighbor produced for it, so each unit acts as a detector for one kind of neighbor. The design comes from PointNet, which processes 3D point sets the same way. The paper prints $\mathbf h^{k}_{u_i}$ inside equation (3); the aggregator at depth $k$ consumes depth $k-1$ vectors, as written above and as in the code. Replacing the max by a mean made no significant difference in the authors’ development tests.

The paper does not analyze what symmetry costs. Xu, Hu, Leskovec and Jegelka (2019) showed that a mean aggregator's output depends only on the proportions of a multiset of neighbor features, a max's only on which distinct values occur, and a sum's on the full multiset. Figure 3 reproduces their three failing pairs. Each neighbor carries one of three 2-dimensional features, and the table reports, for each aggregator, whether node $v$ and node $v'$ end up with identical summaries.

In the first pair MAX and MEAN both return (1, 0) for two copies and for three copies of the same feature, so neither can count neighbors. In the third, a teal and an amber neighbor have the same mean as two of each. Shuffling changes only the RNN row, which is why the paper randomizes the LSTM’s input order: the model is trained to give similar outputs for different orders, but nothing guarantees it.

Two facts limit how much this costs GraphSAGE in practice. First, with fixed-size sampling a sum over the $S$ draws equals $S$ times their mean, so under sampling a sum aggregator would not recover the degree either (our observation, not the paper’s); the citation features include each paper’s degree directly, which puts the count back into the input. Second, by Xu et al.’s own analysis the mean is as discriminating as the sum when features are diverse and rarely repeat, as averaged word vectors are.

Training: the random-walk loss and the supervised alternative

GraphSAGE can be trained without labels, so the same embeddings can be handed to several downstream tasks. The loss for a node $u$ is

with $\sigma$ here the logistic sigmoid. The node $v$ is a positive example: a node that appeared near $u$ on a short random walk. The code runs 50 walks of 5 steps from every training node and pairs the start node with each node visited at steps 1 to 4. The nodes $v_n$ are negatives, $Q = 20$ of them, drawn with probability proportional to degree raised to the power 0.75, the smoothing that word2vec’s negative sampling uses for word frequencies. The first term rewards a large dot product with the walk partner; the second rewards a negative dot product with the random nodes. In the code the expectation is a plain sum over the 20 draws, which is $Q$ times their average.

The loss is the skip-gram negative-sampling loss of DeepWalk, applied to different vectors. In DeepWalk, $\mathbf z_u$ is a row of a table and the gradient updates that row. In GraphSAGE, $\mathbf z_u$, $\mathbf z_v$ and every $\mathbf z_{v_n}$ are outputs of the same sampled forward pass, so the gradient flows through the aggregators into the shared weight matrices, and no parameter belongs to any one node.

Because $-\log\sigma(s) = \log(1 + e^{-s})$, each term shrinks as its dot product moves in the right direction but never reaches zero. The code normalizes the embeddings to unit length before the dot products, so every dot product lies in $[-1, 1]$. The best a single term can do is then $\log(1 + e^{-1}) = 0.313$, and the loss of one node with 20 negatives cannot go below $21 \times 0.313 = 6.58$. Figure 4 puts $\mathbf z_u$ on a circle with its partner and the negatives.

Pointing $\mathbf z_u$ at $\mathbf z_v$ shrinks the amber bar, but with 20 negatives spread around the circle no direction makes all of them dot negatively with $\mathbf z_u$, so the total stays well above the dashed floor. With |z| = 0, every dot product is 0 and every term is $\log 2 = 0.693$, a total of 14.56 for $Q = 20$.

The unsupervised embeddings are evaluated by training a logistic regression (scikit-learn’s SGDClassifier, default settings) on the training nodes’ embeddings and applying it, without further tuning, to the test nodes’ embeddings. The supervised variant replaces equation (1) with cross-entropy on the labels and trains the aggregators and a final linear layer end to end. Both use Adam, batches of 512 and ReLU, with output dimension 256 at every depth. The paper swept the learning rate over $\{10^{-2}, 10^{-3}, 10^{-4}\}$ for the supervised models and $\{2 \times 10^{-6}, 2 \times 10^{-7}, 2 \times 10^{-8}\}$ for the unsupervised ones, and ran the supervised models for 10 epochs.

One training step in code

The listing follows the official TensorFlow code for one supervised step on Reddit with the mean aggregator, rewritten in array notation. Ws and Wn are the self and neighbor halves of each $\mathbf W^k$.

# one supervised step on Reddit, mean aggregator, K = 2 (official code)
# X: [232966, 602] features (+1 zero row for padding); adj: [N, 128] table
B  = batch_of_train_nodes(512)                    # [512]
N1 = sample(adj, B, 10)                           # [512, 10]   S2 draws
N2 = sample(adj, N1.flatten(), 25)                # [5120, 25]  S1 draws
x0, x1, x2 = X[B], X[N1], X[N2]                   # 512 + 5,120 + 128,000 rows

# depth 1: the targets and their one-hop draws each get a 256-d vector
h1_B  = relu(concat(x0 @ Ws1, x1.mean(1) @ Wn1))  # [512, 256]
h1_N1 = relu(concat(x1.reshape(5120, 602) @ Ws1,
                    x2.mean(1) @ Wn1))            # [5120, 256]
# depth 2: only the targets; no ReLU on the last layer in the code
z = concat(h1_B @ Ws2, h1_N1.reshape(512, 10, 256).mean(1) @ Wn2)
z = z / norm(z, axis=1, keepdims=True)            # [512, 256]

logits = z @ Wc + bc                              # [512, 50] subreddits
loss = cross_entropy(softmax(logits), y[B])
# gradients reach Ws1, Wn1 (602x128), Ws2, Wn2 (256x128), Wc, bc: no
# per-node parameter exists, so a node never seen in training costs nothing

At evaluation the code swaps the adjacency table for one built from the full graph, test nodes included, and runs the same function. Nothing is retrained. The paper’s Figure 2A puts the inference time for all 79,534 Reddit test posts at roughly 1 to 2 seconds for the four GraphSAGE variants and about a thousand seconds for DeepWalk (read off a log axis), while training time per batch is similar for all of them.

Results on unseen posts, papers and protein graphs

Three benchmarks, all scored with micro-averaged F1 on nodes absent during training (F1 computed over all predictions pooled together; for a task with one label per node it equals accuracy). Citation: 302,424 papers from six biology fields of the Web of Science, average degree 9.15, features from the abstract (300-dimensional word vectors averaged with Arora et al.’s method) plus the node degree, train on 2000 to 2004, test on 2005. Reddit: as above, average degree 492. PPI (protein-protein interaction): 24 graphs, one per human tissue, averaging 2,373 nodes and degree 28.8, with 121 gene-ontology labels per protein (a protein can have several), training on 20 graphs and testing on 2 that were never seen. On PPI, 42% of the nodes have no nonzero feature, so the neighborhood carries most of the information.

The "% gain over features" row of Table 1 compares the best GraphSAGE variant with the raw-feature classifier, as a relative gain: on citations, 0.839 against 0.575 is 46%. The supervised gains are 46%, 63% and 45%, whose average is the 51% of the introduction. Against the strongest baseline, DeepWalk plus features, the pooling aggregator gains 13.8% (citation) and 29.1% (Reddit) unsupervised and 19.7% and 37.2% supervised, again relative: 0.948 / 0.691 = 1.372. In absolute terms the supervised models reach 0.839 on citations, 0.954 on Reddit and 0.612 on PPI. Each unsupervised variant comes within 0.02 to 0.06 of its supervised counterpart on citations and Reddit; on PPI the gap reaches 0.13 (LSTM), and the best unsupervised score is 0.502.

Among the aggregators, the GCN variant is the lowest GraphSAGE row in five of the six settings (unsupervised Reddit is the exception, where it is highest). The paper’s "7.4% on average" over the GCN aggregator reproduces as the pooling aggregator’s mean relative gain across the six settings; the mean aggregator gains 6.0% and the LSTM 7.1%. To ask which differences would carry over to a new setting, Section 4.4 runs a Wilcoxon signed-rank test (a rank-based paired test) over the six settings. The T statistics reproduce from Table 1: T = 1.0 for each of LSTM, pool and mean against GCN, T = 1.5 for LSTM against mean, T = 4.5 for pool against mean and T = 10.0 for pool against LSTM. The reported p-values (0.02, 0.03, 0.10, 0.46) match a one-sided normal approximation. With six pairs the exact test is coarse: T = 1.0 gives a one-sided p of 0.031 and a two-sided p of 0.0625. The paper itself calls the test underpowered. LSTM and pool are statistically indistinguishable, and the paper gives pool the edge because it runs about twice as fast.

A last experiment replaces a growing share of the citation features with Gaussian noise. With every feature replaced, GraphSAGE-pool still reaches a micro-F1 of about 0.61, against about 0.31 for GraphSAGE-GCN and about 0.25 for the feature-only classifier (random guessing scores 0.206), values read off the paper’s Figure 3. Random features cannot predict a paper’s field, so what pool uses there is the graph structure, and the theorem in the next section is the paper’s explanation of how a feature-based model can learn structure.

What the theorem proves: clustering coefficients from features

The clustering coefficient of a node $v$ with degree $d_v$ is the fraction of pairs of its neighbors that are themselves connected:

where $T_v$ is the number of edges among $v$’s neighbors, the number of triangles through $v$. A node in a triangle has $d_v = 2$, $T_v = 1$ and $c_v = 1$; the center of a star has $c_v = 0$. It is a purely structural quantity, and the question is whether a model that only aggregates features can compute it.

Theorem 1 answers yes in an existence sense. If every node’s feature vector lies in a compact (closed and bounded) set and every two nodes’ features differ by more than some fixed $C > 0$, then for any $\epsilon > 0$ there exist parameters for Algorithm 1 with pooling aggregators and $K = 4$ such that $|z_v - c_v| < \epsilon$ for every node. The theorem is about one fixed graph, it says nothing about whether gradient descent finds those parameters, and the dimensions it needs can grow as $O(|\mathcal V|)$; the appendix states all three limits.

The proof walks through the depths. At depth 1, the pooling aggregator (a ReLU network followed by a max, which by PointNet’s theorem can approximate any continuous set function) turns the distinct features into one-hot vectors, using a graph coloring in which nodes that share a two-hop neighborhood get different colors. At depth 2, summing the neighbors’ one-hot vectors gives $v$ its adjacency row $\mathbf b$, with $d_v$ ones. At depth 3, summing the neighbors’ depth-2 vectors gives $\mathbf c = \sum_{u \in \mathcal N(v)} A_u$, the sum of the neighbors’ adjacency rows. Entry $w$ of $\mathbf c$ counts how many of $v$’s neighbors are adjacent to $w$, so

since every edge between two neighbors of $v$ is counted once from each end. Depth 4 is used as a one-hidden-layer network that computes the clustering coefficient from the depth-3 vector as

Equation (11) in the paper prints the left side as $2(\mathbf b^{\top}\mathbf c - d_v)/(d_v(d_v - 1))$. Figure 6 computes both on a seven-node graph.

The printed version assumes $\mathbf b^{\top}\mathbf c$ is the edge count of $v$’s ego network, $d_v + T_v$; it is $2T_v$. The two formulas agree only when $T_v = d_v$, and on a triangle the printed one gives 0 instead of 1. In Figure 6 it even goes negative, at nodes 2 and 3. The theorem survives, because both expressions are continuous functions of the depth-3 vector and the final network can approximate either one. The proof also uses sums and every node’s full neighbor set; with fixed-size sampling, $\mathbf b$ would count sampled draws instead of edges. That is our reading of the proof; the paper does not discuss it.

Corollary 2 extends the theorem to features drawn at random from any continuous distribution, which are distinct with probability one. That is the setting of the noise experiment, where the pooling aggregator kept 0.61 and the GCN aggregator, which averages and has no per-neighbor network to build indicators with, fell to 0.31. Corollary 3 restates the result for a class of graphs: if some number of depths can make nodes identifiable within every three-hop neighborhood across that class, four more depths approximate the clustering coefficient on all of them.

Limits and later work

The sampled neighborhoods make every embedding random. The official code samples at evaluation as well, so the same node gets slightly different vectors on two calls, and a high-degree node is always summarized from a small subset of its neighbors. The paper names non-uniform and learned samplers as future work. PinSage (Ying et al., 2018), from the same group, built a GraphSAGE-style model at Pinterest that chooses each node’s neighborhood with random walks and trained it on 7.5 billion examples over a graph of 3 billion nodes and 18 billion edges.

The aggregators are less discriminating than the WL test the paper invokes, as Figure 3 showed; Xu et al. proposed the Graph Isomorphism Network, which sums neighbor features through a multilayer perceptron, as an architecture that matches WL. Within months, graph attention networks replaced the fixed mean or max with learned per-edge weights over the full neighborhood and reported 0.973 micro-F1 on the same PPI split, against 0.612 here; a footnote in the GraphSAGE paper already points to Chen and Zhu for better PPI numbers obtained by tuning GraphSAGE itself.

The inductive property depends on features. A graph whose nodes carry no attributes leaves degree and other structural statistics, or random features as in Corollary 2; the code’s option of a trainable vector per node brings back the lookup table and loses the inductive property. The paper also leaves directed and multi-modal graphs for future work.