Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds
Correlation clustering is a widely studied framework for clustering based on pairwise similarity and dissimilarity scores, but its best approximation algorithms rely on impractical linear programming relaxations. We present faster approximation algorithms that avoid these relaxations, for two well-studied special cases: cluster editing and cluster deletion. We accomplish this by drawing new connections to edge labeling problems related to the principle of strong triadic closure. This leads to faster and more practical linear programming algorithms, as well as extremely scalable combinatorial techniques, including the first combinatorial approximation algorithm for cluster deletion. In practice, our algorithms produce approximate solutions that nearly match the best algorithms in quality, while scaling to problems that are orders of magnitude larger.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation …
ClusteringGraph ClusteringEffective Decoding in Graph Auto-Encoder using Triadic Closure
The (variational) graph auto-encoder and its variants have been popularly used for representation learning on graph-structured data. While the encoder is often a powerful graph convolutional network, the decoder reconstr…
ClusteringDecoderGraph GenerationLink Prediction+4Disentangling homophily, community structure and triadic closure in networks
Network homophily, the tendency of similar nodes to be connected, and transitivity, the tendency of two nodes being connected if they share a common neighbor, are conflated properties in network analysis, since one mecha…
Community DetectionGraph ReconstructionLink PredictionStochastic Block ModelNetwork Formation and Dynamics Among Multi-LLMs
Social networks fundamentally shape human opinions, behaviors, and the dissemination of information. As large language models (LLMs) like GPT, Claude, and Llama increasingly integrate into social and professional setting…
Decision MakingUnsupervised Semantic Frame Induction using Triclustering
We use dependency triples automatically extracted from a Web-scale corpus to perform unsupervised semantic frame induction. We cast the frame induction problem as a triclustering problem that is a generalization of clust…
Clustering