Persistent hyperdigraph homology and persistent hyperdigraph Laplacians

Dong Chen; Jian Liu; Jie Wu; Guo-Wei Wei

doi:10.3934/fods.2023010

Article Contents

2023, Volume 5, Issue 4: 558-588. Doi: 10.3934/fods.2023010

This issue Previous Article Hierarchical regularization networks for sparsification based learning on noisy datasets Next Article

Persistent hyperdigraph homology and persistent hyperdigraph Laplacians

1.
Department of Mathematics, Michigan State University, MI, 48824, USA
2.
Mathematical Science Research Center, Chongqing University of Technology, Chongqing 400054, China
3.
Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing 101408, China
4.
Department of Electrical and Computer Engineering, Michigan State University, MI 48824, USA
5.
Department of Biochemistry and Molecular Biology, Michigan State University, MI 48824, USA

^*Corresponding author: Jie Wu, wujie@bimsa.cn
^*Corresponding author: Jie Wu, wujie@bimsa.cn;
^*Corresponding author: Jie Wu, wujie@bimsa.cn^*Corresponding author: Guo-Wei Wei, weig@msu.edu
^*Corresponding author: Guo-Wei Wei, weig@msu.edu

Received: April 2023

Revised: August 2023

Early access: September 2023

Published: December 2023

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

Abstract

Hypergraphs are useful mathematical models for describing complex relationships among members of a structured graph, while hyperdigraphs serve as a generalization that can encode asymmetric relationships in the data. However, obtaining topological information directly from hyperdigraphs remains a challenge. To address this issue, we introduce hyperdigraph homology in this work. We also propose topological hyperdigraph Laplacians, which can extract both harmonic spectra and non-harmonic spectra from directed and internally organized data. Moreover, we introduce persistent hyperdigraph homology and persistent hyperdigraph Laplacians through filtration, enabling the capture of topological persistence and homotopic shape evolution of directed and structured data across multiple scales. The proposed methods offer new multiscale algebraic topology tools for topological data analysis.

Keywords:

Mathematics Subject Classification: Primary: 55N31; Secondary: 05C65, 18G85.

Citation:

Full Text(HTML)

Figure 1. a Illustration of hypergraph $ \mathcal{H} $ in Example 2.7. b, c, and d Illustration of 0-hyperedges, 1-hyperedges, and 2-hyperedges, respectively. The solid black vertices indicate 0-hyperedges, purple edges indicate 1-hyperedges, and pink areas indicate 2-hyperedges. The dashed hollow circle indicates a vertex that is not 0-hyperedge

Download: Full-size image PowerPoint slide

Figure 2. a Illustration of hyperdigraph $ \vec{\mathcal{H}} $ in Example 3.16. b, c, and d Illustration of directed 0-hyperedges, directed 1-hyperedges, and directed 2-hyperedges, respectively. The solid black vertices indicate 0-hyperedges and the dashed hollow circle indicates a vertex that is not a directed 0-hyperedge. The yellow background combined with directed edges represents directed 1-hyperedges. The green background combined with 2 consecutive directed edges represents directed 2-hyperedges. Here, the dashed arrows indicate the directed edges that do not exist

Download: Full-size image PowerPoint slide

Figure 3. a Persistent hypergraph of 6-vertex system ($ \vec{\mathcal{H}} $). The distances between the relevant vertices are $ D_{45} = D_{12} = 6 $, $ D_{05} = D_{01} = D_{23} = D_{34} = \sqrt{5} $, and $ D_{24} = D_{15} = 4 $. b Persistent hyperdigraph ($ \mathcal{\vec{H}} $) of 6-vertex system. The distances between the corresponding vertices are the same as a

Download: Full-size image PowerPoint slide

Figure 4. Comparison of persistent hypergraph Laplacians and persistent hyperdigraph Laplacians. The hollow square markers ($ \mathcal{\vec{H}} $) and circle markers ($ \mathcal{H} $) in each subfigure correspond to the five filtration stages in Figure 3, i.e., $ \mathcal{\vec{H}}_1 $, $ \mathcal{\vec{H}}_2 $, ..., $ \mathcal{\vec{H}}_5 $. and $ \mathcal{H}_1 $, $ \mathcal{H}_2 $, ..., $ \mathcal{H}_5 $

Download: Full-size image PowerPoint slide

