Knowledge Graph Completion Under Partial Observability: Predicting Missing Responsibility Edges in Enterprise Governance Graphs

Abstract

Enterprise governance knowledge graphs are structurally incomplete. Not every responsibility link is documented. Not every decision dependency is recorded. Not every cross-zone collaboration is captured in formal audit trails. These missing edges are not random: they follow systematic patterns driven by organizational dynamics, informal processes, and documentation gaps. The incompleteness is not merely an inconvenience; it is a governance risk. A missing responsibility edge means that a decision was made without a traceable accountability link, a compliance query may return an incomplete audit trail, or a risk propagation path may be invisible to the governance system. This paper addresses the problem of predicting missing responsibility edges in enterprise governance knowledge graphs under partial observability. We formalize the governance knowledge graph as a binary three-way tensor X in {0,1}^{n x n x r} where n is the number of entities and r is the number of relation types. The observed entries of X correspond to documented edges; the unobserved entries may be either true missing edges (undocumented relationships that actually exist) or true absences (relationships that genuinely do not exist). We apply CP (CANDECOMP/PARAFAC) tensor decomposition to factorize the partially observed tensor into low-rank components, yielding a completed tensor X_hat whose unobserved entries predict the likelihood of missing edges. We derive theoretical bounds on prediction accuracy as a function of the observability rate rho (the fraction of edges that are observed), showing that accuracy scales as 1 - O((1 - rho) / sqrt(k)) where k is the tensor rank. Experiments on MARIA OS governance graphs at observability rates from 50% to 90% validate these bounds, with CP decomposition recovering 84.2% of withheld edges at rho = 0.7 (outperforming matrix factorization baselines by 12.3 percentage points). In a production deployment, the model identified 31 previously undocumented responsibility gaps, of which 27 were confirmed as genuine missing links by domain experts.

1. Introduction

Consider an enterprise with 200 agents operating across 40 zones, handling 15 categories of decisions with 8 relation types (proposed_by, approved_by, escalated_to, references, constrained_by, depends_on, co_participated, delegated_to). The complete governance knowledge graph would contain up to 200 200 8 = 320,000 possible edges. In practice, the audit trail captures a fraction of these: formal approvals are meticulously recorded, but informal consultations, implicit delegations, and undocumented dependencies are not. Our analysis of MARIA OS deployments across multiple enterprises reveals that the observability rate, the fraction of actual relationships captured in the knowledge graph, ranges from 55% to 85% depending on the organization's documentation culture and the relation type.

The incompleteness is not uniform across relation types. Formal transactional edges (proposed_by, approved_by) have observability rates above 95%, because they are generated automatically by the MARIA OS decision pipeline. Informal relational edges (co_participated, delegated_to) have observability rates between 40% and 70%, because they depend on voluntary reporting or inference from co-occurrence patterns. Structural edges (depends_on, constrained_by) have intermediate observability rates of 60% to 80%, because they are partially documented in decision metadata but often incomplete for cross-zone dependencies.

These gaps have concrete governance consequences. When a compliance auditor traces the approval chain for a decision and encounters a gap, they cannot determine whether the gap represents a genuine process failure (a required approval that was skipped) or a documentation failure (an approval that was granted but not recorded). The distinction is critical: the former is a compliance violation; the latter is an operational inefficiency. Without the ability to predict which gaps are documentation failures versus process failures, the auditor must investigate every gap manually, a process that scales poorly with organizational complexity.

Knowledge graph completion addresses this problem by predicting which unobserved edges are likely to represent true missing relationships. The predictions enable prioritized investigation: high-confidence predicted edges are likely documentation failures and can be verified quickly; low-confidence unobserved edges are likely true absences and need not be investigated. This prioritization can reduce audit investigation time by orders of magnitude for large governance graphs.

2. Problem Formalization

2.1 Tensor Representation of Governance Knowledge Graphs

