The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions

• URL: http://arxiv.org/abs/2012.14762v1
• Date: Tue, 29 Dec 2020 14:21:54 GMT
• Title: The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions
• Authors: Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus and Reinhard Pichler
• Abstract summary: Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. Various forms of hypergraph decompositions have been proposed in the literature to identify tractable fragments of CSPs.
• Score: 12.888272723854833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. In general, solving CSPs is NP-complete. The structure of CSPs is best described by hypergraphs. Therefore, various forms of hypergraph decompositions have been proposed in the literature to identify tractable fragments of CSPs. However, also the computation of a concrete hypergraph decomposition is a challenging task in itself. In this paper, we report on recent progress in the study of hypergraph decompositions and we outline several directions for future research.

Related papers

• Convolutional Signal Propagation: A Simple Scalable Algorithm for Hypergraphs [0.13654846342364302]
  This paper proposes Convolutional Signal Propagation (CSP), a non-parametric simple and scalable method that operates on bipartite graphs (hypergraphs) We show that CSP offers competitive performance while maintaining low computational complexity. Despite operating on hypergraphs, CSP achieves good results in tasks typically not associated with hypergraphs, such as natural language processing.
  arXiv  Detail & Related papers  (2024-09-26T08:22:09Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Supervised Hypergraph Reconstruction [3.69853388955692]
  Many real-world systems involving high-order interactions are best encoded by hypergraphs. Their datasets often end up being published or studied only in the form of their projections. We propose supervised hypergraph reconstruction. Our approach outperforms all baselines by an order of magnitude in accuracy on hard datasets.
  arXiv  Detail & Related papers  (2022-11-23T23:15:03Z)
• Learn-to-Decompose: Cascaded Decomposition Network for Cross-Domain Few-Shot Facial Expression Recognition [60.51225419301642]
  We propose a novel cascaded decomposition network (CDNet) for compound facial expression recognition. By training across similar tasks on basic expression datasets, CDNet learns the ability of learn-to-decompose that can be easily adapted to identify unseen compound expressions.
  arXiv  Detail & Related papers  (2022-07-16T16:10:28Z)
• Tensor Decompositions for Hyperspectral Data Processing in Remote Sensing: A Comprehensive Review [85.36368666877412]
  hyperspectral (HS) remote sensing (RS) imaging has provided a significant amount of spatial and spectral information for the observation and analysis of the Earth's surface. The recent advancement and even revolution of the HS RS technique offer opportunities to realize the full potential of various applications. Due to the maintenance of the 3-D HS inherent structure, tensor decomposition has aroused widespread concern and research in HS data processing tasks.
  arXiv  Detail & Related papers  (2022-05-13T00:39:23Z)
• Finding Bipartite Components in Hypergraphs [9.759415650727892]
  We study a new heat diffusion process in hypergraphs and employ this process to design a new algorithm that finds approximately bipartite components in a hypergraph. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.
  arXiv  Detail & Related papers  (2022-05-05T16:46:31Z)
• Preventing Over-Smoothing for Hypergraph Neural Networks [0.0]
  We show that the performance of hypergraph neural networks does not improve as the number of layers increases. We develop a new deep hypergraph convolutional network called Deep-HGCN, which can maintain node representation in deep layers.
  arXiv  Detail & Related papers  (2022-03-31T16:33:31Z)
• Learning Multi-Granular Hypergraphs for Video-Based Person Re-Identification [110.52328716130022]
  Video-based person re-identification (re-ID) is an important research topic in computer vision. We propose a novel graph-based framework, namely Multi-Granular Hypergraph (MGH) to better representational capabilities. 90.0% top-1 accuracy on MARS is achieved using MGH, outperforming the state-of-the-arts schemes.
  arXiv  Detail & Related papers  (2021-04-30T11:20:02Z)
• An Efficient Hypergraph Approach to Robust Point Cloud Resampling [57.49817398852218]
  This work investigates point cloud resampling based on hypergraph signal processing (HGSP) We design hypergraph spectral filters to capture multi-lateral interactions among the signal nodes of point clouds. Our test results validate the high efficacy of hypergraph characterization of point clouds.
  arXiv  Detail & Related papers  (2021-03-11T23:19:54Z)
• HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings [8.37315177713779]
  We develop a repository of decomposition software and a workbench for inserting, analyzing, and retrieving hypergraphs. We also develop a new benchmark of hypergraphs stemming from disparate CQ and CSP collections. We describe a number of actual experiments we carried out with this new infrastructure.
  arXiv  Detail & Related papers  (2020-09-02T13:08:55Z)
• Boundary-assisted Region Proposal Networks for Nucleus Segmentation [89.69059532088129]
  Machine learning models cannot perform well because of large amount of crowded nuclei. We devise a Boundary-assisted Region Proposal Network (BRP-Net) that achieves robust instance-level nucleus segmentation.
  arXiv  Detail & Related papers  (2020-06-04T08:26:38Z)

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.