Finding Frequent Patterns in a Large Sparse Graph*

By Michihiro Kuramochi, George Karypis. Data mining and knowledge discovery, 2004

510 citations recorded by the source corpus.

Graph-based modeling has emerged as a powerful abstraction capable of capturing in a single and unified framework many of the relational, spatial, topological, and other characteristics that are present in a variety of datasets and application areas. Computationally efficient algorithms that find patterns corresponding to frequently occurring subgraphs play an important role in developing data mining-driven methodologies for analyzing the graphs resulting from such datasets. This paper presents two algorithms, based on the horizontal and vertical pattern discovery paradigms, that find the connected subgraphs that have a sufficient number of edge-disjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods for determining the number of edge-disjoint embeddings of a subgraph and employ novel algorithms for candidate generation and frequency counting, which allow them to operate on datasets with different characteristics and to quickly prune unpromising subgraphs. Experimental evaluation on real datasets from various domains show that both algorithms achieve good performance, scale well to sparse input graphs with more than 120,000 vertices or 110,000 edges, and significantly outperform previously developed algorithms.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b71822df8f25e3d1963b7323c6beee8e015393d0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Information Systems

In Signal Processing

Citations in the corpus

A survey of frequent subgraph mining algorithms (2012, methodology): “There are a variety of support measures (Vanetik, 2002; Kuramochi & Karypis, 2004c, 2005; Vanetik et al., 2006) that may be adopted for single graph-based FSM, these will be discussed further in Subsection 5.1.2.”
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations (2009, background): “, GraphSig [6], [7], [8], [9], gPrune [10], gApprox [11], gSpan [12], Subdue [13], HSIGRAM/VSIGRAM [14], ADI [15], CSV [16]), finding important nodes (e.”
GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph (2014, methodology): “The literature defines several anti-monotone support metrics such as minimum image based (MNI) [2], harmful overlap(HO) [12], andmaximum independent sets(MIS) [20].”
K-isomorphism: privacy preserving network publication against structural attacks (2010, background): “There are also different kinds of querying or knowledge discovery processing on social networks [17, 14, 25, 6, 5].”
K-Automorphism: A General Framework For Privacy Preserving Network Publication (2009, unknown): “Frequent Sub-graph [11].”
Mining coherent dense subgraphs across massive biological networks for functional discovery (2005, background): “Prior frequent graph mining approaches, mostly based on graph pattern expansion technique (Kuramochi and Karypis, 2004; Yanet al., 2005), iteratively extend frequent patterns and check their support.”
GADDI: distance index based subgraph matching in biological networks (2009, background): “There is some related work in mining frequent subgraphs in a large graph [32, 50, 6, 13, 42].”
A classification for community discovery methods in complex networks (2011, background): “Some examples of graph mining algorithms are [5, 159, 160, 161].”