PaperlayerView exact revision on arXiv

Source-linked AI summary

Hidden relationships in a document-derived property graph: top-k chunk embeddings and inverse-distance weighting over a dynamically evolving ontology

Bilge Kaan Karamete, Hunter Casten

arXiv:2609.00387v1cs.CEcs.LG

TL;DR

The paper addresses the gap between sentence-faithful extraction and disconnected entities whose relationships are only implied across documents. It adds an additive second pass using top-k chunk retrieval, Shepard inverse-distance weighting, and ungated accumulators, reporting dimensionality stability and a 25× faster top-k formulation. The method preserves extracted facts while producing a separately labelled, incrementally maintained layer of embedded edges.

  • Problem

    Sentence-level extraction can leave semantically related entities disconnected, while hidden relationships lack labelled ground truth for direct evaluation.

  • Method

    The method embeds each document's chunks, retrieves top-k neighbours, expands chunk pairs into entity pairs, scores them with corrected Shepard weighting, and persists ungated accumulators.

  • Results

    768-dimensional embeddings agree with a 3072-dimensional reference on 92% of emitted edges, 240-dimensional embeddings agree on 72%, and the aggregate top-k formulation is 25× faster than a window function.

  • Takeaways & Limitations

    The derived layer reconnects implied relationships while remaining separate from extracted facts and supports incremental updates without recomputation.

  • Takeaways & Limitations

    The paper reports no precision or recall because no labelled hidden-relationship corpus exists, and its availability is tied to one embedding-provider family.

Abstract

from arXiv · show

Large language models extracting knowledge graphs from text capture only explicitly stated facts, often leaving semantically related entities disconnected across documents. We present an additive, engine-neutral second pass that discovers these latent ties without altering extracted facts. Each document is chunked and embedded once; top-k nearest- neighbor queries across existing chunks yield candidate node pairs via entity membership maps. Candidate pairs are scored using Shepard inverse-distance weighting with a rescaled chord distance metric, avoiding the threshold-collapsing flaw of affine cosine scoring behind a k-NN gate. Un-gated per-pair accumulators form a commutative monoid, ensuring the pipeline is strictly order-independent and scales incrementally without recomputing prior documents. Implemented across FalkorDB, Kinetica, ArangoDB, and Neo4j, our method shows that 768- and 240-dimensional embeddings retain 92% and 72% edge fidelity against a 3072-D baseline while achieving a 25x faster top-k formulation.

1 Introduction

The paper adds a separate similarity layer to reconnect entities whose relationships are implied across chunks but never explicitly stated. It combines top-k chunk retrieval, Shepard weighting, and persisted accumulators to add auditable embedded edges incrementally without changing extracted facts.

  • Motivation: LLM extraction can produce a correct graph that remains disconnected when related entities are never linked in one sentence.The running example has four stated edges but leaves two components, including Gulgun–Tan and FSI–BabelStreet.
  • Approach: The similarity pass adds only weighted embedded edges with support counts and cannot modify or delete extracted edges.The derived layer is also withheld from the natural-language query path, preserving the distinction between inferred and extracted facts.
  • Approach: Candidate node pairs come from top-k nearest chunks, entity membership expansion, and same-chunk co-occurrence before inverse-distance scoring.The seven-stage pipeline is embed, persist, k-NN, expand, accumulate, select, and link.
  • Incremental construction: Persisting ungated per-pair accumulators makes the incremental construction order-independent and avoids recomputing prior documents.Evidence below threshold remains available for later accumulation and promotion.
  • Scoring: The corrected cosine-space formulation uses Shepard inverse-distance weighting with a rescaled chord-distance value term instead of affine cosine scoring behind a k-NN gate.The affine value term collapses into a narrow admitted band, making the write threshold ineffective; the replacement is v = 1 − β/2.
  • Results: 768-dimensional embeddings agree with a 3072-dimensional reference on 92% of emitted edges, while 240-dimensional embeddings agree on 72% at 960 versus 12,288 bytes per chunk.The implementation writes the same embedded edges across FalkorDB, Kinetica, ArangoDB, and Neo4j, while the top-k formulation is 25× faster than a window-function form.
  • Limitations: Precision and recall are not reported because the corpus has no labelled ground truth for hidden relationships.The agreement figures measure stability under dimensionality reduction, not correctness.

