Ishan Choubey supervised by Prof. Krishna Reddy Polepalli received his Master of Science in  Computer Science and Engineering (CSE). Here’s a summary of his research work on Top-k Subgraph Mining in Uncertain Graph Transactional Databases

Many real-world relational datasets are naturally represented as graphs, but the relationships they contain are often not observed with complete certainty. In biological interaction networks, for example, an edge may be supported by experimental evidence, database integration, or computational prediction, and is therefore more appropriately associated with a confidence value than treated as certainly present or absent. This motivates the use of uncertain graph transactional databases, where each transaction is an uncertain graph and each edge is associated with an existence probability. Mining recurring subgraphs from such databases is useful for identifying structural patterns that persist across uncertain graph collections, but it also changes the meaning and cost of support computation. In certain graph transactional databases, frequent and top-k subgraph mining have been studied extensively, and the support of a pattern is computed by counting the number of graphs in which it occurs. In uncertain graph transactional databases, however, subgraph occurrence is probabilistic because each uncertain graph may realise into multiple certain graphs depending on which uncertain edges exist. Support must therefore be evaluated through expected support rather than deterministic frequency, and computing the occurrence probability of a subgraph becomes substantially more expensive. Existing deterministic top-k subgraph mining methods avoid the difficulty of selecting a minimum-support threshold, but they assume certain graph transactions. Existing uncertain frequent subgraph mining methods account for edge uncertainty, but they are primarily formulated as threshold-based mining problems. The problem addressed in this thesis lies at the intersection of these two settings: mining top-k subgraphs from uncertain graph transactional databases using expected support as the ranking criterion. This thesis formulates the top-k uncertain subgraph mining problem without relying on a user-specified minimum-support threshold and develops two algorithmic frameworks for solving it. The first is an exact method, called Top-k Uncertain Subgraph Miner (TUSM), which explores the candidate subgraph space using best-first search and computes exact expected support through occurrence-probability evaluation. Since occurrence-probability computation is related to DNF counting, the exact method can become computationally expensive when candidate patterns have many embeddings. To reduce this cost, the thesis also proposes an approximate method, called Approximate Top-k Uncertain Subgraph Miner (ATUSM), which replaces exact support evaluation with a sampling-based approximation procedure. Because the approximate setting yields support intervals rather than exact values, ATUSM uses intervalbased comparison and probabilistic distribution queues to maintain candidate rankings during search. The proposed methods are evaluated on synthetic uncertain graph transactional datasets and on uncertain protein–protein interaction graphs derived from real-world biological data. The experimental results indicate that exact top-k uncertain subgraph mining is feasible on smaller datasets, but its runtime is dominated by exact expected-support computation. The approximate framework reduces runtime substantially and provides a practical alternative when exact mining becomes difficult, with the approximation behaviour influenced more strongly by ϵ than by δ. The real-world experiments further indicate that the framework can be applied to biologically grounded uncertain graph data after appropriate size control and preprocessing. Overall, the thesis establishes a threshold-free formulation of top-k subgraph mining for uncertain graph transactional databases and provides exact and approximate methods for studying this problem. 

June 2026