Abstract
Mining uncertain graph and hypergraph databases is critical for applications ranging from sensor network analysis to protein-protein interaction (PPI) networks. This paper addresses the problem of finding matchings that maximize expected reward while strictly limiting risk. We introduce the Bounded Risk Maximum Weighted Matching (BR-MWM) problem, a novel formulation that handles both continuous and discrete probability distributions. Given the NP-hardness of the problem, we develop efficient approximation algorithms, including a $\frac{1}{3}$-approximation for graphs and an $\Omega(\frac{1}{k})$-approximation for hypergraphs of rank $k$. Our experiments on synthetic and real-world datasets, such as DBLP and PPI networks, demonstrate that our approach is both scalable and effective at navigating the reward-risk trade-off.
1. Introduction
In many modern network applications, the existence or weight of an edge is not a deterministic value but a random variable. In online dating, a "match" has a probability of success; in kidney exchanges, a transplant has a risk of failure; in team formation, a collaboration has an uncertain impact. While traditional graph mining focuses on maximizing the total expected reward, this often leads to solutions with high variance—what we term "risk."
A high-reward matching that is unlikely to materialize is often less desirable than a slightly lower-reward matching with a high probability of success. This paper formalizes this intuition by introducing a framework for risk-averse matching in uncertain graph databases.
2. The Bounded Risk Maximum Weighted Matching (BR-MWM) Problem
We define the BR-MWM problem as follows: given an uncertain graph where each edge $e$ has an expected reward $\mu_e$ and a risk $\sigma_e$ (standard deviation), find a matching $M$ that maximizes $\sum_{e \in M} \mu_e$ subject to the constraint $\sum_{e \in M} \sigma_e \le B$, where $B$ is a user-defined risk budget.
As shown in Figure 1, choosing between edges involves balancing these two dimensions. A greedy algorithm focusing solely on reward might choose the horizontal edges (reward 100), but if the risk budget is tight, the vertical edges (reward 40, risk 1) might be more "efficient" depending on the total budget constraints.
3. Algorithmic Framework
The core challenge of BR-MWM is its NP-hardness. To address this, we propose a scalable approximation framework based on the "efficiency" of each edge, defined as the ratio $\alpha_e = \mu_e / \sigma_e$.
Our algorithm proceeds in three main steps:
- Edge Sorting: Sort all edges in descending order of their efficiency ratio $\alpha_e$.
- Nested Subgraphs: Construct a sequence of nested subgraphs $G_1 \subset G_2 \subset \dots \subset G_m$, where $G_i$ contains the $i$ most efficient edges.
- Optimization via Binary Search: Perform a binary search over these subgraphs. In each step, we solve a standard Maximum Weighted Matching (MWM) problem on $G_i$. We then check if the resulting matching violates the risk budget $B$.
This approach allows us to leverage existing, highly optimized matching algorithms as "black boxes." For graphs, using an exact MWM algorithm yields a $\frac{1}{3}$-approximation. For massive datasets, using a greedy MWM yields a $\frac{1}{5}$-approximation in near-linear time. Figure 2 illustrates the general model where edge weights can follow complex distributions, which our framework handles by utilizing their closed-form mean and variance.
4. Experimental Evaluation
We evaluated our algorithms on synthetic graphs and two large-scale real-world datasets: a PPI network and the DBLP collaboration hypergraph.
Scalability and Performance: Our greedy approximation algorithm proved exceptionally scalable, handling the DBLP dataset (1.7M nodes, 3.2M edges) with ease. Interestingly, we found that risk-aversion acts as a natural pruning mechanism; lower risk budgets restrict the search space, often leading to faster execution times than standard MWM because the algorithm ignores a vast majority of highly uncertain edges.
Qualitative Insights from DBLP: In the context of team formation (hypergraph matching), we observed a distinct "phase transition" as the risk budget $B$ increased. At low risk levels, the algorithm identified teams with high success probabilities (0.66 to 1.0) and moderate citation counts. At high risk levels, it identified "moonshot" collaborations—interdisciplinary teams with very high potential impact (nearly 1,000 citations) but a low historical probability of collaborating (around 8.5%).
5. Conclusion
This work provides the first efficient, approximation-guaranteed framework for risk-averse matching in uncertain graphs. By avoiding expensive Monte Carlo sampling and focusing on the reward-to-risk efficiency ratio, we enable risk-aware decision-making in massive networks. Future work will explore extending this philosophy to other graph primitives, such as densest subgraph discovery and $k$-core decomposition in uncertain databases.
Summary updated