Source-linked AI summary
Simrank++: Query rewriting through link analysis of the click graph
Ioannis Antonellis, Hector Garcia-Molina, Chi-Chao Chang
TL;DR
Sponsored-search systems need query rewrites when direct bids or text-based methods provide insufficient coverage. This paper analyzes historical query–ad click graphs, extending SimRank with edge weights and evidence, and finds that the enhanced methods produce more and better rewrites, with weighted SimRank overall best. The paper does not address click or ad fraud.
Problem
Sponsored-search query rewriting must find related queries and potentially useful ads despite limited query and ad text and sparse bid coverage.
Method
The paper uses historical weighted bipartite click graphs and extends SimRank with edge weights and evidence to identify direct and indirect query similarities.
Results
Weighted-based SimRank is the overall best method, while evidence-based SimRank raises precision at 5 rewrites from 75% to 80% and five-rewrite coverage from 79% to 89%.
Takeaways & Limitations
Enhanced SimRank methods can significantly increase the number and quality of useful sponsored-search query rewrites over SimRank and another basic technique.
Takeaways & Limitations
The paper does not address click or ad fraud, although rewriting strategies may need adjustment to protect against it.
Abstract
from arXiv · showhide
We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank as a way to identify queries similar to q, i.e., queries whose ads a user may be interested in. We argue that Simrank fails to properly identify query similarities in our application, and we present two enhanced version of Simrank: one that exploits weights on click graph edges and another that exploits ``evidence.'' We experimentally evaluate our new schemes against Simrank, using actual click graphs and queries form Yahoo!, and using a variety of metrics. Our results show that the enhanced methods can yield more and better query rewrites.
1 Introduction
The paper addresses sponsored-search query rewriting by using historical query–ad click graphs to find useful related queries. It extends SimRank with edge weights and supporting evidence, and evaluates the methods on Yahoo! data.
- Motivation: Sponsored-search systems need related-query rewrites when direct bids are unavailable, so they can retrieve ads likely to interest the user.The front end generates similar queries, which are then used to find additional relevant ads.
- Motivation: Text-based rewriting is limited because ads and queries contain little text, while bid databases cover relatively few queries.These constraints motivate additional rewriting techniques beyond document-search methods.
- Approach: The proposed framework analyzes a historical weighted bipartite click graph to identify directly and indirectly related queries.Queries connect through ads that users clicked after issuing those queries.
- Approach: The paper identifies cases where standard SimRank fails to transfer query–ad relationships into intuitively correct similarity scores.The contribution is framed specifically around adapting similarity computation to sponsored-search click-graph structure.
- Evaluation: The two SimRank extensions incorporate click-graph edge weights and evidence supporting similarity between queries.Both extensions are evaluated against SimRank using Yahoo! click graphs, Yahoo! query logs, several metrics, and manual editorial judgments.
- Evaluation: The enhanced methods significantly increase the number of useful rewrites compared with SimRank and another basic technique.The evaluation includes manual assessment of query-rewrite pairs by Yahoo!’s Editorial Evaluation Team.
2 Problem Definition
The paper defines query similarity through shared clicked ads and longer click-graph paths, using a weighted bipartite graph of queries and ads. It also states important scope boundaries, including exclusion of click fraud.
- Graph model: The click graph is an undirected, weighted bipartite graph connecting queries to ads clicked after those queries were issued.Each edge records impressions, clicks, and position-adjusted expected click rate.
- Similarity objective: Query similarity reflects the likelihood that ads clicked for one query will also be clicked for another.Shared clicked ads provide direct evidence, while chains through other ads can indicate weaker indirect relatedness.
- Similarity objective: Absence of a common clicked ad does not establish that two queries are dissimilar, because the relevant ads may not have been displayed during collection.Missing bids are one stated reason the click graph may fail to expose similarity.
- Scope: The paper does not address click or ad fraud, although rewriting strategies may need adjustment to protect advertisers and search engines.Fraud is explicitly outside the paper’s scope.
- Interpretation: The rewriting task is framed as collaborative filtering, with queries treated as users and clicked ads treated as recommendations.The paper seeks similar queries rather than directly predicting recommended ads, while tuning similarity for sponsored search.
3 Similar queries
The paper defines query similarity through shared clicked ads: queries are similar when users tend to click the same advertisements. Counting common ads captures direct overlap but misses broader graph structure.
- Queries such as “pc” and “camera” are considered similar because they connect through a common ad.
- Common-ad counting gives “pc” equal similarity to “camera” and “digital camera,” while “camera” scores higher with “digital camera.”
- Common-ad counting assigns zero similarity to “pc”-“tv” because it ignores relationships propagated through the rest of the graph.
4 Simrank-based query similarity
Bipartite Simrank recursively estimates query and ad similarities from their relationships in the click graph. Its iterative scores are symmetric and incorporate the graph’s broader structure, but can fail to distinguish query pairs with different shared-ad evidence.
- Bipartite Simrank measures query similarity through similarity between the ads connected to each query, and analogously measures ad similarity through connected queries.
- The method assigns self-similarity 1 and uses decay constants C1 and C2 between 0 and 1 for cross-object similarity.
- Simrank has a unique simultaneous solution, and its similarity scores are symmetric between object pairs.
- Simrank gives “camera” and “digital camera” the same similarity with other queries despite their having two common ads rather than one with “tv.”
5 Random walks behind Simrank
Simrank can be interpreted as the expected meeting time of two random surfers walking from two starting nodes. Uniform transitions distribute movement across neighbors, while decay factors permit self-transitions.
- A Simrank score measures how soon two random surfers are expected to meet at the same node after starting from two objects.
- With uniform transitions, a surfer at a node with n out-neighbors moves to each neighbor with probability 1/n when C1 = C2 = 1.
- Decay factors C1 and C2 control self-transition probabilities for the two node sets.
- For C1 < 1, a surfer remains at the same node with probability 1 − C1 and moves to each of n neighbors with probability C1/n.
6 Simrank in complete bipartite graphs
Complete bipartite subgraphs expose a weakness in Simrank’s treatment of structural similarity. Across the sample graphs, Simrank can rank a weaker connection above a stronger one initially and eventually assign equal scores despite different shared-ad evidence.
- 6 Simrank in complete bipartite graphs: A complete bipartite graph connects every vertex in one node set to every vertex in the other; the paper uses K2,2 and K1,2 examples from click graphs.
- 6 Simrank in complete bipartite graphs: Theorem 6.1 states that, at every positive iteration, the K1,2 pair’s score is at least the K2,2 pair’s score.
- 6 Simrank in complete bipartite graphs: For Km,2 and Kn,2 with m < n, the limiting scores are equal if and only if C1 = C2 = 1.
- 6 Simrank in complete bipartite graphs: These results indicate that Simrank can understate the stronger similarity of queries sharing two advertisers compared with queries sharing one.
7 Revising Simrank
The paper revises SimRank by multiplying similarity with evidence scores, improving similarity behavior in sample graphs and complete bipartite graphs.
- Evidence-based SimRank: Evidence-based SimRank defines graph evidence between two nodes and incorporates that evidence into the SimRank equations.The evidence score increases with the number of common neighbors and approaches one as common neighbors increase.
- Evidence-based SimRank: Evidence-based similarity scores can be obtained after a limited number of SimRank iterations by multiplying the scores by evidence.The paper denotes these as evidence-based similarity scores after k iterations.
- Results: For the sample click graphs, evidence-based SimRank ranks “camera” and “digital camera” above “pc” and “camera” after the first iteration.Table 4 reports the successive similarity scores for the first pair under C1 = C2 = 0.8.
- Results: A theorem states that, for complete bipartite graphs with different numbers of nodes, the limiting evidence-based scores preserve the intended similarity ordering.The stated result is limk→∞sim(k)(A, B) < limk→∞sim(k)(C, D) for the defined graph pair.
8 Weighted Simrank
Weighted SimRank modifies the random walk to use click-graph edge weights and spread, producing similarity scores consistent with those weights.
- Motivation: Weighted SimRank addresses the problem of deriving query similarities that both use click-graph edge weights and remain consistent with them.The section contrasts this with earlier methods that ignored edge-weight information.
- Consistent similarity scores: The paper defines consistency so that similarity comparisons follow edge weights under specified relationships between weight variances.The rules require higher similarity when the compared edge weight is higher, with variance conditions determining the comparison.
- Weighted SimRank: Weighted SimRank changes the random walk transition probability using both an edge weight and the spread value of the destination node.This design is intended to satisfy the consistency rules.
- Results: Theorem 8.1 states that weighted SimRank produces similarity scores consistent with the weights of any weighted bipartite graph.The theorem applies to every pair of nodes in the query-side node set V1.
- Weighted SimRank: The resulting weighted similarity scores are expressed using factors W(q, i) and W(a, i) associated with graph connections.The supplied passage introduces these factors but does not provide their full definitions.
9 Experiments
The experiments compare SimRank variants with Pearson correlation on Yahoo! click-graph data, using rewrite quality, coverage, depth, and evidence-based ordering metrics.
- Experimental design: The evaluation compares SimRank, evidence-based SimRank, and weighted SimRank against a Pearson-correlation query-rewriting baseline.The methods are evaluated as techniques for generating query rewrites.
- Dataset: The click graph covers approximately 15 million queries, 14 million ads, and 28 million edges from two weeks of US Yahoo! search.Edges represent query-ad pairs with at least one click and include clicks, impressions, and expected click rate.
- Dataset: The evaluation uses 120 queries selected from a standardized 1200-query live-traffic sample after filtering for presence in the five extracted subgraphs.The selection procedure gives rarer queries lower representation probability than more popular queries.
- Rewrite generation: Each method produces up to 100 rewrites per query before stemming and bid-term filtering, with evaluation limited to at most five remaining rewrites.The number of remaining rewrites is called the method’s depth.
- Evaluation metrics: Professional Yahoo! evaluators score each query-rewrite pair from 1 to 4, where 1 is most relevant and 4 is a clear mismatch.A second evaluation removes selected edges and tests whether methods recover the desirable ordering from the remaining graph evidence.
- Evaluation metrics: The metrics include precision/recall and query coverage, with precision/recall evaluated under two relevant-versus-irrelevant score partitions.The supplied metric descriptions distinguish scores 1–2 versus 3–4 and score 1 versus scores 2–4.
10 Results
SimRank improves over Pearson, while evidence and edge weights further improve rewrite quality; weighted SimRank is especially strong at predicting desirable rewrite order.
- Query coverage: SimRank provides rewrites for 98% of sampled queries, compared with 41% for Pearson.The broader coverage reflects SimRank’s use of whole-graph structure rather than requiring a shared ad.
- Precision and recall: Simple SimRank substantially improves precision over Pearson, while evidence-based and weighted variants further boost precision under both relevance classifications.The two classifications use scores 1–2 versus 3–4, and score 1 versus scores 2–4.
- Rewriting depth: The enhanced schemes provide the full five rewrites for over 85% of queries.The comparison is between Pearson and the SimRank variations’ rewriting depth.
- Desirability prediction: Weighted SimRank correctly predicts the desirable rewrite for 46 of 50 queries (92%), versus 27 of 50 (54%) for simple and evidence-based SimRank.The latter two methods use graph structure without graph weights in the similarity computation.
- Precision and recall: Weighted SimRank reaches 86% precision after five rewrites, compared with 80% for evidence-based SimRank and 75% for simple SimRank.These values are reported for the P@X evaluation.
- Discussion: Evidence scores increase query coverage by 1%, raise five-rewrite precision from 75% to 80%, and increase five-rewrite depth from 79% to 89%.Weighted SimRank maintains evidence-based coverage at 99% and raises five-rewrite precision to 86%.
11 Conclusions
The paper concludes that weighted-based Simrank performs best overall for click-graph query rewriting, while identifying open issues involving spam clicks and semantic similarity.
- Weighted-based Simrank is the overall best method for generating rewrites based on a click graph.
- The analysis does not address all query rewriting issues.The authors specifically identify spam clicks and combining click-graph scores with semantic text-based similarities as open directions.
- Spam clicks can mislead the presented techniques, motivating spam-resistant variations.
- The authors propose exploring combinations of similarity scores with semantic text-based similarities.
A Simrank similarity scores on complete bipartite graphs
The appendix analyzes Simrank and evidence-based Simrank on complete bipartite graphs, showing that graph structure and decay factors affect the resulting similarity scores.
- Simrank similarity scores on complete bipartite graphs: Theorem A.2 states that, after every positive iteration, Simrank assigns at least as much similarity to the pair in K1,2 as to the pair in K2,2.
- Simrank similarity scores on complete bipartite graphs: Theorem A.3 states that the limiting similarities for the K1,2 and K2,2 cases are equal if and only if C1 = C2 = 1.
- Simrank similarity scores on complete bipartite graphs: The appendix extends the comparison to Km,2 and Kn,2 for m < n, including a condition for equality of limiting scores.
- Evidence-based Simrank similarity scores on complete bipartite graphs: The evidence-based Simrank analysis similarly considers complete bipartite graphs and decay factors greater than 1.