Graph Metric Learning via Gershgorin Disc Alignment

Cheng Yang, Gene Cheung, Wei Hu

Introduction

Metric learning is a fundamental task in machine learning, particularly for distance-based algorithms like k-Nearest Neighbors (k-NN). It involves learning a Mahalanobis distance metric defined by a matrix $M$. For this metric to be valid, $M$ must be a Positive Definite (PD) matrix, ensuring all its eigenvalues are strictly positive.

The Computational Bottleneck

Traditional metric learning algorithms enforce the PD constraint by projecting the matrix onto the PD cone after each gradient step. This projection requires a full eigen-decomposition, which has a computational complexity of $O(K^3)$, where $K$ is the number of features. For high-dimensional data, this becomes a significant bottleneck. While low-rank or sparsity assumptions are often used to mitigate this, they can lead to suboptimal performance if the underlying data does not fit these priors. The authors demonstrate that forcing a low-rank assumption actually worsens the objective function if the dataset's features aren't redundant.

Proposed Method: Signed Graph Metric Learning (SGML)

The authors introduce Signed Graph Metric Learning (SGML), a projection-free framework that replaces the expensive PD cone constraint with tight linear constraints. The method assumes $M$ resides in a space of generalized graph Laplacian matrices corresponding to balanced signed graphs, allowing the model to capture both positive correlations and negative anti-correlations between features.

Gershgorin Disc Perfect Alignment (GDPA)

The core theoretical contribution of SGML is the Gershgorin Disc Perfect Alignment (GDPA) theorem. While the classical Gershgorin Circle Theorem provides bounds on eigenvalues, these bounds are typically too loose for practical optimization. The authors prove that a specific similarity transform, using the matrix's first eigenvector, can perfectly align the lower bounds of these discs with the matrix's smallest eigenvalue.

Gershgorin Disc Perfect Alignment (GDPA) shifts the discs to align their lower bounds with the smallest eigenvalue $\lambda_{min}$ via a similarity transform.

Optimization Framework

By linearizing the PD constraint through GDPA, the problem can be solved using the Frank-Wolfe algorithm. This approach treats the optimization as a sequence of efficient Linear Programs (LPs). To maintain speed, the algorithm uses the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method with a "warm start" to update the required eigenvector without a full decomposition.

The SGML optimization workflow integrates Block Coordinate Descent (BCD), Frank-Wolfe (FW), and LOBPCG for efficient computation.

Experimental Results

The SGML framework was evaluated on 17 binary classification datasets from the UCI and LibSVM repositories. Key findings include:

  • Massive Speedups: SGML is drastically faster than standard PD-cone projection methods on high-dimensional data. It was 8.28x faster on the Madelon dataset (500 features) and 3.10x faster on Colon-cancer (2000 features).
  • Competitive Performance: Despite avoiding exact PD-cone projection, SGML achieved highly competitive objective values and matched or beat the classification accuracy of computationally heavy methods in 10-fold cross-validation.

Conclusion and Future Work

SGML offers a scalable alternative to traditional metric learning by leveraging graph signal processing theory to simplify complex optimization constraints. While the search space of balanced signed graphs is locally convex (guaranteeing convergence to a local minimum), the core GDPA theory is highly generalizable and could potentially speed up other optimization problems involving Positive Definite cone constraints, such as general Semi-Definite Programming (SDP).

Summary updated

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},
}

Loading related content...

Figure