Summary: This paper describes a new approach for regularising triangulated graphs. We commence by embedding the graph onto a manifold using the heat-kernel embedding. Under the embedding, each first-order cycle of the graph becomes a triangle. Our aim is to use curvature information associated with the edges of the graph to effect regularisation. Using the difference in Euclidean and geodesic distances between nodes under the embedding, we compute sectional curvatures associated with the edges of the graph. Using the Gauss-Bonnet theorem we compute the Gaussian curvature associated with each node from the sectional curvatures and through the angular excess of the geodesic triangles. Using the curvature information we perform regularisation with the advantage of not requiring the solution of a partial differential equation. We experiment with the resulting regularization process, and explore its effect on both graph matching and graph clustering.