A computer-implemented technique is described herein for shortening an original query into one or more sub-queries. The technique chooses the sub-query(ies) such that they preserve the original intent of the original query. To accomplish this goal, the technique uses graph-based analysis to generate a set of richly descriptive query-context-specific feature values for each sub-query, and then uses those feature values to score the relevance of that sub-query.