Exponential Family Graph Matching and Ranking
  We present a method for learning max-weight matching predictors in bipartite
graphs. The method consists of performing maximum a posteriori estimation in
exponential families with sufficient statistics that encode permutations and
data features. Although inference is in general hard, we show that for one very
relevant application - web page ranking - exact inference is efficient. For
general model instances, an appropriate sampler is readily available. Contrary
to existing max-margin matching models, our approach is statistically
consistent and, in addition, experiments with increasing sample sizes indicate
superior improvement over such models. We apply the method to graph matching in
computer vision as well as to a standard benchmark dataset for learning web
page ranking, in which we obtain state-of-the-art results, in particular
improving on max-margin variants. The drawback of this method with respect to
max-margin alternatives is its runtime for large graphs, which is comparatively
high.
