Graffiti: graph-based classification in heterogeneous networks |
| |
Authors: | Ralitsa Angelova Gjergji Kasneci Gerhard Weikum |
| |
Affiliation: | (1) Microsoft Research Asia, Sigma Center, No.49, Zhichun Road, Haidian District, Beijing, 100190, People’s Republic of China;(2) Beijing Jiaotong University, No.3, Shangyuan Residence, Haidian District, Beijing, 100044, People’s Republic of China;(3) Academy of Mathematics and Systems Science, Chinese Academy of Sciences, No.55, Zhongguancun East Road, Haidian District, Beijing, 100190, People’s Republic of China |
| |
Abstract: | We address the problem of multi-label classification in heterogeneous graphs, where nodes belong to different types and different
types have different sets of classification labels. We present a novel approach that aims to classify nodes based on their
neighborhoods. We model the mutual influence of nodes as a random walk in which the random surfer aims at distributing class
labels to nodes while walking through the graph. When viewing class labels as “colors”, the random surfer is essentially spraying
different node types with different color palettes; hence the name Graffiti of our method. In contrast to previous work on
topic-based random surfer models, our approach captures and exploits the mutual influence of nodes of the same type based
on their connections to nodes of other types. We show important properties of our algorithm such as convergence and scalability.
We also confirm the practical viability of Graffiti by an experimental study on subsets of the popular social networks Flickr and LibraryThing. We demonstrate the superiority of our approach by comparing it to three other state-of-the-art techniques for graph-based
classification. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|