The G-invariant graph Laplacian

• URL: http://arxiv.org/abs/2303.17001v4
• Date: Fri, 28 Jun 2024 13:40:00 GMT
• Title: The G-invariant graph Laplacian
• Authors: Eitan Rosen, Paulina Hoyos, Xiuyuan Cheng, Joe Kileel, Yoel Shkolnisky,
• Abstract summary: We consider data sets whose data points lie on a manifold that is closed under the action of a known unitary Lie group G. We construct the graph Laplacian by incorporating the distances between all the pairs of points generated by the action of G on the data set. We show that the G-GL converges to the Laplace-Beltrami operator on the data manifold, while enjoying a significantly improved convergence rate.
• Score: 12.676094208872842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Laplacian based algorithms for data lying on a manifold have been proven effective for tasks such as dimensionality reduction, clustering, and denoising. In this work, we consider data sets whose data points lie on a manifold that is closed under the action of a known unitary matrix Lie group G. We propose to construct the graph Laplacian by incorporating the distances between all the pairs of points generated by the action of G on the data set. We deem the latter construction the ``G-invariant Graph Laplacian'' (G-GL). We show that the G-GL converges to the Laplace-Beltrami operator on the data manifold, while enjoying a significantly improved convergence rate compared to the standard graph Laplacian which only utilizes the distances between the points in the given data set. Furthermore, we show that the G-GL admits a set of eigenfunctions that have the form of certain products between the group elements and eigenvectors of certain matrices, which can be estimated from the data efficiently using FFT-type algorithms. We demonstrate our construction and its advantages on the problem of filtering data on a noisy manifold closed under the action of the special unitary group SU(2).

Related papers

• ShapeSplat: A Large-scale Dataset of Gaussian Splats and Their Self-Supervised Pretraining [104.34751911174196]
  We build a large-scale dataset of 3DGS using ShapeNet and ModelNet datasets. Our dataset ShapeSplat consists of 65K objects from 87 unique categories. We introduce textbftextitGaussian-MAE, which highlights the unique benefits of representation learning from Gaussian parameters.
  arXiv  Detail & Related papers  (2024-08-20T14:49:14Z)
• Graph Adversarial Diffusion Convolution [49.974206213411904]
  This paper introduces a min-max optimization formulation for the Graph Signal Denoising (GSD) problem. We derive a new variant of the Graph Diffusion Convolution architecture, called Graph Adversarial Diffusion Convolution (GADC)
  arXiv  Detail & Related papers  (2024-06-04T07:43:04Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  We study the problem of learning Cartesian product graphs under Laplacian constraints. We establish statistical consistency for the penalized maximum likelihood estimation. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values.
  arXiv  Detail & Related papers  (2024-02-12T22:48:30Z)
• G-invariant diffusion maps [11.852406625172216]
  We derive diffusion maps that intrinsically account for the group action on the data. In particular, we construct both equivariant and invariant embeddings, which can be used to cluster and align the data points.
  arXiv  Detail & Related papers  (2023-06-12T18:16:33Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Diffusion Maps for Group-Invariant Manifolds [1.90365714903665]
  We consider the manifold learning problem when the data set is invariant under the action of a compact Lie group $K$. Our approach consists in augmenting the data-induced graph Laplacian by integrating over the $K$-orbits of the existing data points. We show that the normalized Laplacian operator $L_N$ converges to the Laplace-Beltrami operator of the data manifold with an improved convergence rate.
  arXiv  Detail & Related papers  (2023-03-28T17:30:35Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) have proven to be successful tools for semi-supervised classification on graph-based datasets. We propose a new GCN variant whose three-part filter space is targeted at dense graphs.
  arXiv  Detail & Related papers  (2020-08-03T08:48:41Z)
• 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.