論文の概要: Dynamic Spectral Clustering with Provable Approximation Guarantee

• arxiv url: http://arxiv.org/abs/2406.03152v1
• Date: Wed, 5 Jun 2024 11:16:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 18:50:02.204629
• Title: Dynamic Spectral Clustering with Provable Approximation Guarantee
• Title（参考訳）: 確率近似保証を用いた動的スペクトルクラスタリング
• Authors: Steinar Laenen, He Sun,
• Abstract要約: 本論文は, クラスタ構造が緩やかな条件下では, 最終グラフ$G_T$のクラスタはスペクトルクラスタリングアルゴリズムの動的変種によってよく近似できることを示した。 合成と実世界の両方のデータセットに関する実験的研究により、我々の設計したアルゴリズムの実用性がさらに裏付けられる。
• 参考スコア（独自算出の注目度）: 7.6676757797831225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies clustering algorithms for dynamically evolving graphs $\{G_t\}$, in which new edges (and potential new vertices) are added into a graph, and the underlying cluster structure of the graph can gradually change. The paper proves that, under some mild condition on the cluster-structure, the clusters of the final graph $G_T$ of $n_T$ vertices at time $T$ can be well approximated by a dynamic variant of the spectral clustering algorithm. The algorithm runs in amortised update time $O(1)$ and query time $o(n_T)$. Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm.
• Abstract（参考訳）: 本稿では、グラフに新たなエッジ(および潜在的な新しい頂点)を追加し、グラフの基盤となるクラスタ構造が徐々に変化するような、動的に進化するグラフに対するクラスタリングアルゴリズムについて研究する。 この論文は、クラスタ構造上のいくつかの緩やかな条件下で、最終グラフのクラスタが$G_T$ of $n_T$ vertices at time $T$をスペクトルクラスタリングアルゴリズムの動的変種によってうまく近似できることを証明している。 このアルゴリズムは、償却更新時間$O(1)$とクエリ時間$o(n_T)$で実行される。 合成と実世界の両方のデータセットに関する実験的研究により、我々の設計したアルゴリズムの実用性がさらに裏付けられる。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
  スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。 電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。 合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
  論文  参考訳（メタデータ） (2023-10-17T02:31:57Z)
• Deep Temporal Graph Clustering [77.02070768950145]
  深部時間グラフクラスタリング(GC)のための汎用フレームワークを提案する。 GCは、時間グラフの相互作用シーケンスに基づくバッチ処理パターンに適合するディープクラスタリング技術を導入している。 我々のフレームワークは、既存の時間グラフ学習手法の性能を効果的に向上させることができる。
  論文  参考訳（メタデータ） (2023-05-18T06:17:50Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。 提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
  論文  参考訳（メタデータ） (2023-01-01T10:57:36Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

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

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