Dependency Graph Analysis for Large Codebases
Graph traversal reveals a change's blast radius, including consumers the diff never shows.
Sponsored by Graphide

Dependency graph analysis for large codebases shows how changes propagate beyond the files in a diff. It gives engineers a way to use that structure for impact review, architectural checks, and AI agent steering. An interactive codebase graph makes those relationships navigable, but its value depends on keeping the graph current and using it to enforce constraints before changes merge.
Why understanding propagation is the core problem in large codebases
As a codebase grows, it gets harder to judge a local edit on its own. In a monorepo, one modified utility function can break downstream consumers in packages that do not appear in the diff. In a large service mesh, the same problem crosses component boundaries.
Tightly coupled architectures, circular imports, and hidden upstream dependencies make manual propagation tracing unreliable at scale. A reviewer may understand the modified function without knowing the hundreds of files that depend on it transitively. That affected set is the change’s blast radius, and its size need not resemble the size of the patch. The difficulty is therefore not simply reading more code, but following relationships that linear review leaves out. Those relationships have a structure, and that structure can be modeled.
What a dependency graph encodes and the vocabulary engineers need to reason with it
A dependency graph is a directed structure whose nodes represent modules, files, packages, or components. Its edges encode “depends on” relationships. If appA imports libX and libX imports commons, appA has a direct dependency on libX and a transitive dependency on commons. In the reverse reading, libX and appA are dependents of commons. These terms distinguish what a component needs from what might be affected when it changes.
Edge orientation matters because those two questions require traversal in opposite directions. With edges pointing from an importer to its dependency, tracing requirements follows the edges, while tracing affected consumers follows them in reverse. A graph without circular dependencies is a directed acyclic graph, or DAG. Circular imports break that condition and also reveal something about the architecture. A weakly connected component groups nodes that are connected when edge direction is ignored, but being in the same group alone does not show a directed impact path.
The same codebase can also have graphs at different granularities. A package-level graph is relatively sparse and fast to traverse. A call graph is denser and more expensive, but exposes runtime coupling that an import graph can miss. Applications that share dependencies can belong to the same weakly connected component without importing each other directly. This vocabulary gives engineers a way to distinguish broad structural proximity from a specific path along which a change may propagate.
The three core analysis techniques and what each one reveals
Topological depth locates a file within the layers of an acyclic dependency graph. With the importer-to-dependency orientation used here, entry points that nothing imports sit at depth zero, while foundational utilities that import nothing sit near the deepest levels. Topological sorting supplies the ordering that build systems such as Bazel and GNU Make use to determine what must be built first. For impact analysis, that ordering becomes a propagation ladder.
Centrality asks a different question, namely which files are structural hubs. PageRank-style analysis finds files in parts of the dependency graph that have many connections. A highly central shared file can become a single point of failure because many consumers rely on it. Centrality-based coloring or flagging makes that risk visible during review.
Call-graph partitioning addresses the problem of runtime coupling in a graph too dense to inspect as a whole. It decomposes the system into analyzable subgraphs, making coupling boundaries easier to examine. Musco et al. studied four types of call graph across 10 open-source Java projects and used five classical mutation operators to generate 17,000 mutants. They found that greater graph sophistication improved completeness of impact prediction, but the most basic call graph gave the best trade-off between precision and recall.
Once the relevant graph is available, breadth-first search, or BFS, from the changed nodes produces a concrete reachable set. For blast-radius analysis, traversal follows the relationships toward affected dependents. Its useful output is the list of potentially affected nodes. Together, depth, centrality, and call-graph partitioning reveal a change’s position, structural risk, and coupling context.
How graph analysis translates into impact decisions before a change merges
Before merge, impact analysis answers what a change touches that the diff does not show. Traversal starts with the changed set and proceeds toward its transitive dependents. That affected set may be many times larger than the modified file count.
Consider a shared utility changed inside one package of a monorepo. The diff may show changes only in that package even though consumers elsewhere rely on the utility’s behavior. Traversing the reverse dependency graph exposes the consumers that require attention before merge. The result shows which reachable consumers might be affected, though some may not fail.
The three analysis lenses then guide how review effort is allocated. A high-centrality change warrants deeper scrutiny and wider test coverage because its consumers are numerous or structurally important. Depth shows whether the change sits near an entry point or within the shared foundations, although it is not a substitute for tracing actual dependents. A depth-zero entry-point change still needs end-to-end testing as well as unit tests. Call-graph boundaries add runtime context, allowing attention to concentrate on risky changes instead of being spread uniformly across every modified file.
Why AI-generated code makes dependency graph analysis structurally necessary, not optional
AI coding agents can satisfy a local task while violating the architecture that the rest of the codebase depends on. They do not inherently understand architectural topology, and a single session can modify dozens of files. An added import in a high-centrality file or a new circular dependency may go unnoticed unless the environment checks for it. Code can compile and pass local tests while still putting a downstream consumer at risk from a breaking change.
Reading generated code line by line may establish what individual edits do, but it does not establish the propagation surface of the combined change. As the changed set grows, manually reconstructing those relationships becomes impractical. Graph navigation supplies the missing interface by connecting the agent’s edits to the surrounding architecture.
Graph-based navigation vs. semantic retrieval for finding what an agent's change actually affects
Keyword and embedding-based retrieval remain useful when the relevant code has a lexical or semantic signal. BM25 can find matching terms, while embeddings can find code with a meaning close to the query. Neither method, however, establishes dependency reachability. A downstream consumer can depend on a changed file without sharing its names or vocabulary.
The 2026 CodeCompass study found that graph-based navigation outperformed BM25 retrieval by 21.2 percentage points on hidden-dependency tasks. That result concerns precisely the cases where naming patterns do not reveal architectural connections. Graph traversal follows the relationships in the graph even when the connected files look unrelated in a search result. Musco et al.’s work likewise examines impact through runtime call structure. In both cases, the relevant signal is the relationship between code elements.
Retrieval and traversal serve complementary roles. Retrieval helps locate semantically findable code, while graph traversal handles structurally connected but lexically distant consumers. For an agent’s change, finding a plausible edit location is only the beginning of the task. Finding its affected set means following dependencies outward from that location. Because agents can default to lexical heuristics even when structural navigation is available, dependable use of the graph also requires enforcement.
Enforcing architectural constraints at the graph level in CI
The graph first serves as a diagnostic model for understanding propagation, then as a pre-merge decision aid for assessing impact. CI turns that same model into an enforcement mechanism. Architectural rules run against every change rather than depending on a reviewer’s available attention. A violation breaks the build instead of remaining a concern that someone must remember to investigate. This makes the build system the arbiter of the declared architectural constraints.
Dependency direction rules can restrict modules to dependencies at the same level or below, preventing infrastructure from depending on the application layer. Circular dependency constraints can fail the build when Module A depends on Module B and Module B depends on Module A. Layer boundary validation can reject a file created in an invalid architectural location. Impact checks can also block changes whose blast radius is above the thresholds set for it.
The pipeline itself is also part of the dependency surface. GitHub Actions’ 2026 security roadmap introduces workflow-level locking through .github/workflows/actions.lock, generated by the gh actions-lock CLI. The lockfile pins direct and transitive dependencies with commit SHAs. This enforces dependencies in the workflows that run the checks, while application-level graph rules apply to the code under review.
Enforcement also has a latency constraint. Pipeline stages that exceed a few minutes face resistance and may be disabled, undermining their purpose. Sparse package-level graph checks are fast enough to work well as a first gate. Deeper call-graph analysis can be saved for high-centrality files that have changed, where more detail helps assess the greater risk that a change will propagate.
Keeping the dependency graph accurate as the codebase evolves under agent output
A graph that drifts from the code cannot reliably enforce architectural rules. A static diagram is out of date as soon as refactoring changes the relationships it shows. Under agent output, manual upkeep also competes with the speed and volume of generated changes. Automatic graph generation from code and versioning with the repository address this upkeep.
The diagram-as-code approach stores dependency definitions in plain text DOT files or equivalent structured formats beside the source in Git. Structural changes can then version with the code that causes them. Parsing tools such as tree-sitter support fast, incremental, language-agnostic syntax tree reconstruction on every commit. Used in an automated generation process, that keeps the graph from remaining stale beyond a build cycle. The maintenance work belongs to the pipeline.
Current verification workflow
Dependency information can help explain a change’s reach, while CI still needs to establish the outcome of the tests it is responsible for running. Graphide CI runs existing GitHub Actions jobs on Graphide runners, using warm caches, and splitting long test steps only where a check shows every result stays the same, to reduce waiting while preserving the pass/fail verdict. A failing test fails the job. Graphide review is a separate product that presents changed behavior and findings with evidence; it does not block merging on its own. Consult the current documentation for supported workloads and limitations.
Product information updated November 5, 2026 to reflect Graphide’s current CI and review products.
Sources
- A Large-Scale Study of Call Graph-based Impact Prediction using Mutation Testing
- The Navigation Paradox in Large-Context Agentic Coding: Graph-Structured Dependency Navigation Outperforms Retrieval in Architecture-Heavy TasksCode, benchmarks, and experimental infrastructure available at: https://github.com/tpaip607/research-codecompass


