LEARNING AND REASONING FROM WEB PROJECTIONS

• US 20080313119A1
• Filed: 06/15/2007
• Published: 12/18/2008
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dumais, Susan T., Horvitz, Eric J., Leskovec, Jurij
• Granted Patent: US 7,970,721 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system and method that facilitates and effectuates making an inference related to objects of interest within a context. A web projection component can generate sub graphs by projecting objects o interest onto a web graph representing a superset or partially overlapping set of objects to the objects of interest. An inference component can provide inferences relating to the quality of the objects of interest, adjustments to the context, and patterns recognized from graphical properties of the sub graphs.

Claims

1. A system for analyzing one or more objects of interest within a context comprising:

a web projection component that projects the one or more objects of interest onto a web graph to produce one or more sub graphs; and

an inference component that makes an inference related to at least one of the context or the one or more objects of interest based upon graphical properties of the one or more sub graphs.

2. The system of claim 1, wherein the context delineates the one or more objects of interest from a larger set of objects in a data store.

3. The system of claim 2, wherein the context is one of defined by one or more users, defined by one or more systems, or inferred by the system.

4. The system of claim 2, wherein the context is at least one of results from a user or system query, objects a user has previously viewed, pages on a website, newly added objects, objects above or below an occurrence threshold, objects that have recently changed, objects linked to a particular object, or objects downloaded within a period of time

5. The system of claim 2, wherein the web graph comprises nodes representing objects from the data store and edges between nodes representing associations between objects.

6. The system of claim 1, wherein the one or more sub graphs are at least one of a context sensitive projection sub graph or a context sensitive connection sub graph.

7. The system of claim 6, wherein the context sensitive projection sub graph comprises nodes representing nodes from the web graph, wherein each node contains at least one object from the one or more objects of interest, the context sensitive projection sub graph further comprises edges representing edges between nodes from the web graph that contain at least one object from the one or more objects of interest.

8. The system of claim 7, wherein the context sensitive connection sub graph comprises all nodes and edges from the context sensitive projection graph, along with a minimal set of edges and connection nodes to connect all nodes.

9. The system of claim 8, wherein the graphical properties are based upon at least one of an individual sub graph, or a plurality of sub graphs, where in the graphical properties are further based at least on one of nodes, edges, paths, connected components, connector nodes, path shape, path length, node ratio, edge ratio, path ratio, clustering coefficient, node degree, node density, edge density, or node size

10. The system of claim 1, wherein the inference at least one of predicts the quality of the one or more objects of interest, predicts an adjustment of the context, or identifies one or more patterns based upon graphical properties of the one or more sub graphs.

11. The system of claim 10, wherein the quality of the one or more objects of interest can be associated with individual objects from the one or more objects of interest, a sub set of the one or more objects of interest, or the entire set of one or more objects of interest.

12. The system of claim 10, wherein the quality can be indicated by a numerical ranking, alpha ranking, alpha-numeric ranking, ordered ranking, range, or class.

13. The system of claim 10, wherein predicting an adjustment of the context is at least one of whether a context will be narrowed or broadened, whether a related or completely different context is needed, if a context adjustment is needed, or predicting one or more delineation criteria for objects of interest.

14. The system of claim 10, wherein identifying a pattern is at least of identifying clusters, loops, anomalies, linkage patterns, edge density, path length between nodes, and patterns matching or approximating stored reference patterns

15. A method for analyzing objects of interest within a context comprising:

projecting objects of interest onto a web graph to produce one or more sub graphs; and

making an inference related to at least one of the context or objects of interest based upon graphical properties of the one or more sub graphs.

16. The method of claim 15, wherein the web graph comprises nodes representing objects from a data store and edges between nodes representing associations between objects.

17. The method of claim 15, wherein projecting query results onto a web graph comprises:

identifying each node on the web graph that contains an object of interest; and

identifying each edge on the web graph between identified nodes; and

copying each identified node and each identified edge onto a sub graph.

18. The method of claim 17, further comprising:

identifying a shortest path from web graph between the largest set of connected nodes in the sub graph to the second largest set of connected nodes in the sub graph; and

adding nodes and edges along the identified shortest path to the sub graph to form a new largest set of connected nodes; and

identifying a shortest path from web graph between the new largest set of connected nodes in the sub graph to the second largest set of connected nodes in the sub graph and adding nodes and edges along the identified shortest path to the sub graph to form a new largest set of connected nodes until all nodes of the sub graph are connected.

19. The method of claim 15, wherein making the inference comprises at least one of predicting the quality of the objects of interest, predicting one or more changes to the context, or identifying one or more patterns based upon graphical properties of the one or more sub graphs.

20. A system for analyzing objects of interest within a context comprising:

means for projecting objects of interest onto a web graph to produce one or more sub graphs; and

means for making an inference related to at least one of the context or objects of interest based upon graphical properties of the one or more sub graphs.