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

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.

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, the weight matrix incorporating a conical weighting scheme that weighs importance of links relative to attributes;   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 weight matrix uses a modified graph Laplacian based regularization framework. 
     
     
         3 . A method as in  claim 2 , further comprising:
 partitioning edges of the data graph into categories;   assigning a weight to each category; and   assigning to each edge the weight of its respective category.   
     
     
         4 . A method as in  claim 3 , 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.   
     
     
         5 . A method as in  claim 4 , wherein edges between unlabeled nodes are assigned a weight denoting an expectation based on a distribution of edges that have labels. 
     
     
         6 . A method as in  claim 4 , 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. 
     
     
         7 . A method as in  claim 3 , further comprising assigning to each edge a weight that is a conical combination of a weight based on the respective category and a weight based on affinity of attribute values of nodes connected by said edge. 
     
     
         8 . 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. 
     
     
         9 . A method as in  claim 8 , 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.   
     
     
         10 . 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, the weight matrix incorporating a conical weighting scheme that weighs importance of links relative to attributes;   means for applying the weight matrix to the data; and   a graph transduction method applied to the weighted data to generate labels for the unlabeled nodes.   
     
     
         11 . A system as in  claim 10 , wherein the weight matrix uses a modified graph Laplacian based regularization framework. 
     
     
         12 . A system as in  claim 11 , further comprising:
 means for partitioning edges of the data graph into categories;   means for assigning a weight to each category; and   means for assigning to each edge the weight of its respective category.   
     
     
         13 . A system as in  claim 12 , 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.   
     
     
         14 . A system as in  claim 13 , wherein edges between unlabeled nodes are assigned a weight denoting an expectation based on a distribution of edges that have labels. 
     
     
         15 . A system as in  claim 13 , 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. 
     
     
         16 . A system as in  claim 12 , further comprising assigning to each edge a weight that is a conical combination of a weight based on the respective category and a weight based on affinity of attribute values of nodes connected by said edge. 
     
     
         17 . A system as in  claim 10 , 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. 
     
     
         18 . A system as in  claim 17 , 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.   
     
     
         19 . 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, the weight matrix incorporating a conical weighting scheme that weighs importance of links relative to attributes;   second computer code for applying the weight matrix to the data; and   third computer code for applying a graph transduction method to the weighted data to generate labels for the unlabeled nodes.   
     
     
         20 . A computer implemented system as in  claim 19 , wherein the weight matrix uses a modified graph Laplacian based regularization framework.