Persistent Dirac of paths on digraphs and hypergraphs

Faisal Suwayyid; Guo-Wei Wei

doi:10.3934/fods.2024001

Article Contents

2024, Volume 6, Issue 2: 124-153. Doi: 10.3934/fods.2024001

This issue Previous Article Next Article Robust crossings detection in noisy signals using topological signal processing

Persistent Dirac of paths on digraphs and hypergraphs

Faisal Suwayyid^{1, 2,} and
Guo-Wei Wei^{2, 3, 4, ,}

1.
Department of Mathematics, King Fahd University of Petroleum and Minerals, Dhahran 31261, KSA
2.
Department of Mathematics, Michigan State University, MI 48824, USA
3.
Department of Electrical and Computer Engineering, Michigan State University, MI 48824, USA
4.
Department of Biochemistry and Molecular Biology, Michigan State University, MI 48824, USA

^*Corresponding author: Guo-Wei Wei
^*Corresponding author: Guo-Wei Wei

Received: December 2023

Revised: January 2024

Early access: January 22, 2024

Published online: January 22, 2024

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

Abstract

This work introduces the development of path Dirac and hypergraph Dirac operators, along with an exploration of their persistence. These operators excel in distinguishing between harmonic and non-harmonic spectra, offering valuable insights into the subcomplexes within these structures. The paper showcases the functionality of these operators through a series of examples in various contexts. An essential facet of this research involves examining the operators' sensitivity to filtration, emphasizing their capacity to adapt to topological changes. The paper also explores a significant application of persistent path Dirac and persistent hypergraph Dirac in molecular science, specifically in analyzing molecular structures. The study introduces strict preorders derived from molecular structures, which generate graphs and digraphs with intricate path structures. The depth of information within these path complexes reflects the complexity of different preorder classes influenced by molecular structures. This characteristic underscores the effectiveness of these tools in the realm of topological data analysis.

Keywords:

Persistent hypergraph Dirac,
persistent digraph Dirac,
topological data analysis,
spectral data analysis,
simultaneous geometric and topological analyses.

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

Citation:

Full Text(HTML)

Figure 1. The essential subgraphs that generate the second-degree component of the chain complex of path complex induced by digraphs. (A) shows an essential triangle, (B) an essential square where $ v_1\neq v_1' $, and (C) an essential fork-like in digraphs

Download: Full-size image PowerPoint slide

Figure 2. Two digraphs to demonstrate the Dirac operator's ability to distinguish between them

Download: Full-size image PowerPoint slide

Figure 3. The essential subgraphs that contribute to generating the second-degree hypergraph complex component. (A) shows an essential triangle, (B) an essential square where $ v_1\neq v_1' $, and (C) an essential fork-like in hypergraphs

Download: Full-size image PowerPoint slide

Figure 4. Three hypergraphs inducing the same complex: (A) a hypergraph $ G $, (B) a sub-hypergraph obtained by maximal hyperedges only, and (C) $ G $ essential graph

Download: Full-size image PowerPoint slide

Figure 5. A hypergraph to demonstrate the Dirac operator's ability to capture features of hypergraphs

Download: Full-size image PowerPoint slide

Figure 6. $ D_0 $ Dirac matrix visualized as an image, where blue = -1, white = 0, and red = 1

Download: Full-size image PowerPoint slide

Figure 7. Filtration of $ H^5 $

Download: Full-size image PowerPoint slide

Figure 8. Captured features by persistent hypergraph Dirac operators. (A), (B) and (C) show $ \eta(D_1^{(n, m)}) $, $ \hat{\lambda}(D_1^{(n, m)}) $ and $ \overline{\lambda}(D_1^{(n, m)}) $ of the filtration in Figure 7 respectively. (D), (E), and (F) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Figure 9. Two filtrations of the same digraph to demonstrate the sensitivity of persistent path Dirac operators to filtrations. (A)-(E) is the first filtration, and (F)-(J) is the second one

Download: Full-size image PowerPoint slide

Figure 10. Captured features by persistent path Dirac operators induced by the filtrations in Figure 9. (A), (B) and (C) show $ \eta(D_1^{(n, m)}) $, $ \hat{\lambda}(D_1^{(n, m)}) $ and $ \overline{\lambda}(D_1^{(n, m)}) $ of the first filtration in Figure 9 respectively. (D), (E), and (F) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Figure 11. Captured features by persistent path Dirac operators induced by the filtrations in Figure 9. (A), (B) and (C) show $ \eta(D_1^{(n, m)}) $, $ \hat{\lambda}(D_1^{(n, m)}) $ and $ \overline{\lambda}(D_1^{(n, m)}) $ of the second filtration in Figure 9 respectively. (D), (E), and (F) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Figure 12. A filtration of a digraph to compare the eigenvalues of persistent path Laplacian and persistent path Dirac operators

