Answers.Body: <p>Non-Euclidian geometry can be generally boiled down to the phrase</p>
  <blockquote>
  <p>the shortest path between 2 points isn't necessarily a straight line.</p>
  </blockquote>
  <p>Or, put in a way that lends itself very much to machine learning,</p>
  <blockquote>
  <p>things that are similar to each other are not necessarily close if one uses Euclidean distance as a metric (aka the <a href="https://en.wikipedia.org/wiki/Triangle_inequality" rel="nofollow noreferrer">triangle inequality</a> doesn't hold).</p>
  </blockquote>
  <p>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:</p>
  <p>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.</p>
  <p><a href="https://i.sstatic.net/P6mH2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/P6mH2.png" alt="2 good boys and a rad hampster" /></a></p>
  <p>If there was a function, <span class="math-container">$F(\text{image})$</span>, 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 <a href="https://en.wikipedia.org/wiki/Triangle_inequality" rel="nofollow noreferrer">triangle inequality</a> holds.</p>
  <p>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 &gt; 3, but the goal is to transform the data so that it will be &quot;linearly separable&quot;.</p>
  <p><a href="https://i.sstatic.net/S81eT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/S81eT.png" alt="Some points I drew in MSPaint." /></a></p>
  <p>To conclude, non-Euclidian data is everywhere.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T16:20:03.507Z
Answers.Text: 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?!
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T16:30:00.707Z
Answers.Text: 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).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T16:30:35.533Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T17:23:47.613Z
Answers.Text: 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 https://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.
Answers.UserDisplayName: Jaden Travnik
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T17:51:43.910Z
Answers.Text: 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"_'.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-25T14:59:40.840Z
Answers.Text: in polar coordinates, the 1st red/blue statistics is linearly separable; though this would also depend on how you interpret the source of the data...
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-25T15:02:34.263Z
Answers.Text: "the shortest path between 2 points isn't necessarily a straight line." this sentence is slightly problematic because "path" and "straight line" are not well-defined if you are not already in some well-defined space (such as euclidian geometry)
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-25T20:01:20.290Z
Answers.Text: @k.c.sayz'k.csayz' I agree. Thats why I prefaced it with "can be generally boiled down to" as in "This is not well defined but this is the gist in order to get an intuition". Either way, I am open to edits.
Answers.UserDisplayName: Jaden Travnik
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-26T04:51:43.377Z
Answers.Text: no worries, i was being a bit pedantic here: i am under the humble assumption that the phrase just refers to a loose set of research goals rather than a specific idea. specifically, i think i've also seen it mentioned as training to constraint parameters to fit some manifold, but the specifics are unclear to me and maybe i'm miss understanding something...
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-11T22:42:59.600Z
Answers.Text: Who voting such an answer up?
Answers.UserDisplayName: user3352632
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T16:14:41.980Z
Answers.LastActivityDate: 2020-07-10T11:50:16.627Z
Answers.LastEditDate: 2020-07-10T11:50:16.627Z
Answers.UserDisplayName: Jaden Travnik
Answers.Body: <p>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.</p>
  <p>A <a href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow noreferrer">metric</a> <span class="math-container">$d: A \times A \rightarrow \mathbb{R}$</span> 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: <span class="math-container">$d(a,b) = 0 \Leftrightarrow a = b$</span>.  2. symmetric: <span class="math-container">$d(a,b) = d(b,a)$</span>. 3. triangle inequality: <span class="math-container">$d(a,b) + d(b,c) ≥ d(a,c)$</span>.</p>
  <p>A Euclidian metric is a metric that also obeys Pythagoras theorem , or at least: the distance between some point <span class="math-container">$(x,y) \in \mathbb{R}^2$</span> is equal to <span class="math-container">$\sqrt{x^2 + y^2}.$</span> You will find that all Euclidian spaces are <a href="https://en.wikipedia.org/wiki/Isomorphism" rel="nofollow noreferrer">isomorphic</a> to <span class="math-container">$\mathbb{R}^n$</span>, meaning that the two notions are in some sense identical.</p>
  <p>Any graph/data whose underlying data does not &quot;naturally come&quot; from <span class="math-container">$\mathbb{R}^n$</span>, or a graph that does not admit a natural embedding in <span class="math-container">$\mathbb{R}^n$</span> might not be Euclidian, since <span class="math-container">$\mathbb{R}^n$</span> is isomorphic to any euclidian space.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-25T15:33:09.260Z
