Mining of Top-K Subgraphs From Uncertain Graph Data

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.

• Publication year

  2025

• Venue

  IEEE International Conference on Fuzzy Systems

• Publication date

  2025-07-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/FUZZ62266.2025.11152279
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The STRING database in 2023: protein–protein association networks and functional enrichment analyses for any sequenced genome of interest

  2022cited by this paper
• A survey on mining and analysis of uncertain graphs

  2021cited by this paper
• Central Limit Theorem

  2021cited by this paper
• TKG: Efficient Mining of Top-K Frequent Subgraphs

  2019cited by this paper
• Efficient Mining of Frequent Patterns on Uncertain Graphs

  2019cited by this paper
• FS3: A sampling based method for top-k frequent subgraph mining

  2014cited by this paper
• A survey of frequent subgraph mining algorithms

  2012cited by this paper
• Graph mining: A survey of graph mining techniques

  2012cited by this paper
• Kullback-Leibler Divergence

  2011cited by this paper
• Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics

  2010cited by this paper
• TGP: Mining Top-K Frequent Closed Graph Pattern without Minimum Support

  2010cited by this paper
• Frequent subgraph pattern mining on uncertain graph data

  2009influential reference
• An efficient algorithm for discovering frequent subgraphs

  2004cited by this paper
• Efficient mining of frequent subgraphs in the presence of isomorphism

  2003cited by this paper
• gSpan: graph-based substructure pattern mining

  2002cited by this paper
• An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data

  2000cited by this paper
• Monte-Carlo Approximation Algorithms for Enumeration Problems

  1989cited by this paper

• No citing papers are available for this paper.