Why are point clouds and meshes considered to be non-euclidean data structures? I was reading about geometric deep learning and non-euclidean data. I get that graphs are considered non-euclidean. But how come point clouds and meshes are also considered non-euclidean? I don't know a lot about point clouds. But as an example let's assume the point cloud exists in a 3D space, could I not just assign each point a (x,y,z) coordinates and represent the cloud in euclidean space?
Maybe someone can explain why this is not true?
 A: Recall that when dealing with point clouds, we are (almost always) making the assumption that the points are sampled from an underlying topological space. Hence, when we say that a point cloud is Euclidean, what we are really saying is that the points have been sampled from an underlying Euclidean space, i.e. $\mathbf{R}^n$ for some $n$. This is a very pedantic (but proper) use of terminology, i.e. that a topological space $X$ is Euclidean if and only if $X \cong \mathbf{R}^n$ for some $n$. A familiar example is the grid on which we represent a greyscale image, whose points are sampled from $\mathbf{R}^2$. But wait a minute: why do we choose the grid to be (a subset of) $\mathbf{R}^2$? There are arguably a few good reasons, but most importantly, it is because a flat grid is the best model for how an image signal is captured in the physical world, namely by a planar array of light-sensitive photosites in a camera's digital sensor. Therefore, the grid/point cloud is determined by the most natural space on which the signal of interest lies.
What if the signal of interest is an evolving temperature field on the surface of planet Jupiter? In this case, the most appropriate grid would be a discrete subset $\Omega \subset S^2$, where each point of $\Omega$ is parameterized by spherical coordinates $\theta$ and $\phi$. To your point, we absolutely could consider an embedding $S^2 \subset \mathbf{R}^3$, thus representing each grid point with coordinates $x$, $y$, and $z$, and often this is helpful in practice. However, as mentioned in the previous paragraph, this doesn't mean that the point cloud is Euclidean since the points were not directly sampled from $\mathbf{R}^n$. Think of it like this: I should be able to randomly sample from my underlying topological space and obtain an equally good grid point. If I randomly sample from $\mathbf{R}^3$ (the spatial universe in this example), we might get lucky and obtain a point on our embedded $S^2$ (Jupiter's surface in this example), but not in general.
Thus, in general, we can really only say that a point cloud has been sampled from an underlying manifold, and thus we should restrict ourselves to only using the geometric/topological properties of this manifold to define operations such as convolutions and nonlinearities, without using a potential embedding into $\mathbf{R}^n$ as a crutch. This is why we oftentimes work with meshes, for they are (triangulations of) the most general underlying manifolds that we can safely assume the point cloud was sampled from. To solidify this point, I'll give one more space example :D. Assume that we are interested in some hypothetical signal on the 4-dimensional manifold $M$ modeling spacetime. Let's say there exists a $k$ such that $M\subset \mathbf{R}^k$ is an isometric embedding. We know how to deal with $\mathbf{R}^k$ really well, so why not take our operation (e.g. convolution) on $\mathbf{R}^k$ and restrict it to $M$? Well, this would require us to know how our signal extends into $\mathbf{R}^k$ (which does not exist physically). Can we really say that our universe is embedded in some larger space? This point can be summarized as developing a geometry (and its appropriate operations) from an intrinsic point of view, rather than an extrinsic one. See this link.
To cut this long story short, your confusion arises from misunderstanding the use of the word 'Euclidean' in this context. Just because a point cloud (or rather its underlying manifold) can be embedded into a Euclidean space does not mean that the point cloud is itself Euclidean. A priori, it might not even be clear what the most natural/useful embedding would be, so we should resort to the notions of distance and curvature that are intrinsic to the manifold, rather than those induced from a larger $\mathbf{R}^n$. This, along with equivariance, forms the foundation of geometric deep learning.
