Metagraph-based learning on heterogeneous graphs

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

Full description

Saved in:
Bibliographic Details
Main Authors: FANG, Yuan, LIN, Wenqing, ZHENG, Vincent W., WU, Min, SHI, Jiaqi, CHANG, Kevin, LI, Xiao-Li
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/4726
https://ink.library.smu.edu.sg/context/sis_research/article/5729/viewcontent/TKDE19_MG.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5729
record_format dspace
spelling sg-smu-ink.sis_research-57292020-01-16T10:46:56Z Metagraph-based learning on heterogeneous graphs FANG, Yuan LIN, Wenqing ZHENG, Vincent W. WU, Min SHI, Jiaqi CHANG, Kevin LI, Xiao-Li 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. 2019-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4726 info:doi/10.1109/TKDE.2019.2922956 https://ink.library.smu.edu.sg/context/sis_research/article/5729/viewcontent/TKDE19_MG.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Semantic Proximity Search Meta-structures Graph Mining Heterogeneous Graph Representation Computer Engineering Databases and Information Systems
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Semantic Proximity Search
Meta-structures
Graph Mining
Heterogeneous Graph Representation
Computer Engineering
Databases and Information Systems
spellingShingle Semantic Proximity Search
Meta-structures
Graph Mining
Heterogeneous Graph Representation
Computer Engineering
Databases and Information Systems
FANG, Yuan
LIN, Wenqing
ZHENG, Vincent W.
WU, Min
SHI, Jiaqi
CHANG, Kevin
LI, Xiao-Li
Metagraph-based learning on heterogeneous graphs
description 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.
format text
author FANG, Yuan
LIN, Wenqing
ZHENG, Vincent W.
WU, Min
SHI, Jiaqi
CHANG, Kevin
LI, Xiao-Li
author_facet FANG, Yuan
LIN, Wenqing
ZHENG, Vincent W.
WU, Min
SHI, Jiaqi
CHANG, Kevin
LI, Xiao-Li
author_sort FANG, Yuan
title Metagraph-based learning on heterogeneous graphs
title_short Metagraph-based learning on heterogeneous graphs
title_full Metagraph-based learning on heterogeneous graphs
title_fullStr Metagraph-based learning on heterogeneous graphs
title_full_unstemmed Metagraph-based learning on heterogeneous graphs
title_sort metagraph-based learning on heterogeneous graphs
publisher Institutional Knowledge at Singapore Management University
publishDate 2019
url https://ink.library.smu.edu.sg/sis_research/4726
https://ink.library.smu.edu.sg/context/sis_research/article/5729/viewcontent/TKDE19_MG.pdf
_version_ 1770575012487495680