# What is non-Euclidean data?

What is non-Euclidean data?

Here are some sub-questions

• Where does this type of data arise? I have come across this term in the context of geometric deep learning and graph neural networks.

• Apparently, graphs and manifolds are non-Euclidean data. Why exactly is that the case?

• What is the difference between non-Euclidean and Euclidean data?

• How would a dataset of non-Euclidean data look like?

I presume this question was prompted by the paper Geometric deep learning: going beyond Euclidean data (2017). If we look at its abstract:

Many scientific fields study data with an underlying structure that is a non-Euclidean space. Some examples include social networks in computational social sciences, sensor networks in communications, functional networks in brain imaging, regulatory networks in genetics, and meshed surfaces in computer graphics. In many applications, such geometric data are large and complex (in the case of social networks, on the scale of billions), and are natural targets for machine learning techniques. In particular, we would like to use deep neural networks, which have recently proven to be powerful tools for a broad range of problems from computer vision, natural language processing, and audio analysis. However, these tools have been most successful on data with an underlying Euclidean or grid-like structure, and in cases where the invariances of these structures are built into networks used to model them.

We see that the authors use the term "non-Euclidean data" to refer to data whose underlying structure is non-Euclidean.

Since Euclidean spaces are prototypically defined by $$\mathbb{R}^n$$ (for some dimension $$n$$), 'Euclidean data' is data which is sensibly modelled as being plotted in $$n$$-dimensional linear space, for example image files (where the $$x$$ and $$y$$ coordinates refer to the location of each pixel, and the $$z$$ coordinate refers to its colour/intensity).

However some data does not map neatly into $$\mathbb{R}^n$$, for example, a social network modelled by a graph. You can of course embed the physical shape of a graph in 3-d space, but you will lose information such as the quality of edges, or the values associated with nodes, or the directionality of edges, and there isn't an obvious sensible way of mapping these attributes to higher dimensional Euclidean space. And depending on the specific embedding, you may introduce spurious correlations (e.g. two unconnected nodes appearing closer to each other in the embedding than to nodes they are connected to).

Methods such as Graph Neural Networks seek to adapt existing Machine Learning technologies to directly process non-Euclidean structured data as input, so that this (possibly useful) information is not lost in transforming the data into a Euclidean input as required by existing techniques.

• This answer clarifies my original main doubt, given that you emphasize that, in fact, graphs could be represented as a set of vectors (i.e. nodes and edges could be represented as vectors), but you correctly say that there isn't necessarily a natural way of mapping these graphs to a Euclidean space while maintaining their original properties or not introducing properties that did not exist. Maybe the only thing that is missing from this post is the answer to the question: "How would a dataset of non-Euclidean data look like?".
– nbro
Nov 6 '20 at 14:34
• For instance, it could be a list of triplets in the form of entity_1, relation, entity_2. And all these triplets form a graph. Nov 11 at 22:40

Non-Euclidian geometry can be generally boiled down to the phrase

the shortest path between 2 points isn't necessarily a straight line.

Or, put in a way that lends itself very much to machine learning,

