Graph Metric Learning via Gershgorin Disc Alignment

Cheng Yang, Gene Cheung, Wei Hu

TL;DR

This paper introduces a novel metric learning framework that efficiently learns a generalized graph Laplacian matrix as the metric. By reformulating the positive definite constraint using Gershgorin disc alignment and employing Frank-Wolfe iterations, the method achieves projection-free optimization, outperforming existing techniques in classification tasks.

What Problem Does This Paper Address?

Metric learning aims to find an optimal distance metric for data, often represented by a positive definite (PD) matrix $M$. A major hurdle is ensuring $M$ remains PD during optimization, which typically requires computationally expensive projections onto the PD cone. Existing methods often simplify this by restricting $M$ to low-rank or sparse structures, which can limit the quality of the learned metric. This paper addresses the need for a more general and computationally efficient metric learning approach that can handle broader classes of matrices, including positive-diagonal-only metrics, without resorting to costly projections.

Methods

The core innovation lies in a projection-free optimization strategy for learning a metric matrix $M$ within the set $\mathcal{S}$ of generalized graph Laplacian matrices. These matrices are characterized by positive edge weights and node degrees, and importantly, they can represent positive-diagonal-only metrics as a limiting case.

The key steps are:

  1. Gershgorin Disc Alignment: Instead of directly enforcing the PD constraint ($M \succ 0$), the authors leverage the Gershgorin Circle Theorem. They transform the matrix $M$ into $B = SMS^{-1}$, where $S$ is a diagonal matrix of learned scalars. By aligning the left-ends of the Gershgorin discs of $B$ to the smallest eigenvalue, they derive signal-adaptive linear constraints that are sufficient to guarantee $M$ is PD.
  2. Alternating Optimization: The optimization of $M$ is split into two alternating steps: optimizing diagonal terms and optimizing off-diagonal terms.
  3. Frank-Wolfe Iterations: Both optimization steps are framed as linear programs (LPs) and solved efficiently using Frank-Wolfe iterations. This avoids explicit projections.
  4. Eigenvector Computation: The scalars in $S$ are derived from the first eigenvector of the current metric estimate. This eigenvector is efficiently computed using the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) algorithm with warm starts.

Datasets

The paper evaluates its method on four standard classification datasets:

  • Wine (3 classes, 13 features, 178 samples)
  • Iris (3 classes, 4 features, 150 samples)
  • Seeds (3 classes, 7 features, 210 samples)
  • PB (2 classes, 10 features, 300 samples)

The evaluation uses a graph-based classifier with a quadratic formulation, comparing against several existing metric learning methods.

Key Insights and Ideas

  • Gershgorin Discs as PD Enforcers: The paper ingeniously uses the Gershgorin Circle Theorem not just for bounding eigenvalues, but as a mechanism to derive linear constraints that ensure positive definiteness when aligned. This is a clever workaround for the expensive projection step.
  • Signal-Adaptive Constraints: The scalars used in the $S$ matrix are derived from the eigenvector of the current metric estimate. This means the constraints adapt to the learned metric, making the optimization process more dynamic and potentially leading to better solutions.
  • Generalization Beyond Low-Rank: By defining the search space as generalized graph Laplacians, the method naturally encompasses positive-diagonal-only metrics, which are important in some applications but often excluded by low-rank approaches.
  • Projection-Free Optimization: The combination of Gershgorin disc alignment and Frank-Wolfe iterations allows for a projection-free optimization, significantly improving computational efficiency.

Key Results

The proposed metric learning method, when used with a graph-based classifier, achieved the lowest classification error rates across all tested datasets (Wine, Iris, Seeds, PB) compared to several competing metric learning methods. While specific percentage improvements are not detailed in the abstract or introduction, the table in the paper shows consistently lower error rates for the proposed method. For instance, on the Iris dataset, the proposed method achieved a 4.12% error rate with the graph-based classifier, compared to 4.41% for [27] and 4.37% for [10].

Limitations and Future Work

  • Computational Cost of Eigenvector: While LOBPCG with warm start is efficient, computing the eigenvector is still a necessary step in each iteration. The paper notes that this reduces complexity in subsequent iterations, but it's an inherent cost.
  • Sufficiency, Not Necessity: The Gershgorin-based linear constraints are sufficient for positive definiteness, not necessary. This means the search space defined by these constraints is a subset of the true PD cone, which could potentially lead to suboptimal solutions in some theoretical cases, though experiments suggest it performs well in practice.
  • Future Work: The paper doesn't explicitly detail future work, but the framework's generality suggests potential applications in other areas of machine learning that rely on learning distance metrics, such as clustering, retrieval, and anomaly detection. Further exploration of different objective functions $Q(M)$ and their interaction with the proposed framework would also be a natural next step.

Summary updated

Abstract

We propose a general projection-free metric learning framework, where the minimization objective ${\min _{{\mathbf{M}} \in \mathcal{S}}}Q({\mathbf{M}})$ is a convex differentiable function of the metric matrix M, and M resides in the set 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, S includes the important positivediagonal-only matrices as a special case in the limit. The key idea for fast optimization is to rewrite the positive definite cone constraint in S as signal-adaptive linear constraints via Gershgorin disc alignment, so that the alternating optimization of the diagonal and offdiagonal terms in M can be solved efficiently as linear programs via Frank-Wolfe iterations. We prove that left-ends of the Gershgorin discs can be aligned perfectly using the first eigenvector v of 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.
BibTeX
@inproceedings{yang2020graph,
  author = {Cheng Yang and Gene Cheung and Wei Hu},
  title = {{Graph Metric Learning via Gershgorin Disc Alignment}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=4ZOZlt1BRp},
}
Figure