Uncertain Graphs [DRAFT]

(Parchas 2015): Write something about it.

Propabilistic graphs may be:

edge existential

where each edge is augmented with a probability value, which indicates the chance that the edge exists.

weight distribution

where each edge is associated with a probability distribution of weight values.

Evaluation of ST-queries is hard (#P-hard). You have to create all possible (non-probabilistic) words that correspond to the probabilistic graph and evaluate the query in each one.

To improve the efficiency sampling is employed, where possible worlds with high existential probabilities are extracted.

  • Can we take advantage of Ehab’s work to compute the samples?

An Indexing Framework for Queries on Probabilistic Graphs

Downloaded from:


ST-queries include reachability queries (RQ) and shortest distance queries (SDQ). These queries provide answers with probabilistic guarantees. For example, the answer of an RQ tells us the chance that \(s\) can reach \(t\); the SDQ returns the probability distribution of the distance between \(s\) and \(t\).


The main idea is to evaluate the query on \(G(q)\), a weight-distribution probabilistic graph derived from \(G\). Given a probabilistic graph \(G\) and a ST-query \(q\), PTree can generate a probabilistic graph \(G(q)\), which is typically smaller than \(G\) and has fewer possible worlds. Hence, the approach can be considered in some sense as a graph compression algorithm –- but compression of the possible worlds.

In this paper, the authors introduce PTree, a formal indexing framework for probabilistic graphs, and they further present the detailed theoretical and experimental results for three instantiations of PTree (i.e., SPQR tree, FWD, and LIN).

Some references that need exploring

Sampling methods

George S. Fishman. 1986. A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness. IEEE Trans. Reliability 35, 2 (1986).

Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-Constraint Reachability Computation in Uncertain Graphs. PVLDB 4, 9 (2011).

Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. k-Nearest Neighbors in Uncertain Graphs. PVLDB 3, 1 (2010).

Zhaonian Zou, Hong Gao, and Jianzhong Li. 2010. Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics. In KDD.

Indexing methods

Y. Yuan, G. Wang, H. Wang, and L. Chen. Efficient subgraph search over large uncertain graphs. PVLDB, 4(11), 2011.

O. Papapetrou, E. Ioannou, and D. Skoutas. Efficient discovery of frequent subgraph patterns in uncertain graph databases. In EDBT, 2011.

A. Khan, F. Bonchi, A. Gionis, and F. Gullo. Fast reliability search in uncertain graphs. In EDBT, 2014.


  1. Panos Parchas, Francesco Gullo, Dimitris Papadias, Francesco Bonchi. Uncertain Graph Processing through Representative Instances. ACM Transactions on Database Systems 40, 1–39 (2015). Link