論文の概要: Quantifying Node-based Core Resilience

• arxiv url: http://arxiv.org/abs/2306.12038v1
• Date: Wed, 21 Jun 2023 06:05:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 14:47:03.818050
• Title: Quantifying Node-based Core Resilience
• Title（参考訳）: ノードベースコアレジリエンスの定量化
• Authors: Jakir Hossain, Sucheta Soundarajan and Ahmet Erdem Sar{\i}y\"uce
• Abstract要約: コア分解は、様々なグラフ解析タスクのための効率的なビルディングブロックである。 コア分解の重大な弱点の1つは、いくつかのエッジを挿入または削除するグラフの変更に対する感度である。 エッジの除去・挿入時に個々のノードのレジリエンスを捉えるための除去強度と挿入強度の尺度を定義した。
• 参考スコア（独自算出の注目度）: 1.4610038284393165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Core decomposition is an efficient building block for various graph analysis tasks such as dense subgraph discovery and identifying influential nodes. One crucial weakness of the core decomposition is its sensitivity to changes in the graph: inserting or removing a few edges can drastically change the core structure of a graph. Hence, it is essential to characterize, quantify, and, if possible, improve the resilience of the core structure of a given graph in global and local levels. Previous works mostly considered the core resilience of the entire graph or important subgraphs in it. In this work, we study node-based core resilience measures upon edge removals and insertions. We first show that a previously proposed measure, Core Strength, does not correctly capture the core resilience of a node upon edge removals. Next, we introduce the concept of dependency graph to capture the impact of neighbor nodes (for edge removal) and probable future neighbor nodes (for edge insertion) on the core number of a given node. Accordingly, we define Removal Strength and Insertion Strength measures to capture the resilience of an individual node upon removing and inserting an edge, respectively. As naive computation of those measures is costly, we provide efficient heuristics built on key observations about the core structure. We consider two key applications, finding critical edges and identifying influential spreaders, to demonstrate the usefulness of our new measures on various real-world networks and against several baselines. We also show that our heuristic algorithms are more efficient than the naive approaches.
• Abstract（参考訳）: コア分解は、高密度部分グラフ発見や影響ノードの特定など、さまざまなグラフ解析タスクのための効率的なビルディングブロックである。 コア分解の重要な弱点の1つは、グラフの変更に対する感度である。 少数のエッジを挿入または削除することで、グラフのコア構造が劇的に変わる可能性がある。 したがって、グローバルおよび局所レベルにおける与えられたグラフのコア構造のレジリエンスを特徴づけ、定量化し、可能ならば改善することが不可欠である。 以前の作品は、主にグラフ全体や重要な部分グラフのコアレジリエンスと見なされていた。 本研究では,エッジ除去と挿入によるノードベースコアレジリエンス測定について検討する。 まず,従来提案されていたコア強度は,エッジ除去時にノードのコアレジリエンスを正確に捉えていないことを示す。 次に、依存グラフの概念を導入し、(エッジ除去のために)隣ノードと、(エッジ挿入のために)将来の隣ノードが与えられたノードのコア数に与える影響を捉える。 そこで我々は,エッジの除去および挿入時に各ノードのレジリエンスを捕捉するための除去強度と挿入強度をそれぞれ定義する。 これらの測定値のナイーブな計算は費用がかかるため、コア構造に関する重要な観測に基づく効率的なヒューリスティックを提供する。 我々は,重要エッジの発見と影響力のあるスプレッダの同定という2つの重要な応用について検討し,様々な実世界のネットワークと複数のベースラインに対する新しい尺度の有用性を実証する。 また、我々のヒューリスティックアルゴリズムは、単純なアプローチよりも効率的であることを示す。

関連論文リスト

• Graph Anomaly Detection with Noisy Labels by Reinforcement Learning [13.135788402192215]
  本稿では,新しいフレームワークREGAD,すなわちReinforced Graph Anomaly Detectorを提案する。 具体的には,高信頼ラベルを用いたノード間を近似したノイズエッジを切断することにより,ベース検出器の性能向上(AUC)を最大化することを目的とする。
  論文  参考訳（メタデータ） (2024-07-08T13:41:21Z)
• Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph [11.661431088477329]
  本稿では,背景ノードを適切に取得する新しいGraph-Skeleton1モデルを提案する。 特に、0.24億のノードを持つMAG240Mデータセットでは、生成したスケルトングラフは、元のグラフの1.8%のノードしか含んでおらず、非常に同等のパフォーマンスを実現しています。
  論文  参考訳（メタデータ） (2024-02-14T20:33:11Z)
• KITS: Inductive Spatio-Temporal Kriging with Increment Training Strategy [22.457676652258087]
  Krigingは、観測されたソースノード(センサー付き)を使用して、観測されていないノード(センサーなし)を推論するための調整されたタスクである。 ノードの代わりに仮想ノードをトレーニンググラフに追加し、グラフギャップマスキング問題を自然に解決する。 我々は、インクリメントトレーニング戦略をKITSと命名した。
  論文  参考訳（メタデータ） (2023-11-05T04:43:48Z)
• Latent Graph Inference with Limited Supervision [58.54674649232757]
  潜在グラフ推論(LGI)は、データ特徴から基礎となるグラフ構造とノード表現を共同で学習することを目的としている。 既存のLGI手法は、意味的な監督なしに巨大なエッジウェイトが学習され、トレーニング損失に寄与しない、監督飢餓の問題に悩まされることが一般的である。 本稿では,この問題の原因はグラフスカラー化操作であり,重要なノードとラベル付きノード間の接続を著しく破壊する。
  論文  参考訳（メタデータ） (2023-10-06T15:22:40Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
  本研究では,ノード埋め込みモデルのランダムおよび逆毒攻撃に対する経験的ロバスト性を評価する。 ネットワーク特性とノードラベルを用いて計算したエッジの追加,削除,再切り替えの戦略を比較した。 その結果,ノード分類はネットワーク再構成とは対照的に,高い性能劣化に悩まされていることがわかった。
  論文  参考訳（メタデータ） (2022-09-16T17:20:23Z)
• Graph Pooling with Maximum-Weight $k$-Independent Sets [12.251091325930837]
  最大ウェイト$k$非依存集合のグラフ理論的概念に基づくグラフ粗化機構を導入する。 我々は、経路長の歪み境界の理論的保証と、粗化グラフにおける重要な位相特性を保存できることを証明した。
  論文  参考訳（メタデータ） (2022-08-06T14:12:47Z)
• Learning Sparse Graphs with a Core-periphery Structure [14.112444998191698]
  本稿では,コア周辺構造ネットワークに関連するデータ生成モデルを提案する。 ネットワークのコア部分における密接な(疎い)接続を誘導するスパースグラフとニューダルコアスコアを推論する。
  論文  参考訳（メタデータ） (2021-10-08T10:41:30Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。 特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。 抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
  論文  参考訳（メタデータ） (2020-05-15T09:17:08Z)
• Structure-Feature based Graph Self-adaptive Pooling [65.4188800835203]
  グラフデータを扱うための新しいグラフ自己適応プーリング法を提案する。 本手法は, グラフ分類において有効であり, 最先端のグラフプーリング法より優れている。
  論文  参考訳（メタデータ） (2020-01-30T13:58:49Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  半教師付きノード分類の性能を高めるためのグラフ推論学習フレームワークを提案する。 推論過程の学習には,トレーニングノードから検証ノードへの構造関係のメタ最適化を導入する。 4つのベンチマークデータセットの総合的な評価は、最先端の手法と比較して提案したGILの優位性を示している。
  論文  参考訳（メタデータ） (2020-01-17T02:52:30Z)

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

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