Trace of quadratic form with Laplacian matrix notation

Reading some papers about spectral graph analysis and graph neural networks I have found the following notation which I'm not too sure how to expand:

Given matrices $$F, L \in \mathbb{R}^{n \times n}$$, let's consider $$tr(F^TLF)$$.

Assuming that $$L:=D-A$$ is the laplacian associated to some adjacency matrix $$A$$ and $$F \in \mathbb{R}^{n \times n}$$,

1. How to expand the above formula?
2. What it actually represents?
• Your notation is inconsistent, because $\mathbb{R}^n$ is a set of vectors, not matrices, and unless $n=1$ the expression "$tr(F^\prime L F)$" is not defined.
– whuber
Commented Oct 2, 2021 at 19:21
• Sorry it’s just a typo. I meant that \$F, L \in \mathbb{R}^{n \ times n} for both the cases. Commented Oct 2, 2021 at 19:33

Let $$F_i$$ denote the $$i$$th column of $$F$$. Then the $$i$$th element of the diagonal of $$F^TLF$$ is $$F_i^TLF_i$$. It’s a standard result that a quadratic form with the Laplacian can be written as $$x^TLx = \sum_{u\sim v} A_{uv}(x_u - x_v)^2$$ where "$$u\sim v$$" means the sum is over all unordered pairs of edges, and this quantity can be interpreted as measuring how often $$x$$ assigns very different values to nearby nodes. This will be small when $$x$$ only changes over weak edges, and this is the idea behind spectral clustering: the bottom eigenvectors of $$L$$ give a way to assign values to the nodes that don’t have huge changes over strongly connected nodes.

This means $$\text{tr}(F^TLF) = \sum_i F_i^TLF_i$$ can be interpreted as the the total alignment of the columns of $$F$$ with the graph structure as encoded by $$A$$. If all of the columns of $$F$$ only change over loosely connected nodes, i.e. lie in the eigenspace of $$L$$ for small eigenvalues, then this will be small.

If we can diagonalize $$L$$ as $$L = Q\Lambda Q^T$$ (when $$A$$ is the adjacency matrix of an undirected graph this will always be possible via the spectral theorem for square and symmetric real-valued matrices) then we can write each column of $$F$$ with respect to the eigenbasis $$Q$$ as $$F_i = Qc_i$$ and then $$F = QC$$ for $$C = (c_1 \mid \dots \mid c_n)$$. This means $$\text{tr}(F^TLF) = \text{tr}(C^TQ^TQ\Lambda Q^TQC) = \text{tr}(C^T\Lambda C) = \|\Lambda^{1/2} C\|_F^2$$ where $$\|\cdot\|_F$$ denotes the Frobenius norm, and this similarly shows that $$\text{tr}(F^TLF)$$ will be small when the coordinates of the columns of $$F$$ w.r.t. the eigenbasis are concentrated on directions with small eigenvalues.

For more, I'd recommend Fan Chung's Spectral Graph Theory (chapter one here) as a great place to get more comfortable working with and interpreting graph Laplacians.