Online Correlation Clustering for Dynamic Complete Signed Graphs
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(m\times\left( 2+ \alpha (G) \right)+n)$ to $O(m+n)$ for any given value of $\varepsilon$ for a complete signed graph wit…
ClusteringGraph ClusteringHigh-order Correlation Preserved Incomplete Multi-view Subspace Clustering
Incomplete multi-view clustering aims to exploit theinformation of multiple incomplete views to partition data into their clusters. Existing methods only utilize the pair-wise sample correlation and pair-wise view correl…
ClusteringIncomplete multi-view clusteringMulti-view Subspace ClusteringVocal Bursts Intensity PredictionDynamic data summarization for hierarchical spatial clustering
Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) finds meaningful patterns in spatial data by considering density and spatial proximity. As the clustering algorithm is inherently designe…
ClusteringData SummarizationCorrelation Clustering with Random Partial Information
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the …
Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
We study the dynamic correlation clustering problem with $\textit{adaptive}$ edge label flips. In correlation clustering, we are given a $n$-vertex complete graph whose edges are labeled either $(+)$ or $(-)$, and the go…
Adversarial RobustnessClustering