HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings

• URL: http://arxiv.org/abs/2009.01769v1
• Date: Wed, 2 Sep 2020 13:08:55 GMT
• Title: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings
• Authors: Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, Reinhard Pichler
• Abstract summary: 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.
• Score: 8.37315177713779
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To cope with the intractability of answering Conjunctive Queries (CQs) and solving Constraint Satisfaction Problems (CSPs), several notions of hypergraph decompositions have been proposed -- giving rise to different notions of width, noticeably, plain, generalized, and fractional hypertree width (hw, ghw, and fhw). Given the increasing interest in using such decomposition methods in practice, a publicly accessible repository of decomposition software, as well as a large set of benchmarks, and a web-accessible workbench for inserting, analyzing, and retrieving hypergraphs are called for. We address this need by providing (i) concrete implementations of hypergraph decompositions (including new practical algorithms), (ii) a new, comprehensive benchmark of hypergraphs stemming from disparate CQ and CSP collections, and (iii) HyperBench, our new web-inter\-face for accessing the benchmark and the results of our analyses. In addition, we describe a number of actual experiments we carried out with this new infrastructure.

Related papers

• QuOTE: Question-Oriented Text Embeddings [8.377715521597292]
  QuOTE (Question-Oriented Text Embeddings) is a novel enhancement to retrieval-augmented generation (RAG) systems. Unlike traditional RAG pipelines, QuOTE augments chunks with hypothetical questions that the chunk can potentially answer. We demonstrate that QuOTE significantly enhances retrieval accuracy, including in multi-hop question-answering tasks.
  arXiv  Detail & Related papers  (2025-02-16T03:37:13Z)
• Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
  We propose a novel hypergraph learning framework, HyperGraph Transformer (HyperGT) HyperGT uses a Transformer-based neural network architecture to effectively consider global correlations among all nodes and hyperedges. It achieves comprehensive hypergraph representation learning by effectively incorporating global interactions while preserving local connectivity patterns.
  arXiv  Detail & Related papers  (2023-12-18T17:50:52Z)
• Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Design [7.410655263764799]
  We introduce a novel conceptualization of homophily in higher-order networks based on a Message Passing scheme. We investigate some natural, yet mostly unexplored, strategies for processing higher-order structures within HNNs.
  arXiv  Detail & Related papers  (2023-10-11T17:35:20Z)
• 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)
• Learning Situation Hyper-Graphs for Video Question Answering [95.18071873415556]
  We propose an architecture for Video Question Answering (VQA) that enables answering questions related to video content by predicting situation hyper-graphs. We train a situation hyper-graph decoder to implicitly identify graph representations with actions and object/human-object relationships from the input video clip. Our results show that learning the underlying situation hyper-graphs helps the system to significantly improve its performance for novel challenges of video question-answering tasks.
  arXiv  Detail & Related papers  (2023-04-18T01:23:11Z)
• 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)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  We propose an efficient spectral hypergraph coarsening scheme (HyperSF) for preserving the original spectral (structural) properties of hypergraphs. Our results show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering.
  arXiv  Detail & Related papers  (2021-08-17T22:20:23Z)
• 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)
• The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions [12.888272723854833]
  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.
  arXiv  Detail & Related papers  (2020-12-29T14:21:54Z)
• Lookahead-Bounded Q-Learning [8.738692817482526]
  We introduce the lookahead-bounded Q-learning (LBQL) algorithm, a new, provably convergent variant of Q-learning. Our approach is particularly appealing in problems that require expensive simulations or real-world interactions.
  arXiv  Detail & Related papers  (2020-06-28T19:50:55Z)
• Taming the Expressiveness and Programmability of Graph Analytical Queries [74.65487393973993]
  Graph database has enjoyed a boom in the last decade, and graph queries gain a lot of attentions. We focus on analytical queries in this paper. Motivated by this, we propose the flash DSL, which is named after the three primitive operators Filter, LocAl and PuSH.
  arXiv  Detail & Related papers  (2020-04-20T04:08:28Z)

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.