論文の概要: Clustering for directed graphs using parametrized random walk diffusion kernels

• arxiv url: http://arxiv.org/abs/2210.00310v1
• Date: Sat, 1 Oct 2022 16:13:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 13:56:38.171137
• Title: Clustering for directed graphs using parametrized random walk diffusion kernels
• Title（参考訳）: パラメータ付きランダムウォーク拡散核を用いた有向グラフのクラスタリング
• Authors: Harry Sevi, Matthieu Jonckheere, Argyris Kalogeratos
• Abstract要約: 我々は,P-RWDKC(Parametrized Random Walk Diffusion Kernel Clustering)という新しいクラスタリングフレームワークを導入する。 我々のフレームワークは拡散幾何学と一般化スペクトルクラスタリングフレームワークに基づいている。 実世界のデータセットと実世界のグラフから構築した$K$-NNグラフの実験は、我々のクラスタリングアプローチがすべてのテストケースでうまく機能していることを示しています。
• 参考スコア（独自算出の注目度）: 5.145741425164946
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering based on the random walk operator has been proven effective for undirected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defined for digraphs, in most cases such graphs are not strongly connected, and hence the associated random walks are not irreducible, which is a crucial property for clustering that exists naturally in the undirected setting. To remedy this, the usual workaround is to either naively symmetrize the adjacency matrix or to replace the natural random walk operator by the teleporting random walk operator, but this can lead to the loss of valuable information carried by edge directionality. In this paper, we introduce a new clustering framework, the Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC), which is suitable for handling both directed and undirected graphs. Our framework is based on the diffusion geometry and the generalized spectral clustering framework. Accordingly, we propose an algorithm that automatically reveals the cluster structure at a given scale, by considering the random walk dynamics associated with a parametrized kernel operator, and by estimating its critical diffusion time. Experiments on $K$-NN graphs constructed from real-world datasets and real-world graphs show that our clustering approach performs well in all tested cases, and outperforms existing approaches in most of them.
• Abstract（参考訳）: ランダムウォーク演算子に基づくクラスタリングは、無向グラフに対して有効であることが証明されているが、有向グラフへの一般化はより困難である。 ランダムウォーク作用素はグラフに対してよく定義されているが、ほとんどの場合、そのようなグラフは強く連結されていないので、関連するランダムウォークは既約ではない。 これに対処するために、通常の回避策は、隣接行列をネイティブに対称性化するか、自然ランダムウォーク演算子をテレポーティングランダムウォーク演算子に置き換えるかのどちらかであるが、これはエッジ方向性によって運ばれる貴重な情報を失う可能性がある。 本稿では,有向グラフと無向グラフの両方を扱うのに適した新しいクラスタリングフレームワークであるパラメータ付きランダムウォーク拡散カーネルクラスタリング(p-rwdkc)を提案する。 我々のフレームワークは拡散幾何学と一般化スペクトルクラスタリングフレームワークに基づいている。 そこで,パラメトリズドカーネル演算子に付随するランダムウォークダイナミクスを考慮し,その臨界拡散時間を推定することにより,クラスタ構造を所定のスケールで自動的に明らかにするアルゴリズムを提案する。 実世界のデータセットと実世界のグラフから構築された$K$-NNグラフの実験は、クラスタリングアプローチがすべてのテストケースで良好に機能し、既存のアプローチよりも優れていることを示している。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [78.22249047957939]
  アンカーグラフの分解に基づくマルチビュークラスタリング法では,分解行列に対する適切なクラスタ解釈性が欠如している。 複数のビューからアンカーグラフを合成するアンカーグラフテンソルを分解するために、非負のテンソル因子分解を用いることにより、この制限に対処する。
  論文  参考訳（メタデータ） (2024-04-01T03:23:55Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
  本稿では、有向グラフと無向グラフの両方に対処できる一般化スペクトルクラスタリングフレームワークを提案する。 我々のアプローチは、グラフ関数の一般化されたディリクレエネルギーとして導入する新しい函数のスペクトル緩和に基づいている。 また、グラフ上の自然ランダムウォークの反復パワーから構築された正規化尺度の実用的なパラメトリゼーションを提案する。
  論文  参考訳（メタデータ） (2022-03-07T09:18:42Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。 フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
  論文  参考訳（メタデータ） (2022-03-02T20:07:04Z)
• Private Weighted Random Walk Stochastic Gradient Descent [21.23973736418492]
  グラフ内のノードに分散したデータを分散する分散学習環境を考える。 本稿では,データの一様サンプリングと重要サンプリングという2種類のランダムウォークに基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-03T16:52:13Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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