Graph Index & Knowledge Graph Queries

Overview

A graph index stores relationships between entities as edges in a graph structure, enabling queries that traverse connections rather than matching keywords or computing vector similarity. Knowledge graph queries answer questions like “find all companies founded by people who attended Stanford and are connected to investors in the healthcare sector”—multi-hop traversals that would require expensive joins in a relational database and are impossible with inverted indexes alone.

The graph index in a search engine differs from a dedicated graph database (Neo4j, JanusGraph) in that it is tightly integrated with the text and vector indexes. A single query can combine full-text search (“find documents mentioning CRISPR”), vector similarity (“similar to this research paper”), and graph traversal (“authored by someone who co-authored with Nobel laureates”). This hybrid approach makes the search engine a unified query layer over structured relationships and unstructured content.

In a typical search engine implementation, the graph index is stored as adjacency lists in the same segment structure as inverted and vector indexes. Edges are typed (e.g., AUTHORED_BY, CITES, WORKS_AT), and each edge can carry properties. Traversal queries use a query language that specifies hop patterns, edge type filters, and direction constraints. The engine compiles these patterns into execution plans that interleave graph traversal with posting list lookups and vector distance computations.

Core Concepts

Graph Storage in Segments

Like inverted indexes, graph edges are stored per-segment. Each segment contains its own forward and reverse adjacency lists. During segment merges, adjacency lists for the same node are concatenated and re-sorted. Deletions are handled lazily: deleted nodes are marked in a bitset, and their edges are filtered out during traversal. Actual removal happens during compaction.

Property Graphs vs. RDF

The graph index follows the property graph model where both nodes and edges can have arbitrary key-value properties. This differs from RDF (Resource Description Framework), which models everything as (subject, predicate, object) triples. Property graphs are more natural for application data, while RDF is better for linked data and ontology reasoning. Many search and database systems use property graphs because they map directly to the document model already used for text and vector data.

How It Works

Edge Storage Format

Edges are serialized into a compact binary format within each segment. The forward index maps (source_node_id, edge_type) → [target_node_ids] and the reverse index maps (target_node_id, edge_type) → [source_node_ids]. Both are stored as sorted arrays for cache-friendly sequential access during traversal:

// Zig: Graph edge storage and lookup
const std = @import("std");
const Allocator = std.mem.Allocator;

const EdgeType = enum(u16) {
    authored_by,
    cites,
    works_at,
    invested_by,
    related_to,
    _,
};

const Edge = struct {
    target: u32,
    edge_type: EdgeType,
    properties: ?[]const u8, // msgpack-encoded properties
};

