Geometry of the Space of Partitioned Networks: A Unified Theoretical and Computational Framework
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909417765601280 |
|---|---|
| author | Zhang, Stephen Y Lan, Fangfei Zhou, Youjia Barbensi, Agnese Stumpf, Michael P H Wang, Bei Needham, Tom |
| author_facet | Zhang, Stephen Y Lan, Fangfei Zhou, Youjia Barbensi, Agnese Stumpf, Michael P H Wang, Bei Needham, Tom |
| contents | Interactions and relations between objects may be pairwise or higher-order in nature, and so network-valued data are ubiquitous in the real world. The "space of networks", however, has a complex structure that cannot be adequately described using conventional statistical tools. We introduce a measure-theoretic formalism for modeling generalized network structures such as graphs, hypergraphs, or graphs whose nodes come with a partition into categorical classes. We then propose a metric that extends the Gromov-Wasserstein distance between graphs and the co-optimal transport distance between hypergraphs. We characterize the geometry of this space, thereby providing a unified theoretical treatment of generalized networks that encompasses the cases of pairwise, as well as higher-order, relations. In particular, we show that our metric is an Alexandrov space of non-negative curvature, and leverage this structure to define gradients for certain functionals commonly arising in geometric data analysis tasks. We extend our analysis to the setting where vertices have additional label information, and derive efficient computational schemes to use in practice. Equipped with these theoretical and computational tools, we demonstrate the utility of our framework in a suite of applications, including hypergraph alignment, clustering and dictionary learning from ensemble data, multi-omics alignment, as well as multiscale network alignment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06302 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Geometry of the Space of Partitioned Networks: A Unified Theoretical and Computational Framework Zhang, Stephen Y Lan, Fangfei Zhou, Youjia Barbensi, Agnese Stumpf, Michael P H Wang, Bei Needham, Tom Metric Geometry Optimization and Control Machine Learning 51F99, 62R20, 49Q22, 05C65 Interactions and relations between objects may be pairwise or higher-order in nature, and so network-valued data are ubiquitous in the real world. The "space of networks", however, has a complex structure that cannot be adequately described using conventional statistical tools. We introduce a measure-theoretic formalism for modeling generalized network structures such as graphs, hypergraphs, or graphs whose nodes come with a partition into categorical classes. We then propose a metric that extends the Gromov-Wasserstein distance between graphs and the co-optimal transport distance between hypergraphs. We characterize the geometry of this space, thereby providing a unified theoretical treatment of generalized networks that encompasses the cases of pairwise, as well as higher-order, relations. In particular, we show that our metric is an Alexandrov space of non-negative curvature, and leverage this structure to define gradients for certain functionals commonly arising in geometric data analysis tasks. We extend our analysis to the setting where vertices have additional label information, and derive efficient computational schemes to use in practice. Equipped with these theoretical and computational tools, we demonstrate the utility of our framework in a suite of applications, including hypergraph alignment, clustering and dictionary learning from ensemble data, multi-omics alignment, as well as multiscale network alignment. |
| title | Geometry of the Space of Partitioned Networks: A Unified Theoretical and Computational Framework |
| topic | Metric Geometry Optimization and Control Machine Learning 51F99, 62R20, 49Q22, 05C65 |
| url | https://arxiv.org/abs/2409.06302 |