PaperlayerView exact revision on arXiv

Source-linked AI summary

Thinking, Fast and Slow: Combining Vector Spaces and Knowledge Graphs

Sudip Mittal, Anupam Joshi, Tim Finin

arXiv:1708.03310v2cs.AI

TL;DR

Vector spaces and knowledge graphs each have representational limits: embeddings capture similarity but are constrained on complex relations, while graphs support explicit assertions and reasoning. The paper combines them in VKG and decomposes queries across their respective components; VKG search achieves a higher MAP than the vector model alone.

  • Problem

    Vector embeddings are useful for similarity but constrained on complex dependency relations and logic-based operations, while knowledge graphs and vector methods each involve information loss.

    Source: §I · p. 1

  • Method

    VKG links entity embeddings to knowledge-graph nodes and decomposes queries into search, list, and infer subqueries for execution on the appropriate component.

    Source: §V · p. 9

  • Results

    MAP was 0.8 for VKG search on vector space, compared with 0.69 for the vector model alone.

    Source: 1) Evaluating the search query · p. 9

  • Takeaways & Limitations

    The authors conclude VKG can efficiently answer queries that vector embeddings or knowledge graphs alone do not handle.

    Source: §V · p. 9

Abstract

from arXiv · show

Knowledge graphs and vector space models are robust knowledge representation techniques with individual strengths and weaknesses. Vector space models excel at determining similarity between concepts, but are severely constrained when evaluating complex dependency relations and other logic-based operations that are a strength of knowledge graphs. We describe the VKG structure that helps unify knowledge graphs and vector representation of entities, and enables powerful inference methods and search capabilities that combine their complementary strengths. We analogize this to thinking `fast' in vector space along with thinking 'slow' and `deeply' by reasoning over the knowledge graph. We have created a query processing engine that takes complex queries and decomposes them into subqueries optimized to run on the respective knowledge graph or vector view of a VKG. We show that the VKG structure can process specific queries that are not efficiently handled by vector spaces or knowledge graphs alone. We also demonstrate and evaluate the VKG structure and the query processing engine by developing a system called Cyber-All-Intel for knowledge extraction, representation and querying in an end-to-end pipeline grounded in the cybersecurity informatics domain.

I. INTRODUCTION

Vector spaces and knowledge graphs each lose information when used alone: embeddings capture contextual similarity, while graphs represent explicit relations and support reasoning. The paper introduces VKG, a hybrid representation and query engine, and demonstrates it in Cyber-All-Intel for cybersecurity informatics.

I. INTRODUCTION

  • VKG combines explicit graph relations grounded in an ontology with implicit contextual information captured by vector embeddings [2],.The paper presents the combination as a way to use the complementary strengths of both representations.Source: §I · p. 1
  • Using only embeddings loses declarative information, while knowledge graphs can miss contextual information or be constrained by their ontology schema.The paper frames these as complementary information losses across representation methods.Source: §I · p. 1
  • The query engine decomposes input queries into subqueries for searching, listing, and inferring over the VKG structure.The subqueries are run on the graph or vector component as appropriate.Source: §I · p. 1
  • Cyber-All-Intel demonstrates VKG in a cybersecurity informatics system that represents and answers complex queries about vulnerabilities.An example query alerts when a vulnerability similar to denial of service is found in MySQL.Source: §I · pp. 1–2

II. RELATED WORK

Related work covers vector and graph approaches to semantic similarity and search, vectorized graph models, and cybersecurity knowledge representation. The paper distinguishes its approach by retaining a traditional knowledge graph alongside entity embeddings.

A. Vector Space Models & Knowledge Graphs

  • Vector embeddings support neighborhood-based similarity search, while graph-based semantic similarity remains challenging; the proposed VKG links graph nodes to their embeddings [13],,,,,.Prior work also explores top-k graph search and semantic indexing,.Source: A. Vector Space Models & Knowledge… · p. 2
  • Vectorized knowledge graph models such as HOLE and TransE learn vector representations of whole graphs, whereas this work retains a traditional graph for reasoning and dynamic cybersecurity data.The authors cite computational overhead from frequently changing vulnerability relations and incoming threat intelligence as a reason not to vectorize the whole graph.Source: A. Vector Space Models & Knowledge… · p. 2

