System and method for using graph transduction techniques to make relational classifications on a single connected network

Patent metadata

Field	Value
Publication number	US-9355367-B2
Application number	US-201313787807-A
Country	US
Kind code	B2
Filing date	Mar 7, 2013
Priority date	Mar 7, 2013
Publication date	May 31, 2016
Grant date	May 31, 2016

Abstract

A system and method for extending partially labeled data graphs to unlabeled nodes in a single network classification by weighting the data with a weight matrix that uses a modified graph Laplacian based regularization framework and applying graph transduction methods to the weighted data. The technique may be applied to data graphs that are directed or undirected, that may or may not have attributes and that may be homogeneous or heterogeneous.

First claim

Having thus described our invention, what we claim as new and desire to secure by Letters Patent as follow:

1. A method for extending a partially labeled data graph to unlabeled nodes in a single network classification, comprising:
constructing a weight matrix for data in a single network classification, wherein the weight matrix uses a modified graph Laplacian based regularization framework;
partitioning edges of the data graph into categories;
assigning a weight to each category;
assigning to each edge the weight that is a conical combination of a weight based on affinity of attribute values of nodes connected to said edge;
applying the weight matrix to the data; and
applying a graph transduction method to the weighted data to generate labels for the unlabeled nodes.

2. A method as in claim 1 , wherein the categories are
edges between nodes with the same label;
edges between nodes with opposite labels;
edges between unlabeled nodes;
edges between an unlabeled node and a node with a label 1; and
edges between an unlabeled node and a node with a label −1.

3. A method as in claim 2 , wherein edges between unlabeled nodes are assigned a weight denoting an expectation based on a distribution of edges that have labels.

4. A method as in claim 2 , wherein edges between an unlabeled node and a labeled node are assigned a weight denoting an expectation based on a distribution of edges that have labels, said distribution being limited to those edges having one node equal to the labeled node.

5. A method as in claim 1 , wherein applying a graph transduction method further comprises imposing a tradeoff between a fitting accuracy of a prediction function on labeled data and a smoothness of the prediction function over the graph.

6. A method as in claim 5 , further comprising
estimating the smoothness of the prediction function for the graph Laplacian based regularization framework; and
modifying the prediction function to ensure compatibility between the graph transduction method and the graph Laplacian based regularization framework.

7. A system for extending a partially labeled data graph to unlabeled nodes in a single network classification, comprising:
a weight matrix for data in a single network classification, wherein the weight matrix uses a modified graph Laplacian based regularization framework;
means for partitioning edges of the data graph into categories;
means for assigning a weight to each category;
means for assigning to each edge the weight that is a conical combination of a weight based on affinity of attribute values of nodes connected to said edge;
means for applying the weight matrix to the data;
a graph transduction method applied to the weighted data to generate labels for the unlabeled nodes.

8. A system as in claim 7 , wherein the categories are
edges between nodes with the same label;
edges between nodes with opposite labels;
edges between unlabeled nodes;
edges between an unlabeled node and a node with a label 1; and
edges between an unlabeled node and a node with a label −1.

9. A system as in claim 8 , wherein edges between unlabeled nodes are assigned a weight denoting an expectation based on a distribution of edges that have labels.

10. A system as in claim 8 , wherein edges between an unlabeled node and a labeled node are assigned a weight denoting an expectation based on a distribution of edges that have labels, said distribution being limited to those edges having one node equal to the labeled node.

11. A system as in claim 7 , wherein a graph transduction method is applied by imposing a tradeoff between a fitting accuracy of a prediction function on labeled data and a smoothness of the prediction function over the graph.

12. A system as in claim 11 , further comprising
means for estimating the smoothness of the prediction function for the graph Laplacian based regularization framework; and
means for modifying the prediction function to ensure compatibility between the graph transduction method and the graph Laplacian based regularization framework.

13. A computer implemented system for extending a partially labeled data graph to unlabeled nodes in a single network classification, comprising:
a computer processor for executing computer code;
first computer code for constructing a weight matrix for data in a single network classification, wherein the weight matrix uses a modified graph Laplacian based regularization framework;
second computer code for partitioning edges of the data graph into categories;
third computer code for assigning a weight to each category;
fourth computer code for assigning to each edge the weight that is a conical combination of a weight based on affinity of attribute values of nodes connected to said edge;
fifth computer code for applying the weight matrix to the data; and
sixth computer code for applying a graph transduction method to the weighted data to generate labels for the unlabeled nodes.

Assignees

• IBM

Inventors

• Dhurandhar Amit
• Wang Jun

Classifications

• G06N3/0895

  Weakly supervised learning, e.g. semi-supervised or self-supervised learning · CPC title

• G06N3/08

  Learning methods · CPC title

• G06N99/005 Primary

  Physics · mapped topic

• G06N5/022

  Knowledge engineering; Knowledge acquisition · CPC title

• G06N20/00 Primary

  Machine learning · CPC title