This paper introduces a new graph-based method for segmenting breast tumors in US images.Segmentation for breast tumors in ultrasound (US) images is crucial for computer-aided diagnosis system, but it has always been a difficult task due to the defects inherent in the US images, such as speckles and low contrast.The proposed segmentation algorithm constructed a graph using improved neighborhood models. In addition, taking advantages of local statistics, a new pair-wise region comparison predicate that was insensitive to noises was proposed to determine the mergence of any two of adjacent subregions.Experimental results have shown that the proposed method could improve the segmentation accuracy by 1.5–5.6% in comparison with three often used segmentation methods, and should be capable of segmenting breast tumors in US images.