論文の概要: Exact Recovery in the General Hypergraph Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2105.04770v1
• Date: Tue, 11 May 2021 03:39:08 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-13 01:49:39.707705
• Title: Exact Recovery in the General Hypergraph Stochastic Block Model
• Title（参考訳）: 一般ハイパーグラフ確率ブロックモデルにおける厳密な回復
• Authors: Qiaosheng Zhang, Vincent Y. F. Tan
• Abstract要約: 本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
• 参考スコア（独自算出の注目度）: 92.28929858529679
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph stochastic block model (d-HSBM), wherein n nodes are partitioned into k disjoint communities with relative sizes (p1,..., pk). Each subset of nodes with cardinality d is generated independently as an order-d hyperedge with a certain probability that depends on the ground-truth communities that the d nodes belong to. The goal is to exactly recover the k hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and d-HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.
• Abstract（参考訳）: 本稿では,d-uniform hypergraph stochastic block model (d-HSBM) において,nノードを相対サイズ(p1。 基数 d のノードの各部分集合は、d のノードが属する基底真理群に依存する確率のある位数d ハイパーエッジとして独立に生成される。 目標は、観測されたハイパーグラフに基づいて、k隠れのコミュニティを正確に回復することである。 精度の高いしきい値が存在して、正確な回復がしきい値より上にあり、しきい値以下では不可能であることが示される(正確に指定されるパラメータの小さな規則とは別に)。 この閾値は、コミュニティ間での一般化されたチェルノフ・ヘリンジャーの分岐と呼ばれる量で表される。 この一般モデルの結果は,2つの対称群落を持つ標準sbmとd-hsbmの先行結果を特別に復元する。 達成可能性を証明するために,しきい値を満たす多項式時間2段階アルゴリズムを開発した。 第1段階は、あるハイパーグラフスペクトルクラスタリング手法を採用して、コミュニティの粗い推定を行い、第2段階は、各ノードを局所的な精錬ステップを通じて個別に精錬し、正確な回復を確保する。

関連論文リスト

• Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
  本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。 我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
  論文  参考訳（メタデータ） (2024-01-17T13:39:38Z)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Multilayer hypergraph clustering using the aggregate similarity matrix [0.7373617024876725]
  ハイパーグラフブロックモデル(HSBM)の多層版におけるコミュニティリカバリ問題について考察する。 本研究では、半定値プログラミング(SDP)アプローチを調査し、正確な回復を保証するモデルパラメータに関する情報理論条件を求める。
  論文  参考訳（メタデータ） (2023-01-27T11:15:46Z)
• Exact Recovery of Community Detection in dependent Gaussian Mixture Models [5.312472550578279]
  ガウス混合モデルを用いたコミュニティ検出問題について検討する。 我々は,最大推定値の正確な回復に必要かつ十分な条件を証明した。
  論文  参考訳（メタデータ） (2022-09-23T14:26:19Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。 我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。 技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
  論文  参考訳（メタデータ） (2022-02-02T20:11:33Z)
• Density Ratio Estimation via Infinitesimal Classification [85.08255198145304]
  そこで我々は, DRE-inftyを提案する。 DRE-inftyは, 密度比推定(DRE)を, より簡単なサブプロブレムに還元する手法である。 モンテカルロ法にインスパイアされ、中間ブリッジ分布の無限連続体を介して2つの分布の間を滑らかに補間する。 提案手法は,複雑な高次元データセット上での相互情報推定やエネルギーベースモデリングなどの下流タスクにおいて良好に動作することを示す。
  論文  参考訳（メタデータ） (2021-11-22T06:26:29Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。 本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
  論文  参考訳（メタデータ） (2021-08-10T14:46:17Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。 この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。 また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
  論文  参考訳（メタデータ） (2020-06-29T07:03:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。