Query expansion and query-document matching using path-constrained random walks

A computing apparatus, comprising:

• at least one processor;
• and
• memory that comprises computer excutable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:
• executing path-constrained random walks over a labeled and directed graph based upon an input query, wherein the labeled and directed graph comprises:
• a first set of nodes that represent queries comprised in clickthrough data from search logs;
• a second set of nodes that represent documents comprised in the clickthrough data from the search logs;
• a third set of nodes that represent words from the queries and the documents;
• and
• edges between nodes that represent relationships between the queries, the documents, and the words;
• wherein the path-constrained random walks traverse edges of the graph between nodes in accordance with predefined path types, and each of the predefined path comprises a respective sequence of relations between the nodes in the graph for traversing as part of a corresponding path-constrained random walk from the path-constrained random walks;
• and
• computing a score for a relationship between a target node that represents a candidate query expansion term and a source node that represents the input query based at least in part upon the path-constrained random walks.

A computer-readable storage medium including computer-executable instructions that, when executed by a processor, cause the processor to perform acts including:

• receiving an input query;
• executing path-constrained random walks over a computer-implemented labeled and directed graph based upon the input query, wherein the labeled and directed graph comprises:
• a first set of nodes that are representative of queries comprised in clickthrough data from search logs;
• a second set of nodes that are representative of documents comprised in the clickthrough data from the search logs;
• a third set of nodes that are representative of words from the queries and the documents;
• and
• edges between nodes that are representative of relationships between the queries, the documents, and the words;
• wherein the path-constrained random walks begin at a source node representative of the input query, traverse edges of the graph between nodes in accordance with differing predefined path types, and end at a target node representative of a candidate document;
• determining respective values for the path-constrained random walks that traverse the edges of the graph between the nodes in accordance with the differing predefined path types;
• and
• combining the respective values for the path-constrained random walks that traverse the edges of the graph between the nodes in accordance with the differing predefined path types to compute a score for a relationship between the target node representative of the candidate document and the source node representative of the input query.