doi: 10.3934/fods.2021026
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Reconstructing linearly embedded graphs: A first step to stratified space learning

1. 

Mathematical Sciences Institute, Australian National University, Acton, ACT, 2601, Australia

2. 

School of Mathematics and Statistics, The University of Sydney, Camperdown, NSW, 2006, Australia

* Corresponding author: Yossi Bokor

Received  January 2021 Revised  June 2021 Early access September 2021

In this paper, we consider the simplest class of stratified spaces – linearly embedded graphs. We present an algorithm that learns the abstract structure of an embedded graph and models the specific embedding from a point cloud sampled from it. We use tools and inspiration from computational geometry, algebraic topology, and topological data analysis and prove the correctness of the identified abstract structure under assumptions on the embedding. The algorithm is implemented in the Julia package Skyler, which we used for the numerical simulations in this paper.

 

Erratum: Nanda et al. should be Stolz et al. in both the PDF (page 2, line 6) and HTML versions of this paper. We apologize for any inconvenience this may cause.

Citation: Yossi Bokor, Katharine Turner, Christopher Williams. Reconstructing linearly embedded graphs: A first step to stratified space learning. Foundations of Data Science, doi: 10.3934/fods.2021026
References:
[1]

M. AanjaneyaF. ChazalD. ChenM. GlisseL. Guibas and D. Morozov, Metric graph reconstruction from noisy data, Internat. J. Comput. Geom. Appl., 22 (2012), 305-325.  doi: 10.1142/S0218195912600072.  Google Scholar

[2]

P. Bendich, B. Wang and S. Mukherjee, Local homology transfer and stratification learning, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2012, 1355–1370.  Google Scholar

[3]

P. Bendich, B. Wang and S. Mukherjee, Towards stratification learning through homology inference, AAAI Fall Symposium on Manifold Learning and its Applications (AAAI), 2010. Available from: https://www.aaai.org/ocs/index.php/FSS/FSS10/paper/download/2273/2714. Google Scholar

[4]

Y. Bokor, D. Grixti-Cheng, M. Hegland, S. Roberts, and K. Turner, Stratified space learning: Reconstructing embedded graphs, 23rd International Congress on Modelling and Simulation, Australia, 2019. Available from: https://mssanz.org.au/modsim2019/A3/bokor.pdf. Google Scholar

[5]

P. BreidingS. KališnikB. Sturmfels and M. Weinstein, Learning algebraic varieties from samples, Rev. Mat. Complut., 31 (2018), 545-593.  doi: 10.1007/s13163-018-0273-6.  Google Scholar

[6]

S.-W. Cheng, T. K. Dey and E. A. Ramos, Manifold reconstruction from point samples, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, 1018–1027.  Google Scholar

[7]

A. P. DempsterN. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Statist. Soc. Ser. B, 39 (1977), 1-38.  doi: 10.1111/j.2517-6161.1977.tb01600.x.  Google Scholar

[8]

T. K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, Cambridge Monographs on Applied and Computational Mathematics, 23, Cambridge University Press, Cambridge, 2007.  Google Scholar

[9]

T. K. Dey, F. Fan and Y. Wang, Dimension detection with local homology, 26th Canadian Conference on Computational Geometry, Nova Scotia, 2014. Available from: http://www.cccg.ca/proceedings/2014/papers/paper40.pdf. Google Scholar

[10]

E. M. Stein and R. Shakarchi, Real Analysis. Measure Theory, Integration, and Hilbert Spaces, Princeton Lectures in Analysis, 3, Princeton University Press, Princeton, NJ, 2005.  Google Scholar

[11]

B. J. StolzJ. TannerH. A. Harrington and V. Nanda, Geometric anomaly detection in data, Proc. Natl. Acad. Sci. USA, 117 (2020), 19664-19669.  doi: 10.1073/pnas.2001741117.  Google Scholar

show all references

References:
[1]

M. AanjaneyaF. ChazalD. ChenM. GlisseL. Guibas and D. Morozov, Metric graph reconstruction from noisy data, Internat. J. Comput. Geom. Appl., 22 (2012), 305-325.  doi: 10.1142/S0218195912600072.  Google Scholar

[2]

P. Bendich, B. Wang and S. Mukherjee, Local homology transfer and stratification learning, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2012, 1355–1370.  Google Scholar

[3]

P. Bendich, B. Wang and S. Mukherjee, Towards stratification learning through homology inference, AAAI Fall Symposium on Manifold Learning and its Applications (AAAI), 2010. Available from: https://www.aaai.org/ocs/index.php/FSS/FSS10/paper/download/2273/2714. Google Scholar

[4]

Y. Bokor, D. Grixti-Cheng, M. Hegland, S. Roberts, and K. Turner, Stratified space learning: Reconstructing embedded graphs, 23rd International Congress on Modelling and Simulation, Australia, 2019. Available from: https://mssanz.org.au/modsim2019/A3/bokor.pdf. Google Scholar

