GraphPropagation

Method

According to Velikovich_et_al,_NAACL_2010, this is a technique for propagating weights/flow over a graph, from say, a set of seeds.

You have a graph defined from data; for example, in Blair-Goldensohn_et_al,_2008 it's WordNet synonyms and antonyms; or in Velikovich_et_al,_NAACL_2010 it's web-derived distributional similarities. Starting with seed nodes' scores, the algorithm involves repeated matrix-multiplications with the edge matrix to propagate the flow. So at each step, a node's new flow strength (weight? score?) $f_{j}$ is the discounted sum of incoming flow:

$f_{j}\ :=\alpha \sum _{i}e_{ij}f_{i}$

for node $j$ with incoming neighbors $i$ and graph edge weights $e_{ij}$ and per-node flow $f_{i}$, and a discount factor $0<\alpha <1$.

(My apologies if this is bad terminology, I'm not sure the right way to do it)

This method is related to many other techniques in the literature; for example, PageRank and random walks.