Semantic proximity search on graphs with metagraph-based learning

Yuan Fang, Wenqing Lin, Vincent W. Zheng, Min Wu, Kevin Chen Chuan Chang, Xiao Li Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given ubiquitous graph data such as the Web and social networks, proximity search on graphs has been an active research topic. The task boils down to measuring the proximity between two nodes on a graph. Although most earlier studies deal with homogeneous or bipartite graphs only, many real-world graphs are heterogeneous with objects of various types, giving rise to different semantic classes of proximity. For instance, on a social network two users can be close for different reasons, such as being classmates or family members, which represent two distinct classes of proximity. Thus, it becomes inadequate to only measure a generic form of proximity as previous works have focused on. In this paper, we identify metagraphs as a novel and effective means to characterize the common structures for a desired class of proximity. Subsequently, we propose a family of metagraph-based proximity, and employ a supervised technique to automatically learn the right form of proximity within its family to suit the desired class. As it is expensive to match (i.e., find the instances of) a metagraph, we propose the novel approaches of dual-stage training and symmetry-based matching to speed up. Finally, our experiments reveal that our approach is significantly more accurate and efficient. For accuracy, we outperform the baselines by 11% and 16% in NDCG and MAP, respectively. For efficiency, dual-stage training reduces the overall matching cost by 83%, and symmetry-based matching further decreases the cost of individual metagraphs by 52%.

Original languageEnglish (US)
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781509020195
StatePublished - Jun 22 2016
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: May 16 2016May 20 2016

Publication series

Name2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016


Other32nd IEEE International Conference on Data Engineering, ICDE 2016

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management


Dive into the research topics of 'Semantic proximity search on graphs with metagraph-based learning'. Together they form a unique fingerprint.

Cite this