論文の概要: Local Motif Clustering via (Hyper)Graph Partitioning

• arxiv url: http://arxiv.org/abs/2205.06176v1
• Date: Wed, 11 May 2022 12:16:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-13 14:25:03.380494
• Title: Local Motif Clustering via (Hyper)Graph Partitioning
• Title（参考訳）: ハイパーグラフ分割による局所モチーフクラスタリング
• Authors: Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz
• Abstract要約: 我々は,シードノード周辺のモチーフ分布を表すハイパーグラフとグラフモデルを構築した。 我々は、(ハイパー)グラフ用に設計された洗練されたアルゴリズムを用いて、これらのモデルを解く。 提案アルゴリズムは,最先端ツールMAPPRによって計算されたコミュニティと比較して,平均で3分の1のモチーフコンダクタンス値を持つコミュニティを演算する。
• 参考スコア（独自算出の注目度）: 1.9121961872220465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A widely-used operation on graphs is local clustering, i.e., extracting a well-characterized community around a seed node without the need to process the whole graph. Recently local motif clustering has been proposed: it looks for a local cluster based on the distribution of motifs. Since this local clustering perspective is relatively new, most approaches proposed for it are extensions of statistical and numerical methods previously used for edge-based local clustering, while the available combinatorial approaches are still few and relatively simple. In this work, we build a hypergraph and a graph model which both represent the motif-distribution around the seed node. We solve these models using sophisticated combinatorial algorithms designed for (hyper)graph partitioning. In extensive experiments with the triangle motif, we observe that our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR while being 6.3 times faster on average.
• Abstract（参考訳）: グラフ上で広く使われている操作は局所クラスタリングである。すなわち、グラフ全体を処理することなく、シードノード周辺のよく特性化されたコミュニティを抽出する。 近年,局所的モチーフクラスタリングが提案されている。モチーフの分布に基づく局所クラスタを探索する。 この局所クラスタリングの観点は比較的新しいため、これまでエッジベースの局所クラスタリングに用いられてきた統計的および数値的手法の拡張が提案されている。 本研究では,シードノード周辺のモチーフ分布を表現するハイパーグラフとグラフモデルを構築した。 グラフ分割のための高度な組合せアルゴリズムを用いてこれらのモデルを解く。 トライアングルモチーフを用いた広範囲な実験において、我々のアルゴリズムは平均3分の1のモチーフコンダクタンス値でコミュニティを計算し、最先端ツールMAPPRが計算したコミュニティと比較して平均6.3倍高速である。

関連論文リスト

• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。 我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。 本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
  論文  参考訳（メタデータ） (2023-12-07T06:19:39Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• 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)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。 フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
  論文  参考訳（メタデータ） (2022-03-02T20:07:04Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。 nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
  論文  参考訳（メタデータ） (2020-04-25T17:52:05Z)
• Incorporating User's Preference into Attributed Graph Clustering [14.082520165369885]
  局所クラスタに対して,グラフ一様性(GU)と属性一様性(AU)の2つの品質尺度を提案する。 LOCLUによって検出された局所クラスタは、関心領域に集中し、グラフ内の効率的な情報フローを提供し、指定された属性のサブ空間に一様データ分布を示す。
  論文  参考訳（メタデータ） (2020-03-24T19:07:22Z)
• Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
  局所化率削減目標の最小化に基づく局所的ハイパーグラフクラスタリングのためのフレームワークを提案する。 我々のアルゴリズムは強局所的であり、その実行は入力セットのサイズにのみ依存し、優れたローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はない。
  論文  参考訳（メタデータ） (2020-02-21T17:42:22Z)

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

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