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 chal- lenging, that seeks to identify correspon- dences between vertices in network data. We present Community-Enhanced Semi-seeded Network Alignment (CESSNA), a novel al- gorithm that integrates community struc- ture and partial seed information to improve matching efficiency and accuracy. CESSNA de- composes the global matching problem into smaller, community-based blocks, enabling efficient block-wise gradient descent and re- ducing computational complexity to that of the largest non-seeded community. The method flexibly incorporates both true and inferred communities, maintaining robust- ness even in the presence of noise and lim- ited 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. Further- more, we present an innovative application of CESSNA to microbiome data, showing the capacity of this approach for robust, multi- scale 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.