[5]

P. BreidingS. KališnikB. Sturmfels and M. Weinstein, Learning algebraic varieties from samples, Rev. Mat. Complut., 31 (2018), 545-593.  doi: 10.1007/s13163-018-0273-6.  Google Scholar

[6]

S.-W. Cheng, T. K. Dey and E. A. Ramos, Manifold reconstruction from point samples, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, 1018–1027.  Google Scholar

[7]

A. P. DempsterN. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Statist. Soc. Ser. B, 39 (1977), 1-38.  doi: 10.1111/j.2517-6161.1977.tb01600.x.  Google Scholar

[8]

T. K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, Cambridge Monographs on Applied and Computational Mathematics, 23, Cambridge University Press, Cambridge, 2007.  Google Scholar

[9]

T. K. Dey, F. Fan and Y. Wang, Dimension detection with local homology, 26th Canadian Conference on Computational Geometry, Nova Scotia, 2014. Available from: http://www.cccg.ca/proceedings/2014/papers/paper40.pdf. Google Scholar

[10]

E. M. Stein and R. Shakarchi, Real Analysis. Measure Theory, Integration, and Hilbert Spaces, Princeton Lectures in Analysis, 3, Princeton University Press, Princeton, NJ, 2005.  Google Scholar

[11]

B. J. StolzJ. TannerH. A. Harrington and V. Nanda, Geometric anomaly detection in data, Proc. Natl. Acad. Sci. USA, 117 (2020), 19664-19669.  doi: 10.1073/pnas.2001741117.  Google Scholar

