論文の概要: Spectral Clustering via Orthogonalization-Free Methods

• arxiv url: http://arxiv.org/abs/2305.10356v1
• Date: Tue, 16 May 2023 16:01:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-18 14:52:09.263934
• Title: Spectral Clustering via Orthogonalization-Free Methods
• Title（参考訳）: 直交化フリー手法によるスペクトルクラスタリング
• Authors: Qiyuan Pang and Haizhao Yang
• Abstract要約: スペクトルクラスタリングにおける次元性低減に使用されるグラフ信号フィルタは通常、高価な固有値推定を必要とする。 本研究では,スペクトルクラスタリングの次元化として目的関数を最適化し,直交化のない4つの手法を提案する。 提案手法はクラスタリング品質において理想的なグラフ信号フィルタと等価であると数値的に仮定する。
• 参考スコア（独自算出の注目度）: 2.995087247817663
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Signal Filter used as dimensionality reduction in spectral clustering usually requires expensive eigenvalue estimation. We analyze the filter in an optimization setting and propose to use four orthogonalization-free methods by optimizing objective functions as dimensionality reduction in spectral clustering. The proposed methods do not utilize any orthogonalization, which is known as not well scalable in a parallel computing environment. Our methods theoretically construct adequate feature space, which is, at most, a weighted alteration to the eigenspace of a normalized Laplacian matrix. We numerically hypothesize that the proposed methods are equivalent in clustering quality to the ideal Graph Signal Filter, which exploits the exact eigenvalue needed without expensive eigenvalue estimation. Numerical results show that the proposed methods outperform Power Iteration-based methods and Graph Signal Filter in clustering quality and computation cost. Unlike Power Iteration-based methods and Graph Signal Filter which require random signal input, our methods are able to utilize available initialization in the streaming graph scenarios. Additionally, numerical results show that our methods outperform ARPACK and are faster than LOBPCG in the streaming graph scenarios. We also present numerical results showing the scalability of our methods in multithreading and multiprocessing implementations to facilitate parallel spectral clustering.
• Abstract（参考訳）: スペクトルクラスタリングの次元減少として用いられるグラフ信号フィルタは通常、高価な固有値推定を必要とする。 最適化条件でフィルタを解析し,スペクトルクラスタリングの次元化として目的関数を最適化し,直交化のない4つの手法を提案する。 提案手法では,並列計算環境ではスケーラビリティが不十分であることが知られている直交化を一切利用しない。 本手法は理論上、正規化されたラプラシアン行列の固有空間への重み付き変更である適切な特徴空間を構築する。 提案手法は, 高価な固有値推定を必要とせず, 正確な固有値を利用する理想的なグラフ信号フィルタと, クラスタリング品質において等価であると仮定した。 数値計算の結果,提案手法はクラスタリングの品質と計算コストにおいて,電力反復法やグラフ信号フィルタよりも優れていた。 ランダムな信号入力を必要とするPower Iteration法やGraph Signal Filterとは異なり,本手法はストリーミンググラフのシナリオで利用可能な初期化を利用できる。 さらに,本手法はストリーミンググラフのシナリオではLOBPCGよりも高速であり,ARPACKよりも高速であることを示す。 また,並列スペクトルクラスタリングを容易にするマルチスレッディングおよびマルチプロセッシング実装における手法のスケーラビリティを示す数値計算結果を示す。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• 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)
• Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering [12.544602297450533]
  私たちは、ほとんどのエッジがクラスタ内に落ち、わずかにエッジがクラスタ間に落ちているノードのクラスタを特定することを目的としています。 スペクトルクラスタリングのコアステップは、対応するグラフラプラシア行列の固有分解を行う。 本稿では,SVDソルバを高速化し,スペクトルクラスタリングを行うために,スペクトルを並列化可能なアプローチを提案する。
  論文  参考訳（メタデータ） (2022-07-29T10:13:07Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Multiway $p$-spectral graph cuts on Grassmann manifolds [0.3441021278275805]
  直接マルチウェイスペクトルクラスタリングアルゴリズムを$p$-norm, for $p in (1, 2]$で提案する。 グラフ $p$-Laplacian の多重固有ベクトルを計算する問題は、グラスマン多様体上の制約のない最小化問題として再キャストされる。 バランスの取れたグラフの単調な減少を監視することは、検討された$p$レベルから最高の解が得られることを保証します。
  論文  参考訳（メタデータ） (2020-08-30T16:25:04Z)
• Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
  スペクトルクラスタリングにインスパイアされた手法として,ランダムな次元還元プロジェクションから得られた行列スケッチを用いる。 提案手法は,完全に動的なブロックモデルストリームが与えられた場合,性能の高いクラスタリング結果が得られる埋め込みを生成する。 また、ブロックモデルパラメータがその後の埋め込みの必要次元に与える影響についても検討し、ランダムなプロジェクションが分散メモリにおけるグラフクラスタリングの性能を大幅に改善できることを示す。
  論文  参考訳（メタデータ） (2020-07-24T17:38:04Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。 提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。 我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
  論文  参考訳（メタデータ） (2020-03-02T16:40:36Z)

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

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