Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2019

Abstract

Data in the form of graphs are prevalent, ranging from biological and social networks to citation graphs and the Web. Inparticular, most real-world graphs are heterogeneous, containing objects of multiple types, which present new opportunities for manyproblems on graphs. Consider a typical proximity search problem on graphs, which boils down to measuring the proximity between twogiven nodes. Most earlier studies on homogeneous or bipartite graphs only measure a generic form of proximity, without accounting fordifferent “semantic classes”—for instance, on a social network two users can be close for different reasons, such as being classmates orfamily members, which represent two distinct semantic classes. Learning these semantic classes are made possible on heterogeneousgraphs through the concept of metagraphs. In this study, we identify metagraphs as a novel and effective means to characterize thecommon structures for a desired class of proximity. Subsequently, we propose a family of metagraph-based proximity, and employ alearning-to-rank technique that automatically learns the right parameters to suit the desired semantic class. In terms of efficiency, wedevelop a symmetry-based matching algorithm to speed up the computation of metagraph instances. Empirically, extensive experimentsreveal that our metagraph-based proximity substantially outperforms the best competitor by more than 10%, and our matching algorithmcan reduce matching time by more than half. As a further generalization, we aim to derive a general node and edge representationfor heterogeneous graphs, in order to support arbitrary machine learning tasks beyond proximity search. In particular, we propose thefiner-grained anchored metagraph, which is capable of discriminating the roles of nodes within the same metagraph. Finally, furtherexperiments on the general representation show that we can outperform the state of the art significantly and consistently across variousmachine learning tasks.

Keywords

Semantic Proximity Search, Meta-structures, Graph Mining, Heterogeneous Graph Representation

Discipline

Computer Engineering | Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

First Page

1

Last Page

15

ISSN

1041-4347

Identifier

10.1109/TKDE.2019.2922956

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Additional URL

https://doi.org/10.1109/TKDE.2019.2922956

Download

Share

COinS