System, method, and recording medium for knowledge graph augmentation through schema extension

A method, system, and recording medium for knowledge graph augmentation using data based on a statistical analysis of attributes in the data, including mapping classes, attributes, and instances of the classes of the data, indexing semantically similar input data elements based on the mapped data using at least one of a label-based analysis, a content-based analysis, and an attribute-based clustering, and ranking the semantically similar input data elements to create a ranked list.

BACKGROUND

The present invention relates generally to knowledge graph augmentation, and more particularly, but not by way of limitation, to a system, a method, and a recording medium for extending a knowledge graph based on a large corpus of structured data.

Conventional techniques may rely only on labels in schema such as column headers, may use a single statistical measure to find relevant attributes, may rely on text surrounding or describing the structured source, and may rely on query logs and work only when a large user base is available.

Other conventional techniques may merely create an “Attribute Correlation Statistics Database” (AcsDb) which contains attribute counts based on the headers of the respective columns. From these counts, the conventional techniques estimate attribute occurrence probabilities. Applications for this database are a schema auto-complete function, synonym generation and a tool enabling easy join graph traversal for end-users. Such conventional techniques evaluate their Schema Auto-Complete system by giving both the system and a number of humans a single (key)attribute and ask them to create a schema, then measure to which extent the system can reproduce the schema created by the humans. The focus of the exemplary conventional techniques is to find names for possible attributes. The conventional techniques do not consider the content/values of these attributes and hence do not evaluate this aspect.

Other conventional techniques propose an integration of data using web tables, defined as an “EXTEND” operation. These techniques require the user to provide an input table and a keyword query. Based on the user provided input, these techniques attempt to determine one or multiple tables that can extend the input table with the topic given by the keyword query. These conventional techniques use a search engine to find the tables and different value-based matching approaches to determine which tables can be combined. However, the “EXTEND” operation is evaluated by issuing a number of queries in the form (e.g., input table, join key, topic of column to be added) and checking the number of correct values that are returned. As a new attribute is specified, there is no need for a ranking by usefulness. It is unclear in these conventional techniques how the column that contains the value is selected.

Other conventional techniques use label-based and value-based schema matching techniques to map web tables to a knowledge base. For these techniques “Schema Complement” operation, the techniques consider all unmapped columns and rank the unmapped columns using the “AcsDb” and the entity coverage of the input table provided by the user. The goal is to rank complete tables by their usefulness for the complement task. However, such conventional techniques evaluate their system by letting users decide how related the tables are in their output are. The focus is on the tables and not the attributes.

That is, the above conventional systems, and other conventional knowledge graph augmentation systems are limited in their application in that they make no claims about the content/values of these attributes and hence do not evaluate this aspect, it is unclear in these conventional techniques how the column that contains the value is selected, and the focus of such techniques is on tables, not attributes.

Thus, there is a technical problem in the conventional systems that the methods of knowledge graph augmentation rely either on additional sources (e.g., search engine query log) or perform only basic label-based analysis such that they do not adequately augment existing knowledge graphs with any efficiency.

SUMMARY

In an exemplary embodiment, the present invention can provide a method for knowledge graph augmentation using data based on a statistical analysis of attributes in the data, including mapping classes, attributes, and instances of the classes of the data, indexing semantically similar input data elements based on the mapped data using at least one of label-based analysis, content-based analysis, and attribute-based clustering, and ranking the semantically similar input data elements to create a ranked list.

Further, in another exemplary embodiment, the present invention can provide a non-transitory computer-readable recording medium recording a knowledge graph augmentation program using data based on a statistical analysis of attributes in the data, the program causing a computer to perform mapping classes, attributes, and instances of the classes of the data, indexing semantically similar input data elements based on the mapped data using at least one of label-based analysis, content-based analysis, and attribute-based clustering, and ranking the semantically similar input data elements to create a ranked list.

Even further, in another exemplary embodiment, the present invention can provide a system for knowledge graph augmentation using data based on a statistical analysis of attributes in the data, including a mapping device configured to map classes, attributes, and instances of the classes of the data, an indexing device configured to index semantically similar input data elements based on the mapped data using at least one of label-based analysis, content-based analysis, and attribute-based clustering, and a ranking device configured to rank the semantically similar input data elements to create a ranked list.

There has thus been outlined, rather broadly, an embodiment of the invention in order that the detailed description thereof herein may be better understood, and in order that the present contribution to the art may be better appreciated. There are, of course, additional exemplary embodiments of the invention that will be described below and which will form the subject matter of the claims appended hereto.

DETAILED DESCRIPTION

With reference now toFIG. 1, the knowledge graph augmentation system100includes a mapping device101, an indexing device102, and a ranking device103. The knowledge graph augmentation system100includes a processor180and a memory190, with the memory190storing instructions to cause the processor180to execute each device of the knowledge graph augmentation system100.

