論文の概要: HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
- arxiv url: http://arxiv.org/abs/2108.07901v1
- Date: Tue, 17 Aug 2021 22:20:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-19 14:34:39.153881
- Title: HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
- Title（参考訳）: HyperSF: フローベースの局所クラスタリングによるスペクトルハイパーグラフの粗大化
- Authors: Ali Aghdaei, Zhiqiang Zhao, Zhuo Feng
- Abstract要約: 本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
- 参考スコア（独自算出の注目度）: 9.438207505148947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hypergraphs allow modeling problems with multi-way high-order relationships.
However, the computational cost of most existing hypergraph-based algorithms
can be heavily dependent upon the input hypergraph sizes. To address the
ever-increasing computational challenges, graph coarsening can be potentially
applied for preprocessing a given hypergraph by aggressively aggregating its
vertices (nodes). However, state-of-the-art hypergraph partitioning
(clustering) methods that incorporate heuristic graph coarsening techniques are
not optimized for preserving the structural (global) properties of hypergraphs.
In this work, we propose an efficient spectral hypergraph coarsening scheme
(HyperSF) for well preserving the original spectral (structural) properties of
hypergraphs. Our approach leverages a recent strongly-local max-flow-based
clustering algorithm for detecting the sets of hypergraph vertices that
minimize ratio cut. To further improve the algorithm efficiency, we propose a
divide-and-conquer scheme by leveraging spectral clustering of the bipartite
graphs corresponding to the original hypergraphs. Our experimental results for
a variety of hypergraphs extracted from real-world VLSI design benchmarks show
that the proposed hypergraph coarsening algorithm can significantly improve the
multi-way conductance of hypergraph clustering as well as runtime efficiency
when compared with existing state-of-the-art algorithms.
- Abstract（参考訳）: ハイパーグラフは、多方向高次関係のモデリング問題を可能にする。
しかし、既存のハイパーグラフベースのアルゴリズムの計算コストは入力ハイパーグラフサイズに大きく依存する。
計算上の課題の増大に対処するために、グラフ粗さは頂点(ノード)を積極的に集約することで、与えられたハイパーグラフの前処理に応用できる可能性がある。
しかし、ヒューリスティックグラフ粗化手法を取り入れた最先端のハイパーグラフ分割(クラスタリング)法は、ハイパーグラフの構造(グローバル)特性の保存に最適化されていない。
本研究では,ハイパーグラフのスペクトル(構造)特性を適切に保存するための効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は, 局所的な最大フローに基づくクラスタリングアルゴリズムを用いて, 比カットを最小限に抑えるハイパーグラフ頂点の集合を検出する。
アルゴリズムの効率をさらに高めるために,元のハイパーグラフに対応する二部グラフのスペクトルクラスタリングを利用する分割・対数方式を提案する。
実世界のVLSI設計ベンチマークから抽出した様々なハイパーグラフの実験結果から,提案したハイパーグラフ粗大化アルゴリズムは,既存の最先端アルゴリズムと比較して,ハイパーグラフクラスタリングのマルチウェイコンダクタンスと実行効率を著しく向上させることができることが示された。
関連論文リスト
- SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning [4.110108749051657]
大規模ハイパーグラフのためのマルチレベルスペクトルフレームワークSHyParを導入し,ハイパーエッジ有効抵抗とフローベースコミュニティ検出技術を利用した。
SHyParの鍵となるコンポーネントは、ハイパーグラフ粗化のためのフローベースの局所クラスタリングスキームであり、最大フローベースのアルゴリズムを組み込んで、コンダクタンスを大幅に改善したノードを生成する。
論文 参考訳（メタデータ） (2024-10-09T03:29:47Z) - Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
我々は新しいハイパーグラフ学習フレームワークHyperGraph Transformer(HyperGT)を提案する。
HyperGTはTransformerベースのニューラルネットワークアーキテクチャを使用して、すべてのノードとハイパーエッジのグローバル相関を効果的に検討する。
局所接続パターンを保ちながら、グローバルな相互作用を効果的に組み込むことで、包括的なハイパーグラフ表現学習を実現する。
論文 参考訳（メタデータ） (2023-12-18T17:50:52Z) - Hypergraph Isomorphism Computation [20.21325386855039]
Wesfieler-Lehmanカーネルフレームワークを提案し,Hypergraph Weisfeiler-Lehamn Subtree KernelとHypergraph Weisfeiler-Lehamn Hyperedge Kernelの2つの例を実装した。
ハイパーグラフ分類データセットの結果は、他の典型的なカーネルベースの手法と比較して大幅に改善されている。
論文 参考訳（メタデータ） (2023-07-26T09:39:40Z) - From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。
次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。
提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
論文 参考訳（メタデータ） (2023-06-16T04:40:59Z) - Tensorized Hypergraph Neural Networks [69.65385474777031]
我々は,新しいアジャケーシテンソルベースのtextbfTensorized textbfHypergraph textbfNeural textbfNetwork (THNN) を提案する。
THNNは高次外装機能パッシングメッセージを通じて、忠実なハイパーグラフモデリングフレームワークである。
3次元視覚オブジェクト分類のための2つの広く使われているハイパーグラフデータセットの実験結果から、モデルの有望な性能を示す。
論文 参考訳（メタデータ） (2023-06-05T03:26:06Z) - Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and
Spectral Clustering [29.400924845055865]
エッジ依存重み(EDVW)を組み込んだ最近提案されたハイパーグラフモデルのp-ラプラシアンおよびスペクトルクラスタリングについて検討する。
我々は、ハイパーグラフをEDVWで変換し、スペクトル理論がより発展する部分モジュラーハイパーグラフに変換する。
p-ラプラシアンやチェーガーの不等式のような既存の概念や定理は、部分モジュラーハイパーグラフ設定の下で提案され、EDVWでハイパーグラフへ直接拡張することができる。
論文 参考訳（メタデータ） (2022-08-15T22:29:00Z) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。
本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-27T01:14:06Z) - Hypergraph Convolutional Networks via Equivalency between Hypergraphs
and Undirected Graphs [59.71134113268709]
本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。
本稿では,提案するフレームワークが最先端の性能を達成できることを示す。
ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
論文 参考訳（メタデータ） (2022-03-31T10:46:47Z) - Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。
提案されたSSCAGは最先端のアプローチと競合する。
論文 参考訳（メタデータ） (2021-04-24T08:09:27Z) - Hypergraph Partitioning using Tensor Eigenvalue Decomposition [19.01626581411011]
我々は、k-ユニフォームハイパーグラフの分割のための新しいアプローチを提案する。
既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用することで機能する。
我々は、テンソルベースのハイパーグラフ表現を利用することでこの問題を克服する。
論文 参考訳（メタデータ） (2020-11-16T01:55:43Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。