Weighted Decomposition Kernel (WDK): 

A C++ implementation of a family of kernels on discrete data structures within the general class of decomposition kernels called weighted decomposition kernel (WDK) for discrete data structures (e.g. graphs and sequences). WDK is computed by dividing objects into substructures indexed by a selector. Two substructures are then matched if their selectors satisfy an equality predicate, while the importance of the match is determined by a probability kernel on local distributions fitted on the substructures. Under reasonable assumptions, a WDK can be computed efficiently and can avoid combinatorial explosion of the feature space.
Link 
Neighborhood Subgraph Pairwise Distance Kernel (NSPDK): 
The Neighborhood Subgraph Pairwise Distance Kernel decomposes a graph into all pairs of neighborhood subgraphs of small radius at increasing distances.
A fast graph invariant is used to obtain significant speedups in the Gram matrix computation.
Link 
EDeN (Explicit Decomposition with Neighborhoods): 
An updated version of the Neighborhood Subgraph Pairwise Distance Kernel can be used to induce an explicit feature representation for graphs. This in turn allows fast stochastic gradient descent methods to be applied for classification tasks or locality sensitive hashing methods for clustering tasks in linear time.

GraphMake: 
GraphMake is a (hyper)graph sampler that can take a set of graphs in input and output a set of samples that are likely to come from the same underlying distribution.
[Version 2.1 Mar 2013] Link[Beta] 