2 Related work

The paper positions its method at the intersection of text-derived knowledge graphs, graph link prediction, spatial interpolation, and nearest-neighbour search. Its distinctive signal is paragraph provenance in text-embedding space, combined with an auditable, engine-neutral derived layer for directly queried property graphs.

  • Knowledge graphs from text: Unlike GraphRAG, which uses graph structure for answer generation, this paper treats the directly queried property graph as the product.That distinction motivates first-class embedded edges with explicit weights and support attributes.
  • Link prediction: Unlike structural link-prediction methods, this approach scores provenance connections between paragraphs in text-embedding space rather than graph topology.Structural alternatives include TransE, ComplEx, node2vec, and SEAL; the signals are described as complementary.
  • Link prediction: The provenance signal requires no training and makes each derived edge auditable through its supporting paragraph pairs and support count.A structural embedding supplies a score, whereas a chunk pair supplies a citation.
  • Inverse-distance weighting: Shepard interpolation is adapted to high-dimensional cosine space, where L2 normalization makes inverse cosine distance equivalent to Shepard p = 2.The zero-distance singularity is intentionally used so same-paragraph entity pairs dominate similar-but-separate paragraphs.
  • Embedding and search: The method uses dense passage embeddings and Matryoshka prefixes so embedding width becomes a request-time storage choice.Exact top-k self-joins are the default below roughly 10^5 stored vectors, with HNSW used for candidate selection beyond that scale.
  • Embedding and search: Partitioning approaches such as k-means and self-organising maps were measured but not adopted for candidate generation or scoring.The paper reports negative results for partitioning alternatives across multiple representations.
  • Property-graph systems: The engine-neutral design accounts for differing property-graph label models and makes label-scoped traversal central to separating derived from extracted edges.The same weighted embedded edges are written through adapters, while label filtering determines whether the graph remains legible.

3 From documents to a property graph

The pipeline converts documents into a canonical property graph, preserving extracted facts while attaching a separate additive similarity layer. Paragraph-level chunks, entity membership maps, and incremental top-k comparisons support derived edges without altering the extracted graph.

  • Extraction and ontology: Documents are split into paragraph chunks, which are extracted under a constrained schema and folded into a canonical ontology.Paragraph boundaries preserve the unit used for extraction and membership mapping.
  • Extraction and ontology: The live ontology grows as documents arrive through new canonical types, aliases, and separately stored facets.Facets describe dimensions of a type rather than replacing its structural type.
  • Similarity inputs: A chunk-to-entity membership map is the bridge from paragraph embeddings to graph entities, expanding chunk pairs into candidate node pairs.The map records one row for each chunk–entity membership.
  • Additive seam: The derived layer cannot delete, overwrite, or create nodes, so failures can omit intended edges but cannot corrupt extracted facts.Its only mutation is adding edges with a label extraction never emits.
  • Similarity pass: The similarity pass compares each arriving document’s chunks against stored chunks, then writes weighted embedded edges through the same additive seam.The query side contains new chunks while the search side contains every stored chunk.
  • Similarity pass: Exhaustive top-k comparison is affordable because only the arriving document supplies query chunks, making the cost linear in corpus size with a small constant.After a threshold, HNSW can accelerate candidate retrieval, weakening only the true-neighbor guarantee.

4 Embedding: two widths, pinned per graph

The system stores unit-normalized paragraph embeddings at two fixed widths, using Matryoshka truncation to trade storage for agreement with a 3072-dimensional reference. Width and embedder identity are pinned per graph to preserve a shared vector geometry.

  • Normalisation: Chunk vectors are L2-normalized, making inner products equal cosine similarity and enabling raw inner-product k-NN computation.Normalization also supports the later geometric interpretation of inverse-distance weighting.
  • Matryoshka widths: The Matryoshka embedder returns the first N components of the full vector, so width can be selected at request time without retraining.The supported widths are 240 and 768 dimensions.
  • Agreement study: 92% of emitted edges agree with the 3072-dimensional reference at 768 dimensions, while 72% agree at 240 dimensions.The study compares emitted edge sets under identical corpus and parameter settings.
  • Storage trade-off: The 240-dimensional width uses under one thirteenth of the reference storage, while 768 dimensions use one quarter of it.The shipped default is 240 dimensions, with 768 offered as the fidelity option.
  • Scope of evaluation: Agreement with the reference is not accuracy because no labelled set determines whether disagreements are right or wrong.The measurements support a quantified storage-versus-stability trade rather than an accuracy claim.
  • Graph consistency: The graph records its initial width and embedder identity, refusing later conflicts to prevent meaningless comparisons between incompatible vector spaces.Vectors of equal length from different embedders can still lack a shared geometry.