Figure 5. a Persistent hypergraph Laplacians of a 6-vertex system ($ \mathcal{H} $). All vertices come from the vertices of a regular hexagon with sides of length 2, i.e., $ D_{01} = D_{12} = D_{23} = D_{34} = D_{45} = D_{50} = 2 $. b Comparison of Betti numbers ($ \beta_{0} $, $ \beta_{1} $, and $ \beta_{2} $) and the smallest eigenvalue of the non-harmonic spectra ($ \lambda_{0} $, $ \lambda_{1} $, and $ \lambda_{2} $) of persistent hypergraph Laplacians. c Persistent hyperdigraph Laplacians of a 6-vertex system ($ \vec{\mathcal{H}} $). The distances between the corresponding vertices are the same as a. d Comparison of Betti numbers ($ \beta_{0} $, $ \beta_{1} $, and $ \beta_{2} $) and the smallest eigenvalue of the non-harmonic spectra ($ \lambda_{0} $, $ \lambda_{1} $, and $ \lambda_{2} $) of persistent hyperdigraph Laplacians. The corresponding Betti numbers can not tell the changes from $ \mathcal{H}_3 $ to $ \mathcal{H}_4 $ and $ \vec{\mathcal{H}}_3 $ to $ \vec{\mathcal{H}}_4 $, while the $ \lambda_{0} $, $ \lambda_{1} $, and $ \lambda_{2} $ can capture the difference

Download: Full-size image PowerPoint slide

Figure 6. Illustration of the hyperdigraph Laplacian analysis and hypergraph Laplacian analysis for two B$ _7 $C$ _2 $H$ _9 $ isomers in a and b. The first column shows the structural representation of B$ _7 $C$ _2 $H$ _9 $. The second column shows the structural representations after removing the H atoms. The third column shows the hyperdigraph representations of two structures, and the last column shows the hypergraph representations of two structures. The results in the last two columns indicate that hyperdigraph Laplacians, rather than hypergraph Laplacians, can distinguish two isomers

Download: Full-size image PowerPoint slide

Figure 7. Illustration of the persistent hyperdigraph Laplacian analysis of a protein-ligand complex (PDB ID: 1a99). a Illustration of a filtration-induced topological hyperdigraph. Only C-atoms within 4 Å from the ligand are considered for the protein structure (brown dots). The green line segment indicates the directed 1-hyperedges and the orange line indicates the directed 2-hyperedges. b The three dimensional structure of the protein-ligand complex. c and d Betti numbers $ \beta_n $ ($ n $ = 0, 1, 2) and the smallest eigenvalues of non-harmonic spectra $ \lambda_n $ ($ n $ = 0, 1, 2) of persistent hyperdigraph Laplacian for the protein-ligand complex

Download: Full-size image PowerPoint slide

Table 1. Topological Laplacians on different objects

Homologies	notation	restriction	topological Laplacians
graph	$ G=(V,E) $, $ E\subseteq {\bf{P}}_{2}(V) $	none	graph Laplacian
simplicial complex	$ \mathcal{K}=(V,K) $, $ K\subseteq {\bf{P}}(V) $	$ \partial_{\ast}K\subseteq K $	combinatorial Laplacian
digraph	$ G=(V,E) $, $ E\subseteq {\bf{S}}_{2}(V) $	none	path Laplacian
path complex	$ \mathcal{P}=(V,P) $, $ P\subseteq {\bf{\tilde{S}}}(V) $	$ \partial_{0}P,\partial_{\infty}P\subseteq P $	path Laplacian
hypergraph	$ \mathcal{H}=(V,E) $, $ E\subseteq {\bf{P}}(V) $	none	hypergraph Laplacian
hyperdigraph	$ \vec{\mathcal{H}}=(V,\vec{E}) $, $ \vec{E}\subseteq {\bf{S}}(V) $	none	hyperdigraph Laplacian

| Show Table

DownLoad: CSV

Table 2. Illustration of hyperdigraph in Example 3.18

$ n $	$ n=0 $	$ n=1 $	$ n=2 $
$ B_{n+1} $	$ \left(\begin{array}{ccc} -1&1&0\\-1&0&1\\1&-1&0\\0&-1&1\\1&0&-1\\0&1&-1\\\end{array} \right) $	$ \left( \begin{array}{cccccc} 1&-1&0&1&0&0\\-1&1&0&0&0&1\\0&1&1&-1&0&0\\0&0&-1&1&1&0\\1&0&0&0&1&-1\\0&0&1&0&-1&1\\\end{array} \right) $	$ 6\times 0 $ empty matrix
$ L_{n} $	$ \left( \begin{array}{ccc} 4&-2&-2\\-2&4&-2\\-2&-2&4\\\end{array} \right) $	$ \left( \begin{array}{cccccc} 5&-1&-2&0&0&-1\\-1&5&0&-1&-2&0\\-2&0&5&-1&-1&0\\0&-1&-1&5&0&-2\\0&-2&-1&0&5&-1\\-1&0&0&-2&-1&5\\\end{array} \right) $	$ \left( \begin{array}{cccccc} 3&-2&-2&1&1&0\\-2&3&1&0&-2&1\\-2&1&3&-2&0&1\\1&0&-2&3&1&-2\\1&-2&0&1&3&-2\\0&1&1&-2&-2&3\\\end{array} \right) $
$ \beta_{n} $	1	0	2
$ {\bf{Spec}}(L_{n}) $	{0, 6, 6}	{1, 4, 4, 6, 6, 9}	{0, 0, 1, 4, 4, 9}

