Refactoring Ownership Propagation in Corporate Ownership Networks • Michel Libera Blog

The Problem

At first glance, ownership propagation looks deceptively simple. If you own 60% of company A, A owns 40% of B, and B owns 50% of C, then your effective ownership in C is the product of those values — 12%.

This intuition works well for small, linear chains. However, real-world ownership structures are far more complex. Instead of a handful of entities, we deal with thousands, connected through deep hierarchies with overlapping ownership paths. A single entity may be reachable through many different chains, and each of those chains contributes to the final result.

Consider a small example:

        Investor X
        /        \
     60%        30%
     /             \
    A              B
      \          /
      40%      50%
        \      /
            C

Investor X owns C through two paths: X → A → C (60% × 40% = 24%) and X → B → C (30% × 50% = 15%). The effective ownership is the sum of all paths: 39%. Now imagine this pattern repeated across thousands of nodes, with paths overlapping at many points.

The Original Approach and Its Hidden Cost

The original implementation followed a natural approach: to compute ownership, start from a target company and recursively walk upwards through all of its owners. For each owner, repeat the process until reaching entities with no further parents. Conceptually, this meant traversing the graph from leaves to roots.

This was easy to implement and easy to understand. However, it introduced a fundamental inefficiency: it treated each path independently.

Whenever a node was reached through a different path, its entire upstream structure was recomputed. Even if the same ownership chain had already been evaluated, the algorithm would traverse it again. In graphs with shared substructures — which are common in practice — this leads to repeated evaluation of the same nodes and edges.

The Turning Point

The turning point came from a simple observation: instead of walking upwards for each query, we could propagate ownership downwards, computing each node once and reusing the result.

This idea immediately raises a constraint: when processing a node, all of its parents must already be processed. Without this guarantee, the node would receive incomplete data — we’d be combining contributions from some parents while others were still unknown.

This is exactly what topological sorting gives us: an ordering of the graph in which every node appears after all of its predecessors. The intuition is straightforward — you start with the entities that have no owners (the roots), then move to entities whose owners have all been processed, and continue level by level until the entire graph is covered. The classic way to compute this ordering (Kahn’s algorithm) does exactly that: take all nodes with no incoming edges, remove them, and repeat the process on what remains. As a bonus, if the process gets stuck before all nodes are processed, you’ve found a cycle — the algorithm doubles as a cycle detector, which matters later.

Once we have this ordering, ownership propagation becomes a single pass through the sorted list. For each node, we look at its already-computed parents, combine their contributions, and store the result. Each node is computed exactly once — effectively a dynamic programming solution on a DAG.

A Note on Cycles

Real corporate structures sometimes contain circular ownership — A owns part of B, B owns part of C, C owns part of A. Such structures break the DAG assumption and require a different mathematical treatment (typically solving a linear system rather than propagating values).

The new implementation detects cycles and reports them as errors rather than silently producing incorrect results. Handling cyclic ownership properly is a separate problem with its own algorithmic and numerical considerations, which I’ve worked on as well — but that deserves its own article.

The Refactor: Isolating the Algorithm First

Before changing anything algorithmic, the first step was structural. The original ownership logic was tangled with business logic — validation, data loading, formatting, and the actual graph computation lived in the same place. Replacing the algorithm under those conditions would have been risky and hard to verify.

So the first commit didn’t change behavior at all. It extracted ownership propagation into a separate module with a narrow interface — essentially a capability: “given this ownership graph, return effective ownership values.” The business code stopped caring about how the computation worked. It just called the capability.

This had two immediate benefits. First, it made the computation testable in isolation, without spinning up the surrounding domain. Second — and more importantly — it made the new implementation a drop-in replacement. Same interface, different internals. The business logic didn’t need to know that anything had changed.

This isolation step is, in my experience, the single most underrated part of any algorithmic refactor. Without it, you’re not refactoring — you’re rewriting and hoping.

Verifying Correctness: Golden Tests and Differential Testing

A refactor of code that computes ownership percentages — numbers that influence reporting, compliance, and downstream decisions — cannot rely on “looks right to me.” The verification strategy had two layers:

Snapshot tests on production-like data. I captured the old implementation’s output on a representative set of real ownership structures and froze it as the expected baseline. The new implementation had to reproduce these results bit-for-bit (within a defined floating-point tolerance). This caught regressions on the kind of messy, real-world graphs that hand-written tests rarely cover.

Hand-built edge cases. Small graphs with manually computed expected values: a single chain, a diamond (two paths to the same node), a node with many parents, a node with many children, a deeply nested structure, and graphs containing cycles (to verify the new implementation flags them correctly). These tests document the algorithm’s contract more clearly than any prose.

Differential testing. During the transition, both implementations ran side by side on the same inputs and their outputs were compared. Any divergence was logged. This was particularly valuable because it ran continuously against real data flowing through the system, not just curated test cases. By the time the old implementation was removed, both had agreed on every input we’d seen for a sustained period.

This is what gave the refactor its safety: not the elegance of the new algorithm, but the certainty that it produced the same answers as the old one, before anyone depended on it.

Complexity Analysis