Download: Full-size image PowerPoint slide

Figure 13. A figure that demonstrates the allowed digraph edges equipped on the Glycogen molecule, where the loops say two atoms of the same type are connected, and does not mean a directed edge from an atom to itself is allowed for no loops are allowed

Download: Full-size image PowerPoint slide

Figure 14. Glycogen molecule. (A) Glycogen structure. (B) Molecular formula

Download: Full-size image PowerPoint slide

Figure 15. Captured features by persistent path Dirac operators of the filtration on Glycogen molecule in Figure 14. (A), (B) and (C) show $ \eta(D_1^{(n, m)}) $, $ \hat{\lambda}(D_1^{(n, m)}) $ and $ \overline{\lambda}(D_1^{(n, m)}) $ of the operator respectively. (D), (E), and (F) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Figure 16. $ \text{B}_7\text{C}_2\text{H}_9 $ first isomer and its captured features. (A) shows the obtained protein-ligand structure of the first isomer. (B) and (C) show $ \eta(D_1^{(n, m)}) $ and $ \hat{\lambda}(D_1^{(n, m)}) $ obtained from the first isomer. (D) and (E) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Figure 17. $ \text{B}_7\text{C}_2\text{H}_9 $ second isomer and its captured features. (A) shows the obtained protein-ligand structure of the second isomer. (B) and (C) show $ \eta(D_1^{(n, m)}) $ and $ \hat{\lambda}(D_1^{(n, m)}) $ obtained from the second isomer. (D) and (E) show their projections on the $ mz $-plane

Download: Full-size image PowerPoint slide

Table 1. Summary of the notations used for chain complexes of path complexes constructions induced by a digraph in the article

$ V $	nonempty set of vertices of a digraph
$ (v_0, v_1, \cdots, v_p) $	anchor sequence of length $ p $
$ C_p $	the vector space generated by all sequences of vertices
	of length $ p+1 $
$ P_p $	set of all anchor sequences of length $ p $ in the digraph
$ \Lambda_p $	the vector space spanned by $ P_p $ elements
$ \Omega_{p} $	the $ \partial $-invariant $ p $-paths

| Show Table

DownLoad: CSV

Table 2. Captured features by both Laplacian and Dirac operators on the digraph 2A

n	Betti Number $ \beta_n $	$ \text{Spec}(L_n) $	Dirac Nullity	$ \text{Spec}(D_n) $
0	1	0, 3, 3	2	$ 0, 0, \pm\sqrt{3}, \pm\sqrt{3} $
1	1	0, 3, 3	3	$ 0, 0, 0, \pm\sqrt{3}, \pm\sqrt{3} $

| Show Table

DownLoad: CSV

Table 3. Captured features by both Laplacian and Dirac operators on the digraph 2B

n	Betti Number $ \beta_n $	$ \text{Spec}(L_n) $	Dirac Nullity	$ \text{Spec}(D_n) $
0	1	0, 3, 3	2	$ 0, 0, \pm\sqrt{3}, \pm\sqrt{3} $
1	0	3, 3, 3	1	$ 0, \pm\sqrt{3}, \pm\sqrt{3}, \pm\sqrt{3} $

| Show Table

DownLoad: CSV

Table 4. The spectrum of Dirac operators on the hypergraph in Figure 5

n	$ \text{nullity}(D_n) $	$ \text{Spec}(D_n) $
0	10	$ 0(\times 10) $, $ \pm\sqrt{6}(\times 4) $,
1	12	$ 0(\times 12) $, $ \pm1(\times 2) $, $ \pm\sqrt{6}(\times 4) $,
		$ \pm\sqrt{7}(\times 4) $, $ \pm 3(\times 2) $
2	16	$ 0(\times 16) $, $ \pm1(\times 2) $, $ \pm2(\times 4) $,
		$ \pm\sqrt{6}(\times 4) $, $ \pm\sqrt{7}(\times 4) $, $ \pm 3(\times 2) $,
		$ \pm 3.06(\times 6) $
