Computing hypergraph homology

Xiang Liu; Huitao Feng; Jie Wu; Kelin Xia

doi:10.3934/fods.2024007

Article Contents

2024, Volume 6, Issue 2: 172-194. Doi: 10.3934/fods.2024007

This issue Previous Article Robust crossings detection in noisy signals using topological signal processing Next Article Algebraic topology and distributed computing

Computing hypergraph homology

1.
Chern Institute of Mathematics, Nankai University, China
2.
Mathematical Science Research Center, Chongqing University of Technology, China
3.
Beijing Institute of Mathematical Sciences and Applications, China
4.
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

^*Corresponding author: Kelin Xia
^*Corresponding author: Kelin Xia

Received: October 2023

Revised: January 2024

Early access: March 12, 2024

Published online: March 12, 2024

Abstract / Introduction Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

As a generalization of graphs and simplicial complexes, hypergraphs have various applications in chemistry, biology, computer science and data science. Recently, the first well-defined hypergraph-based embedded homology and persistent (embedded) homology models have been proposed and achieved great success in drug design. However, the further applications of these models have been significantly hindered by the lack of efficient computational algorithms. In this paper, we propose an algorithm for embedded homology and persistent (embedded) homology of hypergraphs over field coefficient. One of the key issues for hypergraph-based homology models is the absence of proper boundary operators as in traditional simplicial complex-based models. A supremum/infimum chain complex has been proposed in the embedded homology model with well-defined boundary operators. Here we give detailed algorithms for transforming a filtered hypergraph to its filtered infimum chain complex and supremum chain complex. In this way, the general algorithm for chain complex can be used directly on the supremum/infimum chain complexes. Our algorithm has been validated on hypergraph models of protein structures from the protein data bank. It has been found that our algorithm is very robust and efficient.

Keywords:

Mathematics Subject Classification: Primary: 55N31, 62R40; Secondary: 68T09.

Citation:

Full Text(HTML)

Table 1. A hypergraph $ \mathcal{H} $ and its associated simplicial complex $ K_{\mathcal{H}} $, infimum chain complex $ Inf_*(\mathcal{H}) $, supremum chain complex $ Sup_*(\mathcal{H}) $, embedded homology $ {\rm H}_*(\mathcal{H}) $ and the homology of $ K_{\mathcal{H}} $

	0-D	1-D	2-D	$ n $-D ($ n>2 $)
$ \mathcal{H} $	$ \{v_0\},\{v_1\},\{v_2\} $	$ \{v_0,v_1\} $	$ \{v_0,v_1,v_2\} $	$ \emptyset $
$ K_{\mathcal{H}} $	$ \{v_0\},\{v_1\},\{v_2\} $	$ \{v_0,v_1\},\{v_0,v_2\},\{v_1,v_2\} $	$ \{v_0,v_1,v_2\} $	$ \emptyset $
$ Inf_*(\mathcal{H}) $	$ \mathbb{Z}( \{v_0\},\{v_1\},\{v_2\} ) $	$ \mathbb{Z}( \{v_0,v_1\}) $	0	0
$ Sup_*(\mathcal{H}) $	$ \mathbb{Z}( \{v_0\},\{v_1\},\{v_2\} ) $	$ \mathbb{Z}( \{v_0,v_1\},\partial{\{v_0,v_1,v_2\}}) $	$ \mathbb{Z}( \{v_0,v_1,v_2\} ) $	0
$ {\rm H}_*(\mathcal{H}) $	$ \mathbb{Z}\bigoplus\mathbb{Z} $	0	0	0
$ {\rm H}_*(K_{\mathcal{H}}) $	$ \mathbb{Z} $	0	0	0

| Show Table

DownLoad: CSV

Table 2. Performance comparison between our algorithms and existing one on protein-ligand complex data. The unit for filtration value is Å. The third column is the number of hyperedges, the 4-6 columns are the running time for our algorithms and existing one. The unit of time is second

