blog why graph laplacian is like a laplacian

Why the Graph Laplacian is Like a Laplacian

The Laplacian is an important differential operator, and the graph Laplacian is an important graph associated with matrices. As you'd expect from the names, they're related! But I haven't always seen the relationship laid out clearly (for example Wikipedia's page on the graph Laplacian devotes only two fairly unclear sentences to it). This is probably one of those things experts (which I'm not) don't talk about so much because it's so obvious to them.

Laplacian and Diffusion

Imagine heat diffusing in one dimension. Heat flows into the interval $(x,x+\epsilon)$ at its boundaries, at a rate proportional to the heat differential at the boundaries. A positive difference at the right edge means heat is flowing in while a positive difference at the left edge means heat is flowing out. So the rate of change of heat in the region $(x,x+\epsilon)$ is $f'(x+\epsilon) - f'(x)$. That heat has to fill up an interval of length $\epsilon$, so the change in temperature is $\frac{f'(x+\epsilon) - f'(x)}{\epsilon}$.

If we let the size of our region go to zero...

discrete approximation

manifolds

manifolds

[another approach: start with diffusion after finite time t, differentiate to get instantaneous version / laplacian]

Graph Laplacian

it's a matrix, so it's a linear operator on. what does it operate on? vectors. what are vectors? functions on the graph.

why what it does to the function on the graph is like the above

The Graph Laplacian converges to the Laplacian

Mikhail Belkin and Partha Niyogi

Uses

diffusion in graphs (pagerank isn't quite the same thing, but close)---"solution" (stable point) of pagerank is the highest eigenfunction

smoothness of functions on graphs

machine learning on manifolds

plenty of examples with learning on manifolds