$\mathbf{M}_l$ is low rank, which is a common assumption in distance metric learning [@liu15aaai; @luo2019robust].

Then the Mahalanobis distance in Eq. becomes $$\begin{split}
d_{\mathbf{M}_l}(\mathbf{f}^i_l,\mathbf{f}^j_l)  
&= \sqrt{(\mathbf{f}^i_l - \mathbf{f}^j_l)^{\top} \mathbf{R}_l \mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)} \\
&= \sqrt{(\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l))^{\top}\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)}\\
&= \|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2, 
\end{split}
\label{eq:m_distance_decompose}$$ which is essentially a linear transformation of the Euclidean distance by $\mathbf{R}_l$. When $\mathbf{R}_l$ is an identity matrix, $d_{\mathbf{M}_l}(\mathbf{f}^i_l,\mathbf{f}^j_l)$ defaults to the Euclidean distance.

Hence, each edge weight can be computed as $$a_{i,j} = \exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\}.
\label{eq:weight_R}$$ Accordingly, the optimization problem in Eq. converts to $$\min_{\{\mathbf{R}_l\}}
     \sum_l \sum_{\{i,j\}}\exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\} \, s_{i,j},
     \label{eq:opt_graph_R}$$ which allows to remove the PSD constraint of $\mathbf{M}_l$ and is thus more efficient to solve. The optimal adjacency matrix $\mathbf{A}_l^*$ at the $l$-th layer is then computed from the optimized $\mathbf{R}_l$ via Eq. .

Problem Formulation of Node Feature Learning
--------------------------------------------

Assuming the availability of the learned optimal graph encoded in $\mathbf{A}_l^*$ and the optimal graph $\mathbf{A}_{l-1}$ in the previous layer, we learn node features based on a modified graph spectral convolution in GCN [@Kipf2016SemiSupervisedCW] for its simplicity and effectiveness. Given features of all nodes $\mathbf{F}_{l-1}$ from the $(l-1)$-th layer, the graph 