const AdjacencyIndex = struct {
    // Sorted by (source_id, edge_type, target_id)
    offsets: []u64,    // offsets[node_id] = start position in edges array
    lengths: []u32,    // lengths[node_id] = number of edges from this node
    edges: []Edge,

    /// Get all outgoing edges of a specific type from a node.
    pub fn getEdges(self: *const AdjacencyIndex, node_id: u32, edge_type: EdgeType) []const Edge {
        if (node_id >= self.offsets.len) return &.{};
        const start = self.offsets[node_id];
        const len = self.lengths[node_id];
        const all_edges = self.edges[start .. start + len];

        // Binary search for the first edge of the requested type
        var lo: usize = 0;
        var hi: usize = all_edges.len;
        while (lo < hi) {
            const mid = lo + (hi - lo) / 2;
            if (@intFromEnum(all_edges[mid].edge_type) < @intFromEnum(edge_type)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        // Collect contiguous edges of the same type
        var end = lo;
        while (end < all_edges.len and all_edges[end].edge_type == edge_type) {
            end += 1;
        }
        return all_edges[lo..end];
    }
};

BFS Traversal Engine

The traversal engine executes multi-hop queries by expanding the frontier one hop at a time. At each level, it reads the adjacency lists for all nodes in the current frontier, filters edges by type and direction, and collects the next frontier. A visited set prevents cycles:

// Go: BFS traversal engine for graph queries
package graph

// TraversalStep defines one hop in a multi-hop query.
type TraversalStep struct {
    EdgeType  string
    Direction string // "out", "in", or "both"
    Filter    func(nodeID uint32) bool // optional node filter
    MaxNodes  int    // limit frontier expansion
}

// BFSTraversal executes a multi-hop BFS from seed nodes.
func BFSTraversal(
    index *GraphIndex,
    seeds []uint32,
    steps []TraversalStep,
) [][]uint32 {
    // results[i] = nodes reached after step i
    results := make([][]uint32, len(steps))
    frontier := make(map[uint32]bool, len(seeds))
    visited := make(map[uint32]bool, len(seeds)*10)

    for _, seed := range seeds {
        frontier[seed] = true
        visited[seed] = true
    }

    for i, step := range steps {
        nextFrontier := make(map[uint32]bool)

        for nodeID := range frontier {
            var neighbors []uint32

            switch step.Direction {
            case "out":
                neighbors = index.Forward.GetTargets(nodeID, step.EdgeType)
            case "in":
                neighbors = index.Reverse.GetTargets(nodeID, step.EdgeType)
            case "both":
                neighbors = append(
                    index.Forward.GetTargets(nodeID, step.EdgeType),
                    index.Reverse.GetTargets(nodeID, step.EdgeType)...,
                )
            }

            for _, neighbor := range neighbors {
                if visited[neighbor] {
                    continue
                }
                if step.Filter != nil && !step.Filter(neighbor) {
                    continue
                }
                visited[neighbor] = true
                nextFrontier[neighbor] = true

                if step.MaxNodes > 0 && len(nextFrontier) >= step.MaxNodes {
                    break
                }
            }
        }

        frontier = nextFrontier
        results[i] = make([]uint32, 0, len(nextFrontier))
        for nodeID := range nextFrontier {
            results[i] = append(results[i], nodeID)
        }
    }
    return results
}

Pattern Matching Compilation

Complex graph patterns are compiled into a query plan before execution. The compiler analyzes the pattern to determine the optimal traversal order, pushing down filters to minimize the frontier size at each hop:

// Go: Pattern matching query compilation
package graph

// Pattern represents a parsed graph query pattern.
type Pattern struct {
    Nodes []NodePattern
    Edges []EdgePattern
}

type NodePattern struct {
    Alias      string
    Labels     []string
    Properties map[string]interface{}
}

type EdgePattern struct {
    FromAlias string
    ToAlias   string
    Type      string
    Direction string
    MinHops   int // for variable-length paths
    MaxHops   int
}

// QueryPlan is the compiled execution plan.
type QueryPlan struct {
    Steps []PlanStep
}

type PlanStep struct {
    Type       string // "scan", "traverse", "filter", "intersect"
    NodeAlias  string
    EdgeType   string
    Direction  string
    Filters    []Filter
    UsesIndex  bool   // true if an inverted/vector index narrows the scan
}

// Compile converts a pattern into an optimized query plan.
func Compile(p *Pattern, stats *IndexStats) *QueryPlan {
    plan := &QueryPlan{}

    // Start from the most selective node (smallest estimated cardinality)
    startNode := selectMostSelective(p.Nodes, stats)

    // If the start node has text/vector constraints, use those indexes first
    if hasTextFilter(startNode) {
        plan.Steps = append(plan.Steps, PlanStep{
            Type:      "scan",
            NodeAlias: startNode.Alias,
            UsesIndex: true,
            Filters:   buildFilters(startNode),
        })
    }

    // Add traversal steps in optimal order
    for _, edge := range orderEdgesFrom(startNode.Alias, p.Edges) {
        plan.Steps = append(plan.Steps, PlanStep{
            Type:      "traverse",
            NodeAlias: edge.ToAlias,
            EdgeType:  edge.Type,
            Direction: edge.Direction,
            Filters:   buildNodeFilters(findNode(p.Nodes, edge.ToAlias)),
        })
    }
    return plan
}

Practical Applications

Citation Network Traversal Example

As an example, a search engine might index academic papers with CITES edges. A query like “find papers similar to this one that are cited by at least 3 papers published after 2023” starts with a vector similarity search, then traverses the reverse citation graph, then applies a date filter. This hybrid query returns recent, high-impact papers in a specific research neighborhood—a task that requires three index types working together.

Entity Relationship Exploration

Graph indexes enable exploratory queries in knowledge management systems. Starting from a person entity, the UI shows connected companies (via WORKS_AT), co-authors (via CO_AUTHORED), and topics (via EXPERT_IN). Each traversal result links to full documents that can be searched with text queries, creating a graph-powered navigation layer over the document corpus.

Recommendation via Graph Proximity

Graph-based recommendations use multi-hop traversal to find items connected to the user’s interests. A user who viewed documents A and B can receive recommendations by traversing A -[SIMILAR_TO]-> C and B -[CITES]-> D, scoring candidates by the number and type of paths that connect them to the user’s history. This collaborative filtering via graph structure complements content-based vector similarity.

Access Control via Graph Paths

In multi-tenant search systems, access control can be modeled as graph reachability: a user can access a document if there exists a path (user)-[MEMBER_OF]->(group)-[HAS_ACCESS]->(document). The graph index resolves these permission checks during query evaluation, filtering results to only those reachable from the querying user through the permission graph.

Implementation Patterns

Bidirectional Search for Shortest Paths

Finding the shortest path between two nodes is faster with bidirectional BFS: expand from both the source and target simultaneously, meeting in the middle. For a graph with branching factor b and shortest path length d, unidirectional BFS explores O(b^d) nodes while bidirectional explores O(2 * b^(d/2))—exponentially less for large d.

Edge Caching for Hot Nodes

In real-world graphs, a few hub nodes (popular authors, major companies) have thousands of edges. Caching the adjacency lists of these hot nodes in memory avoids repeated disk reads. An LRU cache keyed by (node_id, edge_type) with a size proportional to the working set provides the best hit rate:

package graph

import (
    "container/list"
    "sync"
)

// EdgeCache is an LRU cache for adjacency lists of hot nodes.
type EdgeCache struct {
    mu       sync.RWMutex
    capacity int
    items    map[cacheKey]*list.Element
    order    *list.List
}

type cacheKey struct {
    NodeID   uint32
    EdgeType string
}

type cacheEntry struct {
    key     cacheKey
    targets []uint32
}

func NewEdgeCache(capacity int) *EdgeCache {
    return &EdgeCache{
        capacity: capacity,
        items:    make(map[cacheKey]*list.Element, capacity),
        order:    list.New(),
    }
}

func (c *EdgeCache) Get(nodeID uint32, edgeType string) ([]uint32, bool) {
    c.mu.RLock()
    defer c.mu.RUnlock()
    key := cacheKey{nodeID, edgeType}
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*cacheEntry).targets, true
    }
    return nil, false
}

func (c *EdgeCache) Put(nodeID uint32, edgeType string, targets []uint32) {
    c.mu.Lock()
    defer c.mu.Unlock()
    key := cacheKey{nodeID, edgeType}
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        elem.Value.(*cacheEntry).targets = targets
        return
    }
    if c.order.Len() >= c.capacity {
        oldest := c.order.Back()
        c.order.Remove(oldest)
        delete(c.items, oldest.Value.(*cacheEntry).key)
    }
    entry := &cacheEntry{key: key, targets: targets}
    elem := c.order.PushFront(entry)
    c.items[key] = elem
}

Bloom Filter Pre-check for Edge Existence

Before traversing the adjacency list, a Bloom filter indexed by (node_id, edge_type) can quickly determine if a node has any edges of the requested type. For sparse graphs where most nodes don’t have a particular edge type, this avoids loading adjacency data from disk. The Bloom filter is small enough to stay in memory for the entire index.

Frontier Pruning with Score Thresholds

Multi-hop traversals can explode the frontier size. Pruning strategies include: limiting the frontier to the top-N nodes by score at each hop, applying early termination when enough final results are found, and using edge weights to prioritize high-relevance paths. These techniques trade completeness for query latency—important when the graph has millions of nodes.

Common Pitfalls

Unbounded Traversal Depth

Variable-length path queries like “find all nodes reachable within 1–10 hops” can visit the entire graph if the branching factor is high. Always set a maximum depth and frontier size limit. Without these bounds, a single query can consume all available memory and block other queries for seconds.

Missing Reverse Index

If you only build the forward adjacency index, backward traversals (finding incoming edges) require scanning all edges in the graph. This turns O(degree) lookups into O(|E|) scans. Always maintain both forward and reverse indexes unless you are certain that backward traversal is never needed.

Stale Edges After Document Deletion

When a document (node) is deleted from the search index, its edges remain in the adjacency lists of other nodes until the next segment merge. Traversal must check the deletion bitset for every target node to avoid returning deleted documents. Forgetting this check causes ghost results that reference non-existent documents.

Graph Queries Ignoring Segment Boundaries

Edges within a segment are self-contained, but edges that cross segment boundaries (source in segment A, target in segment B) must be resolved during merge or at query time. A common bug is treating each segment’s graph independently, which misses cross-segment edges and produces incomplete traversal results. The query engine must maintain a unified view of the graph across all segments.

Cycle Detection in Pattern Matching

Real-world knowledge graphs contain cycles (A cites B, B cites A). Without cycle detection, BFS terminates naturally (visited set), but DFS-based pattern matching can loop forever. Always maintain a per-query visited set and check it before expanding each node. For variable-length paths, the visited set must be per-path, not global, to correctly enumerate all simple (non-repeating) paths.