Figure 2.1.  An example of scenario 1
Figure 3.2.  Graph of $ \Psi\left(\frac{R}{\varepsilon}, 1\right) $
Figure 3.3.  Graph of $ \Phi\left(\frac{R}{\varepsilon}, 1\right) $
Figure 3.4.  Both $ q_1 $ and $ q_2 $ are in the same half-space generated by the hyper-plane through $ p $ perpendicular to $ \overline{uv} $
Figure 3.6.  The case where $ \angle uvw \leq \frac{\pi}{2} $
Figure 3.7.  The case where $ \|\widetilde{p}-\widetilde{q}\|<\|\widetilde{p}-n\| $
Figure 3.8.  The case where $ \|\widetilde{p}-\widetilde{q}\|>\|\widetilde{p}-n\| $
Table 1.  Summary of the output of the algorithm for various ratios $ \frac{R}{\varepsilon} $. Recall we wish to maximise Equation 9. The last 5 columns are the vertex locations obtained
Ratio Correct Log Likelihood v1 v2 v3 v4 v5
$R/\varepsilon$ structure (Equation 9) $\begin{pmatrix} 0\\0\\0\end{pmatrix}$ $\begin{pmatrix}4.6\\ 6.24\\ 0\end{pmatrix}$ $\begin{pmatrix}4.86\\ 0.51\\ 3.47\end{pmatrix}$ $\begin{pmatrix} -1.32\\ 6.29\\ 4\end{pmatrix}$ $\begin{pmatrix}-4.23\\ -3.48\\ -3\end{pmatrix}$
$4$ No - - - - - -
$6$ Yes $-33.183$ $\begin{pmatrix} 0.00 \\ 0.03 \\ 0.01\end{pmatrix}$ $\begin{pmatrix} 4.59 \\ 6.23 \\ -0.02 \end{pmatrix}$ $\begin{pmatrix} 4.56 \\ 0.56 \\ 3.43 \end{pmatrix}$ $\begin{pmatrix} -1.30 \\ 6.26 \\ 3.96\end{pmatrix}$ $\begin{pmatrix} -4.24 \\ -3.46 \\ -3.02 \end{pmatrix}$
$8$ Yes $-32.97$ $\begin{pmatrix} 0.00 \\ 0.02 \\ 0.01 \end{pmatrix}$ $\begin{pmatrix} 4.59 \\ 6.23 \\ -.02 \end{pmatrix}$ $\begin{pmatrix} 4.86 \\ 0.56 \\ 3.42\end{pmatrix}$ $\begin{pmatrix} -1.29 \\ 6.26 \\ 3.96\end{pmatrix}$ $\begin{pmatrix} -4.22\\ -3.45 \\ -3.01\end{pmatrix}$
$10$ Yes $-33.33$ $\begin{pmatrix}0.01 \\ 0.03 \\ 0.01 \end{pmatrix}$ $\begin{pmatrix}4.59 \\6.22\\-0.02 \end{pmatrix}$ $\begin{pmatrix} 4.86\\0.56\\3.42\end{pmatrix}$ $\begin{pmatrix} -1.26\\6.24\\3.95\end{pmatrix}$ $\begin{pmatrix} -4.19\\3.42\\-2.99\end{pmatrix}$
$12$ Yes $-33.84$ $\begin{pmatrix} 0.01\\0.03\\0.01\end{pmatrix}$ $\begin{pmatrix} 4.59\\6.23\\-0.02\end{pmatrix}$ $\begin{pmatrix}4.86\\0.56\\3.42 \end{pmatrix}$ $\begin{pmatrix} -1.26\\6.24 \\3.95 \end{pmatrix}$ $\begin{pmatrix} -4.14\\-3.38\\-2.96 \end{pmatrix}$
$14$ Yes $-36.61$ $\begin{pmatrix} 0.01\\0.03\\0.01\end{pmatrix}$ $\begin{pmatrix} 4.59\\6.26\\-0.03\end{pmatrix}$ $\begin{pmatrix}4.86\\0.56\\3.43 \end{pmatrix}$ $\begin{pmatrix}-1.26\\6.23\\3.95 \end{pmatrix}$ $\begin{pmatrix}-4.00\\-3.27\\-2.56 \end{pmatrix}$
$16$ Yes $-45.30$ $\begin{pmatrix} 0.02\\0.03\\0.01 \end{pmatrix}$ $\begin{pmatrix} 4.58\\6.27\\-0.05 \end{pmatrix}$ $\begin{pmatrix}4.56\\0.56\\3.43 \end{pmatrix}$ $\begin{pmatrix} -0.70\\ 3.70\\ 2.33 \end{pmatrix}$ $\begin{pmatrix}-3.96\\-3.22\\-2.81 \end{pmatrix}$
Ratio Correct Log Likelihood v1 v2 v3 v4 v5
$R/\varepsilon$ structure (Equation 9) $\begin{pmatrix} 0\\0\\0\end{pmatrix}$ $\begin{pmatrix}4.6\\ 6.24\\ 0\end{pmatrix}$ $\begin{pmatrix}4.86\\ 0.51\\ 3.47\end{pmatrix}$ $\begin{pmatrix} -1.32\\ 6.29\\ 4\end{pmatrix}$ $\begin{pmatrix}-4.23\\ -3.48\\ -3\end{pmatrix}$
$4$ No - - - - - -
$6$ Yes $-33.183$ $\begin{pmatrix} 0.00 \\ 0.03 \\ 0.01\end{pmatrix}$ $\begin{pmatrix} 4.59 \\ 6.23 \\ -0.02 \end{pmatrix}$ $\begin{pmatrix} 4.56 \\ 0.56 \\ 3.43 \end{pmatrix}$ $\begin{pmatrix} -1.30 \\ 6.26 \\ 3.96\end{pmatrix}$ $\begin{pmatrix} -4.24 \\ -3.46 \\ -3.02 \end{pmatrix}$
$8$ Yes $-32.97$ $\begin{pmatrix} 0.00 \\ 0.02 \\ 0.01 \end{pmatrix}$ $\begin{pmatrix} 4.59 \\ 6.23 \\ -.02 \end{pmatrix}$ $\begin{pmatrix} 4.86 \\ 0.56 \\ 3.42\end{pmatrix}$ $\begin{pmatrix} -1.29 \\ 6.26 \\ 3.96\end{pmatrix}$ $\begin{pmatrix} -4.22\\ -3.45 \\ -3.01\end{pmatrix}$
$10$ Yes $-33.33$ $\begin{pmatrix}0.01 \\ 0.03 \\ 0.01 \end{pmatrix}$ $\begin{pmatrix}4.59 \\6.22\\-0.02 \end{pmatrix}$ $\begin{pmatrix} 4.86\\0.56\\3.42\end{pmatrix}$ $\begin{pmatrix} -1.26\\6.24\\3.95\end{pmatrix}$ $\begin{pmatrix} -4.19\\3.42\\-2.99\end{pmatrix}$
$12$ Yes $-33.84$ $\begin{pmatrix} 0.01\\0.03\\0.01\end{pmatrix}$ $\begin{pmatrix} 4.59\\6.23\\-0.02\end{pmatrix}$ $\begin{pmatrix}4.86\\0.56\\3.42 \end{pmatrix}$ $\begin{pmatrix} -1.26\\6.24 \\3.95 \end{pmatrix}$ $\begin{pmatrix} -4.14\\-3.38\\-2.96 \end{pmatrix}$
$14$ Yes $-36.61$ $\begin{pmatrix} 0.01\\0.03\\0.01\end{pmatrix}$ $\begin{pmatrix} 4.59\\6.26\\-0.03\end{pmatrix}$ $\begin{pmatrix}4.86\\0.56\\3.43 \end{pmatrix}$ $\begin{pmatrix}-1.26\\6.23\\3.95 \end{pmatrix}$ $\begin{pmatrix}-4.00\\-3.27\\-2.56 \end{pmatrix}$
$16$ Yes $-45.30$ $\begin{pmatrix} 0.02\\0.03\\0.01 \end{pmatrix}$ $\begin{pmatrix} 4.58\\6.27\\-0.05 \end{pmatrix}$ $\begin{pmatrix}4.56\\0.56\\3.43 \end{pmatrix}$ $\begin{pmatrix} -0.70\\ 3.70\\ 2.33 \end{pmatrix}$ $\begin{pmatrix}-3.96\\-3.22\\-2.81 \end{pmatrix}$
[1]

Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81.

[2]

Khalid Addi, Aleksandar D. Rodić. Impact dynamics in biped locomotion analysis: Two modelling and implementation approaches. Mathematical Biosciences & Engineering, 2010, 7 (3) : 479-504. doi: 10.3934/mbe.2010.7.479

[3]

Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021102

[4]

Darko Volkov, Joan Calafell Sandiumenge. A stochastic approach to reconstruction of faults in elastic half space. Inverse Problems & Imaging, 2019, 13 (3) : 479-511. doi: 10.3934/ipi.2019024

[5]

Diogenis A. Kiziridis, Mike S. Fowler, Chenggui Yuan. Modelling fungal competition for space:Towards prediction of community dynamics. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4411-4426. doi: 10.3934/dcdsb.2020104

[6]

Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm. Mathematical Foundations of Computing, 2020, 3 (3) : 205-218. doi: 10.3934/mfc.2020020

[7]

Gianne Derks, Sara Maad, Björn Sandstede. Perturbations of embedded eigenvalues for the bilaplacian on a cylinder. Discrete & Continuous Dynamical Systems, 2008, 21 (3) : 801-821. doi: 10.3934/dcds.2008.21.801

[8]

S. Aiello, Luigi Barletti, Aldo Belleni-Morante. Identification of photon sources, stochastically embedded in an interstellar cloud. Kinetic & Related Models, 2009, 2 (3) : 425-432. doi: 10.3934/krm.2009.2.425

[9]

Ephraim Agyingi, Tamas Wiandt, Sophia A. Maggelakis. Thermal detection of a prevascular tumor embedded in breast tissue. Mathematical Biosciences & Engineering, 2015, 12 (5) : 907-915. doi: 10.3934/mbe.2015.12.907

[10]

Alberto Bressan, Yunho Hong. Optimal control problems on stratified domains. Networks & Heterogeneous Media, 2007, 2 (2) : 313-331. doi: 10.3934/nhm.2007.2.313

[11]

Mathieu Desbrun, Evan S. Gawlik, François Gay-Balmaz, Vladimir Zeitlin. Variational discretization for rotating stratified fluids. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 477-509. doi: 10.3934/dcds.2014.34.477

[12]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169

[13]

Wenning Wei. On the Cauchy-Dirichlet problem in a half space for backward SPDEs in weighted Hölder spaces. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5353-5378. doi: 10.3934/dcds.2015.35.5353

[14]

Xinlin Cao, Yi-Hsuan Lin, Hongyu Liu. Simultaneously recovering potentials and embedded obstacles for anisotropic fractional Schrödinger operators. Inverse Problems & Imaging, 2019, 13 (1) : 197-210. doi: 10.3934/ipi.2019011

[15]

Anthony M. Bloch, Peter E. Crouch, Nikolaj Nordkvist, Amit K. Sanyal. Embedded geodesic problems and optimal control for matrix Lie groups. Journal of Geometric Mechanics, 2011, 3 (2) : 197-223. doi: 10.3934/jgm.2011.3.197

[16]

Yao Xu, Weisheng Niu. Periodic homogenization of elliptic systems with stratified structure. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 2295-2323. doi: 10.3934/dcds.2019097

[17]

Cristopher Hermosilla. Stratified discontinuous differential equations and sufficient conditions for robustness. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4415-4437. doi: 10.3934/dcds.2015.35.4415

[18]

Miles H. Wheeler. On stratified water waves with critical layers and Coriolis forces. Discrete & Continuous Dynamical Systems, 2019, 39 (8) : 4747-4770. doi: 10.3934/dcds.2019193

[19]

Laurent Lévi, Julien Jimenez. Coupling of scalar conservation laws in stratified porous media. Conference Publications, 2007, 2007 (Special) : 644-654. doi: 10.3934/proc.2007.2007.644

[20]

David Colton, Yuk-J. Leung. On a transmission eigenvalue problem for a spherically stratified coated dielectric. Inverse Problems & Imaging, 2016, 10 (2) : 369-378. doi: 10.3934/ipi.2016004

 Impact Factor: 

Metrics

  • PDF downloads (54)
  • HTML views (62)
  • Cited by (0)

[Back to Top]