論文の概要: Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality

• arxiv url: http://arxiv.org/abs/2411.03331v1
• Date: Wed, 23 Oct 2024 05:16:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 12:02:09.247543
• Title: Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
• Title（参考訳）: 重み付き自己ループグラフとしてのハイパーグラフ:スペクトル特性、クラスタリング、チーガー不等式
• Authors: Zihao Li, Dongqi Fu, Hengyu Liu, Jingrui He,
• Abstract要約: ハイパーグラフはグループ関係を研究するときに現れ、機械学習の分野で広く使われている。 ハイパーグラフの統一的な定式化は行われていないが、最近提案されたエッジ依存レイリー重み付け(EDVW)モデリングは、ハイパーグラフの最も一般化されたモデリング手法の1つである。 グラフ上の対応する定義と整合性を持つハイパーグラフQuotient, NCut, boundary/cut, volume, and conductance の定義を提案する。 そして、正規化されたハイパーグラフラプラシアンがNCut値と関連があることを証明し、スペクトルクラスタリングのためのHyperClus-Gアルゴリズムを刺激する。
• 参考スコア（独自算出の注目度）: 40.215737469808026
• License:
• Abstract: Hypergraphs naturally arise when studying group relations and have been widely used in the field of machine learning. There has not been a unified formulation of hypergraphs, yet the recently proposed edge-dependent vertex weights (EDVW) modeling is one of the most generalized modeling methods of hypergraphs, i.e., most existing hypergraphs can be formulated as EDVW hypergraphs without any information loss to the best of our knowledge. However, the relevant algorithmic developments on EDVW hypergraphs remain nascent: compared to spectral graph theories, the formulations are incomplete, the spectral clustering algorithms are not well-developed, and one result regarding hypergraph Cheeger Inequality is even incorrect. To this end, deriving a unified random walk-based formulation, we propose our definitions of hypergraph Rayleigh Quotient, NCut, boundary/cut, volume, and conductance, which are consistent with the corresponding definitions on graphs. Then, we prove that the normalized hypergraph Laplacian is associated with the NCut value, which inspires our HyperClus-G algorithm for spectral clustering on EDVW hypergraphs. Finally, we prove that HyperClus-G can always find an approximately linearly optimal partitioning in terms of Both NCut and conductance. Additionally, we provide extensive experiments to validate our theoretical findings from an empirical perspective.
• Abstract（参考訳）: ハイパーグラフはグループ関係を研究するときに自然に現れ、機械学習の分野で広く使われている。 ハイパーグラフの統一的な定式化は行われていないが、最近提案されたエッジ依存頂点重み付け(EDVW)モデリングは、ハイパーグラフの最も一般化されたモデリング手法の1つである。 しかし、EDVWハイパーグラフに関する関連するアルゴリズム開発は、スペクトルグラフ理論と比較すると、定式化は不完全であり、スペクトルクラスタリングアルゴリズムは十分に開発されておらず、ハイパーグラフチェーガー不等式に関する一つの結果が誤りである。 この目的のために、統一されたランダムウォークに基づく定式化を導出し、グラフ上の対応する定義と一致するハイパーグラフRayleigh Quotient, NCut, boundary/cut, volume, and conductance の定義を提案する。 次に、正規化ハイパーグラフラプラシアンは、EDVWハイパーグラフ上のスペクトルクラスタリングのためのHyperClus-Gアルゴリズムに刺激を与えるNCut値と関連があることを証明した。 最後に、HyperClus-GがNCutとコンダクタンスの両方の観点から、ほぼ線形に最適なパーティショニングを見つけることができることを証明した。 さらに,実証的な観点から理論的な知見を検証するための広範な実験を行った。

関連論文リスト

• Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
  我々は新しいハイパーグラフ学習フレームワークHyperGraph Transformer(HyperGT)を提案する。 HyperGTはTransformerベースのニューラルネットワークアーキテクチャを使用して、すべてのノードとハイパーエッジのグローバル相関を効果的に検討する。 局所接続パターンを保ちながら、グローバルな相互作用を効果的に組み込むことで、包括的なハイパーグラフ表現学習を実現する。
  論文  参考訳（メタデータ） (2023-12-18T17:50:52Z)
• Hypergraph Structure Inference From Data Under Smoothness Prior [46.568839316694515]
  本稿では,ラベル付きデータを監視対象とせずに,潜在的なハイパーエッジの確率を推定する手法を提案する。 本稿では,この手法を用いてハイパーグラフ構造とノード特徴の関係を確率論的モデリングにより導出する。 本手法は,既存のハイパーグラフ構造推定法よりも効率的にデータから有意義なハイパーグラフ構造を学習できることを示す。
  論文  参考訳（メタデータ） (2023-08-27T18:28:58Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。 次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。 提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
  論文  参考訳（メタデータ） (2023-06-16T04:40:59Z)
• Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering [29.400924845055865]
  エッジ依存重み(EDVW)を組み込んだ最近提案されたハイパーグラフモデルのp-ラプラシアンおよびスペクトルクラスタリングについて検討する。 我々は、ハイパーグラフをEDVWで変換し、スペクトル理論がより発展する部分モジュラーハイパーグラフに変換する。 p-ラプラシアンやチェーガーの不等式のような既存の概念や定理は、部分モジュラーハイパーグラフ設定の下で提案され、EDVWでハイパーグラフへ直接拡張することができる。
  論文  参考訳（メタデータ） (2022-08-15T22:29:00Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。 本稿では,提案するフレームワークが最先端の性能を達成できることを示す。 ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
  論文  参考訳（メタデータ） (2022-03-31T10:46:47Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。 提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
  論文  参考訳（メタデータ） (2021-08-17T22:20:23Z)
• Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
  異質なノード度とエッジサイズを持つクラスタ化ハイパーグラフの表現的生成モデルを提案する。 我々は,100万ノードの合成ハイパーグラフを用いた実験など,ハイパーグラフ・ルーバインは高度にスケーラブルであることを示す。 このモデルを用いて,学校連絡ネットワークにおける高次構造の異なるパターン,米国議会法案共同提案,米国議会委員会,共同購入行動における製品カテゴリ,ホテルロケーションを分析した。
  論文  参考訳（メタデータ） (2021-01-24T00:25:22Z)
• Hypergraph Partitioning using Tensor Eigenvalue Decomposition [19.01626581411011]
  我々は、k-ユニフォームハイパーグラフの分割のための新しいアプローチを提案する。 既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用することで機能する。 我々は、テンソルベースのハイパーグラフ表現を利用することでこの問題を克服する。
  論文  参考訳（メタデータ） (2020-11-16T01:55:43Z)
• HNHN: Hypergraph Networks with Hyperedge Neurons [90.15253035487314]
  HNHNはハイパーグラフ畳み込みネットワークであり、ハイパーノードとハイパーエッジの両方に非線形活性化関数が適用される。 実世界のデータセットの分類精度と速度の両面でのHNHNの性能向上を示す。
  論文  参考訳（メタデータ） (2020-06-22T14:08:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。