Graph Metric Learning via Gershgorin Disc Alignment

Abstract

We propose a fast general projection-free metric learning framework, where the minimization objective ${\min }_{\text{M}\in \mathcal{S}}Q(\text{M})$ is a convex differentiable function of the metric matrix $\text{M}$, and $\text{M}$ resides in the set $\mathcal{S}$ of generalized graph Laplacian matrices for connected graphs with positive edge weights and node degrees. Unlike low-rank metric matrices common in the literature, $\mathcal{S}$ includes the important positive-diagonal-only matrices as a special case in the limit. The key idea for fast optimization is to rewrite the positive definite cone constraint in $\mathcal{S}$ as signal-adaptive linear constraints via Gershgorin disc alignment, so that the alternating optimization of the diagonal and off-diagonal terms in $\text{M}$ can be solved efficiently as linear programs via Frank-Wolfe iterations. We prove that the Gershgorin discs can be aligned perfectly using the first eigenvector $\text{v}$ of $\text{M}$, which we update iteratively using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as diagonal / off-diagonal terms are optimized. Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.

accepted to ICASSP 2020

References in corpus (4)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain
• Feature Graph Learning for 3D Point Cloud Denoising
• Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment