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

Wrap-up & Exam Prep

A fast recap of the three information-access topics — Embeddings · Graph Mining · Indexing Text — with the exact concepts, algorithms and skills that are examinable.
A. Anand · wrap-up study deck
The map for this session

Three topics, one way to revise each

Embeddings

  • Distances vertical
  • Dense, semantic features
  • Word2vec & random walks

Graph Mining

  • Matrices vertical
  • Properties, centrality, Laplacian
  • Spectral & Girvan–Newman

Indexing Text

  • Counting vertical
  • Inverted / forward indexes
  • Query processing
For each topic revise the same three layers: Concepts (what & why) → Algorithms (how) → Skills (apply it). The "Exam Material" slides list exactly these.
Part I

Embeddings

Turning raw data types into dense, semantic vectors — unsupervised, automatic feature extraction.
How do we vectorize our input data?

The classic ML approach

The pipeline raw data (tabular · graph · text · …) → split into train / test → compute features → learning algorithm → model → output.
Embeddings = unsupervised automatic feature extraction

From hand-crafted to learned features

Hand-crafted features

  • Sparse
  • Large (high-dimensional)
  • Non-semantic
  • Built by hand

Embeddings

  • Dense
  • Smaller (low-dimensional)
  • Semantic
  • Extracted automatically
An embedding is learned without labels, then reused as the input features for downstream supervised tasks.
High-dimensional → low-dimensional

Embeddings encode nodes (and words)

Original network on the left, two nodes u and v encoded into points z_u and z_v in an embedding space
An encoder ENC(·) maps each node (or word) to a point so that similarity in the embedding space (e.g. a dot product zu·zv) approximates similarity in the context. High-dimensional features → a few semantic ones.
Exam material · Embeddings

What to revise: Embeddings

Concepts

  • Sparsity
  • Dense representations
  • Bag of words
  • Random walks
  • Embeddings table

Algorithms

  • Word2vec
  • Random-walk algorithms

Skills

  • Applying embeddings to supervised tasks
  • The role of context
Part II

Graph Mining

Graph properties, centrality and clustering — read through the lens of matrices and eigendecompositions.
Graphs as matrices

Matrix representations & graph properties

From adjacency matrix we read… distance between nodes · eccentricity (farthest reachable) · radius (min eccentricity) · diameter (max eccentricity) · centrality measures.
The adjacency matrix A is symmetric for an undirected graph; row sums give node degree, and powers Ak count walks of length k.
123456
1011010
2101000
3110100
4001011
5100101
6000110
Graph partitioning · the Fiedler vector

Spectral clustering: split by eigenvector sign

Plot of the second-smallest eigenvector of the graph Laplacian over 20 nodes, values rising from negative to positive with a jump near the middle
The second-smallest eigenvector of the Laplacian (the Fiedler vector). Sorting its entries, the sign of each component assigns nodes to group A (negative) or B (positive) — a principled graph bisection.
Girvan–Newman · centrality computation

Community detection by edge betweenness

Two routes to clusters

Spectral clustering cuts using the Laplacian's eigenvectors; Girvan–Newman cuts by repeatedly deleting high-credit edges. Both turn a graph into groups.

Exam material · Graph Mining

What to revise: Graph Mining

Concepts

  • Graph representation
  • Properties based on distances
  • Centrality measures
  • Laplacian
  • Eigendecompositions

Algorithms

  • Spectral clustering
  • Girvan–Newman algorithm

Skills

  • Applying spectral decomposition to clustering
  • Generalizing bisection to multiple clusters
Part III

Indexing Text

The data structures that let us search massive text collections fast — the inverted index and its dictionary.
The core structure

The inverted index

Inverted index: terms but, heavier, is, jupiter each pointing to a postings list of document IDs
A lexicon (dictionary) of terms, each pointing to a postings list of the document IDs that contain it — e.g. is → 1, 3, 4, 5. Answering a query = intersecting / merging postings lists.
Data structures for indexing

Dictionary lookup & the forward index

Dictionary as a hash table with collision chains of terms and their IDs
Forward index: document 1 what does the fox say mapped to a row of term IDs 124, 53, 1, 49935, 100
Left: the dictionary as a hash table with collision chains, mapping a term to its ID. Right: a forward index — each document stored as its sequence of term IDs.
Exam material · Indexing Text

What to revise: Indexing Text

Concepts

  • Inverted indexes
  • Dictionary
  • Forward indexes
  • MapReduce

Algorithms

  • Query processing algorithms
  • Indexing algorithms

Skills

  • Dealing with large text collections
  • Dealing with query semantics
The spine of the whole course

Everything hangs off three verticals

Distances

  • Similarity & metrics
  • Embeddings for words & nodes
  • Context-based similarity

Matrices

  • Adjacency & Laplacian
  • Eigendecomposition / PCA
  • Graph mining & clustering

Counting

  • Hashing & sketching
  • Dictionaries & postings
  • Indexing text at scale
When a new exam question appears, first ask: is this fundamentally a distance, a matrix, or a counting problem?
How to prepare

Exam preparation checklist

For each topic, be able to…

State the concepts and why they matter, trace the algorithms by hand on a tiny example, and apply the skill to an unseen problem.

Worked examples worth re-running: encode nodes with Word2vec / random walks, bisect a graph with the Fiedler vector, delete edges with Girvan–Newman, and answer a query over an inverted index.

Wrap-up · one slide

Summary

Take away

Embeddings turn raw data into dense, semantic vectors (unsupervised); graph mining reads structure through matrices, the Laplacian and eigendecompositions; indexing makes massive text searchable with inverted and forward indexes.

All three sit on the course spine — Distances · Matrices · Counting. Revise each as Concepts → Algorithms → Skills, and practise the worked examples by hand. Good luck on the exam.