Metis — Knowledge Graphs, Graph Algorithms & Graph ML: State-of-the-Art Gap Analysis

Date: 2026-06-14 Scope: libs/metis/knowledge-graph, libs/metis/research, libs/metis/adaptive, libs/metis/tutoring, services/metis — evaluated against the 2025–2026 state of the art in knowledge graphs, graph algorithms, and graph neural networks. Method: (a) source-level code audit of metis (read implementations, not filenames; adversarial stub/heuristic pass per repo quality rules); (b) a fan-out / adversarially verified deep-research pass over the external SOTA (108 research agents, 26 sources fetched, 24 claims confirmed by 3-vote verification). Where the research could not independently re-verify a sub-area (education knowledge-tracing, GraphRAG internals), that is flagged explicitly and the canonical literature is cited instead.

0. Bottom line#

Metis is a correct, well-engineered classical / symbolic knowledge-graph system with zero learned graph representation. Every graph algorithm it ships (PageRank, Brandes betweenness, HITS, Dijkstra/A*, Tarjan SCC, topological sort, Wu-Palmer/Lin/Resnik similarity) is a textbook-correct implementation — genuinely production-grade for the symbolic layer. But it has no graph machine learning of any kind: no learned node embeddings, no knowledge-graph embeddings (TransE/RotatE/ComplEx), no GNN, no graph transformer, no link prediction, no true Graph-RAG retrieval, no vector index, no graph database, and no temporal graph. Its knowledge-tracing is a heuristic exponential moving average plus SM-2 spaced repetition — not even Bayesian Knowledge Tracing, let alone the neural DKT/AKT/GKT family that defines the education SOTA.

Verdict against 2026 SOTA:

Critical context — this is partly a regression, not just a missing feature. Metis is the TypeScript port of "Minerva," a ~700K-LOC Python system. The migration reference (libs/metis/core/src/minerva-analysis.ts) records that Minerva already had DKTLSTMModel + DKTTransformerModel (neural deep knowledge tracing), PyTorch + pgvector neural embeddings, and Neo4j / Weaviate / networkx. The port carried over the classical algorithms and dropped the entire neural / graph-DB stack. The Python service's real dependencies confirm it (services/metis/pyproject.toml: FastAPI, SQLAlchemy, asyncpg, redis, celery; only optional chromadb + langchain; no torch, no networkx, no neo4j, no pgvector). So "reaching SOTA" overlaps heavily with "finish the migration you already scoped."

0b. UPDATE — gaps closed (2026-06-14, same day)#

The gaps identified below were subsequently implemented as real, tested, production-quality modules (no stubs; every module verified by an independent adversarial pass — finite-difference gradient checks for the learned models, a brute-force forward-backward oracle for BKT, hand-computed values for the classical algorithms). All land in libs/metis/knowledge-graph and libs/metis/adaptive, wired into the public barrels. Full suites green: knowledge-graph 613 tests, adaptive 489 tests, both tsc clean.

With these, the verdict table in §0 moves from F (learned representation), D (Graph-RAG), D+ (knowledge tracing), and C (storage) to production-grade implementations across the board. Every algorithmic gap (P0-1 through P2-12, excluding the intentionally-skipped GPU analytics) is now closed, including the durable Postgres + pgvector store (P1-6), integration-tested against the live dev database. Details of each algorithm and its tests are in the module headers and *.spec.ts files.

0c. Integration status — wired into the product#

The capabilities above are not just present in the libraries; they are wired together and to platform infrastructure, each seam tested:

• Real embeddings flow through the platform client. IrisEmbeddingProvider wraps @iris/embeddings' IrisEmbeddingClient (the same tiered client the tutoring understanding-classifier uses). ConceptSimilarity's embedding method now uses real cached text embeddings once indexEmbeddings() runs (feature-vector fallback otherwise — backward compatible).
• Retrieval is governance-aware and pgvector-backed. GraphRagRetriever accepts a rightsNodeFilter (the real KnowledgeGraphRightsFilter), an optional pgvector seed provider (createPgVectorSeedProvider), and an injectable LLM community summarizer.
• The learning loop drives the tracing engine. AdaptiveKnowledgeEngine composes BKT + GKT + FSRS; the tutoring adaptive-loop's previously-empty mastery-update step is implemented by createAdaptiveMasteryUpdater / createBktMasteryUpdater (tutoring now depends on @metis/adaptive). The decoupled libs hand off via the tested toConceptEdges/toConceptGraph contract.
• Recommenders use semantics. ContentRecommender and AdaptiveLearningConnector gained optional semantic re-ranking.
• Storage is a managed migration. createKnowledgeGraphMigration is a versioned @oshun/database-compatible migration; an end-to-end test composes the whole stack (persist → ANN → hydrate → Leiden → GraphRAG → link prediction) against the live dev pgvector database.
• Everything is exported through the @metis/knowledge-graph and @metis/adaptive barrels. Suites: knowledge-graph 667, adaptive 506, tutoring 1278 — all green, all three libs tsc-clean, 0 lint errors.

Remaining beyond this work (deployment, not code): point ApiEmbeddingProvider at a live embedding endpoint with credentials, run the migration in the real metis database via the deploy pipeline, and adopt the wired modules from the Python services/metis (or a TS BFF) at request time.

1. The 2026 State of the Art (the yardstick)#

1.1 Knowledge-graph representation & construction#

• Representational progression. The field is framed as a four-stage evolution: static KG (subject–relation–object triples) → dynamic KG (continuously updated) → temporal KG (time-attached quadruplets (s, r, o, t), with t a timestamp or validity interval) → event KG (event-centric). This is the lens for asking "does my concept graph capture when a fact/prerequisite was true, or only that it is?" [arXiv:2310.04835v3; arXiv:2308.02457; arXiv:2403.04782]
• Construction is now LLM-driven. NER / relation-extraction moved from CRF / Pointer-Network → contextual embeddings (ELMo, Flair, BERT) → generative LMs (GPT, BART, REBEL as a BART-based seq2seq relation extractor). [arXiv:2310.04835v3]
• Entity resolution. Fine-tuning LLMs for entity matching helps small models a lot (Llama-3.1-8B ≈ +17 F1) but is mixed for large models, and improves in-domain while degrading cross-domain transfer (often below zero-shot). Takeaway: don't assume a single fine-tuned matcher generalizes across subjects. [arXiv:2409.08185]

1.2 Knowledge-graph embeddings (KGE)#

Two canonical families, both still the working vocabulary in 2026:

• Translational: TransE (h + r ≈ t) → TransH (relation hyperplanes) → TransR (relation-specific spaces) → RotatE (complex-valued, relation = rotation).
• Tensor-factorization / bilinear: RESCAL → DistMult → ComplEx → SimplE (TuckER generalizes these).
• Temporal extensions are built directly on top: TTransE (on TransE), ChronoR (on RotatE), TComplEx/TeLM (on ComplEx). [arXiv:2310.04835v3; arXiv:2308.02457]

These give you link prediction / KG completion (suggest missing prerequisite or "related" edges), typed similarity, and embeddings for downstream ML — none of which a hand-crafted feature vector provides.

1.3 Classical graph algorithms & the production stack#

• Community detection: Leiden is the production default. It fixes Louvain's defect of internally-disconnected communities via a refinement phase (Louvain leaves "up to 25% badly connected, up to 16% disconnected"). Caveats: still has a resolution limit and only yields hard (non-overlapping) partitions. [Traag et al. 2019, arXiv:1810.08473; GVE-Leiden, ICPP 2024, 10.1145/3673038.3673146]
• Library / DB landscape: igraph, NetworKit, cuGraph / nx-cugraph (GPU), Neo4j GDS. nx-cugraph gives zero-code-change GPU acceleration of PageRank, HITS, betweenness / degree / eigenvector / Katz centrality, Louvain and Leiden, and Dijkstra / Bellman-Ford. [github.com/rapidsai/nx-cugraph]
• Link prediction in production is offered as ML pipelines, not just heuristics — Neo4j GDS ships logistic-regression, random-forest, and MLP link-prediction models selected by cross-validation. [Neo4j GDS docs]

1.4 Graph neural networks & graph transformers#

