Skip to content

[Feature] Add cross-chunk graph deduplication and entity resolution #435

Open

Description

@iiiiSaber

Search before asking

  • I had searched in the feature and found no similar feature requirement.

Related: #344 focuses on chunk-level extraction concurrency. This request addresses deduplication and entity resolution after chunk extraction.

Feature Description (功能描述)

Graph extraction processes chunks independently and concatenates their vertices and edges. Repeated entities can appear multiple times, while different names for the same entity can remain disconnected. There is no cross-chunk policy for resolving aliases or conflicting properties before import.

Observed reproduction using DeepSeek through POST /graph/extract, with two input strings, split_type: "document", and review disabled. The inline schema defines person, company, and city vertices keyed by name, plus works_for and located_in edges.

Chunk 1: Alice works for Acme.
Chunk 2: Acme Ltd., also known as Acme, is based in Beijing.

The request returned HTTP 200 in 8.31 seconds, with status: "succeeded", no warnings, 4 vertices, and 2 edges:

1:Alice --works_for--> 2:Acme
2:Acme Ltd. --located_in--> 3:Beijing

The explicit alias remained two company identities, leaving the subgraphs disconnected. After resolving the supported alias, the expected graph has 3 vertices and 2 edges:

Alice --works_for--> Acme --located_in--> Beijing

This records one observed run; model output may vary.

Proposal

Add an optional internal stage after chunk extraction. Run deterministic checks first; use the LLM only as an optional judge for unresolved candidates:

  1. Deterministic duplicate detection: group vertices by schema-compatible labels and compare typed IDs and declared identity keys. Consolidate matching identities without LLM calls. Conflicting authoritative identifiers rule out a merge; conflicting properties are reported rather than overwritten.
  2. Deterministic candidate matching: for remaining vertices, use character n-grams/token overlap and a lexical similarity score, such as Jaro-Winkler, to shortlist potential aliases within compatible groups. Preserve punctuation-sensitive identifiers and keep short names eligible. Normalized names or similarity scores alone do not authorize a merge.
  3. Optional LLM judgment: only send unresolved candidate pairs to the existing configured model, including both extracted entities, the relevant schema, and their original source chunks. Request an internal same, different, or uncertain decision with supporting evidence. If judgment is disabled, fails, exceeds its budget, or remains uncertain, keep the entities separate. Bound candidate counts, model calls, and concurrency.
  4. Apply confirmed merges: combine deterministic matches and model-confirmed matches only after checking group-wide identity constraints and contradictory decisions. Resolve mappings to stable canonical IDs, rewrite edge endpoints, merge compatible properties with provenance, and validate the combined graph. Deduplicate relationships using schema identity while preserving legitimate parallel edges and self-loops.

For the reproduction above, deterministic matching should shortlist Acme and Acme Ltd.. The optional judge can then use the original second chunk's "also known as Acme" statement to confirm the alias.

Are you willing to submit a PR?

  • Yes I am willing to submit a PR!

Code of Conduct

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions