A Correlation Clustering Approach to Link Classification in Signed Networks

Nicoló Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:34.1-34.20, 2012.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-cesa-bianchi12, title = {A Correlation Clustering Approach to Link Classification in Signed Networks}, author = {Cesa-Bianchi, Nicoló and Gentile, Claudio and Vitale, Fabio and Zappella, Giovanni}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {34.1--34.20}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/cesa-bianchi12/cesa-bianchi12.pdf}, url = {https://proceedings.mlr.press/v23/cesa-bianchi12.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T A Correlation Clustering Approach to Link Classification in Signed Networks %A Nicoló Cesa-Bianchi %A Claudio Gentile %A Fabio Vitale %A Giovanni Zappella %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-cesa-bianchi12 %I PMLR %P 34.1--34.20 %U https://proceedings.mlr.press/v23/cesa-bianchi12.html %V 23 %X 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.
RIS
TY - CPAPER TI - A Correlation Clustering Approach to Link Classification in Signed Networks AU - Nicoló Cesa-Bianchi AU - Claudio Gentile AU - Fabio Vitale AU - Giovanni Zappella BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-cesa-bianchi12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 34.1 EP - 34.20 L1 - http://proceedings.mlr.press/v23/cesa-bianchi12/cesa-bianchi12.pdf UR - https://proceedings.mlr.press/v23/cesa-bianchi12.html AB - 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. ER -
APA
Cesa-Bianchi, N., Gentile, C., Vitale, F. & Zappella, G.. (2012). A Correlation Clustering Approach to Link Classification in Signed Networks. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:34.1-34.20 Available from https://proceedings.mlr.press/v23/cesa-bianchi12.html.

Related Material