What's the derivative of degree (Laplacian) matrix with respect to adjacency matrix? For a symmetric adjacency matrix $A\in \{0, 1\}^{n \times n}$, the degree is defined as $D_{ii} = \sum_i A_{ij} = \sum_j A_{ij}$.
What the derivative of the degree matrix w.r.t. adjacency matrix?
I know it's a 4-dimensional tensor.
Taking $n=3$ as example
$$
\frac{\partial D_{00}}{\partial A} = 
\begin{pmatrix} 
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0 
\end{pmatrix}
$$
or
$$
\frac{\partial D_{00}}{\partial A} = 
\begin{pmatrix} 
1 & 0 & 0 \\
1 & 0 & 0 \\
1 & 0 & 0 
\end{pmatrix}
$$
or
$$
\frac{\partial D_{00}}{\partial A} = 
\begin{pmatrix} 
1 & 1/2 & 1/2 \\
1/2 & 0 & 0 \\
1/2 & 0 & 0 
\end{pmatrix}
$$
or
$$
\frac{\partial D_{00}}{\partial A} = 
\begin{pmatrix} 
0 & 1/2 & 1/2 \\
1/2 & 0 & 0 \\
1/2 & 0 & 0 
\end{pmatrix}
$$
which one is correct?
Ideally, it should be symmetric, and the element on the diagonal should be 1 or 0?
 A: The derivative you are looking has definitely to be symmetric.
Let $\phi=D_{00}=\mathrm{tr}(A_{00}+A_{01}+A_{02})$
and consider the perturbation
$$
d\mathbf{A}=
\begin{pmatrix}
0 & 0 & h \\
0 & 0 & 0 \\
h & 0 & 0
\end{pmatrix}
$$
We know that this pertubation should yield to $d\phi=h$.
The relation
$d\phi= \frac{\partial D_{00}}{\mathbf{A}}:d\mathbf{A}$ is correct iff
$$
\frac{\partial D_{00}}{\mathbf{A}}
=
\begin{pmatrix}
1 & 1/2 & 1/2 \\
1/2 & 0 & 0 \\
1/2 & 0 & 0
\end{pmatrix}
$$
A: $
\def\c#1{\color{red}{#1}}
\def\m#1{\left[\begin{array}{r}#1\end{array}\right]}
\def\o{{\large\tt1}}\def\d{{\theta}}\def\e{{\large\varepsilon}}
\def\E{{\cal E}}\def\F{{\cal F}}\def\G{{\cal H}}
\def\L{\left}\def\R{\right}
\def\LR#1{\L(#1\R)}
\def\BR#1{\Big(#1\Big)}
\def\bR#1{\big(#1\big)}
\def\vecc#1{\operatorname{vec}\LR{#1}}
\def\Sym#1{\operatorname{Sym}\LR{#1}}
\def\diag#1{\operatorname{diag}\LR{#1}}
\def\Diag#1{\operatorname{Diag}\LR{#1}}
\def\trace#1{\operatorname{Tr}\LR{#1}}
\def\qiq{\quad\implies\quad}
\def\p{\partial}\def\grad#1#2{\frac{\p #1}{\p #2}}
$Use the all-ones vector $\{\o\}$ and the tensors $\{\d,\G\}$ with components
$$\eqalign{
\d_{ijk} &= \begin{cases}
\o\quad{\rm if}\;(i=j=k) \\
0 \quad{\rm otherwise} \\
\end{cases} \\
\G_{ijk\ell} &= \begin{cases}
\o\quad{\rm if}\;(i=j)\;{\rm and}\;(k=\ell) \\
0 \quad{\rm otherwise} \\
\end{cases} \\
}$$
to write the degree matrix in the following form and calculate its gradient
$$\eqalign{
D &= \Diag{A\cdot\o} &= \d\cdot\bR{A\cdot\o} \\
dD &= \bR{\d\cdot dA\cdot\o} &= \bR{\d\cdot\G\cdot\o}:dA \\
\grad{D}{A} &= \bR{\d\cdot\G\cdot\o} &= \bR{\d\star\o}
 \qquad \big({\rm "\!\!the\;gradient\!\!"}\big) \\
}$$
where $(\star)$ denotes dyadic product, $(\cdot)$ the single dot product, and $(:)$ the double dot product.
The gradient is a $4^{th}$order tensor, which admits 2 different decompositions into matrix-valued components. Multiplying on the left by the Cartesian basis matrix $E_{ij}$
produces the components
$$\eqalign{
&E_{ij}:\LR{\grad{D}{A}} = E_{ij}:\bR{\d\star\o} \\
&\c{\grad{D_{ij}}{A}} = \diag{E_{ij}}\cdot\o^T \\
}$$
while multiplying on the right produces components
$$\eqalign{
&\LR{\grad{D}{A}}:E_{ij}
  = \bR{\d\star\o}:E_{ij} \\
&\grad{D}{A_{ij}}
  = \bR{\d\cdot E_{ij}\cdot\o}
  = \bR{\d\cdot\e_i} 
  = \Diag{\e_i} 
  = E_{ii} 
\\
}$$
where $\e_i$ is a Cartesian basis vector and $\,E_{ij}=\e_i\e_j^T$

So in your example, the first matrix is the correct one since
$$
\c{\grad{D_{00}}{A}}
 = \diag{E_{00}}\cdot\o^T
 = \m{1\\0\\0}\cdot\m{1&1&1} 
 = \m{1&1&1\\0&0&0\\0&0&0} 
$$
Note that Diag(v) converts a vector into a diagonal matrix,
while diag(M) extracts the diagonal of a square matrix into a vector.

Oops! I forgot the symmetry constraint on $A$. But that merely symmetrizes the gradient, so
$$
\Sym{\grad{D_{00}}{A}}
 = \frac 12\LR{\m{1&1&1\\0&0&0\\0&0&0}+\m{1&1&1\\0&0&0\\0&0&0}^T}
 = \frac 12 \m{2&1&1\\1&0&0\\1&0&0}
$$
which is your third matrix.
