論文の概要: Hypergraph Isomorphism Computation
- arxiv url: http://arxiv.org/abs/2307.14394v1
- Date: Wed, 26 Jul 2023 09:39:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 17:08:32.924580
- Title: Hypergraph Isomorphism Computation
- Title（参考訳）: ハイパーグラフ同型計算
- Authors: Yifan Feng, Jiashu Han, Shihui Ying, Yue Gao
- Abstract要約: Wesfieler-Lehmanカーネルフレームワークを提案し,Hypergraph Weisfeiler-Lehamn Subtree KernelとHypergraph Weisfeiler-Lehamn Hyperedge Kernelの2つの例を実装した。
ハイパーグラフ分類データセットの結果は、他の典型的なカーネルベースの手法と比較して大幅に改善されている。
- 参考スコア（独自算出の注目度）: 20.21325386855039
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The isomorphism problem is a fundamental problem in network analysis, which
involves capturing both low-order and high-order structural information. In
terms of extracting low-order structural information, graph isomorphism
algorithms analyze the structural equivalence to reduce the solver space
dimension, which demonstrates its power in many applications, such as protein
design, chemical pathways, and community detection. For the more commonly
occurring high-order relationships in real-life scenarios, the problem of
hypergraph isomorphism, which effectively captures these high-order structural
relationships, cannot be straightforwardly addressed using graph isomorphism
methods. Besides, the existing hypergraph kernel methods may suffer from high
memory consumption or inaccurate sub-structure identification, thus yielding
sub-optimal performance. In this paper, to address the abovementioned problems,
we first propose the hypergraph Weisfiler-Lehman test algorithm for the
hypergraph isomorphism test problem by generalizing the Weisfiler-Lehman test
algorithm from graphs to hypergraphs. Secondly, based on the presented
algorithm, we propose a general hypergraph Weisfieler-Lehman kernel framework
and implement two instances, which are Hypergraph Weisfeiler-Lehamn Subtree
Kernel and Hypergraph Weisfeiler-Lehamn Hyperedge Kernel. In order to fulfill
our research objectives, a comprehensive set of experiments was meticulously
designed, including seven graph classification datasets and 12 hypergraph
classification datasets. Results on hypergraph classification datasets show
significant improvements compared to other typical kernel-based methods, which
demonstrates the effectiveness of the proposed methods. In our evaluation, we
found that our proposed methods outperform the second-best method in terms of
runtime, running over 80 times faster when handling complex hypergraph
structures.
- Abstract（参考訳）: 同型問題(isomorphism problem)は、低次構造情報と高次構造情報の両方を取り込むネットワーク解析における根本的な問題である。
低次構造情報の抽出に関して、グラフ同型アルゴリズムは、構造同値を解析してソルバ空間次元を減少させ、タンパク質設計、化学経路、コミュニティ検出などの多くの応用においてその威力を示す。
現実のシナリオにおいてより一般的に発生する高次関係に対して、これらの高次構造関係を効果的に捉えているハイパーグラフ同型問題は、グラフ同型法を用いて簡単には解決できない。
さらに、既存のハイパーグラフカーネルメソッドは、高いメモリ消費や不正確なサブ構造識別に苦しむ可能性があるため、サブ最適性能をもたらす。
本稿では,上記の問題に対処するため,ワイスプダー・リーマンテストアルゴリズムをグラフからハイパーグラフに一般化することにより,最初にハイパーグラフ同型テスト問題に対するハイパグラフワイスプダー・リーマンテストアルゴリズムを提案する。
次に,提案手法に基づき,hypergraph weisfeiler-lehmanカーネルフレームワークを提案し,hypergraph weisfeiler-lehamnサブツリーカーネルとhypergraph weisfeiler-lehamnハイパーエッジカーネルの2つのインスタンスを実装した。
研究目的を達成するため、7つのグラフ分類データセットと12のハイパーグラフ分類データセットを含む包括的な実験セットを慎重に設計した。
ハイパーグラフ分類データセットの結果は,提案手法の有効性を示す他のカーネルベース手法と比較して有意な改善を示した。
評価の結果,提案手法は,複雑なハイパーグラフ構造を扱う場合,実行時の80倍以上の速度で実行可能であることがわかった。
関連論文リスト
- A classification model based on a population of hypergraphs [0.0]
本稿では,新しいハイパーグラフ分類アルゴリズムを提案する。
ハイパーグラフは任意の順序の多方向相互作用を探索する。
このアルゴリズムは2つのデータセットで評価される。
論文 参考訳（メタデータ） (2024-05-23T21:21:59Z) - From Graphs to Hypergraphs: Hypergraph Projection and its Remediation [2.0590577326314787]
実世界の相互接続システムを表現するために,ハイパーグラフの代わりにグラフを使用する場合のモデリング選択の意味について検討する。
我々は,ハイパーエッジ分布の重要な統計量に基づく学習に基づくハイパーグラフ再構成手法を開発した。
論文 参考訳（メタデータ） (2024-01-16T17:31:54Z) - 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) - Learning from Heterogeneity: A Dynamic Learning Framework for Hypergraphs [22.64740740462169]
本稿では,動的ハイパーエッジ構築と注意深い埋め込み更新が可能なLFHというハイパーグラフ学習フレームワークを提案する。
提案手法の有効性を評価するため,いくつかの一般的なデータセットを対象とした総合的な実験を行った。
論文 参考訳（メタデータ） (2023-07-07T06:26:44Z) - 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) - Deep Hypergraph Structure Learning [34.972686247703024]
高次相関の学習は、近年、ハイパーグラフが広く使われているデータ表現学習において、優位性を示している。
データ間のハイパーグラフ構造の生成方法はまだ難しい課題です。
DeepHGSLはハイパーグラフに基づく表現学習のためのハイパーグラフ構造を最適化するために設計されている。
論文 参考訳（メタデータ） (2022-08-26T10:00:11Z) - 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) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。