Power Spectrum Signatures of Graphs

• URL: http://arxiv.org/abs/2503.09660v2
• Date: Fri, 14 Mar 2025 17:09:50 GMT
• Title: Power Spectrum Signatures of Graphs
• Authors: Karamatou Yacoubou Djima, Ka Man Yim,
• Abstract summary: We propose a novel point signature, the power spectrum signature, a measure on $mathbbR$ defined as the squared graph Fourier transform of a graph signal.<n>We show that the power spectrum signature is stable under perturbations of the input graph with respect to the Wasserstein metric.<n>To demonstrate the practical value of our signature, we showcase several applications in characterizing geometry and symmetries in point cloud data, and graph regression problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Point signatures based on the Laplacian operators on graphs, point clouds, and manifolds have become popular tools in machine learning for graphs, clustering, and shape analysis. In this work, we propose a novel point signature, the power spectrum signature, a measure on $\mathbb{R}$ defined as the squared graph Fourier transform of a graph signal. Unlike eigenvectors of the Laplacian from which it is derived, the power spectrum signature is invariant under graph automorphisms. We show that the power spectrum signature is stable under perturbations of the input graph with respect to the Wasserstein metric. We focus on the signature applied to classes of indicator functions, and its applications to generating descriptive features for vertices of graphs. To demonstrate the practical value of our signature, we showcase several applications in characterizing geometry and symmetries in point cloud data, and graph regression problems.

Related papers

• Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
  We define a novel Graph-Dictionary signal model, where a finite set of graphs characterizes relationships in data distribution through a weighted sum of their Laplacians. We propose a framework to infer the graph dictionary representation from observed data, along with a bilinear generalization of the primal-dual splitting algorithm to solve the learning problem. We exploit graph-dictionary representations in a motor imagery decoding task on brain activity data, where we classify imagined motion better than standard methods.
  arXiv  Detail & Related papers  (2024-11-08T17:40:43Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification [0.6999740786886536]
  Persistent Weisfeiler-Lehman Random walk scheme (abbreviated as PWLR) for graph representations. We generalize many variants of Weisfeiler-Lehman procedures, which are primarily used to embed graphs with discrete node labels.
  arXiv  Detail & Related papers  (2022-08-29T08:50:37Z)
• Signed Graph Neural Networks: A Frequency Perspective [14.386571627652975]
  Graph convolutional networks (GCNs) are designed for unsigned graphs containing only positive links. We propose two different signed graph neural networks, one keeps only low-frequency information and one also retains high-frequency information.
  arXiv  Detail & Related papers  (2022-08-15T16:42:18Z)
• Embedding Graphs on Grassmann Manifold [31.42901131602713]
  This paper develops a new graph representation learning scheme, namely EGG, which embeds approximated second-order graph characteristics into a Grassmann manifold. The effectiveness of EGG is demonstrated using both clustering and classification tasks at the node level and graph level.
  arXiv  Detail & Related papers  (2022-05-30T12:56:24Z)
• Stratified Graph Spectra [0.0]
  This paper seeks a generalized transformation decoding the magnitudes of eigencomponents from vector-valued signals. Several attempts are explored, and it is found that performing the transformation at hierarchical levels of adjacency help profile the spectral characteristics of signals more insightfully.
  arXiv  Detail & Related papers  (2022-01-10T23:35:13Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)
• 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.