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.
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.