"....Treating every pixel as a node in a graph sounded scary at first..."

Li et al handle this issue in 'Lazy Snapping, SIGGRAPH 2004' by pre-segmenting (unsupervised) the image into small color coherent regions, and constructing the graph on resulting regions, instead of pixels. This simple idea reduces the graph complexity by orders of magnitude, and makes their segmentation run at almost interactive rates. (0.2 seconds per image or so).