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

Graph Mining

Representing graphs as matrices, measuring structure, finding central nodes and communities — with spectral clustering, Girvan–Newman, and node embeddings.
A. Anand · lecture 13 study deck
Part I

Graphs are everywhere — and massive

What a graph is, what questions it answers, and how we store one on a computer.
Many real-world datasets are graphs

Why graphs?

People & web

  • Social networks
  • Web graphs (pages & links)
  • Citation networks

Science

  • Protein–protein interactions
  • Molecules
  • XML / parse trees

Infrastructure

  • Road networks
  • Internet routing
  • Product / co-purchase graphs
These graphs are massive — we need automatic methods to understand them, not eyeballing.
What's possible with graphs · routing

Finding shortest paths

Google Maps route from The Hague to Leiden over the road network
A route is a shortest path on a weighted road graph. The same primitive powers internet routing and "degrees of separation" in social networks.
What's possible with graphs

Important nodes & communities

  • Finding important nodes — social-media influencers & early adopters, authoritative web pages, key proteins. PageRank is the classic algorithm.
  • Discovering communities — groups of developers / customers, clusters of related papers in a citation network.
  • Both reduce to structure: who is connected to whom, and how densely.
Graph with a highlighted central node among two colored clusters
The vocabulary

What is a graph?

Graph G = (V, E) A set of vertices V with |V| = n and a set of edges E with |E| = m. Edges may be directed or undirected, and optionally weighted.
How to store a graph

Three ways to store a graph

Adjacency matrix

  • n × n, entry aij=1 if edge i–j
  • O(n²) space — dense, even if few edges
  • Edge lookup in O(1); enables linear algebra

Adjacency list

  • Per node, a list of neighbours
  • O(n + m) space — great for sparse graphs
  • Neighbour iteration is fast

Edge list

  • Just the set of (u, v) pairs
  • O(m) space — simplest
  • Slow for "are i, j adjacent?"
Real graphs are sparse (m ≪ n²), so lists save memory — but the matrix view unlocks spectral methods.
Part II

Graph properties

Distances, small-world and scale-free structure — the characteristics real networks share.
The data-miner's warning

Why study graph properties?

Key idea

Many real-world graphs share the same structural characteristics. Explaining why they appear is a core area of network research.

As data miners we must know the consequences: a "finding" that is fully explained by a generic property (e.g. a few huge-degree hubs) is not interesting — it is what any such graph would show.

Distances in a graph

Eccentricity, radius & diameter

A property of real networks

The small-world property

Small-world A graph is small-world if its average path length grows only logarithmically with the number of nodes — avg path ∝ log n. Any two nodes are reachable in surprisingly few hops.
The World Wide Web · Broder et al., WWW'00

Scale-free: power-law degrees

Log-log in-degree and out-degree distributions of the web, straight lines
Web in-degree follows a power law with exponent γ ≈ 2.09, out-degree γ ≈ 2.72 — straight lines on a log–log plot. Most nodes have tiny degree; a few are huge hubs.
The degree distribution

The scale-free property

Degree distribution f(k) = number of vertices with degree k. A graph is scale-free if f(k) ∝ k−γ — a power-law distribution.
f(ck) = α(ck)−γ = (α c−γ) k−γ  ∝  k−γ
"Scale-free" = rescaling the degree axis by c just rescales the curve — the shape is unchanged. The majority of vertices have small degree; a few hubs have very high degree.
Question
In a network of millions, which few nodes act as bridges between communities — the ones whose removal would split the graph apart?
Not necessarily the most-connected nodes.
Think — then → for the answer.
Part III

Centrality — which nodes matter

Degree, eccentricity, closeness and betweenness — and Girvan–Newman for communities.
Ranking vertices by importance

What is centrality?

Definition A centrality is a function c : V → ℝ that induces a total order on vertices. The higher c(v), the more important / central the vertex. The more central a node, the faster it reaches the rest of the graph.
The two simplest measures

Degree & eccentricity centrality

Degree centrality c(vi) = d(vi) — simply the degree of the vertex. More neighbours = more central.
Eccentricity centrality c(vi) = 1 / e(vi) — the least eccentric vertex is the most central; the most eccentric is peripheral.
Minimise the average distance

Closeness centrality

Closeness The vertex with the least total distance to all others is the centre:
c(x) = 1∑y≠x∈V d(y, x)
Lying on many shortest paths

Betweenness centrality

Betweenness
b(x) = ∑s≠x≠t σst(x)σst
σst = number of shortest paths s→t; σst(x) = how many of them pass through x.
Computing betweenness efficiently

The Girvan–Newman algorithm

Stage 1

Pre-processing & BFS

Root the graph at a node; run BFS top-down. Level = shortest-path length from root; each node's label = sum of its parents' labels (number of shortest paths from root).

Stage 2

Credit assignment

Work bottom-up, assigning credit to nodes and edges based on the BFS labels.

Stage 3

Aggregation

Repeat for every root node, then sum credits to get final betweenness.

Girvan–Newman · the bottom-up rules

Credit assignment

Example: a node reached via B (label 3) and G (label 1) sends ¾ of its credit up to B and ¼ to G.
From betweenness to communities

Clustering by removing weak ties

Girvan–Newman community detection

Edges between communities carry the most shortest paths — highest edge betweenness. So we cut them:

Part IV

Spectral clustering

Represent the graph as a matrix, then use its eigenvectors to find communities.
What makes a good partition?

Graph partitioning

A good partition Split V into groups that maximise within-group connections and minimise between-group connections.
Matrix representations · a 6-node example

Adjacency matrix A

123456
1011010
2101000
3110100
4001011
5100101
6000110
n × n,  aij = 1 if there is an edge between i and j.

