論文の概要: Minimizing Localized Ratio Cut Objectives in Hypergraphs
- arxiv url: http://arxiv.org/abs/2002.09441v2
- Date: Wed, 1 Jul 2020 02:48:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 01:55:25.585607
- Title: Minimizing Localized Ratio Cut Objectives in Hypergraphs
- Title（参考訳）: ハイパーグラフにおける局所的切断対象の最小化
- Authors: Nate Veldt and Austin R. Benson and Jon Kleinberg
- Abstract要約: 局所化率削減目標の最小化に基づく局所的ハイパーグラフクラスタリングのためのフレームワークを提案する。
我々のアルゴリズムは強局所的であり、その実行は入力セットのサイズにのみ依存し、優れたローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はない。
- 参考スコア（独自算出の注目度）: 32.80813008862995
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hypergraphs are a useful abstraction for modeling multiway relationships in
data, and hypergraph clustering is the task of detecting groups of closely
related nodes in such data. Graph clustering has been studied extensively, and
there are numerous methods for detecting small, localized clusters without
having to explore an entire input graph. However, there are only a few
specialized approaches for localized clustering in hypergraphs. Here we present
a framework for local hypergraph clustering based on minimizing localized ratio
cut objectives. Our framework takes an input set of reference nodes in a
hypergraph and solves a sequence of hypergraph minimum $s$-$t$ cut problems in
order to identify a nearby well-connected cluster of nodes that overlaps
substantially with the input set.
Our methods extend graph-based techniques but are significantly more general
and have new output quality guarantees. First, our methods can minimize new
generalized notions of hypergraph cuts, which depend on specific configurations
of nodes within each hyperedge, rather than just on the number of cut
hyperedges. Second, our framework has several attractive theoretical properties
in terms of output cluster quality. Most importantly, our algorithm is
strongly-local, meaning that its runtime depends only on the size of the input
set, and does not need to explore the entire hypergraph to find good local
clusters. We use our methodology to effectively identify clusters in
hypergraphs of real-world data with millions of nodes, millions of hyperedges,
and large average hyperedge size with runtimes ranging between a few seconds
and a few minutes.
- Abstract（参考訳）: ハイパーグラフはデータのマルチウェイ関係をモデル化するのに有用な抽象化であり、ハイパーグラフクラスタリングは、データ内の密接に関連するノードのグループを検出するタスクである。
グラフクラスタリングは広く研究されており、入力グラフ全体を探索することなく、小さな局所クラスタを検出する方法は数多く存在する。
しかし、ハイパーグラフの局所化クラスタリングには特別なアプローチがいくつかある。
本稿では,局所化比カット目標の最小化に基づく局所ハイパーグラフクラスタリングの枠組みを提案する。
我々のフレームワークはハイパーグラフ内の参照ノードの入力集合を取り、ハイパーグラフの最小値$s$-$t$の切断問題を解くことで、入力集合とほぼ重なる近隣のよく接続されたノードのクラスタを特定する。
提案手法はグラフベースの手法を拡張するが,より汎用的で,新たな出力品質保証を備えている。
まず,切削されたハイパーエッジの数ではなく,各ハイパーエッジ内のノードの特定の構成に依存するハイパーグラフ切断の新たな一般化概念を最小化することができる。
第二に、我々のフレームワークは、出力クラスタの品質の観点から、いくつかの魅力的な理論的特性を持っています。
最も重要なのは、アルゴリズムが強くローカルであることです。つまり、ランタイムは入力セットのサイズのみに依存しており、よいローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はありません。
我々の手法は,数百万のノードと数百万のハイパーエッジを持つ実世界のデータのハイパーグラフ内のクラスタを効果的に識別するために用いられる。
関連論文リスト
- 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) - DGCLUSTER: A Neural Framework for Attributed Graph Clustering via
Modularity Maximization [5.329981192545312]
本稿では,グラフニューラルネットワークを用いてモジュラリティの目的を最適化し,グラフサイズと線形にスケールする新しい手法DGClusterを提案する。
私たちはDGClusterを、さまざまなサイズの実世界のデータセットで、複数の一般的なクラスタ品質メトリクスで広範囲にテストしています。
われわれの手法は最先端の手法よりも一貫して優れており、ほぼすべての設定で顕著な性能向上を示している。
論文 参考訳（メタデータ） (2023-12-20T01:43:55Z) - Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
我々は新しいハイパーグラフ学習フレームワークHyperGraph Transformer(HyperGT)を提案する。
HyperGTはTransformerベースのニューラルネットワークアーキテクチャを使用して、すべてのノードとハイパーエッジのグローバル相関を効果的に検討する。
局所接続パターンを保ちながら、グローバルな相互作用を効果的に組み込むことで、包括的なハイパーグラフ表現学習を実現する。
論文 参考訳（メタデータ） (2023-12-18T17:50:52Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - BOURNE: Bootstrapped Self-supervised Learning Framework for Unified
Graph Anomaly Detection [50.26074811655596]
自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。
ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。
BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
論文 参考訳（メタデータ） (2023-07-28T00:44:57Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳（メタデータ） (2023-05-28T15:33:24Z) - Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。
SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。
OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
論文 参考訳（メタデータ） (2021-10-15T03:25:28Z) - HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2021-08-17T22:20:23Z) - Community Detection in General Hypergraph via Graph Embedding [1.4213973379473654]
本研究では,一般のハイパーグラフネットワーク,均一あるいは非均一なコミュニティ構造を検出する新しい方法を提案する。
提案手法では,非一様ハイパーグラフを均一なマルチハイパーグラフに拡張するヌルを導入し,低次元ベクトル空間にマルチハイパーグラフを埋め込む。
論文 参考訳（メタデータ） (2021-03-28T03:23:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。