Graph Laplacian Operator

Let \(L\) be the Laplacian operator

Let \(f(x,y)​\) be \[ L: f \Longrightarrow \frac{\partial^2 f}{\partial x^2}+\frac{\partial^2 f}{\partial y^2}\tag{0} \]

Then Laplace equation refers to \(Lf=0\), thus \[ \frac{\partial^2 f(x,y)}{\partial x^2}+\frac{\partial^2f(x,y)}{\partial y^2}=0 \tag{1} \] A function satisfies formula (1) is called Harmonic function. Then lets discretize this function.

Assume \(f\) is a real function on \(\mathbb{Z}\), let's define \(f'\) a function on \(\mathbb{Z}+\frac{1}{2}\), and \(f'(\frac{1}{2}+n)=f(n+1)-f(n)\), eg. \(f'(\frac{1}{2})=f(1)-f(0)\). Then the second-order differential becomes a function on \(\mathbb{Z}\), and \(f''(n)=f(n+1)+f(n-1)-2f(n)\).

Considering 2-D situation, define \(f\) a function on \(\mathbb{Z}^2\), and formula (1) becomes: \[ f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y)=0 \tag{2} \] Formula (2) demonstrates the value of \(f\) on \((x,y)\) equals to average value of 4 points around \((x,y)\). Then we spread the conception to simple undirected graphs.

Define a simple undirected graph \(G=(V,E)​\), whose adjacency matrix is \(A​\) and degree matrix is \(D​\). The let \(L=D-A​\). Define \(f​\) a function on \(V​\), and the value of \(f(v)​\) on each node equals to the average value of nodes connected directly with this node, thus \[ \forall v\in V, f(v)=\frac{1}{\left|N(v)\right|}\sum_{u\in N(v)}f(u) \tag{3} \] among which \(N(v)=\{u\in V|uv \in E\}\)

We can consider \(f\) a vector on \(\mathbb{R}^n\), still written as \(f\). \[ V={v_1, v_2, \ldots,v_n} \\ \\ f = \begin{pmatrix} f(v_1)\\ f(v_2)\\ \vdots\\ f(v_n) \end{pmatrix} \tag{4} \] We can transform the condition a vector form: \[ (D-A)f=0 \Rightarrow Lf=0 \tag{5} \]