Single-cell sequencing, enabling the analysis of characteristics from individual cells, allows a more accurate understanding of the cellular processes that drive biological systems. With the increasing scale of single-cell data, specialized computational methods are required to address specific biological questions. We developed GeneSwitches R package to explore gene expression changes during cell state transitions and identify key modulators of the biological process, especially in the tumor microenvironment. Head and neck squamous cell carcinoma (HNSCC) is highly aggressive and diverse, with a high rate of metastases to regional lymph nodes and poor outcomes.Using single-cell RNA-seq, we identified key modulators for immune evasion during early metastasis in HNSCC. Trajectory analysis of cancer cells identified a subpopulation of pre-nodal metastatic cells, driven by actionable pathways including AXL and AURK. Blocking these two proteins blunted tumor invasion in patient-derived cultures. Furthermore, analyses of tumor-infiltrating CD8+ T cells showed two distinct trajectories to T-cell dysfunction, corroborated by their clonal architecture based on single-cell TCR-seq. We uncovered a role for SOX4 in mediating T-cell exhaustion and may improve the response to immunotherapy. Finally, interactome analyses between pre-nodal cancer cells and CD8+ T cells uncovered a putative role for the Midkine pathway to suppress CD8-mediated anti-tumor activity and abrogate re-invigoration by PD1-blockade, and thus could be targeted to improve the treatment of tumor metastasis in HNSCC.