In this paper, we firstly applied label propagation algorithm (LPA) to coherent optical communication system for nonlinear impairment compensation (NLC), which could exploit the relationship among constellation points to segment the community with only very small amount of label data to predict the label situation on most test data. The effectiveness of the proposed scheme was verified through 28 GBaud polarization division multiplexing (PDM)-16 quadrature amplitude modulation (QAM), PDM-32QAM and PDM-64QAM simulation system. By analyzing the simulation results, we obtained the best propagation coefficient α , which demonstrated that the proposed scheme could effectively make nonlinear decision on received symbols and compensate signal impairment caused by Kerr nonlinear effect and amplified spontaneous emission (ASE) noise, showing a strong robustness and generalization to variations of the transmission environment under different modulation formats, transmission distances, launch power and channel numbers. Then, the proposed scheme was further studied by 20 GBaud PDM-16QAM long-haul transmission experiments. The results demonstrated that the proposed scheme required no training process and exhibited optimistic compensation performance to the coherent optical communication system with nonlinear impairments. Finally, we analyzed computational complexity of the LPA-assisted NLC scheme in detail, which was O(m*N).