Extraction of inference rules from heterogeneous graphs

Abstract

According to an aspect, a heterogeneous graph in a data store is accessed. The heterogeneous graph includes a plurality of nodes having a plurality of node types. The nodes are connected by edges having a plurality of relation types. One or more intermediary graphs are created based on the heterogeneous graph. The intermediary graphs include intermediary nodes that are the relation types of the edges of the heterogeneous graph and include intermediary links between the intermediary nodes based on shared instances of the nodes between relation types in the heterogeneous graph. The intermediary graphs are traversed to find sets of relations based on intermediary links according to a template. An inference rule is extracted from the heterogeneous graph based on finding sets of relations in the intermediary graphs. The inference rule defines an inferred relation type between at least two of the nodes of the heterogeneous graph.

What is claimed is: 
     
         1 . A method comprising:
 accessing a heterogeneous graph in a data store, the heterogeneous graph comprising a plurality of nodes having a plurality of node types, the nodes connected by edges having a plurality of relation types;   creating one or more intermediary graphs based on the heterogeneous graph, the one or more intermediary graphs comprising intermediary nodes that are the relation types of the edges of the heterogeneous graph and further comprising intermediary links between the intermediary nodes based on shared instances of the nodes between the relation types in the heterogeneous graph;   traversing the one or more intermediary graphs to find sets of relations based on the intermediary links according to a template; and   extracting inference rules from the heterogeneous graph based on finding the sets of relations in the one or more intermediary graphs, each of the inference rules defining an inferred relation type between at least two of the nodes of the heterogeneous graph.   
     
     
         2 . The method of  claim 1 , wherein creating one or more intermediary graphs further comprises:
 creating a source intermediary graph comprising the intermediary nodes connected with undirected links as the intermediary links, the undirected links based on the relation types of the intermediary nodes sharing a common source node in the heterogeneous graph.   
     
     
         3 . The method of  claim 2 , wherein creating one or more intermediary graphs further comprises:
 creating a target intermediary graph comprising the intermediary nodes connected with undirected links as the intermediary links, the undirected links based on the relation types of the intermediary nodes sharing a common target node in the heterogeneous graph.   
     
     
         4 . The method of  claim 3 , wherein creating one or more intermediary graphs further comprises:
 creating a target-source intermediary graph comprising the intermediary nodes connected with directed links as the intermediary links, the directed links based on the relation types of the intermediary nodes having a source node that is a target node of another relation type in the heterogeneous graph.   
     
     
         5 . The method of  claim 4 , further comprising for each intermediary link between a first relation type and a second relation type in the target-source intermediary graph:
 finding a first set of relations in the source intermediary graph associated with the first relation type;   finding a second set of relations in the target intermediary graph associated with the second relation type; and   determining an intersection between the first set of relations and the second set of relations.   
     
     
         6 . The method of  claim 1 , further comprising:
 traversing the heterogeneous graph to extract all of the inference rules that are inferable from the heterogeneous graph according to the template.   
     
     
         7 . The method of  claim 6 , wherein the template defines a rule pattern as three node types having three relation types between the three node types. 
     
     
         8 . The method of  claim 7 , wherein a computational complexity to extract all of the inference rules from the heterogeneous graph according to the template comprising the rule pattern is of order (n 2 +T 3 ) complexity, where n is the number of nodes in the heterogeneous graph and T is the number of relation types in the heterogeneous graph.