Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis

• URL: http://arxiv.org/abs/2103.04150v1
• Date: Sat, 6 Mar 2021 16:32:32 GMT
• Title: Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis
• Authors: Ellen Chen, Jennifer DeJong, Tom Halverson, David I Shuman
• Abstract summary: ranked data sets are increasingly prevalent in contexts such as political elections, computer vision, recommender systems, and bioinformatics. We develop specialized algorithms and open software that take advantage of the symmetry and structure of the permutahedron to improve the scalability of the proposed method.
• Score: 1.8352113484137624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ranked data sets, where m judges/voters specify a preference ranking of n objects/candidates, are increasingly prevalent in contexts such as political elections, computer vision, recommender systems, and bioinformatics. The vote counts for each ranking can be viewed as an n! data vector lying on the permutahedron, which is a Cayley graph of the symmetric group with vertices labeled by permutations and an edge when two permutations differ by an adjacent transposition. Leveraging combinatorial representation theory and recent progress in signal processing on graphs, we investigate a novel, scalable transform method to interpret and exploit structure in ranked data. We represent data on the permutahedron using an overcomplete dictionary of atoms, each of which captures both smoothness information about the data (typically the focus of spectral graph decomposition methods in graph signal processing) and structural information about the data (typically the focus of symmetry decomposition methods from representation theory). These atoms have a more naturally interpretable structure than any known basis for signals on the permutahedron, and they form a Parseval frame, ensuring beneficial numerical properties such as energy preservation. We develop specialized algorithms and open software that take advantage of the symmetry and structure of the permutahedron to improve the scalability of the proposed method, making it more applicable to the high-dimensional ranked data found in applications.

Related papers

• Differentiable Mapper For Topological Optimization Of Data Representation [33.33724208084121]
  We build on a recently proposed framework incorporating topology to provide the first filter optimization scheme for Mapper graphs. We demonstrate the usefulness of our approach by optimizing Mapper graph representations on several datasets.
  arXiv  Detail & Related papers  (2024-02-20T09:33:22Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• 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)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  Current Graph Neural Networks (GNN) architectures rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance.
  arXiv  Detail & Related papers  (2022-05-31T12:24:01Z)
• Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach [0.0]
  We study a class of frames, called Frobenius-Schur frames, where every atom belongs to the coefficient space of only one irreducible representation of the symmetric group. We provide a characterization for all Frobenius-Schur frames on the group algebra of the symmetric group which are "compatible" with respect to the generating set. Our results generalize frame constructions for the permutahedron to any inverse-closed generating set.
  arXiv  Detail & Related papers  (2022-03-06T19:41:36Z)
• SHGNN: Structure-Aware Heterogeneous Graph Neural Network [77.78459918119536]
  This paper proposes a novel Structure-Aware Heterogeneous Graph Neural Network (SHGNN) to address the above limitations. We first utilize a feature propagation module to capture the local structure information of intermediate nodes in the meta-path. Next, we use a tree-attention aggregator to incorporate the graph structure information into the aggregation module on the meta-path. Finally, we leverage a meta-path aggregator to fuse the information aggregated from different meta-paths.
  arXiv  Detail & Related papers  (2021-12-12T14:18:18Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Optimal radial basis for density-based atomic representations [58.720142291102135]
  We discuss how to build an adaptive, optimal numerical basis that is chosen to represent most efficiently the structural diversity of the dataset at hand. For each training dataset, this optimal basis is unique, and can be computed at no additional cost with respect to the primitive basis. We demonstrate that this construction yields representations that are accurate and computationally efficient.
  arXiv  Detail & Related papers  (2021-05-18T17:57:08Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  We propose a powerful and equivariant message-passing framework based on two ideas. First, we propagate a one-hot encoding of the nodes, in addition to the features, in order to learn a local context matrix around each node. Second, we propose methods for the parametrization of the message and update functions that ensure permutation equivariance.
  arXiv  Detail & Related papers  (2020-06-26T17:15:16Z)
• Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut) [1.52292571922932]
  Representing data residing on a graph as a linear combination of building block signals can enable efficient and insightful visual or statistical analysis of the data. We survey a particular class of dictionaries called localized spectral graph filter frames. We emphasize computationally efficient methods that ensure the resulting transforms and their inverses can be applied to data residing on large, sparse graphs.
  arXiv  Detail & Related papers  (2020-06-19T16:49:33Z)

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.