Answers.LastActivityDate: 2021-08-25T15:33:09.260Z
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.Body: <blockquote>
  <p>Where does this type of data arise?</p>
  </blockquote>
  <p>In terms of <em>learning</em> on non-Euclidean data, it was probably first coined by prof. Bronstein <a href="https://arxiv.org/abs/1611.08097" rel="nofollow noreferrer">here</a>. Recently, prof. Bronstein published, along with other top authors in the field, a <a href="https://arxiv.org/pdf/2104.13478.pdf" rel="nofollow noreferrer">book</a> 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).</p>
  <blockquote>
  <p>Apparently, graphs and manifolds are non-Euclidean data. Why exactly is that the case?</p>
  </blockquote>
  <p>According to the unified mathematical framework presented in prof. Bronstein's book, the blueprint of geometric DL consists of an underlying domain <span class="math-container">$\Omega$</span> and signals <span class="math-container">$\mathcal{X}(\Omega)$</span> and functions <span class="math-container">$\mathcal{F}(\mathcal{X}(\Omega))$</span>.</p>
  <p>The domain is the geometric/algebraic <strong>structure</strong> 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).</p>
  <p>The signal is the observable state/value/quantity/features in the points of the domain.</p>
  <p>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.</p>
  <p>Translation equivariance is a property of the domain of images (among other groups). Convolutions as functions of a signal on the domain <span class="math-container">$R^2$</span> 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) &quot;inductive bias&quot;, as <strong>the function used is aware of the domain, knows its properties, and uses them</strong>.</p>
  <p>The underlying domain of an image is <span class="math-container">$\mathbb{R}^2$</span> (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 <a href="https://ai.stackexchange.com/a/30368/54143">this</a> answer, this group admits the Euclidean distance between two points in the plane as <span class="math-container">$d(x, y) = \sqrt{\sum_{i=0}^{1} (x_i - y_i)^2}$</span>.</p>
  <p>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 <span class="math-container">$\mathbb{Z}^2$</span> instead, which can be seen as a &quot;grid&quot; of integer-valued points separated by a distance of 1. You can easily &quot;visualize&quot; the distance between the points of the domain.</p>
  <p>Now let's move to graphs. What is the underlying domain of the graph? It's a set of nodes <span class="math-container">$\mathcal{V}$</span> and a set of edges <span class="math-container">$\mathcal{E}$</span>. There is no such thing as distance in the Euclidean sense between the nodes of a graph. If you ask &quot;What is the distance between point A and B?&quot;, the answer is probably a function of the connectivity of the graph (which is part of the domain), <strong>and is not the same for arbitrary points in the graph</strong>.</p>
  <blockquote>
  <p>How would a dataset of non-Euclidean data look like?</p>
  </blockquote>
  <p>Usually, a data point (sample) consists of a domain and a signal.</p>
  <ul>
  <li>The domain can be for example a weighted adjacency matrix of the graph, which lists the &quot;distances&quot; between nodes, for those that exist.</li>
  <li>Features can be either per node, per edge or both.</li>
  </ul>
  <p>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.</p>
  <p>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).</p>
  <p>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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T23:05:06.720Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T23:05:08.467Z
