論文の概要: Hypergraph Partitioning using Tensor Eigenvalue Decomposition
- arxiv url: http://arxiv.org/abs/2011.07683v1
- Date: Mon, 16 Nov 2020 01:55:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 23:40:25.691113
- Title: Hypergraph Partitioning using Tensor Eigenvalue Decomposition
- Title（参考訳）: テンソル固有値分解を用いたハイパーグラフ分割
- Authors: Deepak Maurya and Balaraman Ravindran
- Abstract要約: 我々は、k-ユニフォームハイパーグラフの分割のための新しいアプローチを提案する。
既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用することで機能する。
我々は、テンソルベースのハイパーグラフ表現を利用することでこの問題を克服する。
- 参考スコア（独自算出の注目度）: 19.01626581411011
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hypergraphs have gained increasing attention in the machine learning
community lately due to their superiority over graphs in capturing super-dyadic
interactions among entities. In this work, we propose a novel approach for the
partitioning of k-uniform hypergraphs. Most of the existing methods work by
reducing the hypergraph to a graph followed by applying standard graph
partitioning algorithms. The reduction step restricts the algorithms to
capturing only some weighted pairwise interactions and hence loses essential
information about the original hypergraph. We overcome this issue by utilizing
the tensor-based representation of hypergraphs, which enables us to capture
actual super-dyadic interactions. We prove that the hypergraph to graph
reduction is a special case of tensor contraction. We extend the notion of
minimum ratio-cut and normalized-cut from graphs to hypergraphs and show the
relaxed optimization problem is equivalent to tensor eigenvalue decomposition.
This novel formulation also enables us to capture different ways of cutting a
hyperedge, unlike the existing reduction approaches. We propose a hypergraph
partitioning algorithm inspired from spectral graph theory that can accommodate
this notion of hyperedge cuts. We also derive a tighter upper bound on the
minimum positive eigenvalue of even-order hypergraph Laplacian tensor in terms
of its conductance, which is utilized in the partitioning algorithm to
approximate the normalized cut. The efficacy of the proposed method is
demonstrated numerically on simple hypergraphs. We also show improvement for
the min-cut solution on 2-uniform hypergraphs (graphs) over the standard
spectral partitioning algorithm.
- Abstract（参考訳）: 最近、ハイパーグラフは、エンティティ間の超動的相互作用をキャプチャするグラフよりも優れているため、機械学習コミュニティで注目を集めている。
本稿では,k-一様超グラフの分割に対する新しいアプローチを提案する。
既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用する。
削減ステップでは、アルゴリズムが重み付けされた対の相互作用のみをキャプチャすることを制限するため、元のハイパーグラフに関する必須情報を失う。
我々は、テンソルに基づくハイパーグラフの表現を利用してこの問題を克服し、実際の超動的相互作用をキャプチャする。
グラフ縮小へのハイパーグラフはテンソル収縮の特別な場合であることを示す。
最小比カットと正規化カットの概念をグラフからハイパーグラフに拡張し、緩和最適化問題はテンソル固有値分解と同値であることを示す。
この新規な定式化により、既存の還元アプローチとは異なり、ハイパーエッジの切断方法も異なっています。
スペクトルグラフ理論から着想を得たハイパーグラフ分割アルゴリズムを提案する。
また、等階超グラフラプラシアンテンソルの最小正の固有値に対して、その導電率の観点からより強い上限を導出し、分割アルゴリズムを用いて正規化カットを近似する。
提案手法の有効性を簡単なハイパーグラフで数値的に示す。
また、標準的なスペクトル分割アルゴリズムよりも2ユニフォームハイパーグラフ(グラフ)上でのmin-cutソリューションの改善を示す。
関連論文リスト
- Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality [40.215737469808026]
ハイパーグラフはグループ関係を研究するときに現れ、機械学習の分野で広く使われている。
ハイパーグラフの統一的な定式化は行われていないが、最近提案されたエッジ依存レイリー重み付け(EDVW)モデリングは、ハイパーグラフの最も一般化されたモデリング手法の1つである。
グラフ上の対応する定義と整合性を持つハイパーグラフQuotient, NCut, boundary/cut, volume, and conductance の定義を提案する。
そして、正規化されたハイパーグラフラプラシアンがNCut値と関連があることを証明し、スペクトルクラスタリングのためのHyperClus-Gアルゴリズムを刺激する。
論文 参考訳（メタデータ） (2024-10-23T05:16:48Z) - 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) - Graphon Pooling for Reducing Dimensionality of Signals and Convolutional
Operators on Graphs [131.53471236405628]
グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。
これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。
我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
論文 参考訳（メタデータ） (2022-12-15T22:11:34Z) - Hypergraph Convolutional Networks via Equivalency between Hypergraphs
and Undirected Graphs [59.71134113268709]
本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。
本稿では,提案するフレームワークが最先端の性能を達成できることを示す。
ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
論文 参考訳（メタデータ） (2022-03-31T10:46:47Z) - Love tHy Neighbour: Remeasuring Local Structural Node Similarity in
Hypergraph-Derived Networks [2.246222223318928]
ノードペア間のハイパーグラフ指向の類似度スコアを複数提案する。
グラフトポロジーに基づくスコアをハイパーグラフに拡張するための理論的定式化を提供する。
論文 参考訳（メタデータ） (2021-10-30T14:12:58Z) - HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2021-08-17T22:20:23Z) - Hypergraph Dissimilarity Measures [8.890638003061605]
本稿では,ハイパーグラフの相似性を特定のスケールで評価したり,より総合的なマルチスケール比較を行う手法を提案する。
合成ハイパーグラフ上でこれらの測定を検証し,生物学的データセットに適用する。
論文 参考訳（メタデータ） (2021-06-15T15:10:24Z) - Hyperedge Prediction using Tensor Eigenvalue Decomposition [21.673771194165276]
グラフにおけるリンク予測は、2つのノード間のダイアディック相互作用をモデル化することによって研究される。
このような相互作用はハイパーグラフを用いてモデル化することができ、これはハイパーエッジが2つ以上のノードを接続できるグラフの一般化である。
テンソルに基づくハイパーグラフの表現を利用し、テンソル固有ベクトルの新しい解釈を提案する。
論文 参考訳（メタデータ） (2021-02-06T01:55:04Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。