Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding
- URL: http://arxiv.org/abs/2112.07862v1
- Date: Wed, 15 Dec 2021 03:45:39 GMT
- Title: Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding
- Authors: Fei Chen, Gene Cheung, Xue Zhang
- Abstract summary: We leverage existing fast extreme eigenvector computation algorithms for speedy execution.
Our embedding is among the fastest in the literature, while producing the best clustering performance for manifold graphs.
- Score: 38.902986549367434
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Our goal is to efficiently compute low-dimensional latent coordinates for
nodes in an input graph -- known as graph embedding -- for subsequent data
processing such as clustering. Focusing on finite graphs that are interpreted
as uniformly samples on continuous manifolds (called manifold graphs), we
leverage existing fast extreme eigenvector computation algorithms for speedy
execution. We first pose a generalized eigenvalue problem for sparse matrix
pair $(\A,\B)$, where $\A = \L - \mu \Q + \epsilon \I$ is a sum of graph
Laplacian $\L$ and disconnected two-hop difference matrix $\Q$. Eigenvector
$\v$ minimizing Rayleigh quotient $\frac{\v^{\top} \A \v}{\v^{\top} \v}$ thus
minimizes $1$-hop neighbor distances while maximizing distances between
disconnected $2$-hop neighbors, preserving graph structure. Matrix $\B =
\text{diag}(\{\b_i\})$ that defines eigenvector orthogonality is then chosen so
that boundary / interior nodes in the sampling domain have the same generalized
degrees. $K$-dimensional latent vectors for the $N$ graph nodes are the first
$K$ generalized eigenvectors for $(\A,\B)$, computed in $\cO(N)$ using LOBPCG,
where $K \ll N$. Experiments show that our embedding is among the fastest in
the literature, while producing the best clustering performance for manifold
graphs.
Related papers
- 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) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$.
We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
arXiv Detail & Related papers (2021-11-02T05:26:10Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
An $soperatorname-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects $s$ and $t$.
In this work we describe a quantum algorithm for the minimum $soperatorname-t$ cut problem on undirected graphs.
arXiv Detail & Related papers (2021-10-29T07:35:46Z) - 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) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs.
It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
This paper revisits and extends the widely used accelerated gradient tracking.
Our complexities improve significantly on the ones of $cal O(frac1epsilon5/7)$ and $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
arXiv Detail & Related papers (2021-04-06T15:34:14Z) - 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.