Community-Enhanced Semi-seeded Network Alignment (CESSNA): A Robust Method with Application to Microbiome Networks

Network alignment (i.e., graph matching) is a fundamental, though computationally challenging, problem that seeks to identify correspondences between vertices in network data. We present Community-Enhanced Semi-seeded Network Alignment (CESSNA), a novel algorithm that integrates community structure and partial seed information to improve matching efficiency and accuracy. CESSNA decomposes the global matching problem into smaller, community-based blocks, enabling efficient block-wise gradient descent and reducing computational complexity to that of the largest non-seeded community. The method flexibly incorporates both true and inferred communities, maintaining robustness even in the presence of noise and limited seed data. Experiments on synthetic and real-world datasets demonstrate that CESSNA consistently outperforms traditional seeded and unseeded graph matching approaches, achieving up to a 46-fold increase in accuracy over state-of-the-art methods without any seeds on the Wikipedia dataset. Furthermore, we present an innovative application of CESSNA to microbiome data, showing the capacity of this approach for robust, multiscale graph comparison in complex network data. These findings highlight the potential of CESSNA for addressing a broad spectrum of non-traditional network alignment problems, and emphasize CESSNA’s ability to accomplish efficient and accurate network alignment and its utility for uncovering new insights in biologically hierarchical data.