Graph indexing: a frequent structure-based approach

By Xifeng Yan, Philip S. Yu, Jiawei Han. ACM SIGMOD Conference, 2004

735 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/021abd34e933f03f6ba5a832e484ff0d57946732

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

Discriminative Frequent Pattern Analysis for Effective Classification (2007, background): “broad applications in areas like association rule mining, indexing, and clustering [1, 23, 20].”
TALE: A Tool for Approximate Large Graph Matching (2008, methodology): “To reduce the search space, GraphGrep [13], GIndex [19] and TreePi [22] index substructures of the database (paths, frequent subgraphs and trees respectively) to filter out graphs that do not match the query.”
GADDI: distance index based subgraph matching in biological networks (2009, methodology): “When the database of interests is composed of many small or medium sized graphs, GraphGrep [38, 16], GIndex [46] and TreePi [51] use substructures (paths, frequent subgraphs and trees respectively) to filter out graphs that do not match the query.”
Comparing Stars: On Approximating Graph Edit Distance (2009, background): “Srinivasa et al. build multiple abstract graphs[27], gIn-dex [34] uses the discriminative frequent structures, C-Tree [13] adopts graph closure, SAGA [28] employs pathway fragments, cIndex [9] adopts contrast subgraphs while Tree + ∆ [37] exploits frequent tree-features(Tree) and a small number of…”
TrGraph: Cross-Network Transfer Learning via Common Signature Subgraphs (2015, methodology): “In this work, we also adopt the idea of graph transfer but focus on non-streaming scenarios for cross-network node classification.”
Substructure similarity search in graph databases (2005, methodology): “tain the query graph, or vice versa [19, 20, 25]; and (3) full structure similarity search: find structures that are similar to the query graph [17, 24, 18].”
SPIN: mining maximal frequent subgraphs from graph databases (2004, background): “There are also many applications in data management research such as efﬁcient storage of semi-structured databases [5], efﬁcient indexing [21], and web information management [16].”
Large-scale malware indexing using function-call graphs (2009, methodology): “To reduce the search space, several indexing techniques have been proposed using frequent features, including GraphGrep [31], GIndex [37], Tree+∆ [44] and TALE [33], which use paths, graphs, trees and important nodes, respectively, as the main frequent feature to remove graphs that do not match the ”
Closure-Tree: An Index Structure for Graph Queries (2006, background): “[11] proposed GIndex that uses frequent patterns as index features.”
GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph (2014, background): “Mining frequent subgraphs is a central and well studied problem in graphs, and plays a critical role in many data mining tasks that include graph classification [9], modeling of user profiles [11], graph clustering [15], database design [10] and index selection [31].”
Taming verification hardness: an efficient algorithm for testing subgraph isomorphism (2008, methodology): “De-fault real dataset is a subset containing 10K graphs, which is ﬁrstly used in [16] and can be downloaded from http://www. xifengyan.net/software.htm .”
Graph Matching Networks for Learning the Similarity of Graph Structured Objects (2019, background): “The similarity is typically deﬁned by either exact matches (full-graph or sub-graph isomorphism) (Berretti et al., 2001; Shasha et al., 2002; Yan et al., 2004; Srinivasa & Kumar, 2003) or some measure of structural similarity, e.g. in terms of graph edit distances (Willett et al., 1998; Ray-mond et…”
Preserving Privacy in Social Networks Against Neighborhood Attacks (2008, background): “The general graph isomorphism problem which determines whether two graphs are isomorphic is NP-hard [17].”
Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases (2013, methodology): “There are graph-index based subgraph isomorphism algorithms such as gIndex [17, 18], FG-Index [2], Tree+Δ [22], SwiftIndex [12], C-Tree [19], and gCode [23].”
gStore: Answering SPARQL Queries via Subgraph Matching (2011, methodology): “Although many subgraph matching methods have been proposed (e.g., [17, 24]), they are not scalable to very large graphs.”
An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases (2012, background): “The ﬁrst subcategory includes Graph-Grep [12], gIndex [16], FG-Index [1], Tree+Δ [19], gCode [20], SwiftIndex [11], and C-Tree [4].”
A survey of frequent subgraph mining algorithms (2012, neutral): “, 2004; Newman, 2004; Huang & Lai, 2006) Graph indexing (Shasha et al., 2002; Yan et al., 2004) Graph searching (Yan et al.”