PDBID	filtration	No. hyperedges	Time($ Sup_^ $)	Time$ (Inf_^) $	Time([32])
1A1C	7.0	478	0.01	0.47	0.27
1A1C	8.0	1028	0.04	2.99	1.18
1A1C	9.0	1912	0.13	12.59	3.84
1A0Q	7.0	419	0.01	0.36	0.20
1A0Q	8.0	825	0.03	1.84	0.75
1A0Q	9.0	1618	0.10	8.59	2.64
3AID	7.0	565	0.01	0.62	0.41
3AID	8.0	1299	0.06	4.47	1.89
3AID	9.0	2520	0.23	21.66	6.61

| Show Table

DownLoad: CSV

Table 3. Performance of our algorithm on protein-ligand complex data. The unit for filtration value is Å. The third column lists the number of hyperedges of the hypergraphs. The last column is the computational time (seconds)

PDBID	No. atoms	filtration	No. hyperedges	Time
1YDK	383	9.0	8140	2.23
1YDK	383	10.0	15681	9.45
1YDK	383	11.0	29619	51.59
1ALW	227	9.0	7213	1.77
1ALW	227	10.0	14137	7.12
1ALW	227	11.0	26068	32.93
1A69	388	9.0	7493	1.94
1A69	388	10.0	15367	9.62
1A69	388	11.0	31343	61.68

| Show Table

DownLoad: CSV

Table 4. Performance of our algorithm on protein data. The unit for filtration (fil) value is Å. The number of atoms, residues and hyperedges ($ \mathcal{H} $) are listed in the second, third and fifth columns respectively. $ \beta_{0,1,2}(\mathcal{H}) $ and $ \beta_{0,1,2}(K_\mathcal{H}) $ are the betti numbers $ (\beta_0,\beta_1,\beta_2) $ for the hypergraphs and their associated simplicial complexes. The last column is the computational time (seconds)

