Recursive Attribute Factoring

Clustering, or factoring of a document collection attempts to "explain" each observed documentin terms of one or a small number of inferred prototypes. Prior work demonstrated that when links exist between documents in the corpus (as is the case with a collection of web pages or scientific papers), building a joint model of document contents and connections produces a better model than that built from contents or connections alone. Many problems arise when trying to apply these joint models to corpus at the scale of the World Wide Web, however; one of these is that the sheer overhead of representing a feature space on the order of billions of dimensions becomes impractical. Weaddress this problem with a simple representational shift inspired by probabilistic relationalmodels: instead of representing document linkage in terms of the identities of linking documents, we represent it by the explicit and inferred attributes ofthe linking documents. Several surprising results come with this shift: in addition to being computationally more tractable, the new model produces factors thatmore cleanly decompose the document collection. We discuss several variations on this model and show how some can be seen as exact generalizations of the PageRank algorithm.