Sharp detection boundaries on testing dense subhypergraph

• URL: http://arxiv.org/abs/2101.04584v1
• Date: Tue, 12 Jan 2021 16:31:47 GMT
• Title: Sharp detection boundaries on testing dense subhypergraph
• Authors: Mingao Yuan and Zuofeng Shang
• Abstract summary: We study the problem of testing the existence of a dense subhypergraph. The null hypothesis is an Erdos-Renyi uniform random hypergraph. The alternative hypothesis is a uniform random hypergraph that contains a dense subhypergraph.
• Score: 6.903929927172917
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of testing the existence of a dense subhypergraph. The null hypothesis is an Erdos-Renyi uniform random hypergraph and the alternative hypothesis is a uniform random hypergraph that contains a dense subhypergraph. We establish sharp detection boundaries in both scenarios: (1) the edge probabilities are known; (2) the edge probabilities are unknown. In both scenarios, sharp detectable boundaries are characterized by the appropriate model parameters. Asymptotically powerful tests are provided when the model parameters fall in the detectable regions. Our results indicate that the detectable regions for general hypergraph models are dramatically different from their graph counterparts.

Related papers

• Generative Edge Detection with Stable Diffusion [52.870631376660924]
  Edge detection is typically viewed as a pixel-level classification problem mainly addressed by discriminative methods. We propose a novel approach, named Generative Edge Detector (GED), by fully utilizing the potential of the pre-trained stable diffusion model. We conduct extensive experiments on multiple datasets and achieve competitive performance.
  arXiv  Detail & Related papers  (2024-10-04T01:52:23Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected. We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure. Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
  arXiv  Detail & Related papers  (2024-02-08T14:43:56Z)
• Hypergraph Structure Inference From Data Under Smoothness Prior [46.568839316694515]
  We propose a method to infer the probability for each potential hyperedge without labelled data as supervision. We use this prior to derive the relation between the hypergraph structure and the node features via probabilistic modelling. Experiments on both synthetic and real-world data demonstrate that our method can learn meaningful hypergraph structures from data more efficiently than existing hypergraph structure inference methods.
  arXiv  Detail & Related papers  (2023-08-27T18:28:58Z)
• Hard Nominal Example-aware Template Mutual Matching for Industrial Anomaly Detection [74.9262846410559]
  textbfHard Nominal textbfExample-aware textbfTemplate textbfMutual textbfMatching (HETMM) textitHETMM aims to construct a robust prototype-based decision boundary, which can precisely distinguish between hard-nominal examples and anomalies.
  arXiv  Detail & Related papers  (2023-03-28T17:54:56Z)
• The Treasure Beneath Multiple Annotations: An Uncertainty-aware Edge Detector [70.43599299422813]
  Existing methods fuse multiple annotations using a simple voting process, ignoring the inherent ambiguity of edges and labeling bias of annotators. We propose a novel uncertainty-aware edge detector (UAED), which employs uncertainty to investigate the subjectivity and ambiguity of diverse annotations. UAED achieves superior performance consistently across multiple edge detection benchmarks.
  arXiv  Detail & Related papers  (2023-03-21T13:14:36Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• Statistical Limits for Testing Correlation of Hypergraphs [4.898744396854313]
  We consider the hypothesis testing of correlation between two $m$-uniform hypergraphs on $n$ unlabelled nodes. Under the null hypothesis, the hypergraphs are independent, while under the alternative hypothesis, the hyperdges have the same marginal distributions as in the null hypothesis but are correlated after some unknown node permutation.
  arXiv  Detail & Related papers  (2022-02-11T20:11:21Z)
• Hypothesis Testing for Equality of Latent Positions in Random Graphs [0.2741266294612775]
  We consider the hypothesis testing problem that two vertices $i$ and $j$th have the same latent positions, possibly up to scaling. We propose several test statistics based on the empirical Mahalanobis distances between the $i$th and $j$th rows of either the adjacency or the normalized Laplacian spectral embedding of the graph. Using these test statistics, we address the model selection problem of choosing between the standard block model and its degree-corrected variant.
  arXiv  Detail & Related papers  (2021-05-23T01:27:23Z)
• Information Limits for Detecting a Subhypergraph [6.903929927172917]
  We consider the problem of recovering a subhypergraph based on an observed adjacency tensor corresponding to a uniform hypergraph. We consider both weak recovery and exact recovery of the subhypergraph, and establish information-theoretic limits in each case.
  arXiv  Detail & Related papers  (2021-05-05T18:08:42Z)
• Heterogeneous Dense Subhypergraph Detection [6.903929927172917]
  We study the problem of testing the existence of a heterogeneous dense subhypergraph. The null hypothesis corresponds to a heterogeneous Erd"os-R'enyi uniform random hypergraph. The alternative hypothesis corresponds to a heterogeneous uniform random hypergraph that contains a dense subhypergraph.
  arXiv  Detail & Related papers  (2021-04-08T20:44:22Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated. Under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null.
  arXiv  Detail & Related papers  (2020-08-23T19:19:45Z)

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.