論文の概要: Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More

• arxiv url: http://arxiv.org/abs/2308.06448v1
• Date: Sat, 12 Aug 2023 02:47:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-15 17:23:58.311543
• Title: Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More
• Title（参考訳）: マックスカット、ミンカット等の緩和としての潜在ランダムステップ
• Authors: Sudhanshu Chanpuriya and Cameron Musco
• Abstract要約: クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
• 参考スコア（独自算出の注目度）: 30.919536115917726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Algorithms for node clustering typically focus on finding homophilous structure in graphs. That is, they find sets of similar nodes with many edges within, rather than across, the clusters. However, graphs often also exhibit heterophilous structure, as exemplified by (nearly) bipartite and tripartite graphs, where most edges occur across the clusters. Grappling with such structure is typically left to the task of graph simplification. We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification, and provides a framework for modeling arbitrary graph structure. Our model is based on factorizing the process of taking a random walk on the graph. It permits an unconstrained parametrization, allowing for optimization via simple gradient descent. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones. We illustrate our algorithm's capabilities on a synthetic graph, as well as simple unsupervised learning tasks involving bipartite and tripartite clustering of orthographic and phonological data.
• Abstract（参考訳）: ノードクラスタリングのアルゴリズムは、グラフの相同構造を見つけることに集中する。 つまり、クラスタをまたぐのではなく、多くのエッジを持つ類似ノードのセットを見つけるのです。 しかし、グラフは(ほぼ)二部グラフや三部グラフで示されるように、しばしばヘテロ親和性構造を示す。 このような構造のグラッリングは通常、グラフ単純化のタスクに委ねられる。 クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案し、任意のグラフ構造をモデル化するためのフレームワークを提供する。 我々のモデルは、ランダムウォークをグラフ上で行う過程を分解することに基づいている。 これは制約のないパラメトリゼーションを可能にし、単純な勾配降下による最適化を可能にする。 ソフトクラスタリングへのハードクラスタリングを緩和することで、アルゴリズムは潜在的なハードクラスタリング問題を扱いやすいクラスタリングに緩和する。 合成グラフ上でのアルゴリズムの能力と、直交および音韻データの二分節および三分節クラスタリングを含む単純な教師なし学習タスクについて説明する。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  グラフクラスタリングは機械学習の基本的な問題である。 近年、ディープラーニング手法は最先端の成果を達成しているが、事前に定義されたクラスタ番号なしでは動作できない。 本稿では,グラフ情報理論の新たな視点からこの問題に対処することを提案する。
  論文  参考訳（メタデータ） (2024-05-20T05:46:41Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
  密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。 我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
  論文  参考訳（メタデータ） (2023-01-28T11:10:50Z)
• Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
  グラフクラスタリングフレームワーク textitPCon を開発した。 既存のソリューションの多くをフレームワークに還元できることを示します。 本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
  論文  参考訳（メタデータ） (2022-11-22T12:45:27Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。 フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
  論文  参考訳（メタデータ） (2022-03-02T20:07:04Z)
• 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)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)

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

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