From sparse hand-crafted features to dense, semantic vectors — word2vec for text and random-walk embeddings (DeepWalk, node2vec) for graphs.
A. Anand · lecture 8 study deck
Part I
From raw data to vectors
Every learning algorithm eats vectors. How do we turn tables, text and graphs into them — and why the obvious way is a bad one.
The ML pipeline needs numbers
How do we vectorize the input?
The classic ML pipeline
raw data → compute features → learning algorithm → model → deploy on test → output.
Everything downstream assumes each instance is already a vector.
But raw data comes in many shapes: tabular, text, graph, …
The first — often overlooked — step is choosing how each instance becomes a point in some feature space.
This choice decides whether distances, similarity and learning will actually work.
One recipe per data type
Instances as vectors
Tabular
Each row = an instance vector
Each column = a dimension
Values already numeric
Text
Each word = a dimension
Bag of words: value = word frequency
Vocabulary-sized vectors
Graph
Each vertex = a dimension
Dim = 1 if an edge to that vertex
A vertex = one row of the adjacency matrix
All three give the same thing: a long, mostly-zero vector in a vocabulary- or vertex-sized space.
Typical hand-crafted feature space
What is the problem?
These representations are…
Sparse — almost all entries are zero · Large — one dimension per word / vertex ·
Non-semantic — dimensions carry no meaning · Hand-crafted — you choose the features by hand.
We want the opposite: dense, smaller, semantic, and automatically extracted.
The goal of this lecture
Automatic feature extraction
Raw text / tables / graphs first map to a sparse, large, hand-crafted space; embeddings add a
second step to a dense, small, semantic space that is learned, not designed.
Why one-hot / bag-of-words hurts
Issues with sparse representations
Distances are misleading — in very high dimensions everything is roughly equidistant.
Vocabulary mismatch — hotel and motel share no dimension, so they look unrelated.
Large space requirements — vectors as wide as the whole vocabulary.
These are local (1-hot) representations: each word is its own isolated axis.
(whotel)ᵀ wmotel= (whotel)ᵀ wcat= 0
Any two distinct one-hot words are orthogonal — the dot product is 0 whether the words are near-synonyms or unrelated.
One-hot vs. distributed
Local vs. distributed representations
Local (1-hot): one active dimension per word — no shared structure.
Distributed: meaning is spread across many features (barks, fruit, has-tail, …),
so banana and mango now overlap.
Same disease for graphs
Sparsity in adjacency matrices
Adjacency rows are sparse too
A vertex's row in the adjacency matrix is sparse, large, non-semantic and hand-crafted — the number of
edges is far smaller than the number of vertices (#edges ≪ #vertices).
So both text and graphs need the same cure: learn a dense, low-dimensional, semantic embedding.
Question
With one-hot vectors, every pair of distinct words is equally dissimilar — “cat” is as far from “dog” as from “democracy”. How could a representation capture that some words are related — learned from text alone?
We want nearby vectors for words that behave alike.
Think — then → for the answer.
Part II
Word embeddings
Learn a vector per word so that words used in similar contexts land close together — word2vec.
The definition
What is an embedding?
Definition
An embedding is a learned, dense,
low-dimensional vector that represents an object — a word, a node, a product — so that
similar objects get nearby vectors.
Learned, not hand-designed — the values come from training.
Dense (~100–300 numbers), unlike a sparse one-hot of size |vocabulary|.
Geometry carries meaning: distance / direction in the space stands for relationships.
The objective in one picture
What we want from an embedding
Encode each word so that similarity in the embedding space (e.g. the dot product zuᵀzv)
approximates similarity in its textual context — many features → a few semantic ones.
The distributional hypothesis
What is “context”?
Distributional similarity
“You shall know a word by the company it keeps.” — J. R. Firth, 1957.
Words that occur in similar contexts have similar meanings.
“We took two hours to reach the top of the hill.”
“The top of the hill had the best view.”
“This purple top will go well with my blue jeans.”
The surrounding words tell you which sense of top is meant — context is the signal we learn from.
Word2Vec · key idea
A word is known by the company it keeps
The duck test
“If it walks like a duck and quacks like a duck, it must be a duck.” The blanks share a context:
like a __ and quacks · like a __ it must · be a __.
Form ⟨word, context⟩ pairs by sliding a window over the text.
Learn vectors so a word predicts the words around it.
Q: how do we turn “predict the context” into something trainable?
The encoder view
The word2vec model
Context vector × Win → a small hidden representation × Wout → predicted center word.
Input/output are vocabulary-sized (millions); the hidden layer is tiny (≈ 300).
Reading it as classification
Word2vec as multi-class classification
A shallow net: input layer WV×N → hidden h → output W′N×V.
Given a word we predict its context; each vocabulary word is one output class.
How the parameters are learned
Training with gradient descent
Softmax over the vocabulary
The output layer turns scores into probabilities with a softmax, trained against the true context word
with cross-entropy loss.
ŷij= softmax(wj · xi) =e wj · xi ∑ℓ=1V e wℓ · xi
Scores = dot products of the center word with every vocabulary word; gradient descent nudges the vectors to raise the true context word's probability.
Making softmax affordable · not exam material
Negative sampling
Why the denominator hurts
The softmax denominator sums over all V words — with V in the millions, every update is far too expensive.
Negative sampling: instead of all N words, update only the true context word plus a few
C random “negative” words. Cheap, and works well in practice.
Marked in the slides as not exam material — but it is exactly what makes word2vec (and node2vec) trainable at scale.
Question
A trained word2vec model has learned good vectors. Where do those vectors actually live — which numbers in the model are the parameters you updated?
The model is “just” two matrices.
Think — then → for the answer.
The answer to “where are the embeddings?”
Parameters are the embeddings
We never use the predictions — we keep the weights. The hidden-layer vector for a word is its
word embedding; the task was just a pretext to learn good vectors.
Input vs. output embeddings
Word2vec learns two matrices
Both Win (the Embedding matrix) and Wout (the Context matrix) are
vocab × embedding-size. The input embeddings are usually taken as the final word vectors.
What the vectors capture
The geometry of embeddings
Analogies become arithmetic
Directions in the space encode relationships, so analogies can be solved by adding and subtracting vectors.
vec(king) − vec(man) + vec(woman) ≈ vec(queen)
The man → woman direction is roughly the same as king → queen.
Good embeddings are often pre-computed and freely available (e.g. via gensim).
Part III
Applying embeddings to supervised tasks
Embeddings are learned without labels — then plugged into a supervised model as features.
Documents → classes
Text classification
Embed each document, then run the ordinary pipeline — train data → learning algorithm → model →
predict the label (Physics · Chemistry · Maths) of a new document.
From words to documents
Representing a whole document
Bag of word-vectors
Each word is a vector. Represent a document as the average (or sum) of the vectors of the words it contains.
Simple, fast, and surprisingly strong as a baseline document representation.
Order is ignored — it is still a bag — but each dimension is now semantic, not a raw word count.
Libraries such as gensim provide word2vec and these aggregations out of the box.
Part IV
Graph embeddings
Reuse the word2vec idea on networks: random walks play the role of sentences — DeepWalk and node2vec.
The objective, for nodes
What we want from node embeddings
Encode each node so that similarity in the embedding space (the dot product zuᵀzv)
approximates similarity in the original network. Same recipe as words — different notion of context.
Question
Word2vec needs a word’s context window. A graph has no sentences and no left/right order. How could we reuse the very same method to embed nodes?
What plays the role of “a sentence” on a graph?
Think — then → for the answer.
Node embeddings · motivation from word2vec
Context on a graph = random walks
The analogy
In text, a sliding window gives each word its context. On a graph there is no linear order — so we
generate sequences by walking the network.
Random walks turn a graph into many short “sentences” of nodes.
Nodes that co-occur on walks play the role of words that co-occur in context.
Then run exactly the same skip-gram training on those sequences.
The random-walk objective
Random-walk embeddings
Make zuᵀzv approximate the probability that u and vco-occur on a random walk under strategy R: estimate PR(v | u), then optimize the vectors to encode it.
Used in the lab
Putting it together: two stages
1 · Create training data — sample random walks (fixed-window or biased).
2 · Train / optimize — given an input node, predict its walk neighbours with
skip-gram + negative sampling, then read off the embeddings.
Fixed-window walks
DeepWalk: unbiased fixed walks
Start at a random node, move to each neighbour with equal probability, and stop after a fixed length.
The same node may be sampled several times in one walk.
Biased walks · node2vec
node2vec: BFS vs. DFS neighbourhoods
Two ways to define a neighbourhood NR(u): BFS stays close — a local, microscopic view
of structure; DFS wanders far — a global, macroscopic view. node2vec interpolates between them.
The return and in-out parameters
node2vec: biasing the walk with p and q
From the current node: go back (weight 1/p), stay at the same distance (weight 1),
or move outward (weight 1/q). p controls revisiting; q trades BFS-like vs DFS-like exploration.
The loss, and why it is hard
Random-walk optimization
L = ∑u∈V ∑v∈NR(u)−logexp(zuᵀzv) ∑n∈V exp(zuᵀzn)
Sum over all start nodes u, and over each node v seen on walks from u.
The fraction is the predicted probability that u and v co-occur on a walk.
Done naïvely the nested sum is O(|V|²) — too expensive.
L ≈ log σ(zuᵀzv) − ∑i=1k log σ(zuᵀzni) , ni ∼ PV
Negative sampling again: normalise against k random negatives instead of all nodes (σ = sigmoid). not exam material
Embeddings first, labels later
Downstream: node classification
Learn f : u → ℝdwithout labels, then train a classifier on a subset of labelled nodes
to predict the rest (? → Physics / Chemistry / Maths).
Lecture 8 · wrap-up
Summary
Take away
Hand-crafted features are sparse, large, non-semantic. Embeddings replace them with
dense, small, semantic vectors where similarity ≈ dot product.
word2vec learns word vectors by predicting context over ⟨word, context⟩ pairs; the hidden-layer weights
are the embeddings, made trainable by negative sampling. Analogies become vector arithmetic.
Graph embeddings reuse the idea: random walks are sentences. DeepWalk uses fixed unbiased walks;
node2vec biases them with p, q to blend BFS (local) and DFS (global). Same skip-gram objective.
Where to read more
References
Mikolov et al., Distributed Representations of Words and Phrases and their Compositionality, NeurIPS 2013.
Perozzi, Al-Rfou & Skiena, DeepWalk: Online Learning of Social Representations, KDD 2014.