LINK-BASED CLASSIFICATION OF GRAPH NODES

• US 20090132561A1
• Filed: 11/21/2007
• Published: 05/21/2009
• Est. Priority Date: 11/21/2007
• Status: Abandoned Application

• Current Assignee: AT&T Labs Incorporated (AT&T, Inc.), Rutgers University
• Original Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Inventors: Rozenbaum, Irina, Bhagat, Smriti, Cormode, Graham
• Application Number:
  US11/943,681
• Publication Number:
  US 20090132561A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A method of labeling unlabeled nodes in a graph that represents objects that have an explicit structure between them. A computing device can use a labeling engine to labeled nodes in a graph that are labeled and can identify an unlabeled node in the graph that is structurally associated with the labeled nodes. The labeling engine can label the unlabeled node with the label of the labeled node based on the structural association between the unlabeled node and the labeled node.

Claims

1. A method of determining information associated with an object represented as a node in a graph comprising:

associating a label of at least one labeled node with an unlabeled node based on a structural association between the unlabeled node and the labeled node.

2. The method of claim 1, wherein associating the label comprises associating the label of the at least one labeled node with the unlabeled node using a local iterative approach.

3. The method of claim 2, wherein associating the label comprises determining a frequency at which the label occurs based on a connection between the unlabeled node and the labeled node.

4. The method of claim 2, wherein the graph comprises a node of a type different than that of the unlabeled node, the method further comprising associating a pseudo-label with the node of the different type.

5. The method of claim 4, wherein the node of the different type is structurally associated with the unlabeled node, the associating of the label being based on the structural association between the node of the different type and the unlabeled node.

6. The method of claim 2, wherein the label associated with the unlabeled node changes during an iteration of the local iterative approach.

7. The method of claim 1, wherein associating the label comprises associating the label of the at least one labeled node with the unlabeled node using a global nearest neighbor approach.

8. The method of claim 7, wherein the structural association comprises a similarity between a node interconnectivity of a first neighborhood of the unlabeled node and a node interconnectivity of a second neighborhood associated with the labeled node.

9. A computer-readable medium comprising instructions executable by a computing device for determining information associated with an object represented as a node in a graph by:

associating a label of at least one labeled node with an unlabeled node based on a structural association between the unlabeled node and the labeled node.

10. The medium of claim 9, wherein associating the label comprises associating the label of the at least one labeled node with the unlabeled node using a local iterative approach.

11. The medium of claim 10, wherein associating the label comprises determining a frequency at which the label occurs based on a connection between the unlabeled node and the labeled node.

12. The medium of claim 10, wherein the graph comprises a node of the type different than that of the unlabeled node, the medium further comprising associating a pseudo-label with the node of the different type.

13. The medium of claim 12, wherein the node of a different type is structurally associated with the unlabeled node, the associating of the label being based on the structural association between the node of the different type and the unlabeled node.

14. The medium of claim 10, wherein the label associated with the unlabeled node changes during an iteration of the local iterative approach.

15. The medium of claim 9, wherein associating the label comprises associating the label of the at least one labeled node with the unlabeled node using a global nearest neighbor approach.

16. The medium of claim 15, wherein the structural association comprises a similarity between a node interconnectivity of a first neighborhood of the unlabeled node and a node interconnectivity of a second neighborhood associated with the labeled node.

17. A system for inferring a label classification associated with an objected represented as a node in a graph:

a computing device configured to associate a label associated with at least one labeled node with at least one unlabeled node based on the structural association between the unlabeled node and the labeled node in the graph.

18. The system of claim 17, wherein the computing device performs at least one of a local iterative approach or a global nearest neighbor approach.

19. The system of claim 18, wherein the structural association is a similarity between a node interconnectivity of a first neighborhood of the unlabeled node and a node interconnectivity of a second neighborhood of the labeled node.

20. The system of claim 17, wherein the graph comprises a node of a different type compared to the unlabeled node for which a pseudo-label is assigned.