Graph Basics: Adjacency, Degree, and Laplacian

Let $G=(V,E)$ be an undirected unweighted graph with nodes

$$V=\{1,\ldots,n\}.$$

The adjacency matrix $A\in\{0,1\}^{n\times n}$ is

$$A_{ij}= \begin{cases} 1, & \text{if }\{i,j\}\in E,\\ 0, & \text{otherwise.} \end{cases}$$

Because the graph is undirected, $A$ is symmetric.

The degree of node $i$ is

$$d_i=\sum_{j=1}^{n}A_{ij}.$$

The degree matrix is diagonal:

$$D_{ii}=d_i,\qquad D_{ij}=0\text{ for }i\ne j.$$

The combinatorial graph Laplacian is

$$L=D-A.$$

Now put a scalar signal on the graph:

$$x=(x_1,\ldots,x_n)^\top.$$

The matrix-vector product $Lx$ has one row per node:

$$(Lx)_i = d_i x_i-\sum_{j:\{i,j\}\in E}x_j.$$

So $(Lx)_i$ compares node $i$ to its neighbors. If $x_i$ agrees with nearby values, the row is small. If $x_i$ disagrees sharply, the row is large.

The global smoothness energy is the quadratic form

$$x^\top Lx.$$

For an undirected unweighted graph,

$$x^\top Lx = \sum_{\{i,j\}\in E}(x_i-x_j)^2.$$

This identity is the key mechanism. The Laplacian turns local edge disagreements into a single scalar. Smooth graph signals have low energy. Signals that alternate across many edges have high energy.

The same matrices later support several ML operations:

• graph neural networks use adjacency-like neighborhoods for message passing;
• spectral clustering studies eigenvectors of Laplacian matrices;
• graph regularization penalizes functions that vary too much across nearby nodes.

Those later topics add normalization, weights, directed edges, and learned features. This page keeps the first invariant visible: graph structure becomes matrix arithmetic.