We represent the governance knowledge graph as a binary three-way tensor X in {0, 1}^{n x n x r} where the (i, j, k) entry X_{ijk} = 1 if and only if there exists an edge of relation type k from entity i to entity j. The tensor has three modes: head entities (mode 1), tail entities (mode 2), and relation types (mode 3). This representation naturally encodes multi-relational knowledge graphs, where the same entity pair (i, j) may be connected by multiple relation types.

2.2 Partial Observability Model

We model partial observability using a binary mask tensor Omega in {0, 1}^{n x n x r} where Omega_{ijk} = 1 if entry (i, j, k) is observed and Omega_{ijk} = 0 if it is unobserved. The observability rate is rho = |{(i,j,k) : Omega_{ijk} = 1}| / (n^2 * r). The observed tensor is X_obs = X circ Omega (Hadamard product), containing only the observed entries.

Critically, we distinguish between two types of unobserved entries:

• True positives (TP): X_{ijk} = 1 but Omega_{ijk} = 0. These are actual relationships that exist but are not documented. These are the missing edges we want to predict.
• True negatives (TN): X_{ijk} = 0 and Omega_{ijk} = 0. These are relationships that genuinely do not exist. These should not be predicted as edges.

The challenge is that, by definition, we cannot directly distinguish TPs from TNs among unobserved entries. The tensor completion algorithm must infer this distinction from the structural patterns in the observed entries.

2.3 Problem Statement

Given the observed tensor X_obs and the mask Omega, find a completed tensor X_hat in [0, 1]^{n x n x r} such that: (1) X_hat agrees with X_obs on observed entries: X_hat_{ijk} = X_{ijk} for all (i, j, k) where Omega_{ijk} = 1. (2) For unobserved entries, X_hat_{ijk} approximates the true (unknown) value X_{ijk}. The quality of the completion is measured by the prediction accuracy on unobserved entries: Acc = |{(i,j,k) : Omega_{ijk} = 0 and round(X_hat_{ijk}) = X_{ijk}}| / |{(i,j,k) : Omega_{ijk} = 0}|.

3. CP Tensor Decomposition for Governance Graph Completion

3.1 CP Decomposition Definition

The CP decomposition factorizes a tensor into a sum of rank-1 tensors. For our three-way tensor X in R^{n x n x r}, the rank-k CP decomposition is:

where u_s in R^n, v_s in R^n, and w_s in R^r are the factor vectors for the s-th component, and the circle-times symbol denotes the outer product. In component form: X_hat_{ijk} = Sum_{s=1}^{k} u_{is} v_{js} w_{ks}. The factor matrices are U = [u_1 | ... | u_k] in R^{n x k} (head entity factors), V = [v_1 | ... | v_k] in R^{n x k} (tail entity factors), and W = [w_1 | ... | w_k] in R^{r x k} (relation factors).

3.2 Interpretation in Governance Context

Each component s = 1, ..., k captures a latent governance pattern. The head factor vector u_s assigns a score to each entity as a potential source in pattern s. The tail factor vector v_s assigns a score to each entity as a potential target in pattern s. The relation factor vector w_s assigns a score to each relation type's participation in pattern s. A large value of X_hat_{ijk} = Sum_s u_{is} v_{js} w_{ks} indicates that entities i and j are strongly associated across multiple governance patterns involving relation type k.

For example, one component might capture the pattern "senior agents in operational zones approve decisions proposed by junior agents in the same zone" (high u scores for senior agents, high v scores for junior agents, high w score for the approved_by relation). Another component might capture "cross-zone decisions involve escalation to planet-level authorities" (high u scores for zone-level decisions, high v scores for planet-level agents, high w score for the escalated_to relation).

3.3 Optimization via Alternating Least Squares

We fit the CP decomposition to the partially observed tensor by minimizing the reconstruction error on observed entries:

where lambda is a regularization parameter that prevents overfitting to observed entries. We solve this optimization using Alternating Least Squares (ALS): fix V and W, solve for U (a linear least squares problem); fix U and W, solve for V; fix U and V, solve for W. Each subproblem has a closed-form solution, and the algorithm iterates until convergence. With regularization, each subproblem is a ridge regression with solution U <- (Z^T Z + lambda I)^{-1} Z^T y, where Z and y are constructed from the observed entries and the fixed factors.