B. Knowledge Representation for Cybersecurity

  • Cybersecurity knowledge representation includes ontologies and repositories,,,,, the UCO ontology, and systems that extract vulnerability information or issue alerts,.UCO integrates heterogeneous cybersecurity data and schemas, including standards such as STIX and CYBEX.Source: B. Knowledge Representation for… · pp. 2–3

III. VKG STRUCTURE

VKG links entities represented as knowledge-graph nodes to their vector-space representations, allowing applications to reason over explicit graph relations and compute over vectors. Its design uses the vector component for contextual similarity and the graph component for explicit assertions and reasoning.

III. VKG STRUCTURE

  • Each VKG entity is represented as a knowledge-graph node linked to a vector-space representation, so applications can reason over graph relations and compute over vectors.The structure creates a representation for relations and entities of interest present in text.Source: §III · p. 3
  • Graph assertions can encode facts such as Milo being a cat and Tom having Milo as a pet, while Milo's vector can find similar pets.The graph provides explicit relations; the vector representation supports similarity search.Source: §III · p. 3
  • VKG combines contextual information from embeddings with explicit relations and reasoning tools from knowledge graphs.Embeddings support neighborhood search and partial matching, while graphs support query languages, rules, and description-logic reasoning.Source: §III · p. 3
  • The design assigns fast top-k search to the vector component and slower reasoning computations to the knowledge graph, decomposing input queries across the two.The paper analogizes this to thinking fast in vector space and slowly and deeply with graph reasoning.Source: §III · p. 3
  • VKG can add domain knowledge from external sources such as DBpedia, YAGO, and Freebase to graph nodes, including facts absent from the input corpus.The example links Microsoft Internet Explorer to its DBpedia equivalent with owl:sameAs.Source: §III · p. 4

A. Populating the VKG Structure

The VKG population process builds vector and graph representations from a corpus, then links graph nodes to vector vocabulary entries. Its cost is dominated by RDF triple generation in the Cyber-All-Intel corpus.

A. Populating the VKG Structure

  • The population system takes a text corpus and creates the graph and vector parts separately before linking them.Vector training creates entity embeddings; entity and relation extraction yields RDF triples asserted using domain-specific ontologies.Source: A. Populating the VKG Structure · p. 4
  • Graph nodes link to corresponding vector-vocabulary words through the hasVector relation, allowing embeddings to be updated when the corpus changes.The vocabulary word is retained in the knowledge graph, while its embedding mapping is kept in the vector model output.Source: A. Populating the VKG Structure · pp. 4–5
  • Construction complexity scales with N × D × H for vectorization, C + R for RDF triple generation, and V for linking.The stated vectorization complexity assumes one hidden layer.Source: A. Populating the VKG Structure · p. 5
  • For the Cyber-All-Intel corpus of vocabulary size 246,321, RDF triple generation (C + R) took most of the construction time.Vector training (N × D × H) runs periodically, every two weeks in Cyber-All-Intel; hashing can improve the V-sized linking step and query-engine performance.Source: A. Populating the VKG Structure · p. 5

1) Cyber-All-Intel System:

Cyber-All-Intel represents cybersecurity information in a VKG populated from multiple data sources. Its query engine routes similarity search and graph-based listing or inference to the respective VKG components, and can filter vector results using graph information.

1) Cyber-All-Intel System:

  • Cyber-All-Intel collects and preprocesses cybersecurity data, stores a corpus, then creates RDF triples and vector embeddings and links them.Its sources include vulnerability databases, social media, blogs, and dark-web markets.Source: 1) Cyber-All-Intel System · p. 5

