Human papillomavirus-related (p16-positive) oropharyngeal squamous cell carcinoma patients develop recurrent disease, mostly distant metastasis, in approximately 10% of cases, and the remaining patients, despite cure, can have major morbidity from treatment. Identifying patients with aggressive versus indolent tumors is critical. Hematoxylin and eosin-stained slides of a microarray cohort of p16-positive oropharyngeal squamous cell carcinoma cases were digitally scanned. A novel cluster cell graph was constructed using the nuclei as vertices to characterize and measure spatial distribution and cell clustering. A series of topological features defined on each node of the subgraph were analyzed, and a random forest decision tree classifier was developed. The classifier (QuHbIC) was validated over 25 runs of 3-fold cross-validation using case subsets for independent training and testing. Nineteen (11.9%) of the 160 patients on the array developed recurrence. QuHbIC correctly predicted outcomes in 140 patients (87.5% accuracy). There were 23 positive patients, of whom 11 developed recurrence (47.8% positive predictive value), and 137 negative patients, of whom only 8 developed recurrence (94.2% negative predictive value). The best other predictive features were stage T4 (18 patients; 83.1% accuracy) and N3 nodal disease (10 patients; 88.6% accuracy). QuHbIC-positive patients had poorer overall, disease-free, and disease-specific survival (P<0.001 for each). In multivariate analysis, QuHbIC-positive patients still showed significantly poorer disease-free and disease-specific survival, independent of all other variables. In summary, using just tiny hematoxylin and eosin punches, a computer-aided histomorphometric classifier (QuHbIC) can strongly predict recurrence risk. With prospective validation, this testing may be useful to stratify patients into different treatment groups.