Graph-based methods have attracted interest in areas such as computer vision and network science. In this talk we will present some advances from our research on graph-theoretic approaches for clustering and segmentation. We will focus on two approaches: 1) An unsupervised approach where we extend the geodesic active contours of computer vision to arbitrary graphs by developing efficient finite difference schemes and geometric approximations of gradient and curvature, for which we provide theoretical results on their convergence in probability and asymptotic error bounds for the class of random geometric graphs. 2) A supervised approach where we develop graph-driven diffusion processes on arbitrary graphs by relating the SIR epidemic propagation model to the random walker algorithm. This helps us to develop the normalized random walker by integrating the importance of each node to the final clustering or segmentation solution. For both approaches we provide experimental results for graph clustering and image segmentation.