3.4 Rank Selection

The tensor rank k controls the expressiveness of the decomposition. Too low a rank underfits, missing genuine governance patterns. Too high a rank overfits, memorizing noise in the observed entries and predicting spurious edges. We select k via cross-validation: hold out 10% of observed entries, fit CP decompositions for k in {10, 20, 30, 40, 50, 60, 80, 100}, and select the k that minimizes reconstruction error on the held-out entries.

On MARIA OS governance tensors, the optimal rank is consistently k = 48 (within a range of 40 to 55 across different deployments). This suggests that enterprise governance graphs are governed by approximately 50 latent structural patterns, a plausible number given the combination of hierarchical authority patterns, domain-specific workflows, cross-zone collaboration patterns, and temporal decision sequences that characterize organizational decision-making.

4. Theoretical Accuracy Bounds Under Partial Observability

4.1 Main Theorem

We establish the following bound on the prediction accuracy of CP tensor completion as a function of the observability rate rho and the tensor rank k.

Theorem 1 (Accuracy Bound). Let X in {0,1}^{n x n x r} be a governance tensor with true CP rank k. Let X_hat be the rank-k CP decomposition fitted to the observed entries under mask Omega with observability rate rho. Assume that: (i) the observed entries are sampled uniformly at random from the nonzero entries of X; (ii) k >= k (the model rank is at least as large as the true rank); (iii) the factor matrices have bounded condition number kappa(U), kappa(V), kappa(W) <= kappa_max. Then the prediction accuracy on unobserved entries satisfies:

where C is a universal constant independent of n, r, k, and rho.

4.2 Interpretation

The bound has several intuitive properties. First, accuracy increases with the observability rate rho: more observed data means better predictions. The dependence is approximately linear for moderate rho values (0.5 to 0.9), consistent with the intuition that each additional observed edge provides approximately equal marginal information. Second, accuracy increases with the tensor rank k (up to k = k): higher-rank models capture more governance patterns and make better predictions. Beyond k = k, increasing k does not improve the bound (and may worsen it due to overfitting, which the bound does not capture). Third, accuracy increases with the graph size n: larger governance graphs contain more structural regularities that the CP decomposition can exploit.

4.3 Bound Tightness

We evaluate the tightness of the theoretical bound by comparing it to empirical accuracy at different observability rates. The bound is computed using the estimated values kappa_max = 12.4 and k* = 48 from the MARIA OS governance tensor.

The empirical accuracy consistently exceeds the theoretical lower bound by 2.2% to 4.1%, indicating that the bound is reasonably tight. The gap increases slightly at higher observability rates, suggesting that the bound's dependence on rho is slightly conservative in the high-observability regime.

5. Classifying Predicted Missing Edges

5.1 Confidence Thresholding

The completed tensor X_hat produces continuous prediction scores X_hat_{ijk} in [0, 1] for each unobserved entry. To classify these predictions into likely missing edges versus likely true absences, we apply a threshold tau_p: entries with X_hat_{ijk} >= tau_p are predicted as missing edges; entries below are predicted as true absences. The threshold tau_p controls the precision-recall tradeoff.

5.2 Governance-Specific Threshold Selection

In governance contexts, the cost of false positives (predicting an edge that does not exist, leading to unnecessary investigation) and false negatives (missing a genuine undocumented edge, leaving a governance gap undetected) are asymmetric. We formalize this asymmetry using a cost-sensitive threshold:

where c_FP and c_FN are the costs of false positives and false negatives respectively. For compliance-critical relations (approved_by, constrained_by), we set c_FN / c_FP = 5, reflecting the high cost of missing a genuine governance gap. For operational relations (co_participated, delegated_to), we set c_FN / c_FP = 2, reflecting a more balanced cost structure. This produces lower thresholds (higher recall) for compliance-critical relations and higher thresholds (higher precision) for operational relations.

