Heterogeneous Dense Subhypergraph Detection

• URL: http://arxiv.org/abs/2104.04047v1
• Date: Thu, 8 Apr 2021 20:44:22 GMT
• Title: Heterogeneous Dense Subhypergraph Detection
• Authors: Mingao Yuan and Zuofeng Shang
• Abstract summary: 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.
• Score: 6.903929927172917
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of testing the existence of a heterogeneous dense subhypergraph. The null hypothesis corresponds to a heterogeneous Erd\"{o}s-R\'{e}nyi uniform random hypergraph and the alternative hypothesis corresponds to a heterogeneous uniform random hypergraph that contains a dense subhypergraph. We establish detection boundaries when the edge probabilities are known and construct an asymptotically powerful test for distinguishing the hypotheses. We also construct an adaptive test which does not involve edge probabilities, and hence, is more practically useful.

Related papers

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity. An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Kernel Robust Hypothesis Testing [20.78285964841612]
  In this paper, uncertainty sets are constructed in a data-driven manner using kernel method. The goal is to design a test that performs well under the worst-case distributions over the uncertainty sets. For the Neyman-Pearson setting, the goal is to minimize the worst-case probability of miss detection subject to a constraint on the worst-case probability of false alarm.
  arXiv  Detail & Related papers  (2022-03-23T23:59:03Z)
• 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)
• Group Testing with Non-identical Infection Probabilities [59.96266198512243]
  We develop an adaptive group testing algorithm using the set formation method. We show that our algorithm outperforms the state of the art, and performs close to the entropy lower bound.
  arXiv  Detail & Related papers  (2021-08-27T17:53:25Z)
• Typing assumptions improve identification in causal discovery [123.06886784834471]
  Causal discovery from observational data is a challenging task to which an exact solution cannot always be identified. We propose a new set of assumptions that constrain possible causal relationships based on the nature of the variables.
  arXiv  Detail & Related papers  (2021-07-22T14:23:08Z)
• 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)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• A practical test for a planted community in heterogeneous networks [0.0]
  For a real network data, the existence of a dense subgraph is generally unknown. The power of the test is theoretically investigated and we evaluate the performance of the test by simulation and real data example.
  arXiv  Detail & Related papers  (2021-01-15T01:34:14Z)
• Sharp detection boundaries on testing dense subhypergraph [6.903929927172917]
  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.
  arXiv  Detail & Related papers  (2021-01-12T16:31:47Z)

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.