論文の概要: Sublinear Algorithms for Hierarchical Clustering

• arxiv url: http://arxiv.org/abs/2206.07633v1
• Date: Wed, 15 Jun 2022 16:25:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-16 15:12:42.283543
• Title: Sublinear Algorithms for Hierarchical Clustering
• Title（参考訳）: 階層クラスタリングのためのサブ線形アルゴリズム
• Authors: Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil
• Abstract要約: 本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。 すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 14.124026862687941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in domains such as phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources. The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) MPC model where the graph edges are partitioned over several machines connected via a communication channel. We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing better algorithms in each of these models.
• Abstract（参考訳）: グラフ上の階層的クラスタリングは、系統学、ソーシャルネットワーク分析、情報検索といった分野におけるデータマイニングと機械学習の基本的なタスクである。 具体的には,最近普及したdasguptaによる階層クラスタリングの目的関数について考察する。 この目的関数を最小化する以前のアルゴリズムは、線形時間/空間の複雑さを必要とする。 多くのアプリケーションにおいて、基礎となるグラフは巨大であり、線形時間/空間アルゴリズムを使ってもグラフを計算的に処理することは困難である。 その結果,サブ線形資源のみを用いてグローバルな計算を行うアルゴリズムの設計に強い関心が寄せられている。 本研究の目的は,(1)エッジをストリームとして提示する(動的)ストリーミングモデル,(2)グラフを隣接および次数クエリでクエリするクエリモデル,(3)グラフエッジを通信チャネルを介して接続された複数のマシンに分割したmpcモデル,の3つのよく検討されたサブリニア計算モデルの下での大規模グラフの階層的クラスタリングを検討することである。 上記の3モデルすべてにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。 アルゴリズムの結果の核心は、グラフのカットという観点からの目的の視点であり、これにより、目的関数に小さな歪みしか導入せずに階層的なクラスタリングを行うためにカットスペーサーの緩和された概念を使うことができる。 提案アルゴリズムの主な貢献は,クエリモデルとMPCモデルにおいて,目的形式の切断スペーサーをどのように効率的に構築できるかを示すことである。 各モデルでより良いアルゴリズムを設計する可能性を排除し、ほぼ一致する下限を確立することで、アルゴリズムの結果を補完します。

関連論文リスト

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Learning Optimal Graph Filters for Clustering of Attributed Graphs [20.810096547938166]
  多くの現実世界のシステムは、システム内の異なるエンティティがノードによって表現され、エッジによって相互作用するグラフとして表現することができる。 グラフィカルな構造を持つ大規模なデータセットを研究する上で重要なタスクはグラフクラスタリングである。 本稿では,FIR(Finite Impulse Response)およびARMA(Autoregressive moving Average)グラフフィルタのパラメータをクラスタリングに最適化したグラフ信号処理手法を提案する。
  論文  参考訳（メタデータ） (2022-11-09T01:49:23Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。 アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。 そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
  論文  参考訳（メタデータ） (2021-12-01T10:35:34Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)

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

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