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.
@InProceedings{pmlr-v23-cesa-bianchi12,
title = {A Correlation Clustering Approach to Link Classification in Signed Networks},
author = {Nicoló Cesa-Bianchi and Claudio Gentile and Fabio Vitale and Giovanni Zappella},
booktitle = {Proceedings of the 25th Annual Conference on Learning Theory},
pages = {34.1--34.20},
year = {2012},
editor = {Shie Mannor and Nathan Srebro and Robert C. Williamson},
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 = {http://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.}
}
%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
%J Proceedings of Machine Learning Research
%P 34.1--34.20
%U http://proceedings.mlr.press
%V 23
%W PMLR
%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.
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
PY - 2012/06/16
DA - 2012/06/16
ED - Shie Mannor
ED - Nathan Srebro
ED - Robert C. Williamson
ID - pmlr-v23-cesa-bianchi12
PB - PMLR
SP - 34.1
DP - PMLR
EP - 34.20
L1 - http://proceedings.mlr.press/v23/cesa-bianchi12/cesa-bianchi12.pdf
UR - http://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 -
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 PMLR 23:34.1-34.20
This site last compiled Sun, 15 Jul 2018 13:29:10 +0000