TY - JOUR

T1 - Effective graph-neural-network based models for discovering Structural Hole Spanners in large-scale and diverse networks

AU - Goel, Diksha

AU - Shen, Hong

AU - Tian, Hui

AU - Guo, Mingyu

N1 - Publisher Copyright:
© 2024 The Author(s)

PY - 2024/9/1

Y1 - 2024/9/1

N2 - A Structural Hole Spanner (SHS) is a set of nodes in a network that act as a bridge among different otherwise disconnected communities. While several solutions exist for SHS discovery, they often suffer from high runtime, particularly in large-scale networks. Additionally, discovering SHSs across diverse networks poses another challenge, as the traditional one-model-fits-all approach fails to capture inter-graph differences, especially in diverse networks. Therefore, there is an urgent need of developing effective solutions for discovering SHSs in large-scale and diverse networks. Inspired by the recent advancement of graph neural network approaches on various graph problems, we propose graph neural network-based models to discover SHS nodes in large-scale and diverse networks. Our approach transform the problem into a learning problem and propose an efficient model GraphSHS, that exploits both the network structure and node features to discover SHS nodes in large scale networks, endeavouring to lessen the computational cost while maintaining high accuracy. To effectively discover SHSs across diverse networks, we propose another model Meta-GraphSHS based on meta-learning that learns generalizable knowledge from diverse training graphs (instead of directly learning the model) and utilizes the learned knowledge to create a customized model to identify SHSs in each new graph. Theoretically, we demonstrate that the depth of the proposed graph neural network model should be at least Ω(n/logn) to accurately calculate the SHSs discovery problem. We evaluate the performance of the proposed models through extensive experiments on synthetic and real-world datasets. Our experimental results show that GraphSHS discovers SHSs with high accuracy and is at least 167.1 times faster than the comparative methods on large-scale real-world datasets. Furthermore, Meta-GraphSHS effectively discovers SHSs across diverse synthetic networks with an accuracy of 96.2%.

AB - A Structural Hole Spanner (SHS) is a set of nodes in a network that act as a bridge among different otherwise disconnected communities. While several solutions exist for SHS discovery, they often suffer from high runtime, particularly in large-scale networks. Additionally, discovering SHSs across diverse networks poses another challenge, as the traditional one-model-fits-all approach fails to capture inter-graph differences, especially in diverse networks. Therefore, there is an urgent need of developing effective solutions for discovering SHSs in large-scale and diverse networks. Inspired by the recent advancement of graph neural network approaches on various graph problems, we propose graph neural network-based models to discover SHS nodes in large-scale and diverse networks. Our approach transform the problem into a learning problem and propose an efficient model GraphSHS, that exploits both the network structure and node features to discover SHS nodes in large scale networks, endeavouring to lessen the computational cost while maintaining high accuracy. To effectively discover SHSs across diverse networks, we propose another model Meta-GraphSHS based on meta-learning that learns generalizable knowledge from diverse training graphs (instead of directly learning the model) and utilizes the learned knowledge to create a customized model to identify SHSs in each new graph. Theoretically, we demonstrate that the depth of the proposed graph neural network model should be at least Ω(n/logn) to accurately calculate the SHSs discovery problem. We evaluate the performance of the proposed models through extensive experiments on synthetic and real-world datasets. Our experimental results show that GraphSHS discovers SHSs with high accuracy and is at least 167.1 times faster than the comparative methods on large-scale real-world datasets. Furthermore, Meta-GraphSHS effectively discovers SHSs across diverse synthetic networks with an accuracy of 96.2%.

KW - Diverse networks

KW - Graph neural networks

KW - Large-scale networks

KW - Meta-learning

KW - Neural networks

KW - Structural Hole Spanners

UR - http://www.scopus.com/inward/record.url?scp=85188715815&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2024.123636

DO - 10.1016/j.eswa.2024.123636

M3 - Article

AN - SCOPUS:85188715815

SN - 0957-4174

VL - 249

JO - Expert Systems with Applications

JF - Expert Systems with Applications

M1 - 123636

ER -