Weighted Best-Path Score in Impact Analysis: How code-review-graph Ranks Affected Nodes

The weighted best-path score is a multiplicative ranking metric that propagates impact from changed code through relationship edges, applying edge-specific weights and depth decay while keeping only the highest score when multiple paths reach the same node.

In the code-review-graph open-source project, this score drives the impact analysis engine that identifies which parts of a codebase are most likely affected by a code change. Understanding how this score works is essential for interpreting results and tuning the analysis for your repository's structure.

---

How the Weighted Best-Path Score Works

The scoring algorithm follows a five-stage pipeline that combines graph traversal with probabilistic decay. Each stage is implemented in specific source files with configurable parameters.

1. Seed Node Initialization

All qualified names appearing in changed files enter the frontier with a fixed score of 1.0. These seeds represent the starting points of impact propagation—in graph.py, the initialization populates the _impact_frontier temporary table before traversal begins.

from code_review_graph.graph import GraphStore

store = GraphStore("my_repo/graph.db")

# Start impact analysis from specific changed files

result = store.get_impact_radius_sql(
    changed_files=["/project/src/auth.py"],
    max_depth=2,
    max_nodes=10,
)

2. Edge Traversal with Direction Policies

For every node in the frontier, the engine examines incident edges filtered by impact direction rules. These rules are defined in code_review_graph/constants.py at lines 57-88:

• CALLS edges are traversed incoming (who calls this function?)
• TESTED_BY edges are traversed outgoing (what tests cover this?)

Each edge kind also carries a weight reflecting semantic strength—stronger relationships propagate more impact. The default weight map lives in the same file at lines 54-68.

3. Score Calculation with Decay

When reaching a neighbor node, the candidate score computes as:

new_score = current_score × edge_weight × IMPACT_DEPTH_DECAY

The IMPACT_DEPTH_DECAY constant defaults to 0.6 and is defined in constants.py at lines 94-99. This decay factor ensures that impact weakens with distance from the original change—nodes "closer" to modified code score higher, all else equal.

-- Core score computation from graph.py (simplified)
SELECT
    e.target_qualified AS node_qn,
    f.score * COALESCE(p.weight, ?) * ? AS score
FROM _impact_frontier f
JOIN edges e ON e.source_qualified = f.node_qn
LEFT JOIN _impact_policies p ON p.kind = e.kind

4. Best-Path Selection via MAX Aggregation

A node may be reachable through multiple paths. The engine enforces single best-path retention using MAX(score) aggregation in the _impact_next temporary table—see graph.py lines 46-66. This guarantees each qualified name keeps only its highest discovered score, regardless of path multiplicity.

The SQL implementation explicitly uses:

INSERT OR REPLACE INTO _impact_next (node_qn, score)
SELECT node_qn, MAX(score) FROM (/* ... UNION of incoming/outgoing traversals ... */)
GROUP BY node_qn

5. Floor Filtering and Result Truncation

Scores falling below IMPACT_SCORE_FLOOR (default 0.05) are discarded—preventing infinite expansion in cyclical graphs. After BFS termination or MAX_IMPACT_DEPTH reached, results are truncated to max_nodes entries with an optional truncation flag.

---

Weighted Best-Path Score Formula

Combining all components, the complete scoring logic:

Component	Default Value	Location
Initial seed score	1.0	graph.py frontier init
Edge weights	0.3–1.0 per kind	constants.py
Direction policy	varies by edge kind	constants.py
IMPACT_DEPTH_DECAY	0.6	constants.py
IMPACT_SCORE_FLOOR	0.05	constants.py
MAX_IMPACT_DEPTH	5	constants.py

Final score for node n via path p:

score(n, p) = Π(edge_weight_i) × (IMPACT_DEPTH_DECAY)^depth

With best-path selection: final_score(n) = max_p score(n, p)

---

Code Example: Working with Impact Scores

from code_review_graph.graph import GraphStore

