Purpose <p>Despite the success of immune checkpoint inhibitors (ICIs) that target immunosuppressive interactions, treatment resistance remains a major clinical challenge. The tumor microenvironment is comprised of tumor, immune, and stromal cell types that communicate through secreted and cell surface proteins. This can be represented by a weighted, directed network where pairs of cell types communicate via multiple ligand-receptor interactions with varying strengths. Identifying interaction network motifs that are linked with outcome or evolve pre- to post-ICI presents a rational framework to identify combination therapeutic targets.</p> Methods <p>Interaction inference was performed on publicly available single-cell RNA-sequencing data from melanoma patients. The constructed patient-specific networks were input to multivariate statistical learning approaches to identify network motifs that predicted response pre-treatment and that shifted pre- to post-treatment. Relevance of interactions was validated by (1) differential expression of related pathways in single cell RNA sequencing (scRNA-seq) data, (2) survival associations in an independent bulk RNA-seq dataset, and (3) repeated analyses of scRNA-seq data in a second cohort.</p> Results <p>Immune-immune interactions with roles in T cell activation, chemotaxis, and adhesion were upregulated in patients who respond to therapy pre-treatment. Related pathways were perturbed in involved immune cells and expression of these genes was associated with improved survival. The interactome also distinguished pre- and post-treatment biopsies with high accuracy despite no significant differences in individual interactions. Analysis in the validation dataset with mixed responses pre-treatment recapitulated results from the discovery analyses.</p> Conclusion <p>Unbiased analysis of interaction networks and their evolution is a powerful framework to guide prognostic indicators and novel combination targets to improve patient outcomes.</p>