Chapter 2: Deep learning

Graphs as matrices: PageRank and spectral clustering

You will be able to turn a network into tables of numbers, rank its pages and split it into two groups. Search engines rank web pages this way, and interviewers ask about both steps. The graph networks of the next lesson use the same tables.

20 minInteractive lessonChapter 2: Deep learningLesson 16 of 20

What you will learn

  • Write a small graph as adjacency, degree and normalized adjacency matrices
  • Compute PageRank by power iteration and explain the damping factor
  • Explain how the Laplacian's second eigenvector splits a graph into two groups

Key terms

adjacency matrix $A$
a table with a 1 where two pages share a link, and 0 if not
degree $d$
a page's number of links, the sum of its row in A
normalized table $\hat{A}$
A with each 1 divided by the square root of both pages' degrees multiplied
PageRank
a score for how much time a random clicker spends on each page
Laplacian $L$
the table D minus A; it scores how much a signal changes along links

Prerequisites

Take Why transformers replaced RNNs: parallelism and teacher forcing first. It comes right before this lesson in the course.

Where this lesson picks up: In the last lesson, self-attention linked every pair of positions in one parallel step, while an RNN went one token at a time. Many real networks, such as web pages or bank accounts, link only some pairs, so how do you compute with just those links?

What comes next

Next lesson: Graph neural networks: message passing and link prediction

More lessons in this part

Take the lesson

Short cards, one idea at a time, with quick checks as you go.