Although as shown inFIGS. 5-7and as described later, the computer system/server12is exemplarily shown in cloud computing node10as a general-purpose computing device which may execute in a layer of the knowledge graph augmentation system100(FIG. 7), it is noted that the present invention can be implemented outside of the cloud environment.

The knowledge graph augmentation system100receives data105(i.e., a corpus of structured data, a large database, comma separated files (CSV), etc.) and a knowledge graph106. The knowledge graph106input into the knowledge graph augmentation system100includes an existing knowledge graph106that the knowledge graph augmentation system100augments (i.e., expands/adds values to) by adding missing values, extending the set of entities, and extending the schema such that the existing knowledge graph can be refined, extended, and/or adapted for new domains and applications. In other words, the knowledge graph augmentation system100builds/expands on an existing knowledge graph106.

The mapping device101includes an instance mapping device111, an attribute mapping device112, and a class mapping device113.

It should be noted that an “attribute” (or “label”) described herein relates to a column heading, and the corresponding content associated with that attribute is a set of values of that attribute or label. For example, as exemplarily shown inFIG. 3, an exemplary attribute or label is “industry” in the second data105B, with the corresponding set of values being telecoms, aerospace and defense, etc.

Further, it should be noted that “data” described herein relates to structured data, tables, comma separated files (CSV), etc. such that the knowledge augmentation system100can identify values within the data.

Based on the input knowledge graph106, the class mapping device113sorts through the data105and identifies each table that includes a class of the knowledge graph106. As exemplarily shown inFIG. 3, the class mapping device113receives the knowledge graph106and identifies that the first data105A, the second data105B, and third data105C include the class of “country” or “company”.

Thus, the class mapping device113identifies that the first data105A, the second data105B, and third data105C are tables that are related to the knowledge graph106.

The attribute mapping device112maps each of the attributes in the tables that the class mapping device113has identified to be associated with a class of the knowledge graph106. Thus, the attribute mapping device112maps each attribute of each table that the class mapping device113has identified. More plainly stated, the attribute mapping device112maps the column heading of each of the columns of the tables (for example, the first data105A, the second data105B, and third data105C) as attributes associated with the class in the knowledge graph106.

The instance level mapping device111maps each instance of a value of the set of values within a class and the corresponding set of values associated with that value. As exemplarily shown inFIG. 3, the instance level mapping device111maps “Citigroup®” of the first data105A as an instance of the class “company” and then associates the corresponding set of values with that instance of the class (i.e., banking, 21.54, 1884.32, 247.42).

Thus, the mapping device101maps each class, attribute, and instance of each class and outputs the mapped data to the indexing device102.

The indexing device102includes a label-based analysis device114, a content-based analysis device115, and an attribute clustering device116. The indexing device102indexes semantically similar input data elements using the label-based analysis device114, the content-based analysis device115, and the attribute clustering device116.

The label-based analysis device114analyzes the headers of a column of the mapped data (i.e., the label/attribute of the column). The label-based analysis device114identifies each of the columns among the mapped data that have an exact match of their labels. The label-based analysis device114can also identify each of the columns among the mapped data that have a string similarity between the labels of the columns. For example, the label-based analysis device114can identify the column of the first data105A having the label “industry” as being related to the column of the third data105C having the matching label “industry”.

The content-based analysis device115analyzes the set of values associates with each column of each of the data105and compares the values based on a column-to-column similarity.

For example, the content-based analysis device115can calculate a cosine similarity of the set of values between columns (i.e., column-to-column calculation) by converting the text to a vector and determining the closeness of each value of the set of values based on the cosine similarity. This calculation can be done according to known techniques of converting the set of values to a vector and calculating the cosine similarity between the vectors. Based on the cosine similarity between values, the content-based analysis device115determines how related the columns are to each other.

Even further, the content-based analysis device115can calculate a containment ratio between columns to determine the column-to-column similarity. The content-based analysis device115determines the amount of values of the set of values that match each other. For example, the content-based analysis device115can analyze the second data105C and the third data105C to find that three values of the third data105C (i.e., “oil & gas operations”, “oil & gas operations”, and “telecommunications services”) overlap with the values of the second data105B such that there is a containment ratio of 3 out of 4 of the third data105C in the second data105B. Therefore, it is likely that the second data105B and the third data105C are related.

Also, the content-based analysis device115can index the data based on a key-value analysis. For example, after the instance mapping device111maps each instance of a value of the set of values within a class and the corresponding set of values associated with that value, if a first value of a column mapped within a first class matches the exact same first value of a second column mapped within a second class, the content-based analysis device will not index the values since they are not associated with the same key. In this manner, the content-based analysis device115performs key-value based matching of values.