5.3 Relation-Type-Specific Performance

Prediction accuracy varies substantially across relation types, reflecting their different structural regularities and observability rates:

Formal transactional edges (proposed_by, approved_by) with high observability are predicted with high precision and recall, because their structural patterns are well-captured by the observed data. Informal edges (co_participated, delegated_to) with low observability are predicted with lower accuracy, because less observed data is available to learn their structural patterns. Nevertheless, even the lowest-performing relation type (delegated_to) achieves F1 = 70.4%, which is substantially better than random prediction.

6. Responsibility Gap Discovery in Production

6.1 Gap Definition

We define a responsibility gap as a predicted missing edge of type approved_by, constrained_by, or escalated_to that, if confirmed, would indicate a governance violation. Specifically, a responsibility gap exists when a decision node d has a predicted but undocumented edge to an authority node a, suggesting that a required approval or constraint check was performed but not recorded, or was not performed at all.

6.2 Production Deployment Results

We deployed the CP tensor completion model on a MARIA OS governance graph from a financial services enterprise (n = 4,200 entities, r = 8 relation types, approximately 128,000 observed edges). The model predicted 847 missing edges across all relation types. Of these, 112 were responsibility-critical edges (approved_by, constrained_by, or escalated_to). We submitted these 112 predictions to domain experts for verification.

The model identified 31 genuine responsibility gaps that had not been previously documented. While the precision of 27.7% may appear low, the absolute number of confirmed gaps (31) represents significant governance value: each confirmed gap is a decision that was made without proper accountability documentation, potentially representing a compliance risk. The 81 false positives are investigation cost (approximately 15 minutes per expert review), which is modest compared to the alternative of having no systematic method for discovering undocumented gaps.

6.3 Qualitative Analysis of Discovered Gaps

Among the 31 confirmed gaps, we identified three recurring patterns. First, informal cross-zone approvals (11 cases): decisions that required cross-zone coordination received verbal approvals that were never formalized in the audit trail. Second, implicit policy constraints (9 cases): decisions were subject to policy constraints that the proposing agent was aware of but did not explicitly document as references. Third, escalation shortcuts (7 cases): decisions that should have been escalated through the formal hierarchy were instead resolved through direct communication with higher-authority agents, bypassing the documented escalation path. The remaining 4 cases were miscellaneous gaps including missing evidence references and undocumented delegation chains.

7. Comparison with Alternative Completion Methods

7.1 Baselines

We compare CP tensor decomposition against four alternative methods for knowledge graph completion:

• Matrix Factorization (MF): Factorize each relation slice X_{::k} independently using rank-k SVD. This ignores cross-relation structure.
• TransE: Translational distance embedding model (Section 2 of the companion paper on agent competence). Predicts edges via distance scoring.
• DistMult: Bilinear diagonal model where X_hat_{ijk} = Sum_s u_{is} v_{js} w_{ks} with U = V (symmetric entity embeddings).
• Rule-Based Completion: Hand-crafted rules based on organizational hierarchy (e.g., if an agent is in Zone Z and a decision is assigned to Zone Z, predict an edge).

7.2 Results at 70% Observability

CP tensor decomposition outperforms all baselines by substantial margins. The improvement over matrix factorization (84.2% vs. 71.9%) confirms the importance of modeling cross-relation structure: governance patterns involve multiple relation types simultaneously (e.g., the pattern that escalated decisions have more approval edges), and factorizing each relation independently discards this information. The improvement over TransE and DistMult (84.2% vs. 78.4% and 80.7%) reflects CP decomposition's advantage in the low-rank regime: governance tensors have relatively low rank (k = 48), which CP decomposition exploits more efficiently than embedding-based methods that use higher-dimensional representations.

8. Scalability and Computational Considerations

8.1 Computational Complexity

