A method, system and computer program product are presented for generating a description in natural language for a color. The method includes acquiring a list of tuples, generating a graph by using each of the tuples as a node and adding edges between the nodes when a difference between colors of the nodes in terms of human perception is outside a predetermined range, filtering the edges based on external color comparative descriptions, incorporating a new node in the graph by finding a closest neighbor node based on the color difference and adding a new edge between the new node and the closest neighbor node, learning a feature vector for each of the nodes by using message passing and the colors of the nodes as initial seeds, and generating a description of the new node by using each of the learned feature vectors as initial states for a neural-network based decoder.