A measure of the similarity of two weighted multigraphs?
To compare shapes, typically obtained after image segmentation, it has been shown that their skeleton could be used. A
search with the keywords : skeleton+pruning+image+recognition yields a lot of results.

From the skeleton of the B character (left) to its associated (networkx) graph (right). 
Previously, pruning of skeletons was performed by removing pixels, one after an other, from the endpoints by morphological hitormiss. A response curve of a skeleton to pruning, can be defined by counting the endpoints of the skeleton as pruning is iterated. It was observed that the responses from similar shapes were similar. So, such response curves may be used to compute some similarity measures, or distances, between shapes.
The time necessary to prune a skeleton depends on its number of pixels. So it may be worth prior pruning to convert a skeleton into a graph. Thus pruning a graph could be independent from the weight of its edges.
The response of a a weighted multigraph to iterative pruning was performed with
graphtool (and additionnal python librairies : mahotas, numpy, scipy,
matplotlib). This response yields a curve: a "
Response to
Pruning
Curve" or RPC. Then a distance was defined between two RPCs, to compute a similarity index between two graphs.
The graph tool version used is:
2.11 (commit b6b2152c, Mon Oct 26 10:31:30 2015 +0100)
Algorithm for pruning a graph from its leaves :
 Make a weighted undirectional multigraph
 (Visualize it)
 Start pruning:
 Count the vertices on degree 1
 Read the weight of the edges bound to vertices of degree1 (V1)
 Get the edge(s) of minimal weight
 Remove this/these edge(s)
 Decrease the weight of the other edges bound to vertices v1 by this minimal weight
 Do it until no more vertices of degree 1 remains
 Cumulate the weight of removed edges
 The response to pruning of a graph, associates the number of degree1 vertices to the cumulative weight of the removed edges.
