Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment.

Area of Science:

• Machine Learning
• Graph Theory
• Linear Algebra

Background:

• Metric learning aims to learn a distance metric from data.
• Positive definite (PD) matrices are crucial for Mahalanobis distances.
• Existing methods often rely on computationally expensive cone projections.

Purpose of the Study:

• To develop a fast, projection-free metric learning framework for graph Laplacian matrices.
• To leverage the Gershgorin disc perfect alignment (GDPA) theorem for efficient optimization.
• To enable optimization of graph metric matrices beyond low-rank assumptions.

Main Methods:

• Developed a novel metric learning framework operating on generalized graph Laplacian matrices.
• Utilized the Gershgorin disc perfect alignment (GDPA) theorem to replace cone constraints with linear constraints.
• Employed the Frank-Wolfe method for efficient alternating optimization of matrix elements.
• Incorporated Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) for eigenvector updates.

Main Results:

• The proposed method significantly outperforms traditional cone-projection schemes in speed.
• Achieved competitive binary classification performance compared to existing metric learning approaches.
• Demonstrated the effectiveness of GDPA in enabling projection-free optimization.
• The framework efficiently handles diagonal-only matrices as a special case.

Conclusions:

• The projection-free framework offers a substantial speedup for graph metric learning.
• GDPA is a key theoretical advancement for efficient matrix optimization.
• The method provides a viable and efficient alternative for learning graph metrics.