B. Query Processing

  • Complex application queries can combine commands, such as searching for products similar to Google Chrome and listing their vulnerabilities.The system assigns similarity searches to embeddings and list or infer operations to the knowledge graph.Source: B. Query Processing · p. 6
  • Similarity tasks suit the vector part, while declarative retrieval, inference, and rule-based reasoning belong on the knowledge graph.The paper notes that expert systems such as Cyber-All-Intel require concrete, well-reasoned solutions rather than only top-K plausible answers.Source: B. Query Processing · p. 6
  • VKG Search filters embedding-based similarity results using graph facts, such as retaining only entities classified as vulnerabilities.The example searches for entities similar to “denial of service” and applies the knowledge-graph class constraint.Source: B. Query Processing · p. 6
  • Knowledge-graph queries retrieve asserted facts or run application-specific inference rules, and graphs can integrate information through owl:sameAs.For example, Cyber-All-Intel can list vulnerabilities in Internet Explorer; graph filtering can refine similarity-search output.Source: B. Query Processing · p. 6
  • The query engine extends SPARQL by routing search to the vector part, list queries to SPARQL, and infer queries to the Apache Jena inference engine.The graph uses the Unified Cybersecurity Ontology, while the vector part uses word2vec.Source: 1) Cyber-All-Intel System · p. 5, B. Query Processing · p. 6

1) Query processing system:

An application query may be decomposed into components that run on the knowledge graph, the vector part, or both. The query-processing system executes those subqueries and combines their outputs to answer the original query.

1) Query processing system:

  • An input VKG query can be decomposed into components that run on the knowledge-graph part or the vector part.A query may contain multiple components on one part and another component on the other.Source: 1) Query processing system · pp. 6–7
  • The query-processing system executes each subquery on its designated VKG part and combines the outputs to answer the original query.Source: 1) Query processing system · p. 7

2) Example query:

The example decomposes a cybersecurity query into vector search and knowledge-graph operations; overlapping vulnerability sets trigger an alert.

2) Example query:

  • The query is split into finding vulnerabilities similar to denial of service, listing MySQL vulnerabilities, and inferring whether to alert.The first operation runs on vector embeddings; the listing and alert inference run on the knowledge graph.Source: 2) Example query · p. 7
  • The vector subquery searches for denial-of-service-like vulnerabilities and produces set V for use by later subqueries.The system filters the search output to retain vulnerabilities.Source: 2) Example query · p. 7
  • The first knowledge-graph subquery lists vulnerabilities explicitly mentioned for MySQL, producing set K.The query plan runs Qv and Qkg1 simultaneously, then runs Qkg2 after computing V and K.Source: 2) Example query · p. 7
  • The second knowledge-graph subquery uses domain-expert or administrator logic to decide whether overlap between V and K warrants an alert.In the illustrated case, the overlap results in an alert.Source: 2) Example query · p. 7
  • The example raises an alert when the vector-derived and graph-derived vulnerability sets overlap.The figure presents outputs from Qv and Qkg; the prose says an alert is raised when V and K overlap.Source: 2) Example query · p. 7, Figure 4 · p. 7

IV. EXPERIMENTAL RESULTS

The section introduces the experimental setup, then describes the data and evaluates the VKG structure and query engine using evaluation measures and runtime results.

IV. EXPERIMENTAL RESULTS

  • The experiments describe the data and evaluate the VKG structure and query processing engine using evaluation measures and runtime results.The section first presents the data description before the evaluation.Source: §IV · p. 7

A. Dataset and Experimental Setup

The experimental setup combines a multi-source cybersecurity corpus with word2vec and a linked knowledge graph, and uses annotated data to evaluate the system.

