論文の概要: UltraProp: Principled and Explainable Propagation on Large Graphs
- arxiv url: http://arxiv.org/abs/2301.00270v1
- Date: Sat, 31 Dec 2022 19:08:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 16:05:20.939110
- Title: UltraProp: Principled and Explainable Propagation on Large Graphs
- Title（参考訳）: UltraProp: 大きなグラフの原則と説明可能な伝播
- Authors: Meng-Chieh Lee, Shubhranshu Shekhar, Jaemin Yoo, Christos Faloutsos
- Abstract要約: 本研究は,ネットワーク効果分析(NEA)とウルトラプロップ(UltraProp)の2つの知見に基づく。
NEAは、グラフがネットワーク効果を示すかどうかを統計的に検証し、異方性を持つ多くの実世界のグラフにNEが存在しないことを驚くほど発見する。
UltraProp はノード分類問題を顕著な利点で解決する: (a) ネットワーク効果 (NE) と近傍微分 (ND) の洞察による精度; (b) 説明可能
- 参考スコア（独自算出の注目度）: 17.968412301917187
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a large graph with few node labels, how can we (a) identify the mixed
network-effect of the graph and (b) predict the unknown labels accurately and
efficiently? This work proposes Network Effect Analysis (NEA) and UltraProp,
which are based on two insights: (a) the network-effect (NE) insight: a graph
can exhibit not only one of homophily and heterophily, but also both or none in
a label-wise manner, and (b) the neighbor-differentiation (ND) insight:
neighbors have different degrees of influence on the target node based on the
strength of connections. NEA provides a statistical test to check whether a
graph exhibits network-effect or not, and surprisingly discovers the absence of
NE in many real-world graphs known to have heterophily. UltraProp solves the
node classification problem with notable advantages: (a) Accurate, thanks to
the network-effect (NE) and neighbor-differentiation (ND) insights; (b)
Explainable, precisely estimating the compatibility matrix; (c) Scalable, being
linear with the input size and handling graphs with millions of nodes; and (d)
Principled, with closed-form formula and theoretical guarantee. Applied on
eight real-world graph datasets, UltraProp outperforms top competitors in terms
of accuracy and run time, requiring only stock CPU servers. On a large
real-world graph with 1.6M nodes and 22.3M edges, UltraProp achieves more than
9 times speedup (12 minutes vs. 2 hours) compared to most competitors.
- Abstract（参考訳）: ノードラベルの少ないグラフが与えられたら、どうすればいいのか?
(a)グラフの混合ネットワーク効果を識別し、
b) 未知のラベルを正確にかつ効率的に予測する。
ネットワーク効果分析(NEA)とウルトラプロップ(UltraProp)は,2つの知見に基づく。
(a)ネットワーク効果(NE)の洞察:グラフは、ホモフィリーかつヘテロフィリーの1つだけでなく、ラベル的にも、あるいは全くも表すことができ、
(b) 隣の微分(nd) 洞察: 隣人は接続の強さに基づいて、対象ノードに対する影響度が異なる。
NEAは、グラフがネットワーク効果を示すかどうかを統計テストし、異種グラフを持つ多くの実世界のグラフにNEが存在しないことを驚くほど発見する。
UltraProp はノード分類問題を顕著な利点で解決する。
(a)ネットワーク効果(NE)と近隣微分(ND)の洞察のおかげで正確なこと。
b) 互換性マトリックスを正確に推定すること。
(c)スケーラブルで、入力サイズと線形で、数百万のノードでグラフを扱うこと。
(d)原理、閉形式公式、理論的保証。
8つの実世界のグラフデータセットに適用されるultrapropは、正確さと実行時間で上位の競合相手を上回り、ストックcpuサーバのみを必要とする。
1.6Mノードと22.3Mエッジを持つ大規模な現実世界グラフでは、UltraPropは競合相手に比べて9倍以上のスピードアップ(12分対2時間)を達成する。
関連論文リスト
- Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
MultItask acTIve Graph Anomaly Detection framework,すなわちMITIGATEを提案する。
ノード分類タスクを結合することにより、MITIGATEは既知の異常を伴わずに配布外ノードを検出する能力を得る。
4つのデータセットに関する実証的研究は、MITIGATEが異常検出のための最先端の手法を著しく上回っていることを示している。
論文 参考訳（メタデータ） (2024-01-24T03:43:45Z) - Breaking the Entanglement of Homophily and Heterophily in
Semi-supervised Node Classification [25.831508778029097]
統計的観点から,ノードプロファイルとトポロジの関係を定量化するAMUDを提案する。
また、AMUDのための新しい有向グラフ学習パラダイムとしてADPAを提案する。
論文 参考訳（メタデータ） (2023-12-07T07:54:11Z) - TouchUp-G: Improving Feature Representation through Graph-Centric
Finetuning [37.318961625795204]
グラフニューラルネットワーク(GNN)は、多くのハイインパクトな実世界のグラフアプリケーションにおいて最先端のアプローチとなっている。
機能豊富なグラフでは、PMを直接利用して機能を生成するのが一般的である。
PMから抽出されたノード特徴がグラフに依存しず、GNNがグラフ構造とノード特徴の間の潜在的な相関を十分に活用できないため、このプラクティスは準最適である。
論文 参考訳（メタデータ） (2023-09-25T05:44:40Z) - Learning on Graphs with Out-of-Distribution Nodes [33.141867473074264]
グラフニューラルネットワーク(GNN)は、グラフ上で予測タスクを実行するための最先端モデルである。
この研究は、分散ノードによるグラフ学習の問題を定義する。
本稿では,異なるノード間の相互作用を明示的にモデル化する新しいGNNモデルであるOut-of-Distribution Graph Attention Network (OODGAT)を提案する。
論文 参考訳（メタデータ） (2023-08-13T08:10:23Z) - BOURNE: Bootstrapped Self-supervised Learning Framework for Unified
Graph Anomaly Detection [50.26074811655596]
自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。
ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。
BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
論文 参考訳（メタデータ） (2023-07-28T00:44:57Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。
GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。
また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-05-22T10:29:52Z) - Resisting Graph Adversarial Attack via Cooperative Homophilous
Augmentation [60.50994154879244]
最近の研究では、グラフニューラルネットワークは弱く、小さな摂動によって簡単に騙されることが示されている。
本研究では,グラフインジェクションアタック(Graph Injection Attack)という,新興だが重要な攻撃に焦点を当てる。
本稿では,グラフデータとモデルの協調的同好性増強によるGIAに対する汎用防衛フレームワークCHAGNNを提案する。
論文 参考訳（メタデータ） (2022-11-15T11:44:31Z) - Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with
Heterophily [58.76759997223951]
我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。
また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
論文 参考訳（メタデータ） (2022-03-19T14:26:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。