Neural Subgraph Counting with Wasserstein Estimator

Wang, H; Hu, R; Zhang, Y; Qin, L; Wang, W; Zhang, W

Neural Subgraph Counting with Wasserstein Estimator

Wang, H Hu, R Zhang, Y

Qin, L

Wang, W Zhang, W

Permalink

Publisher:: ASSOC COMPUTING MACHINERY
Publication Type:: Conference Proceeding
Citation:: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022, pp. 160-175
Issue Date:: 2022-06-10

Closed Access

	Filename	Description	Size
	SIGMOD_22_2.pdf	Accepted version	1.63 MB	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	Wang, H
dc.contributor.author	Hu, R
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Wang, W
dc.contributor.author	Zhang, W
dc.date	2022-06-12
dc.date.accessioned	2023-01-13T03:53:33Z
dc.date.available	2023-01-13T03:53:33Z
dc.date.issued	2022-06-10
dc.identifier.citation	Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022, pp. 160-175
dc.identifier.isbn	9781450392495
dc.identifier.issn	0730-8078
dc.identifier.uri	http://hdl.handle.net/10453/164958
dc.description.abstract	Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness. In this paper, we propose a novel approximate subgraph counting algorithm, NeurSC, that can exploit and combine information from both the query graphs and the data graphs effectively and efficiently. It consists of two components: (1) an extraction module that adaptively generates simple yet representative substructures from data graph for each query graph and (2) an estimator WEst that first computes the representations from individual and joint distributions of query and data graphs and then estimates subgraph counts with the learned representations. Furthermore, we design a novel Wasserstein discriminator in WEst to minimize the Wasserstein distance between query and data graphs by updating the parameters in network with the vertex correspondence relationship between query and data graphs. By doing this, WEst can better capture the correlation between query and data graphs which is essential to the quality of the estimation. We conduct experimental studies on seven large real-life labeled graphs to demonstrate the superior performance of NeurSC in terms of estimation accuracy and robustness.
dc.language	en
dc.publisher	ASSOC COMPUTING MACHINERY
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP210101347
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	Proceedings of the ACM SIGMOD International Conference on Management of Data
dc.relation.ispartof	International Conference on Management of Data (SIGMOD)
dc.relation.ispartofseries	International Conference on Management of Data
dc.relation.isbasedon	10.1145/3514221.3526163
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Neural Subgraph Counting with Wasserstein Estimator
dc.type	Conference Proceeding
utslib.location.activity	Philadelphia, PA
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/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
dc.date.updated	2023-01-13T03:53:32Z
pubs.finish-date	2022-06-17
pubs.publication-status	Published
pubs.start-date	2022-06-12

Abstract:

Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness. In this paper, we propose a novel approximate subgraph counting algorithm, NeurSC, that can exploit and combine information from both the query graphs and the data graphs effectively and efficiently. It consists of two components: (1) an extraction module that adaptively generates simple yet representative substructures from data graph for each query graph and (2) an estimator WEst that first computes the representations from individual and joint distributions of query and data graphs and then estimates subgraph counts with the learned representations. Furthermore, we design a novel Wasserstein discriminator in WEst to minimize the Wasserstein distance between query and data graphs by updating the parameters in network with the vertex correspondence relationship between query and data graphs. By doing this, WEst can better capture the correlation between query and data graphs which is essential to the quality of the estimation. We conduct experimental studies on seven large real-life labeled graphs to demonstrate the superior performance of NeurSC in terms of estimation accuracy and robustness.

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

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