Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment

Given a convex and differentiable objective Q(M) for a real symmetric matrix M 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 M resides in a space cS of generalized graph Laplacian matrices corresponding to balanced signed graphs. M ∈ cS that is also PD is called a graph metric matrix. Unlike low-rank metric matrices common in the literature, cS 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 M ∈ cS and diagonal matrix S, where Sii = 1/vi and v is M's first eigenvector, we prove that Gershgorin disc left-ends of similarity transform B = S M S-1 are perfectly aligned at the smallest eigenvalue λmin. 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 M can be solved efficiently as linear programs via the Frank-Wolfe method. We update v using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as entries in M are optimized successively. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes, and produces competitive binary classification performance.