Purpose: To identify functionally related prognostic gene sets for head and neck squamous cell carcinoma (HNSCC) by unsupervised statistical analysis of microarray data. Patients and Methods: Microarray analysis was performed on 14 normal oral epithelium and 71 HNSCCs from patients with outcome data. Spectral clustering (SC) analysis of the data set identified multiple vectors representing distinct aspects of gene expression heterogeneity between samples. Gene ontology (GO) analysis of vector gene lists identified gene sets significantly enriched within defined biologic pathways. The prognostic significance of these was established by Cox survival analysis. Results: The most influential SC vectors were V2 and V3. V2 separated normal from tumor samples. GO analysis of V2 gene lists identified pathways with heterogeneous expression between HNSCCs, notably focal adhesion (FA)/extracellular matrix remodeling and cytokine-cytokine receptor (CR) interactions. Similar analysis of V3 gene lists identified further heterogeneity in CR pathways. V2CR genes represent an innate immune response, whereas high expression of V3CR genes represented an adaptive immune response that was not dependent on human papillomavirus status. Survival analysis demonstrated that the FA gene set was prognostic of poor outcome, whereas classification for adaptive immune response by the CR gene set was prognostic of good outcome. A combined FA&CR model dramatically exceeded the performance of current clinical classifiers (P <.001 in our cohort and, importantly, P = .007 in an independent cohort of 60 HNSCCs). Conclusion: The application of SC and GO algorithms to HNSCC microarray data identified gene sets highly significant for predicting patient outcome. Further large-scale studies will establish the usefulness of these gene sets in the clinical management of HNSCC. © 2010 by American Society of Clinical Oncology.