A. Dataset and Experimental Setup

  • The corpus includes 85,190 NVD vulnerabilities, 351,004 cleaned Tweets, and 25,146 Reddit and blog posts, alongside other sources.Sources include chat rooms, dark web, blogs, RSS feeds, social media, and vulnerability databases.Source: A. Dataset and Experimental Setup · p. 7
  • Word2vec models used dimensions of 500, 1000, 1500, 1800, or 2500, term frequencies of 1, 2, 5, 8, or 10, and a context window of 7.The knowledge graph was linked to equivalent entities in the vector-model vocabulary to form the VKG.Source: A. Dataset and Experimental Setup · p. 7
  • Five cybersecurity-familiar graduate students annotated entity classes and relations; annotations with Cohen’s Kappa below 0.7 were excluded.The entity and relation classes correspond to classes and properties in the Unified Cybersecurity Ontology and Intelligence Ontology.Source: A. Dataset and Experimental Setup · p. 8
  • The annotators treated products with the same vulnerabilities and products with the same use as correlated notions of similarity.The passage illustrates this with SQL-injection-bearing products and products affected by CSRF.Source: A. Dataset and Experimental Setup · p. 8
  • The test sets included 14 vulnerability groups, 11 attack groups, and 31 product groups, with abbreviations manually added to the groups.Examples of included abbreviations are DOS and CSRF.Source: A. Dataset and Experimental Setup · p. 8

B. Evaluations

The evaluations cover VKG search, knowledge-graph list queries, and linking between vector and graph representations; infer queries are excluded because their reasoning logic varies by application.

B. Evaluations

  • The study evaluates search and list queries but not infer queries, whose reasoning logic depends on the ontology and can vary by application.Source: B. Evaluations · p. 8
  • The evaluation compares vector embeddings, knowledge graphs, and VKG search, and assesses list-query triple quality and vector-to-graph linking.List queries run only on the knowledge-graph part because embeddings contain no declarative information.Source: B. Evaluations · p. 8

1) Evaluating the search query:

VKG search achieved higher MAP than the vector model alone by filtering entities using knowledge-graph class declarations. Embeddings also outperformed knowledge graphs in most similar groups and ran faster; separately, sampled knowledge-graph triples were manually assessed for correctness.

1) Evaluating the search query:

  • The best vector model reached MAP 0.69 on 56 similar groups with dimensionality 1500 and term frequency 2.Increasing dimensionality and decreasing term frequency sharply increased model-generation time.Source: 1) Evaluating the search query · p. 8, Figure 5 · p. 8
  • 47 of 56 similar groups had higher MAP with vector embeddings than with knowledge graphs, and vector neighborhood search was 11 times faster.The graph performed poorly for vulnerabilities and attacks, whose dense schemas affected schema matching.Source: Figure 6 · p. 9, 1) Evaluating the search query · p. 9
  • VKG search on vector space achieved MAP 0.8, significantly better than 0.69 from the vector model alone; graph class-type declarations enabled filtering entities, explaining the higher-quality results.Source: 1) Evaluating the search query · p. 9

2) Evaluating the list query:

  • Annotators marked 83% of 250 sampled cybersecurity triples correct, 9% partially correct, and 8% wrong.The triples were compared with their original text.Source: 2) Evaluating the list query · p. 9

3) Evaluating Vector and Graph linking:

Annotators found 97% of 250 reviewed VKG links correctly matched triple nodes to vector-model vocabulary. The paper concludes that combining vectors and graphs supports search, list, and inference queries, and demonstrates the approach in Cyber-All-Intel.

3) Evaluating Vector and Graph linking:

  • 97% of 250 reviewed VKG triples linked correctly to the corresponding vector-model vocabulary.The authors attribute this accuracy to the knowledge graph and vector models sharing an underlying corpus vocabulary.Source: 3) Evaluating Vector and Graph linking · p. 9

V. CONCLUSION & FUTURE WORK

  • The VKG engine decomposes queries into search, list, and infer commands, routing search to vectors aided by graph assertions and list/infer to the graph.The conclusion says this can answer queries not handled efficiently by either representation alone.Source: §V · p. 9
  • Cyber-All-Intel demonstrates VKG extraction, representation, and querying in a cybersecurity informatics pipeline using intelligence from textual sources.Sources include vulnerability databases, dark-web markets, social networks, and blogs.Source: §V · pp. 9–10
  • The authors identify more query commands and additional use cases and applications as future work.Source: §V · p. 10

Related papers

Loading 1708.03310v2…