Efficient and Accurate Label Propagation on Dynamic Graphs and Label Sets
Venue
International Journal on Advances in Networks and Services, vol. 6 (2013), pp. 246-259
Publication Year
2013
Authors
Michele Covell, Shumeet Baluja
BibTeX
Abstract
Many web-based application areas must infer label distributions starting from a
small set of sparse, noisy labels. Previous work has shown that graph-based
propagation can be very effective at finding the best label distribution across
nodes, starting from partial information and a weighted-connection graph. In their
work on video recommendations, Baluja et al. showed high-quality results using
Adsorption, a normalized propagation process. An important step in the original
formulation of Adsorption was re-normalization of the label vectors associated with
each node, between every propagation step. That interleaved normalization forced
computation of all label distributions, in synchrony, in order to allow the
normalization to be correctly determined. Interleaved normalization also prevented
use of standard linear-algebra methods, like stabilized bi-conjugate gradient
descent (BiCGStab) and Gaussian elimination. We show how to replace the interleaved
normalization with a single pre-normalization, done once before the main
propagation process starts, allowing use of selective label computation (label
slicing) as well as large-matrix-solution methods. As a result, much larger graphs
and label sets can be handled than in the original formulation and more accurate
solutions can be found in fewer propagation steps. We further extend that work to
handle graphs that change and expand over time. We report results from using
pre-normalized Adsorption in topic labeling for web domains, using label slicing
and BiCGStab. We also report results from using incremental updates on changing
co-author network data. Finally, we discuss two options for handling mixed-sign
(positive and negative) graphs and labels.
