hide
Free keywords:
-
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.