PDBID	No. atoms	No. residues	fil	No. $ \mathcal{H} $	$ \beta_{0,1,2}(\mathcal{H}) $	$ \beta_{0,1,2}(K_\mathcal{H}) $	Time
1C26	305	32	5.0	13500	(305, 50, 8648)	(305, 65, 8648)	5.29
1C26	305	32	6.0	32187	(305, 51, 24604)	(305, 65, 24604)	41.93
1C26	305	32	6.5	45166	(305, 51, 36184)	(305, 65, 36184)	89.81
1BU4	879	105	4.0	14954	(879,251, 6095)	(879,314, 6095)	7.04
1BU4	879	105	4.5	26617	(879,270, 14192)	(879,337, 14192)	35.33
1BU4	879	105	5.0	50372	(879,272, 32655)	(879,341, 32655)	129.92
1P38	2949	351	3.0	18097	(2949,279, 2860)	(2949,327, 2860)	7.51
1P38	2949	351	3.5	28582	(2949,500, 7993)	(2949,614, 7993)	25.98
1P38	2949	351	4.0	51103	(2949,777, 21008)	(2949,934, 21008)	104.86
6M00	2296	294	3.0	14442	(2296,164, 2313)	(2296,201, 2313)	4.65
6M00	2296	294	3.5	22885	(2296,332, 6523)	(2296,441, 6523)	14.73
6M00	2296	294	4.0	39425	(2296,543, 16230)	(2296,663, 16230)	55.57

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Adams, A. Tausz and M. Vejdemo-Johansson, Javaplex: A research software package for persistent (co) homology, in International Congress on Mathematical Software, Springer, 2014,129-136. doi: 10.1007/978-3-662-44199-2_23.
[2]	S. Bai, F. Zhang and P. H. S. Torr, Hypergraph convolution and hypergraph attention, Pattern Recognition, 110 (2021), 107637. doi: 10.1016/j.patcog.2020.107637.
[3]	U. Bauer, Ripser: A lean C++ code for the computation of Vietoris-Rips persistence barcodes, Software available at https://github.com/Ripser/ripser.
[4]	U. Bauer, M. Kerber and J. Reininghaus, Distributed computation of persistent homology, in 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2014, 31-38. doi: 10.1137/1.9781611973198.4.
[5]	U. Bauer, M. Kerber and J. Reininghaus, Clear and compress: Computing persistent homology in chunks, in Topological Methods in Data Analysis and Visualization III, Springer, 2014,103-117. doi: 10.1007/978-3-319-04099-8_7.
[6]	U. Bauer, M. Kerber and J. Reininghaus, Dipha (a distributed persistent homology algorithm), Software available at https://github.com/DIPHA/dipha.
[7]	U. Bauer, M. Kerber, J. Reininghaus and H. Wagner, Phat–persistent homology algorithms toolbox, Journal of Symbolic Computation, 78 (2017), 76-90. doi: 10.1016/j.jsc.2016.03.008.
[8]	U. Bauer and M. Schmahl, Efficient computation of image persistence, 39th International Symposium on Computational Geometry, Art. No. 14, 14 pp, arXiv preprint, arXiv: 2201.04170. doi: 10.4230/lipics.socg.2023.14.
[9]	J.-D. Boissonnat and C. Maria, Computing persistent homology with various coefficient fields in a single pass, Journal of Applied and Computational Topology, 3 (2019), 59-84. doi: 10.1007/s41468-019-00025-y.
[10]	S. Bressan, J. Li, S. Ren and J. Wu, The embedded homology of hypergraphs and applications, Asian Journal of Mathematics, 23 (2019), 479-500. doi: 10.4310/AJM.2019.v23.n3.a6.
[11]	G. Carlsson and V. de Silva, Zigzag persistence, Foundations of Computational Mathematics, 10 (2010), 367-405. doi: 10.1007/s10208-010-9066-0.
[12]	G. Carlsson, V. de Silva and D. Morozov, Zigzag persistent homology and real-valued functions, in Proc. 25th Annu. ACM Sympos. Comput. Geom., 2009,247-256. doi: 10.1145/1542362.1542408.
[13]	C. Chen and M. Kerber, Persistent homology computation with a twist, Proceedings 27th European Workshop on Computational Geometry, 11 (2011), 197-200.
[14]	S. Chowdhury and F. Mémoli, Persistent homology of asymmetric networks: An approach based on dowker filtrations, arXiv preprint, arXiv: 1608.05432.
[15]	F. R. K. Chung and R. L. Graham, Cohomological aspects of hypergraphs, Transactions of the American Mathematical Society, 334 (1992), 365-388. doi: 10.1090/S0002-9947-1992-1089416-0.
[16]	V. de Silva, D. Morozov and M. Vejdemo-Johansson, Persistent cohomology and circular coordinates, Discrete and Comput. Geom., 45 (2011), 737-759. doi: 10.1007/s00454-011-9344-x.
[17]	T. K. Dey, F. Fan and Y. Wang, Computing topological persistence for simplicial maps, in Proc. 30th Annu. Sympos. Comput. Geom. (SoCG), 2014,345-354. doi: 2014.
[18]	P. Dłotko and H. Wagner, Simplification of complexes for persistent homology computations, Homology, Homotopy and Applications, 16 (2014), 49-63. doi: 10.4310/HHA.2014.v16.n1.a3.
[19]	H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Soc., 2010. doi: 10.1090/mbk/069.
[20]	H. Edelsbrunner, D. Letscher and A. Zomorodian, Topological persistence and simplification, Discrete Comput. Geom., 28 (2002), 511-533. doi: 10.1007/s00454-002-2885-2.
[21]	E. Emtander, Betti numbers of hypergraphs, Communications in Algebra, 37 (2009), 1545-1571. doi: 10.1080/00927870802098158.
[22]	Y. Feng, H. You, Z. Zhang, R. Ji and Y. Gao, Hypergraph neural networks, Proceedings of the AAAI Conference on Artificial Intelligence, 33 (2019), 3558-3565. doi: 10.1609/aaai.v33i01.33013558.
[23]	A. Grigor'yan, R. Jimenez, Y. Muranov and S.-T. Yau, On the path homology theory of digraphs and Eilenberg–Steenrod axioms, Homology, Homotopy and Applications, 20 (2018), 179-205. doi: 10.4310/HHA.2018.v20.n2.a9.
[24]	A. Grigor'yan, R. Jimenez, Y. Muranov and S.-T. Yau, Homology of path complexes and hypergraphs, Topology and its Applications, 267 (2019), 106877. doi: 10.1016/j.topol.2019.106877.
[25]	A. Grigor'yan, Y. Lin, Y. Muranov and S.-T. Yau, Cohomology of digraphs and (undirected) graphs, Asian Journal of Mathematics, 19 (2015), 887-932. doi: 10.4310/AJM.2015.v19.n5.a5.
[26]	A. Grigor'yan, Y. V. Muranov and S.-T. Yau, Graphs associated with simplicial complexes, Homology, Homotopy and Applications, 16 (2014), 295-311. doi: 10.4310/HHA.2014.v16.n1.a16.
[27]	B. Hendrickson and T. G. Kolda, Graph partitioning models for parallel computing, Parallel Computing, 26 (2000), 1519-1534. doi: 10.1016/S0167-8191(00)00048-X.
[28]	J. Jiang, Y. Wei, Y. Feng, J. Cao and Y. Gao, Dynamic hypergraph neural networks, in IJCAI, 2019, 2635-2641. doi: 10.24963/ijcai.2019/366.
[29]	S. Klamt, U.-U. Haus and F. Theis, Hypergraphs and cellular networks, PLoS Computational Biology, 5 (2009), e1000385. doi: 10.1371/journal.pcbi.1000385.
[30]	E. V. Konstantinova and V. A. Skorobogatov, Application of hypergraph theory in chemistry, Discrete Mathematics, 235 (2001), 365-383. doi: 10.1016/S0012-365X(00)00290-9.
[31]	X. Liu, H. Feng, J. Wu and K. Xia, Persistent spectral hypergraph based machine learning (PSH-ML) for protein-ligand binding affinity prediction, Briefings in Bioinformatics, 22 (2021), bbab127. doi: 10.1093/bib/bbab127.
[32]	X. Liu, X. Wang, J. Wu and K. Xia, Hypergraph based persistent cohomology (HPC) for molecular representations in drug design, Briefings in Bioinformatics, 22 (2021), bbaa411. doi: 10.1093/bib/bbaa411.
[33]	C. Maria, J.-D. Boissonnat, M. Glisse and M. Yvinec, The gudhi library: Simplicial complexes and persistent homology, in International Congress on Mathematical Software, Springer, 2014,167-174. doi: 10.1007/978-3-662-44199-2_28.
[34]	C. Maria and S. Y. Oudot, Zigzag persistence via reflections and transpositions, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014,181-199. doi: 10.1137/1.9781611973730.14.
[35]	C. Maria and H. Schreiber, Discrete morse theory for computing zigzag persistence, in Workshop on Algorithms and Data Structures, Springer, 2019,538-552. doi: 10.1007/978-3-030-24766-9_39.
[36]	N. Milosavljević, D. Morozov and P. Škraba, Zigzag persistent homology in matrix multiplication time, in Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, 2011,216-225. doi: 10.1145/1998196.1998229.
[37]	K. Mischaikow and V. Nanda, Morse theory for filtrations and efficient computation of persistent homology, Discrete & Computational Geometry, 50 (2013), 330-353. doi: 10.1007/s00454-013-9529-6.
[38]	D. Morozov, Dionysus, Software available at http://www.mrzv.org/software/dionysus.
[39]	V. Nanda, Perseus: The persistent homology software, Software available at http://www.sas.upenn.edu/vnanda/perseus.
[40]	A. D. Parks and S. L. Lipscomb, Homology and hypergraph acyclicity: A combinatorial invariant for hypergraphs, Technical report, Naval Surface Warfare Center Dahlgren VA, 1991. doi: 10.21236/ADA241584.
[41]	S. Ren, Persistent homology for hypergraphs and computational tools-a survey for users, Journal of Knot Theory and Its Ramifications, 29 (2020), 2043007. doi: 10.1142/S0218216520430075.
[42]	S. Ren, C. Wang, C. Wu and J. Wu, A discrete morse theory for hypergraphs, arXiv preprint, arXiv: 1804.07132.
[43]	S. Ren, C. Wu and J. Wu, Hodge decompositions for weighted hypergraphs, arXiv preprint, arXiv: 1805.11331.
[44]	S. Ren and J. Wu, Stability of persistent homology for hypergraphs, arXiv preprint, arXiv: 2002.02237.
[45]	A. Zomorodian and G. Carlsson, Computing persistent homology, Discrete Comput. Geom., 33 (2005), 249-274. doi: 10.1007/s00454-004-1146-y.