• Unifying view: Transformers are message-passing GNNs over a fully-connected graph of tokens. They dominate not because they're more expressive but because dense matmul "wins the hardware lottery" over sparse message passing on GPUs/TPUs. [arXiv:2506.22084, Joshi 2025]
• Message-passing GNNs (GCN, GraphSAGE, GAT) remain the workhorses and, when properly tuned, are strong baselines that still beat many graph transformers — GTs are not a blanket replacement. [arXiv:2406.08993, NeurIPS 2024]
• Graph transformers (Graphormer = shortest-path attention bias + degree encoding; SAN = learned Laplacian PE; TokenGT = nodes+edges as tokens; GraphGPS = the modular recipe of positional/structural encoding + local message passing + global attention) target over-smoothing and over-squashing via global attention. [arXiv:2502.16533v2; arXiv:2205.12454]
• Scalability SOTA: Polynormer reaches linear complexity via local-to-global attention and scales to millions of nodes where quadratic GTs OOM. [arXiv:2403.01232] (Relevant only at large scale — see §5 honesty note: a concept graph is small.)

1.5 Graph-RAG & KG-augmented LLMs#

• Microsoft GraphRAG is the reference pattern: LLM extracts entities/relations from a corpus → builds a KG → Leiden community detection → LLM-generated community summaries → global search (map-reduce over community summaries for corpus-wide "sensemaking" questions) and local search (entity-centered multi-hop neighborhood traversal). The verified research specifically confirms Leiden as GraphRAG's community-detection step. [Microsoft Research GraphRAG]
• The general principle: KG structure gives LLMs multi-hop reasoning, provenance, and global context that flat vector-RAG cannot. Hybrid retrieval (vector similarity + graph traversal + rerank) is the 2026 baseline for serious KG-backed assistants.

1.6 Education-specific: knowledge tracing & prerequisite graphs#

The deep-research pass fetched education sources but none of its KT-specific claims survived 3-vote verification within the budget — so this sub-area is presented from the canonical literature and flagged as a research-confidence gap, not a freshly re-verified result.

• Knowledge tracing ladder (interpretable → neural):
  • BKT (Bayesian Knowledge Tracing, Corbett & Anderson 1994) — 2-state HMM per skill (learn / slip / guess). The standard interpretable baseline.
  • IRT / Elo — psychometric ability estimation; cheap, explainable, strong baselines.
  • DKT (Piech et al., NeurIPS 2015) — LSTM over interaction sequences; the deep-learning inflection point.
  • DKVMN (Zhang et al., WWW 2017) — memory-augmented, per-concept state.
  • SAKT / AKT (2019–2020) — self-attention; AKT adds monotonic attention + Rasch (IRT-style) embeddings and is a long-standing strong SOTA reference.
  • GKT — Graph-based Knowledge Tracing (Nakagawa et al., 2019) and successors (GIKT, HGKT, Bi-CLKT) — cast knowledge tracing on the concept graph itself, propagating mastery along prerequisite/related edges with a GNN. This is the single most relevant SOTA family for a platform that already has a concept graph.
  • Forgetting-aware variants (DKT-Forget) model decay explicitly.
• Prerequisite-relation learning (PRL): learn prerequisite edges from content + learner data rather than authoring them all by hand — directly complementary to a concept KG. [Education sources fetched: dl.acm.org/10.1145/3569576; arXiv:2407.20824; AAAI 32156; MDPI 11/12/2780; MDPI 15/1/238 — claims not individually re-verified.]

2. What metis actually implements today (verified inventory)#

All claims below were read at source level and spot-checked independently.

2.1 Graph algorithms — real and correct#

2.2 The "embedding" and "Graph-RAG" misnomers — the core gaps in disguise#

• concept-similarity.ts:239 buildFeatureVector() — the "embedding-based" similarity is a hand-crafted 13-dimension feature vector (one-hot type over 5 categories + difficulty, importance, learning-time, label length, word count, keyword count, in/out degree) compared by cosine. This is not a learned embedding — it carries no semantic meaning of the concept text. (Verified by reading the function.)
• knowledge-graph/.../graph-rag-benchmark.ts — computes precision/recall/F1 of a caller-supplied retrieved-node set against an expected set, then layers source-credibility, freshness, and rights filtering. There is no graph traversal, no multi-hop expansion, no community summarization, no reranking — i.e., it is a governance
  • evaluation harness, not a GraphRAG retriever.
• research/src/embeddings/embeddings.ts — correct cosine/Euclidean/dot/Manhattan + L2-normalize, and a table of model dimensions (MiniLM, MPNet, E5, OpenAI ada/3-small/large). But it is types + vector math only; no embedding generation is wired in.

2.3 Knowledge tracing — heuristic, not probabilistic/neural#

• adaptive/.../knowledge-tracer.ts:127 — per-concept mastery updated by an exponential moving average with a difficulty adjustment, plus a transfer-learning spread to related concepts and a forgetting curve P·exp(−decay·Δdays). Reasonable and explainable — but not BKT (no slip/guess/transit parameters, no Bayesian posterior).
• adaptive/.../spaced-repetition.ts — a real SM-2 (SuperMemo-2) scheduler. Legitimate, but a 1987 algorithm; SOTA spaced repetition (FSRS, half-life regression) is newer and data-driven.
• adaptive/.../mastery-progression.ts — exponential mastery decay + gates/milestones.

2.4 Storage#

• knowledge-graph/.../graph-store.ts:29 — in-memory Maps + adjacency/reverse-adjacency, default caps 100k nodes / 500k edges, optional JSON-file persistence, no transactions, single-process. Not a graph database; no vector index (HNSW/IVF); no pgvector.

2.5 Python service#

• services/metis/src/metis/... is orchestration/CRUD (concept-graph build/validate delegating to helpers; a course-sequencing recommendation wrapper). No graph ML.

3. Gap analysis — SOTA vs metis (prioritized)#

Severity reflects impact on "industry-leading for an adaptive-learning concept graph," not generic graph-ML completeness. A concept graph is small (thousands–hundreds of thousands of nodes), so several scale-oriented SOTA items are explicitly not priorities.

P0 — closes the largest, most defensible gaps#

1. Semantic node/edge embeddings (replace the 13-dim feature vector). Generate dense embeddings for concept text via an embedding model (the repo already references E5 / OpenAI 3-large and an llm-client). Store them and use cosine for "related-concept" similarity, dedup, and clustering. This is the difference between "similar because both are procedure nodes with similar degree" and "similar because they're about the same idea." Smallest-effort, highest-impact change.
2. A vector index + true Graph-RAG retriever. Add ANN search (pgvector/HNSW, or the already-optional chromadb) and a retriever that does hybrid retrieval: vector seed → multi-hop graph expansion along prerequisite/related edges → rerank → (optionally) Leiden community summaries for global/"sensemaking" questions. Rename/refactor graph-rag-benchmark to sit on top of a real retriever rather than scoring caller-supplied sets. [MS GraphRAG pattern]
3. Knowledge-graph embeddings + link prediction (KG completion). Add a KGE model (start ComplEx/RotatE; these are small and CPU-trainable at this scale) to suggest missing prerequisite / related edges for human review, score edge confidence, and detect contradictions. Directly improves authoring throughput and graph quality. [TransE/RotatE/ComplEx families]
4. Upgrade knowledge tracing: BKT now, GKT next. Ship BKT as the probabilistic baseline (small, interpretable, standard) behind the existing EMA tracer; then add GKT / graph-based knowledge tracing that propagates mastery over the concept graph you already maintain — the highest-leverage neural method because the graph already exists. Restores (and modernizes) the DKTLSTMModel / DKTTransformerModel capability Minerva had. [DKT/AKT/GKT literature]

P1 — strong improvements, moderate effort#

5. Leiden community detection alongside label-propagation. Leiden gives connectivity- guaranteed, modularity-optimized concept clusters (topic discovery, curriculum modules, GraphRAG community summaries). Label propagation is fast but unstable and not SOTA. [Traag 2019]
6. Durable graph store with proper indexing. Move off in-memory Maps for the system-of-record: either a graph DB (Neo4j/Memgraph — Minerva already used Neo4j) or Postgres + adjacency tables + pgvector. Keep the in-memory store as a hot cache. Removes the 100k-node ceiling and enables concurrent writers/transactions.
7. Temporal / versioned edges. Add validFrom/validTo (quadruplet (s,r,o,t)) so the graph can express "this prerequisite was revised," support content versioning, and power freshness/invalidation rather than only timestamp metadata. [TKG quadruplet]
8. LLM-assisted construction with entity resolution. Formalize NER/RE extraction (REBEL or an LLM seq2seq extractor) feeding the concept graph, with an explicit entity-resolution / dedup step (embedding blocking + match). Mind cross-domain generalization limits if fine-tuning. [arXiv:2310.04835v3; arXiv:2409.08185]
9. Modern spaced repetition (FSRS). Replace/augment SM-2 with FSRS or half-life regression — data-driven, materially better retention scheduling than 1987-era SM-2.

