StructSim: Querying Structural Node Similarity at Billion Scale

Chen, X; Lai, L; Qin, L; Lin, X

StructSim: Querying Structural Node Similarity at Billion Scale

Chen, X Lai, L Qin, L

Lin, X

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2020 IEEE 36th International Conference on Data Engineering (ICDE), 2020, 2020-April, pp. 1950-1953
Issue Date:: 2020-05-27

Closed Access

	Filename	Description	Size
	09101469.pdf	Published version	180.57 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	Chen, X
dc.contributor.author	Lai, L
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Lin, X
dc.date	2020-04-20
dc.date.accessioned	2021-04-13T11:00:36Z
dc.date.available	2021-04-13T11:00:36Z
dc.date.issued	2020-05-27
dc.identifier.citation	2020 IEEE 36th International Conference on Data Engineering (ICDE), 2020, 2020-April, pp. 1950-1953
dc.identifier.isbn	978-1-7281-2904-4
dc.identifier.issn	1063-6382
dc.identifier.uri	http://hdl.handle.net/10453/148068
dc.description.abstract	Structural node similarity is widely used in analyzing complex networks. As one of the structural node similarity metrics, role similarity has the good merit of indicating automorphism (isomorphism). Existing algorithms to compute role similarity (e.g., RoleSim and NED) suffer from severe performance bottlenecks, and thus cannot handle large real-world graphs. In this paper, we propose a new framework StructSim to compute nodes' role similarity. Under this framework, we prove that StructSim is guaranteed to be an admissible role similarity metric based on the maximum matching. While maximum matching is too costly to scale, we then devise the BinCount matching to speed up the computation. BinCount-based StructSim admits a precomputed index to query one single pair in O(k log D) time, where k is a small user-defined parameter and D is the maximum node degree. Extensive empirical studies show that StructSim is significantly faster than existing works for computing structural node similarities on the real-world graphs, with comparable effectiveness.
dc.language	en
dc.publisher	IEEE
dc.relation.ispartof	2020 IEEE 36th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	IEEE International Conference on Data Engineering
dc.relation.ispartofseries	IEEE International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde48307.2020.00211
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	StructSim: Querying Structural Node Similarity at Billion Scale
dc.type	Conference Proceeding
utslib.citation.volume	2020-April
utslib.location.activity	Dallas, TX, USA
utslib.for	0804 Data Format
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	*
pubs.consider-herdc	false
dc.date.updated	2021-04-13T11:00:35Z
pubs.finish-date	2020-04-24
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2020-04-20
pubs.volume	2020-April
dc.location	Piscataway, USA

Abstract:

Structural node similarity is widely used in analyzing complex networks. As one of the structural node similarity metrics, role similarity has the good merit of indicating automorphism (isomorphism). Existing algorithms to compute role similarity (e.g., RoleSim and NED) suffer from severe performance bottlenecks, and thus cannot handle large real-world graphs. In this paper, we propose a new framework StructSim to compute nodes' role similarity. Under this framework, we prove that StructSim is guaranteed to be an admissible role similarity metric based on the maximum matching. While maximum matching is too costly to scale, we then devise the BinCount matching to speed up the computation. BinCount-based StructSim admits a precomputed index to query one single pair in O(k log D) time, where k is a small user-defined parameter and D is the maximum node degree. Extensive empirical studies show that StructSim is significantly faster than existing works for computing structural node similarities on the real-world graphs, with comparable effectiveness.

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

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