Graph-Based Code Analysis: State of the Art Research (2024-2026)

Graph-Based Code Analysis: State of the Art Research (2024-2026)

Purpose: Research synthesis to inform GraFOSa improvements. Maps latest academic and industry advances to specific GraFOSa capabilities.

Date: 2026-03-02

Companion: GRAFOSA-IMPROVEMENT-ROADMAP.md (Sprint 1-5 already planned)

Executive Summary

Three parallel research sweeps covering 30 topic areas identified 6 breakthrough techniques directly applicable to GraFOSa, plus 12 emerging approaches worth tracking. The research strongly validates GraFOSa's existing architecture (8-layer graph kernel, PageRank, Tarjan SCC) and identifies the biggest gaps as: (1) no LLM-graph fusion, (2) no incremental analysis, (3) no semantic embeddings, and (4) no temporal/evolution tracking.

Top 6 Actionable Findings

1. Code Property Graphs: The Convergence Point

What's Changed (2024-2026)

The CPG (Code Property Graph = AST + CFG + PDG merged) has become the standard representation across all major tools:

QVoG (arXiv 2024) — Compresses CPGs by storing code at statement level rather than individual AST nodes. A typical graph shrinks from ~100 nodes/460 edges to 10 nodes/15 edges. Uses a declarative SQL-like DSL translated to Gremlin queries (16.3 lines avg vs CodeQL's 86.3). Achieves 90% precision / 95% recall on Juliet benchmarks.

LLMxCPG (USENIX Security 2025) — Two-phase pipeline: (1) LLM generates targeted CPG queries to extract minimal vulnerability-relevant code "slices" (67-91% volume reduction), (2) second LLM classifies the slice. 15-40% F1 improvement over baselines. Open source: github.com/qcri/llmxcpg.

Fraunhofer AISEC CPG Library (v9.0.2, 2025) — Language-agnostic CPG library supporting C/C++, Java, Go, Python, TypeScript, Ruby. Architecture: pluggable Language Frontends + refinement Passes — clean separation model.

CodeQL Incremental Analysis (2025) — Now supports incremental security analysis across all languages. PR scans 20-40% faster. Database format 2-3x more compact.

What This Means for GraFOSa

GraFOSa's 8-layer kernel IS essentially a CPG variant. The key improvements:

1. QVoG's compression — GraFOSa should adopt statement-level nodes for algorithm layers (PageRank, SCC, topological sort) while keeping full AST for display. This directly addresses the scale concern in the roadmap.

2. LLMxCPG for Sprint 4 — Instead of building full behavioral flow analysis from scratch, use LLM-guided CPG slicing to extract the specific code paths relevant to feedback loops. This could reduce the 6-8 week Sprint 4 effort by providing a "good enough" first pass.

3. Fraunhofer's Frontend+Pass pattern — Model for adding new language support (roadmap items 2.2, 3.1). Each language = one frontend, analysis passes are language-agnostic.

2. Incremental Analysis: The Non-Negotiable Gap

What's Changed

Full re-analysis on every change is increasingly recognized as untenable. Three production-ready approaches exist:

Stack Graphs (GitHub, production since 2024) — Creates isolated subgraphs per source file for incremental name resolution. Now powers precise code navigation for Python and TypeScript on GitHub.com. OpenHands, Aider, and SWE-agent all have open issues exploring adoption. github/stack-graphs.

Tree-sitter (v0.25, production) — Incremental AST parsing. File edits trigger localized tree updates, not full re-parse. 36x faster than JavaParser in benchmarks.

PMD Incremental Analysis (production) — Caches per-file results, only re-analyzes changed files. Proven pattern for static analysis tools.

Ingress/IncBoost (VLDB/SoCC 2024) — Automated incrementalization of graph algorithms. Handles edge deletions and weight updates efficiently.

What This Means for GraFOSa

GraFOSa currently rebuilds its entire graph on every scan. Adding incremental analysis should be Sprint 6, Task 1:

1. Tree-sitter for parsing layer — Already in the roadmap (Sprint 3). This is the foundation.
2. Stack Graphs for name resolution — NEW recommendation. Replaces the current full-graph import chain traversal with file-incremental name binding. Directly fixes the "rebuild everything" problem.
3. Delta graph computation — On each git commit, re-parse only changed files, update affected edges, propagate changes through graph. Cache invalidation boundary = the transitive closure of changed nodes.

Estimated impact: 10-100x speedup for incremental scans after initial full build.

3. GNN + LLM Fusion: The Research Frontier

What's Changed

The most active research area. Three distinct integration patterns have emerged:

Pattern A: Graph-to-LLM (enrichment)

• GALLa (ACL 2025) — Injects graph structure into LLMs during fine-tuning via GNN + adapter. Graph data needed only at training time, zero inference overhead. codefuse-ai/GALLa.
• TAPE (ICLR 2024) — LLM generates text representations for graph nodes, smaller model produces embeddings for GNN input. 2.88x speedup.

Pattern B: LLM-to-Graph (query)

• CodexGraph (NAACL 2025) — LLM translates natural language to graph database queries (Cypher/GSQL). 22.96% Pass@1 on SWE-bench Lite. arxiv.org/abs/2408.03910.
• CGM (Code Graph Model) (NeurIPS 2025) — Bakes graph structure into LLM attention mask. 43.00% on SWE-bench Lite (first among open-weight models).

Pattern C: Hybrid (bidirectional)

• GraphCodeAgent (2025) — Dual-graph (Requirement Graph + Structural-Semantic Code Graph) with ReAct-style agent loop. 43.81% improvement on DevEval.
• RANGER (Sept 2025) — MCTS-guided graph exploration with bi-encoder/cross-encoder scoring.

Pattern D: Multi-graph fusion

• MAGNET (2025) — Cross-attention between AST, CFG, and DFG representations. 96.5% F1 for clone detection.
• Dual-branch GNN (Scientific Reports 2025) — Shared graph encoder + task-specific branches for defect prediction and quality assessment simultaneously.

What This Means for GraFOSa

GraFOSa currently has zero LLM integration. The roadmap's "What NOT to Build" correctly says "don't embed an LLM — keep GraFOSa as the data layer." However, the research shows LLM-as-query-translator (Pattern B) is different from embedding an LLM:

1. CodexGraph pattern for MCP tools — GraFOSa already has 46 MCP tools. Adding a natural language query translator that generates Cypher/graph queries would let users ask "what depends on the authentication module?" instead of calling specific tools. This is an MCP tool enhancement, not an embedded LLM.

2. TAPE-style node enrichment — Use LLM calls to generate semantic descriptions for top PageRank nodes. Store as node attributes. This makes PageRank results interpretable without changing the algorithm.

3. MAGNET cross-attention — Validates GraFOSa's multi-layer approach but is 4-6 weeks of GNN infrastructure work. Watch, don't build yet.

4. GraphRAG for Code: The New Paradigm

What's Changed

Retrieval-Augmented Generation over graphs has matured from research to production in 18 months:

Microsoft GraphRAG (production) — Entity-relationship graphs + Leiden community detection + hierarchical summaries. Local (entity-focused) and global (theme-level) retrieval.

LazyGraphRAG (Microsoft, late 2024) — 1000x cheaper indexing, 700x cheaper global queries. Combines best-first and breadth-first search. Production deployment in Azure.

LightRAG (EMNLP 2025) — 10x token reduction via dual-level retrieval (entity + relationship). Supports incremental updates. HKUDS/LightRAG.

E2GraphRAG (May 2025) — 10x faster indexing than GraphRAG, 100x retrieval speedup over LightRAG.

What This Means for GraFOSa

GraFOSa's graph kernel is the perfect input for GraphRAG. The integration path:

1. LightRAG overlay (1 week) — Export GraFOSa's entity-relationship data, feed into LightRAG. Instantly enables natural language queries over the codebase graph: "What would break if we removed the SmartRouter?" → traverses dependencies, gathers context, synthesizes answer.

2. LazyGraphRAG for global queries — "What are the top 5 architectural risks in this codebase?" → community-level summaries from GraFOSa's graph. 700x cheaper than full GraphRAG.

3. NOT recommended: Full GraphRAG — Too expensive for large codebases without LazyGraphRAG optimization. GraFOSa's graph already has structure; GraphRAG's entity extraction step is redundant.

5. Dead Code Detection: Beyond Reachability

What's Changed

GraFOSa's reachability-based dead code detection (endpoint → IMPORTS BFS) is ~98% accurate for files. New techniques complement it:

DePA (Dead Code Perplexity Analysis) (arXiv Feb 2025) — Computes line-level perplexity using a Code LLM, comparing each line against file distribution. 0.85 precision for locating dead code within poisoned segments (vs 0.31-0.41 for ONION baselines).

AUG-PDG (Scientific Reports 2025) — Extends program dependency graphs with VarEnd/ScopeEnd edges. Enables precise dead variable detection as a byproduct of vulnerability analysis. 8.34% accuracy improvement over baselines.

What This Means for GraFOSa

GraFOSa's dead file detection is already strong (~98%). The gap is dead symbols (~65% accuracy). Two complementary approaches:

1. AUG-PDG VarEnd edges — Add variable lifetime tracking to GraFOSa's data flow layer. This directly addresses the symbol-level dead code gap without requiring an LLM.

2. DePA as optional deep scan — For ambiguous cases (code that's structurally reachable but semantically dead), use LLM perplexity as a second opinion. This is an "enhance Sprint 2" addition, not a replacement.

3. Supply chain angle — DePA was designed to detect dead code poisoning (malicious injections). GraFOSa could flag suspicious dead code that looks injected vs naturally deprecated.

6. Self-Improving Analysis Systems

What's Changed

The most dramatic research advances are in systems that improve their own analysis over time:

SICA (Self-Improving Coding Agent) (ICLR 2025 Workshop) — Evaluates its own performance, identifies shortcomings, updates its own implementation. SWE-Bench Verified: 17% → 53%. Improvements came from tool orchestration heuristics, not weight updates. MaximeRobeyns/self_improving_coding_agent.

Darwin Godel Machine (Sakana AI, 2025) — Self-evolving agent that rewrites its own code via evolutionary search. SWE-bench: 20% → 50%. Transfers across LLM backends. sakana.ai/dgm.

AFlow (ICLR 2025 Oral) — Monte Carlo Tree Search over agentic workflows. Outperforms manual methods by 5.7%, automatic methods by 19.5%. Smaller models outperform GPT-4o at 4.55% of cost. FoundationAgents/AFlow.

Agent-R1 (2025) — End-to-end RL for LLM agents with process rewards for each tool call.

DSPy MIPROv2 (2024-2025) — Three-stage prompt optimizer using Bayesian optimization. Composes across pipeline stages. Production-ready.

What This Means for GraFOSa

GraFOSa's analysis rules are currently static. The research suggests two paths:

Path A: Rule self-tuning (immediate, low-risk)

• Track false positive rates per rule category (the roadmap's Sprint 5.1 time-series tracking enables this)
• Use DSPy MIPROv2 to optimize LLM prompts used in any future LLM-enhanced analysis
• Adjust severity thresholds based on historical accuracy (e.g., if dead symbol detection is 65% accurate, lower its severity weight automatically)

Path B: Full self-improvement (6-12 month horizon)

• SICA pattern: GraFOSa evaluates its own findings against developer actions (did they actually delete the flagged dead code?), then adjusts detection rules
• AFlow pattern: MCTS over analysis pipeline configurations (which layers to run, in what order, with what thresholds)
• Requires the feedback loop that Sprint 5.1 (time-series) and Sprint 5.2 (health diff) would provide

7. Temporal Knowledge Graphs for Code Evolution

What's Changed

Graphiti/Zep (open source, production) — Temporal knowledge graph framework with real-time incremental updates, bi-temporal data model (event time + ingestion time), hybrid search (semantic + BM25 + graph traversal). Outperforms MemGPT on Deep Memory Retrieval. getzep/graphiti.

EvoReasoner (2025) — Models knowledge evolution with 2-8% accuracy improvements after temporal graph updates.

What This Means for GraFOSa

The roadmap's Sprint 5 (longitudinal analysis) plans SQLite-backed health snapshots. Graphiti could replace/enhance this:

1. Bi-temporal code history — Track both when code changed (event time) and when GraFOSa detected it (ingestion time). Enables "what did the graph look like before this vulnerability was introduced?" queries.

2. Incremental graph updates — Graphiti's real-time update model means GraFOSa doesn't need to batch-process snapshots. Each commit produces a graph delta that Graphiti absorbs.

3. Evolution queries — "Show me all functions whose PageRank increased >20% in the last month" — identifies emerging bottlenecks before they become critical.

8. Vulnerability Detection with GNNs

What's Changed

MultiGLICE (March 2025) — Inter-procedural program slicing + GNNs for multiclass vulnerability detection across 38 CWE types in C/C++, C#, Java, PHP. 23% F1 improvement over baselines, 17x faster training. Configurable inter-procedural depth. Open source.

MoCQ (2025) — Neuro-symbolic approach integrating LLMs with Joern and CodeQL. Claude 3.7 Sonnet achieved best performance at 0.49 F1.

Vul-LMGNN (2024) — Fuses pre-trained code language models with CPGs. Joint training of language model and gated code GNN modules.

What This Means for GraFOSa

GraFOSa's security scanning currently uses regex patterns and can't distinguish Prisma $executeRaw (safe) from $executeRawUnsafe (unsafe). The research suggests:

1. MoCQ-style hybrid (recommended) — Use GraFOSa's existing graph as the structural component, invoke Joern/CodeQL via MCP for deep analysis, then use LLM to classify results. This fits the MCP tool architecture perfectly.

2. MultiGLICE integration — If GraFOSa adds CPG construction (AST + CFG + PDG merge), MultiGLICE can run GNN-based detection over it. Covers 38 CWE types automatically.

3. Vul-LMGNN — Research-stage but shows that combining graph structure with LLM embeddings as node features improves detection. Aligns with the TAPE/GALLa enrichment pattern.

9. Technical Debt and Anti-Pattern Detection

What's Changed

SNA for Technical Debt (PLOS ONE 2025) — First to use Social Network Analysis metrics (betweenness centrality, clustering coefficient, modularity) for TD prediction. XGBoost with combined SNA + traditional metrics: F2=0.77, recall=0.87.

Forrester: Doom Loops (2025) — Models TD propagation as a graph problem. "Doom loops" = SCCs in the dependency graph where mutual dependencies create cascading debt.

Microservice Anti-Pattern Detection via GNNs (SPE Dec 2025) — Models systems as graphs, uses GNNs to detect 4 anti-patterns. Uses LLMs to generate synthetic training data.

What This Means for GraFOSa

GraFOSa already has PageRank and Tarjan SCC. The gap is interpreting the results:

1. Betweenness centrality (immediate) — Add to existing graph algorithms. High betweenness = "debt amplifier" (everything flows through it, maintenance burden spreads). This directly improves the health scoring that Sprint 1.3 addresses.

2. Doom loop detection — GraFOSa's SCC output already identifies cycles. Flagging SCCs where nodes also have quality issues (high complexity, dead code, security smells) as "doom loops" is a labeling enhancement, not new analysis.

3. Anti-pattern GNN classifier (future) — Train on GraFOSa's existing labeled data (known anti-patterns from Conduir audit). Use the LLM-generated synthetic data approach to augment sparse training examples.

10. Code Embeddings and Semantic Search

What's Changed

Voyage-code-3 (Dec 2024) — State-of-the-art code retrieval embeddings. Outperforms OpenAI-v3-large by 13.80%. Supports Matryoshka dimensions (2048/1024/512/256) and quantized formats (int8, binary) for 4x-32x storage reduction.

DeepSeek-Coder-V2 — MoE model, 338 languages, 128K context. Self-hostable.

What This Means for GraFOSa

Code embeddings bridge structural and semantic analysis:

1. Node embedding enrichment — Generate Voyage-code-3 embeddings for every function/class. Enables semantic similarity within the graph: "find structurally unrelated but semantically similar code" (clone detection signal).

2. Dead code confidence scoring — Embed flagged dead code, compare against active code. High similarity to active code suggests a false positive (the code is a variant, not truly dead).

3. Hybrid retrieval — Combine PageRank structural scores with embedding-based semantic similarity for the MCP query tools.

11. Graph Databases: The Scale Path

What's Changed

Neo4j Infinigraph (Sept 2025) — 100TB+ scale, sharding with global index, ACID compliance. GDS plugin includes PageRank, Louvain, connected components.

Memgraph — In-memory graph database, ~100x faster than Neo4j for write-heavy traversal workloads. Cypher-compatible.

What This Means for GraFOSa

GraFOSa's in-memory graph works for current scale. If targeting enterprise codebases (100K+ files):

1. Neo4j export (recommended) — Export GraFOSa's 8-layer kernel to Neo4j. Gains: persistent queryable graph, Cypher queries, visualization, CodexGraph-style LLM query translation.

2. Memgraph for analysis workloads — If traversal-heavy operations (SCC, dead code BFS) become slow, Memgraph's in-memory model is 100x faster for those patterns.

12. Supply Chain Security via Dependency Graphs

What's Changed

GUAC (OpenSSF, production) — Ingests SBOMs, SLSA attestations, VEX statements, OSV data into unified dependency graph. guac.sh.

Maven Central study (2025) — Only 1% of releases have direct vulnerabilities, but 46.8% affected by transitive vulnerabilities. Graph propagation analysis is essential.

Logical Attack Graphs (2025) — Models real attacks (XZ compromise) as graph traversals through supply chain dependencies.

What This Means for GraFOSa

GraFOSa doesn't currently analyze supply chain dependencies. Two additions:

1. GUAC integration — Import SBOM data as a new layer in the graph kernel. Connect package nodes to code nodes via IMPORTS edges. Enables "what code uses this vulnerable dependency?" queries.

2. Transitive vulnerability propagation — Use graph traversal to compute the blast radius of any CVE through the dependency tree. Surface the 46.8% transitive exposure.

Consolidated Research-Informed Roadmap Extension

The existing GRAFOSA-IMPROVEMENT-ROADMAP.md covers Sprints 1-5. Based on this research, here are recommended additions:

Sprint 6: Incremental Analysis + Embeddings (2-3 weeks)

Sprint 7: LLM-Graph Query Layer (1-2 weeks)

Sprint 8: Enhanced Detection (2-3 weeks)

Sprint 9: Temporal + Self-Improving (3-4 weeks, research-informed)

Watch List (12-24 month horizon)

Key Research Sources

Code Property Graphs

• QVoG: Scalable Defect Detection via Traversal on Code Graph (arXiv 2024)
• LLMxCPG: Context-Aware Vulnerability Detection (USENIX Security 2025)
• Fraunhofer AISEC CPG Library (v9.0.2, GitHub)

Incremental Analysis

• Stack Graphs: Name Resolution at Scale (GitHub)
• Introducing Stack Graphs (GitHub Blog)
• CodeQL Incremental Analysis (GitHub 2025)

GNN + LLM Fusion

• GALLa: Graph Aligned LLMs (ACL 2025)
• CodexGraph: LLM Agents with Graph Databases (NAACL 2025)
• CGM: Code Graph Model (NeurIPS 2025)
• MAGNET: Multi-Graph Attentional Network (2025)
• TAPE: LLM-to-LM Graph Representation (ICLR 2024)

GraphRAG

• LazyGraphRAG (Microsoft 2024)
• LightRAG (EMNLP 2025)
• E2GraphRAG (May 2025)
• RANGER: Repository-Level Graph-Enhanced Retrieval (Sept 2025)

Dead Code + Vulnerability Detection

• DePA: Dead Code Perplexity Analysis (arXiv Feb 2025)
• Augmented PDG for Vulnerability Detection (Scientific Reports 2025)
• MultiGLICE: GNN + Program Slicing (March 2025)
• MoCQ: Neuro-symbolic Vulnerability Detection (2025)

Self-Improving Systems

• SICA: A Self-Improving Coding Agent (ICLR 2025 Workshop)
• Darwin Godel Machine (Sakana AI 2025)
• AFlow: Automating Agentic Workflow Generation (ICLR 2025 Oral)
• Agent-R1: End-to-End RL for LLM Agents (2025)
• DSPy MIPROv2 (Stanford NLP)

Temporal Knowledge Graphs

• Graphiti/Zep: Temporal KG for Agent Memory (2025)
• EvoReasoner: Evolution Modeling for TKGs (2025)

Technical Debt + Anti-Patterns

• SNA Metrics for Technical Debt Prediction (PLOS ONE 2025)
• Forrester: Solving Tech Debt with AI + Graph (2025)
• Microservice Anti-Pattern Detection via GNNs (SPE Dec 2025)

Code Embeddings + Retrieval

• Voyage-code-3 (Dec 2024)
• Neo4j Codebase Knowledge Graphs (2025)
• Neo4j Infinigraph Launch (Sept 2025)

Architecture Recovery

• SSAR: Architecture Recovery via Community Detection (ICSE 2026)
• Code2DFD: Security-Rich Dataflow Diagrams (2023-2025)

Supply Chain Security

• GUAC: Graph for Understanding Artifact Composition (OpenSSF)
• Vulnerability Propagation in Maven Central (2025)

Explainability

• CFExplainer: Counterfactual GNN Explanations (ISSTA 2024)
• GraphXAI Survey (Neural Computing 2025)

Research synthesis generated 2026-03-02 from 30 topic areas across 3 parallel research sweeps. Cross-referenced against GraFOSa codebase (936 tests, 46 MCP tools, 8 layers) and GRAFOSA-IMPROVEMENT-ROADMAP.md (Sprints 1-5).