論文の概要: SF-GRASS: Solver-Free Graph Spectral Sparsification
- arxiv url: http://arxiv.org/abs/2008.07633v1
- Date: Mon, 17 Aug 2020 21:37:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 04:35:35.081354
- Title: SF-GRASS: Solver-Free Graph Spectral Sparsification
- Title（参考訳）: sf-grass:ソルバフリーグラフのスペクトルスパーシフィケーション
- Authors: Ying Zhang, Zhiqiang Zhao, Zhuo Feng
- Abstract要約: 本研究では,新しいスペクトルグラフ粗化技術とグラフ信号処理技術を活用することで,スペクトルグラフスカラー化のための解法フリーアプローチ(SF-GRASS)を提案する。
提案手法は,様々な実世界の大規模グラフや回路網に対して,ほぼ直線時間で高品質なスペクトルスペーサーの階層を生成することができることを示す。
- 参考スコア（独自算出の注目度）: 16.313489255657203
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent spectral graph sparsification techniques have shown promising
performance in accelerating many numerical and graph algorithms, such as
iterative methods for solving large sparse matrices, spectral partitioning of
undirected graphs, vectorless verification of power/thermal grids,
representation learning of large graphs, etc. However, prior spectral graph
sparsification methods rely on fast Laplacian matrix solvers that are usually
challenging to implement in practice. This work, for the first time, introduces
a solver-free approach (SF-GRASS) for spectral graph sparsification by
leveraging emerging spectral graph coarsening and graph signal processing (GSP)
techniques. We introduce a local spectral embedding scheme for efficiently
identifying spectrally-critical edges that are key to preserving graph spectral
properties, such as the first few Laplacian eigenvalues and eigenvectors. Since
the key kernel functions in SF-GRASS can be efficiently implemented using
sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is
simple to implement and inherently parallel friendly. Our extensive
experimental results show that the proposed method can produce a hierarchy of
high-quality spectral sparsifiers in nearly-linear time for a variety of
real-world, large-scale graphs and circuit networks when compared with the
prior state-of-the-art spectral method.
- Abstract（参考訳）: 最近のスペクトルグラフスパーシフィケーション技術は、大きなスパース行列の解法、無向グラフのスペクトル分割法、電力/熱グリッドのベクトル無し検証、大グラフの表現学習など、多くの数値およびグラフアルゴリズムの高速化において有望な性能を示している。
しかしながら、事前のスペクトルグラフスパーシフィケーション法は、通常は実装が難しい高速ラプラシアン行列ソルバに依存している。
この研究は、新たに出現するスペクトルグラフ粗さ化とグラフ信号処理(gsp)技術を活用して、スペクトルグラフスパーシフィケーションのためのソルバフリーアプローチ(sf-grass)を導入した。
本稿では,グラフのスペクトル特性保存の鍵となるスペクトル臨界エッジを効率的に同定するための局所スペクトル埋め込みスキームについて紹介する。
SF-GRASSの核関数はスパース行列ベクトル乗算(SpMV)を用いて効率的に実装できるため、提案手法は実装が簡単で、本質的に並列性が高い。
提案手法は,従来のスペクトル法と比較して,実世界,大規模グラフ,回路ネットワークにおいてほぼ線形の時間内に高品質のスペクトルスパルサライザを階層的に生成できることを示す。
関連論文リスト
- GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
Graph State Space Network (GrassNet)は、任意のグラフスペクトルフィルタを設計するためのシンプルで効果的なスキームを提供する理論的なサポートを持つ、新しいグラフニューラルネットワークである。
我々の知る限り、我々の研究はグラフGNNスペクトルフィルタの設計にSSMを使った最初のものである。
9つの公開ベンチマークでの大規模な実験により、GrassNetは現実世界のグラフモデリングタスクにおいて優れたパフォーマンスを達成することが明らかになった。
論文 参考訳（メタデータ） (2024-08-16T07:33:58Z) - Spectral Graph Reasoning Network for Hyperspectral Image Classification [0.43512163406551996]
畳み込みニューラルネットワーク(CNN)は、ハイパースペクトル画像(HSI)分類において顕著な性能を達成した。
本稿では、2つの重要なモジュールからなるスペクトルグラフ推論ネットワーク(SGR)学習フレームワークを提案する。
2つのHSIデータセットの実験により、提案したアーキテクチャが分類精度を大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2024-07-02T20:29:23Z) - inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition [4.6193503399184275]
inGRASSは、大きな非方向グラフのインクリメンタルスペクトルスカラー化のために設計された新しいアルゴリズムである。
提案アルゴリズムはスケーラビリティが高く,並列性が高く,セットアップフェーズにほぼ線形時間を要する。
実験では、inGRASSは、同等のソリューション品質を維持しながら、200倍以上のスピードアップを達成する。
論文 参考訳（メタデータ） (2024-02-26T19:49:54Z) - HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
従来の知恵は、スペクトル畳み込みネットワークは無向グラフ上にしか展開できないと規定している。
ここでは、このグラフフーリエ変換への伝統的な依存が超フルであることを示す。
本稿では,新たに開発されたフィルタの周波数応答解釈を行い,フィルタ表現に使用するベースの影響を調査し,ネットワークを基盤とする特性演算子との相互作用について議論する。
論文 参考訳（メタデータ） (2023-10-03T17:42:09Z) - A Sparse Graph Formulation for Efficient Spectral Image Segmentation [0.0]
スペクトルクラスタリングは、セグメンテーション問題を解決する最も伝統的な方法の1つである。
単純なグリッドグラフに余分なノードを含めることで、スパースグラフを定式化します。
元の正規化カットアルゴリズムをこのグラフに適用すると、スペクトル画像セグメンテーションの単純でスケーラブルな方法が導かれる。
論文 参考訳（メタデータ） (2023-06-22T19:06:27Z) - Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。
本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。
複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
論文 参考訳（メタデータ） (2023-03-02T07:36:23Z) - SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements [16.313489255657203]
線形測定による抵抗ネットワーク学習のためのスペクトルグラフ密度化フレームワーク(SGL)
グラフの多重レベルスペクトル近似を利用するソルバフリー法(SF-SGL)。
ベクトルレスパワー/熱的整合性検証のためのEDAアルゴリズム
論文 参考訳（メタデータ） (2023-02-09T00:33:19Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z) - Gaussian Processes on Graphs via Spectral Kernel Learning [9.260186030255081]
グラフのノード上で定義された信号の予測のためのグラフスペクトルに基づくガウス過程を提案する。
合成実験におけるモデルの解釈可能性を示し、様々な基底真理スペクトルフィルタを精度良く回収できることを示す。
論文 参考訳（メタデータ） (2020-06-12T17:51:22Z) - Spectral Graph Attention Network with Fast Eigen-approximation [103.93113062682633]
スペクトルグラフ注意ネットワーク(SpGAT)は、重み付きフィルタとグラフウェーブレットベースに関する異なる周波数成分の表現を学習する。
固有分解による計算コストを削減するために,高速近似変種SpGAT-Chebyを提案する。
半教師付きノード分類タスクにおけるSpGATとSpGAT-Chebyの性能を徹底的に評価する。
論文 参考訳（メタデータ） (2020-03-16T21:49:34Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳（メタデータ） (2020-02-20T09:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。