Efficient Probabilistic Supergraph Search

Zhang, W; Lin, X; Zhang, Y; Zhu, K; Zhu, G

Efficient Probabilistic Supergraph Search

Zhang, W Lin, X Zhang, Y

Zhu, K Zhu, G

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (4), pp. 965 - 978
Issue Date:: 2016-04-01

Closed Access

	Filename	Description	Size
	TKDE_2016_uncertain_graph.pdf	Accepted Manuscript Version	960.28 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Zhu, K	en_US
dc.contributor.author	Zhu, G	en_US
dc.date.issued	2016-04-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (4), pp. 965 - 978	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/44060
dc.description.abstract	© 2015 IEEE. Given a query graph q, retrieving the data graphs g from a set D of data graphs such that q contains g, namely supergraph containment search, is fundamental in graph data analysis with a wide range of real applications. It is very challenging due to the NP-Completeness of subgraph isomorphism testing. Driven by many real applications, in this paper, we study the problem of probabilistic supergraph search; that is, given a set D of uncertain data graphs, a certain query graph q and a probability threshold θ, we retrieve the data graphs gu from D such that the probability of q containing gu is not smaller than θ. We show that besides the NP-Completeness of subgraph isomorphism testing, the problem of calculating probabilities is #P-Complete; thus, it is even more challenging than the supergraph containment search. To tackle the computational hardness, we first propose two novel pruning rules, based on probabilistic connectivity and features, respectively, to efficiently prune non-promising data graphs. Then, efficient verification algorithms are developed with the aim of sharing computation and terminating non-promising computation as early as possible. Extensive performance studies on both real and synthetic data demonstrate the efficiency and effectiveness of our techniques in practice.	en_US
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2015.2499201	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Efficient Probabilistic Supergraph Search	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.citation.volume	28	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	080109 Pattern Recognition and Data Mining	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	28	en_US

Abstract:

© 2015 IEEE. Given a query graph q, retrieving the data graphs g from a set D of data graphs such that q contains g, namely supergraph containment search, is fundamental in graph data analysis with a wide range of real applications. It is very challenging due to the NP-Completeness of subgraph isomorphism testing. Driven by many real applications, in this paper, we study the problem of probabilistic supergraph search; that is, given a set D of uncertain data graphs, a certain query graph q and a probability threshold θ, we retrieve the data graphs gu from D such that the probability of q containing gu is not smaller than θ. We show that besides the NP-Completeness of subgraph isomorphism testing, the problem of calculating probabilities is #P-Complete; thus, it is even more challenging than the supergraph containment search. To tackle the computational hardness, we first propose two novel pruning rules, based on probabilistic connectivity and features, respectively, to efficiently prune non-promising data graphs. Then, efficient verification algorithms are developed with the aim of sharing computation and terminating non-promising computation as early as possible. Extensive performance studies on both real and synthetic data demonstrate the efficiency and effectiveness of our techniques in practice.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/44060