eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit

[[concept]]

Theorem

Let ${G_{n}}$ be a convergent graph sequence with limit graphon $W$ . Then

lim_{n \to \infty} \frac{λ_{j} (A_{n})}{n} = λ_{j} (W) = lim_{n \to \infty} λ_{j} (T_{W_{n}})

ie, the eigenvalues of the induced graphon converge to the eigenvalues of the limit.

Where

$A_{n}$ is the adjacency matrix of $G_{n}$
$W_{n}$ is the graphon induced by $A_{n}$
$T_{W_{n}}$ the graphon shift operator for $W_{n}$

Proof

$W_{n} (u, v) = \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) 1 (v \in I_{j})$ $A_{n} = V_{n} Λ_{n} V_{n}^{*}$

Thus

\begin{aligned} T_{W_{n}} φ (v) & = \int_{0}^{1} W_{n} (u, v) φ (u) d u & = λ φ (v) \\ = \int_{0}^{1} \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) 1 (v \in I_{j}) φ (u) d u & = λ φ (v) \\ = 1 (v \in I_{j}) \int_{0}^{1} \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) φ (u) d u & = λ φ (v) \\ ⟹ & = \sum_{i, j = 1}^{n} [A_{n}]_{i j} \int_{0}^{1} 1 (u \in I_{i}) φ (u) d u & = λ φ (v \in I_{j}) \end{aligned}

LHS is a constant for each $v \in I_{j}$ . This means that $φ$ is a step function $φ (v \in I_{j}) = x_{j}$ . Thus, we can rewrite the last line as

\begin{aligned} λ x_{j} & = \sum_{i = 1}^{n} [A_{n}]_{i j} x_{i} \frac{1}{n} \end{aligned}

since for each $i$ we have $φ (u) = {\begin{cases} x_{i}, x_{i} \in I_{i} \\ 0, otherwise \end{cases}$ . The above is just a matrix multiplication, so we get

\begin{aligned} ⟹ λ x & = \frac{1}{n} A_{n} x \\ ⟹ λ_{j} (T_{W_{n}}) & = \frac{λ_{j} (A_{n})}{n} \forall j \end{aligned}

For convergence, this means that

\begin{aligned} (1) & t (c_{k}, G_{n}) & = \sum_{i = 1}^{n} λ_{i}^{k} \\ (2) & t (c_{k}, G_{n}) & \to \tilde{t} (c_{k}, W) \end{aligned}

where

$c_{k}$ is the $k$ -cycle graph
$t$ is the graph homomorphism density
$\tilde{t}$ is the graphon homomorphism density

(the full proof involves writing out the expressions for (1) and showing (2) that the elements in the sum converge pointwise. We do not show this for this class.)

Mentions

File
2025-03-31 lecture 16
2025-04-02 lecture 17
the graph convolution converges to the graphon convolution in the spectral domain for a convergent sequence of graph signals

const { dateTime } = await cJS()

return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}