Abstract The defificiency of segmentation labels is one of the main obstacles to semantic segmentation in the wild. To alleviate this issue, we present a novel framework that generates segmentation labels of images given their image-level class labels. In this weakly supervised setting, trained models have been known to segment local discriminative parts rather than the entire object area. Our solution is to propagate such local responses to nearby areas which belong to the same semantic entity. To this end, we propose a Deep Neural Network (DNN) called AffifinityNet that predicts semantic affifinity between a pair of adjacent image coordinates. The semantic propagation is then realized by random walk with the affifinities predicted by AffifinityNet. More importantly, the supervision employed to train AffifinityNet is given by the initial discriminative part segmentation, which is incomplete as a segmentation annotation but suffificient for learning semantic affifinities within small image areas. Thus the entire framework relies only on image-level class labels and does not require any extra data or annotations. On the PASCAL VOC 2012 dataset, a DNN learned with segmentation labels generated by our method outperforms previous models trained with the same level of supervision, and is even as competitive as those relying on stronger supervision