論文の概要: Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection
in Graphs
- arxiv url: http://arxiv.org/abs/2206.12786v1
- Date: Sun, 26 Jun 2022 04:59:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 16:23:54.301219
- Title: Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection
in Graphs
- Title(参考訳): グラフの異常パターン検出のための校正非パラメトリックスキャン統計
- Authors: Chunpai Wang, Daniel B. Neill, Feng Chen
- Abstract要約: 非パラメトリックスキャン統計(NPSS)は、有意ノードの割合よりも高い連結部分グラフを同定する。
NPSSは、異常な部分グラフに対する最近校正された統計量の多元性を説明できない。
本稿では,NPSSの再校正,複数の仮説テストの調整,基礎となるグラフ構造を考慮した新しい統計手法を提案する。
- 参考スコア(独自算出の注目度): 4.756490355031122
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new approach, the calibrated nonparametric scan statistic
(CNSS), for more accurate detection of anomalous patterns in large-scale,
real-world graphs. Scan statistics identify connected subgraphs that are
interesting or unexpected through maximization of a likelihood ratio statistic;
in particular, nonparametric scan statistics (NPSSs) identify subgraphs with a
higher than expected proportion of individually significant nodes. However, we
show that recently proposed NPSS methods are miscalibrated, failing to account
for the maximization of the statistic over the multiplicity of subgraphs. This
results in both reduced detection power for subtle signals, and low precision
of the detected subgraph even for stronger signals. Thus we develop a new
statistical approach to recalibrate NPSSs, correctly adjusting for multiple
hypothesis testing and taking the underlying graph structure into account.
While the recalibration, based on randomization testing, is computationally
expensive, we propose both an efficient (approximate) algorithm and new,
closed-form lower bounds (on the expected maximum proportion of significant
nodes for subgraphs of a given size, under the null hypothesis of no anomalous
patterns). These advances, along with the integration of recent core-tree
decomposition methods, enable CNSS to scale to large real-world graphs, with
substantial improvement in the accuracy of detected subgraphs. Extensive
experiments on both semi-synthetic and real-world datasets are demonstrated to
validate the effectiveness of our proposed methods, in comparison with
state-of-the-art counterparts.
- Abstract(参考訳): 大規模実世界のグラフにおける異常パターンをより正確に検出するための新しい手法として、キャリブレーションされた非パラメトリックスキャン統計法(CNSS)を提案する。
Scan statistics identified connected subgraphs that are interesting or unexpected by the maximization of a chance ratio statistic; in particular, nonparametric scan statistics (NPSSs) identified subgraphs higher than a expected than% of individually significant node。
しかし,最近提案されたNPSS法は誤校正され,部分グラフの多重性に対する統計量の最大化を考慮できないことを示す。
これにより、微妙な信号の検出力が低下し、より強い信号であっても検出されたサブグラフの精度が低下する。
そこで本研究では,NPSSの再校正,複数仮説の検証,基礎となるグラフ構造を考慮した新しい統計手法を提案する。
ランダム化テストに基づく再校正は計算コストがかかるが,提案手法は効率のよい(近似)アルゴリズムと新しい閉形式下限(任意のサイズの部分グラフに対する有意なノードの最大比率)の両方を,異常なパターンのないヌル仮説の下で提案する。
これらの進歩と最近のコアツリー分解手法の統合により、CNSSは検出された部分グラフの精度を大幅に向上し、大規模な実世界のグラフにスケールすることができる。
半合成および実世界の両方のデータセットに対する大規模な実験を行い,提案手法の有効性を検証する。
関連論文リスト
- Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gaps [7.174572371800217]
本稿では,不完全かつノイズの多い観測を用いて,テンソル線形形式を統計的に推定する簡易かつ効率的な手法を提案する。
これは、信頼区間の構築、ヘテロスケダティックおよびサブ指数雑音下での推論、同時テストなど、様々な統計的推論タスクに適している。
論文 参考訳(メタデータ) (2024-10-15T03:09:52Z) - Reproduction of scan B-statistic for kernel change-point detection algorithm [10.49860279555873]
変化点検出は、幅広い応用のために大きな注目を集めている。
本稿では,カーネルベースの効率的なスキャンB統計に基づくオンライン変更点検出アルゴリズムを最近提案した。
数値実験により, 走査型B統計が常に優れた性能を発揮することが示された。
論文 参考訳(メタデータ) (2024-08-23T15:12:31Z) - Graph Out-of-Distribution Generalization with Controllable Data
Augmentation [51.17476258673232]
グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。
トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。
仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
論文 参考訳(メタデータ) (2023-08-16T13:10:27Z) - Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural
Networks [89.28881869440433]
本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。
解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
論文 参考訳(メタデータ) (2023-02-06T16:54:20Z) - Convergence of uncertainty estimates in Ensemble and Bayesian sparse
model discovery [4.446017969073817]
ブートストラップに基づく逐次しきい値最小二乗推定器による雑音に対する精度と頑健性の観点から経験的成功を示す。
このブートストラップに基づくアンサンブル手法は,誤差率の指数収束率で,確率的に正しい可変選択を行うことができることを示す。
論文 参考訳(メタデータ) (2023-01-30T04:07:59Z) - Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
本研究では, スコアマッチングの統計的効率と推定される分布の等尺性との間に, 密接な関係を示す。
これらの結果はサンプル状態と有限状態の両方で定式化する。
論文 参考訳(メタデータ) (2022-10-03T06:09:01Z) - Differential privacy and robust statistics in high dimensions [49.50869296871643]
高次元Propose-Test-Release (HPTR) は指数的メカニズム、頑健な統計、Propose-Test-Release メカニズムという3つの重要なコンポーネントの上に構築されている。
本論文では,HPTRが複数のシナリオで最適サンプル複雑性をほぼ達成していることを示す。
論文 参考訳(メタデータ) (2021-11-12T06:36:40Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳(メタデータ) (2020-05-22T22:30:52Z) - An Optimal Statistical and Computational Framework for Generalized
Tensor Estimation [10.899518267165666]
本稿では,低ランクテンソル推定問題に対するフレキシブルなフレームワークについて述べる。
計算画像、ゲノミクス、ネットワーク解析の応用から多くの重要な例を含む。
論文 参考訳(メタデータ) (2020-02-26T01:54:35Z) - Statistical Outlier Identification in Multi-robot Visual SLAM using
Expectation Maximization [18.259478519717426]
本稿では、同時局所化およびマッピング(SLAM)におけるマップ間ループ閉包外乱検出のための、新しい分散手法を提案する。
提案アルゴリズムは優れた初期化に頼らず、一度に2つ以上のマップを処理できる。
論文 参考訳(メタデータ) (2020-02-07T06:34:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。