Graph Based Retrieval

Graph-based retrieval uses edges between documents, entities, authors, citations, topics, or permissions as retrieval evidence. It complements BM25 and dense retrieval when relationships matter more than shared words or embedding distance.

Retrieval over a graph

Represent the corpus as $G=(V,E)$. A query can seed one or more nodes, then retrieve by paths, personalized PageRank, metapaths, or neighborhood overlap. A simple score from seed set $S$ is inverse shortest-path distance:

$$s(v;S)=\underset{u\in S}{\max }\frac{1}{1+\mathrm{dist}(u,v)}.$$

For citation or web graphs, link analysis variants propagate authority through edges; for knowledge graphs, typed edges constrain which paths are meaningful.

Worked example

This snippet expands a citation-style graph two hops from a seed paper and reports candidate papers with their shared neighbours.

import networkx as nx
 
G = nx.Graph()
G.add_edges_from([
    ("paperA", "method:bm25"), ("paperA", "paperC"), ("paperC", "method:bm25"),
    ("paperC", "dataset:msmarco"), ("paperB", "method:dense"), ("paperB", "dataset:msmarco"),
    ("paperD", "method:bm25"), ("paperD", "dataset:trec"),
])
seed = "paperA"
lengths = nx.single_source_shortest_path_length(G, seed, cutoff=2)
candidates = sorted((n, d) for n, d in lengths.items() if n.startswith("paper") and n != seed)
print("two_hop_papers", candidates)
print("shared_neighbors", {n: sorted(set(G[seed]) & set(G[n])) for n, _ in candidates})

Observed output:

two_hop_papers [('paperC', 1), ('paperD', 2)]
shared_neighbors {'paperC': ['method:bm25'], 'paperD': ['method:bm25']}

paperD is not textually connected to paperA in this toy graph, but it is retrievable through the shared method:bm25 node. That is the core value of graph retrieval in literature and enterprise search.

Caveats

Graph edges are editorial claims. Citation edges can encode popularity rather than relevance; entity links can be wrong; missing edges create false negatives. Graph traversal should usually be fused with hybrid search and evaluated with task-specific ranking metrics, not trusted as a standalone authority signal.

References

• Manning, Raghavan, and Schuetze, Introduction to Information Retrieval: Link analysis
• NetworkX Documentation: Link Analysis

Nav

Section — Information Retrieval and Search

← ELK Stack Knowledge Graphs →