3	18	$ 0(\times 18) $, $ \pm0.93(\times 2) $, $ \pm1(\times 2) $,
		$ \pm2(\times 4) $, $ \pm\sqrt{6}(\times 4) $, $ \pm\sqrt{7}(\times 10) $,
		$ \pm 2.89(\times 4) $, $ \pm 3(\times 2) $, $ \pm 3.06(\times 6) $,
		$ \pm 3.24(\times 2) $

| Show Table

DownLoad: CSV

Table 5. Eigenvalues of persistent path Laplacian and persistent path Dirac operators induced by the filtration in Figure 12

$ \text{Spec}(L^{(0, 1)}_1)= $	$ \{2, 4, 4, 4, 5\} $	$ \text{Spec}(D^{(0, 1)}_1)= $	$ \{0 (\times 5), \pm\sqrt{1.59}, \pm\sqrt{3}, \pm 2, $
			$ \pm\sqrt{4.41}, \pm\sqrt{5}, \pm\sqrt{5}\} $
$ \text{Spec}(L^{(0, 2)}_1)= $	$ \{2, 4, 4, 4, 5\} $	$ \text{Spec}(D^{(0, 2)}_1)= $	$ \{0 (\times 4), \pm\sqrt{0.89}, \pm\sqrt{1.7}, \pm 2, $
			$ \pm\sqrt{3.25}, \pm\sqrt{4.86}, \pm\sqrt{5}, \pm\sqrt{5.3}\} $
$ \text{Spec}(L^{(0, 3)}_1)= $	$ \{2, 4, 4, 4, 5.09\} $	$ \text{Spec}(D^{(0, 3)}_1)= $	$ \{0 (\times 6), \pm\sqrt{1.19}, \pm\sqrt{3}, \pm 2, $
			$ \pm\sqrt{3.47}, \pm\sqrt{5}, \pm\sqrt{5.09}, \pm\sqrt{5.34}\} $

| Show Table

DownLoad: CSV

Table 6. The distances between every two atoms in Glycogen molecule that share a bond as calculated by 6

	H $ \leftrightarrow $ O	C $ \leftrightarrow $ O	C $ \leftrightarrow $ C	C $ \leftrightarrow $ H
Distance	0.97 Å	1.43 Å	1.53 Å	1.1 Å

| Show Table

DownLoad: CSV

Table 7. A list of (persistent) topological operators (i.e., homology, Laplacian, and Dirac) on various mathematical objects, such as simplicial complex, digraph, directed flag, path complex, hypergraph, and hyperdigraph. Starred objects are constructed in this article. Double-starred objects can be constructed similarly.

