Models for information propagation on graphs
This work addresses the need for theoretical frameworks in graph-based information propagation, which is incremental as it unifies existing model classes rather than introducing a new paradigm.
The paper tackles the problem of modeling information propagation on graphs by proposing and unifying three classes of models: wave-based propagation, travel-time-based propagation, and eikonal equation-based propagation, and proves equivalences between them, with applications to semi-supervised learning and trust networks.
We propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave which emanates from a set of \emph{known} nodes at an initial time, to all other \emph{unknown} nodes at later times with an ordering determined by the arrival time of the information wave front. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial \emph{known} set of nodes to a node is defined as the minimum of a generalised travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each \emph{unknown} node, with boundary conditions at the \emph{known} nodes. The solution value of the local equation at a node is coupled to those of neighbouring nodes with lower values. We provide precise formulations of the model classes and prove equivalences between them. Finally we apply the front propagation models on graphs to semi-supervised learning via label propagation and information propagation on trust networks.