論文の概要: 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倍高速である。
関連論文リスト
- Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳(メタデータ) (2022-03-02T20:07:04Z) - Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
GRCCAと呼ばれるクラスタ割り当てを対比して、教師なしグラフ表現モデルを提案する。
クラスタリングアルゴリズムとコントラスト学習を組み合わせることで、局所的およびグローバルな情報を合成的にうまく活用する動機付けがある。
GRCCAは、ほとんどのタスクにおいて強力な競争力を持っている。
論文 参考訳(メタデータ) (2021-12-15T07:28:58Z) - Robust Correlation Clustering with Asymmetric Noise [3.8073142980733]
相関クラスタリング(英語版)はグラフクラスタリングの定式化であり、(1) ノード間の類似性/異性度を示すエッジウェイトを持つ符号付きグラフを入力とし、(2) 入力グラフ内のクラスタ数を事前に見積もる必要がない。
グラフノードの特徴ベクトル/埋め込みの生成に基づく新しいグラフ生成モデルNode Factors Model (NFM)を提案する。
論文 参考訳(メタデータ) (2021-10-15T21:47:27Z) - Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。
SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。
OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
論文 参考訳(メタデータ) (2021-10-15T03:25:28Z) - Git: Clustering Based on Graph of Intensity Topology [25.679620842010422]
我々は、新しいクラスタリングアルゴリズムGIT(textbfIntensity textbfTopologyのtextbfGraphに基づくクラスタリング)を提案する。
高速な局所クラスタ検出、堅牢なトポグラフの構築、エッジカットにより、GITは魅力的なARISE性能を示す。
論文 参考訳(メタデータ) (2021-10-04T09:29:43Z) - Learning Hierarchical Graph Neural Networks for Image Clustering [81.5841862489509]
本稿では,画像の集合を未知の個数にクラスタリングする方法を学ぶ階層型グラフニューラルネットワーク(GNN)モデルを提案する。
我々の階層的なGNNは、階層の各レベルで予測される連結コンポーネントをマージして、次のレベルで新しいグラフを形成するために、新しいアプローチを用いています。
論文 参考訳(メタデータ) (2021-07-03T01:28:42Z) - Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。
提案されたSSCAGは最先端のアプローチと競合する。
論文 参考訳(メタデータ) (2021-04-24T08:09:27Z) - Graph Contrastive Clustering [131.67881457114316]
本稿では,クラスタリングタスクに適用可能な新しいグラフコントラスト学習フレームワークを提案し,gcc(graph constrastive clustering)法を考案した。
特に、グラフラプラシアンに基づくコントラスト損失は、より識別的かつクラスタリングフレンドリーな特徴を学ぶために提案されている。
一方で、よりコンパクトなクラスタリング割り当てを学ぶために、グラフベースのコントラスト学習戦略が提案されている。
論文 参考訳(メタデータ) (2021-04-03T15:32:49Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳(メタデータ) (2021-03-25T09:31:41Z) - Structured Graph Learning for Scalable Subspace Clustering: From
Single-view to Multi-view [28.779909990410978]
グラフベースのサブスペースクラスタリング手法は有望な性能を示した。
コストのかかる時間のオーバーヘッドに遭遇し、明示的なクラスタの探索に失敗し、見えないデータポイントに一般化することはできません。
上記の3つの課題を同時に解決しようとする,スケーラブルなグラフ学習フレームワークを提案する。
論文 参考訳(メタデータ) (2021-02-16T03:46:11Z) - Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural
Networks [24.017988997693262]
ノードとノードのクラスタメンバーシップ間の接続が時間とともに変化する可能性がある動的グラフにおけるノードのクラスタリングの問題を検討する。
まず,ノード間の重み付き接続に基づいてノードをクラスタ化し,その重みが時間とともに一定速度で減少する,簡易な崩壊ベースのクラスタリングアルゴリズムを提案する。
本稿では,各クラスタの最適減衰率を特徴付け,真のクラスタのほぼ完全回復を実現するクラスタリング手法を提案する。
論文 参考訳(メタデータ) (2020-12-16T04:31:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。