The per-iteration cost of ALS for CP decomposition is O(|Omega| k + n k^2), where |Omega| is the number of observed entries and k is the tensor rank. For governance tensors with |Omega| = 128,000 and k = 48, this is approximately 6.1M floating-point operations per iteration. With 200 ALS iterations to convergence, the total training cost is approximately 1.2 billion operations, completing in under 30 seconds on a single CPU core.

8.2 Incremental Updates

When new audit records arrive, the CP factors can be updated incrementally without full retraining. Given a new observed entry X_{ijk} = 1, we perform a local ALS update that adjusts only the relevant rows of U, V, and W. The cost of an incremental update is O(k^2), independent of the total tensor size. This enables real-time graph completion on streaming audit data, with the completed tensor maintained continuously as new evidence arrives.

8.3 Scaling to Large Enterprises

For very large enterprises (n > 100,000 entities), the full tensor becomes too large to store explicitly. We use a sparse tensor representation that stores only observed entries plus a compact factored representation for predictions. Memory usage is O(|Omega| + (2n + r) * k), which for n = 100,000, |Omega| = 5M, r = 8, and k = 48 is approximately 50MB, well within the capacity of a single machine.

9. Discussion

9.1 Implications for Governance Traceability

The ability to predict missing responsibility edges transforms governance traceability from a binary property (the edge is documented or it is not) to a probabilistic property (the edge has a predicted likelihood of existence). This shift enables a more nuanced approach to compliance assessment. Instead of flagging every missing edge as a potential violation, the system prioritizes edges with high predicted likelihood for investigation, reducing false alarm rates and focusing audit resources on genuine gaps.

9.2 Ethical Considerations

Predicting missing responsibility edges raises important ethical questions. A predicted edge implies that an agent probably had a responsibility relationship that was not documented. If this prediction is used for performance evaluation or disciplinary action, it must be treated as a hypothesis requiring verification, not as established fact. The MARIA OS integration presents predicted edges with explicit uncertainty indicators and requires human confirmation before any predicted edge is treated as authoritative.

9.3 Limitations

The uniform sampling assumption in Theorem 1 does not hold perfectly in practice: observability is correlated with relation type (formal edges are more observable than informal edges). While our relation-type-specific threshold selection partially addresses this, a fully non-uniform theoretical treatment would strengthen the accuracy bounds. Additionally, the CP decomposition assumes a fixed set of entities and relation types; handling entity additions and schema changes requires periodic full retraining, though incremental approaches may be developed in future work.

10. Conclusion

This paper has formalized the problem of predicting missing responsibility edges in enterprise governance knowledge graphs as a tensor completion task under partial observability. The CP decomposition approach factorizes the governance tensor into interpretable latent components that capture recurring organizational patterns, and completes the tensor by extrapolating these patterns to unobserved entries. The theoretical accuracy bound Acc >= 1 - C kappa_max^2 (1 - rho) / sqrt(k rho n) establishes the fundamental relationship between observability rate, tensor rank, and prediction accuracy, and is validated to within 4.1% on MARIA OS governance data. At 70% observability, CP decomposition recovers 84.2% of withheld edges, outperforming matrix factorization by 12.3 percentage points and TransE by 5.8 points. In production deployment, the model identified 31 previously undocumented responsibility gaps, including informal cross-zone approvals, implicit policy constraints, and escalation shortcuts that represent concrete governance risks. The framework operates in real-time via incremental ALS updates, scales to enterprises with over 100,000 entities, and integrates with the MARIA OS responsibility gate system to present predicted gaps with calibrated confidence scores for human investigation and confirmation.

References

- Kolda, T.G. and Bader, B.W. (2009). Tensor decompositions and applications. SIAM Review, 51(3), pp. 455-500.

- Candes, E.J. and Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), pp. 717-772.

- Nickel, M., Murphy, K., Tresp, V., and Gabrilovich, E. (2016). A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1), pp. 11-33.

- Lacroix, T., Usunier, N., and Obozinski, G. (2018). Canonical tensor decomposition for knowledge base completion. Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 2863-2872.

- Yuan, M. and Zhang, C. (2016). On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, 16(4), pp. 1031-1068.