2013 MiningDiscriminativeSubgraphsfr

• (Ranu et al., 2013) ⇒ Sayan Ranu, Minh Hoang, and Ambuj Singh. (2013). “Mining Discriminative Subgraphs from Global-state Networks.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487692

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Mining+Discriminative+Subgraphs+from+Global-state+Networks
• http://dl.acm.org/citation.cfm?id=2487575.2487692&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; discriminative subgraphs; network-constrained decision trees

Abstract

Global-state networks provide a powerful mechanism to model the increasing heterogeneity in data generated by current systems. Such a network comprises of a series of network snapshots with dynamic local states at nodes, and a global network state indicating the occurrence of an event. Mining discriminative subgraphs from global-state networks allows us to identify the influential sub-networks that have maximum impact on the global state and unearth the complex relationships between the local entities of a network and their collective behavior. In this paper, we explore this problem and design a technique called MINDS to mine minimally discriminative subgraphs from large global-state networks. To combat the exponential subgraph search space, we derive the concept of an edit map and perform Metropolis Hastings sampling on it to compute the answer set. Furthermore, we formulate the idea of network-constrained decision trees to learn prediction models that adhere to the underlying network structure. Extensive experiments on real datasets demonstrate excellent accuracy in terms of prediction quality. Additionally, MINDS achieves a speed-up of at least four orders of magnitude over baseline techniques.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 MiningDiscriminativeSubgraphsfr	Sayan Ranu Minh Hoang Ambuj Singh			Mining Discriminative Subgraphs from Global-state Networks				10.1145/2487575.2487692		2013