What is non-Euclidean data? Where does this type of data arises? 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?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Graphs are non-eucledian because the triangle inequality and broadly other eucledian geometric properties doesn't hold just like Jaden mentioned. As far as dataset goes there are various ways of representing a graph. Also afaik, there are a lot of non eucledian spaces like the complex plane, Riemann plane, etc (not sure tho) $\endgroup$ – DuttaA Mar 15 '19 at 17:05
-
$\begingroup$ @DuttaA You should explain in which sense the triangle inequality doesn't hold for graphs. Also, note that the notion of norm is not usually defined for graphs (AFAIK), so you don't even need to talk about the triangle inequality to explain why graphs are non-Euclidean. $\endgroup$ – nbro Mar 15 '19 at 18:01
-
$\begingroup$ in graph theory an edge is what is considered between 2 vertices, so edge1+edge2>edge3 is not necessarily true...And about norms I don't know I just said what I read in a book...So I really don't know what mathematicians think $\endgroup$ – DuttaA Mar 15 '19 at 18:06
$\begingroup$
$\endgroup$
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 eucidian 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(img), 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 its also what modern machine learning is doing. Taking data and mapping it to a space such that the triangle inequality holds.
Lets 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.
answered Mar 15 '19 at 16:14
-
$\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 '19 at 16:20
-
$\begingroup$ I simply believe 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 notion between vertices, so a graph can't be "Euclidean data". I believe 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 '19 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 '19 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$ – Jaden Travnik♦ Mar 15 '19 at 17:23
-
$\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 '19 at 17:51
