Node and Graph Embeddings
An embedding maps a node, edge, or whole graph to a fixed-length vector. The coordinates do not have universal meaning: they are useful only relative to the objective, training graph, sampling process, and downstream task that produced them.
Prerequisites
Complete graph query patterns. Embeddings approximate selected structural or semantic relationships; they do not replace exact queries when exact matches are required.
Learning goals
- Distinguish node, edge, and whole-graph representations.
- Connect random-walk co-occurrence to a skip-gram-style objective.
- Explain how negative sampling defines part of the learning problem.
- Evaluate embeddings on a held-out task rather than by attractive plots alone.
Learning contract
- Unit: one vector per known node for the worked update; graph-level pooling is discussed but not trained.
- Positive context: Ada–Ben is declared observed; Ada–Dia is a declared negative sample for this calculation only.
- Objective: binary logistic loss on dot products, with one transparent gradient step and no random walk.
- Interpretation limit: vector proximity represents the chosen training signal, not friendship, identity, importance, or causality.
Objectives before algorithms
DeepWalk forms truncated random walks, treats node sequences like sentences, and predicts nearby nodes. node2vec changes the walk distribution with return and in–out parameters to trade between local and outward exploration. Matrix-factorization, knowledge-graph scoring, and graph-level pooling optimize different targets. Two methods both called “graph embeddings” may therefore preserve incompatible notions of similarity.
Negative examples are usually sampled because nonedges are numerous. But an unobserved edge may be missing, impossible, or simply not yet observed. The negative distribution changes the objective and can overrepresent high-degree nodes or easy pairs. For temporal link prediction, negatives and features must be available at the prediction cutoff.
Embeddings can rotate or reflect without changing dot products, so raw coordinates are not stable identities. Compare downstream metrics, neighborhoods, calibration, and slices under repeated seeds. Fit embeddings on the training graph only; computing them on a graph containing held-out edges leaks topology.
Worked example
import math
source = [0.2, -0.1]
positive = [0.4, 0.3]
negative = [-0.2, 0.5]
learning_rate = 0.1
dot = lambda left, right: sum(a * b for a, b in zip(left, right))
sigmoid = lambda value: 1 / (1 + math.exp(-value))
positive_score = dot(source, positive)
negative_score = dot(source, negative)
loss = -math.log(sigmoid(positive_score)) - math.log(sigmoid(-negative_score))
gradient = [
(sigmoid(positive_score) - 1) * pos + sigmoid(negative_score) * neg
for pos, neg in zip(positive, negative)
]
updated = [value - learning_rate * grad for value, grad in zip(source, gradient)]
print(f"positive_score={positive_score:.3f} negative_score={negative_score:.3f} loss={loss:.3f}")
print(f"source_before={source} source_after={[round(value, 4) for value in updated]}")
print("boundary=one-declared-update-not-a-trained-embedding")
Expected output:
positive_score=0.050 negative_score=-0.090 loss=1.318
source_before=[0.2, -0.1] source_after=[0.2291, -0.1093]
boundary=one-declared-update-not-a-trained-embedding
This scalar calculation makes the objective visible. Production libraries provide optimized walks, batching, sparse operations, checkpoints, and multi-device execution; those operational features do not choose the right graph, negatives, or evaluation split for you.
Limitations
- Random-walk embeddings privilege patterns reachable under their walk distribution.
- Isolates and new nodes need features, retraining, or an inductive encoder.
- Dot-product geometry cannot express every relation, direction, or uncertainty pattern.
- Downstream performance can hide representation harm for sparse or underobserved neighborhoods.
Practice
Swap the positive and negative contexts. Predict the gradient direction, then calculate whether the updated Ada vector moves toward the newly positive context under the dot product.
Next steps
Continue to graph neural networks and message passing to generate representations from features and neighborhoods.
Primary sources
Checked 2026-10-18: B. Perozzi, R. Al-Rfou, and S. Skiena, DeepWalk; A. Grover and J. Leskovec, node2vec; W. L. Hamilton, R. Ying, and J. Leskovec, GraphSAGE.