This paper is an interim report about an industrial application that uses Datalog combined with empirical methods to compute competitor information from a knowledge graph. The Owler knowledge graph is one of the world's largest companies information systems (CIS). It contains data about 16+ million companies crowd-sourced from over 1 million experts. In particular, for most companies, it contains a set of competitors. Such competitor information is very useful for many B2B applications such as lead generation. However, competitor relations in crowd-sourced CIS are naturally incomplete. This paper presents CompeGen, a method that applies Vadalog (a particular variant of Datalog) rules to infer new competitor pairs from existing ones in the Owler CIS. Since using the Vadalog inference program alone is insuficient, CompeGen combines its inference process with a “learning” process to acquire some required logical facts and further validates the inference results via an empirical validation process. CompeGen was tested using the companies belonging to the “Internet Software” sector in Owler. It has discovered 23,180 new competitors of which over 80% were correct. We are improving the system and will report further results in the full paper.
In today’s global competitive environment, competitor data constitutes information useful to many business applications, such as Competitive Intelligence, Lead Generation, Recommender Systems, and so on. For example, for lead generation, the competitors of a customer A of some company C may be good sales leads for C, as they are likely to require the same products or services as A. Competition-data sellers usually maintain a manually curated database or knowledge graph containing competitor pairs as part of a companies information system (CIS) that also maintains other useful information about companies such as the industry sectors in which they operate. The Owler1 knowledge graph (a.k.a., the Owler competitive graph, see the graph on the left of Fig. 1 as an example) is one of the world’s largest CIS. It contains data about 16+ million companies crowd-sourced from over 1 million experts. However, competitor relations in such crowd-sourced CIS are naturally rather incomplete. The main goal that we target is to infer new competitor pairs from existing competitor pairs in the Owler CIS. Datalog programs that perform inference based on knowledge about companies are naturally suitable for inferring new competitor pairs from existing ones in a CIS. However, using a Datalog program alone is not suficient because the required knowledge may be absent, and the inference results are sometimes inaccurate. In this paper, we present CompeGen designed based on our key idea: Key Idea: Combine a knowledge-based inference process with an upstream knowledgelearning process and a downstream validation process.
CompeGen “learns” new knowledge from the existing knowledge in Owler, and then performs
an inference process based on both the learned and the existing knowledge about companies.
The inference results are further validated by an empirical validation process based on
cooccurrences of companies in documents of a document repository. The combination of ()
knowledge about companies [
The inference process of CompeGen uses several diferent types of knowledge (represented as
logical facts) about companies: () Competitor(A, B, ) which represents an existing competitor
pair in Owler that a company A has a competitor of B with a proximity score ranging from 0
(extremely unlikely to compete) to 100000 (sure competitors); () CompSector(C1,S1) which
represents the fact that a company identified by the company ID C1 belongs to the industry
sector S1; () CompatSec(S1,S2,) which represents the fact that two sectors S1 and S2 are
compatible sectors with a sector compatibility score of . Two sectors, S and S’, are compatible if
there are more than a certain amount of competitor pairs in each of which one company belongs
to S and the other belongs to S’ (see Section 3). For example, in Figure 1, the sectors S1 and
S2 are compatible. Knowledge of types () and () comes directly from the Owler CIS while
the knowledge about sector compatibilities is learned from existing knowledge in the Owler
CIS, which is explained in the next section. Based on such knowledge, CompeGen computes
candidate competitor pairs via Vadalog, which is a particular variant of Datalog well-suited for
knowledge graphs [
Cand(C1,C3,PScore):-Cand(C1,C2,PS12),Competitor(C2,C3,PS23),
CompSector(C1,SEC1),CompSector(C3,SEC3),C1 != C3, CompatSec(SEC1,SEC3,SeCoScore),Penalty(A), Cutoff(B),
PScore=max((PS12+PS23-100000-A)*SeCoScore), PScore>B.
Each candidate competitor pair (C1,C3) computed by the above program is represented by the fact Cand(C1,C3,PScore) where PScore is a plausibility score expressing a degree of plausibility that company C3 is a competitor of company C1. The above Vadalog program computes a new fact Cand(C1,C3,PScore), either if such a fact is already in the Competitor relation, or if there is an already computed fact Cand(C1,C2,PS12) and a fact Competitor(C2,C3,PS23), where the certain conditions are satisfied. These conditions require that C1 be diferent from C3, and that the computed plausibility score PScore be larger than some cutof constant B (represented as Cutof(B)), where PScore is the maximum value of (PS12 + PS23 − 100000− ) × (SeCoScore is the compatibility score of the sectors of C1 and of C3) over all matching choices of C2, SEC1, and SEC3. A penalty constant (represented as Penalty(A)), with 0 < < 100000, lowers the proximity scores of new candidate pairs generated by transitivity.
The CompeGen approach can be intuitively explained via the main steps described below. First, at Step I , a knowledge-learning process is performed to learn the knowledge about sector compatibilities, i.e., sector compatibility scores, from the data in the Owler CIS. Let be a sector and 1, . . . , be all sectors such that there is at least one competitor pair from and , i.e., there is one edge from to in the competitive graph, for 1 ≤ ≤ . For every such , is defined to be the number of edges from to . Let = max1≤ ≤ (). Let = 0.2 be some empirically decided cutof-constant. If < this then means that and are not compatible, and thus the compatibility weight (, ) = 0. Otherwise, (, ) is calculated via an empirically determined function (, ) = 1 − (1 − ), where = 3. A smaller , such as 1, may cause (, ) to be lower than expected, especially when is very large while is also large but much smaller than . For example, when = 20000 and = 10000, (, ) = 0.5 if = 1, while (, ) = 0.875 if = 3, and the latter is more reasonable. The compatibility score * (, ) is the maximum of the compatibility weights (, ) and (, ).
Next, at Step II , candidate competitor pairs, e.g., (A,C) in Fig. 1, are generated via the Vadalog program described in Section 2.
The next task (Step III ) is to validate each generated candidate competitor pair, e.g., (A,C), against a document repository. The Web is used as the document repository in CompeGen. A Competition Likelihood Score CLS(A,C) of A and C, ranges from 0 (not competitors) to 1 (competitors), is determined based on the co-occurrences of A and C in diferent Web pages. CLS(A,C) is calculated based on a comparison of a number of search results for two groups of queries to the document repository (Step III’ ): (i) a first group of queries, for co-occurrences of names of A and of C together with names of some competitors A* of A (if any), such as D, or some competitors C* of C (if any), such as E. (ii) a second group of queries, corresponding to the ifrst queries, where either A or C is replaced by random companies R(A) or R(C) from the CIS not known to be in a competitor relationship with A or C, such as H. Examples of web pages that match these two groups of queries are in dashed boxes labeled Q1 and Q2 , respectively. From the average number of search results of queries in query groups (i) and (ii), denoted by 1 and 2, respectively, a Query-result Diference Ratio (QDR) is calculated by 1/2 (Step III” ). Based on the QDR, the likelihood score CLS(A,C) is calculated (Step III”’ ) according to a predefined QDR-to-CLS lookup table, such as T1 , whereby a higher CLS is achieved if the QDR is larger. The final part (Step IV ) computes for each candidate pair (A,C) a final proximity score via: fs(, ) = (,)+(,)× 105 . If (i) fs(, ) is larger than a given constant (e.g., 2 90000), and (ii) (A,C) is not already stored in the Owler CIS with a score ≥ fs(, ) then (A,C) is inserted into the CIS with fs(, ).
CompeGen was tested using the companies belonging to the “Internet Software” sector in Owler. CompeGen has discovered 23,180 new competitor pairs. We randomly sampled 200 of these new competitor pairs and asked internal experts to validate these 200 pairs’ correctness. It turned out that 162 pairs were correct, thus the precision of CompeGen is around 0.81. Since the total number of missing competitor pairs in Owler was unknown, it was hard to evaluate the recall of CompeGen. However, discovering 23,180 new competitor pairs with a precision of 0.81 for a single sector has shown the potential to improve the Owler CIS using CompeGen. That has led to Meltwater’s adoption of CompeGen in the completion task of Owler. We are making several improvements to CompeGen, of which the results will be reported in the full paper.