To understand the impact of this change, it is useful to formalize the problem.

Let:

N be the number of entities
E be the number of ownership relations
P be the total number of distinct ownership paths in the graph

In the recursive approach, the algorithm explores all ownership paths from a node to the roots. The cost scales with the number of paths, not with the size of the graph itself. In graphs with overlapping structures, the number of paths can grow much faster than N or E — in pathological cases (such as a “diamond chain” where every level has two parallel routes), the path count doubles with each level, growing exponentially with depth.

So for the recursive approach:

Time: O(P), where P can in the worst case be exponential in the depth of the graph
Memory: O(D) for the recursion stack, where D is the maximum depth

The topological approach behaves fundamentally differently:

Topological sort: O(N + E)
Single-pass propagation: O(N + E)
Total time: O(N + E)
Memory: O(N + E) — results for all nodes are stored and reused

At first glance, this looks like a trade-off: the recursive approach uses less memory in theory, while the topological approach uses more. But this comparison is misleading without considering what actually happens at runtime.

Beyond Big-O: What Actually Happens at Runtime

Big-O notation captures asymptotic behavior, but it does not describe how the algorithm interacts with the runtime environment. This is where .NET specifics matter.

The recursive approach, despite its small theoretical memory footprint, causes significant transient allocations. Each traversal creates intermediate objects — temporary lists of parents, dictionaries holding partial results per path, closures for LINQ operations, boxed values. These are short-lived and end up in Gen 0 of the GC, but they accumulate quickly. Frequent Gen 0 collections aren’t free: they pause work, dirty CPU caches, and at high allocation rates they promote surviving objects into Gen 1 and Gen 2, where collections become progressively more expensive.

The topological approach allocates memory more deliberately:

the result dictionary is allocated once and filled in-place
each node is computed exactly once, so no intermediate per-path structures are needed
the topological order is materialized as a single array that’s traversed linearly

This leads to a crucial distinction:

recursion has low peak structural memory (the stack), but high allocation churn at runtime
the topological approach has higher steady memory usage, but dramatically lower allocation overhead

In a managed runtime like .NET, allocation churn often matters more for real-world performance than peak memory.

Benchmark Results

The performance characteristics described above were measured across three representative graph structures. Benchmarks were run on .NET using BenchmarkDotNet, measuring execution time, allocated bytes, and Gen 0/1/2 collections.

Case 1: Moderate graph (~40 entities)

A typical mid-sized ownership structure with moderate path overlap.

screen

Execution time decreased by roughly 18%, while memory allocation dropped by over 50%, with noticeably fewer Gen 0 collections. A measurable improvement, but nothing dramatic — at this scale, the recursive approach still copes reasonably well.

Case 2: Larger graph (~100 entities)

A larger structure with more entities and deeper hierarchies.

screen

Execution time improved by around 27%, but the more significant change was in memory — allocations dropped by approximately 75%, and GC activity dropped substantially. The pattern is clear: as path count grows, the recursive approach pays an increasingly steep allocation tax.

Case 3: Dense graph with heavy path overlap (~20 entities)

The most striking result. A small graph in terms of node count, but with many overlapping ownership paths — exactly the structure that punishes the recursive approach the hardest.

screen

Execution time improved by approximately 95%
Memory usage dropped by around 97%
GC overhead was nearly eliminated

This case illustrates the central insight: performance is driven more by graph structure than by graph size. A graph of 20 nodes outperformed in this scenario tells you more than a graph of 1,000 nodes with simple structure.

Why the Difference Is So Large

The key distinction is what each algorithm scales with.

The recursive approach scales with the number of ownership paths
The topological approach scales with the number of nodes and edges

In real-world ownership networks, the number of paths can grow much faster than the graph itself. Consider a “diamond chain” with N = 10,000 entities and depth D = 20, where each level introduces two parallel routes:

Recursive: on the order of 10,000 × 2²⁰ ≈ 10 billion operations for that pathological shape
Topological: on the order of 10,000 + E — tens of thousands of operations

Real ownership structures are rarely this pathological, but they don’t need to be. Even modest path multiplication, repeated across many subgraphs, is enough to make the difference go from “noticeable” to “the system is unusable on production data.”

Closing Thoughts

The most important lesson from this refactor is that performance problems are often rooted in how the problem is modeled, not in micro-optimizations of the existing model.

The recursive solution was intuitive, but it treated each path independently. The topological solution recognizes the graph as a shared structure and evaluates it accordingly. By reversing the direction of computation and enforcing a correct evaluation order, the system became both more efficient and more predictable.

But the algorithm itself was only half the work. The other half was the boring, unglamorous part: isolating the old logic into a replaceable module, capturing its behavior with golden tests, and running both implementations side by side until there was no doubt that the new one was a faithful replacement. That’s what made it possible to ship without fear.

The key insight is simple:

If we compute in the right order, we don’t need to compute more than once.

And once the computation follows the structure of the graph, both performance and clarity improve naturally.

A quick note on what’s next.

Cyclic ownership — where the DAG assumption breaks down — is a different problem requiring a different approach (linear algebra rather than graph traversal). I’ll cover that in a separate article.