⌂ Lectures
← →/space · tap / swipe to advance · F fullscreen
CSE2525 · Data Mining · 2026–27

Embeddings

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.
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 input you design hand-crafted features model learns learned embedding same job — but the features are learned, not engineered
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

(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

one-hot · 50,000 dims, a single 1 × E (lookup) embedding · ~300 dims, every entry meaningful
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.
The objective in one picture

What we want from an embedding

parliamentsenatetaxvote same company → close different company → far apart
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.
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 __.
The encoder view

The word2vec model

one-hot (V) EV×d v bottleneck (d) Ud×V softmax over V
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

water E,U softmax over the whole vocabulary spots (the true neighbour) one center word → a probability for every vocabulary word
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

embedding matrix E  (V × d) ← row = “cat” the numbers in these rows are the parameters θ — gradient descent updates them directly
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

E — input / center word i → U — output / context every word gets two vectors — one row in each table
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

woman queen +royal+royal king − man + woman ≈ queen — a direction the model was never told
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)
Part III

Applying embeddings to supervised tasks

Embeddings are learned without labels — then plugged into a supervised model as features.
Documents → classes

Text classification

document look up average doc vector clf a whole document becomes one vector — the average of its word vectors
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.
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

nodes close in the graph should get nearby vectors
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.
The random-walk objective

Random-walk embeddings

a random walk “ 4 3 2 6 ” walk = a sentence node vectors
Make zuᵀzv approximate the probability that u and v co-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

Stage 1 · unsupervised graph → walks → node vectors Stage 2 · supervised vectors + labels → classifier
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

DeepWalk: take uniform fixed-length walks from every node → “sentences”
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

BFS · local (structural role) DFS · far-reaching (community)
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

t v (here) return 1/pstay close q biggo far q small p, q bias the walk between BFS-like and DFS-like exploration
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) −log exp(zuᵀzv)
∑n∈V exp(zuᵀzn)
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

? embed every node, then a classifier labels the unknown from its neighbours’ vectors
Learn f : u → ℝd without 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