Answers.Text: 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?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T09:02:37.483Z
Answers.Text: 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 :)
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T09:37:50.490Z
Answers.Text: Ok, thanks, now, it's a bit clearer. But are you saying that you would train, e.g., a graph neural network with multiple graphs (so one graph would be one data point)? I am not sure that's the case. Moreover, you say that the "domain is usually incorporated into architectures via inductive biases.". What do you mean by that exactly?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T12:00:43.203Z
Answers.Text: 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.
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T12:05:38.137Z
Answers.Text: For the part with the inductive biases, there is the CNN example in my initial comment. CNNs are built such that convolutions (which are translation equivariant) take advantage of the nature of the image, which is also translation equivariant/invariant because its underlying domain is R2.
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T12:22:04.073Z
Answers.Text: Your example of the dataset with multiple graphs that represent different molecules. is good! Yes, I am familiar with CNNs. But what would be the inductive bias in the case of graphs and GNNs?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T14:54:33.807Z
Answers.Text: 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.
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T16:19:29.433Z
Answers.Text: Yes, I am aware of these architectures that take as input adjacency matrices and perform some kind of message passing, which some people call graph convolution. But I wouldn't say that "domain is usually incorporated into architectures via inductive biases". Isn't the input to these graph neural networks e.g. adjacency matrices that represent the structure/domain of the graphs? Then you would work on this input by performing some kind of message passing or conv, right? Isn't this the intuition? So, I wouldn't say that the structure of the graph (or domain) is incorporated in the architecture.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T16:26:27.080Z
Answers.Text: However, there's definitely an inductive bias in graph neural networks, because they "assume" (in the way they are designed and by performing these message passing algorithms) that the data they get is non-Euclidean. So, rather than writing what you wrote, I would write that GNNs have an inductive bias that assumes that the inputs are graphs. It's possible I am missing something because it's been a while I had to deal with GNNs and I forgot the details.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-16T20:44:53.280Z
Answers.Text: You are correct that "domain is usually incorporated into architecture via inductive biases" is a very vague and possibly incorrect explanation. I made some more edits to the original post. Your last comment is on point, and somehow reflects what I was trying to say. They know the input is a graph, so the "blocks"/"layers" are designed so that they exploit the symmetries of the group (I suppose permutation invariance, at least). Hope my answer is more clear now.
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T21:25:42.080Z
Answers.LastActivityDate: 2022-04-16T20:43:02.933Z
Answers.LastEditDate: 2022-04-16T20:43:02.933Z
Answers.UserDisplayName: Andrei-Cristian Rad
Answers.Body: <p>As far as I understand, the concept of <em>non-Euclidean space</em> doesn't bring the ordinality or hierarchy among the features, compared to that with the data formed in the Euclidean space.</p>
  <p>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 <span class="math-container">$n$</span> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T11:52:27.000Z
Answers.Text: Maybe you should define the concept of a manifold and why it is important to understand the concept of Euclidean and non-Euclidean data.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T03:47:23.347Z
Answers.LastActivityDate: 2020-07-10T11:51:44.223Z
Answers.LastEditDate: 2020-07-10T11:51:44.223Z
Answers.UserDisplayName: Devansh Khandekar
Answers.Body: <p>I presume this question was prompted by the paper <a href="https://arxiv.org/abs/1611.08097" rel="noreferrer">Geometric deep learning:
  going beyond Euclidean data</a> (2017). If we look at its abstract:</p>
  
  <blockquote>
    <p>Many scientific fields study <strong>data with an underlying structure that is a non-Euclidean space.</strong> 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 <strong>deep neural networks</strong>, 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 <strong>have been most successful on data with an underlying Euclidean or grid-like structure,</strong> and in cases where the invariances of these structures are built into networks used to model them.</p>
  </blockquote>
  
  <p>We see that the authors use the term "non-Euclidean data" to refer to data whose underlying structure is non-Euclidean.</p>
  
  <p>Since Euclidean spaces are prototypically defined by <span class="math-container">$\mathbb{R}^n$</span> (for some dimension <span class="math-container">$n$</span>), 'Euclidean data' is data which is sensibly modelled as being plotted in <span class="math-container">$n$</span>-dimensional linear space, for example image files (where the <span class="math-container">$x$</span> and <span class="math-container">$y$</span> coordinates refer to the location of each pixel, and the <span class="math-container">$z$</span> coordinate refers to its colour/intensity).</p>
  
  <p>However some data does not map neatly into <span class="math-container">$\mathbb{R}^n$</span>, for example, a social network modelled by a graph. You can of course <a href="https://math.stackexchange.com/questions/584171/show-that-every-graph-can-be-embedded-in-mathbbr3">embed the physical shape of a graph in 3-d space</a>, 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).</p>
  
  <p>Methods such as <a href="https://ai.stackexchange.com/questions/11169/what-is-a-graph-neural-network/20626#20626">Graph Neural Networks</a> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-06T14:34:41.217Z
