Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2016

Abstract

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%.

Keywords

Graphic methods, Semantics, Social networking (online)

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

2016 IEEE 32nd International Conference on Data Engineering ICDE: May 16-20, Helsinki, Finland

First Page

277

Last Page

288

ISBN

9781509020195

Identifier

10.1109/ICDE.2016.7498247

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Additional URL

https://doi.ieeecomputersociety.org/10.1109/ICDE.2016.7498247

Download

Share

COinS