arXiv research

Dual regularized graph Laplacian improves spectral clustering for community detection.

Root Laplacian Eigenmaps help in spectral embedding of graphs.

Paper optimizes Laplacian regularization for sparse network clustering.

Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.

This paper explains spectral clustering and its equivalence to PCA, breaking it into fully connected and multi-connected cases.

Enhances clustering performance with a novel high-order Laplacian matrix.

Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a $d$-dimensional compact submanifold $M$ in $\mathbb{R}^D$, we establish the spectral convergence rate…

Survey of Laplacian-based methods for data dimensionality reduction and embedding.

Paper provides a performance guarantee for spectral clustering.

New method clusters evolving networks using spatio-temporal graph Laplacian.

The paper corrects for node degree in spectral clustering using random walk Laplacian.

The cost of computing the spectrum of Laplacian matrices hinders the application of spectral clustering to large data sets. While approximations recover computational tractability, they can potentially affect clustering performance. This paper proposes a practical approach to learn spectral clustering based on adaptive…

The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used for spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, $K$) is generally unknown a-priori. Consequently, the majority of …

Improved spectral clustering for community detection in networks.

Unified spectral clustering for sparse networks with heterogeneous degrees.

A tutorial on dynamic Laplacian for time-evolving data clusters.

This paper approximates $p$-resistance for multi-class graph clustering.

Spectral clustering is robust to helpful model changes but not to random changes.

A new method for community detection in networks is presented.

Graph Laplacians computed from weighted adjacency matrices are widely used to identify geometric structure in data, and clusters in particular; their spectral properties play a central role in a number of unsupervised and semi-supervised learning algorithms. When suitably scaled, graph Laplacians approach limiting cont…

This paper speeds up spectral clustering for large graphs by dilating their eigenspectrum.

New outlier detection method using graph Laplacian spectrum boosts performance.

The eigendeomposition of nearest-neighbor (NN) graph Laplacian matrices is the main computational bottleneck in spectral clustering. In this work, we introduce a highly-scalable, spectrum-preserving graph sparsification algorithm that enables to build ultra-sparse NN (u-NN) graphs with guaranteed preservation of the or…

New algorithm for multiway spectral clustering on Grassmann manifolds.

The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used in spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, $K$) is generally unknown a-priori. Consequently, the majority of t…

Graph-Laplacians and their spectral embeddings play an important role in multiple areas of machine learning. This paper is focused on graph-Laplacian dimension reduction for the spectral clustering of data as a primary application. Spectral embedding provides a low-dimensional parametrization of the data manifold which…

Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering - clustering the vertices of a graph based on their spectral embedding - is commonly approached via K-means (or, more generally, Gaussian mixture model) clustering composed with either…

Novel GNN for signed and directed networks using magnetic signed Laplacian.

Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social networks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several emp…

Study gaps and clusters in eigenvalues of magnetic Laplacian on manifolds.

New method for mixed memberships using symmetrized Laplacian inverse matrix.

Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We pro…

Clustering of data sets is a standard problem in many areas of science and engineering. The method of spectral clustering is based on embedding the data set using a kernel function, and using the top eigenvectors of the normalized Laplacian to recover the connected components. We study the performance of spectral clust…

Study graph-based algorithms for multi-manifold clustering with sufficient conditions.

Spectral clustering is one of the most popular methods for community detection in graphs. A key step in spectral clustering algorithms is the eigen decomposition of the $n{\times}n$ graph Laplacian matrix to extract its $k$ leading eigenvectors, where $k$ is the desired number of clusters among $n$ objects. This is pro…

Spectral clustering is widely used to partition graphs into distinct modules or communities. Existing methods for spectral clustering use the eigenvalues and eigenvectors of the graph Laplacian, an operator that is closely associated with random walks on graphs. We propose a new spectral partitioning method that exploi…

Improved spectral clustering guarantees for dynamic stochastic block models.

For a symplectic manifold with quantizing line bundle, a choice of almost complex structure determines a Laplacian acting on tensor powers of the bundle. For high tensor powers Guillemin-Uribe showed that there is a well-defined cluster of low-lying eigenvalues, whose distribution is described by a spectral density fun…

This paper establishes the consistency of spectral approaches to data clustering. We consider clustering of point clouds obtained as samples of a ground-truth measure. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. We investigate the…

Following Hartigan, a cluster is defined as a connected component of the t-level set of the underlying density, i.e., the set of points for which the density is greater than t. A clustering algorithm which combines a density estimate with spectral clustering techniques is proposed. Our algorithm is composed of two step…

New method circumvents curse of dimensionality in Laplacian estimation.

Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the…

GRASPEL learns large graphs from data efficiently.

New method clusters directed graphs using Koopman operators.

Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the n…

Network Lasso clusters sparse graph clusters efficiently.

We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensi…

The study of higher-order homology embeddings for manifold topology.