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?
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.
The so called squared Euclidean distance describes the dissimilarity between datapoints. A typical example is a database which holds geographical location data of houses on a map. Between two houses a distance in kilometers can be estimated. Because the distance has a numerical value, it's called euclidean. The opposite is an arbitrary distance between datapoints. This allows to get information not on a numercial basis but on a semantic level. For example, if each house is tagged with a construction year, it's possible to group all houses together which were build after the year 2000. This allows to filter the information with a different criteria.
Non-euclidean data is equal to knowledge-based datamining. The information in the database is grounded with natural language, ontologies and a grammar. Non-euclidean information storage is more powerful than the normal one.