I haven't read the paper either ;] (just skimmed bibliography to get a sense, as I usually do first) but Arora (one of the authors) is an expert on probabilistic approximations, and they do cite 2001 paper by Feige which is standard ref. on approximations to dense subgraph. Also, what they reduce their model to is a "planted" hidden clique variant of dense subgraph, a problem which is hard "on average" and not only in worst case (propety used in crypto protocols also).