Finding the optimal adjacency matrix

117 Views Asked by At

Notation: Let $\mathbf{A} \in \{0,1\}^{n \times n}$ be the adjacency matrix of an undirected graph. Let $\mathbf{D}$ be the degree matrix of this graph and let $\mathbf{L} = \mathbf{D} - \mathbf{A}$ be the Laplacian matrix. The normalized Laplacian matrix $\mathbf{L}_N$ is defined as

\begin{equation} \mathbf{L}_N := \mathbf{D}^{-1/2} (\mathbf{D} - \mathbf{A}) \mathbf{D}^{-1/2} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2}. \end{equation}

Given an initial adjacency matrix $\mathbf{A}^0$, a constant $b > 0$ and a matrix $\mathbf{Z} \in \mathbb{R}^{m \times n}$, consider the following two optimization problems

\begin{equation} \min_{\mathbf{A}} \quad \mathsf{Tr} \left( \mathbf{Z} \mathbf{L} \mathbf{Z}^\top \right) \quad \text{s.t.}\quad \left\| \mathbf{A} - \mathbf{A}^0 \right\|_2 \leq b \tag{OP$_1$} \end{equation}

\begin{equation} \min_{\mathbf{A}} \quad \mathsf{Tr} \left(\mathbf{Z}\mathbf{L}_N\mathbf{Z}^\top \right) \quad \text{s.t.}\quad \left\| \mathbf{A} - \mathbf{A}^0 \right\|_2 \leq b \tag{OP$_2$} \end{equation}

where $\| \cdot \|_2$ is the $2$-norm and $\mathsf{Tr}(\cdot)$ denotes the trace. Which type do these optimization problems belong to? Any potential solution algorithms?