Joint Inference of Multiple Label Types in Large Networks

Deepayan Chakrabarti, Stanislav Funiak, Jonathan Chang, Sofus Macskassy
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):874-882, 2014.

Abstract

We tackle the problem of inferring node labels in a partially labeled graph where each node in the graph has multiple label types and each label type has a large number of possible labels. Our primary example, and the focus of this paper, is the joint inference of label types such as hometown, current city, and employers, for users connected by a social network. Standard label propagation fails to consider the properties of the label types and the interactions between them. Our proposed method, called EdgeExplain, explicitly models these, while still enabling scalable inference under a distributed message-passing architecture. On a billion-node subset of the Facebook social network, EdgeExplain significantly outperforms label propagation for several label types, with lifts of up to 120% for recall@1 and 60% for recall@3.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-chakrabarti14, title = {Joint Inference of Multiple Label Types in Large Networks}, author = {Chakrabarti, Deepayan and Funiak, Stanislav and Chang, Jonathan and Macskassy, Sofus}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {874--882}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/chakrabarti14.pdf}, url = {https://proceedings.mlr.press/v32/chakrabarti14.html}, abstract = {We tackle the problem of inferring node labels in a partially labeled graph where each node in the graph has multiple label types and each label type has a large number of possible labels. Our primary example, and the focus of this paper, is the joint inference of label types such as hometown, current city, and employers, for users connected by a social network. Standard label propagation fails to consider the properties of the label types and the interactions between them. Our proposed method, called EdgeExplain, explicitly models these, while still enabling scalable inference under a distributed message-passing architecture. On a billion-node subset of the Facebook social network, EdgeExplain significantly outperforms label propagation for several label types, with lifts of up to 120% for recall@1 and 60% for recall@3.} }
Endnote
%0 Conference Paper %T Joint Inference of Multiple Label Types in Large Networks %A Deepayan Chakrabarti %A Stanislav Funiak %A Jonathan Chang %A Sofus Macskassy %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-chakrabarti14 %I PMLR %P 874--882 %U https://proceedings.mlr.press/v32/chakrabarti14.html %V 32 %N 2 %X We tackle the problem of inferring node labels in a partially labeled graph where each node in the graph has multiple label types and each label type has a large number of possible labels. Our primary example, and the focus of this paper, is the joint inference of label types such as hometown, current city, and employers, for users connected by a social network. Standard label propagation fails to consider the properties of the label types and the interactions between them. Our proposed method, called EdgeExplain, explicitly models these, while still enabling scalable inference under a distributed message-passing architecture. On a billion-node subset of the Facebook social network, EdgeExplain significantly outperforms label propagation for several label types, with lifts of up to 120% for recall@1 and 60% for recall@3.
RIS
TY - CPAPER TI - Joint Inference of Multiple Label Types in Large Networks AU - Deepayan Chakrabarti AU - Stanislav Funiak AU - Jonathan Chang AU - Sofus Macskassy BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-chakrabarti14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 874 EP - 882 L1 - http://proceedings.mlr.press/v32/chakrabarti14.pdf UR - https://proceedings.mlr.press/v32/chakrabarti14.html AB - We tackle the problem of inferring node labels in a partially labeled graph where each node in the graph has multiple label types and each label type has a large number of possible labels. Our primary example, and the focus of this paper, is the joint inference of label types such as hometown, current city, and employers, for users connected by a social network. Standard label propagation fails to consider the properties of the label types and the interactions between them. Our proposed method, called EdgeExplain, explicitly models these, while still enabling scalable inference under a distributed message-passing architecture. On a billion-node subset of the Facebook social network, EdgeExplain significantly outperforms label propagation for several label types, with lifts of up to 120% for recall@1 and 60% for recall@3. ER -
APA
Chakrabarti, D., Funiak, S., Chang, J. & Macskassy, S.. (2014). Joint Inference of Multiple Label Types in Large Networks. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):874-882 Available from https://proceedings.mlr.press/v32/chakrabarti14.html.

Related Material