arXiv research

Root Laplacian Eigenmaps help in spectral embedding of graphs.

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

ULES embeds dynamic networks with stability guarantees.

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

InfiniteWalk connects deep network embeddings to spectral graph theory with a nonlinear transformation.

HSSE framework embeds single-cell RNA-seq data at multiple scales.

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

We present a novel spectral embedding of graphs that incorporates weights assigned to the nodes, quantifying their relative importance. This spectral embedding is based on the first eigenvectors of some properly normalized version of the Laplacian. We prove that these eigenvectors correspond to the configurations of lo…

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…

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

Graph embeddings, a class of dimensionality reduction techniques designed for relational data, have proven useful in exploring and modeling network structure. Most dimensionality reduction methods allow out-of-sample extensions, by which an embedding can be applied to observations not present in the training set. Appli…

We analyze the spectral clustering procedure for identifying coarse structure in a data set $x_1, \dots, x_n$, and in particular study the geometry of graph Laplacian embeddings which form the basis for spectral clustering algorithms. More precisely, we assume that the data is sampled from a mixture model supported on …

A novel 3D shape registration method using spectral graph embedding and probabilistic matching.

This paper characterizes and explains the disagreement between two graph embedding methods.

New method learns high-quality Laplacian representations for reinforcement learning.

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…

ELD compares graphs by their embedded Laplacian eigenvectors, resolving ambiguities.

The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describ…

Method detects trajectory outliers using Hodge Laplacian embeddings.

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

A fast graph embedding method for large graphs.

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…

We prove a central limit theorem for the components of the eigenvectors corresponding to the $d$ largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized La…

Study eigenvalues of drift Laplacian on symmetric self-shrinkers in R^3.

Graph embedding method captures both local and global network structure.

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…

In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to large-scale graphs. Our contribution consists of reformulating spect…

Stochastic neighbor embedding (SNE) and related nonlinear manifold learning algorithms achieve high-quality low-dimensional representations of similarity data, but are notoriously slow to train. We propose a generic formulation of embedding algorithms that includes SNE and other existing algorithms, and study their rel…

The paper proves spectral convergence rates for graph Laplacian to manifold Laplace-Beltrami operator.

SpecNet2 improves spectral embedding without orthogonalization, achieving better performance and efficiency.

Spectral embedding uses eigenfunctions of the discrete Laplacian on a weighted graph to obtain coordinates for an embedding of an abstract data set into Euclidean space. We propose a new pre-processing step of first using the eigenfunctions to simulate a low-frequency wave moving over the data and using both position a…

Dual regularized graph Laplacian improves spectral clustering for community detection.

Spectro-Riemannian Graph Neural Networks integrate spectral and curvature signals for better graph representation learning.

Study spectral properties of sub-Laplacians in Carnot groups.

The concern of this paper is to clarify a relationship between the curvatures at infinity and the spectral structure of the Laplacian. In particular, this paper discusses the question of whether there is an eigenvalue of the Laplacian embedded in the essential spectrum or not. The borderline-behavior of the radial curv…

Spectral graph sparsification preserves geometry of GNN embeddings.

Spectral embedding of adjacency or Laplacian matrices of undirected graphs is a common technique for representing a network in a lower dimensional latent space, with optimal theoretical guarantees. The embedding can be used to estimate the community structure of the network, with strong consistency results in the stoch…

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…

Researchers calculate spectral invariants from Dirichlet-to-Neumann map for Witten-Laplacian with potential.

Graph spectral analysis can yield meaningful embeddings of graphs by providing insight into distributed features not directly accessible in nodal domain. Recent efforts in graph signal processing have proposed new decompositions-e.g., based on wavelets and Slepians-that can be applied to filter signals defined on the g…

Learning meaningful graphs from data plays important roles in many data mining and machine learning tasks, such as data representation and analysis, dimension reduction, data clustering, and visualization, etc. In this work, for the first time, we present a highly-scalable spectral approach (GRASPEL) for learning large…

Paper introduces magnetic Hodge Laplacian for differential forms.

We consider the Neumann Laplacian acting on square-integrable functions on a triangle in the hyperbolic plane that has one cusp. We show that the generic such triangle has no eigenvalues embedded in its continuous spectrum. To prove this result we study the behavior of the real-analytic eigenvalue branches of a degener…

The aim of the present article is to give an overview of spectral theory on metric graphs guided by spectral geometry on discrete graphs and manifolds. We present the basic concept of metric graphs and natural Laplacians acting on it and explicitly allow infinite graphs. Motivated by the general form of a Laplacian on …

This paper improves spectral clustering for large datasets using the Nystrom method.

Theoretical analysis of t-SNE for visualizing clustered data.

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…

Study spectral settings of generalized Laplacians on homogeneous spaces.