論文の概要: Non-adaptive Learning of Random Hypergraphs with Queries

• arxiv url: http://arxiv.org/abs/2501.12771v1
• Date: Wed, 22 Jan 2025 10:14:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 13:30:23.262659
• Title: Non-adaptive Learning of Random Hypergraphs with Queries
• Title（参考訳）: クエリによるランダムハイパーグラフの非適応学習
• Authors: Bethany Austhof, Lev Reyzin, Erasmo Tani,
• Abstract要約: 隠れハイパーグラフの$G=(V,E)$を1バッチのクエリで(非適応的に)学習する問題について検討する。 We generalize the results of Li et al. to the setting of random $k$-uniform hypergraphs。
• 参考スコア（独自算出の注目度）: 0.9831489366502302
• License:
• Abstract: We study the problem of learning a hidden hypergraph $G=(V,E)$ by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set $S\subseteq V$ contain at least one full hyperedge?'' In this model, it is known that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than $\Omega(\min\{m^2\log n, n^2\})$ even when the hypergraph is constrained to be $2$-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. overcame this lower bound in the setting in which $G$ is a graph by assuming that the graph learned is sampled from an Erd\H{o}s-R\'enyi model. We generalize the result of Li et al. to the setting of random $k$-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.
• Abstract（参考訳）: 隠れハイパーグラフの$G=(V,E)$を1バッチのクエリで(非適応的に)学習する問題について検討する。 このモデルでは、任意のハイパーグラフを$\Omega(\min\{m^2\log n, n^2\})$以下にすることで、任意のハイパーグラフを非適応的に学習できるアルゴリズムが存在しないことが知られている(つまり、ハイパーグラフは単にグラフである)。 最近、Li と al はこの下界を、学習したグラフが Erd\H{o}s-R\enyi モデルから標本化されることを仮定して、$G$ がグラフであるような設定で覆っている。 We generalize the results of Li et al to the setting of random $k$-uniform hypergraphs。 この結果を達成するために、単一ハイパーエッジの学習問題と標準グループテスト問題との間の新しい等価性を利用する。 後者の結果は独立した関心を持つこともある。

関連論文リスト

• Hypergraph $p$-Laplacian regularization on point clouds for data interpolation [3.79830302036482]
  ハイパーグラフはデータの高次関係をモデル化するために広く使われている。 点クラウド上の$varepsilon_n$-ballハイパーグラフと$k_n$-nearest 近傍ハイパーグラフを定義する。 半教師付き環境でのハイパーグラフ$p$-ラプラシアン正則化と$p$-ラプラシアン正則化の間の変分一貫性を証明した。
  論文  参考訳（メタデータ） (2024-05-02T09:17:32Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Core-periphery Models for Hypergraphs [0.0]
  コア周辺構造に対するランダムなハイパーグラフモデルを提案する。 我々は,実際に線形wrtを持つ大規模ハイパーグラフにスケール可能な,新しい統計的推論アルゴリズムを開発した。 我々の推論アルゴリズムはハイパーグラフ内のノードの評判(ランク)に対応する埋め込みを学習することができる。
  論文  参考訳（メタデータ） (2022-06-01T22:11:44Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。 本稿では,提案するフレームワークが最先端の性能を達成できることを示す。 ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
  論文  参考訳（メタデータ） (2022-03-31T10:46:47Z)
• Learning Low Degree Hypergraphs [6.062751776009752]
  エッジ検出クエリによるハイパーグラフ学習の問題について検討する。 本稿では,エッジサイズが指数関数的に大きくなるクエリの複雑さに悩まされることなく,学習可能なハイパーグラフの族を特定することを目的とする。
  論文  参考訳（メタデータ） (2022-02-21T04:38:24Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)

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

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