論文の概要: Robust Detection of Planted Subgraphs in Semi-Random Models

• arxiv url: http://arxiv.org/abs/2508.02158v1
• Date: Mon, 04 Aug 2025 07:59:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:22.238751
• Title: Robust Detection of Planted Subgraphs in Semi-Random Models
• Title（参考訳）: 半ランダムモデルによる植林部分グラフのロバスト検出
• Authors: Dor Elimelech, Wasim Huleihel,
• Abstract要約: Erd"os-R'enyiランダムグラフにおける植木部分グラフの検出は広く研究されている。 ほとんどの先行研究は純粋にランダムな生成モデルを想定しており、結果として得られるアルゴリズムは現実世界の摂動に直面して脆弱である可能性がある。 本研究では,グラフが統計学者に開示される前に,グラフの外側の辺を取り除くことができる半ランダムモデルについて検討する。 本研究は,半ランダムモデル,計算統計的トレードオフ,ロバストネスの研究において,植込み部分グラフ検出のための最初の堅牢なフレームワークを構築した。
• 参考スコア（独自算出の注目度）: 7.320365821066746
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Detection of planted subgraphs in Erd\"os-R\'enyi random graphs has been extensively studied, leading to a rich body of results characterizing both statistical and computational thresholds. However, most prior work assumes a purely random generative model, making the resulting algorithms potentially fragile in the face of real-world perturbations. In this work, we initiate the study of semi-random models for the planted subgraph detection problem, wherein an adversary is allowed to remove edges outside the planted subgraph before the graph is revealed to the statistician. Crucially, the statistician remains unaware of which edges have been removed, introducing fundamental challenges to the inference task. We establish fundamental statistical limits for detection under this semi-random model, revealing a sharp dichotomy. Specifically, for planted subgraphs with strongly sub-logarithmic maximum density detection becomes information-theoretically impossible in the presence of an adversary, despite being possible in the classical random model. In stark contrast, for subgraphs with super-logarithmic density, the statistical limits remain essentially unchanged; we prove that the optimal (albeit computationally intractable) likelihood ratio test remains robust. Beyond these statistical boundaries, we design a new computationally efficient and robust detection algorithm, and provide rigorous statistical guarantees for its performance. Our results establish the first robust framework for planted subgraph detection and open new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in graph inference problems.
• Abstract（参考訳）: Erd\"os-R\'enyiランダムグラフにおける植木部分グラフの検出は広く研究され、統計と計算のしきい値の両方を特徴付ける多くの結果が得られた。 しかし、ほとんどの先行研究は純粋にランダムな生成モデルを想定しており、結果として得られるアルゴリズムは現実世界の摂動に直面して脆弱である可能性がある。 本研究では,グラフが統計学者に開示される前に,グラフの外側の辺を取り除くことができるような,植木部分グラフ検出問題に対する半ランダムモデルの研究を開始する。 重要なことに、統計学者はどの辺が取り除かれたのか知らないままであり、推論タスクに根本的な課題を提起している。 この半ランダムモデルに基づく検出の基本的な統計的限界を確立し、鋭い二分法を明らかにする。 具体的には、強い対数的最大密度検出を持つ植木部分グラフは、古典的ランダムモデルでは可能でありながら、敵の存在下では情報理論的に不可能となる。 対照的に、超対数密度を持つ部分グラフの場合、統計的限界は基本的に変化せず、最適(計算上は難解な)確率比テストが頑健であることを証明する。 これらの統計的境界を超えて、計算効率が高く堅牢な新しい検出アルゴリズムを設計し、その性能に対する厳密な統計的保証を提供する。 本研究は, 半ランダムモデル, 計算統計的トレードオフ, グラフ推論問題におけるロバスト性の研究において, 植込み部分グラフ検出のための最初のロバストな枠組みを確立した。

関連論文リスト

• SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search [2.082364067210557]
  本稿では,SBMパラメータを頑健に推定するアルゴリズムを提案する。 また,本手法は外れ値検出手法として機能し,グラフがモデルから逸脱する原因となるノードを適切に同定し,高次ノードを刈り取るといった単純な手法を克服する。
  論文  参考訳（メタデータ） (2025-06-04T07:47:25Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in Graphs [4.756490355031122]
  非パラメトリックスキャン統計(NPSS)は、有意ノードの割合よりも高い連結部分グラフを同定する。 NPSSは、異常な部分グラフに対する最近校正された統計量の多元性を説明できない。 本稿では,NPSSの再校正,複数の仮説テストの調整,基礎となるグラフ構造を考慮した新しい統計手法を提案する。
  論文  参考訳（メタデータ） (2022-06-26T04:59:13Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  多くの実世界のデータセットでは、複数のソースが集約され、本質的に欠落した情報(センサーの故障、調査における未回答の疑問...)が欠落する。 本稿では,広範に研究された線形モデルに焦点をあてるが,不足する値が存在する場合には,非常に難しい課題であることが判明した。 最終的には、多くの学習タスクを解決し、入力機能の数を指数関数的にすることで、現在の現実世界のデータセットでは予測が不可能になる。
  論文  参考訳（メタデータ） (2022-02-03T08:45:34Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  実世界の機械学習デプロイメントは、ソース(トレーニング)とターゲット(テスト)ディストリビューションのミスマッチによって特徴づけられる。 本研究では,ラベル付きソースデータとラベルなしターゲットデータのみを用いて,対象領域の精度を予測する手法を検討する。 本稿では,モデルの信頼度をしきい値として学習し,精度をラベルなし例のごく一部として予測する実践的手法である平均閾値保持信頼度(ATC)を提案する。
  論文  参考訳（メタデータ） (2022-01-11T23:01:12Z)
• Projected Sliced Wasserstein Autoencoder-based Hyperspectral Images Anomaly Detection [42.585075865267946]
  本稿では,PSW自動エンコーダを用いた異常検出手法を提案する。 特に、計算フレンドリーな固有分解法を利用して、高次元データをスライスする主成分を見つける。 様々な実世界のハイパースペクトル異常検出ベンチマークで実施した総合的な実験は,提案手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2021-12-20T09:21:02Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions [1.8275108630751844]
  ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。 従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。 この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
  論文  参考訳（メタデータ） (2020-12-14T01:15:39Z)
• Interpretable Anomaly Detection with Mondrian P{\'o}lya Forests on Data Streams [6.177270420667713]
  スケールでの異常検出は、非常に困難な実用性の問題である。 最近の研究は、異常検出のためのデータを要約するために、(ランダムな)$k$emphd-treesのバリエーションを合体させてきた。 これらの手法は、容易に解釈できないアドホックスコア関数に依存している。 我々はこれらの手法をモンドリアンポリアフォレストと呼ぶ確率的枠組みでコンテキスト化する。
  論文  参考訳（メタデータ） (2020-08-04T13:19:07Z)
• Improving Maximum Likelihood Training for Text Generation with Density Ratio Estimation [51.091890311312085]
  本稿では,テキスト生成で遭遇する大規模なサンプル空間において,効率よく安定な自動回帰シーケンス生成モデルのトレーニング手法を提案する。 本手法は,品質と多様性の両面で,最大類似度推定や他の最先端シーケンス生成モデルよりも安定に優れている。
  論文  参考訳（メタデータ） (2020-07-12T15:31:24Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)

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

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