21
$\begingroup$

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?

$\endgroup$
0

5 Answers 5

12
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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?". $\endgroup$
    – nbro
    Nov 6, 2020 at 14:34
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2021 at 22:40
8
$\begingroup$

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.

2 good boys and a rad hampster

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

Some points I drew in MSPaint.

To conclude, non-Euclidian data is everywhere.

$\endgroup$
10
  • 2
    $\begingroup$ 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?! $\endgroup$
    – nbro
    Mar 15, 2019 at 16:20
  • $\begingroup$ 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). $\endgroup$
    – nbro
    Mar 15, 2019 at 16:30
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Mar 15, 2019 at 16:30
  • $\begingroup$ 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. $\endgroup$ Mar 15, 2019 at 17:23
  • 1
    $\begingroup$ 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"'. $\endgroup$
    – nbro
    Mar 15, 2019 at 17:51
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Where does this type of data arise?

In terms of learning on non-Euclidean data, it was probably first coined by prof. Bronstein here. Recently, prof. Bronstein published, along with other top authors in the field, a book about geometric deep learning, which in essence presents a unified mathematical framework for symmetries-based learning, and exemplifies the extension of concepts from classical ML/DL to the domain of higher-dimensional geometric domains (chapter 4).

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

According to the unified mathematical framework presented in prof. Bronstein's book, the blueprint of geometric DL consists of an underlying domain $\Omega$ and signals $\mathcal{X}(\Omega)$ and functions $\mathcal{F}(\mathcal{X}(\Omega))$.

The domain is the geometric/algebraic structure behind any instance of that data type (basically shows how its composing features are arranged). Associated with this domain is a symmetry group (all the transformations under which the domain is invariant).

The signal is the observable state/value/quantity/features in the points of the domain.

The function(s) are the blocks/layers that we want to build as functions of the signals on the domain. Here is where we can inject inductive biases.

Translation equivariance is a property of the domain of images (among other groups). Convolutions as functions of a signal on the domain $R^2$ are translation equivariant, meaning that if you move an object in an image, you would still find the same features (at different locations) when applying the same kernel over the two images. This is the (geometric prior) "inductive bias", as the function used is aware of the domain, knows its properties, and uses them.

The underlying domain of an image is $\mathbb{R}^2$ (the position of the pixels in the (x, y) plane). In this context, one can say that the signal of an is simply the colour/intensity of the pixels. As pointed out in this answer, this group admits the Euclidean distance between two points in the plane as $d(x, y) = \sqrt{\sum_{i=0}^{1} (x_i - y_i)^2}$.

In broad terms, non-Euclidean data is data whose underlying domain does not obey Euclidean distance as a metric between points in the domain. For visualization simplicity, think of $\mathbb{Z}^2$ instead, which can be seen as a "grid" of integer-valued points separated by a distance of 1. You can easily "visualize" the distance between the points of the domain.

Now let's move to graphs. What is the underlying domain of the graph? It's a set of nodes $\mathcal{V}$ and a set of edges $\mathcal{E}$. There is no such thing as distance in the Euclidean sense between the nodes of a graph. If you ask "What is the distance between point A and B?", the answer is probably a function of the connectivity of the graph (which is part of the domain), and is not the same for arbitrary points in the graph.

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

Usually, a data point (sample) consists of a domain and a signal.

  • The domain can be for example a weighted adjacency matrix of the graph, which lists the "distances" between nodes, for those that exist.
  • Features can be either per node, per edge or both.

In a concrete example, the domain can be a road network graph with distances and connectivity between road intersections, and the signal can be per-node features indicating how many cars are in the intersection at a given point.

Of course, the domain can also be different between data points (i.e. in the PROTEINS dataset, where each protein is a graph connected (edges) aminoacids (nodes), with different structures).

A non-Euclidean dataset simply consists of multiple such data points, which may or may not have the same underlying domain (i.e. same graph structure defined by an adjacency matrix).

$\endgroup$
11
  • $\begingroup$ Thanks for this answer and welcome to our community! There are a few unclear things in this answer. First, you don't explain exactly what a signal is. It seems that you define a (non-Euclidean) "data point" as something that has a "domain" and a "signal", so it seems that you define it similar to a function, which has also a "domain". But what is a signal? Of course, the term signal pops up in signal processing, but maybe you should explain what it really is in signal processing and why you call the features of a "non-Euclidean data point" a signal. $\endgroup$
    – nbro
    Apr 15 at 23:05
  • $\begingroup$ Second, you also call "Euclidean data" a "data point", why? Third, you talk about data points and you give an example at the end, but what is a dataset of non-Euclidean data? Note that I assume that a dataset is not the same thing as a data point, which is just one element of a dataset. So, what is the difference between a "data point" and a "dataset" in the context of Euclidean data and geometric deep learning? $\endgroup$
    – nbro
    Apr 15 at 23:05
  • $\begingroup$ Thanks for pointing out the mistakes, I made some corrections. I have tried to explain it in broad terms as I am not very good at formal mathematics formulations. For the last item, I simply forgot to define the dataset after defining a data point, haha. Hope it's better now :) $\endgroup$ Apr 16 at 9:02
  • 1
    $\begingroup$ Yes, you can train a GNN with multiple different graphs. Look at the PROTEINS dataset, where each data point (sample) is a different protein that is represented as a graph. The nodes are amino-acids and the edges are connections between them (based on some rules). The underlying domain (the individual nodes and edges -- their existence, not their values) is different for each protein. One can have 3 amino-acids with 4 edges, one can have 4 amino-acids with 5 edges. The values of the amino-acids (node features / signals) are also different from sample to sample. $\endgroup$ Apr 16 at 12:00
  • 1
    $\begingroup$ Permutation invariance is a property of a graph - there is no order relationship between the nodes (as there is in $\mathbb{R}^2$ where you can say the coordinate (1, 0) is to the right of (0, 0)). So you can permute the nodes however you want (without changing the edges), and you would have the same graph. The question is how do you exploit this property, or how do you make use of this in the context of a neural network. Most of the "Message Passing" architectures in GNNs (GAT, GCN, etc.) are formulated so that their update rule is permutation invariant. Please refer to the respective papers. $\endgroup$ Apr 16 at 14:54
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Maybe you should define the concept of a manifold and why it is important to understand the concept of Euclidean and non-Euclidean data. $\endgroup$
    – nbro
    Jul 10, 2020 at 11:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .