Frequent Graph Pattern Mining Algorithms

[Peter Belcak]

Hello,

I wonder what the contribution policy is regarding the frequent (sub-)graph pattern mining algorithms. These tend to be quite expensive in terms of computational resources but are very useful nevertheless. I've working on an implementation of gSpan and looking into Gaston as a part of my research and now I'm thinking they could also form a nice part of NetworkX.

Anyone with any insight or strong opinion? I had searched the mailing list and found only one mention of gSpan from 2014, and that person was only asking whether it would ever be implemented in Python.

Best,

Peter

[Dan Schult]

We are interested in algorithms that "mine for" subgraph patterns. Our primary tools for this feature are in `algorithms/isomorphism`. Good links for gSpan and Gaston indicate that they are 1) implemented with licenses that are not compatible with inclusion into NetworkX, 2) not actively supported and 3) not pure python applications.  Each of these hurdles to inclusion can be overcome.  For example, if you are implementing your code in Python and based on the algorithms rather than simply porting their code, that could take care of 1 & 3. We would want good tests that are fairly complete to help us address 2) in the long run.

In summary, "yes" we are interested in such algorithms and so long as we can avoid license issues and non-python code it could be added to NetworkX.  Other perfectly good options include releasing a separate package that e.g. wraps the gSpan or Gaston code. In that case, an example in NetworkX could showcase how to use the separate package to do this work.