Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach

Wu, X; Xu, Y; Zhang, W; Zhang, Y

Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach

Wu, X Xu, Y Zhang, W Zhang, Y

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2023, 17, (2), pp. 175-183
Issue Date:: 2023-01-01

Closed Access

	Filename	Description	Size
	VLDB_2024_bipartite_graph_embedding.pdf	Published version	1.81 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	Wu, X
dc.contributor.author	Xu, Y
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date.accessioned	2024-03-04T03:38:32Z
dc.date.available	2024-03-04T03:38:32Z
dc.date.issued	2023-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2023, 17, (2), pp. 175-183
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/176056
dc.description.abstract	Bipartite graph embedding (BGE), as the fundamental task in bipartite network analysis, is to map each node to compact lowdimensional vectors that preserve intrinsic properties. The existing solutions towards BGE fall into two groups: metric-based methods and graph neural network-based (GNN-based) methods. The latter typically generates higher-quality embeddings than the former due to the strong representation ability of deep learning. Nevertheless, none of the existing GNN-based methods can handle billion-scale bipartite graphs due to the expensive message passing or complex modelling choices. Hence, existing solutions face a challenge in achieving both embedding quality and model scalability. Motivated by this, we propose a novel graph neural network named AnchorGNN based on global-local learning framework, which can generate high-quality BGE and scale to billion-scale bipartite graphs. Concretely, AnchorGNN leverages a novel anchor-based message passing schema for global learning, which enables global knowledge to be incorporated to generate node embeddings. Meanwhile, AnchorGNN offers an efficient one-hop local structure modelling using maximum likelihood estimation for bipartite graphs with rational analysis, avoiding large adjacency matrix construction. Both global information and local structure are integrated to generate distinguishable node embeddings. Extensive experiments demonstrate that AnchorGNN outperforms the best competitor by up to 36% in accuracy and achieves up to 28 times speed-up against the only metric-based baseline on billion-scale bipartite graphs.
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation	http://purl.org/au-research/grants/arc/LP210301046
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation	http://purl.org/au-research/grants/arc/DP240101322
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3626292.3626300
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.subject.classification	4605 Data management and data science
dc.title	Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach
dc.type	Journal Article
utslib.citation.volume	17
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
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	2024-03-04T03:38:31Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	17
utslib.citation.issue	2

Abstract:

Bipartite graph embedding (BGE), as the fundamental task in bipartite network analysis, is to map each node to compact lowdimensional vectors that preserve intrinsic properties. The existing solutions towards BGE fall into two groups: metric-based methods and graph neural network-based (GNN-based) methods. The latter typically generates higher-quality embeddings than the former due to the strong representation ability of deep learning. Nevertheless, none of the existing GNN-based methods can handle billion-scale bipartite graphs due to the expensive message passing or complex modelling choices. Hence, existing solutions face a challenge in achieving both embedding quality and model scalability. Motivated by this, we propose a novel graph neural network named AnchorGNN based on global-local learning framework, which can generate high-quality BGE and scale to billion-scale bipartite graphs. Concretely, AnchorGNN leverages a novel anchor-based message passing schema for global learning, which enables global knowledge to be incorporated to generate node embeddings. Meanwhile, AnchorGNN offers an efficient one-hop local structure modelling using maximum likelihood estimation for bipartite graphs with rational analysis, avoiding large adjacency matrix construction. Both global information and local structure are integrated to generate distinguishable node embeddings. Extensive experiments demonstrate that AnchorGNN outperforms the best competitor by up to 36% in accuracy and achieves up to 28 times speed-up against the only metric-based baseline on billion-scale bipartite graphs.

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

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