One explanation for “data whose underlying structure is non-Euclidean” : Typically in computer vision or image processing, we are interested in analyzing functions defined over a “flat” domain, meaning that there is a clear notion of using plain vectors to denote position. For example, an image can be thought of as a function over 2D plane: that is I(x0,y0) is the image intensity at the 2D point (x0,y0), and if I need the value of the image at another pixel ‘d’ units along the x direction I would compute I(x0+d, y0) which is a vector (d,0) added to (x0,y0). This property is very useful for example when you want to define convolutions (the main computational ingredient of CNN’s).

In general, this need not have been the case. For example, if you are analyzing functions over something curved - say like a sphere, you cannot move along the sphere using vectors! This means that you need to redefine the whole notion of convolution.

A typical example is that of geometric shapes (3D point clouds representing some 3d structure). A more data-processing example could be say social networks. In both cases the analysis(regression/classification/detection etc) is to be done on a complex curved surface and not a flat structure like an image. It is obviously harder to imagine a surface modeling social networks, but if you think of it as a graph, then a discrete graph can be construed as a sample set of a surface (even for higher dimensions more that 3)