| Show Table

DownLoad: CSV

Table 3. Illustration of hyperdigraph in Example 3.19

$ n $	$ n=0 $	$ n=1 $	$ n=2 $
$ B_{n+1} $	$ 0\times 3 $ empty matrix	$ \left( \begin{array}{ccc} -\frac{1}{2}&\frac{3}{2\sqrt{5}}&- \frac{\sqrt{13}}{\sqrt{10}}\\\end{array} \right) $	$ 6\times 0 $ empty matrix
$ L_{n} $	none	$ \left( \begin{array}{ccc} \frac{1}{4}&-\frac{3}{4\sqrt{5}}&\frac{\sqrt{13}}{2\sqrt{10}}\\-\frac{3}{4\sqrt{5}}&\frac{9}{20}&-\frac{3\sqrt{13}}{10\sqrt{2}}\\\frac{\sqrt{13}}{2\sqrt{10}}&-\frac{3\sqrt{13}}{10\sqrt{2}}&\frac{13}{10}\\\end{array} \right) $	2
$ \beta_{n} $	0	2	0
$ {\bf{Spec}}(L_{n}) $	none	{0, 0, 2}	{2}

| Show Table

DownLoad: CSV

Table 4. The Betti numbers and spectra for the volume-based filtration of hyperdigraphs in Example 4.4

