Geometry of the space of partitioned networks: a unified theoretical and computational framework

Abstract Network data are ubiquitous in the real world, capturing pairwise and high-order relations among objects. We introduce a class of measure-theoretic network objects, termed partitioned measure networks, that generalize many existing representations of network data, including graphs, hypergraphs and augmented graphs (i.e. graphs whose nodes are associated with categorical classes). We then propose a metric, the partitioned network distance, between partitioned measure networks, which extends both the Gromov-Wasserstein distance for graphs and the co-optimal transport distance for hypergraphs. By characterizing the geometry of the space of partitioned measure networks, we provide a unified theoretical treatment of generalized network structures encompassing both pairwise and higher-order relations. In particular, we show that this metric endows the space with an Alexandrov geometry of non-negative curvature and leverages this structure to define gradients for certain functionals commonly encountered in geometric data analysis. We further extend our framework to incorporate node-level label information and derive efficient computational schemes for utilizing the partitioned network distance in practice. Equipped with these theoretical and computational advances, we demonstrate the utility of our framework across diverse applications, including hypergraph alignment, clustering and dictionary learning from ensemble data, multi-omics alignment, as well as multiscale network alignment.