HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings
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.
Code (1)
Similar Papers 제목 키워드 기반
HyperBench: Standardizing and Scaling Synthetic Evaluation for Hyperspectral Super-Resolution
Hyperspectral super-resolution (HSR) reconstructs a high-spatial-resolution hyperspectral image by fusing a low-resolution hyperspectral image (LR-HSI) with a high-resolution multispectral image (HR-MSI). In the absence …
Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
Hypergraphs naturally arise when studying group relations and have been widely used in the field of machine learning. There has not been a unified formulation of hypergraphs, yet the recently proposed edge-dependent vert…
ClusteringUniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, wh…
Clusteringhypergraph partitioningStochastic Block ModelThe Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
Hypergraphs allow one to encode higher-order relationships in data and are thus a very flexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor method…
On Metzler positive systems on hypergraphs
In graph-theoretical terms, an edge in a graph connects two vertices while a hyperedge of a hypergraph connects any more than one vertices. If the hypergraph's hyperedges further connect the same number of vertices, it i…