$ \mathcal{H}^{f}(t) $	Betti numbers			Spectra
$ \mathcal{H}^{f}(t) $	$ \beta_{0} $	$ \beta_{1} $	$ \beta_{2} $	$ p=0 $	$ p=1 $	$ p=2 $
$ t=0 $	3	0	0	{0, 0, 0}	none	none
$ t=\sqrt{2} $	2	0	0	{0, 0, 2}	{2}	none
$ t=\sqrt{3} $	2	0	0	{0, 0, 2}	{2}	none
$ t=\sqrt{5} $	1	0	0	{0, 3, 3}	{3, 3, 3}	{3}

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Y. Akhremtsev, T. Heuer, P. Sanders and S. Schlag, Engineering a direct $k$-way hypergraph partitioning algorithm, In 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, (2017), 28-42. doi: 10.1137/1.9781611974768.3.
[2]	B. Ameneyro, V. Maroulas and G. Siopsis, Quantum persistent homology, arXiv preprint, arXiv: 2202.12965, 2022.
[3]	D. N. Arnold, R. S. Falk and R. Winther, Finite element exterior calculus, homological techniques, and applications, Acta Numerica, 15 (2006), 1-155. doi: 10.1017/S0962492906210018.
[4]	G. Ausiello and L. Laura, Directed hypergraphs: Introduction and fundamental algorithms–A survey, Theoretical Computer Science, 658 (2017), 293-306. doi: 10.1016/j.tcs.2016.03.016.
[5]	C. Berge, Hypergraphs: Combinatorics of Finite Sets, volume 45, Elsevier, 1984.
[6]	C. Berge and E. Minieka, Graphs and Hypergraphs, Graphs and Hypergraphs. North-Holland Publishing Company, 1973. ISBN 9780444103994. https://books.google.com.sg/books?id=X32GlVfqXjsC.
[7]	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.
[8]	P. Bubenik and P. Dłotko, A persistence landscapes toolbox for topological statistics, Journal of Symbolic Computation, 78 (2017), 91-114. doi: 10.1016/j.jsc.2016.03.009.
[9]	Z. Cang and G.-W. Wei, Topologynet: Topology based deep convolutional and multi-task neural networks for biomolecular property predictions, PLoS Computational Biology, 13 (2017), e1005690. doi: 10.1371/journal.pcbi.1005690.
[10]	Z. Cang and G.-W. Wei, Persistent cohomology for data with multicomponent heterogeneous information, SIAM Journal on Mathematics of Data Science, 2 (2020), 396-418. doi: 10.1137/19M1272226.
[11]	G. Carlsson, Topology and data, Bulletin of the American Mathematical Society, 46 (2009), 255-308. doi: 10.1090/S0273-0979-09-01249-X.
[12]	D. Chen, J. Liu, J. Wu, G.-W. Wei, F. Pan and S.-T. Yau, Path topology in molecular and materials sciences, The Journal of Physical Chemistry Letters, 14 (2023), 954-964. doi: 10.1021/acs.jpclett.2c03706.
[13]	J. Chen, Y. Qiu, R. Wang and G.-W. Wei, Persistent Laplacian projected Omicron BA.4 and BA.5 to become new dominating variants, Computers in Biology and Medicine, 151 (2022), 106262. doi: 10.1016/j.compbiomed.2022.106262.
[14]	J. Chen, R. Zhao, Y. Tong and G.-W. Wei, Evolutionary de Rham-Hodge method, arXiv: 1912.12388, 2019. doi: 10.48550/arXiv.1912.12388.
[15]	J. Chen, R. Zhao, Y. Tong and G.-W. Wei, Evolutionary de Rham-Hodge method, Discrete and Continuous Dynamical Systems. Series B, 26 (2021), 3785-3821. doi: 10.3934/dcdsb.2020257.
[16]	M. Desbrun, A. N. Hirani, M. Leok and J. E. Marsden, Discrete exterior calculus, arXiv preprint, arXiv: math/0508341, 2005.
[17]	W. Dörfler and D. A. Waller, A category-theoretical approach to hypergraphs, Archiv der Mathematik, 34 (1980), 185-192. doi: 10.1007/BF01224952.
[18]	H. Edelsbrunner and J. Harer, Persistent homology-a survey, Contemporary Mathematics, 453 (2008), 257-282. doi: 10.1090/conm/453/08802.
[19]	T. Eiter and G. Gottlob, Hypergraph transversal computation and related problems in logic and AI, In Logics in Artificial Intelligence: 8th European Conference, JELIA 2002 Cosenza, Italy, September 23-26, 2002 Proceedings 8, 549-564. Springer, 2002. doi: 10.1007/3-540-45757-7_53.
[20]	M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23 (1973), 298-305. doi: 10.21136/CMJ.1973.101168.
[21]	G. Gallo, G. Longo, S. Pallottino and S. Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, 42 (1993), 177-201. doi: 10.1016/0166-218X(93)90045-P.
[22]	G. Gallo and M. G. Scutella, Directed hypergraphs as a modelling paradigm, Rivista di Matematica per le Scienze Economiche e Sociali, 21 (1998), 97-123. doi: 10.1007/BF02735318.
[23]	A. Gomes and D. Miranda, Path cohomology of locally finite digraphs, Hodge's theorem and the $ p $-lazy random walk, arXiv preprint, arXiv: 1906.04781, 2019.
[24]	J. Grbic, J. Wu, K. Xia and G.-W. Wei, Aspects of topological approaches for data science, Foundations of Data Science, 4 (2022), 165-216. doi: 10.3934/fods.2022002.
[25]	A. Grigor'yan, Y. Lin, Y. Muranov and S.-T. Yau, Homologies of path complexes and digraphs, arXiv preprint, arXiv: 1207.2834, 2013.
[26]	A. Grigor'yan, Y. Lin, Yu. V. Muranov and S. Yau, Path complexes and their homologies, Journal of Mathematical Sciences, 248 (2020), 564-599. doi: 10.1007/s10958-020-04897-9.
[27]	A. Grigor'yan, Y. Muranov and S.-T. Yau, Homologies of digraphs and Künneth formulas, Communications in Analysis and Geometry, 25 (2017), 969-1018. doi: 10.4310/CAG.2017.v25.n5.a4.
[28]	J. Hansen and R. Ghrist, Toward a spectral theory of cellular sheaves, Journal of Applied and Computational Topology, 3 (2019), 315-358. doi: 10.1007/s41468-019-00038-7.
[29]	F. Harary and E. M. Palmer, Graphical Enumeration, Elsevier, 2014.
[30]	A. N. Hirani, Discrete Exterior Calculus, California Institute of Technology, 2003.
[31]	D. Horak and J. Jost, Spectra of combinatorial Laplace operators on simplicial complexes, Advances in Mathematics, 244 (2013), 303-336. doi: 10.1016/j.aim.2013.05.007.
[32]	T. Kaczynski, K. M. Mischaikow and M. Mrozek, Computational Homology, volume 3., Springer, 2004. doi: 10.1007/b97315.
[33]	G. Kirchhoff, Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird, Annalen der Physik, 148 (1847), 497-508. doi: 10.1002/andp.18471481202.
[34]	J. Liu, J. Li and J. Wu, The algebraic stability for persistent Laplacians, arXiv preprint, arXiv: 2302.03902, 2023.
[35]	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.
[36]	F. Mémoli, Z. Wan and Y. Wang, Persistent Laplacians: Properties, algorithms and implications, SIAM Journal on Mathematics of Data Science, 4 (2022), 858-884. doi: 10.1137/21M1435471.
[37]	Z. Meng and K. Xia, Persistent spectral–based machine learning (PerSpect ML) for protein-ligand binding affinity prediction, Science Advances, 7 (2021), eabc5329. doi: 10.1126/sciadv.abc5329.
[38]	Y. Muranov, A. Szczepkowska and V. Vershinin, Path homology of directed hypergraphs, Homology Homotopy Appl., 24 (2022), 347–363, arXiv preprint, arXiv: 2109.09842, 2021. doi: 10.4310/HHA.2022.v24.n2.a18.
[39]	Y. Qiu and G.-W. Wei, Persistent spectral theory-guided protein engineering, Nature Computational Science, 3 (2023), 149-163. doi: 10.1038/s43588-022-00394-y.
[40]	R. Qu, J. Wang, Z.-s. Li and Y.-R. Bao, Encoding hypergraphs into quantum states, Physical Review A, 87 (2013), 022311. doi: 10.1103/PhysRevA.87.022311.
[41]	M. Ramaswamy, S. Sarkar and Y.-S. Chen, Using directed hypergraphs to verify rule-based expert systems, IEEE Transactions on Knowledge and Data Engineering, 9 (1997), 221-237. doi: 10.1109/69.591448.
[42]	S. Ren, C. Wang, C. Wu and J. Wu, A discrete Morse theory for hypergraphs, arXiv preprint, arXiv: 1804.07132, 2020.
[43]	S. Ren, C. Wu and J. Wu, Hodge decompositions for weighted hypergraphs, arXiv preprint, arXiv: 1805.11331, 2018.
[44]	M. Thakur and R. Tripathi, Linear connectivity problems in directed hypergraphs, Theoretical Computer Science, 410 (2009), 2592-2618. doi: 10.1016/j.tcs.2009.02.038.
[45]	J. Townsend, C. P. Micucci, J. H. Hymel, V. Maroulas and K. D. Vogiatzis., Representation of molecular structures with persistent homology for machine learning applications in chemistry, Nature Communications, 11 (2020), 3230. doi: 10.1038/s41467-020-17035-5.
[46]	R. Wang, D. D. Nguyen and G.-W. Wei, Persistent spectral graph, Int. J. Numer. Methods Biomed. Eng., 36 (2020), e3376, 27 pp, arXiv preprint, arXiv: 1912.04135, 2019. doi: 10.1002/cnm.3376.
[47]	R. Wang and G.-W. Wei, Persistent path Laplacian, Foundations of Data Science, 5 (2023), 26-55. doi: 10.3934/fods.2022015.
[48]	R. Wang, R. Zhao, E. Ribando-Gros, J. Chen, Y. Tong and G.-W. Wei, HERMES: Persistent spectral graph software, Foundations of Data Science, 3 (2021), 67-97. doi: 10.3934/fods.2021006.
[49]	J. Wee, G. Bianconi and K. Xia, Persistent Dirac for molecular representation, Scientific Reports, 13 (2023), Article number: 11183, arXiv preprint, arXiv: 2302.02386, 2023. doi: 10.1038/s41598-023-37853-z.
[50]	J. Wee and K. Xia, Persistent spectral based ensemble learning (PerSpect-EL) for protein–protein binding affinity prediction, Briefings in Bioinformatics, 23 (2022). doi: 10.1093/bib/bbac024.
[51]	G.-W. Wei, Topological data analysis hearing the shapes of drums and bells, arXiv preprint, arXiv: 2301.05025, 2023.
[52]	X. Wei, J. Chen and G.-W. Wei, Persistent topological Laplacian analysis of SARS-CoV-2 variants, J. Comput. Biophys. Chem., 22 (2023), 569-587. doi: 10.1142/S2737416523500278.
[53]	X. Wei and G.-W. Wei, Persistent sheaf Laplacians, Found. Data Sci., 5 (2023), 26–55, arXiv preprint, arXiv: 2112.10906, 2021. doi: 10.3934/fods.2022015.
[54]	A. Zomorodian and G. Carlsson, Computing persistent homology, In Proceedings of the Twentieth Annual Symposium on Computational Geometry, (2004), 347-356. doi: 10.1145/997817.997870.