SwiggyMart, a food-delivery platform, wants to add a feature: "Restaurants similar to this one." Under the hood, its data is a graph: restaurants and customers are nodes, and an edge connects a customer to every restaurant they have ordered from. The product team's first instinct is to hand this graph to a machine-learning model the way you'd hand it any tabular dataset: give each restaurant an ID, one-hot encode that ID, and feed the vector in. It fails immediately, and the reason it fails is exactly what this chapter is about, and exactly what fixes it is a node embedding.
Say SwiggyMart has 500,000 restaurants. A one-hot vector for restaurant number 118,204 is 500,000 numbers long: a single 1 in position 118,204 and zeroes everywhere else. Take any two distinct restaurants, however similar their customers, and compute the dot product of their one-hot vectors: it is always exactly 0. Cosine similarity between any two different restaurants is always 0. The representation cannot express "these two are alike" no matter how much the underlying graph says they are, because a one-hot vector encodes nothing but "which slot is this," never "who does this restaurant's customer base overlap with." It is also absurd computationally: 499,999 stored zeroes to represent one restaurant, and a brand-new restaurant with its first order forces you to either extend every existing vector's length or bolt on a new ID nobody else's vector can relate to.
A node embedding replaces the ID with a short, dense vector: z_v ∈ R^d for some small d (production systems typically use d between 64 and 256; we will use d = 2 in this chapter purely so the vectors can be drawn on a page). The defining property is not the shortness; it's what the shortness buys you. Two nodes that play a similar role in the graph should end up with vectors that are close together, so that "restaurants similar to this one" becomes a nearest-neighbour search in R^d rather than a graph traversal. The rest of this chapter builds one such embedding, by hand and in code, on a graph small enough to fully trace.
A graph small enough to embed by hand
Three SwiggyMart customers and four restaurants, with an edge for every order placed:
U1 (Aisha) --- R1 (Idli Corner)
U1 (Aisha) --- R4 (South Spice)
U2 (Rohan) --- R1 (Idli Corner)
U2 (Rohan) --- R4 (South Spice)
U2 (Rohan) --- R2 (Punjabi Dhaba)
U3 (Meera) --- R2 (Punjabi Dhaba)
U3 (Meera) --- R3 (Sushi House)Look at the structure, not the restaurant names, for a moment. R1 and R4 are both connected to exactly the pair {U1, U2}. R2 is connected to {U2, U3}. R3 is connected only to {U3}. Nowhere in this graph does any node carry a "cuisine" label; the algorithm we are about to run will never be told that Idli Corner and South Spice both happen to serve South Indian food. It only ever sees which customer ordered from which restaurant. If the resulting embeddings still place R1 and R4 close together, that closeness is a discovery about shared customer behaviour, not a fact we handed the model. Keep that distinction in mind; it is the exact point the misconception section below will come back to correct.
Step 1: turning edges into training pairs with random walks
The classical way to define "graph proximity" for embeddings, used by DeepWalk (Perozzi, Al-Rfou & Skiena, KDD 2014) and refined by node2vec (Grover & Leskovec, KDD 2016), is to simulate a random walker on the graph: start at a node, repeatedly jump to a uniformly random neighbour, and record the sequence of nodes visited. A walk models something concrete here: it is a plausible sequence of "customer to restaurant" hops a random browsing session might trace through the order graph.
One valid four-step walk starting at R1, where each hop follows a real edge in the graph above, is:
R1 -> U2 -> R4 -> U1From a walk, we don't train on the whole sequence at once; we slide a window across it, exactly as word2vec does across a sentence. With window size w = 2, every node in the walk is paired with every other node within 2 positions of it (itself excluded). For the walk above, indexed R1(0), U2(1), R4(2), U1(3), the window rule j in [max(0, i-w), min(len, i+w+1)), j != i produces exactly these 10 (center, context) pairs:
(R1,U2) (R1,R4)
(U2,R1) (U2,R4) (U2,U1)
(R4,R1) (R4,U2) (R4,U1)
(U1,U2) (U1,R4)Run thousands of such walks from every node (20 walks of length 4 from each of the 7 nodes, in the code below: 1,400 pairs in total) and a clear statistical pattern emerges. R1 and R4 co-occur with U1 and U2 constantly, R2 and R3 co-occur with U3 constantly, and R1/R4 almost never share a window with R2/R3, because no walk can reach from one side of the graph to the other without passing through U2, and even then, rarely within a 2-step window. This co-occurrence frequency is the raw signal the embedding will be trained to reproduce as vector similarity.
Step 2: the shallow encoder, and one gradient step done in full
The simplest possible encoder is a lookup table: a matrix Z with one row per node, initialised to small random values, with no other machinery. "Training" means adjusting the rows of Z directly (there is no neural network transforming an input; the vector is the trainable parameter, which is why this family of methods is called a shallow embedding). The objective, following word2vec's skip-gram with negative sampling: for every true (center, context) pair pulled from a walk, push sigmoid(z_center . z_context) toward 1; for a handful of randomly sampled "negative" pairs (a center paired with a node that did not appear in its window), push sigmoid(z_center . z_negative) toward 0. Negative sampling is not optional decoration: without it, the trivial way to make every true pair's dot product large is to collapse all vectors to the same point, which also makes every dot product large. Negative pairs are what force the model to spend some vectors on being far apart.
Trace exactly one update. Suppose at some point during training the relevant vectors are z_R1 = (0.10, -0.05), and the true pair drawn is (R1, U2) with z_U2 = (-0.08, 0.12), alongside one negative sample (R1, R3) with z_R3 = (0.05, 0.15). Learning rate lr = 0.1.
Positive pair (R1, U2), target 1:
dot = z_R1 . z_U2 = (0.10)(-0.08) + (-0.05)(0.12) = -0.008 - 0.006 = -0.014
score = sigmoid(-0.014) = 0.4965
gradient factor = score - 1 = -0.5035 (negative, pushes dot product UP)
dL/dz_R1 (from this pair) = (score-1) . z_U2 = -0.5035 x (-0.08, 0.12) = (0.04028, -0.06042)
dL/dz_U2 = (score-1) . z_R1 = -0.5035 x (0.10, -0.05) = (-0.05035, 0.02518)Negative pair (R1, R3), target 0:
dot = z_R1 . z_R3 = (0.10)(0.05) + (-0.05)(0.15) = 0.005 - 0.0075 = -0.0025
score = sigmoid(-0.0025) = 0.49938
gradient factor = score = 0.49938 (positive, pushes dot product DOWN)
dL/dz_R1 (from this pair) = score . z_R3 = 0.49938 x (0.05, 0.15) = (0.02497, 0.07491)
dL/dz_R3 = score . z_R1 = 0.49938 x (0.10, -0.05) = (0.04994, -0.02497)z_R1 receives both contributions, summed: (0.04028+0.02497, -0.06042+0.07491) = (0.06525, 0.01449). Gradient descent update, z <- z - lr*grad:
z_R1_new = (0.10, -0.05) - 0.1x(0.06525, 0.01449) = (0.09348, -0.05145)
z_U2_new = (-0.08, 0.12) - 0.1x(-0.05035, 0.02518) = (-0.07497, 0.11748)
z_R3_new = (0.05, 0.15) - 0.1x(0.04994, -0.02497) = (0.04501, 0.15250)Check the effect: the true pair's dot product moved from -0.01400 to -0.01305 (up, toward similarity), while the negative pair's dot product moved from -0.00250 to -0.00364 (down, toward dissimilarity). One shared update rule, opposite outcomes, purely because the gradient's sign flips between a target-1 and a target-0 pair. Repeat this update, with fresh random pairs and fresh random negatives, thousands of times, and the pattern from Step 1 (R1/R4 constantly co-occurring, R1/R2 almost never) compounds into a real geometric separation.
Step 3: running it to convergence
The code below is the same mechanism as the hand-traced step above, looped over all 1,400 pairs generated from 140 random walks (20 per node, length 4), for 60 epochs, with 5 negative samples per positive pair drawn from a smoothed degree distribution (unigram frequency raised to the 0.75 power, the same smoothing word2vec uses so that hub nodes like U2 aren't oversampled as negatives). It was run exactly as shown; the printed values are the actual output.
import numpy as np
from collections import Counter
np.random.seed(42)
adj = {
'U1': ['R1', 'R4'], 'U2': ['R1', 'R4', 'R2'], 'U3': ['R2', 'R3'],
'R1': ['U1', 'U2'], 'R2': ['U2', 'U3'], 'R3': ['U3'], 'R4': ['U1', 'U2'],
}
nodes = list(adj.keys())
idx = {n: i for i, n in enumerate(nodes)}
V = len(nodes)
def random_walk(start, length):
walk = [start]
cur = start
for _ in range(length - 1):
cur = adj[cur][np.random.randint(len(adj[cur]))]
walk.append(cur)
return walk
walks = [random_walk(n, 4) for n in nodes for _ in range(20)]
WINDOW = 2
pairs = []
for w in walks:
for i, center in enumerate(w):
for j in range(max(0, i - WINDOW), min(len(w), i + WINDOW + 1)):
if j != i:
pairs.append((center, w[j]))
freq = Counter(n for w in walks for n in w)
unigram = np.array([freq[n] for n in nodes], dtype=float) ** 0.75
unigram /= unigram.sum()
def sigmoid(x):
return 1.0 / (1.0 + np.exp(-x))
def train(D, seed, epochs=60, lr=0.05, k=5):
rng = np.random.RandomState(seed)
Z = (rng.rand(V, D) - 0.5) * 0.1
order = pairs[:]
for _ in range(epochs):
rng.shuffle(order)
for center, context in order:
c, o = idx[center], idx[context]
zc, zo = Z[c], Z[o]
score = sigmoid(np.dot(zc, zo))
g = score - 1.0
gzc, gzo = g * zo, g * zc
for ni in rng.choice(V, size=k, p=unigram):
if ni == o:
continue
zn = Z[ni]
sn = sigmoid(np.dot(zc, zn))
gzc += sn * zn
Z[ni] -= lr * (sn * zc)
Z[c] -= lr * gzc
Z[o] -= lr * gzo
return Z
def cosine(a, b):
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
print("Total (center, context) pairs:", len(pairs))
Z = train(D=2, seed=7)
for n in nodes:
print(f"z_{n} = [{Z[idx[n]][0]:+.3f}, {Z[idx[n]][1]:+.3f}]")
for a, b in [('R1','R4'), ('R1','R3'), ('U1','U2'), ('U1','U3')]:
print(f"cos(z_{a}, z_{b}) = {cosine(Z[idx[a]], Z[idx[b]]):+.3f}")Total (center, context) pairs: 1400
z_U1 = [-0.899, -0.419]
z_U2 = [+0.027, -0.267]
z_U3 = [+0.671, +0.733]
z_R1 = [-0.237, -0.341]
z_R2 = [+0.667, +0.157]
z_R3 = [+0.364, +1.093]
z_R4 = [-0.291, -0.554]
cos(z_R1, z_R4) = +0.992
cos(z_R1, z_R3) = -0.960
cos(z_U1, z_U2) = +0.328
cos(z_U1, z_U3) = -0.924R1 and R4 land at cosine similarity +0.992, nearly the same direction from the origin, while R1 and R3 land at -0.960, nearly opposite. Aisha (U1) and Rohan (U2), who share both restaurants, are modestly aligned at +0.328, and both are strongly separated from Meera (U3) at -0.924. Re-running the identical code with d = 4 instead of d = 2 (same seed, same walks) gives cos(R1,R4) = +0.909 and, notably, cos(U1,U2) improves to +0.496: with only two numbers per node, the model was forced to compromise between separating the restaurant cluster and the customer cluster, and a slightly larger d gives it room to satisfy both simultaneously. This is the general trade-off behind the production choice of d = 64 or d = 128: too small and unrelated structural signals fight for the same few coordinates, too large and you're back to overfitting individual nodes instead of learning shared structure.
The diagram: graph to walk to pairs to vector space
The misconception this example is built to correct
The natural assumption on first seeing R1 and R4 end up 0.99-cosine-similar is: "the algorithm figured out they're both South Indian food." It did not, and it could not have; cuisine was never part of the input. Look back at Step 1 and Step 3: the only data that ever touched the training loop was a list of (center, context) node-ID pairs, generated purely from which customer ordered from which restaurant. Idli Corner and South Spice became similar for exactly one reason: they share the same two customers, U1 and U2, and for no other. If SwiggyMart's data happened to be different and Rohan's account had instead been used almost exclusively to order two completely unrelated cuisines, those two restaurants would have converged in embedding space just the same, cuisine notwithstanding.
This is worth internalising precisely because it cuts both ways. It's why shallow node embeddings are powerful with zero manual feature engineering: structure alone, at scale, correlates strongly with real-world similarity (Pinterest's PinSage, Ying et al., KDD 2018, builds graph embeddings over billions of pins and boards for exactly this reason). But it's also why an embedding's "similarity" is not automatically meaningful. Two nodes can converge in vector space purely from a coincidental overlap in who interacts with them, with no underlying causal or semantic relationship at all; a graph-shaped instance of the same correlation-vs-causation trap you've met in tabular statistics. A node embedding tells you two entities occupy a similar position in the graph's structure; it never, by itself, tells you why.
Active recall
Q1. SwiggyMart has 500,000 restaurants. Why is a one-hot ID vector unusable as a "restaurant embedding" for a similarity feature?
Q2. We trained with walk length 4 and window 2. Suppose we now increase the walk length to 12, keeping window = 2 and the same number of walks per node fixed. List every consequence for the resulting embeddings, not just the first one that comes to mind.
Q3. Using the trained vectors z_R1 = (-0.237, -0.341) and z_R2 = (0.667, 0.157), compute cos(z_R1, z_R2) by hand to two decimal places. Would R1 and R2 be recommended together?
Q4. True or False, with justification: because R1 (Idli Corner) and R4 (South Spice) ended up with cosine similarity +0.99, the training algorithm must have used their menu or cuisine data.
Q5. SwiggyMart onboards "R5, Tandoori Treats" today with zero orders so far. What embedding does the shallow lookup-table model give R5, and what would you actually have to do to obtain a usable vector for it?
Q6. In the hand-traced gradient step, why did the update push dot(z_R1, z_U2) up while pushing dot(z_R1, z_R3) down, given that the exact same update rule (sigmoid, then gradient descent) was applied to both?
A1. A one-hot vector for 500,000 restaurants is 500,000-dimensional, with a single 1 and everything else 0. The dot product, and hence cosine similarity, between any two distinct one-hot vectors is always exactly 0, so no two restaurants can ever be "similar" in this representation regardless of how much their customer bases overlap. It's also wasteful (499,999 stored zeroes per restaurant) and doesn't extend gracefully: adding restaurant 500,001 changes the length of every other vector in the system.
A2. Several distinct effects, not one. (a) Window size, not walk length, defines the notion of "proximity" being learned; with window still 2, each step of even a 12-long walk is still only paired with nodes within 2 positions of it, so the type of relationship captured does not change. (b) Longer walks generate roughly 4x more (center, context) pairs per walk than length-4 walks did (42 vs. 10 pairs per walk), so total training data grows substantially: more gradient updates, generally more stable convergence for the same epoch count. (c) In this specific small, densely-interconnected graph, a 12-step walk will bounce back and forth through the highest-degree node (U2, degree 3) far more often than through a fringe node like R3 (degree 1), so U2 and its immediate neighbours (R1, R2, R4) receive disproportionately more gradient updates while R3's embedding is comparatively under-trained and noisier. (d) Training cost rises roughly linearly with total pair count. (e) A common wrong answer is "now the model directly learns 12-hop relationships," which is false; that conflates walk length with window size. Walk length mainly matters for reaching distant, otherwise-disconnected parts of a much larger graph than this one; it does not by itself widen the co-occurrence horizon that window size controls.
A3. dot = (-0.237)(0.667) + (-0.341)(0.157) = -0.1581 - 0.0535 = -0.2116. |z_R1| = sqrt(0.237^2 + 0.341^2) = sqrt(0.1725) ≈ 0.4153. |z_R2| = sqrt(0.667^2 + 0.157^2) = sqrt(0.4696) ≈ 0.6852. cos = -0.2116 / (0.4153 x 0.6852) ≈ -0.74. Strongly negative: R1 and R2 sit almost opposite each other in embedding space and would not be recommended together, consistent with the fact that Idli Corner and Punjabi Dhaba share only a single, weak structural link (Rohan orders from both, but Aisha's exclusive pattern with R1 and Meera's exclusive pattern with R2 dominate the geometry).
A4. False. Every pair the model ever trained on was a bare (node-ID, node-ID) pair extracted from random walks over the order graph; no cuisine, price, or rating feature was ever part of the input. R1 and R4 became similar solely because they share the same two customers, U1 and U2, and so kept landing in each other's walk-window context. That both happen to be South Indian restaurants is a fact about the world the algorithm was never shown; it is coincidence from the model's point of view, not evidence it used menu data.
A5. None: a shallow lookup-table embedding is one row of the matrix Z, and Z only has rows for nodes present during training. R5 was never in the graph when Z was fit, so it has no row at all; you cannot query "its" vector. To get a usable vector you would either (a) wait for R5 to accumulate some orders, add its edges to the graph, and retrain Z from scratch (or fine-tune it), the standard fix for this fully transductive method, or (b) switch to an inductive approach that computes a node's vector on demand by aggregating its (even few) neighbours' existing vectors or features, so a new node gets an embedding immediately without retraining the whole table.
A6. Because the two pairs entered the loss with opposite target labels, which flips the sign of the gradient even though the update rule is mechanically identical. (R1, U2) was a true pair drawn from a walk (target 1); its gradient factor was (score - 1), a negative number, which drove z_R1 in the direction that increases the dot product, lowering the loss -log(score) by making score approach 1. (R1, R3) was a negative sample (target 0); its gradient factor was +score, a positive number, driving z_R1 in the direction that decreases the dot product, lowering the loss -log(1 - score) by making score approach 0. Same formula, opposite sign, because one pair is being pulled together and the other is being pushed apart.
Think About It
Think about this: How would you explain node embeddings: representing nodes in vectors to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where node embeddings: representing nodes in vectors is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting node embeddings: representing nodes in vectors to at least 3 other topics you have studied.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind node embeddings: representing nodes in vectors, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.