why $\frac{1}{2} \sum_{i, j} \mathbf{A}^{(t)}(i, j)\left\|\mathbf{y}_i-\mathbf{y}_j\right\|_2^2$ can boils down to a generalized eigen-problem

Question

I'm reading a paper, it writes "$\frac{1}{2} \sum_{i, j} \mathbf{A}^{(t)}(i, j)\left\|\mathbf{y}_i-\mathbf{y}_j\right\|_2^2$ can boils down to a generalized eigen-problem" (snapshot: part1 and part2). But I don't know why. May anyone explain it for me?

Answer 1

Suppose that the adjacency matrix $\mathbf{A}$ is symmetric and consider the matrix $\mathbf{Y}$ whose $n$th row is $\mathbf{y}_n^T$.

Part 1: It is straightforward to see that \begin{eqnarray*} \phi(\mathbf{Y}) &=& \frac12 \sum_{i,j} \mathbf{A}_{ij} \left\|\mathbf{y}_i-\mathbf{y}_j\right\|_2^2 \\ &=& \frac12 \sum_{i,j} \mathbf{A}_{ij} \left\|\mathbf{y}_i\right\|_2^2 + \frac12 \sum_{i,j} \mathbf{A}_{ij} \left\|\mathbf{y}_j\right\|_2^2 - \sum_{i,j} \mathbf{A}_{ij} \mathbf{y}_i^T\mathbf{y}_j \\ &=& \sum_{i} \left( \sum_j \mathbf{A}_{ij} \right) \mathbf{y}_i^T\mathbf{y}_i - \sum_{i,j} \mathbf{A}_{ij} \mathbf{y}_i^T\mathbf{y}_j \\ &=& (\mathbf{D-A}):\mathbf{Y}\mathbf{Y}^T \\ &=& \mathbf{L}:\mathbf{Y}\mathbf{Y}^T \\ &=& \mathrm{tr}(\mathbf{Y}^T \mathbf{L} \mathbf{Y}) \end{eqnarray*} where $\mathbf{L}=\mathbf{D-A}$ and $\mathbf{D}$ is the diagonal matrix with elements $D_{ii}=\sum_j A_{ij}$.

Here the column operator $:$ denotes the Frobenius inner product between two products $\mathbf{A}:\mathbf{B}=\sum_{ij} A_{ij}B_{ij} = \mathrm{tr}(\mathbf{A}^T \mathbf{B})$.

Part2 : Setting the gradient to $0$ yields the linear system $\mathbf{LY}=\mathbf{0}$. The eigenvalue remains to be found but this is clearly the right path. I assume some hypotheses are missing to go further...