Title: Efficient Permission-Aware Traversal and Incremental Materialization over Large Knowledge Graphs

Company and Project Context:

This project is conducted in collaboration with Bevel, a company building the context layer for AI in enterprises. As organizations adopt AI agents and assistants, the central bottleneck is no longer model capability but context: an AI system is only as useful, accurate, and trustworthy as its access to a structured, current, and governed representation of how the organization actually works. Bevel addresses this by building knowledge graphs that unify a company's fragmented information, including documents, tickets, processes, policies, and people across systems such as SharePoint, Jira, and Confluence, into a single connected model that both employees and AI agents can query, and that is continuously maintained as the underlying sources change.

A foundational requirement for any such system deployed inside a real organization is access control. The knowledge graph aggregates information from many source systems, each with its own access policies, and any query, whether issued by a person or by an agent acting on their behalf, must return only information the requesting user is authorized to see. Getting this right is both a hard technical problem and a precondition for enterprise adoption: in regulated and security-conscious environments, a system that cannot rigorously guarantee permission correctness cannot be deployed at all. This project tackles the core algorithmic and systems challenge underlying that guarantee.

Description of Content:

Access control is straightforward in hierarchical (folder-based) systems, where each object has a single parent and access is inherited along a unique path from the root. In a knowledge graph it is substantially harder. The graph is not a tree but a directed, densely connected structure in which a single node may be reachable through many paths and may inherit access policies from multiple, potentially conflicting, source systems. Naively propagating permissions along all edges causes access to leak across the graph, since in a richly connected graph nearly every node is transitively reachable from every other; conversely, ignoring the graph structure entirely forfeits the benefits of the connected model and requires permissions to be maintained per-node by hand. A correct and scalable solution must therefore propagate access selectively, along a designated subset of access-conferring edge types, and must resolve conflicts that arise when multiple paths or multiple source permissions yield different answers for the same node.

This project investigates the design, implementation, and empirical evaluation of efficient algorithms for permission-aware querying over large knowledge graphs. The work comprises:

1. Formalization of propagation semantics. Define a model in which edges are typed and access propagation is specified per edge type (direction and conferred rights), and in which conflict-resolution policies (e.g. deny-overrides for conflicting paths; most-restrictive for multi-source inheritance) are made explicit and well-founded.
2. Efficient permission-checked traversal. Develop traversal algorithms that determine the authorized subset of nodes relevant to a query without exploring the full graph, exploiting the observation that access checks need only traverse the comparatively small authorization subgraph induced by access-conferring edges. Opportunities for parallelization will be investigated.
3. Incremental materialization under change. Since permissions change continuously (e.g. group-membership or source-document ACL changes), full recomputation is infeasible at scale. The project will study incremental update strategies that propagate only the effects of a changed relationship, informed by established relationship-based access-control systems (Google Zanzibar; OpenFGA; SpiceDB) as prior art, while addressing the additional structure specific to derived knowledge-graph nodes.
4. Consistency. Investigate consistency guarantees that prevent stale-permission leaks during propagation, ensuring a user cannot observe data to which access was just revoked.

Title: Operations Research and Decision Analysis Module ID: MGT001374

The project draws on both halves of the course. The traversal and materialization work (Parts 2–3) is graph-algorithmic: restricting access checks to the authorization subgraph induced by access-conferring edges is a reachability and subgraph-extraction problem from the Graph Theory and Network Flow unit, and avoiding full recomputation after each permission change relies on the same overlapping-substructure principle behind Dynamic Programming, memoizing prior authorization results and updating only the affected subproblems. The conflict-resolution work (Part 1) maps onto Decision Analysis. Choosing how to resolve divergent permissions from multiple paths or source systems, deny-overrides versus most-restrictive versus source-priority, is an aggregation-rule problem, much like Multi-Criteria Decision Making, and weighing the risk of a stale-permission leak against an overly conservative denial (Part 4) is a decision under uncertainty. Thus, the course provides the graph/DP toolkit for the algorithmic core of the project and the decision-analysis toolkit for principled, auditable resolution of conflicting access signals.

Milestone 1 - Formalization & literature review Mid-June - early July Survey existing relationship-based access-control systems (e.g. OpenFGA, SpiceDB) and graph-traversal/reachability literature, define the edge-typing scheme for access-conferring relations and draft candidate conflict-resolution policies (deny-overrides, most-restrictive). Deliverable: a formal specification of the propagation model and a shortlist of traversal/incremental-update strategies to evaluate.

Milestone 2 - Empirical baseline evaluation July Bevel evaluates the shortlisted strategies against production-scale knowledge graphs, measuring traversal cost, authorization-subgraph size, and update propagation overhead under realistic permission-change workloads. Deliverable: a benchmark report identifying which approaches are viable at scale and where the main bottlenecks lie (e.g. full-graph recomputation costs, parallelization limits).

Milestone 3 - Algorithm design and implementation August Based on M1-M2, design and implement the permission-aware traversal algorithm and the incremental materialization mechanism, including consistency safeguards. Integrate and test against the benchmark suite from M2, iterating on the design where the empirical results expose gaps. Deliverable: a working prototype with measured performance against the baseline.

Milestone 4 - Evaluation, documentation, and presentation Late August - early September Consolidate results into a final evaluation (correctness checks, performance comparison against baselines), write the final report, and prepare the presentation. Deliverable: final report and presentation slides.