Risk-Averse Matchings over Uncertain Graph Databases

Charalampos E. Tsourakakis, Shreyas Sekar, Johnson Lam, Yang LiuarXiv 2018 · DOI · arXiv

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.

Figure 1: A simple uncertain graph illustrating the trade-off between reward and risk. Edges are labeled with (risk, reward) pairs.

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:

  1. Edge Sorting: Sort all edges in descending order of their efficiency ratio $\alpha_e$.
  2. 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.
  3. 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$.
Figure 2: An uncertain graph under the general model, where edge weights are characterized by multiple parameters to represent diverse probability distributions.

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

Abstract

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 work 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? This problem naturally arises in the context of several important applications, such as online dating, kidney exchanges, and team formation. We introduce a novel formulation for finding matchings with maximum expected reward and bounded risk under a general model of uncertain weighted (hyper)graphs that we introduce in this work. Our model generalizes probabilistic models used in prior work, and captures both continuous and discrete probability distributions, thus allowing to handle privacy related applications that inject appropriately distributed noise to (hyper)edge weights. Given that our optimization problem is NP-hard, we turn our attention to designing efficient approximation algorithms. For the case of uncertain weighted graphs, we provide a $\frac{1}{3}$-approximation algorithm, and a $\frac{1}{5}$-approximation algorithm with near optimal run time. For the case of uncertain weighted hypergraphs, we provide a $Ω(\frac{1}{k})$-approximation algorithm, where $k$ is the rank of the hypergraph (i.e., any hyperedge includes at most $k$ nodes), that runs in almost (modulo log factors) linear time. 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.
BibTeX
@misc{tsourakakis2018risk,
  author = {Charalampos E. Tsourakakis and Shreyas Sekar and Johnson Lam and Yang Liu},
  title = {{Risk-Averse Matchings over Uncertain Graph Databases}},
  year = {2018},
  eprint = {1801.03190},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.03190},
}

Loading related content...

Figure