store = GraphStore("my_repo/graph.db")
result = store.get_impact_radius_sql(
    changed_files=["/project/src/auth.py"],
    max_depth=2,
    max_nodes=10,
)

print("Impacted nodes by weighted best-path score:")
for node in result["impacted_nodes"]:
    qn = node.qualified_name
    score = result["impact_scores"][qn]
    print(f"{qn:<40} → {score:.4f}")

# Typical output showing decay cascade:

# /project/src/service.py::login          → 0.6000  (direct caller, weight 1.0)

# /project/src/util.py::hash_password    → 0.3600  (2 hops: 1.0 × 0.6 × 0.6)

# /project/src/config.py::load_settings   → 0.3000  (indirect, lower edge weight)

The best-path weighting is engine-independent—both SQL and NetworkX implementations produce identical scores:

result_sql = store.get_impact_radius_sql(["/project/src/auth.py"])
result_nx  = store._get_impact_radius_networkx(["/project/src/auth.py"])

assert result_sql["impact_scores"] == result_nx["impact_scores"]

---

Tuning the Weighted Best-Path Score

Modify constants in code_review_graph/constants.py to adjust analysis behavior:

# Sharper decay for more localized results

IMPACT_DEPTH_DECAY = 0.4  # default 0.6

# Higher floor for stricter relevance

IMPACT_SCORE_FLOOR = 0.1  # default 0.05

# Custom edge weights for your domain

EDGE_IMPACT_WEIGHTS = {
    "CALLS": 1.0,        # strong propagation

    "IMPORTS": 0.5,      # moderate

    "MENTIONS": 0.2,     # weak signal

}

Changes affect both SQL and NetworkX engines since both reference the same constants module.

---

Summary

• Weighted best-path score combines edge semantics, multiplicative decay, and maximum-path selection to rank code affected by changes
• Seed nodes start at 1.0; each hop multiplies by edge_weight × IMPACT_DEPTH_DECAY (default 0.6)
• Best-path rule keeps only MAX(score) per node, handling multiple reachability paths
• Floor truncation (default 0.05) prevents noise from distant or cyclical relationships
• Implementation spans constants.py (parameters), graph.py (SQL/NetworkX engines), and tests/test_graph.py (verification)

---

Frequently Asked Questions

How is the weighted best-path score different from simple shortest-path distance?

Simple shortest-path counts hops regardless of relationship strength. The weighted best-path score in code-review-graph incorporates edge-specific weights (defined in constants.py lines 54-68) and exponential depth decay, so a longer path through strong relationships can outrank a shorter path through weak ones. The MAX(score) aggregation in graph.py lines 48-66 selects the optimal trade-off per node.

Why does impact score decrease with depth even if edge weights are 1.0?

The IMPACT_DEPTH_DECAY factor (default 0.6, constants.py lines 94-99) applies unconditionally to every hop. This reflects the intuition that indirect relationships are inherently less reliable indicators of impact. A three-hop path with weight-1.0 edges scores 0.6³ = 0.216, while a one-hop path with weight 0.5 scores 0.5 × 0.6 = 0.30—demonstrating how decay penalizes distance.

Can two different paths produce the same final score for a node?

Yes, if their combined edge-weight-and-decay products are equal. For example: path A with two hops of weight 1.0 scores 1.0 × 0.6 × 1.0 × 0.6 = 0.36; path B with one hop of weight 0.6 scores 0.6 × 0.6 = 0.36. The MAX(score) aggregation in graph.py handles ties transparently—both paths validate the same score, and the node retains 0.36.

Where are the unit tests for weighted best-path scoring?

The tests/test_graph.py file contains class TestWeightedImpactScoring verifying correct scoring, ranking order, edge-weight handling, and parity between SQL and NetworkX engines. These tests ensure that modifications to constants.py parameters or graph.py algorithms preserve expected mathematical properties of the weighted best-path score.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}