In other words, the key-value analysis compares only those values of two columns, which are mapped to the same entity in the knowledge base. This means that two columns are equivalent only if they contain similar values for the same entities.

The attribute clustering device116clusters similar attributes. For example, assume that there are five attributes: “attr1”, “attr2”, “attr3”, “attr4”, “attr5” where “attr1”, “attr2”, and “attr3” have the same label “label1”, “attr4” has label “label2”, and “attr5” has label “label3”. Also assume that there is a Boolean content-based similarity function simulation that indicates similarity between contents of attributes, (e.g., sim(attr1,attr2) means contents of “attr1” and “attr2” are similar).

The label-based analysis device114will make three index items for the three labels: “i1” (label1): “attr1”, “attr2”, “attr3”; “i2” (label2): “attr4”; and “i3” (label3): “attr5”. The label-based analysis device114assumes that “label1”, “label2”, and “label3” are not similar or that the label-based analysis device114is using exact label-based analysis. Or, the label-based analysis device114can index similar labels together, for example if “label2” and “label3” are similar, then “i2” and “i3” will be merged.

The attribute-based clustering device116, performs a clustering of the attributes based on the content-based and/or label-based similarity. For example, if there is a graph where nodes represent attributes and edges represent content-based similarity of attributes, then the attribute-based clustering device116can use an existing graph clustering algorithm to perform this clustering. The most basic kind of graph clustering algorithm is graph partitioning (“partitioning clustering”). Using partitioning clustering in the above example merges “i2” and “i3” because the attribute-based clustering device116views the content-based similarity between attributes as a similarity graph, attributes “attr2”, “attr3”, “attr4”, and “attr5” will all be in the same partition. Therefore, “i1”: “attr1” and “i2”: “attr2”, “attr3”, “attr4”, and “attr5”.

It should be noted that although “partitioning clustering” is exemplarily described as a graph clustering algorithm, the clustering is not limited thereto, and can include “partitioning”, “center”, and “merge-center” clustering.

It should be noted that “attr2” and “attr5” are now indexed together although sim(attr2,attr5) is not present (i.e., their contents are not directly similar).

The label-based analysis device114, the content-based analysis device115, and the attribute clustering device116can perform each of their respective functions individually or in any combination thereof. In a preferable embodiment, each of the label-based analysis device114, the content-based analysis device115, and the attribute clustering device116performs their respective functions in combination. However, each device can independently index the data in that at least one of the devices114,115, and116performs their function.

For example, if data is analyzed that has no headers, the label-based analysis device114may not perform its functions properly. Thus, the combination of devices114,115, and116can improve the output to the ranking device103.

The indexing device102outputs the indexed tables of the data105to the ranking device103.

The ranking device103includes a coherence ranking device117, a consistency ranking device118, a class-based ranking device119, and a page ranking device120.

FIG. 4exemplarily shows an output of each of the device117,118,119, and120(i.e., a ranked list104). For example, the coherence ranking device117outputs the exemplary items in the column “Coherency”, the consistency ranking device118outputs the exemplary items in the column “Consistency”, the class-based ranking device119outputs the exemplary items in the column “Conditional”, and the page ranking device120outputs the exemplary items in the column “Trust+Conditional”. The outputs in each of the columns ofFIG. 4is exemplarily output based on the first data105A, the second data105B, and the third data105C.

The ranking device103ranks the attributes that will be used to augment the knowledge graph input into the knowledge graph augmentation system100. For example, the knowledge graph106input into the system100includes the attributes “company” and “country”. Thus, the ranking device103will rank which attribute columns to augment the knowledge graph with using the four devices117,118,119, and120.

The coherence ranking device117ranks the attributes which co-occur with existing attributes of the knowledge graph106higher than the frequent ones. In other words, attributes that appear more frequently may be less interesting than an attribute that co-occurs with more existing attributes of the knowledge graph106.

Therefore, as exemplary shown inFIG. 4, the coherence ranking device117ranks “sales” as the highest rank because it is determined to be more unique than industry since industry is seen more often and it co-occurs with both attributes in the knowledge graph106.

The consistency ranking device118ranks the attributes of the tables of the data105based on the class information, the frequency of the attribute, and the co-occurrence with existing attributes of the knowledge graph106. In other words, the more often an attribute occurs with an attribute that is already in the knowledge graph106, the better the attribute may be to augment the knowledge graph106.

Thus, as can be seen inFIG. 4as compared with the class-based ranking device119output “ranks”, “sales” is above “rank” and “video uses” since sales co-occurs with the attributes “company” and “country” in the third data105C (i.e., attributes in the knowledge graph106). That is to say, in an exemplary embodiment, it may be more likely that sales is relevant than the attributes of “rank” and “video uses”.