Symmetric for undirected graphs → its eigenvectors are real and orthogonal.
From A to the Laplacian

Degree matrix D and Laplacian L = D − A

Degree matrix D (diagonal, dii = deg i)
300000
020000
003000
000300
000030
000002
Laplacian L = D − A (symmetric)
3-1-10-10
-12-1000
-1-13-100
00-13-1-1
-100-13-1
000-1-12
Every row of L sums to 0 → the all-ones vector is an eigenvector with eigenvalue λ₁ = 0.
Why the matrix view helps

What does A·x mean?

Neighbour averaging If x assigns a label xj to each node j, then y = A·x gives yi = ∑j∈N(i) xj — each entry is the sum of its neighbours' labels.
Eigenvectors

An eigenvector x with A·x = λx is a labelling that is reproduced (up to scale λ) by neighbour-summing.

For a d-regular graph the all-ones vector is an eigenvector with eigenvalue λ = d. These special labellings encode global structure — the basis of spectral clustering.

The second eigenvector of L

λ₂ and the Fiedler vector

Key fact The smallest Laplacian eigenvalue is λ₁ = 0. The second eigenvalue λ₂ (algebraic connectivity) and its eigenvector x₂ — the Fiedler vector — reveal the best split.
  • λ₂ solves a relaxed minimum-cut optimisation.
  • Sorting nodes by their value in x₂ puts the two communities on opposite signs.
Sorted values of the second eigenvector with a sharp jump at the middle
The sorted x₂ values show a sharp jump near zero — a clean two-way split.
The algorithm in three stages

Spectral clustering

1 · Pre-processing

Build the matrix

Construct a matrix representation of the graph — the (unnormalised) Laplacian L = D − A.

2 · Decomposition

Eigen-decompose

Compute eigenvalues/eigenvectors of L. Map each node to a low-dimensional representation using one or more eigenvectors (start with x₂).

3 · Grouping

Assign clusters

Split the nodes in the new representation into two (or more) clusters.

Stage 3 · where to split

Choosing the splitting point

The eigenvector gives the order; the sweep picks the single best cut point along it.
Spectral partitioning in action

Example: two communities

Graph with dense clusters joined by a few edges
Sorted second eigenvector with one jump
Left: dense clusters joined by sparse bridges. Right: the sorted Fiedler vector x₂ — the single jump at the middle is exactly where the two communities separate.
More than two communities

Reading several clusters from the spectrum

Sorted second eigenvector of a 40-node graph with several plateaus
Third eigenvector components showing block structure
The sorted x₂ (left) shows several plateaus — candidate groups. Using more eigenvectors (x₃, right) exposes additional block structure for finer partitions.
Partitioning into k clusters

k-way spectral clustering

Recursive bi-partitioning

  • Hagen et al., 1992
  • Apply the 2-way split recursively, hierarchically
  • Disadvantage: inefficient and unstable

Multiple eigenvectors

  • Shi–Malik, 2000
  • Build a reduced space from the first k eigenvectors, then cluster (e.g. k-means)
  • The preferred modern approach
Using several eigenvectors at once gives a stable k-dimensional embedding of each node.
Eigenvectors as node embeddings

From eigenvectors to embeddings

Spectral embedding Stacking a node's values across the top eigenvectors gives a low-dimensional vector per node — a graph embedding where connected / similar nodes land close together.
Transductive vs inductive

Transductive: the embedding is computed for the fixed graph you have — a new node means recomputing the eigenvectors.

Inductive: learn a function that embeds any node, so unseen nodes get vectors without redoing the decomposition.

Part V

Node embeddings & the lab

Random walks, Node2Vec / DeepWalk, and the Medium-articles assignment.
Lab assignment · Medium articles

A real-world graph: Medium articles

Neo4j knowledge graph of Medium articles linked to tags, lists and authors
Articles connect to tags, reading lists and authors. Task: a 3-way classification of articles into software-dev, AI and UX from the graph structure.
Building a node graph from relations

Monopartite projection

Bipartite article-list graph projected to an article-article common-list graph
The raw graph is bipartite (articles ↔ lists). Project it to an article–article graph: two articles sharing a list get a COMMON_LIST edge — now spectral / walk methods apply.
The assignment pipeline

Dataset → embedding → classifier

1

Graph construction

Build the Medium article graph from subscription / tag / list relations.

2

Random walks & embedding

Generate node embeddings — spectral (Laplacian) or random-walk based.

3

Classification

Feed embeddings to a classifier for the 3-way topic prediction.

Two embedding routes to compare: spectral (eigenvectors of L) vs random walks.
Two ways to embed nodes

Spectral embeddings vs random walks

Spectral embeddings

  • Build the (unnormalised) Laplacian L
  • Compute its eigenvalues & eigenvectors
  • Use the top eigenvectors as node vectors

Random walks

  • Start at a node, randomly traverse edges
  • Fixed-length walks from every node
  • Walks → "sentences" → embeddings
Random walks power the popular node-embedding methods DeepWalk and Node2Vec: treat each walk as a sentence of node-IDs and learn vectors with a word2vec-style model.
Lecture 13 · wrap-up

Summary

Take away

Graphs are everywhere and large — stored as adjacency matrix / list / edge list. Real networks are small-world (log paths) and scale-free (power-law degrees).

Centrality ranks nodes — degree, eccentricity, closeness, betweenness; Girvan–Newman cuts high-betweenness edges to find communities.

Spectral clustering uses the Laplacian's eigenvectors (the Fiedler vector x₂) to partition a graph, and generalises to node embeddings — spectral or random-walk based (DeepWalk, Node2Vec).