Large Scale and Stable Graph Differential Analysis via Multi-Layer Node Embeddings and Ranking

1Advances in computational biology now enable the inference of increasingly accurate, genome-wide molecular interaction networks from multi-omic data collected across large cohorts. Comparing such networks across distinct biological states can identify biologically informative and potentially actionable higher-order interactions that differentiate these states. However, developing methods for effective graph differential analysis remains challenging as it requires capturing subtle structural changes within the context of complex, high-dimensional networks shaped by heterogeneous biological processes. We introduce node2vec2rank (n2v2r), a multi-layer spectral embedding algorithm that, in contrast to conventional feature-based approaches, compares graphs by inferring node representations that summarize network structure in a data-driven manner. Node2vec2rank is computationally efficient, stable, and provably recovers the correct ranking of differences between weighted graphs. We used n2v2r to compare networks from breast cancer subtypes, to analyze networks capturing single-cell dynamics, and to investigate sex differences in lung adenocarcinoma. The results of these analyses show that n2v2r is a versatile and powerful tool that can uncover biologically relevant insights from complex biological networks, distinguishing between states of health and disease.