Examples relate to providing spatial analysis using attribute graphs. In one examples, there are a number of spatial points that each represent characteristics in a dimensional space. Non-data points are generated in the dimensional space, and a Delaunay triangulation is performed using the spatial points and the non-data points to generate a plurality of edges, where interior points of the plurality of non-data points that are in an interior space of the plurality of spatial points are excluded from the Delaunay triangulation. Next, spatial edges from the plurality of edges that each connect a spatial point that is connected to a first mixed edge to another spatial point that is connected to a second mixed edge are identified, where the spatial edges are used to generate a robust contour of a cluster of the spatial points.