2000万entities, 10亿attribute value pairs,2000万relations。
1小时抽取entities,3小时抽取属性对,3小时抽取relation from Enterprise
Knowledge Graph (EKG)
一个月更新一次
This is an application paper table about what challenge they made when they develop Enterprise Knowledge Graph, called EKG, which incorporates information about 40,000,000 enterprises in China.
The product is sold as a service and the target is securities companies. Because the securities companies provide investment bank services and investment consulting services, they have to know the information about the small and medium-sized enterprises. So the product can help securities companies to know and to approach target companies better and quicker.
There are two kinds of challenges in this project, the technology challenges, and business challenges.
Business challenges
There are two challenges on the business side.
Data Privacy: how to provide deep and useful analysis services without violating the privacies of a company and its employees.
Killer Services on the Graph: EKG is complex and huge, how to make the graph easy to use is a challenge.
The solution for two challenges.
Data Privacy:
transform the original data into the rank form or the ratio form instead of using real accurate values (rank form or the ratio form?)
obscure critical nodes (e.g., person-related information) which should not be shown when visualizing the EKG as a graph
Killer Services on the Graph:
deliver services that directly meet the business requirements of users. For example, the service finding an enterprise’s real controllers tells the investors from investment banks who are the real owner of a company, and the service enterprise path discovery provides hints on how the investors could reach the enterprises they want to invest in.
Technology challenges
Technology challenges arise from the diversity and the scale of the data sources.
Constructing problems such as transforming the databases to RDF (D2R), representing and querying difficulties when meta properties and n-ary relations are involved
Performance issues since the KG contain more than one billion triples
Before introducing challenges in detail, let's see the whole workflow to build the EKG first.
At the first stage of our project, we mainly utilize relational databases (RDBs) from
CSAIC.
Secondly, we supplement the EKG with bidding information from the Chinese Government Procurement Network (CGPN) and stock information from Eastern Wealth Network (EWN).
Then the EKG is fused with the patent information extracted from the Patent Search and Analysis Network of State Intellectual Property Office (PASN-SIPO) in another project.
At last, the competitor relations and acquisition events are added to the EKG. This information is extracted from encyclopedia sites, namely Wikipedia, Baidu Baike and Hudong Baike.
The following challenges are encountered during the above process:
Data Model (Complex data types): meta property (property of relations, or property graph) and event (n-ary relation). But no existing mature solutions on representing and querying meta properties and events in an efficient way.
D2R Mapping: using D2R tools (e.g., D2RQ9) to map RDBs from CSAIC into RDF has following challenges: a) Mapping of meta property. b) Data in the same column of RDBs map to
different classes in RDF. c) Data in the same RDB tables may map to different classes having subClass relations.
Information Extraction: Extract useful relation from various types, like "competitive", "acquisition" and so on. Entity extraction becomes difficult when there are abbreviations of company names in encyclopedic sites. The same company may be written in various variations or abbreviations. For
example, abbreviations like “中铝(Chalco)”, “中铝公司(Chinalco)”, and “中国铝业(Chinalco)” can all represent the company “中国铝业股份有限公司(Aluminum Corporation of China Limited)”.
Query Performance: We encounter performance bottlenecks since the number of triples of our EGK has reached billions. Furthermore, there are more complex query patterns when the EKG usage scenarios increase: a) When users query the KG on an IPC code, we should find all the
subClasses of the IPC code recursively, then find the patents belong to the subClasses. b) Query all properties of an instance. The problem arises since different properties of the same instance may store as different triples in graph store. c) The queries on meta properties and n-ary relations.
The authors carefully select the most suitable methods and adapt them to the above problems.
First, we split the original tables into atomic tables and complex tables, then we use D2RQ tools to handle mappings on atomic tables. At last, we develop programs to process ad hoc mappings on complex tables.
We use multi-strategy learning methods in [16]( Bootstrapping yahoo! finance by wikipedia
for competitor mining) to extract competitor relations and acquisition events from various data sources of encyclopedic sites.
We adopt a graph-based entity linking algorithms in [2] (Graph ranking for collective named entity disambiguation) to accomplish the task of entity linking.
We design our own storage structure to fully optimize the performance of miscellaneous queries in EKG. We use a hybrid storage solution composed of multiple kinds of databases. For large-scale data, we use NoSQL database namely Mongodb as the underlying storage. For high-frequency query data, we use a memory database to store data.
Data Model:除了基本的数据类型(int,float,string),需要保存更复杂的数据类型,比如sequential data(电话号码), range-type data (effective operating time of an enterprise),map-type data(比如每年的营收,应该用map结构保存,键是年份,而值是营收)。EKG中的relation并不只是binary relation,还存在“property of relation”和“n-ary relations”。前者叫meta property或peoperty graph,后者有时叫做event。meta property的例子,如果一个人被公司雇佣,那么就有一个“entry time”的property,与“employ”关系相关。event的例子则是 投资者,公司,投资时间,投资金额,投资回报(investment ratios)等等。因为RDF中的关系是binary的,如何表示这些event和meta property有很多讨论,比如W3C的“Defining N-ary Relation on the Semantic Web”。但是本文作者并没有发现一个成熟的方案,可以有效地表示meta properties和event。
D2R Mapping:首先使用D2R工具(D2RQ),将CSAIC里的RDB转换为RDF。但是遇到了下面的问题:1 mapping of meta property。(没看懂这里说了个什么问题)2 RDB中同一列的数据被映射到了RDF中的不同classes(叫做conditional class mapping)。比如一个专利申请者可能是自然法人,也可能是一个公司。3 在同一个RDB table里的数据,可能会映射到有subclass的relation(叫做conditional taxonomy mapping)。比如 listed company是company的一个子类,一个公司可能会被映射到company,也可能被映射到listed company。
Information Extraction:竞争者,收购信息,其他一些从百科网站收集的关系信息。从infobox这样的半结构来源里提取信息还好,但是有一些信息直接包含在text里。如何从不同数据中提取信息的任务很困难。另外,还有一个问题是百科网上有很多缩写的公司,一个公司可能有多个不同的写法:“中铝(Chalco)”, “中铝公司(Chinalco)”, and “中国铝业(Chinalco)” can all represent the company “中国铝业股份有限公司(Aluminum Corporation of China Limited)”. 而且很多不同的公司名可能有一个相同的缩写,比如 “大连万达集团股份有限公司(Dalian Wanda Group Co., Ltd)” and “万达信息股份有限公司(Wonders Information Co., Ltd)” can all be abbreviated as “万达(Wanda)”.
D2R mapping。首先我们把原始的table氛围atomic table和complex table,然后使用D2RQ工具来对atomic table进行映射。最后,我们自己写程序来处理 ad hoc mapping on complex tables.
使用(Bootstrapping Yahoo! Finance by Wikipedia for Competitor Mining,这篇论文没公开)里的方法来提取竞争者信息,来源是各种百科网站。首先用HTML处理器来提取一些半结构化的信息,然后使用Hearst patterns(用一些一些定义好的规则来抽取三元组的方法,文章1,文章2)来提取文本中的信息。
使用基于图的entity linking 算法( Graph ranking for collective named entity disambiguation)来做entity linking。首先计算mentions和KG中entities的相似度,找到候选的entities,然后构建一个undirected graph来实现disambiguation。
现在的graph databased提供的功能,并不能很好地整合meta properties和events,我们设计了自己的storage sturcture来实现EKG的混合查询。比如混合的存储方案包含不同种类的数据库,对于大规模的数据,我们使用nosql (mongodb),对于高性能的查询,使用memory database,可以大幅度提升查询速度。我们还将main data table缩减为多个single data table。我们把meta properties的relation保存在同一个table里,这样可以同时对ordinary peoperty和meta property进行查询。我们还构建了n-ary relation的index和meta properties的index。
3 Approach Overview
3.1 Problem Definition
KG里的G包含schema graph G_s, 和 data graph G_d,还有二者之间的 R。
data graph G_d,其中N-d 是 a set of nodes,表示instances和literals (字面量),P_d 表示 a set of nodes,表示properties;E_d 是 a set of edges,表示node之间的relations。每个edge (Subject, Predicate, Object) 代表一个fact。N_d包含两个不想交的部分,即instance和literals。如果triple里的object是一个isntance,那么我们叫这个property为relation或object property,不然的话,就叫做datatype property。
Data Sources and Related Tasks to Construct the EKG
构建EKG主要有5个信息来源:
KG主要是基于CSAIC的结构化企业信息。其中包含了4千万公司,6千万人,8百万的诉讼,1百万的信用信息。关于公司的信息包含 company executives, registration number, address and
so on。 关于人物的信息,包含 ID card number, position and so on。 关于诉讼的信息包含 complainant(申诉人), case number, trial date and so on。关于信用的信息包括performance status, court and so on。 我们把RDB转换为RDF,来构建KG ( Ontology instance linking: Towards interlinked knowledge graphs)。
PSAN-SIPO, 最大也是最成功的专利网站。抽取了5百万的专利薪酬,包含专利申请者,专利编号,专利名。用这些信息来构建了一个专利KG。Basic KG 和 专利KG 之间用公司和任务来连接,然后构成EKG。
从CGPN抽取出了3百万的企业竞标信息,包含investor, investee, invest time and so on。上市公司的股票信息抽取自EWN。然后EKG融合了上面这些收取的信息。
竞争关系和收购信息抽取自百科网站,然后通过公司名和人物名添加到EKG中。
这里举个例子:
3.2 Data-driven KG constructing process
如图3所示,一共有5个步骤,Schema Design, D2R Transformation, Information Extraction, Data Fusion with Instance Matching, Storage Design and Query Optimization。
当EKG构建之后,我们就可以提供“使用场景”给安全公司了。整个过程是数据导向,逐渐迭代的。D2R Transformation 和 the Information Extraction,这两个步骤是否初始化,是取决于 type of data source。新的迭代是否开始,取决于input of new data sources。如果一次迭代中有多个数据来源,我们首先选择最结构话的数据。下面的例子里有2次迭代,第一次迭代是两个分开的项目,一个是从CSAIC中转 一些换EKG,另一个是从PASN-SIPO中提取 patent KG。这两个KG服务于不同的用户。第二次iteration,我们使用data fusion algorithms来将两个KG通过companies和person进行连接。其他还有一些数据来源可以添加到KG里,我们使用HTML wrapper来提取半结构化的信息。然后使用Hearst patterns和DS来从free text中提取更多的信息。最后,我们使用Instance Matching algorightms来检查instance pairs是否对齐了。
第一次迭代,EKG包含4个基本概念,Company, Person, Credit, Litigation。主要的关系包含 “subsidiary”, “shareholder”, and “executive”。patent KG只包含 “Patent”,主要关系是 “applicant”。 第二次迭代,添加 “ListedCompany”, “Stock”, “Bidding” and “Investment” 到 EKG里。除了新添加的概念(“stock code” and “issue number”),在EKG之间还有新的relations,比如“acquisition” and“competitive” as well as “subClassof” relation between “Company” and “ListedCompany”,如果Figure 1 所示。
Post Processing:a) Meta property mapping。(详情先不管了) b) Conditional taxonomy mapping。(详情先不管了) c) Conditional class mapping。
4.3 Information Extraction
大部分抽取研究只关注抽取某个特定的目标,但是我们要抽取更多的目标,different types of entities(e.g., companies), binary relations(e.g., competitors), and attribute value pairs(e.g., CEO of a company). 还涉及事件抽取 event(n-ary relation) extraction (e.g., company acquiring) and 同义词抽取 synonym extraction (e.g., abbreviation of companies). The extraction strategy varies according to the data sources and extraction targets. 这里的抽取方式使用了一个叫做multi-stragety learning的方法(Bootstrapping Yahoo! Finance by Wikipedia for Competitor Mining):
使用HTML wrapper,从PSAN-SIPO, EWN and CGPN抽取 Entities and attribute value pairs of patent, stock and bidding information
使用HTML wrapper,从百科网站的infoboxes来抽取公司的 Attribute value pairs (e.g., the chairman of an enterprise ) of enterprises。我们通过页面的更新时间来判断信息是否正确。这个步骤可以填充database中的null value
a)candidate detection,首先找到KB中的提高的mention的候补entity。 首先我们对公司名进行标准化,比如从不同source得到的公司名,已经在KB中的公司名。具体的做法是 删除suffix (e.g., “股份有限公司(Corp.)”, “ 有限公司(Co.,Ltd)”, “集团(Group)”, and so on)。这么做是为了计算core word of mention 和 core word of entity in KB的相似度。然后我们context similarity来及算mention和 KB中被标准化过的entitties,具体做法是计算包含mention的senttence和KB中的textual desciptiong(wiki的第一段)
b) disambiguation, 选择最可能的cadidate进行link。这里使用(Graph ranking for collective named entity disambiguation)里提到的算法
Summary:
详细介绍了一个企业KG的构筑工程。涉及到了工程和商业两个方面的困难。结果很像企查查这类服务。
Resource:
Paper information:
Notes:
This is an application paper table about what challenge they made when they develop Enterprise Knowledge Graph, called EKG, which incorporates information about 40,000,000 enterprises in China.
The product is sold as a service and the target is securities companies. Because the securities companies provide investment bank services and investment consulting services, they have to know the information about the small and medium-sized enterprises. So the product can help securities companies to know and to approach target companies better and quicker.
There are two kinds of challenges in this project, the technology challenges, and business challenges.
Business challenges
There are two challenges on the business side.
The solution for two challenges.
Data Privacy:
Killer Services on the Graph:
Technology challenges
Technology challenges arise from the diversity and the scale of the data sources.
Before introducing challenges in detail, let's see the whole workflow to build the EKG first.
The following challenges are encountered during the above process:
The authors carefully select the most suitable methods and adapt them to the above problems.
中文总结:
1 Introduction
产品叫魔镜,客户是安全公司,这些公司给银行提供投资咨询服务,比如新三板。因此安全公司的客户是中小企业。
2 Challenges
商业挑战:
技术挑战:主要来自diversity和data source scale
Data Model:除了基本的数据类型(int,float,string),需要保存更复杂的数据类型,比如sequential data(电话号码), range-type data (effective operating time of an enterprise),map-type data(比如每年的营收,应该用map结构保存,键是年份,而值是营收)。EKG中的relation并不只是binary relation,还存在“property of relation”和“n-ary relations”。前者叫meta property或peoperty graph,后者有时叫做event。meta property的例子,如果一个人被公司雇佣,那么就有一个“entry time”的property,与“employ”关系相关。event的例子则是 投资者,公司,投资时间,投资金额,投资回报(investment ratios)等等。因为RDF中的关系是binary的,如何表示这些event和meta property有很多讨论,比如W3C的“Defining N-ary Relation on the Semantic Web”。但是本文作者并没有发现一个成熟的方案,可以有效地表示meta properties和event。
D2R Mapping:首先使用D2R工具(D2RQ),将CSAIC里的RDB转换为RDF。但是遇到了下面的问题:1 mapping of meta property。(没看懂这里说了个什么问题)2 RDB中同一列的数据被映射到了RDF中的不同classes(叫做conditional class mapping)。比如一个专利申请者可能是自然法人,也可能是一个公司。3 在同一个RDB table里的数据,可能会映射到有subclass的relation(叫做conditional taxonomy mapping)。比如 listed company是company的一个子类,一个公司可能会被映射到company,也可能被映射到listed company。
Information Extraction:竞争者,收购信息,其他一些从百科网站收集的关系信息。从infobox这样的半结构来源里提取信息还好,但是有一些信息直接包含在text里。如何从不同数据中提取信息的任务很困难。另外,还有一个问题是百科网上有很多缩写的公司,一个公司可能有多个不同的写法:“中铝(Chalco)”, “中铝公司(Chinalco)”, and “中国铝业(Chinalco)” can all represent the company “中国铝业股份有限公司(Aluminum Corporation of China Limited)”. 而且很多不同的公司名可能有一个相同的缩写,比如 “大连万达集团股份有限公司(Dalian Wanda Group Co., Ltd)” and “万达信息股份有限公司(Wonders Information Co., Ltd)” can all be abbreviated as “万达(Wanda)”.
Query Performance:EGK的triple有十亿以上,出现了性能瓶颈。另外,有很多复杂的查询场景:1 找到一个superclass的所有实例。比如,每个专利在专利KG里有一个 IPC code,而IPC是一个多层级的专利分类系统。当用户在KG中查找IPC code的时候,我们应该以递归的方式找到IPC code的所有subclasses,然后找到对应的subclass。 2 查找一个实例的所有properties。这里的问题是同一个实例,它的不同属性可能保存在不同的graph stor的不同triple里。如果properties特别多的话,可能会有很多I/O操作。比如,我们的EKG中每个公司有超过100个属性,如果每个属性保存在不同的property table,那么查询时的read operation就会超过100次。 3 对meta propertie和n-ary relation的查询。有一些查询需要整合一些操作,比如用filtering和sorting来处理meta properties和ordinary properties。比如,找到那些投资回报率超过10%,并且投资金额大于1千万的投资事件。如果用triple store来分开保存properties和meta properties的话,之后执行join operation的时候,需要加载所有triples到内存里。
为了解决上面的问题,下面精心选取了一些较为合适的方法和算法:
3 Approach Overview
3.1 Problem Definition
KG里的G包含schema graph G_s, 和 data graph G_d,还有二者之间的 R。
其中 schema graph G_s 包含 N_s, P_s, E_s。 N_s是nodes,表示不同的classed (concepts); P_s 是nodes,表示properties,P_s 包含
rdf:subClassOf, rdfs:equivalentClass
,还有一些用户定义的aplicant
; E_s 则是一些edges,表示N和P之间的relation。举例来说的话,看上图中的Patent这个概念,它的属性是applicant(申请者),而这个属性范围则是 company 或 person,因为专利的申请人可以是个人或公司。有两种特殊情况:1 Ps是一个relation而不是class,此时叫Ps为 meta property。比如一个人受雇于一个公司,那么meta property就是entry time;2 如果Ps连接到不止一个subject或object,我们称之为n-ary realtion。data graph G_d,其中N-d 是 a set of nodes,表示instances和literals (字面量),P_d 表示 a set of nodes,表示properties;E_d 是 a set of edges,表示node之间的relations。每个edge (Subject, Predicate, Object) 代表一个fact。N_d包含两个不想交的部分,即instance和literals。如果triple里的object是一个isntance,那么我们叫这个property为relation或object property,不然的话,就叫做datatype property。
G_s 和 G_d 之间的R,将data graph里的instances 与 schema graph里的classes进行连接,使用的是
rdf:type
property。Data Sources and Related Tasks to Construct the EKG
构建EKG主要有5个信息来源:
KG主要是基于CSAIC的结构化企业信息。其中包含了4千万公司,6千万人,8百万的诉讼,1百万的信用信息。关于公司的信息包含 company executives, registration number, address and so on。 关于人物的信息,包含 ID card number, position and so on。 关于诉讼的信息包含 complainant(申诉人), case number, trial date and so on。关于信用的信息包括performance status, court and so on。 我们把RDB转换为RDF,来构建KG ( Ontology instance linking: Towards interlinked knowledge graphs)。
PSAN-SIPO, 最大也是最成功的专利网站。抽取了5百万的专利薪酬,包含专利申请者,专利编号,专利名。用这些信息来构建了一个专利KG。Basic KG 和 专利KG 之间用公司和任务来连接,然后构成EKG。
从CGPN抽取出了3百万的企业竞标信息,包含investor, investee, invest time and so on。上市公司的股票信息抽取自EWN。然后EKG融合了上面这些收取的信息。
竞争关系和收购信息抽取自百科网站,然后通过公司名和人物名添加到EKG中。
这里举个例子:
3.2 Data-driven KG constructing process
如图3所示,一共有5个步骤,Schema Design, D2R Transformation, Information Extraction, Data Fusion with Instance Matching, Storage Design and Query Optimization。
当EKG构建之后,我们就可以提供“使用场景”给安全公司了。整个过程是数据导向,逐渐迭代的。D2R Transformation 和 the Information Extraction,这两个步骤是否初始化,是取决于 type of data source。新的迭代是否开始,取决于input of new data sources。如果一次迭代中有多个数据来源,我们首先选择最结构话的数据。下面的例子里有2次迭代,第一次迭代是两个分开的项目,一个是从CSAIC中转 一些换EKG,另一个是从PASN-SIPO中提取 patent KG。这两个KG服务于不同的用户。第二次iteration,我们使用data fusion algorithms来将两个KG通过companies和person进行连接。其他还有一些数据来源可以添加到KG里,我们使用HTML wrapper来提取半结构化的信息。然后使用Hearst patterns和DS来从free text中提取更多的信息。最后,我们使用Instance Matching algorightms来检查instance pairs是否对齐了。
4 Building Knowledge Graphs
4.1 Schema Design
我们使用一个top-down的方法来构建EKG, 来保证数据质量和更严格的shema。当有新的数据来源添加的时候,我们人工地设计和扩展EKG的shema。之所以不用一些自动构建shema的方法,是因为这些方法比较适合complex domain,而我们固定了是企业KG,所以人工即可。
第一次迭代,EKG包含4个基本概念,Company, Person, Credit, Litigation。主要的关系包含 “subsidiary”, “shareholder”, and “executive”。patent KG只包含 “Patent”,主要关系是 “applicant”。 第二次迭代,添加 “ListedCompany”, “Stock”, “Bidding” and “Investment” 到 EKG里。除了新添加的概念(“stock code” and “issue number”),在EKG之间还有新的relations,比如“acquisition” and“competitive” as well as “subClassof” relation between “Company” and “ListedCompany”,如果Figure 1 所示。
4.2 D2R Transformation
将RDB转换为RDF,需要3步,table splitting, basic D2R transformation by D2RQ and post-processing. 因为从CSAIC得到的原始data table是多个省份整合而成的数据库,不符合数据库的设计原则(BCNF), 一些table可能包含多个entities和relation。甚至可能包含n-ary relation或者同样的table column可能包含不同的entity types。为了让table更容易理解和处理,我们将orginal table分割为更小的table,叫做atomic entity table, atomic relation tables, complex entity tables (那些需要conditional class mapping的table,在sec2提到过). 一个atomic entity table 对应一个class,一个atomic relation table对应一个relation instance,其domain涉及两个classes。我们使用D2RQ将atomic entity table和atomic relation table转换为RDF。另外还写了一特殊的程序来解决complex relation table,这些table可能需要meta property mapping, conditional taxonomy mapping等等(在sec2提到过)。
4.3 Information Extraction
大部分抽取研究只关注抽取某个特定的目标,但是我们要抽取更多的目标,different types of entities(e.g., companies), binary relations(e.g., competitors), and attribute value pairs(e.g., CEO of a company). 还涉及事件抽取 event(n-ary relation) extraction (e.g., company acquiring) and 同义词抽取 synonym extraction (e.g., abbreviation of companies). The extraction strategy varies according to the data sources and extraction targets. 这里的抽取方式使用了一个叫做multi-stragety learning的方法(Bootstrapping Yahoo! Finance by Wikipedia for Competitor Mining):
在这个过程中,一个问题是在百科网站上,很很多公司名的缩写。我们需要使用entity linki8ng 算法来将一个company mention和EKG里的公司进行关联。我们采用了一个基于图的方法来实现这个entity linking,分为两步:
4.4 Data Fusion with Instance Matching
不同来源的数据应该融合到EKG里。比如 如何一个patent的applicant属性是一个公司,那么就应该把instance连接到EKG里的company。这个instance matching of companies的问题很简单。因为在中国,根据官方的要求,每个公司的全名必须是unique的。在patent和bidding网站上,公司也必须是全名。因此将patent KG和 basic KG进行连接是非常简单的。但是这个问题对于person instance matching就比较困难了。尽管每个人有独一无二的身份证ID,但是这个ID在patent数据源里是不存在的。所以我们用了一个简单的启发式方法,如果patent inventor的名字和申请者,分别与basic KG中的个人和公司名字一样,,那么我们就说这个patent invector与basic KG中的人物名相匹配。
4.5 Storage Design and Query Optimization
在NoSQL数据库的基础上,我们设计了产IDEtriple store。我们在MongoDB上实现了很多不同的数据种类,包括List type, Range type, Map type,并实现了每种type对应的查询界面。比如对于Map type,交互界面上可以查询所有的value,或某个value的key,或者最大值,最小值。
提升查询效果的方法:
5 Deployment and Usage Scenarios
整个platform构建在公网上,花1小时抽取entity,话3h抽取attribute value pairs,4h抽取relation。每个月重新构建一次来添加新的企业信息。下面介绍了几个使用场景:
Next Reading: