A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --
This work addresses the problem of link classification in signed networks for researchers in network analysis and machine learning, offering a novel active learning approach with theoretical guarantees.
The paper tackles link classification in signed networks by using correlation clustering as a measure of label regularity, deriving learning bounds in online, batch, and active settings, and introduces efficient active algorithms based on covering graphs with small circuits, achieving mistake bounds for arbitrary signed networks.
Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are the first active algorithms for link classification with mistake bounds that hold for arbitrary signed networks.