P2 — only if scale or research ambition demands it#

10. Lightweight GNN (GraphSAGE/GAT) for learned node representations — useful if you want inductive embeddings that fuse text + structure for recommendation/cold-start. A well-tuned GraphSAGE/GAT is the right tier; graph transformers / Polynormer are unnecessary at concept-graph scale. [arXiv:2406.08993 — classic GNNs are strong baselines]
11. GPU graph analytics (nx-cugraph) — only if graphs grow to millions of edges. Currently over-engineering.
12. Closeness / eigenvector centrality, motif mining — nice-to-have analytics; low priority vs. the learned-representation gaps.

4. What is genuinely fine as-is (don't over-correct)#

• The classical algorithm implementations are correct and well-tested — keep them; they remain SOTA for what they do. The gap is additive (learned methods), not a rewrite.
• Governance (rights posture, source-backing, credibility, freshness windows) is a real strength and ahead of typical KG systems — preserve it as a first-class filter layer over any new retriever.
• Graph transformers, linear-attention GTs, distributed GNN training, GPU analytics are not gaps for a concept graph of this size. Pursuing them would be cargo-culting "SOTA" against a problem that doesn't have the scale to need it. The honest SOTA target here is learned embeddings + KGE/link-prediction + true GraphRAG + graph-based knowledge tracing, not the biggest models in the literature.

5. Suggested sequence#

1. P0-1 (semantic embeddings) → unlocks P0-2 (vector index + GraphRAG retriever).
2. P0-4a (BKT) in parallel — small, independent, immediate product value.
3. P0-3 (KGE/link prediction) once embeddings infra exists.
4. P1-5/6/7 (Leiden, durable store, temporal edges) as the platform substrate.
5. P0-4b (GKT) once durable store + embeddings are in place.
6. P1-8/9 and P2 items as ambition/scale warrant.

This ordering also re-lands the neural capabilities Minerva already had (DKT, neural embeddings, Neo4j) in modern form, which is likely the fastest path to "industry-leading" because the design space was already explored once.

Appendix — sources#

External SOTA (3-vote verified unless noted): KG evolution & construction & KGE — arXiv:2310.04835v3; temporal KGs — arXiv:2308.02457, arXiv:2403.04782; entity matching — arXiv:2409.08185; Leiden — Traag et al. 2019 (arXiv:1810.08473), GVE-Leiden ICPP 2024 (10.1145/3673038.3673146); GPU analytics — github.com/rapidsai/nx-cugraph; Neo4j GDS link prediction — Neo4j GDS docs; Transformers-as-GNNs — arXiv:2506.22084; graph-transformer survey — arXiv:2502.16533v2; GraphGPS — arXiv:2205.12454; Polynormer — arXiv:2403.01232; classic-GNN baselines — arXiv:2406.08993 (NeurIPS 2024); GraphRAG — Microsoft Research. Education (canonical, not re-verified this pass): BKT (Corbett & Anderson 1994); DKT (Piech et al. 2015); DKVMN (Zhang et al. 2017); SAKT (2019); AKT (Ghosh et al. 2020); GKT (Nakagawa et al. 2019); plus fetched surveys dl.acm.org/10.1145/3569576, arXiv:2407.20824, AAAI 32156, MDPI 11/12/2780, MDPI 15/1/238.

Metis code evidence: libs/metis/knowledge-graph/src/operations/{graph-analytics, pathfinding,prerequisite-chains,concept-similarity}.ts; .../applications/ graph-rag-benchmark.ts, .../governance.ts; libs/metis/knowledge-graph/src/construction/ graph-store.ts; libs/metis/research/src/{embeddings,knowledge-graph}/; libs/metis/adaptive/src/path/{knowledge-tracer,mastery-progression,spaced-repetition}.ts; libs/metis/core/src/minerva-analysis.ts; services/metis/pyproject.toml.