Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
Cheng Yang, Gene Cheung, Wei Hu
Abstract
Given a convex and differentiable objective <inline-formula><tex-math notation="LaTeX">$Q({\mathbf M})$</tex-math></inline-formula> for a real symmetric matrix <inline-formula><tex-math notation="LaTeX">${\mathbf M}$</tex-math></inline-formula> in the positive definite (PD) cone—used to compute Mahalanobis distances—we propose a fast general metric learning framework that is entirely projection-free. We first assume that <inline-formula><tex-math notation="LaTeX">${\mathbf M}$</tex-math></inline-formula> resides in a space <inline-formula><tex-math notation="LaTeX">${\mathcal S}$</tex-math></inline-formula> of generalized graph Laplacian matrices corresponding to balanced signed graphs. <inline-formula><tex-math notation="LaTeX">${\mathbf M}\in {\mathcal S}$</tex-math></inline-formula> that is also PD is called a graph metric matrix. Unlike low-rank metric matrices common in the literature, <inline-formula><tex-math notation="LaTeX">${\mathcal S}$</tex-math></inline-formula> includes the important diagonal-only matrices as a special case. The key theorem to circumvent full eigen-decomposition and enable fast metric matrix optimization is Gershgorin disc perfect alignment (GDPA): given <inline-formula><tex-math notation="LaTeX">${\mathbf M}\in {\mathcal S}$</tex-math></inline-formula> and diagonal matrix <inline-formula><tex-math notation="LaTeX">${\mathbf S}$</tex-math></inline-formula> , where <inline-formula><tex-math notation="LaTeX">$S_{ii} = 1/v_i$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">${\mathbf v}$</tex-math></inline-formula> is the first eigenvector of <inline-formula><tex-math notation="LaTeX">${\mathbf M}$</tex-math></inline-formula> , we prove that Gershgorin disc left-ends of similarity transform <inline-formula><tex-math notation="LaTeX">${\mathbf B}= {\mathbf S}{\mathbf M}{\mathbf S}^{-1}$</tex-math></inline-formula> are perfectly aligned at the smallest eigenvalue <inline-formula><tex-math notation="LaTeX">$\lambda _{\min }$</tex-math></inline-formula> . Using this theorem, we replace the PD cone constraint in the metric learning problem with tightest possible linear constraints per iteration, so that the alternating optimization of the diagonal / off-diagonal terms in <inline-formula><tex-math notation="LaTeX">${\mathbf M}$</tex-math></inline-formula> can be solved efficiently as linear programs via the Frank-Wolfe method. We update <inline-formula><tex-math notation="LaTeX">${\mathbf v}$</tex-math></inline-formula> using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as entries in <inline-formula><tex-math notation="LaTeX">${\mathbf M}$</tex-math></inline-formula> are optimized successively. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes, and produces competitive binary classification performance.