Systems, methods, and computer storage media having computer-executable instructions embodied thereon for rewriting queries and labeling word pairs. Queries are received and alternate words are identified for word pairs (i.e., query words and alternate words). Word pair links are presented to users and indicators are received based on actions taken by the users. Labels are assigned to the word pairs based on the indicators and communicated to a classifier.