Spectral segmentation has been shown to produce perceptually meaningful groupings. The underlying similarity matrices are usually very large. Several approximations - deterministic and stochastic - are used in practice. The approximations usually use only local information. It has been shown recently that a few random long-range interactions facilitate emergence of structure in several domains like Ising models. In this paper we explore the use of long-range interactions in spectral segmentation.