5 Scoring: inverse-distance weighting over cosine neighbourhoods

The section formulates cosine-neighbourhood scoring as inverse-distance weighting with a rescaled chord-distance value, then shows why affine cosine scoring collapses behind the k-NN gate. The formulation also constrains admissible thresholds and requires careful accumulation guards.

  • Evidence construction: The method converts chunk-pair cosine evidence into node-pair evidence through entity membership expansion and canonicalisation.Each chunk pair contributes to an unordered node pair only when its chunks contain the corresponding entities.
  • Inverse-distance weighting: On L2-normalised vectors, the distance relation makes the weighting exactly Shepard inverse-squared-distance weighting, regularised at the origin.The constant relating cosine distance to Euclidean distance cancels in the weighted mean.
  • Value function: The rescaled chord-distance value gives 1 for identical directions, 1/2 for orthogonal vectors, and 0 for opposed vectors without depending on the gate.This geometric scaling replaces the affine value term.
  • Gate interaction: At β = 0.35, affine scoring confines every weight to [0.825, 1], so any threshold at or below 0.825 admits every candidate.The gate therefore collapses the useful threshold range.
  • Threshold constraint: The chord formulation yields a gate-dependent floor, requiring the write threshold and neighbourhood gate to be configured together.The implementation displays the implied floor, while an earlier version displayed the floor of the replaced value term.
  • Accumulation safeguards: The proposed accumulation uses per-node-pair triples and guards against duplicate contributions within chunk pairs and mirrored intra-document chunk pairs.These guards prevent systematic overcounting, especially for dominant same-chunk evidence.

6 A layer that evolves with the corpus

The evolving layer persists additive, ungated accumulators so evidence can accumulate across arriving documents without recomputation and with order-independent final state. Its guarantees are bounded by candidate generation, intermediate snapshots, and aggregate quadratic ingest cost.

  • Accumulator state: The edge weight is computed from a stored accumulator triple at read time, enabling associative and commutative merges across batches.The accumulator stores weighted-value sum, weight sum, and support rather than the derived weight.
  • Order independence: Final accumulator state and node-pair weights are independent of document arrival order when documents are processed against a fixed corpus.This follows because per-document accumulator maps combine by commutative monoid addition.
  • Evolving evidence: Intermediate emitted edges can depend on arrival order because thresholding applies to partial sums, while later documents can cause previously subthreshold pairs to cross the threshold.The snapshot reflects evidence seen so far rather than the eventual accumulated state.
  • Candidate-generation boundary: Candidate generation is not order-free because each arriving document queries the corpus as it exists at that moment.In a comparison, 89.8% of common-pair weights agreed to the last bit, with mean absolute difference 8.1 × 10^-4.
  • Scaling: Exact insertion costs Θ(c N) similarity evaluations for a document with c chunks against N stored chunks, while approximate indexing targets roughly Θ(c log N).Across one-document-at-a-time ingestion, the cumulative exact work remains quadratic in total chunk count.
  • Limitation: The cumulative quadratic remains a horizon: ingesting one million chunks takes about four hours and ten million takes seventeen days.These figures describe aggregate ingestion rather than a single insertion.
  • Approximate search: HNSW reproduces 99.6% of the exact written-edge result at its cheapest setting and 100% from ef = 80 upward, with insertion costing 0.003 s versus 0.185 s to rebuild.The reported comparison is on written edges after downstream filtering, not merely retrieved neighbours.
  • Scope boundaries: Changing the value function invalidates every stored accumulator, while the per-endpoint cap bounds each run’s additions rather than the graph-wide final edge count.Existing edges are not retracted when later evidence lowers a weight below threshold.

