Quadratic form involving graph Laplacian

141 Views Asked by At

I have a connected undirected graph of $n$ nodes. Each node $i$ has a vector ${\bf x}_i$ and is connected to $d_i$ neighbours. Let $\tilde{{\bf L}} := {\bf L} \otimes {\bf I}_n$, where $\bf L$ is the graph Laplacian matrix and ${\bf I}_n$ is the $n \times n$ identity matrix. Furthermore, let ${\bf X} = \begin{bmatrix} {\bf x}_1 & \cdots & {\bf x}_n \end{bmatrix}$ be the concatenation of the vectors $\{ {\bf x}_i \}_{i=1}^n$. I want to find a matrix $\bf B$ (related to the graph) such that the term $${\bf X}^\top \left( \tilde{{\bf L}}^\top \tilde{{\bf L}} + {\bf B} \right) {\bf X}$$ can be expressed as a function of only ${\bf x}_i$ and $\sum\limits_{j \in \mathcal{N}_j} {\bf x}_j$, where $\mathcal{N}_j$ is the set of neighbours of node $i$.