Clustering query refinements by inferred user intent
Methods, systems, and apparatus, including computer programs encoded on computer storage media, for clustering query refinements. One method includes building a representation of a graph for a first query, wherein the graph has a node for the first query, a node for each of a plurality of refinements for the first query, and a node for each document in the document sets of the refinements, and wherein the graph has edges from the first query node to each of the refinement nodes, edges from the first query to each document in the respective document set of the first query, edges from each refinement to each document in the respective document set of the refinement, and edges from each refinement to each co-occurring query of the refinement. The method further includes clustering the refinements into refinement clusters by partitioning the refinement nodes in the graph into proper subsets.
1. A method, comprising:
identifying a plurality of refinements R(q) of a first search query q, each refinement rεR(q) being a search query that follows the first query q in a session of queries submitted to a search system;
identifying a document set D(r) of each of the refinements r, the document set of a refinement being the documents d that have been presented as search results in response to the refinement by the search system and that have received user selections while being presented as the search results;
building a representation of a graph G for the first search query q, wherein the graph G has a node for the first search query q, a node for each of the refinements r, a node for each document d in the document sets of the refinements, and an off-topic node for an off-topic state f and wherein the graph G has edges from the first search query node q to each of the refinement nodes r, edges from the first search query node q to each document node of the respective document set D(q) of the first search query q, edges from each refinement node to each document node in the respective document set D(r) of the refinement, and edges from each refinement node to each node for a co-occurring query Q(r) of the refinement and to the off-topic node;
building a transition probability matrix P for the graph G that includes first probabilities for each edge (r i , d), second probabilities for each edge (r i , f) and third probabilities for each edge (r i , r j );
calculating a visit probability vector for each refinement in the plurality of refinements R(q) from the transition probability matrix P, where each vector has elements representing a probability for each document in the document set D(q) and the document sets of the refinements R(q);
clustering the refinements into refinement clusters by partitioning the visit probability vectors into proper subsets; and
deriving search suggestion for the first search query based on the refinement clusters and providing, to a user device, data that causes the user device to display the search suggestions as search suggestions for the first query.
2. The method of claim 1 , wherein:
for each edge (r i , d), where dεD(r i ) and n d (d|r i ) is the number of user selections received by the document d, a result of the query r i :
P
[
r
i
,
d
]
=
ɛ
×
n
d
(
d
❘
r
i
)
∑
d
k
∈
D
(
r
i
)
n
d
(
d
k
❘
r
i
)
.
3. The method of claim 1 , wherein for each edge (r 1 , f):
P
[
r
i
,
f
]
=
(
1
-
ɛ
)
×
∑
q
′
∈
(
Q
(
r
i
)
-
R
(
q
)
)
n
s
(
r
i
,
q
′
)
∑
q
′
∈
Q
(
r
i
)
n
s
(
r
i
,
q
′
)
.
4. The method of claim 1 , wherein for each edge (r i , r j ):
P
[
r
i
,
r
j
]
=
(
1
-
ɛ
)
×
n
s
(
r
i
,
r
j
)
∑
q
′
∈
Q
(
r
i
)
n
s
(
r
i
,
q
′
)
where ε is a numerical parameter between 0 and 1.
5. The method of claim 1 , wherein for each document d (all of which are terminal in G), then self-transitions:
P[d,d]= 1
6. A system, comprising:
a data processing apparatus; and
a non-transitory computer readable medium storing instruction executable by the data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising:
identifying a plurality of refinements R(q) of a first search query q, each refinement rεR(q) being a search query that follows the first query q in a session of queries submitted to a search system;
identifying a document set D(r) of each of the refinements r, the document set of a refinement being the documents d that have been presented as search results in response to the refinement by the search system and that have received user selections while being presented as the search results;
building a representation of a graph G for the first search query q, wherein the graph G has a node for the first search query q, a node for each of the refinements r, a node for each document din the document sets of the refinements, and an off-topic node for an off-topic state/and wherein the graph G has edges from the first search query node q to each of the refinement nodes r, edges from the first search query node q to each document node of the respective document set D(q) of the first search query q, edges from each refinement node to each document node in the respective document set D(r) of the refinement, and edges from each refinement node to each node for a co-occurring query Q(r) of the refinement and to the off-topic node;
building a transition probability matrix P for the graph G that includes first probabilities for each edge (r i , d), second probabilities for each edge (r i , f), and third probabilities for each edge (r i , r j );
calculating a visit probability vector for each refinement in the plurality of refinements R(q) from the transition probability matrix P, where each vector has elements representing a probability for each document in the document set D(q) and the document sets of the refinements R(q); and
clustering the refinements into refinement clusters by partitioning the visit probability vectors into proper subsets; and
deriving search suggestion for the first search query based on the refinement clusters and providing, to a user device, data that causes the user device to display the search suggestions as search suggestions for the first query.
7. The system of claim 6 , wherein:
for each edge (r 1 , d), where dεD(r i ) and n d (d|r i ) is the number of user selections received by the document d, a result of the query r i :
P
[
r
i
,
d
]
=
ɛ
×
n
d
(
d
❘
r
i
)
∑
d
k
∈
D
(
r
i
)
n
d
(
d
k
❘
r
i
)
.
8. The system of claim 6 , wherein for each edge (r i , f):
P
[
r
i
,
f
]
=
(
1
-
ɛ
)
×
∑
q
′
∈
(
Q
(
r
i
)
-
R
(
q
)
)
n
s
(
r
i
,
q
′
)
∑
q
′
∈
Q
(
r
i
)
n
s
(
r
i
,
q
′
)
.
9. The system of claim 6 , wherein for each edge (r i , r j ):
P
[
r
i
,
r
j
]
=
(
1
-
ɛ
)
×
n
s
(
r
i
,
r
j
)
∑
q
′
∈
Q
(
r
i
)
n
s
(
r
i
,
q
′
)
where ε is a numerical parameter between 0 and 1.
10. The system of claim 6 , wherein for each document d (all of which are terminal in G), then self-transitions:
P[d,d]= 1
11. A non-transitory computer readable medium storing instruction executable by a data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising:
identifying a plurality of refinements R(q) of a first search query q, each refinement rεR(q) being a search query that follows the first query q in a session of queries submitted to a search system;
identifying a document set D(r) of each of the refinements r, the document set of a refinement being the documents d that have been presented as search results in response to the refinement by the search system and that have received user selections while being presented as the search results;
building a representation of a graph G for the first search query q, wherein the graph G has a node for the first search query q, a node for each of the refinements r, a node for each document din the document sets of the refinements, and an off-topic node for an off-topic state/and wherein the graph G has edges from the first search query node q to each of the refinement nodes r, edges from the first search query node q to each document node of the respective document set D(q) of the first search query q, edges from each refinement node to each document node in the respective document set D(r) of the refinement, and edges from each refinement node to each node for a co-occurring query Q(r) of the refinement and to the off-topic node;
building a transition probability matrix P for the graph G that includes first probabilities for each edge (r i , d), second probabilities for each edge (r i , f), and third probabilities for each edge (r i , r j );
calculating a visit probability vector for each refinement in the plurality of refinements R(q) from the transition probability matrix P, where each vector has elements representing a probability for each document in the document set D(q) and the document sets of the refinements R(q); and
clustering the refinements into refinement clusters by partitioning the visit probability vectors into proper subsets; and
deriving search suggestion for the first search query based on the refinement clusters and providing, to a user device, data that causes the user device to display the search suggestions as search suggestions for the first query.