Semantic Similarity Graph Construction

117 concepts109 papers1 proposal

The Core Intuition: Moving Beyond Pairwise Similarity

When we represent text as dense vector embeddings, our first instinct is often to compute the cosine similarity between pairs of vectors. If we want to know how related two words, sentences, or documents are, we look at their dot product in the embedding space.

However, isolated pairwise comparisons suffer from a fundamental limitation: they miss the global topology of meaning. Language and knowledge are not just collections of independent pairs; they form a complex web of indirect associations. For instance, two concepts might not share a high direct similarity score due to domain shifts or vocabulary mismatches, yet they may be strongly connected via a chain of intermediate concepts.

By transforming vector spaces into semantic similarity graphs, researchers build a structural landscape where textual units act as nodes and their embedding similarities define the edges. This graph-based representation allows us to leverage network science, community detection, and random walks to uncover higher-order relationships that flat vector spaces obscure.

Constructing the Graph: From Vectors to Topology

The construction of a semantic similarity graph follows a repeatable recipe across various scales of text:

  1. Node Definition: Identify the discrete textual or conceptual units of interest. These can be individual words, relational triples, sentences, or entire documents.
  2. Embedding Generation: Map each node into a high-dimensional vector space using a representation model (such as Word2Vec, BERT, or specialized document encoders).
  3. Edge Establishment: Connect nodes based on their proximity in the embedding space.

To prevent the graph from becoming a dense, uninformative clique where every node connects to everything else, researchers apply sparsification strategies:

  • Thresholding: An edge is drawn only if the cosine similarity between two nodes exceeds a predefined minimum value. For example, Günes Erkan et al. utilize this approach in LexPageRank to model sentence centrality for multi-document summarization, while Goran Glavaš et al. apply it to sentence nodes for unsupervised text segmentation.
  • $k$-Nearest Neighbors ($k$-NN): Each node is connected exclusively to its top $k$ most similar neighbors. This ensures a bounded degree distribution. Jianglin Lu et al. demonstrate that building a $k$-NN graph over semantic embeddings naturally approximates the power-law distribution found in real-world scale-free networks, allowing dominant thematic hubs to emerge organically. Similarly, Venkatesh Bollineni et al. construct $k$-NN networks of document embeddings to map thematic clusters in ancient texts.

Exploiting the Topology: Random Walks and Diffusion

Once the graph is built, why does it work better than raw embeddings? The power lies in graph traversal algorithms that capture transitive similarity.

Consider the problem of dictionary expansion or keyword discovery. If we only look at immediate neighbors in an embedding space, we might miss relevant terms that lie just beyond our threshold. J. L. Schindler et al. show that graph diffusion methods can effectively capture longer, indirect chains of meaning across a similarity network, outperforming direct pairwise lookups.

Another powerful mechanism is the random walk. By simulating a particle moving across the similarity graph, we can compute a global probability distribution that reflects both local similarity and structural importance. For instance, Elaheh ShafieiBavani et al. apply a random walk algorithm over a semantic network to evaluate summary quality, capturing nuanced conceptual overlap rather than surface-level word matching. Similarly, Erik Cambria et al. utilize spreading activation over a graph-based common-sense knowledge base to discover how sentiment propagates across conceptually related terms.

Applications Across Scales

This paradigm is remarkably versatile, operating seamlessly at every level of linguistic granularity:

Lexical and Word-Level Graphs

At the word level, similarity graphs help model the mental lexicon and predict cognitive properties. Hae Won Park et al. represent a vocabulary as a graph where nodes are words and edges are based on an embedding similarity threshold, using it to predict a child's vocabulary knowledge based on network connectivity. To predict fine-grained emotional intensity, Liang-Chih Yu et al. use embedding similarity to weight edges between words, ensuring that label propagation is proportional to semantic proximity.

In a structural analysis of machine translation, Fatemeh Mohammadi et al. construct word similarity networks to quantify how specific gender stereotypes cluster around target anchors in high-dimensional spaces. Even for complex expressions, Rafael Ehren constructs graphs for individual multiword expression instances, using cosine similarity weights to distinguish between literal and idiomatic meanings.

Sentence and Triple-Level Graphs

When moving to relational data, text segments or facts can be grouped structurally. Dmitry Ustalov et al. treat relational triples as nodes in a similarity graph, mapping semantic frame induction to a community detection problem where coherent frames emerge as tightly knit subgraphs. For document enrichment, Bing Qin et al. connect extracted triples via vector similarity, enabling the discovery of related background knowledge across disparate facts.

In the context of large language models, Yukun Li et al. transform a set of model-generated responses into a similarity graph to analyze the agreement landscape among multiple stochastic outputs, calibrating the model's confidence based on the network's topology.

Document and Item-Level Graphs

At the largest scale, entire documents or entities are linked to map broad domains or bypass data sparsity. Weijian Zhang et al. calculate the cosine similarity between full-text document embeddings to build an immediate, citation-like network for newly published research papers before formal citations accumulate. Similarly, Rabindra Nath Nandi et al. treat individual patent documents as nodes and establish edges via semantic similarity scores to predict an invention's future impact using Graph Neural Networks.

In recommendation systems, where user-item interaction data can be sparse, Zaiqiao Meng et al. connect item nodes in a sub-graph based on the semantic similarity of their textual reviews, creating a content-aware network that mitigates the cold-start problem. To extend this further, Ziqiang Cui et al. construct a global item-item similarity graph from textual summaries, allowing recommendation engines to retrieve semantically related items that are completely disconnected in traditional structural knowledge graphs.

By mapping continuous vector spaces into discrete topological networks, semantic similarity graph construction combines the nuanced representational power of deep learning with the global analytical tools of network science.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_semantic_similarity_graph_construction_662ba8c2,
  title = {semantic similarity graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semantic-similarity-graph-construction/rdr_662ba8c2990a4d41978d7f3cd0f6587b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_semantic_similarity_graph_construction_662ba8c2_v1,
  title = {semantic similarity graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semantic-similarity-graph-construction/rdr_662ba8c2990a4d41978d7f3cd0f6587b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake