The problems of object classification (labeling the nodes of a graph) and link prediction (predicting the links in a graph) have been largely studied independently. Com- monly, object classification is performed assuming a com- plete set of known links and link prediction is done assum- ing a fully observed set of node attributes. In most real world domains, however, attributes and links are often miss- ing or incorrect. Object classification is not provided with all the links relevant to correct classification and link pre- diction is not provided all the labels needed for accurate link prediction. In this paper, we propose an approach that addresses these two problems by interleaving object clas- sification and link prediction in a collective algorithm. We investigate empirically the conditions under which an inte- grated approach to object classification and link prediction improves performance, and find that performance improves over a wide range of network types, and algorithm settings.