@conference {14447,
	title = {Collective graph identification},
	booktitle = {Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining},
	series = {KDD {\textquoteright}11},
	year = {2011},
	month = {2011///},
	pages = {87 - 95},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	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.},
	keywords = {collective classification, entity resolution, link prediction, semi-supervised learning},
	isbn = {978-1-4503-0813-7},
	doi = {10.1145/2020408.2020429},
	url = {http://doi.acm.org/10.1145/2020408.2020429},
	author = {Namata,Galileo Mark and Kok,Stanley and Getoor, Lise}
}
@conference {14451,
	title = {Identifying graphs from noisy and incomplete data},
	booktitle = {Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data},
	series = {U {\textquoteright}09},
	year = {2009},
	month = {2009///},
	pages = {23 - 29},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {There is a growing wealth of data describing networks of various types, including social networks, physical networks such as transportation or communication networks, and biological networks. At the same time, there is a growing interest in analyzing these networks, in order to uncover general laws that govern their structure and evolution, and patterns and predictive models to develop better policies and practices. However, a fundamental challenge in dealing with this newly available observational data describing networks is that the data is often of dubious quality -- it is noisy and incomplete -- and before any analysis method can be applied, the data must be cleaned, and missing information inferred. In this paper, we introduce the notion of graph identification, which explicitly models the inference of a "cleaned" output network from a noisy input graph. It is this output network that is appropriate for further analysis. We present an illustrative example and use the example to explore the types of inferences involved in graph identification, as well as the challenges and issues involved in combining those inferences. We then present a simple, general approach to combining the inferences in graph identification and experimentally show the utility of our combined approach and how the performance of graph identification is sensitive to the inter-dependencies among these inferences.},
	keywords = {classification, data mining, entity resolution, link prediction, social networks, statistical relational learning},
	isbn = {978-1-60558-675-5},
	doi = {10.1145/1610555.1610559},
	url = {http://doi.acm.org/10.1145/1610555.1610559},
	author = {Namata,Jr.,Galileo Mark S. and Getoor, Lise}
}