Topological Structure	Homologies	Topological Laplacians	Topological Diracs
simplicial complex	simplicial homology	Laplacian	simplicial Dirac
digraph	homology of digraphs	digraph Laplacian	digraph Dirac**
directed flag	directed flag homology	directed flag Laplacian	directed flag Dirac**
path complex	path homology	path Laplacian	path Dirac*
hypergraph	homology of hypergraphs	hypergraph Laplacian	hypergraph Dirac*
hyperdigraph	hyperdigraph homology	hyperdigraph Laplacian	hyperdigraph Dirac**

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Alhevaz, M. Baghipur, H. A. Ganie and Y. Shang, On the generalized distance energy of graphs, Mathematics, 8 (2020), 17.
[2]	B. Ameneyro, V. Maroulas and G. Siopsis, Quantum persistent homology, arXiv preprint, 2022. arXiv: 2202.12965.
[3]	B. Ameneyro, G. Siopsis and V. Maroulas, Quantum persistent homology for time series, 2022 IEEE/ACM 7th Symposium on Edge Computing (SEC), 2022,387-392. doi: 10.1109/SEC54971.2022.00057.
[4]	F. Baccini, F. Geraci and G. Bianconi, Weighted simplicial complexes and their representation power of higher-order network data and topology, Physical Review E, 106 (2022), Paper No. 034319, 17 pp. doi: 10.1103/physreve.106.034319.
[5]	H. Bergwerf, Glycogen, MolView, Available from: https://molview.org/.
[6]	G. Bianconi, The topological Dirac equation of networks and simplicial complexes, Journal of Physics: Complexity, 2 (2021), 035022.
[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]	L. Calmon, J. Restrepo, J. Torres and G. Bianconi, Dirac synchronization is rhythmic and explosive, Communications Physics, 5 (2022), 253.
[10]	L. Calmon, M. T. Schaub and G. Bianconi, Dirac signal processing of higher-order topological signals, New Journal of Physics, 25 (2023), Paper No. 093013, 18 pp. doi: 10.1088/1367-2630/acf33c.
[11]	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.
[12]	D. Chen, J. Liu, J. Wu and G.-W. Wei, Persistent hyperdigraph homology and persistent hyperdigraph Laplacians, Foundation of Data Science, 5 (2023), 558-588. doi: 10.3934/fods.2023010.
[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, Discrete Contin. Dyn. Syst. Ser. B, 26 (2021), 3785-3821. doi: 10.3934/dcdsb.2020257.
[15]	V. Consonni and R. Todeschini, New spectral indices for molecule description, MATCH Commun. Math. Comput. Chem., 60 (2008), 3-14.
[16]	J. Dodziuk, De Rham-Hodge theory for $L^2$-cohomology of infinite coverings, Topology, 16 (1977), 157-165. doi: 10.1016/0040-9383(77)90013-1.
[17]	H. Edelsbrunner and J. Harer, Persistent homology-a survey, Contemporary Mathematics, 453 (2008), 257-282. doi: 10.1090/conm/453/08802.
[18]	J. Grbić, J. Wu, K. Xia and G.-W. Wei, Aspects of topological approaches for data science, Foundations of Data Science (Springfield, Mo.), 4 (2022), 165-216. doi: 10.3934/fods.2022002.
[19]	A. Grigor'yan, Y. Lin, Y. Muranov and S.-T. Yau, Homologies of path complexes and digraphs, arXiv preprint, 2012, arXiv: 1207.2834.
[20]	A. Grigor'yan, Y. Lin, Y. Muranov and S.-T. Yau, Path complexes and their homologies, Journal of Mathematical Sciences, 248 (2020), 564-599. doi: 10.1007/s10958-020-04897-9.
[21]	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.
[22]	J. Jost and R. Mulas, Hypergraph Laplace operators for chemical reaction networks, Advances in Mathematics, 351 (2019), 870-896. doi: 10.1016/j.aim.2019.05.025.
[23]	T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology, Springer, New York, 2004. doi: 10.1007/b97315.
[24]	S. Krishnagopal and G. Bianconi, Topology and dynamics of higher-order multiplex networks, Chaos, Solitons & Fractals, 177 (2023), 114296. doi: 10.1016/j.chaos.2023.114296.
[25]	S. Lloyd, S. Garnerone and P. Zanardi, Quantum algorithms for topological and geometric analysis of data, Nature Communications, 7 (2016), 10138.
[26]	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.
[27]	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.
[28]	D. D. Nguyen and G.-W. Wei, AGL-score: Algebraic graph learning score for protein–ligand binding scoring, ranking, docking, and screening, Journal of Chemical Information and Modeling, 59 (2019), 3291-3304. doi: 10.1021/acs.jcim.9b00334.
[29]	L. Pauling, The nature of the chemical bond. Ⅳ. The energy of single bonds and the relative electronegativity of atoms, Journal of the American Chemical Society, 54 (1932), 3570-3582. doi: 10.1021/ja01348a011.
[30]	Y. Qiu and G.-W. Wei, Persistent spectral theory-guided protein engineering, Nature Computational Science, 3 (2023), 149-163.
[31]	A. D. Shepard, A cellular Description of the Derived Category of a Stratified Space, Brown University, 1985.
[32]	R. Wang, D. D. Nguyen and G.-W. Wei, Persistent spectral graph, International Journal for Numerical Methods in Biomedical Engineering, 36 (2020), e3376, 27 pp. doi: 10.1002/cnm.3376.
[33]	R. Wang and G.-W. Wei, Persistent path Laplacian, Foundations of Data Science, 5 (2023), 26-55. doi: 10.3934/fods.2022015.
[34]	R. Wang, R. Zhao, E. Ribando-Gros, J. Chen, Y. Tong and G.-W. Wei, HERMES: Persistent spectral graph software, Foundations of Data Science (Springfield, Mo.), 3 (2021), 67-97. doi: 10.3934/fods.2021006.
[35]	J. Wee, G. Bianconi and K. Xia, Persistent Dirac for molecular representation, Scientific Reports, 13 (2023).
[36]	X. Wei and G.-W. Wei, Persistent sheaf Laplacians, arXiv preprint, 2021, arXiv: 2112.10906.
[37]	A. Zomorodian and G. Carlsson, Computing persistent homology, Discrete Comput. Geom., 33 (2005), 249-274. doi: 10.1007/s00454-004-1146-y.