Make a toygraph to play with:
By default in graphtool, the graphs are multigraphs and that's what we
need. The edges of the graph must be weighted, this property has to be created. The weight
of an edge corresponds to the size of a branch in a skeleton (the number of
pixels). The following python code, shows the creation of a graph with an edge property called 'weight':
The graph can be displayed such that the thickness of its edges maps to the weight of edges:
Start to prune the graph:
Two different versions of the pruning function were written. The second called prune_once_faster() depends on the GraphView() method of the graphtool library to filter vertices of degree 1, hopping to make a faster function:
The pruning function is destructive, applying it iteratively on the same graph yields, if you write in a jupyter cell:
G0 = make_toy_graph()
g0 = G0.copy()
prune_graph_once(g0)
g1 = g0.copy()
prune_graph_once(g0)
g2 = g0.copy()
prune_graph_once(g0)
g3 = g0.copy()
print G0, number_of_degree1_vertices(G0)
print g1, number_of_degree1_vertices(g1)
print g2, number_of_degree1_vertices(g2)
print g3, number_of_degree1_vertices(g3)
You will have as output:
<Graph object, undirected, with 4 vertices and 4 edges at 0x9c65c1ac> 2
<Graph object, undirected, with 4 vertices and 3 edges at 0x9c65cc2c> 1
<Graph object, undirected, with 4 vertices and 2 edges at 0x9c654dec> 1
<Graph object, undirected, with 4 vertices and 1 edge at 0x9c65424c> 0
Indicating that the number of edges decreases as the number of vertices of degree 1, each time the graph is pruned.
Pruning iteratively a graph:
Let's count the number of vertices of degree 1 as the graph is pruned. The toy graph used here to check its response, has two vertices of degree 3 and two vertices of degree 1 (vertices 2 an 3). The initial values of the weight of the edges bound to vertices 2 and 3, are :
15, 20
The smallest weight is 15 So after one pruning, the weights becomes:
1515 = 0, 2015 = 5
The edge 12 of weight 0 is removed (vertex 2 is now of degree 0).
The edge 13 has the smallest weight (5).
So after a second round of pruning, the edge 13 is removed.
The vertex 1 was of degree 2, now it is of 1. The weight of the edge 01 is 8.
A third pruning removes the last edge 01 of weight equal to 8.
The degree of vertex 0 is 2 (there's a loop), so the edge 00 can't be pruned. The different weights are cumulated as follow:
0, 15, 15+5, 20+8
Applied to a skeleton made of pixels, this would mean that:
 15 prunings of 1 pixel would remove one branche of size 15.
 20 prunings would remove the two branches of size 15 and 20.
 28 prunings would remove the three branches of sizes 15, 20 and 8 (initially between two vertices of degree 3).
The weights are stored in a vector X .
The corresponding counts of degree 1 vertices are stored in a vector Y.
Both X,Y are returned by the function
response_to_iterative_pruning()
Make a feature vector from the pruning curve?
A response curve was plotted as a step curve:
The upper curve is the response when the weight of edges are used. In the lower one, the weights were normalised by the total weights of the graph (% total length or total weight), hopping to produce a scale invariant response. For the following, only the raw response will be used.
Distance between two graphs:
First, we need new toy graphs to compare them. The second new graph differe from the first only by its weight:
The third one has no loop:
A fourth has a loop elsewhere:
The response of the three first graphs are:

Overlayed responses of first and third graph (right) 
We could try to compute the area between two step curves. For two
identical curves the area would be null, as the curves differe the area
may increase. Fine!
However, the curves are just defined from
discrete data, it may not be so easy to define for such kind of integration.
Let's forget the curves and just look at the points from the
scatter plot. When looking at two pruning curves obtained from toygraphs
2 and 3, we could just compute the distances matrix between the points
from the two curves. The more the curves are different, the more the
distances should increase ... why not, give it a try:
scipy provides just what we need!
The response curve is given as (X, Y) with
 Y : the corresponding number of leaf in the graph (vertices of degree 1)
First, let's compute the distances between the points of the same curve:
T=make_toy_graph()
X, Y = response_to_iterative_pruning(T.copy())
pruning_curve = zip(X,Y)
D = cdist( pruning_curve, pruning_curve)
print D
Thanks to scipy, we get a 4x4 (since the graph has four vertices) matrix of distances D :
[[ 0. 15.03329638 20.02498439 28.0713377 ]
[ 15.03329638 0. 5. 13.03840481]
[ 20.02498439 5. 0. 8.06225775]
[ 28.0713377 13.03840481 8.06225775 0. ]]
Which can be displayed as an image (the matrix is symetric, only upper element are displayed):
For each of the three first graphs T,T1,T2 , one can define 32−32+3=6 matrices of distances.
Those matrices are elements of another matrix (a matrix of matrices).
The elements of the diagonal are squared matrices corresponding to
"intradistances" (distances between the points of the same response
curve).
The elements outside the diagonal correspond to
"interdistances" matrices (distances computed from points belonging to
two different response curves), the "interdistance matrices", here, can be rectangular if the corresponding pairs of graphs do not have the same
number of vertices (and square if the two graphs have the same number of vertices):
For each matrix, the total distance can be computed as the sum of their elements. This yields:
[[ 178. 187. 256.]
[ 0. 105. 135.]
[ 0. 0. 140.]]
At first sight, this is not good, elements outside the diagonal (total distance between two response curves, that is the distance between two graphs) should be greater than those of the diagonal.
Defining a normalized distance between two graphs
We try to heal this situation by normalising the interdistances . The total interdistances is normalized by the sum of total
intradistances. The total inter distances is multiplied by two in order
to have a normalised distance:
nD .
nD(responsecurvei,responsecurvei)=1
When conputed against the pair of same response curve, the normalized distance equals 1 as wished.
Finally
nD is computed as follow:
nD(ri,rj)=12distance(ri,rj)ri+rj=ri+rj2distance(ri,rj)
such that:
nD(ri,rj)<=1
Let's see the matrix of normalised distance on the three first graphs:
[[ 1. 0.75751403 0.62186779]
[ 0. 1. 0.90636131]
[ 0. 0. 1. ]]
As an image:
This seems better. With that distance, the similarity of a graph on itself is 1 and two different graphs have a similarity bellow 1. It remains to see if that distance can discriminate between graphs of interest possibly after supervised classification.