論文の概要: Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs

• arxiv url: http://arxiv.org/abs/2203.03221v3
• Date: Sun, 14 Sep 2025 15:55:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-16 17:26:22.551183
• Title: Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs
• Title（参考訳）: クラスタリングと非直接グラフのための一般化ディリクレエネルギーとグラフラプラシアン
• Authors: Harry Sevi, Gwendal Debaussart-Joniec, Malik Hacini, Matthieu Jonckheere, Argyris Kalogeratos,
• Abstract要約: 有向グラフのクラスタリングは、エッジ接続の非対称性のため、依然として根本的な課題である。 我々は、古典的なディリクレエネルギーを拡張する新しいエネルギー汎関数である一般化ディリクレエネルギー(GDE)を導入する。 本稿では,弱連結なダイグラフのクラスタリングを可能にする一般化スペクトルクラスタリング(GSC)手法を提案する。
• 参考スコア（独自算出の注目度）: 2.4118754741048987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering in directed graphs remains a fundamental challenge due to the asymmetry in edge connectivity, which limits the applicability of classical spectral methods originally designed for undirected graphs. A common workaround is to symmetrize the adjacency matrix, but this often leads to losing critical directional information. In this work, we introduce the generalized Dirichlet energy (GDE), a novel energy functional that extends the classical Dirichlet energy to handle arbitrary positive vertex measures and Markov transition matrices. GDE provides a unified framework applicable to both directed and undirected graphs, and is closely tied to the diffusion dynamics of random walks. Building on this framework, we propose the generalized spectral clustering (GSC) method that enables the principled clustering of weakly connected digraphs without resorting to the introduction of teleportation to the random walk transition matrix. A key component of our approach is the utilization of a parametrized vertex measure encoding graph directionality and density. Experiments on real-world point-cloud datasets demonstrate that GSC consistently outperforms existing spectral clustering approaches in terms of clustering accuracy and robustness, offering a powerful new tool for graph-based data analysis.
• Abstract（参考訳）: 有向グラフのクラスタリングは、エッジ接続の非対称性が元来、非有向グラフのために設計された古典的スペクトル法の適用性を制限しているため、依然として根本的な課題である。 一般的な回避策は、隣接行列を対称性付けることであるが、これはしばしば重要な方向情報を失う。 本研究では、任意の正の頂点測度とマルコフ遷移行列を扱うために古典的ディリクレエネルギーを拡張する新しいエネルギー汎関数である一般化ディリクレエネルギー(GDE)を導入する。 GDEは、有向グラフと無向グラフの両方に適用可能な統一フレームワークを提供し、ランダムウォークの拡散力学と密接に結びついている。 この枠組みに基づいて、ランダムウォーク遷移行列へのテレポーテーションを導入することなく、弱連結ダイグラフの原理的クラスタリングを可能にする一般化スペクトルクラスタリング(GSC)法を提案する。 提案手法の鍵となる要素は,グラフの向きと密度を符号化するパラメタライズされた頂点測度の利用である。 実世界のポイントクラウドデータセットの実験では、GSCはクラスタリングの正確性と堅牢性の観点から既存のスペクトルクラスタリングアプローチを一貫して上回り、グラフベースのデータ分析のための強力なツールを提供する。

関連論文リスト

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
  論文  参考訳（メタデータ） (2025-06-19T08:01:00Z)
• 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)
• Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models [22.421702511126373]
  ブロックモデルに対する統計的推測を利用して、有向グラフに対するスペクトルクラスタリングアルゴリズムの開発を導く。 我々は、スペクトル緩和の誤クラスタリング誤差に関する理論上界を確立し、この緩和に基づいて、有向グラフに対する新しい自己適応スペクトルクラスタリング法を導入する。
  論文  参考訳（メタデータ） (2024-03-28T15:47:13Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  グラフ機械学習のための微粒なグラフ合理化(FIG)を提案する。 私たちのアイデアは、入力ノード間のリッチなインタラクションを提供するセルフアテンションメカニズムによって推進されます。 実験では,実世界の7つのデータセットを対象とし,提案したFIGは,13のベースライン手法と比較して大きな性能上の優位性を示した。
  論文  参考訳（メタデータ） (2023-12-13T02:56:26Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network [31.38584638254226]
  我々は、グラフの集合を異なるグループに分割する問題を、同じグループのグラフが類似しているのに対して、異なるグループのグラフが異なるように研究する。 この問題を解決するために,Deep Graph-Level Clustering (DGLC) と呼ばれる新しい手法を提案する。 DGLCはグラフレベルの表現学習とグラフレベルのクラスタリングをエンドツーエンドで実現しています。
  論文  参考訳（メタデータ） (2023-02-05T12:28:08Z)
• Causally-guided Regularization of Graph Attention Improves Generalizability [69.09877209676266]
  本稿では,グラフアテンションネットワークのための汎用正規化フレームワークであるCARを紹介する。 メソッド名は、グラフ接続に対するアクティブ介入の因果効果とアテンションメカニズムを一致させる。 ソーシャル・メディア・ネットワーク規模のグラフでは、CAR誘導グラフ再構成アプローチにより、グラフの畳み込み手法のスケーラビリティとグラフの注意力の向上を両立させることができる。
  論文  参考訳（メタデータ） (2022-10-20T01:29:10Z)
• Clustering for directed graphs using parametrized random walk diffusion kernels [5.145741425164946]
  我々は,P-RWDKC(Parametrized Random Walk Diffusion Kernel Clustering)という新しいクラスタリングフレームワークを導入する。 我々のフレームワークは拡散幾何学と一般化スペクトルクラスタリングフレームワークに基づいている。 実世界のデータセットと実世界のグラフから構築した$K$-NNグラフの実験は、我々のクラスタリングアプローチがすべてのテストケースでうまく機能していることを示しています。
  論文  参考訳（メタデータ） (2022-10-01T16:13:40Z)
• Demystifying Graph Convolution with a Simple Concatenation [6.542119695695405]
  グラフトポロジ、ノード特徴、ラベル間の重なり合う情報を定量化する。 グラフの畳み込みは、グラフの畳み込みに代わる単純だが柔軟な代替手段であることを示す。
  論文  参考訳（メタデータ） (2022-07-18T16:39:33Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。 近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
  論文  参考訳（メタデータ） (2021-06-26T06:24:51Z)
• Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
  スペクトルクラスタリングにインスパイアされた手法として,ランダムな次元還元プロジェクションから得られた行列スケッチを用いる。 提案手法は,完全に動的なブロックモデルストリームが与えられた場合,性能の高いクラスタリング結果が得られる埋め込みを生成する。 また、ブロックモデルパラメータがその後の埋め込みの必要次元に与える影響についても検討し、ランダムなプロジェクションが分散メモリにおけるグラフクラスタリングの性能を大幅に改善できることを示す。
  論文  参考訳（メタデータ） (2020-07-24T17:38:04Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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