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}$,

*

*How to expand the above formula?

*What it actually represents?


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.
