Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment
- URL: http://arxiv.org/abs/2208.08726v1
- Date: Thu, 18 Aug 2022 09:19:01 GMT
- Title: Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment
- Authors: Chinthaka Dinesh, Gene Cheung, Saghar Bagheri, Ivan V. Bajic
- Abstract summary: 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.
- Score: 51.74913666829224
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A basic premise in graph signal processing (GSP) is that a graph encoding
pairwise (anti-)correlations of the targeted signal as edge weights is
exploited for graph filtering. However, existing fast graph sampling schemes
are designed and tested only for positive graphs describing positive
correlations. In this paper, we show that for datasets with strong inherent
anti-correlations, a suitable graph contains both positive and negative edge
weights. In response, we propose a linear-time signed graph sampling method
centered on the concept of balanced signed graphs. Specifically, given an
empirical covariance data matrix $\bar{\bf{C}}$, we first learn a sparse
inverse matrix (graph Laplacian) $\mathcal{L}$ corresponding to a signed graph
$\mathcal{G}$. We define the eigenvectors of Laplacian $\mathcal{L}_B$ for a
balanced signed graph $\mathcal{G}_B$ -- approximating $\mathcal{G}$ via edge
weight augmentation -- as graph frequency components. Next, we choose samples
to minimize the low-pass filter reconstruction error in two steps. We first
align all Gershgorin disc left-ends of Laplacian $\mathcal{L}_B$ at smallest
eigenvalue $\lambda_{\min}(\mathcal{L}_B)$ via similarity transform
$\mathcal{L}_p = \S \mathcal{L}_B \S^{-1}$, leveraging a recent linear algebra
theorem called Gershgorin disc perfect alignment (GDPA). We then perform
sampling on $\mathcal{L}_p$ using a previous fast Gershgorin disc alignment
sampling (GDAS) scheme. Experimental results show that our signed graph
sampling method outperformed existing fast sampling schemes noticeably on
various datasets.
Related papers
- 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) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
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.
arXiv Detail & Related papers (2021-12-15T03:45:39Z) - 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) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels.
When restricting labels $x_i$ to binary values, the problem is NP-hard.
We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
arXiv Detail & Related papers (2021-06-03T07:22:48Z) - 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) - Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph.
We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z)
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.