論文の概要: Hypergraph Clustering Based on PageRank
- arxiv url: http://arxiv.org/abs/2006.08302v1
- Date: Mon, 15 Jun 2020 11:50:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 05:25:20.478807
- Title: Hypergraph Clustering Based on PageRank
- Title(参考訳): PageRankに基づくハイパーグラフクラスタリング
- Authors: Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, Yuichi Yoshida
- Abstract要約: ハイパーグラフは3次関係や高次関係をモデル化するのに有用なオブジェクトである。
ハイパーグラフに基づくパーソナライズされたPageRankに基づく2つのクラスタリングアルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 28.304311692306428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A hypergraph is a useful combinatorial object to model ternary or
higher-order relations among entities. Clustering hypergraphs is a fundamental
task in network analysis. In this study, we develop two clustering algorithms
based on personalized PageRank on hypergraphs. The first one is local in the
sense that its goal is to find a tightly connected vertex set with a bounded
volume including a specified vertex. The second one is global in the sense that
its goal is to find a tightly connected vertex set. For both algorithms, we
discuss theoretical guarantees on the conductance of the output vertex set.
Also, we experimentally demonstrate that our clustering algorithms outperform
existing methods in terms of both the solution quality and running time. To the
best of our knowledge, ours are the first practical algorithms for hypergraphs
with theoretical guarantees on the conductance of the output set.
- Abstract(参考訳): ハイパーグラフは3次あるいは高次関係をモデル化するための有用な組合せオブジェクトである。
クラスタリングハイパーグラフは、ネットワーク分析における基本的なタスクである。
本研究では,ハイパーグラフに基づくパーソナライズされたPageRankに基づく2つのクラスタリングアルゴリズムを提案する。
第一は、特定の頂点を含む有界体積を持つ密連結な頂点集合を見つけることを目的とするという意味で局所的である。
2つ目は、その目的がタイトに連結された頂点集合を見つけることであるという意味で、グローバルである。
両アルゴリズムにおいて,出力頂点集合のコンダクタンスに関する理論的保証について議論する。
また,クラスタリングアルゴリズムは,ソリューションの品質と実行時間の両方において,既存の手法よりも優れていることを示す。
我々の知識を最大限に活用するために、我々は、出力セットのコンダクタンスに関する理論的保証のあるハイパーグラフのための最初の実用的なアルゴリズムである。
関連論文リスト
- Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
この研究はグラフ局所クラスタリングに重点を置いており、様々なモダリティの内部接続性のため、グラフ以外の幅広い応用がある。
非近似型Andersen-Chung-Lang(ACL)アルゴリズムを離散グラフを超えて拡張し、その二次最適性をより広い範囲のグラフに一般化する。
理論的には、2つの穏やかな条件下では、両方のアルゴリズムが少なくとも1/2確率のコンダクタンスの観点から2次最適局所クラスターを識別できることが証明される。
論文 参考訳(メタデータ) (2024-12-04T03:56:14Z) - Hyperedge Modeling in Hypergraph Neural Networks by using Densest Overlapping Subgraphs [0.0]
グラフクラスタリングにおける最も重要な問題の1つは、最も重なり合う部分グラフ(DOS)を見つけることである。
本稿では,最も重なり合う部分グラフを生成するプロセスを改善するための新しいアプローチとして,アグロメラティシオン (DOSAGE) アルゴリズムを用いたDOS問題の解を提案する。
標準ベンチマークの実験では、DOSAGEアルゴリズムはノード分類タスクにおいて、HGNNや他の6つのメソッドよりも大幅に優れていた。
論文 参考訳(メタデータ) (2024-09-16T14:56:10Z) - A classification model based on a population of hypergraphs [0.0]
本稿では,新しいハイパーグラフ分類アルゴリズムを提案する。
ハイパーグラフは任意の順序の多方向相互作用を探索する。
このアルゴリズムは2つのデータセットで評価される。
論文 参考訳(メタデータ) (2024-05-23T21:21:59Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and
Open Resource [87.7460720701592]
本稿では, この分野における公式定義, 評価, 開発について紹介する。
ディープグラフクラスタリング手法の分類は,グラフタイプ,ネットワークアーキテクチャ,学習パラダイム,クラスタリング手法など,4つの異なる基準に基づいて提示される。
コンピュータビジョン、自然言語処理、レコメンデーションシステム、ソーシャルネットワーク分析、バイオインフォマティクス、医学を含む6分野におけるディープグラフクラスタリング手法の適用について述べる。
論文 参考訳(メタデータ) (2022-11-23T11:31:11Z) - Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
グラフニューラルネットワークは、多数のグラフ分類タスクにおいて最先端のパフォーマンスを達成する。
HoscPoolはクラスタリングベースのグラフプーリング演算子で、階層的に高階情報をキャプチャする。
グラフ分類タスクにおいてHoscPoolを評価し,そのクラスタリングコンポーネントを地層構造を持つグラフ上で評価する。
論文 参考訳(メタデータ) (2022-09-02T09:17:10Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳(メタデータ) (2022-01-25T00:10:03Z) - HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
論文 参考訳(メタデータ) (2021-08-17T22:20:23Z) - Learning Spatial Context with Graph Neural Network for Multi-Person Pose
Grouping [71.59494156155309]
イメージベース多人数ポーズ推定のためのボトムアップ手法は,キーポイント検出とグループ化の2段階からなる。
本研究では,グラフ分割問題としてグループ化タスクを定式化し,グラフニューラルネットワーク(gnn)を用いて親和性行列を学習する。
学習された幾何学に基づく親和性は、強固なキーポイント結合を達成するために外観に基づく親和性とさらに融合する。
論文 参考訳(メタデータ) (2021-04-06T09:21:14Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。
提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
論文 参考訳(メタデータ) (2020-04-01T13:39:37Z) - Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
局所化率削減目標の最小化に基づく局所的ハイパーグラフクラスタリングのためのフレームワークを提案する。
我々のアルゴリズムは強局所的であり、その実行は入力セットのサイズにのみ依存し、優れたローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はない。
論文 参考訳(メタデータ) (2020-02-21T17:42:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。