GraphSAGE

Overview

GraphSAGE (SAmple and aggreGatE) is a versatile inductive framework. Instead of training distinct embeddings for each node, it learns functions that generate embeddings by sampling and aggregating features from a node’s local neighborhood. This enables efficient generation of node embeddings for new data. GraphSAGE was proposed by W.H Hamilton et al. of Stanford University in 2017:

• W.L. Hamilton, R. Ying, J. Leskovec, Inductive Representation Learning on Large Graphs (2017)

The GraphSAGE algorithm is to produce node embeddings using a trained GraphSAGE model. The training process is outlined in GraphSAGE Train.

Concepts

Transductive and Inductive Framework

Most conventional graph embedding methods learn node embeddings by utilizing information from all nodes throughout the iterations. When new nodes are introduced to the network, the model must be retrained using the entire dataset. These transductive frameworks don't naturally extend to generalize.

GraphSAGE, on the other hand, acts as an inductive framework. It trains a collection of aggregator functions rather than creating individual embeddings for each node. This allows embeddings for newly added nodes to be derived based on the features and structural details of existing nodes, eliminating the need to reiterate the entire training procedure. This inductive capacity is crucial for high-throughput, operational machine learning systems.

GraphSAGE: Embedding Generation

Assume that we have already trained the parameters of K aggregator functions (denoted as AGGREGATE_k) and K weight matrices (denoted as W^k). Let's now delve into the process of generating GraphSAGE embeddings (i.e., the forward propagation).

1. Neighborhood Sampling

In graph G = (V, E), for each target node to generate the embedding, sample some nodes from its 1st layer of neighborhood to the K-th layer of neighborhood:

• The number of nodes sampled at each layer is fixed as S_k (k = 1,2,...,K).
• Sampling proceeds from layer 1 to layer K, obtaining node sets B^k (k = K,...,1,0).
  • Initialize B^K with all target nodes.
  • During sampling at the k-th layer, obtain set B^K-k by taking the union of B^K-k+1 and the collection of nodes sampled at layer k.
• The sampling is typically performed uniformly. If the number of neighbors at one layer is smaller than the set number, perform repeated sampling until the desired number of nodes is attained.

NOTE

The creators of GraphSAGE observed that the value of K need not be large; practical success can be achieved even with modest values, such as K = 2, given that S₁·S₂ is below 500.

For the target node a in the above graph, considering the settings K = 2, S₁ = 3, and S₂ = 5. B² is initialized as {a}.

• Sampling starts at the 1st layer: 3 immediate neighbors are selected, resulting N(a) = {b, c, d}, then B¹ = B² ⋃ N(a) = {a, b, c, d}.
• Next, sampling is performed at the 2nd layer: 5 neighbors are selcted based on nodes in N(a), resulting N(b) = {i, h}, N(c) = {f}, N(d) = {g, j}, this yields B⁰ = B¹ ⋃ N(b) ⋃ N(c) ⋃ N(d) = {a, b, c, d, f, g, h, i, j}.

2. Feature Aggregation

For each node v ∈ B⁰, initialize their embedding vectors as their feature vectors:

where each feature vector X_v is composed of several specified numeric property values of the node.

The final embeddings of the target nodes are computed through K iterations. In the k-th (k = 1,2,...,K) iteration, for each node v ∈ B^k:

1. Aggregate the (k-1)-th vectors of its sampled neighbors into a neighborhood vector, using the aggregator function AGGREGATE_k.

1. Concatenate its (k-1)-th vector with the aggregated neighborhood vector. This concatenated vector is then refined by going through a fully connected layer weighted by matrix W^k, followed by a non-linear activation function σ (e.g., Sigmoid, ReLu).

1. Normalize $h_v^k$:

The process of feature aggregation of our example can be illustrated as below:

Considerations

• The GraphSAGE algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command：algo(graph_sage)
• Parameters:

Examples

Property Writeback

UQL
algo(graph_sage).params({
  model_task_id: 4785,
  ids: ['ULTIPA8000000000000001', 'ULTIPA8000000000000002']
}).write({
  db:{
    property_name: 'embedding_graphSage'
  }
})

Results: Embedding for each node is written to a new property named embedding_graphSage