A large number of applications such as querying sensor networks, and analyzing protein-protein interaction (PPI) networks, rely on mining uncertain graph and hypergraph databases. In this paper we study the following problem:
Given an uncertain, weighted (hyper)graph, how can we efficiently find a (hyper)matching with high expected reward, and low risk?
For instance, the figure on the left shows an uncertain graph with two perfect matchings. While the matching has expected reward , and the matching expected reward 80, the former entails greater risk: with probability the actual reward will be 0.
- Model. We introduce a general model of uncertain weighted hypergraphs, that subsumes prior work and is suitable for a wider variety of applications, including privacy related applications that inject continuous noise to the edge weights. We provide a novel formulation for risk-averse (hyper)graph matchings.
- Approximation algorithms. For the case of uncertain weighted graphs, we provide a -approximation algorithm, and a -approximation algorithm with near optimal run time. For the case of uncertain weighted hypergraphs, we provide a -approximation algorithm, where is the rank of the hypergraph (i.e., any hyperedge includes at most $k$ nodes), that runs in almost (modulo log factors) linear time.
- Experiments. We complement our theoretical results by testing our approximation algorithms on a wide variety of synthetic experiments, where we observe in a controlled setting interesting findings on the trade-off between reward, and risk. We also provide an application of our formulation for providing recommendations of teams that are likely to collaborate, and have high impact.