Outlier detection aims at detecting abnormal values from observational data, which has been used in various files. In outlier detection, normal data are generally embedded in some kind of intrinsic structure that is not suitable for characterizing outliers. Hence, how to effectively utilize the difference in structure between normal data and outliers will contribute to the identification of outlier. Then, a novel label propagation-based outlier detection algorithm is proposed in this paper. To characterize the above intrinsic structure, the graph model is adopted for implementing multiple label propagations. Thus, the difference in structure between normal data and outliers will be identical to the difference of label confidence between them. Furthermore, the statistical characteristic of the label confidences associated to those normal data is explored to give the final ensemble decision on the abnormity of the input test data. The experimental results have validated the effectiveness of the proposed method.