論文の概要: Online Correlation Clustering for Dynamic Complete Signed Graphs
- arxiv url: http://arxiv.org/abs/2211.07000v1
- Date: Sun, 13 Nov 2022 19:36:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 20:12:45.729611
- Title: Online Correlation Clustering for Dynamic Complete Signed Graphs
- Title（参考訳）: 動的完全符号付きグラフに対するオンライン相関クラスタリング
- Authors: Ali Shakiba
- Abstract要約: 動的完備グラフに対する相関クラスタリングの問題点を考察する。
相関クラスタリングのための [CALM+21] におけるオンライン近似アルゴリズムを用いる。
これは、グラフ編集操作の完全なセットを可能にする、動的グラフのための最初のオンラインアルゴリズムである。
- 参考スコア（独自算出の注目度）: 9.13755431537592
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the correlation clustering problem for complete signed graphs, the input
is a complete signed graph with edges weighted as $+1$ (denote recommendation
to put this pair in the same cluster) or $-1$ (recommending to put this pair of
vertices in separate clusters) and the target is to cluster the set of vertices
such that the number of disagreements with these recommendations is minimized.
In this paper, we consider the problem of correlation clustering for dynamic
complete signed graphs where (1) a vertex can be added or deleted, and (2) the
sign of an edge can be flipped. In the proposed online scheme, the offline
approximation algorithm in [CALM+21] for correlation clustering is used. Up to
the author's knowledge, this is the first online algorithm for dynamic graphs
which allows a full set of graph editing operations.
The proposed approach is rigorously analyzed and compared with a baseline
method, which runs the original offline algorithm on each time step. Our
results show that the dynamic operations have local effects on the neighboring
vertices and we employ this locality to reduce the dependency of the running
time in the Baseline to the summation of the degree of all vertices in $G_t$,
the graph after applying the graph edit operation at time step $t$, to the
summation of the degree of the changing vertices (e.g. two endpoints of an
edge) and the number of clusters in the previous time step. Moreover, the
required working memory is reduced to the square of the summation of the degree
of the modified edge endpoints rather than the total number of vertices in the
graph.
- Abstract（参考訳）: 完全符号付きグラフの相関クラスタリング問題では、入力は$+1$(このペアを同じクラスタに配置することを推奨する)または$-1$(このペアの頂点を別々のクラスタに配置することを推奨する)の重み付けのある完全符号付きグラフであり、ターゲットは、これらの推奨との不一致の数を最小化するような頂点の集合をクラスタ化することである。
本稿では,(1)頂点の追加や削除が可能であり,(2)エッジの符号をフリップできる動的完全符号グラフの相関クラスタリングの問題について考察する。
提案手法では,[calm+21]における相関クラスタリングのためのオフライン近似アルゴリズムを用いる。
著者の知識によると、このアルゴリズムは動的グラフのための最初のオンラインアルゴリズムであり、完全なグラフ編集操作を可能にする。
提案手法は,各時間ステップで元のオフラインアルゴリズムを実行するベースライン法と比較し,厳密に解析した。
その結果, 動的演算は隣接する頂点に局所的影響があることを示し, この局所性を用いてベースラインにおけるランニング時間の依存性を, グラフ編集操作を時間ステップ$t$で適用した後のグラフ, 変化する頂点の次数(エッジの2つのエンドポイントなど)と前回の時間ステップにおけるクラスタ数の和に換算した上で, G_t$で全ての頂点の次数の和を求める。
さらに、必要なワーキングメモリは、グラフ内の頂点の総数ではなく、修正されたエッジエンドポイントの次数の総和に還元される。
関連論文リスト
- One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information
Maximization Network [31.38584638254226]
我々は、グラフの集合を異なるグループに分割する問題を、同じグループのグラフが類似しているのに対して、異なるグループのグラフが異なるように研究する。
この問題を解決するために,Deep Graph-Level Clustering (DGLC) と呼ばれる新しい手法を提案する。
DGLCはグラフレベルの表現学習とグラフレベルのクラスタリングをエンドツーエンドで実現しています。
論文 参考訳（メタデータ） (2023-02-05T12:28:08Z) - Learning Optimal Graph Filters for Clustering of Attributed Graphs [20.810096547938166]
多くの現実世界のシステムは、システム内の異なるエンティティがノードによって表現され、エッジによって相互作用するグラフとして表現することができる。
グラフィカルな構造を持つ大規模なデータセットを研究する上で重要なタスクはグラフクラスタリングである。
本稿では,FIR(Finite Impulse Response)およびARMA(Autoregressive moving Average)グラフフィルタのパラメータをクラスタリングに最適化したグラフ信号処理手法を提案する。
論文 参考訳（メタデータ） (2022-11-09T01:49:23Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Robust Correlation Clustering with Asymmetric Noise [3.8073142980733]
相関クラスタリング(英語版)はグラフクラスタリングの定式化であり、(1) ノード間の類似性/異性度を示すエッジウェイトを持つ符号付きグラフを入力とし、(2) 入力グラフ内のクラスタ数を事前に見積もる必要がない。
グラフノードの特徴ベクトル/埋め込みの生成に基づく新しいグラフ生成モデルNode Factors Model (NFM)を提案する。
論文 参考訳（メタデータ） (2021-10-15T21:47:27Z) - Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph
Clustering [37.68977275752782]
ノイズの多いエッジとグラフのノードは、クラスタリング結果を悪化させる可能性がある。
ノイズの多いノードやエッジに対するグラフクラスタリングの堅牢性を改善するために,新しいデュアルグラフ埋め込みネットワーク(DGEN)を提案する。
3つのベンチマークグラフデータセットの実験は、いくつかの最先端アルゴリズムと比較して優位性を示す。
論文 参考訳（メタデータ） (2021-04-30T06:51:51Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。
与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。
実験の結果,本手法は著しい改善をもたらすことがわかった。
論文 参考訳（メタデータ） (2021-03-30T17:36:40Z) - Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。
実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
論文 参考訳（メタデータ） (2021-02-23T07:45:58Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。
標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。
総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
論文 参考訳（メタデータ） (2020-07-08T19:48:19Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。