論文の概要: inGRASS: Incremental Graph Spectral Sparsification via
Low-Resistance-Diameter Decomposition
- arxiv url: http://arxiv.org/abs/2402.16990v1
- Date: Mon, 26 Feb 2024 19:49:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 18:41:13.825357
- Title: inGRASS: Incremental Graph Spectral Sparsification via
Low-Resistance-Diameter Decomposition
- Title（参考訳）: InGRASS:低抵抗次元分解によるインクリメンタルグラフスペクトルスペーサー化
- Authors: Ali Aghdaei and Zhuo Feng
- Abstract要約: inGRASSは、大きな非方向グラフのインクリメンタルスペクトルスカラー化のために設計された新しいアルゴリズムである。
提案アルゴリズムはスケーラビリティが高く,並列性が高く,セットアップフェーズにほぼ線形時間を要する。
実験では、inGRASSは、同等のソリューション品質を維持しながら、200倍以上のスピードアップを達成する。
- 参考スコア（独自算出の注目度）: 5.457150493905064
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This work presents inGRASS, a novel algorithm designed for incremental
spectral sparsification of large undirected graphs. The proposed inGRASS
algorithm is highly scalable and parallel-friendly, having a nearly-linear time
complexity for the setup phase and the ability to update the spectral
sparsifier in $O(\log N)$ time for each incremental change made to the original
graph with $N$ nodes. A key component in the setup phase of inGRASS is a
multilevel resistance embedding framework introduced for efficiently
identifying spectrally-critical edges and effectively detecting redundant ones,
which is achieved by decomposing the initial sparsifier into many node clusters
with bounded effective-resistance diameters leveraging a
low-resistance-diameter decomposition (LRD) scheme. The update phase of inGRASS
exploits low-dimensional node embedding vectors for efficiently estimating the
importance and uniqueness of each newly added edge. As demonstrated through
extensive experiments, inGRASS achieves up to over $200 \times$ speedups while
retaining comparable solution quality in incremental spectral sparsification of
graphs obtained from various datasets, such as circuit simulations, finite
element analysis, and social networks.
- Abstract（参考訳）: この研究は、大きな非方向グラフのインクリメンタルスペクトルスカラー化のために設計された新しいアルゴリズムであるInGRASSを提示する。
提案するingrassアルゴリズムは高度にスケーラブルで並列性に富み、セットアップフェーズのほぼ線形な時間複雑性と、n$ノードで元のグラフへのインクリメンタルな変更毎に$o(\log n)$時間でスペクトルスパーシファイアを更新できる能力を備えている。
InGRASSのセットアップフェーズにおけるキーコンポーネントは、スペクトルクリティカルエッジを効率的に識別し、冗長なエッジを効果的に検出するために導入されたマルチレベル抵抗埋め込みフレームワークであり、低抵抗径分解(LRD)方式を利用して、初期スペーサーを多くのノードクラスタに分割することで実現されている。
InGRASSの更新フェーズでは、低次元ノード埋め込みベクトルを利用して、新しく追加されたエッジの重要性とユニークさを効率的に推定する。
広範な実験によって実証されたように、InGRASSは、回路シミュレーション、有限要素解析、ソーシャルネットワークなど、様々なデータセットから得られるグラフのインクリメンタルスペクトルスカラー化において、同等のソリューション品質を維持しながら、200ドル以上のスピードアップを達成する。
関連論文リスト
- Point Cloud Denoising With Fine-Granularity Dynamic Graph Convolutional Networks [58.050130177241186]
ノイズの摂動は、しばしば3次元の点雲を破損させ、表面の再構成、レンダリング、さらなる処理といった下流のタスクを妨げる。
本稿では,GDGCNと呼ばれる粒度動的グラフ畳み込みネットワークについて紹介する。
論文 参考訳（メタデータ） (2024-11-21T14:19:32Z) - Sparse Decomposition of Graph Neural Networks [20.768412002413843]
本稿では,集約中に含まれるノード数を削減する手法を提案する。
線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。
提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
論文 参考訳（メタデータ） (2024-10-25T17:52:16Z) - Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。
最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。
我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
論文 参考訳（メタデータ） (2023-10-23T01:25:44Z) - Accelerating Scalable Graph Neural Network Inference with Node-Adaptive
Propagation [80.227864832092]
グラフニューラルネットワーク(GNN)は、様々なアプリケーションで例外的な効果を発揮している。
大規模グラフの重大化は,GNNによるリアルタイム推論において重要な課題となる。
本稿では,オンライン伝搬フレームワークと2つの新しいノード適応伝搬手法を提案する。
論文 参考訳（メタデータ） (2023-10-17T05:03:00Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - A Graph Encoder-Decoder Network for Unsupervised Anomaly Detection [7.070726553564701]
グラフから異常ノードを検出するための教師なしグラフエンコーダデコーダモデルを提案する。
符号化段階では、クラスタ割り当て行列を見つけるためにLCPoolと呼ばれる新しいプール機構を設計する。
復号段階ではLCUnpoolと呼ばれるアンプール演算を提案し,元のグラフの構造と結節の特徴を再構築する。
論文 参考訳（メタデータ） (2023-08-15T13:49:12Z) - SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements [16.313489255657203]
線形測定による抵抗ネットワーク学習のためのスペクトルグラフ密度化フレームワーク(SGL)
グラフの多重レベルスペクトル近似を利用するソルバフリー法(SF-SGL)。
ベクトルレスパワー/熱的整合性検証のためのEDAアルゴリズム
論文 参考訳（メタデータ） (2023-02-09T00:33:19Z) - Low-complexity Near-optimum Symbol Detection Based on Neural Enhancement
of Factor Graphs [2.030567625639093]
本稿では,シンボル検出のための因子グラフフレームワークの線形シンボル間干渉チャネルへの応用について考察する。
ニューラルエンハンスメントによる因子グラフに基づくシンボル検出の性能向上のための戦略を開発し,評価する。
論文 参考訳（メタデータ） (2022-03-30T15:58:53Z) - Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。
実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
論文 参考訳（メタデータ） (2021-06-03T17:05:40Z) - SF-GRASS: Solver-Free Graph Spectral Sparsification [16.313489255657203]
本研究では,新しいスペクトルグラフ粗化技術とグラフ信号処理技術を活用することで,スペクトルグラフスカラー化のための解法フリーアプローチ(SF-GRASS)を提案する。
提案手法は,様々な実世界の大規模グラフや回路網に対して,ほぼ直線時間で高品質なスペクトルスペーサーの階層を生成することができることを示す。
論文 参考訳（メタデータ） (2020-08-17T21:37:19Z) - Fast Graph Attention Networks Using Effective Resistance Based Graph
Sparsification [70.50751397870972]
FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。
我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
論文 参考訳（メタデータ） (2020-06-15T22:07:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。