gSpan: graph-based substructure pattern mining

By Xifeng Yan, Jiawei Han. 2002

2,497 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Text Categorization as a Graph Classification Problem (2015, methodology): “We used gSpan (graph-based Substructure pattern (Yan and Han, 2002)) as frequent sub-graph miner like (Jiang et al., 2010; Arora et al., 2010) mostly because of its fast available C++ implementation from gBoost (Saigo et al., 2009).”
A brief survey on anonymization techniques for privacy preserving publishing of social network data (2008, methodology): “To facilitate the isomorphism tests among neighborhoods of different vertices which will be conducted frequently in anonymization, a simple yet effective neighborhood component coding technique based on minimal DFS code [35] was proposed which represents neighborhoods in a concise way.”
Graph indexing: a frequent structure-based approach (2004, methodology): “Since each graph can have many diﬁerent DFS search trees and each of them has a DFS code, a lexicographic order is designed in [20, 21] to order the DFS codes.”
A Survey of Sequential Pattern Mining (2017, background): “Graph mining is a quite challenging task because the search space can be very large even for small graph databases and it is necessary to de-sign strategies to check if diﬀerent generated graphs are isomorphic [110].”
Near-optimal Supervised Feature Selection among Frequent Subgraphs (2009, methodology): “To avoid this overhead, non-Apriori-based algorithms such as gSpan [30], MoFa [2], FFSM [14], and Gaston [24] adopt the patterngrowth methodology, which attempts to extend graphs from a single subgraph directly.”
State of the art of graph-based data mining (2003, background): “More recently, DFS based canonical labeling approach called gSpan (graph-based Substructure pattern mining) has been proposed [24].”
oddball: Spotting Anomalies in Weighted Graphs (2010, methodology): “Frequent subgraph mining [18, 30] is used to detect non-crashing bugs in software flow graphs [22].”
Polonium: Tera-Scale Graph Mining and Inference for Malware Detection (2011, background): “Data points on the left generally represent new machines that have not submitted many file reports yet; with time, these points (machines) gradually move towards the right to join the dominant distribution.”
Text Classification using Graph Mining-based Feature Extraction (2010, background): “Frequent subgraph (and sub-tree) mining, using various app ro ches, has been extensively studied [9, 10, 22, 8, 2].”
Multiple Structure-View Learning for Graph Classification (2018, methodology): “To solve this issue, a commonly used subgraph estimation criterion (i.e., discovering all frequent subgraphs) is proposed by Yan and Han [17].”
Mining significant graph patterns by leap search (2008, methodology): “Frequent subgraph mining has been extensively studied in data mining community with various efficient algorithms developed such as AGM [12], FSG [16], and gSpan [26], followed by Path-Join, MoFa, FFSM, SPIN, Gaston, and so on.”
Multi-graph-view Learning for Graph Classification (2014, methodology): “Alternatively, we employ a Depth-First-Search (DFS) based algorithm gSpan [10] to iteratively enumerate subgraphs.”
Efficient aggregation for graph summarization (2008, methodology): “Methods that mine graphs for frequent patterns [11, 19, 20, 23] are also employed to understand the characteristics of large graphs.”
Finding Frequent Patterns in a Large Sparse Graph* (2004, methodology): “In recent years, a number of efficient and scalable algorithms have been developed to find patterns in the graph-transaction setting (Borgelt and Berthold, 2002; Yan and Han, 2002; Inokuchi et al., 2003; Hong et al., 2003; Yan and Han, 2003; Huan et al., 2003; Kuramochi and Karypis, 2004a).”