Query log mining for detecting spam hosts

• US 8,996,622 B2
• Filed: 09/30/2008
• Issued: 03/31/2015
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Donato, Debora, Gionis, Aristides, Corsi, Claudio, Ferragina, Paolo
• Primary Examiner(s): MIAH, RAZU A
• Application Number:
  US12/241,731
• Publication Number:
  US 20100082752A1
• Time in Patent Office: 2,373 Days
• Field of Search: 709204-207, 709223-226, 707/3, 726 22- 23
• US Class Current: 709/206
• CPC Class Codes: G06F 16/95 Retrieval from the web
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Disclosed are methods and apparatus for detecting spam hosts. In one embodiment, one or more graphs are generated using data obtained from a query log, where the one or more graphs include at least one of an anticlick graph or a view graph. Values of one or more syntactic features of the one or more graphs are ascertained. Values of one or more semantic features of the one or more graphs are determined by propagating categories from a web directory among nodes in each of the one or more graphs. Spam hosts are then detected based upon the values of the syntactic features and the semantic features.

Claims

1. A method, comprising:

generating by a network device one or more graphs using data obtained from a query log, the one or more graphs including an anticlick graph, wherein the anticlick graph represents information pertaining to documents in previously provided search results that, according to the data obtained from the query log, have not been clicked by a user that submitted a corresponding search query and does not represent information pertaining to documents in the previously provided search results that, according to the data obtained from the query log, have been clicked by the user that submitted the corresponding search query, wherein the anticlick graph includes one or more nodes representing or corresponding to documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query;

ascertaining by the network device values of one or more syntactic features of the one or more graphs;

determining by the network device values of one or more semantic features of the one or more graphs by propagating categories from a web directory among nodes in each of the one or more graphs; and

detecting by the network device spam hosts based upon the values of the syntactic features and the semantic features;

wherein the anti-click graph includes a host-based graph or a document-based graph, wherein the nodes of the host-based graph includes one or more host nodes representing hosts corresponding to the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query, and wherein the nodes of the document-based graph includes one or more document nodes representing the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query.

2. The method as recited in claim 1, wherein the one or more semantic features comprise one or more measures of dispersion of each of the host nodes in the host-based graph.

3. The method as recited in claim 1, wherein the one or more semantic features comprise one or more measures of dispersion of each of the document nodes in the document-based graph.

4. The method as recited in claim 1, wherein the one or more graphs further comprise a click graph.

5. The method as recited in claim 1, wherein the one or more graphs further comprise a click graph and a view graph.

6. The method as recited in claim 1, wherein the one or more syntactic features of the one or more graphs includes at least one of topQx or topTy.

7. The method as recited in claim 6, wherein x is 1 and y is 1.

8. The method as recited in claim 6, wherein x is 100 and y is 100.

9. The method as recited in claim 1, wherein propagating is performed using a tree-based propagation by weighted average.

10. The method as recited in claim 1, wherein propagating is performed by random walk.

11. The method as recited in claim 1, wherein the web directory is DMOZ.

12. The method as recited in claim 1, wherein determining values of the one or more semantic features of the one or more graphs further comprises:

categorizing by the network device a subset of hosts in the anti-click graph that can found in a web directory that includes a plurality of categories such that each of the subset of hosts is associated with one or more of the plurality of categories; and

propagating by the network device the one or more of the plurality of categories to other host nodes and query nodes in the anti-click graph such that each node in the anti-click graph has an associated category tree.

13. The method as recited in claim 1, wherein determining values of the one or more semantic features of the one or more graphs further comprises:

categorizing by the network device a subset of documents in the anti-click graph that can found in a web directory that includes a plurality of categories such that each of the subset of documents is associated with one or more of the plurality of categories; and

propagating by the network device the one or more of the plurality of categories to other document nodes and query nodes in the anti-click graph such that each node in the anti-click graph has an associated category tree.

14. The method as recited in claim 13, further comprising:

associating by the network device a score with each category tree, wherein the category tree indicates a semantic spread of the corresponding node.

15. A non-transitory computer-readable medium storing thereon computer-readable instructions, comprising:

instructions for generating one or more graphs using data obtained from a query log, the one or more graphs including an anticlick graph, wherein the anticlick graph represents information pertaining to search results that, according to the data obtained from the query log, have not been clicked by a user that submitted a corresponding search query and does not represent information pertaining to search results that, according to the data obtained from the query log, have been clicked by the user that submitted the corresponding search query, wherein the anticlick graph includes one or more edges, the one or more edges being between a query and the corresponding search results that, according to the data obtained from the query log, have not been clicked by the user that submitted the query;

instructions for propagating categories from a web directory among nodes in each of the one or more graphs;

instructions for determining values of one or more semantic features of the one or more graphs after propagating categories among the nodes; and

instructions for detecting spam hosts based upon the values of the semantic features;

wherein the anti-click graph includes a host-based graph or a document-based graph, wherein the nodes of the host-based graph includes one or more host nodes representing hosts corresponding to the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query, and wherein the nodes of the document-based graph includes one or more document nodes representing the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query.

16. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

generating one or more graphs using data obtained from a query log, the one or more graphs including an anticlick graph, wherein the anticlick graph represents a search query and information pertaining to documents in corresponding search results that, according to the data obtained from the query log, have not been clicked by a user that submitted the search query, wherein the anticlick graph does not represent information pertaining to documents in the corresponding search results that, according to the data obtained from the query log, have been clicked by the user that submitted the search query, wherein the anticlick graph includes one or more edges, the one or more edges being between a query and the corresponding search results that, according to the data obtained from the query log, have not been clicked by the user that submitted the query;

ascertaining values of one or more syntactic features of the one or more graphs;

propagating categories from a web directory among nodes in each of the one or more graphs;

determining values of one or more semantic features of the one or more graphs; and

detecting spam hosts using the values of the syntactic features and the semantic features;

wherein the anti-click graph includes a host-based graph or a document-based graph, wherein the nodes of the host-based graph includes one or more host nodes representing hosts corresponding to the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query, and wherein the nodes of the document-based graph includes one or more document nodes representing the documents that, according to the data obtained from the query log, have not been clicked by the user that submitted the corresponding search query.

17. The apparatus as recited in claim 16, wherein the one or more semantic features comprise one or more measures of dispersion of each document node or host node in the one or more graphs.

18. The apparatus as recited in claim 16, wherein the one or more syntactic features of the one or more graphs comprises at least one of topQx or topTy.

19. The apparatus as recited in claim 16, wherein the search results that have not been clicked by the user that submitted the query and are represented in the anti-click graph were, according to the data obtained from the query log, ranked in the search results before one of the search results that have been clicked by the user that submitted the query.

20. The apparatus as recited in claim 16, wherein the search results that have not been clicked by the user that submitted the query and are represented in the anti-click graph were, according to the data obtained from the query log, ranked in the search results before a first one of the search results that have been clicked by the user that submitted the query.