# Bi-objective Optimization in Role Mining

arXiv: https://arxiv.org/abs/2403.16757 · HTML: https://mlsanity.com/paper/2403.16757/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 25 Mar 2024.

## Builds on (most cited first, 7 of 7)

- [On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation](https://mlsanity.com/paper/1509.09236/) (2015)
- [Parameterized Low-Rank Binary Matrix Approximation](https://mlsanity.com/paper/1803.06102/) (2018)
- [Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations](https://mlsanity.com/paper/1511.01699/) (2015)
- [Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints](https://mlsanity.com/paper/1604.05636/) (2016)
- [The Queen's Guard: A Secure Enforcement of Fine-grained Access Control In Distributed Data Analytics Platforms](https://mlsanity.com/paper/2106.13123/) (2021)
- [The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency](https://mlsanity.com/paper/1512.07019/) (2015)
- [Solving the Workflow Satisfiability Problem using General Purpose Solvers](https://mlsanity.com/paper/2105.03273/) (2021)

## Abstract (arXiv)

Role mining is a technique used to derive a role-based authorization policy from an existing policy. Given a set of users U, a set of permissions P and a user-permission authorization relation mahtitUPAsubseteq U× P, a role mining algorithm seeks to compute a set of roles R, a user-role authorization relation mathitUAsubseteq U× R and a permission-role authorization relation mathitPAsubseteq R× P, such that the composition of mathitUA and mathitPA is close (in some appropriate sense) to mathitUPA. In this paper, we first introduce the Generalized Noise Role Mining problem (GNRM) -- a generalization of the MinNoise Role Mining problem -- which we believe has considerable practical relevance. Extending work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter r + k, where r is the number of roles in the solution and k is the number of discrepancies between mathitUPA and the relation defined by the composition of mathitUA and mathitPA. We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both r and k subject to upper bounds r≤ barr and k≤ bark, where barr and bark are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter barr+bark. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi's performance is fixed-parameter tractable, (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies.