論文の概要: Balancing Summarization and Change Detection in Graph Streams
- arxiv url: http://arxiv.org/abs/2311.18694v2
- Date: Tue, 12 Dec 2023 14:48:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-13 19:07:32.256149
- Title: Balancing Summarization and Change Detection in Graph Streams
- Title（参考訳）: グラフストリームにおける要約と変化検出のバランス
- Authors: Shintaro Fukushima and Kenji Yamanishi
- Abstract要約: 我々は,グラフ要約における圧縮速度と変化検出における精度との間にはトレードオフがあると主張している。
本稿では,このトレードオフのバランスを保ち,信頼性の高いグラフ要約と変更検出を同時に実現するための新しい定量的手法を提案する。
- 参考スコア（独自算出の注目度）: 11.188324016882342
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study addresses the issue of balancing graph summarization and graph
change detection. Graph summarization compresses large-scale graphs into a
smaller scale. However, the question remains: To what extent should the
original graph be compressed? This problem is solved from the perspective of
graph change detection, aiming to detect statistically significant changes
using a stream of summary graphs. If the compression rate is extremely high,
important changes can be ignored, whereas if the compression rate is extremely
low, false alarms may increase with more memory. This implies that there is a
trade-off between compression rate in graph summarization and accuracy in
change detection. We propose a novel quantitative methodology to balance this
trade-off to simultaneously realize reliable graph summarization and change
detection. We introduce a probabilistic structure of hierarchical latent
variable model into a graph, thereby designing a parameterized summary graph on
the basis of the minimum description length principle. The parameter specifying
the summary graph is then optimized so that the accuracy of change detection is
guaranteed to suppress Type I error probability (probability of raising false
alarms) to be less than a given confidence level. First, we provide a
theoretical framework for connecting graph summarization with change detection.
Then, we empirically demonstrate its effectiveness on synthetic and real
datasets.
- Abstract（参考訳）: 本研究では,グラフ要約とグラフ変更検出のバランス問題に対処する。
グラフ要約は、大規模グラフをより小さなスケールに圧縮する。
しかし、疑問は残る: 元のグラフはどれくらい圧縮されるべきなのか?
この問題は,サマリグラフのストリームを用いて統計的に有意な変化を検出することを目的とした,グラフ変化検出の観点から解かれる。
圧縮率が極端に高い場合、重要な変更は無視できるが、圧縮率が極端に低い場合は、メモリの増加とともに誤報が増加する可能性がある。
これは、グラフ総和の圧縮率と変更検出の精度との間にトレードオフがあることを意味する。
本稿では,このトレードオフのバランスを保ち,信頼性の高いグラフ要約と変更検出を同時に実現するための新しい定量的手法を提案する。
本稿では,階層的潜在変数モデルの確率的構造をグラフに導入し,最小記述長原理に基づいてパラメータ化された要約グラフを設計する。
次に、サマリーグラフを特定するパラメータを最適化し、変更検出の精度を保証し、タイプiのエラー確率(誤報を発生させる可能性)を所定の信頼レベル未満に抑える。
まず,グラフ要約と変化検出を結合する理論的枠組みを提案する。
そして、その効果を合成および実データに実証的に示す。
関連論文リスト
- Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detection [30.618065157205507]
本稿では,グラフレベルの異常検出のための新しい手法Motif-consistent Counterfactuals with Adversarial Refinement (MotifCAR)を提案する。
このモデルは、あるグラフのモチーフと、識別(カテゴリ)情報を含むコアサブグラフと、別のグラフのコンテキストサブグラフを組み合わせて、生の反事実グラフを生成する。
MotifCARは高品質な反ファクトグラフを生成することができる。
論文 参考訳（メタデータ） (2024-07-18T08:04:57Z) - Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
グラフレベルの異常検出(GLAD)は、コレクションの大多数と比べて顕著な相違を示すグラフを識別することを目的としている。
本稿では,異常なグラフを検出し,同時に情報的説明を生成する自己解釈グラフaNomaly dETectionモデル(SIGNET)を提案する。
論文 参考訳（メタデータ） (2023-10-25T10:10:07Z) - Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
コントラスト学習は、監督の有無にかかわらず、表現を学習するための第一の方法として現れてきた。
近年の研究では、グラフ表現学習における事前学習の有用性が示されている。
本稿では,グラフの対照的な目的に対する拡張を構築する際に,候補のバンクを提供するためのグラフ変換操作を提案する。
論文 参考訳（メタデータ） (2023-02-06T16:26:29Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。
ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。
合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
論文 参考訳（メタデータ） (2023-01-07T05:14:45Z) - Large Graph Signal Denoising with Application to Differential Privacy [2.867517731896504]
本稿では,データ駆動型ウェーブレット・タイト・フレーム手法を用いて,グラフ上の信号のデノイングを行う場合について考察する。
我々はChebyshev-Jackson近似を用いて、大きなグラフにスケーラブルにする。
実データとシミュレーションデータから,様々な大きさのグラフに対して総合的な性能解析を行う。
論文 参考訳（メタデータ） (2022-09-05T16:32:54Z) - Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。
本稿では、労働者が同じデータ分散を共有するとき、疎結合な分散最適化の正確な図面を描くことを目的とする。
我々の理論は深層学習における経験的観察と一致し、異なるグラフトポロジーの相対的メリットを正確に記述する。
論文 参考訳（メタデータ） (2022-06-07T08:19:06Z) - Graph Denoising with Framelet Regularizer [25.542429117462547]
本稿では,特徴雑音と構造雑音の両面からグラフデータの正則化を行う。
本モデルでは, グラフが汚染されている場合でも, 一般的なグラフ畳み込みと比較して, 性能が著しく向上する。
論文 参考訳（メタデータ） (2021-11-05T05:17:23Z) - Intrusion-Free Graph Mixup [33.07540841212878]
グラフニューラルネットワーク(GNN)の一般化を改善するための,単純かつ効果的な正規化手法を提案する。
視覚とテキストのためのMixup regularizerの最近の進歩を利用して、ランダムなサンプルペアとそのラベルを補間して、トレーニング用の合成サンプルを作成する。
提案手法は,グラフ分類学習を効果的に正規化することが可能であり,一般的なグラフ拡張ベースラインよりも予測精度が優れている。
論文 参考訳（メタデータ） (2021-10-18T14:16:00Z) - Partition and Code: learning how to compress graphs [50.29024357495154]
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
論文 参考訳（メタデータ） (2021-07-05T11:41:16Z) - Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。
従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
論文 参考訳（メタデータ） (2021-05-12T06:47:34Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。