The class-based ranking device119ranks the attributes of the tables of the data105based on the class information and the frequency of the attribute. In other words, the most frequent attributes in the tables of the data105may be the most relevant or interesting to augment the knowledge graph106with.

In other words, based on the mapping output by the indexing device102performed by at least one of the devices of the indexing device102, each of the tables of data105are related to the knowledge graph by either containing a “company” or “country” attribute. The class-based ranking device119ranks each attribute of the tables of data105(i.e., the first data105A, the second data105B, and the third data105C) based on the number of times that the attributes occurs.

For example, industry is in each of the three tables and has a highest rank by the class-based ranking device119, “assets”, “profits”, and “market value” are in two of the three tables and has the second highest ranking (i.e., they are all tied for second highest) by the class-based ranking device119, and “rank”, “video uses”, and “sales” has the lowest ranking (i.e., they are all tied for lowest) by the class-based ranking device119.

The page ranking device120, concurrently with at least one of the coherence ranking device117, the consistency ranking device118, and the class-based ranking device119, ranks the attributes of the tables of the data105based on the source of where the data105was taken from (i.e., Wikipedia may be the highly ranked source of data105, a blog may be a lower ranked source, etc.)

In an exemplary embodiment, the first data105A may be derived from a source (i.e., web-page, crawled data, blog, etc.) that has a highest trust value, the second data105B may be derived from a source that has a trust value lower than the first data105A, and the third data105C may be derived from a source page that has a trust value higher than the second data105C but lower than the first data105A.

Thus, as exemplarily shown inFIG. 4, if the page ranking device120is combined with the ranks output by the class-based ranking device119, “sales” moves above “video uses” since “sales” is in a higher trusted source (i.e., the third data105C) than “video uses” (i.e., the second data105B).

The ranking device103ranks the attributes of the data105using at least one of the coherence ranking device117, the consistency ranking device118, the class-based ranking device119, and the page ranking device120, or any combination thereof.

The ranking device103outputs a ranked list104as exemplarily shown inFIG. 4. Each of the columns of the ranked lists can be weighted and combined so as to output one ranked list. For example, if the coherence ranking device117outputs rankings that are 80% accurate and the class-based ranking device119outputs rankings that are only 5% accurate, the rankings can be combined by taking into account the accuracy of the rankings by weighting each column of the ranked list104and performing averaging to output a single list (i.e., merge each ranked column together into one ranked list).

For example, the weights could be associated with the current number of each item in the ranked list. That is, “industry” appears first in three of the ranked lists and second in the other. Thus, “industry” could have a weighted score of 1.25 (i.e., (1+1+2+1)/4) and “market value” could have a weighted score of 4.25 (i.e., (4+4+5+4)/4). This can be done for each of the attributes output from the ranking device103to calculate a merged ranked list.

Of course, other rankings and/or weightings can be performed based on other criteria (i.e., age/date of the data source in which newer data sources are deemed more reliable, etc.)

FIG. 2shows a high level flow chart for a knowledge graph augmentation method200that receives data105and a knowledge graph106as an input.

Step201maps each class, attribute, and instance of each class of the data105and outputs the mapped data105to the indexing step202.

Step202indexes the map data by analyzing the headers of a column of the mapped data to identifies each of the columns together amongst the mapped data that have an exact match of their labels, identify each of the columns amongst the mapped data that have a string similarity between the labels of the columns, compare the values based on a column-to-column similarity (i.e., calculate a cosine similarity of the set of values between columns, calculate a containment ratio between columns to determine the column-to-column similarity, etc), and/or cluster the set of values of the attributes together based on an overlap between corresponding attributes.

Step203receives the indexed data105from the indexing202and ranks the data105based on coherence ranking, consistency ranking, class-based ranking, and/or page-based ranking to output a ranked list104.

In view of the foregoing and other problems, disadvantages, and drawbacks of the aforementioned conventional techniques, it is desirable to provide a new and improved knowledge graph augmentation system, method, and non-transitory recording medium that, given a large corpus of structured data (e.g., millions of CSV files, or a large DB), an existing knowledge graph can be augmented more efficiently with data that is more relevant through the indexing and ranking of the attributes of data.

Thus, the disclosed knowledge graph augmentation system, method and non-transitory recording medium improves over existing techniques in at least that the disclosed invention takes in an existing knowledge graph along with a corpus of structured data and provides a ranked list of attributes to complement the knowledge graph and relies on the existing knowledge graph and the input corpus and no other source to find attributes that complement the input knowledge through a combination of label, value, and key-value based mappings.

Exemplary Hardware Aspects, Using a Cloud Computing Environment

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

Workloads layer90provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation91; software development and lifecycle management92; virtual classroom education delivery93; data analytics processing94; transaction processing95; and, more particularly relative to the present invention, the knowledge graph augmentation system100described herein.