The CriticalSet problem: Identifying Critical Contr... | AI Research

The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks addresses the challenge of finding the most influential "contributors" within a network where items depend on specific groups of people or entities. In these bipartite networks, the goal is to identify a subset of $k$ contributors whose removal would result in the maximum number of items becoming isolated—meaning they no longer have any supporting contributors. This is a common problem in graph mining, yet it has remained largely unexplored under the "all-or-nothing" dependency model.

The Challenge of Complexity

The authors prove that the CriticalSet problem is NP-hard, meaning it is computationally difficult to find an exact solution as the network grows. Furthermore, the problem requires maximizing a supermodular set function, which is problematic because standard greedy algorithms—often used to solve similar optimization tasks—do not provide reliable approximation guarantees for this specific structure.

A Game-Theoretic Solution

To overcome these mathematical hurdles, the researchers modeled the problem as a coalitional game. They derived a centrality measure called ShapleyCov, which is based on the Shapley value. This metric effectively calculates the "expected number of items" that would be isolated if a specific contributor were to leave the network. By treating the network as a game, the authors provide a formal way to rank contributors based on their unique impact on the system.

The MinCov Algorithm

Building on the insights from ShapleyCov, the authors introduced MinCov, a linear-time iterative peeling algorithm. Instead of simply looking at how many items a contributor supports, MinCov accounts for "connection redundancy." It prioritizes contributors who are the sole support for many items, effectively "peeling" away the most critical nodes first. This approach is designed to be highly efficient, allowing it to handle massive datasets.

Performance and Scalability

The researchers tested their methods on both synthetic data and large-scale real-world networks, including a Wikipedia graph containing over 250 million edges. The results demonstrate that both MinCov and ShapleyCov significantly outperform traditional baseline methods. Notably, MinCov achieves performance nearly identical to a complex Stochastic Hill Climbing metaheuristic—staying within 0.02 AUC—while operating at a speed that is several orders of magnitude faster.