論文の概要: Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
- arxiv url: http://arxiv.org/abs/2002.09460v2
- Date: Fri, 19 Jun 2020 15:10:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 01:54:59.899940
- Title: Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
- Title（参考訳）: ハイパーグラフと二部グラフにおけるパラメータ付き相関クラスタリング
- Authors: Nate Veldt and Anthony Wirth and David F. Gleich
- Abstract要約: ハイパーグラフと二部グラフにおける新たなクラスタリングの目的について考察する。
これらの目的は、複雑なデータにおける多様な知識発見を可能にするために、1つ以上の解決パラメータによってパラメータ化される。
- 参考スコア（独自算出の注目度）: 15.36202554903105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by applications in community detection and dense subgraph
discovery, we consider new clustering objectives in hypergraphs and bipartite
graphs. These objectives are parameterized by one or more resolution parameters
in order to enable diverse knowledge discovery in complex data.
For both hypergraph and bipartite objectives, we identify parameter regimes
that are equivalent to existing objectives and share their (polynomial-time)
approximation algorithms. We first show that our parameterized hypergraph
correlation clustering objective is related to higher-order notions of
normalized cut and modularity in hypergraphs. It is further amenable to
approximation algorithms via hyperedge expansion techniques.
Our parameterized bipartite correlation clustering objective generalizes
standard unweighted bipartite correlation clustering, as well as bicluster
deletion. For a certain choice of parameters it is also related to our
hypergraph objective. Although in general it is NP-hard, we highlight a
parameter regime for the bipartite objective where the problem reduces to the
bipartite matching problem and thus can be solved in polynomial time. For other
parameter settings, we present approximation algorithms using linear program
rounding techniques. These results allow us to introduce the first
constant-factor approximation for bicluster deletion, the task of removing a
minimum number of edges to partition a bipartite graph into disjoint
bi-cliques.
In several experimental results, we highlight the flexibility of our
framework and the diversity of results that can be obtained in different
parameter settings. This includes clustering bipartite graphs across a range of
parameters, detecting motif-rich clusters in an email network and a food web,
and forming clusters of retail products in a product review hypergraph, that
are highly correlated with known product categories.
- Abstract（参考訳）: コミュニティ検出や密集したサブグラフ発見の応用に動機づけられ,ハイパーグラフや二部グラフにおける新しいクラスタリングの目的を考える。
これらの目的は、複雑なデータにおける多様な知識発見を可能にするために、1つ以上の解決パラメータによってパラメータ化される。
ハイパーグラフとバイパージットの両方の目的に対して,既存の目的と等価なパラメータレジームを同定し,それらの近似アルゴリズムを共有する。
まず,パラメータ化ハイパーグラフ相関クラスタリングの目標は,ハイパーグラフにおける正規化カットとモジュラリティの高次概念と関連していることを示す。
さらに、ハイパーエッジ展開技術によって近似アルゴリズムを適用できる。
パラメタライズド2部相関クラスタリングの目的は、標準の非重み付き2部相関クラスタリングと2クラスタの削除を一般化する。
パラメータの特定の選択は、ハイパーグラフの目的にも関係しています。
一般にnpハードであるが、問題は2部マッチング問題に還元され、多項式時間で解くことができる2部目標のパラメータレジームを強調する。
他のパラメータの設定では、線形プログラム丸め法を用いて近似アルゴリズムを提案する。
これらの結果から、二部グラフを二角形に分割する最小限のエッジを除去するタスクである双クラスター削除に対する最初の定数係数近似を導入することができる。
いくつかの実験結果において、異なるパラメータ設定で得られるフレームワークの柔軟性と結果の多様性を強調する。
これには、さまざまなパラメータにわたる2部グラフのクラスタリング、eメールネットワークとフードウェブにおけるモチーフ豊富なクラスタの検出、製品レビューハイパーグラフにおける小売製品のクラスタの形成、既知の製品カテゴリと高い相関性を持つ。
関連論文リスト
- Interpetable Target-Feature Aggregation for Multi-Task Learning based on Bias-Variance Analysis [53.38518232934096]
マルチタスク学習(MTL)は、タスク間の共有知識を活用し、一般化とパフォーマンスを改善するために設計された強力な機械学習パラダイムである。
本稿では,タスククラスタリングと特徴変換の交点におけるMTL手法を提案する。
両段階において、鍵となる側面は減った目標と特徴の解釈可能性を維持することである。
論文 参考訳（メタデータ） (2024-06-12T08:30:16Z) - HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。
HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
論文 参考訳（メタデータ） (2024-05-27T11:04:05Z) - Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳（メタデータ） (2024-04-16T07:05:16Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - 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) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。
本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-27T01:14:06Z) - T-LoHo: A Bayesian Regularization Model for Structured Sparsity and
Smoothness on Graphs [0.0]
グラフ構造化データでは、構造化されたスパーシリティと滑らかさが団結する傾向にある。
グラフィカルな関係を持つ高次元パラメータに先立って提案する。
構造された空間と滑らかさを同時に検出するために使用します。
論文 参考訳（メタデータ） (2021-07-06T10:10:03Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。
複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。
これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
論文 参考訳（メタデータ） (2021-03-25T14:35:07Z) - Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
異質なノード度とエッジサイズを持つクラスタ化ハイパーグラフの表現的生成モデルを提案する。
我々は,100万ノードの合成ハイパーグラフを用いた実験など,ハイパーグラフ・ルーバインは高度にスケーラブルであることを示す。
このモデルを用いて,学校連絡ネットワークにおける高次構造の異なるパターン,米国議会法案共同提案,米国議会委員会,共同購入行動における製品カテゴリ,ホテルロケーションを分析した。
論文 参考訳（メタデータ） (2021-01-24T00:25:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。