Answers.Text: 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?_".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-11T22:40:52.973Z
Answers.Text: 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.
Answers.UserDisplayName: user3352632
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-12T18:41:55.610Z
Answers.Text: @brazofuerte Would text be classified as non-euclidean data? I mean we don't use the term geometric deep learning when we are doing nlp.
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-25T18:43:14.533Z
Answers.LastActivityDate: 2020-04-25T18:59:57.083Z
Answers.LastEditDate: 2020-04-25T18:59:57.083Z
Answers.UserDisplayName: brazofuerte
Body: <p>What is non-Euclidean data?</p>
  <p>Here are some sub-questions</p>
  <ul>
  <li><p>Where does this type of data arise? I have come across this term in the context of geometric deep learning and graph neural networks.</p>
  </li>
  <li><p>Apparently, graphs and manifolds are non-Euclidean data. Why exactly is that the case?</p>
  </li>
  <li><p>What is the difference between non-Euclidean and Euclidean data?</p>
  </li>
  <li><p>How would a dataset of non-Euclidean data look like?</p>
  </li>
  </ul>
  
Tags: <deep-learning><definitions><geometric-deep-learning><graph-neural-networks><non-euclidean-data>
Title: What is non-Euclidean data?
UserDisplayName: nbro
ThreadText: # What is non-Euclidean data?
  
  (Asked by: username_0 on 2019-03-14)
  
  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?
  
  **Tags:** deep-learning, definitions, geometric-deep-learning, graph-neural-networks, non-euclidean-data
  
  ---
  
  ## 5 answers
  
  ### Answer by username_6 on 2020-04-25. Score: 16 | Accepted answer
  
  I presume this question was prompted by the paper [Geometric deep learning:
  going beyond Euclidean data](https://arxiv.org/abs/1611.08097) (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](https://math.stackexchange.com/questions/584171/show-that-every-graph-can-be-embedded-in-mathbbr3), 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](https://ai.stackexchange.com/questions/11169/what-is-a-graph-neural-network/20626#20626) 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.
  
  > **Comments:**
  > **username_0**: 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?_".  
  > **username_3**: 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.  
  > **username_7**: @brazofuerte Would text be classified as non-euclidean data? I mean we don't use the term geometric deep learning when we are doing nlp.  
  
  ---
  
  ### Answer by username_1 on 2019-03-15. Score: 10
  
  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](https://en.wikipedia.org/wiki/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](https://i.sstatic.net/P6mH2.png)](https://i.sstatic.net/P6mH2.png)
  
  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](https://en.wikipedia.org/wiki/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.](https://i.sstatic.net/S81eT.png)](https://i.sstatic.net/S81eT.png)
  
  To conclude, non-Euclidian data is everywhere.
  
  > **Comments:**
  > **username_0**: 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?!  
  > **username_0**: 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).  
  > **username_0**: 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.  
  > **username_1**: 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 https://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.  
  > **username_0**: 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"_'.  
  > **username_2**: in polar coordinates, the 1st red/blue statistics is linearly separable; though this would also depend on how you interpret the source of the data...  
  > **username_2**: "the shortest path between 2 points isn't necessarily a straight line." this sentence is slightly problematic because "path" and "straight line" are not well-defined if you are not already in some well-defined space (such as euclidian geometry)  
  > **username_1**: @k.c.sayz'k.csayz' I agree. Thats why I prefaced it with "can be generally boiled down to" as in "This is not well defined but this is the gist in order to get an intuition". Either way, I am open to edits.  
  > **username_2**: no worries, i was being a bit pedantic here: i am under the humble assumption that the phrase just refers to a loose set of research goals rather than a specific idea. specifically, i think i've also seen it mentioned as training to constraint parameters to fit some manifold, but the specifics are unclear to me and maybe i'm miss understanding something...  
  > **username_3**: Who voting such an answer up?  
  
  ---
  
  ### Answer by username_2 on 2021-08-25. Score: 1
  
  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](https://en.wikipedia.org/wiki/Metric_(mathematics)) $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](https://en.wikipedia.org/wiki/Isomorphism) 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.
  
  
  ---
  
  ### Answer by username_4 on 2022-04-15. Score: 1
  
  > Where does this type of data arise?
  
  In terms of *learning* on non-Euclidean data, it was probably first coined by prof. Bronstein [here](https://arxiv.org/abs/1611.08097). Recently, prof. Bronstein published, along with other top authors in the field, a [book](https://arxiv.org/pdf/2104.13478.pdf) 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](https://ai.stackexchange.com/a/30368/54143) 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).
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: 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?  
  > **username_4**: 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 :)  
  > **username_0**: Ok, thanks, now, it's a bit clearer. But are you saying that you would train, e.g., a graph neural network with multiple graphs (so one graph would be one data point)? I am not sure that's the case. Moreover, you say that the "domain is usually incorporated into architectures via inductive biases.". What do you mean by that exactly?  
  > **username_4**: 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.  
  > **username_4**: For the part with the inductive biases, there is the CNN example in my initial comment. CNNs are built such that convolutions (which are translation equivariant) take advantage of the nature of the image, which is also translation equivariant/invariant because its underlying domain is R2.  
  > **username_0**: Your example of the dataset with multiple graphs that represent different molecules. is good! Yes, I am familiar with CNNs. But what would be the inductive bias in the case of graphs and GNNs?  
  > **username_4**: 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.  
  > **username_0**: Yes, I am aware of these architectures that take as input adjacency matrices and perform some kind of message passing, which some people call graph convolution. But I wouldn't say that "domain is usually incorporated into architectures via inductive biases". Isn't the input to these graph neural networks e.g. adjacency matrices that represent the structure/domain of the graphs? Then you would work on this input by performing some kind of message passing or conv, right? Isn't this the intuition? So, I wouldn't say that the structure of the graph (or domain) is incorporated in the architecture.  
  > **username_0**: However, there's definitely an inductive bias in graph neural networks, because they "assume" (in the way they are designed and by performing these message passing algorithms) that the data they get is non-Euclidean. So, rather than writing what you wrote, I would write that GNNs have an inductive bias that assumes that the inputs are graphs. It's possible I am missing something because it's been a while I had to deal with GNNs and I forgot the details.  
  > **username_4**: You are correct that "domain is usually incorporated into architecture via inductive biases" is a very vague and possibly incorrect explanation. I made some more edits to the original post. Your last comment is on point, and somehow reflects what I was trying to say. They know the input is a graph, so the "blocks"/"layers" are designed so that they exploit the symmetries of the group (I suppose permutation invariance, at least). Hope my answer is more clear now.  
  
  ---
  
  ### Answer by username_5 on 2020-07-10. Score: 0
  
  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.
  
  > **Comments:**
  > **username_0**: Maybe you should define the concept of a manifold and why it is important to understand the concept of Euclidean and non-Euclidean data.  
  
  ---
  
  