Graph Metric Learning via Gershgorin Disc Alignment

• URL: http://arxiv.org/abs/2001.10485v4
• Date: Mon, 9 Mar 2020 22:42:43 GMT
• Title: Graph Metric Learning via Gershgorin Disc Alignment
• Authors: Cheng Yang, Gene Cheung, Wei Hu
• Abstract summary: We propose a fast general projection-free metric learning framework, where the objective $min_textbfM in mathcalS$ is a convex differentiable function of the metric matrix $textbfM$. We prove that the Gershgorin discs can be aligned perfectly using the first eigenvector $textbfv$ of $textbfM$. Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.
• Score: 46.145969174332485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a fast general projection-free metric learning framework, where the minimization objective $\min_{\textbf{M} \in \mathcal{S}} Q(\textbf{M})$ is a convex differentiable function of the metric matrix $\textbf{M}$, and $\textbf{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 $\textbf{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 $\textbf{v}$ of $\textbf{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.

Related papers

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Optimal Matrix Sketching over Sliding Windows [38.09464189820894]
  Matrix sketching, aimed at approximating a matrix $boldsymbolA in mathbbRNtimes d$ consists of vector streams of length $N$ with a smaller sketching matrix $boldsymbolB in mathbbRelltimes d, ell ll N$. We introduce the DS-FD algorithm, which achieves the optimal $Oleftfracdvarepsilonright)$ space bound for matrix sketching over row-normalized, sequence-based sliding windows
  arXiv  Detail & Related papers  (2024-05-13T14:38:35Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  Current methods either invert a graph kernel runtime matrix with $mathcalO(n3)$ or $mathcalO(n2)$ space complexity or sample a large volume of random spanning trees. We propose an improvement based on the textitonline relaxation technique introduced by a series of works.
  arXiv  Detail & Related papers  (2023-05-25T17:13:08Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  We consider a structural assumption on the graph Laplacian matrix $L$. The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria. We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
  arXiv  Detail & Related papers  (2020-10-25T18:12:50Z)
• Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
  We propose a fast general metric learning framework that is entirely projection-free. We replace the PD cone constraint in the metric learning problem with possible linear constraints per distances. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes.
  arXiv  Detail & Related papers  (2020-06-15T23:15:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.