7 Implementation

The implementation separates pure similarity arithmetic, embedding, orchestration, storage, and graph adapters. It uses aggregate top-k retrieval, additive accumulation, and an engine-neutral embedded edge layer that remains outside the natural-language answer path.

  • Modular architecture: The pass is split into pure arithmetic, embedding, orchestration, storage, and graph-adapter modules.The arithmetic module has no I/O or configuration, while storage and adapters are injected parameters.
  • Top-k retrieval: Top-k retrieval uses a self-join restricted to arriving-document chunks while searching all persisted chunks.The query expands chunk pairs through entity membership maps into candidate node pairs.
  • Top-k retrieval: 25× faster top-k formulation: aggregation took 1,403 ms versus 35,819 ms for a window-function form at 768 dimensions over 100k rows.The aggregate maintains bounded heaps instead of materialising and sorting every candidate pair.
  • Accumulation: Batch accumulation preserves the same per-pair arithmetic while reducing a 19,900-pair merge from 82.3 s through single multi-row conflict resolution.The rewrite changes statement count, not the arithmetic.
  • Engine portability: Supported engines write the embedded label through a shared adapter, while schema-backed labels require a DDL change rather than an additive element write.Direction is read from the store and must agree with the graph’s declared direction.
  • Answer-path separation: Embedded edges are similarity artefacts, not extracted facts, and the answer path filters them from relation types and ontology triples.They remain available to direct graph queries, visualisation, and consumers that explicitly interpret weighted similarity edges.

8 Results

The running examples show the pass adding weighted embedded edges without changing extracted nodes or stated edges, while threshold and cap gates control emitted density. Formulation studies identify chord weighting and aggregate top-k retrieval as important design choices.

  • 8.1 The running example: The pass adds four embedded edges and no nodes, joining two extraction components into one graph.The four derived weights range from 0.72 to 0.84, above the default threshold of 0.7.
  • 8.1 The running example: 86 embedded edges raised the Figure 6 graph to 110 total edges from 24 stated relations.The similarity layer therefore contributed nearly four in five edges in that run.
  • 8.1 The running example: 24 below-threshold pairs were retained in accumulators, while the cap removed 23 of 147 pairs that cleared θ.Thresholding and the per-endpoint cap therefore act as separate gates.
  • 8.1 The running example: At θ = 0.70, all 124 edges remained and the graph was connected; at θ = 0.74, 58 same-paragraph edges remained and the graph split into two components.The transition occurs in a narrow threshold band, while values above 0.74 produce no further changes.
  • 8.2 Embedding width: 92% of emitted edges agreed with the 3072-dimensional reference at 768 dimensions, versus 72% at 240 dimensions.The 240-dimensional setting uses 960 bytes per chunk against 3,072 bytes at 768 dimensions and 12,288 at 3072 dimensions.
  • Formulation studies: The chord term placed the gate floor at 0.582 and allowed a threshold of 0.7 to filter values, unlike the affine term’s [0.825, 1] range.Moving the L2 term into the weight reduced the closest-to-boundary influence ratio from 350× to 19×.

9 A corpus-scale test on public threat intelligence

The corpus-scale test uses public threat-intelligence feeds to evaluate cross-document discovery, incremental accumulation, and ontology growth. It reached 246 ingested documents, but ingestion failures, feed-summary inputs, and prefix skew constrain interpretation.

  • Corpus and sampling: The corpus-scale run ingested 246 of 856 public threat-intelligence documents from 43 live sources.The 246 documents were a feed-order prefix rather than a representative sample.
  • Corpus and sampling: Threat reporting provides cross-document ties because independent publishers describe shared campaigns in different words without stating every connection.This setting directly matches the pass’s intended latent-link use case.
  • Corpus construction: Feed summaries had a median length of 395 characters, with 403 single-paragraph documents and 318 at the six-paragraph cap.Single-chunk documents must find neighbours elsewhere in the graph beyond same-chunk co-mention.
  • Run configuration: The run used 240 dimensions, k = 20, β = 0.35, θ = 0.7, and cap 10, with concurrent document processing enabled by accumulator algebra.Chunks were persisted before each document queried for neighbours.
  • Run outcomes: 246 documents produced 974 paragraphs, 7,672 entities, and 7,787 relations in 8.0 hours, with seven failed documents.Failures included four DuckDB lock conflicts, one timeout, and malformed facet payloads; failed documents wrote no ledger row or vectors.
  • Pipeline cost: Ontology folding caused per-document time to rise from 11.9 s to 80.4 s by document twelve, while the similarity pass itself took 3 s of a 73 s document.Fan-out of independent fold checks improved the pipeline end to end by 6.3×.

