Can knowledge graph structure help embeddings represent more combinations?

This explores whether graph structure can get around a hard mathematical limit on what embedding vectors can represent. The corpus has a sharp answer to the premise behind your question: embeddings really do hit a combinatorial ceiling. Do embedding dimensions fundamentally limit retrievable document combinations? uses communication-complexity theory to prove that for any embedding dimension d, there's a maximum number of top-k document combinations a vector search can ever surface — and this holds even for embeddings trained directly on the test data, on trivially simple tasks. So the limit isn't a tuning problem you can train away by adding data; it's baked into the geometry of packing relationships into a fixed-length vector.

Graph structure helps precisely because it stops trying to pack combinations into a single point in vector space and instead makes them explicit as edges and paths. Can knowledge graphs enable multi-hop reasoning in one retrieval step? (HippoRAG) is the clearest demonstration: by converting a corpus into a knowledge graph and walking it with Personalized PageRank, it assembles multi-hop combinations of facts in a single retrieval step — matching iterative methods at a fraction of the cost — combinations that a flat embedding search struggles to return together. Can multimodal knowledge graphs answer questions that flat retrieval cannot? makes the same point from the failure side: hierarchical graphs answer cross-chapter, global questions that flat chunk retrieval simply cannot reach, because the answer lives in the connections, not in any single chunk's embedding.

The most direct response to your literal wording — representing *more* combinations — comes from Can hypergraphs capture multi-hop reasoning better than graphs?. Ordinary graphs only encode pairwise links, but hypergraph edges let three or more entities bind into a single relation without breaking it apart. That's a richer combinatorial vocabulary than either embeddings or plain graphs offer, bought at the price of more representational complexity. So there's a spectrum here: embeddings (cheapest, hardest ceiling) → pairwise graphs → hypergraphs (most expressive joint constraints).

There's a deeper reframing worth noticing. Several notes argue the win isn't "more combinations" but *the right structure for the question*. Can routing queries to task-matched structures improve RAG reasoning? (StructRAG) routes each query to whichever structure fits — table, graph, algorithm, catalogue, or plain chunks — borrowing cognitive-fit theory from psychology, and beats uniform retrieval. Can symbolic rules from knowledge graphs guide complex reasoning? shows that rules read off a graph's topology can guide reasoning that pure semantic similarity misses. And Can organizing knowledge structures beat raw training data volume? reaches 50% of full-corpus performance on 0.3% of the data by organizing chunks into a taxonomy — structure substituting for volume, the same way a student learns position-in-a-field from a textbook rather than memorizing pages.

The thing you may not have known you wanted to know: the relationship between structure and embeddings isn't that graphs simply "add more" to vectors. Why do reasoning systems keep discovering new connections? finds that iterative graph reasoning settles into a critical state where roughly 12% of edges stay *semantically surprising* even after being structurally connected — meaning the structure keeps generating combinations that the embeddings, on their own, would never have placed near each other. That's the real answer to your question: structure doesn't expand the embedding's representational budget, it routes around it entirely.