Skip to main content

Implementation of frequent subgraph mining algorithm gSpan

Project description


For Chinese readme, please go to README-Chinese.

gSpan is an algorithm for mining frequent subgraphs.

This program implements gSpan with Python. The repository on GitHub is This implementation borrows some ideas from gboost.

Undirected Graphs

This program supports undirected graphs, and produces same results with gboost on the dataset graphdata/

Directed Graphs

So far(date: 2016-10-29), gboost does not support directed graphs. This program implements gSpan for directed graphs. More specific, this program can mine frequent directed subgraph that has at least one node that can reach other nodes in the subgraph. But correctness is not guaranteed since the author did not do enough testing. After running several times on datasets graphdata/ and, there is no fault.

How to install

This program supports both Python 2 and Python 3.

Method 1

Install this project using pip:

pip install gspan-mining
Method 2

First, clone the project:

git clone
cd gSpan

You can optionally install this project as a third-party library so that you can run it under any path.

python install

How to run

The command is:

python -m gspan_mining [-s min_support] [-n num_graph] [-l min_num_vertices] [-u max_num_vertices] [-d True/False] [-v True/False] [-p True/False] [-w True/False] [-h] database_file_name 
Some examples
  • Read graph data from ./graphdata/, and mine undirected subgraphs given min support is 5000
python -m gspan_mining -s 5000 ./graphdata/
  • Read graph data from ./graphdata/, mine undirected subgraphs given min support is 5000, and visualize these frequent subgraphs(matplotlib and networkx are required)
python -m gspan_mining -s 5000 -p True ./graphdata/
  • Read graph data from ./graphdata/, and mine directed subgraphs given min support is 5000
python -m gspan_mining -s 5000 -d True ./graphdata/
  • Print help info
python -m gspan_mining -h

The author also wrote example code using Jupyter Notebook. Mining results and visualizations are presented. For detail, please refer to main.ipynb.

Running time

  • Environment

    • OS: Windows 10
    • Python version: Python 2.7.12
    • Processor: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz 3.60 GHz
    • Ram: 8.00 GB
  • Running time On the dataset ./graphdata/, running time is listed below:

Min support Number of frequent subgraphs Time
5000 26 51.48 s
3000 52 69.07 s
1000 455 3 m 49 s
600 1235 7 m 29 s
400 2710 12 m 53 s


gSpan: Graph-Based Substructure Pattern Mining, by X. Yan and J. Han. Proc. 2002 of Int. Conf. on Data Mining (ICDM'02).

One C++ implementation of gSpan.

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

gspan_mining-0.2.3.tar.gz (9.0 kB view hashes)

Uploaded source

Built Distribution

gspan_mining-0.2.3-py3-none-any.whl (10.6 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page