Discovering Technology Gaps using the IntSight Knowledge Navigator

The User-Level Problem. Consider a customer that performs technology research and produces technology products in several different areas. It works with a large number of research and industrial partners who also produce research and/or products in the same space. The company is trying to create a future growth plan in its current areas of expertise as well as some related areas where it is trying to expand. As part of its competitive landscape analysis, it would like to perform a “technology gap analysis”, which is a discovery process to identify technology areas in which its competitors have made more progress compared to the company itself and its ecosystem of partners. The outcome of the discovery process is to understand the gap areas, the players involved, and the nature of their advancement.

Ontology. The ontology, modeled in OWL-DL [6], is transformed into a property graph that preserves all ontology properties [7]. The subproperty axioms in OWL-DL are maintained in a separate tree in the same property graph. Currently, the model does not have any chain rules. Each transitive ontological relationship like subclassOf and componentOf is a directed acyclic graph. Every node maintains a list of the root-to-node tree-path in Apache Solr to avoid explicit graph traversal in the graph database for transitive closure and reachability queries. For nodes with multiple root-to-node paths, we maintain additional paths from the parent of the nearest join-node (of a DAG) to the current node. Further, a term-to-path index is maintained to find relevant paths for a term.

Data Graph. The data graph is constructed from heterogeneous data sources and distributed across all three stores. The knowledge graph construction process is beyond the scope of this document. Table I shows a few of the data sources, their structure, and their placement in the polystore. The knowledge graph is designed as a materialized polystore view over these component data sets. Unlike a database view that is defined as a single (potentially complex) query against a set of base tables or views, a polystore view is specified as a query script that specifies the relational, graph and text-index components of the view. For example, consider the patent data source which is partitioned into the patent metadata component residing in a table, and a patent description component, which is stored in Solr. The entities derived from patents include the patents themselves, organizations, individuals, the technology concepts pertaining to the patent; the relationships include co-ownership, IP-transfer, significant co-occurrences between technologies in selected sections of the patent, etc. As the view is materialized, the entities (together with their properties) are stored in separate relational tables, the relationships together with their end entities are stored in the graph database, and additional indices (e.g., one for time and technology terms) are stored in separate index structures. Figure 2 shows a pictorial view of this materialized structure.

Mapping Structures. The forward mapping structure is a fast lookup structure that captures the relationship between concepts and their instances in the materialized polystore view. This structure takes the form of a key list and three compressed posting lists that contain the IDs of these instances in the three stores. A reverse mapping structure is also maintained for every store, such that a string occurring in a record of that store is mapped to the corresponding concept node in the ontology. For example, strings “GPU” and ”Graphics Processing Unit” map to the same concept node. Note that this mapping is partial, and an algorithmically detected entity occurring in the data may not have a matching concept in the ontology.

Technology Landscape Analysis. Informally, a technology landscape captures the “players” in a set of specified technology areas and their activities. Hence, we define a technology landscape as the triple $L=(P,T,C)$ with
- Performance Relation $P=(Org,Int,Tech,M_{1},M_{2},\ldots)$ where $M_{i}$ is a key performance indicator like the number of patent applications of organization $Org$ on the specific technology $Tech$ in time interval $Int$
- Technology Correlation Graph $T$ whose nodes represent technologies $t\in dom(Tech)$ and edges represent an ontological relationship or a co-occurrence relationship, and
- Organizational Partnership Graph $C$ whose nodes are organizations $o\in dom(Org)$ and edges indicate if they have a cooperative relationship (e.g., joint patent holders, coauthors) in a technology area $t\in dom(Tech)$.

Algorithm 1 presents the steps for the Technology Landscape Analysis. The analysis starts with a user specifying two lists $Pos$ consisting of terms of interest, and $Neg$ consisting of terms not of interest. Thus, if $Pos=$ [“query processing”, “accelerator”] and $Neg=$ [FPGA], the use is interested in hardware accelerator technologies (excluding FPGAs) related to query processing tasks.

Query Expansion. The first step is to use the ontology for query expansion [8, 9] to collect a larger set of positive terms that cover the desired technology space from the ontology. The nominal algorithm computes the union of the transitive closure (along specific ontological relationships) of all terms in the $Pos$ list and subtracts from it the union of the transitive closure of terms in the $Neg$ list. However, for an ontology over a million nodes, multiple transitive closure operations is very expensive. We use the node-to-path index and the root-to-node labels effectively to perform query expansion efficiently.

Densifying Subgraph Detection. With the expanded set of ontological terms $T$, we identify nodes $N$ in the data graph $D$ that correspond to these concept terms using the mapping structures. Using each node in $N$, we identify subgraphs (regions of interest) around these nodes that satisfy the following conditions (a) the number of nodes in the subgraph exceeds $minNodes$, (b) the average clustering coefficient of the subgraph exceeds $minClust$, and (c) the period over which there is a monotonic increase in density matches or exceeds the value of the $history$ parameter. The densifying regions, collectively called the ROI graph $G$, represent parts of the original data graph that are seeing significant activity in recent times. To facilitate the computation of densifying subgraphs, we compute a temporal index of communities in the graph computed through truss-based clustering computed in an HPC cluster. The index is updated every time the materialized view is updated at fixed time intervals. Further, each node in our knowledge graph always maintains some basic network properties about itself including its indegree, outdegree and clustering coefficient.

Landscape Construction. The technology nodes in the regions of interest are connected to Organization names that have, additional information about them in the entity tables of of the knowledge graph. Using the ROI graph $G$, we extract the companies inside $G$ or within the first neighborhood of $G$ (since each technology term is connected to any organization working on it). For each of these companies, the technologies produced by these companies that are included in $G$ and a set of KPI metrics (e.g., number of patents/publications, $\ldots$) associated with these companies. Secondly, we extract the subgraph induced by the technology nodes from $G$ and merge it with subgraphs from the ontology containing these nodes to create the Technology Correlation graph $T$. Similarly, we extract the subgraph induced by the companies in $G$ and its first neighbors to create the Organization Correlation Graph $C$. The technology landscape thus created is returned to the user which the densifying graph $G$ is materialized for later reuse.

Gap Discovery. The gap discovery method presented in Algorithm 2, accepts the landscape and the materialized ROI graph from Algorithm 1, a reference organization $me$ against which the gap will be computed, and a set of predicates $cond[]$ explained below. The algorithm starts by computing the ego network of the $me$ organization to identify all partner institutions. All other organizations are considered as competitors, labeled as $comp$. Independently, the ROI graph $G$ is mined for quasi-cliques $\alpha$ to identify technology combinations that have dominant activity in which the members of $comp$ participate. These participating organizations, labeled as $\alpha_{org}$, are filtered based on three sets of conditions: 1) The organizations must satisfy a set of organization specific properties (e.g., amount of investment), 2) The technology areas they are working on must satisfy certain properties ( major activities in the area must not be less than a year old) and 3) the KPI distance between $me$ and the organization should be beyond a threshold $\theta$. The KPI, are computed from the $M_{i}$ properties of the organization in the Performance Relation $P$ of the technology landscape. The result of the algorithm is the organization’s information from $P$, and quasi-clique in $\alpha$ that the organization is associated with.