論文の概要: Hierarchical Clustering and Signal Denoising on Digraphs
- arxiv url: http://arxiv.org/abs/2609.34670v1
- Date: Mon, 28 Sep 2026 09:05:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 11:25:10.544516
- Title: Hierarchical Clustering and Signal Denoising on Digraphs
- Title（参考訳）: 図形上の階層的クラスタリングと信号のデノジング
- Abstract要約: 本稿では、その隣接行列から導かれるエルミート行列として、ディグラフ(方向グラフ)の表現を提案する。
エルミート行列のスペクトル分解に基づいて、$k$-meansのグラフクラスタリングアルゴリズムを導入し、グラフ上の分割を生成する。
合成ダイグラフと実世界のダイグラフの実験は、ダイグラフクラスタリングのためのmyprojアルゴリズムの優位性を実証している。
- 参考スコア（独自算出の注目度）: 5.669214484049271
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose a representation of a digraph (directed graph) as a Hermitian matrix derived from its adjacency matrix. This representation characterizes both the connectivity and the edge orientation of the digraph. Based on the spectral decomposition of the Hermitian matrix, a digraph clustering algorithm with $k$-means is introduced to produce a partition on the graph. Applying this algorithm (bottom-up) recursively to a digraph with partially labeled vertices yields a spectral hierarchical digraph clustering (\myproj) algorithm that produces consistent nested partitions of the digraph, or equivalently, a tree structure. Furthermore, based on the in-degree and out-degree of each cluster in the digraph clustering, a pair of hierarchical interval partitions (filtrations) can be derived in a top-down manner to produce a pair of nested knot sequences. These knot sequences facilitate the construction of multilevel spline quasi-interpolants, enabling a noisy graph signal to be decomposed into a coarse approximation and inter-level details, followed by adaptive thresholding and reconstruction. Experiments on synthetic and real-world digraphs demonstrate the superiority of our {\myproj} algorithm for digraph clustering across diverse graph structural properties (homophily and heterophily) and supervision settings. Moreover, experiments on digraph signal processing using multilevel spline quasi-interpolants further demonstrate the effectiveness of signal recovery on digraphs in terms of RMSE and SNR.
- Abstract（参考訳）: 本稿では,その隣接行列から導かれるエルミート行列として,ディグラフ(方向グラフ)の表現を提案する。
この表現は、ダイグラフの接続性とエッジ配向の両方を特徴付ける。
エルミート行列のスペクトル分解に基づいて、$k$-meansのグラフクラスタリングアルゴリズムを導入し、グラフ上の分割を生成する。
このアルゴリズム (bottom-up) を部分的にラベル付き頂点を持つグラフに再帰的に適用すると、ダイグラフの一貫したネスト分割を生成するスペクトル階層的ダイグラフクラスタリング (\myproj) アルゴリズムが得られる。
さらに、ダイグラフクラスタリングにおける各クラスタのイン・ディグリーとアウト・ディグリーに基づいて、一対の階層的間隔分割(フィルタ)をトップダウンに導出し、ネストした結び目配列を生成する。
これらの結び目配列は、多重レベルスプライン準補間体の構築を促進し、ノイズグラフ信号を粗い近似と階層間詳細に分解し、適応しきい値と再構成を行う。
合成および実世界のダイグラフの実験は、様々なグラフ構造特性(ホモフィリーおよびヘテロフィリー)にまたがるダイグラフのクラスタリングと監視設定において、我々の {\myproj}アルゴリズムの優位性を示す。
さらに,マルチレベルスプライン準補間材を用いたダイグラフ信号処理実験により,RMSEおよびSNRによるダイグラフ上での信号回復の有効性を実証した。
関連論文リスト
- Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。
ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
論文 参考訳（メタデータ） (2026-07-30T02:45:31Z) - A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。
コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。
この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
論文 参考訳（メタデータ） (2025-07-17T10:02:57Z) - SSHPool: The Separated Subgraph-based Hierarchical Pooling [47.78745802682822]
グラフ分類のための新しい局所グラフプーリング法,すなわち分離部分グラフベース階層プール(SSH)を開発した。
局所グラフ畳み込み単位を局所構造として個別に用いて各部分グラフをより粗いノードに圧縮する。
我々は、グラフ分類のためのSSHPoolモジュールに関連するエンドツーエンドのGNNフレームワークを開発する。
論文 参考訳（メタデータ） (2024-03-24T13:03:35Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。
本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-27T01:14:06Z) - SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
グラフマッチングの精度、構造的不整合(SI)を測定するための新しい基準を提案する。
具体的には、SIは、グラフのマルチホップ構造に対応するために熱拡散ウェーブレットを組み込む。
ミラー降下法を用いて,新しいK-ホップ構造に基づくマッチングコストでGromov-Wasserstein距離を解くことにより,SIGMAを導出可能であることを示す。
論文 参考訳（メタデータ） (2022-02-06T15:18:37Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z) - Affinity Fusion Graph-based Framework for Natural Image Segmentation [20.674669923674834]
このフレームワークは、マルチスケールスーパーピクセルの親和性ノードと呼ばれる新しい定義に従って、隣接グラフとカーネルスペクトルクラスタリングベースのグラフ(KSCグラフ)を組み合わせる。
KSCグラフは、これらの親和性ノード間の非線形関係を探索するために、新しいカーネルスペクトルクラスタリングによって構築される。
各スケールでの隣接グラフを構築し、アフィニティノードで提案されたKSCグラフを更新するためにさらに使用される。
論文 参考訳（メタデータ） (2020-06-24T08:01:10Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
カーネル重み付けの観点からノード集約を再解釈する。
本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。
特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
論文 参考訳（メタデータ） (2020-05-16T04:44:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。