Graph expansion inside a vector database (Milvus)

What you'll learn

• Explain how powers of an incidence matrix expand vector-search seeds into candidate relations.
• Trace the candidate set and source passages at each expansion degree.
• Diagnose a hub that floods the candidates, and an entity split across spellings.
• Choose separate budgets for seeds, degree, reranking and final passages.

Lesson 3 of T13.3 answered corpus-wide questions from community reports. This lesson goes back to multi-hop questions, with no graph database at all: the graph lives in a few arrays beside a vector store.

The notebook's question is "What contribution did the son of Euler's teacher make?" Answering it takes three hops: Euler's teacher was Johann Bernoulli, Johann's son was Daniel, and Daniel's contributions are in a passage that never mentions Euler. A flat search on the question scores passages against Euler and contributions, and the Daniel passage has little reason to rank. Larkspur has the same shape: cancellation leads to export, export to snapshot, and the snapshot passage holds the retention rule.

Graph expansion grows a set of retrieved entities or relations into their graph neighbourhood, a fixed number of steps at a time, before reranking picks what reaches the answer. The Milvus notebook stores three collections and two adjacency maps:

Table 1: The notebook's stores. Traversal runs in application memory; Milvus supplies vector search and stored records.

Its four-passage Bernoulli dataset yields 26 entities and 22 relations, counted by running the notebook's preparation cells in the scratchpad.

Let B be the entity-by-relation incidence matrix: B[e,r]=1 when entity e takes part in relation r. Then B Bᵀ connects entities that share a relation, and Bᵀ B connects relations that share an entity. The notebook raises these to the target degree, multiplies the entity side by B to land on relations, takes the nonzero entries, and merges the candidates from the entity and relation seeds (Milvus Graph RAG tutorial).

Figure 1: Expansion inside the retrieval pipeline. Only the first step touches the vector store.

Matrix products count walks. A nonzero entry says a path exists, and does not certify that the relation helps answer the question. The diagonal of B Bᵀ is nonzero too (each entity shares a relation with itself). A higher degree therefore keeps every earlier candidate and adds new ones. Direction and relation type need separate handling: an undirected incidence matrix forgets which way a predicate points.

The interactive lab computes the entity-side row of (B Bᵀ)^d B on an eight-entity Larkspur fixture. Degree 0 shows the relations touching the seed and serves as a teaching baseline; the notebook's target degree starts at 1. The fixture has no embedding or model output, and choosing a seed stands in for the vector search.

With Cancellation selected, degree 0 reaches the cancellation-to-export and cancellation-to-billing relations. Each degree then adds two:

Table 2: Expansion from the Cancellation seed, as the lab prints it.

Starting from Outage gives the same relation counts and different passages: 1, 2, 4 and then all 5. The export question needs the degree 1 snapshot relation. The billing branch arrives at the same degree, reachable and irrelevant. Rerank relations against the question, then fetch and deduplicate their passages, and compare the candidate set before and after reranking against the golden evidence set. Keep the route for debugging; cite the passage.

The notebook's own data shows how fast a hub fills the set. We ran its expansion cells from three seed entities:

Table 3: Expansion on the notebook's Bernoulli data (scratchpad run of its pure cells; no embedding calls).

From "Leonhard Euler", one degree passes through Johann Bernoulli, who takes part in nine relations, and pulls in all four passages. We call this the hub flood. The candidate set now holds every passage in the corpus, and only the reranker and the final limit decide what the model reads.

The notebook's budgets sit at different stages:

Table 4: The notebook's budgets, read from its code.

These control different things. Raising the seed count can enlarge the candidate set and the reranker's prompt while the final context stays at two passages. Bound the degree, the candidate relation count and the passage count before an expensive reranker runs. When a hub connects many unrelated policies, filter by product, relation type, version and access rights before following it. Record which budget stopped the expansion, so a missing passage can be traced to a stage.

Treat identity mapping as part of retrieval correctness. The notebook's entities are raw strings from its triplets. "Euler", "Leonhard Euler" and "leonhard Euler" are three separate nodes, as are "the Bernoulli theorem" and "The Bernoulli theorem". Table 3 shows the cost: a seed that lands on the wrong spelling reaches one relation instead of ten. We call this the split identity. Normalise names and resolve aliases to stable IDs at indexing time.

The same stable IDs keep vectors and adjacency in step. An operational index needs explicit updates to both on every source change. A fresh vector record with stale adjacency retrieves the right entity and still traverses the wrong policy graph.

The code for this lesson is in these notebooks. Colab runs one in your browser: install the packages its first cell imports and set the API keys it reads. To run every notebook as written, clone the repository and use its uv environment.

• Vector search picks seed entities and relations; powers of the incidence matrix expand them. Products count walks and do not show that a relation answers the question.
• Each degree adds candidates, and a hub can pull in the whole corpus at degree 1. Bound degree, relation count and passages before the reranker, and rerank against the question.
• Resolve entity spellings to stable IDs and update vectors and adjacency together. A split identity or stale adjacency sends a correct vector hit down the wrong path.