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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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]

Cécilia Tarpau, Javier Cebeiro, Geneviève Rollet, Maï K. Nguyen, Laurent Dumas. Analytical reconstruction formula with efficient implementation for a modality of Compton scattering tomography with translational geometry. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2021075

[4]

Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 655-668. doi: 10.3934/dcdss.2021102

[5]

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

[6]

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

[7]

Thi Tuyet Trang Chau, Pierre Ailliot, Valérie Monbet, Pierre Tandeo. Comparison of simulation-based algorithms for parameter estimation and state reconstruction in nonlinear state-space models. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022054

[8]

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

[9]

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

[10]

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

[11]

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

[12]

John Guckenheimer. Continuation methods for principal foliations of embedded surfaces. Journal of Computational Dynamics, 2022  doi: 10.3934/jcd.2022007

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

 Impact Factor: 

Metrics

  • PDF downloads (324)
  • HTML views (323)
  • Cited by (0)

[Back to Top]