9.3 The ontology as it is learned

The ontology is learned incrementally from extracted types and relations rather than specified in advance. Adding the derived layer preserves structural vocabulary but increases relation connectivity, while ontology folding can produce persistent near-synonym proliferation.

  • Ontology learning: The first document is processed against an empty graph, and later documents are folded against the ontology accumulated so far.The resulting ontology is described as a residue of arriving documents rather than a fixed design.
  • Ontology learning: Organization already represented 27.8% of nodes after five documents, while Campaign and Activity each represented 1.4%.Type shares depend on what has arrived and the long tail remains subject to future corpus needs.
  • Ontology boundary: Near-synonym proliferation persisted in a longer run, ending with 903 node labels and 1,315 edge labels that exceeded the workbench’s Graphviz layout capacity.The earlier run produced pairs such as Product/Software Product and Technology/TechnologyConcept.
  • Extracted ontology: The five-document extracted ontology contains 5 types, 5 relation types, and 5 arrows over 7 edges after one document.The extracted panels filter out embedded relations.
  • Derived ontology: With the derived layer restored, the five-document graph contains 13 arrows over 107 nodes and 262 edges, including 67 derived arrows and 207 derived edges.Nearly four derived edges occur for every stated edge, and all derived edges have weight ≥0.9997 in this short run.

9.5 What the vocabulary did over 246 documents

Across 246 documents, structural vocabulary largely stabilised, while facet vocabulary continued expanding and prevented the ontology from converging as a whole.

  • 24 canonical entity types were reached by document 246, with the final 46 documents adding 0.04 new types per document.The first ten documents added types at 1.33 per document, and the cap of 100 canonicals per kind was never approached.
  • 145 canonicals survived from 1,119 proposals, as nearly nine names in ten were absorbed rather than minted.The ledger and cumulative log differ because some names were first minted on a facet axis and later used structurally.
  • 85 of 104 canonical entity names were minted on a facet axis, leaving 101 distinct node labels at the run’s end.Nodes carry both structural types and facets as labels, while facet names are not capped like structural types.
  • EntityType and RelationType were deliberately not folded, but this exposed a defect in handling missing-axis placeholders.The reported repair left every count in the section unchanged.
  • Facet vocabulary does not stabilise on its own because facets are a different ontology kind and remain uncapped.Capping facet names would change what the ontology means, so the uncapped growth is reported rather than fixed.

9.6 The derived layer at corpus scale

At corpus scale, the derived layer becomes much larger than the extracted graph and connects documents densely, while persisted accumulators preserve weaker evidence for later promotion.

  • 69,867 distinct derived edges account for 89.6% of the graph’s 77,999 edges across 6,706 nodes.The run wrote 635,562 EMBEDDED emissions; the extracted graph is consequently the smaller layer.
  • 66.1% of written derived edges come from same-chunk co-mentions with median weight 1.000, while 23,400 cross-document edges have median weight 0.749.A weight of 1 means co-mention by construction, whereas cross-document edges represent ties unstated by any single document.
  • 1,517,795 un-gated accumulator rows cover 6.8% of node pairs, including 93,322 below the gate and eligible for later promotion.These persisted assertions can change arithmetically when additional documents arrive, without recomputing prior evidence.
  • With top_n = 10, 55.3% of endpoints exceed the nominal cap; derived degree has median 11, ninetieth percentile 36, and maximum 742.The cap applies per run, so hubs accumulate a fresh top ten from every document that mentions them rather than obeying a graph-wide degree bound.
  • Raising θ from 0.70 to 0.80 discards 88.8% of candidate pairs but only 27.6% of schema arrows.Because each schema arrow survives if any instance survives, θ is strong for instance filtering but weak for ontology-level decluttering.
  • Only 0.36% of 1.5 million pairs have weights in [0.80, 0.999), leaving little intermediate population for threshold tuning.The distribution is bimodal: same-chunk co-mentions cluster at 1.0, while cross-document evidence lies near the 0.582 floor.