things that are similar to each other are not necessarily close if one uses Euclidean distance as a metric (aka the triangle inequality doesn't hold).

You mention graphs and manifolds as being non-Euclidian, but, really, the majority of problems being worked on don't have Euclidian data. Take the below images for example:

Clearly, 2 of the images are more similar to each other than the third one is, but if we looked at the pixels alone, the Euclidean distance between the pixel values don't represent this similarity. If there was a function, $$F(\text{image})$$, that mapped images to a space of values where similar images produced values that were closer together, we could better understand the data, infer some statistics about the distributions, and make predictions on data we have yet to see. This is what classic techniques of image recognition have done and it's also what modern machine learning is doing. Taking data and mapping it to a space such that the triangle inequality holds.

Let's look at a more concrete example, some points I drew in MSPaint. On the left is some space that we are interested in where points have 2 classes (red or blue). Even though there are points that are close to each other, they may have different colors/classes. Ideally, we could have a function that converts these points to some space where we can draw a line to separate these 2 classes. In general, there would be many lines, or hyper-planes in dimensions > 3, but the goal is to transform the data so that it will be "linearly separable". To conclude, non-Euclidian data is everywhere.

• I think that your example of the points and this sentence "Clearly, 2 of the images are more similar to each other than the third one is but if we looked at the pixels alone, the euclidean distance between the pixel values don't represent this similarity." is really a stretch. Actually, I think you're mixing the concepts of "relation between inputs and classes" and "non-Euclidean data". Why would the fact that there isn't a linear relation between inputs and outputs imply that the data is non-Euclidean?!
– nbro
Mar 15 '19 at 16:20
• I think that non-Euclidean data is data that doesn't have the Euclidean properties. For example, in an image, there's the notion of the left pixel of a certain pixel 𝑝 (i.e. there's an order). In a graph, there isn't such a notion between vertices, so a graph can't be "Euclidean data". I think that data where you can naturally perform dot products and norms is likely Euclidean (at least in the sense that I initially intended or in geometric deep learning).
– nbro
Mar 15 '19 at 16:30
• In GDL, the input to the models are usually vector features of the vertices. However, these are "just" feature vectors associated with the vertices (so one could think that graphs are also Euclidean because you can calculate the dot product between two vectors), but they do not describe the structure of the graph, which can be described e.g. using an adjacency matrix.
– nbro
Mar 15 '19 at 16:30
• You're intuition about non-euclidean data not having euclidean properties is correct but only in the specific notion that "similar things are close together" which is what I tried to highlight. The fact that a dot product (or en.wikipedia.org/wiki/Inner_product_space#Examples) can be computed doesn't imply a euclidean space. However this doesn't prevent one from assuming that the space is euclidean and using an approximation of euclidean distance which can sometimes be fruitful. Mar 15 '19 at 17:23
• Again, I think you are mixing inputs with outputs (or classes). I don't think your answer is completely correct (as I stated above). Apparently, the definition of Euclidean space isn't actually well accepted (as e.g. the notion of a vector space). I don't get why this 'but only in the specific notion that "similar things are close together"'.
– nbro
Mar 15 '19 at 17:51

It's hard to say because Euclidean space is defined with respect to some kind of metric, so without any clearer exposition on the nature of the data/problem, the phrase itself may or may not be clear.

A metric $$d: A \times A \rightarrow \mathbb{R}$$ is a function that defines distance between any two points in the space with respect to axioms that 1. two points have zero distance iff they are the same: $$d(a,b) = 0 \Leftrightarrow a = b$$. 2. symmetric: $$d(a,b) = d(b,a)$$. 3. triangle inequality: $$d(a,b) + d(b,c) ≥ d(a,c)$$.

A Euclidian metric is a metric that also obeys Pythagoras theorem , or at least: the distance between some point $$(x,y) \in \mathbb{R}^2$$ is equal to $$\sqrt{x^2 + y^2}.$$ You will find that all Euclidian spaces are isomorphic to $$\mathbb{R}^n$$, meaning that the two notions are in some sense identical.

Any graph/data whose underlying data does not "naturally come" from $$\mathbb{R}^n$$, or a graph that does not admit a natural embedding in $$\mathbb{R}^n$$ might not be Euclidian, since $$\mathbb{R}^n$$ is isomorphic to any euclidian space.

As far as I understand, the concept of non-Euclidean space doesn't bring the ordinality or hierarchy among the features, compared to that with the data formed in the Euclidean space.

The difference between both these techniques is not remarkable for discriminative tasks like classification. But, for generative modeling, the non-Euclidean techniques helps in defining the latent manifold space for the given data distribution. This can further help in traversing the manifold from the same distribution (to generate similar samples from the same or underlying manifold) even with $$n$$ degrees of freedom in the latent space. This is not possible with Euclidean techniques. One cannot fully traverse/generate samples from or outside the manifold without the minimal change in the Euclidean space. More precisely, it can, but it will only present it as noisy data.

• Maybe you should define the concept of a manifold and why it is important to understand the concept of Euclidean and non-Euclidean data.
– nbro
Jul 10 '20 at 11:52