論文の概要: Graph clustering with Boltzmann machines
- arxiv url: http://arxiv.org/abs/2203.02471v2
- Date: Mon, 7 Mar 2022 23:56:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-09 11:33:48.276573
- Title: Graph clustering with Boltzmann machines
- Title(参考訳): boltzmannマシンによるグラフクラスタリング
- Authors: Pierre Miasnikof, Mohammad Bagherbeik, Ali Sheikholeslami
- Abstract要約: ボルツマンマシンはグロビマシンよりも優れたクラスタリング結果を提供することを示す。
また,Louvain法を用いて得られたクラスタと比較した。
- 参考スコア(独自算出の注目度): 1.5469452301122177
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Graph clustering is the process of grouping vertices into densely connected
sets called clusters. We tailor two mathematical programming formulations from
the literature, to this problem. In doing so, we obtain a heuristic
approximation to the intra-cluster density maximization problem. We use two
variations of a Boltzmann machine heuristic to obtain numerical solutions. For
benchmarking purposes, we compare solution quality and computational
performances to those obtained using a commercial solver, Gurobi. We also
compare clustering quality to the clusters obtained using the popular Louvain
modularity maximization method. Our initial results clearly demonstrate the
superiority of our problem formulations. They also establish the superiority of
the Boltzmann machine over the traditional exact solver. In the case of smaller
less complex graphs, Boltzmann machines provide the same solutions as Gurobi,
but with solution times that are orders of magnitude lower. In the case of
larger and more complex graphs, Gurobi fails to return meaningful results
within a reasonable time frame. Finally, we also note that both our clustering
formulations, the distance minimization and $K$-medoids, yield clusters of
superior quality to those obtained with the Louvain algorithm.
- Abstract(参考訳): グラフクラスタリングは、頂点をクラスタと呼ばれる密結合集合にグループ化するプロセスである。
我々は2つの数学的プログラミングの定式化を文献からこの問題に仕立て上げた。
これにより,クラスタ内密度最大化問題に対するヒューリスティック近似が得られる。
ボルツマン機械ヒューリスティックの2つの変種を用いて数値解を得る。
ベンチマークのために,商用解法 gurobi を用いて得られた解の質と計算性能を比較した。
また,Louvainモジュラリティ最大化法を用いて得られたクラスタと比較した。
最初の結果は問題定式化の優位性を明確に示している。
彼らはまた、従来の正確な解法よりもボルツマンマシンの優位性を確立する。
より小さな複素グラフの場合、ボルツマンマシンはgurobiと同じ解を提供するが、解時間は桁違いに低い。
より大きく複雑なグラフの場合、グロビは妥当な時間枠内で有意義な結果を返すことができない。
最後に、我々のクラスタリングの定式化、距離最小化、および$k$-medoidsは、luuvainアルゴリズムで得られたものよりも優れた品質のクラスタを産出する。
関連論文リスト
- An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳(メタデータ) (2024-03-17T21:43:19Z) - Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
ネットワークが与えられた場合、各ノードではなく、クラスタレベルでリソースを割り当てることによって、リソースの割り当てと使用効率が向上する。
本稿では,この制約付きクラスタリング問題を強化学習を用いて解く手法を提案する。
結果の節では,大規模インスタンスにおいても,アルゴリズムが最適に近い解を見つけることを示す。
論文 参考訳(メタデータ) (2024-02-15T18:27:18Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳(メタデータ) (2023-05-28T15:33:24Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳(メタデータ) (2023-05-22T17:43:34Z) - Regularization and Optimization in Model-Based Clustering [4.096453902709292]
k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。
一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。
これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
論文 参考訳(メタデータ) (2023-02-05T18:22:29Z) - 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) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳(メタデータ) (2021-04-13T23:21:01Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳(メタデータ) (2020-08-18T16:22:06Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。