  We propose a model for online graph problems where algorithms are given
access to an oracle that predicts (e.g., based on modeling assumptions or on
past data) the degrees of nodes in the graph. Within this model, we study the
classic problem of online bipartite matching, and a natural greedy matching
algorithm called MinPredictedDegree, which uses predictions of the degrees of
offline nodes. For the bipartite version of a stochastic graph model due to
Chung, Lu, and Vu where the expected values of the offline degrees are known
and used as predictions, we show that MinPredictedDegree stochastically
dominates any other online algorithm, i.e., it is optimal for graphs drawn from
this model. Since the "symmetric" version of the model, where all online nodes
are identical, is a special case of the well-studied "known i.i.d. model", it
follows that the competitive ratio of MinPredictedDegree on such inputs is at
least 0.7299. For the special case of graphs with power law degree
distributions, we show that MinPredictedDegree frequently produces matchings
almost as large as the true maximum matching on such graphs. We complement
these results with an extensive empirical evaluation showing that
MinPredictedDegree compares favorably to state-of-the-art online algorithms for
online matching.