9.8 Seeing the neighbourhood structure: the corpus on S2

The S2 projection preserves broad neighbour-versus-random separation but loses much of the detailed neighbourhood structure, so its shape alone is not reliable evidence.

  • PCA is used because the L2-normalised vectors lie on S239 and PCA preserves the most squared distance among the retained coordinates.For unit vectors, classical multidimensional scaling on the cosine Gram matrix is algebraically identical to PCA.
  • The projection retains only 11.0% of variance, with median deviation retention 0.304, retention@20 of 14.2%, and cosine rank correlation ρ = 0.371.Each of these measures worsened as the corpus grew.
  • 240-dimensional nearest neighbours project to median cosine +0.865 versus −0.007 for random pairs, and remain closer than random pairs 85.6% of the time.This broad separation remains essentially unchanged from 85.3% at 56 chunks despite losing which specific neighbour is which.
  • The gate admits 497,499 of 497,503 chunk pairs, so drawing all admitted arcs would approximate a complete graph and obscure the comparison.The gate is not drawn as a projected spherical cap because projection does not preserve angles.

10 Limitations

The method has important scope and evaluation boundaries: its evidence is unvalidated for accuracy, several design choices constrain deployment, and the derived layer can overwhelm graph traversal.

  • No precision or recall is available because the corpus lacks human labels for hidden relationships.Agreement between configurations of one method must not be interpreted as accuracy.
  • The chord value term is analytically motivated but not validated against a third alternative without ground-truth hidden relationships.The arguments concern formula shape, not whether the resulting edges are better.
  • On this corpus, the gate admits 100.00% of chunk pairs and θ = 0.7 passes 98.2% of node pairs, leaving selection mainly to the per-endpoint cap.This concentration limits how strongly the gate and threshold are tested here.
  • The ε = 10−6 setting is untuned, and its appropriate magnitude may differ for long paragraphs where sharing one is weaker evidence.The crossover point for changing ε has not been characterised.
  • Changing the value term invalidates stored accumulators, and the current remedy is re-extraction into a fresh graph.Nothing detects mixtures of accumulators written under different value functions.
  • Exact k-NN is linear in corpus size per document and may require HNSW beyond roughly ten million chunks.The current implementation values exactness because today’s scan constant is small, but cumulative ingest is the scaling horizon.
  • Warehouse-backed graphs are excluded because schema-level labels cannot receive the additive element write required by the link stage.Materialising the layer behind views would be a different design.
  • Whole-document extraction emits a clique, so the pass requires paragraph-sized chunking and cannot combine both extraction modes.Documents beyond the paragraph cap are truncated, leaving tail entities without similarity evidence.

11 Conclusion

The paper combines a separate embedded layer with corrected cosine-space weighting and persisted accumulators to recover implied ties without altering extracted facts. This design supports order-independent incremental updates, while its evaluation remains limited because the corpus lacks labelled hidden relationships.

  • 11 Conclusion: The derived layer adds weighted embedded edges without modifying or deleting extraction-produced facts.It uses one separate edge label carrying a weight and support count.
  • 11 Conclusion: The cosine-space formulation avoids a k-NN gate failure in which affine value scoring makes write thresholds ineffective.The rescaled chord distance preserves a meaningful threshold and imposes a constraint tied to the gate.
  • 11 Conclusion: Persisted per-pair accumulators make the layer order-independent, avoid recomputation as documents arrive, and allow thin evidence to accumulate past the threshold.Associative addition, rather than change monitoring, lets the layer evolve with the corpus.
  • 11 Conclusion: The method’s evaluation cannot yet establish how often its generated edges would be endorsed by readers.A labelled set and precision measurements across thresholds are identified as necessary next work; ε remains inherited rather than empirically tuned.
Loading 2609.00387v1…