2011 CollectiveGraphIdentification

• (Namata et al., 2011) ⇒ Galileo Mark Namata, Stanley Kok, and Lise Getoor. (2011). “Collective Graph Identification.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020429

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Collective+Graph+Identification
• http://dl.acm.org/citation.cfm?id=2020408.2020429&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; collective classification; data mining; design; entity resolution; experimentation; link prediction; performance; semi-supervised learning

Abstract

Data describing networks (communication networks, transaction networks, disease transmission networks, collaboration networks, etc.) is becoming increasingly ubiquitous. While this observational data is useful, it often only hints at the actual underlying social or technological structures which give rise to the interactions. For example, an email communication network provides useful insight but is not the same as the "real" social network among individuals. In this paper, we introduce the problem of graph identification, i.e., the discovery of the true graph structure underlying an observed network. We cast the problem as a probabilistic inference task, in which we must infer the nodes, edges, and node labels of a hidden graph, based on evidence provided by the observed network. This in turn corresponds to the problems of performing entity resolution, link prediction, and node labeling to infer the hidden graph. While each of these problems have been studied separately, they have never been considered together as a coherent task. We present a simple yet novel approach to address all three problems simultaneously. Our approach, called C3, consists of Coupled Collective Classifiers that are iteratively applied to propagate information among solutions to the problems. We empirically demonstrate that C3 is superior, in terms of both predictive accuracy and runtime, to state-of-the-art probabilistic approaches on three real-world problems.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 CollectiveGraphIdentification	Stanley Kok Galileo Mark Namata Lise Getoor			Collective Graph Identification				10.1145/2020408.2020429		2011