Mining of Top-K Subgraphs From Uncertain Graph Data
Ishan Choubey, Rage Uday Kiran, Nivesh Mittapally, P. Krishna Reddy · 2025
A graph transactional database (GTD) is a collection of graphs. Frequent Top-k Subgraph Pattern Mining involves finding the complete set of top-k frequently occurring subgraph patterns in a GTD. Most previous studies focused on finding these patterns in certain graphs by disregarding the crucial information regarding the existential probabilities that may exist between the edges of any two nodes. With this motivation, this paper proposes a novel model to discover top-k (frequently occurring) subgraphs in an uncertain graph transactional database. We introduce a novel algorithm, top-k uncertain subgraph miner (TUSM), to find all top-k subgraphs in the data. We also introduce an approximate top-k uncertain subgraph miner (ATUSM) algorithm to tackle the computational expansiveness of TUSM. Experimental results on synthetic and protein-protein interaction datasets demonstrate that the proposed model finds valuable information and the algorithms are efficient.