Knowledge Discovery
Session 08

Graphs and Graph Metrics

4 hours · Week 8

DRAFT: This content is under development. Check back closer to the course start date.

Notebooks for this session

Four runnable Jupyter notebooks — three worked demos and one hands-on exercise. Open them straight from docs/08_graphs/demos/; setup instructions are under Hands-on demos below.

Demo D1
DeepWalk embeddings, from scratch
Random walks → skip-gram in PyTorch on a 3-community synthetic graph. Watch noise turn into clusters during training.
Demo D2
NetworkX playground
Layouts, four centrality measures, and PageRank re-implemented from scratch on Zachary's Karate Club.
Demo D3
node2vec, link prediction & GNNs
Four acts on the Karate Club: biased walks and the p/q knobs, hidden-edge prediction, and a GCN with PyTorch Geometric.
Exercise
Build node embeddings yourself
Skeleton notebook — fill in six TODO lines to build the whole DeepWalk pipeline end to end.

Learning Objectives

  • Represent real-world systems as graphs: nodes, edges, directed/undirected, weighted, bipartite
  • Compute and interpret centrality measures: degree, betweenness, closeness, eigenvector
  • Understand PageRank and random-walk based importance
  • Reason about structural properties: connected components, diameter, clustering coefficient

Topics

Hands-on demos

Full descriptions of the four notebooks linked at the top of this page — runnable on a laptop in seconds. Code lives in docs/08_graphs/demos/.

D1 · DeepWalk node embeddings

A synthetic 60-node graph with three planted communities, shown three ways (force-directed picture, adjacency matrix, degree distribution). Then trains DeepWalk-style node embeddings from scratch with PyTorch (random walks → skip-gram with negative sampling), snapshots the 2-D embeddings during training, and ends with a 1-NN community-prediction sanity check (~96% accuracy).

  • Notebook (.ipynb) — narrated, with discussion of why the triangle geometry emerges
  • Script (.py) — same code, saves fig1_graph_representations.png and fig2_embeddings_evolution.png

D2 · NetworkX playground

Hands-on tour for students. Build a small graph from an edge list, draw it with four different layouts, compute basic stats and four centrality measures (degree, betweenness, closeness, PageRank) on Zachary's Karate Club, then re-implement PageRank from scratch in ten lines of NumPy and verify it matches nx.pagerank to ~10−6. Closes with a tiny directed-web example and four scaffolded exercises.

  • Notebook (.ipynb) — the headline interactive demo for this lecture
  • README — full description of all demos and the exercise

D3 · node2vec, link prediction & GNNs

Picks up where D1 ends and runs four "acts" on Zachary's Karate Club: node2vec's biased random walk (the p/q knobs) and how it switches the embedding between homophily and structural roles; an interactive p/q explorer; link prediction by hiding 20% of edges and scoring them back (ROC/AUC); and a 2-layer GCN in PyTorch Geometric trained from just 4 labelled nodes — bridging into the GNN material in session 10.

  • Notebook (.ipynb) — needs torch-geometric and ipywidgets (both in requirements.txt)

Exercise · Build node embeddings yourself

A skeleton notebook for students. The graph, helper code, and the skip-gram model are provided; you fill in six # TODO lines that are the real ideas — the random-walk step, the sliding-window (target, context) pairs, the PyTorch training step, the embedding scatter plot, and the KMeans sanity-check. Ends with a free-form playground and wrap-up questions. Covers the basic DeepWalk pipeline only; demo D1 is the fully worked version.

How to run

With uv — no environment to manage, dependencies fetched on the fly:

cd docs/08_graphs/demos
uv run --with-requirements requirements.txt --with jupyterlab jupyter lab

Or the classic way:

cd docs/08_graphs/demos
python -m venv .venv
source .venv/bin/activate           # on macOS / Linux
pip install -r requirements.txt
jupyter lab

Demo D1 also runs as a plain script: python demo_d1_graph_node_embeddings.py. Demo D3 needs torch-geometric (included in requirements.txt — CPU is fine, no GPU build required).

Materials