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

Sijing Yu, Daniel L. Sussman, Vince Lyzinski
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1801-1809, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-yu26a, title = { Community-Enhanced Semi-seeded Network Alignment (CESSNA): A Robust Method with Application to Microbiome Networks }, author = {Yu, Sijing and Sussman, Daniel L. and Lyzinski, Vince}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1801--1809}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/yu26a/yu26a.pdf}, url = {https://proceedings.mlr.press/v300/yu26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Community-Enhanced Semi-seeded Network Alignment (CESSNA): A Robust Method with Application to Microbiome Networks %A Sijing Yu %A Daniel L. Sussman %A Vince Lyzinski %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-yu26a %I PMLR %P 1801--1809 %U https://proceedings.mlr.press/v300/yu26a.html %V 300 %X 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.
APA
Yu, S., Sussman, D.L. & Lyzinski, V.. (2026). Community-Enhanced Semi-seeded Network Alignment (CESSNA): A Robust Method with Application to Microbiome Networks . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1801-1809 Available from https://proceedings.mlr.press/v300/yu26a.html.

Related Material