Exploring building blocks of cell organization by estimating network motifs using graph isomorphism network

The spatial arrangement of cells within tissues plays a pivotal role in shaping tissue functions. A critical spatial pattern is network motif as the building blocks of cell organization. Network motifs can be represented as recurring significant interconnections of cells with various types in a spatial cell-relation graph, i.e., enriched occurrences of isomorphic subgraphs in the graph, which is computationally infeasible to have an optimal solution with large-size (>3 nodes) subgraphs. We introduce Triangulation Network Motif Neural Network (TrimNN), a neural network-based approach designed to estimate the prevalence of network motifs of any size in a triangulated cell graph. TrimNN simplifies the intricate task of occurrence regression by decomposing it into several binary present/absent predictions on small graphs. TrimNN is trained using representative pairs of predefined subgraphs and triangulated cell graphs to estimate overrepresented network motifs. On typical spatial omics samples within thousands of cells in dozens of cell types, TrimNN robustly infers the presence of a large-size network motif in seconds. In a case study using STARmap Plus technologies, TrimNN identified several biological meaningful large-size network motifs significantly enriched in a mouse model of Alzheimers disease at different months of age. TrimNN provides an accurate, efficient, and robust approach for quantifying network motifs, which helps pave the way to disclose the biological mechanisms underlying cell organization in multicellular differentiation, development, and disease progression.