Multiway $p$-spectral graph cuts on Grassmann manifolds
- URL: http://arxiv.org/abs/2008.13210v2
- Date: Fri, 26 Nov 2021 13:44:03 GMT
- Title: Multiway $p$-spectral graph cuts on Grassmann manifolds
- Authors: Dimosthenis Pasadakis, Christie Louis Alappat, Olaf Schenk, Gerhard
Wellein
- Abstract summary: We present a novel direct multiway spectral clustering algorithm in the $p$-norm, for $p in (1, 2]$.
The problem of computing multiple eigenvectors of the graph $p$-Laplacian is recasted as an unconstrained minimization problem on a Grassmann manifold.
Monitoring the monotonic decrease of the balanced graph cuts guarantees that we obtain the best available solution from the $p$-levels considered.
- Score: 0.3441021278275805
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nonlinear reformulations of the spectral clustering method have gained a lot
of recent attention due to their increased numerical benefits and their solid
mathematical background. We present a novel direct multiway spectral clustering
algorithm in the $p$-norm, for $p \in (1, 2]$. The problem of computing
multiple eigenvectors of the graph $p$-Laplacian, a nonlinear generalization of
the standard graph Laplacian, is recasted as an unconstrained minimization
problem on a Grassmann manifold. The value of $p$ is reduced in a
pseudocontinuous manner, promoting sparser solution vectors that correspond to
optimal graph cuts as $p$ approaches one. Monitoring the monotonic decrease of
the balanced graph cuts guarantees that we obtain the best available solution
from the $p$-levels considered. We demonstrate the effectiveness and accuracy
of our algorithm in various artificial test-cases. Our numerical examples and
comparative results with various state-of-the-art clustering methods indicate
that the proposed method obtains high quality clusters both in terms of
balanced graph cut metrics and in terms of the accuracy of the labelling
assignment. Furthermore, we conduct studies for the classification of facial
images and handwritten characters to demonstrate the applicability in
real-world datasets.
Related papers
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs.
Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
arXiv Detail & Related papers (2024-03-21T11:57:16Z) - Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs.
We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon.
To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
arXiv Detail & Related papers (2024-03-15T14:26:53Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints.
The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution.
We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
arXiv Detail & Related papers (2022-10-21T13:19:45Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification.
We show that the resulting model lead to new graphs and residual scaling parameter.
We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
arXiv Detail & Related papers (2022-09-12T04:46:55Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
This paper presents a convex-analytic framework to learn from data.
We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
arXiv Detail & Related papers (2021-09-17T17:46:12Z) - $\ell_2$-norm Flow Diffusion in Near-Linear Time [18.263667346853698]
We provide an $widetildeO(m)$-time randomized algorithm for the $ell$-norm flow diffusion problem.
It is done simply by sweeping over the dual solution vector.
It adapts the high-level algorithmic framework of Laplacian system solvers, but requires several new tools.
arXiv Detail & Related papers (2021-05-30T21:27:58Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
multilayer graph clustering aims at dividing the graph nodes into categories or communities.
We propose a clustering-friendly embedding of the layers of a given multilayer graph.
Experiments show that our method leads to a significant improvement.
arXiv Detail & Related papers (2021-03-30T17:36:40Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z) - Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained
Graphical Models? [13.572602792770288]
We consider the problem of learning a graph under the Laplacian constrained Gaussian graphical models.
We show that a large regularization parameter will surprisingly lead to a complete graph, i.e., every edge connected by an edge.
arXiv Detail & Related papers (2020-06-26T12:06:10Z)
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.