Unweighted, Unlabeled GraphΒΆ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''An example of similarity comparison between unlabeled and unweighted graphs
using the marginalized graph kernel.

Note: it is known that all unlabeled and unweighted graphs are identical under
the similarity metric defined by the marginalized graph kernel. This example
merely illustrates the usage of the package.'''
import numpy as np
import networkx as nx
from graphdot import Graph
from graphdot.kernel.marginalized import MarginalizedGraphKernel
from graphdot.microkernel import Constant

# 0 -- 1
g1 = nx.Graph()
g1.add_node(0)
g1.add_node(1)
g1.add_edge(0, 1)

# 0 -- 1 -- 2
g2 = nx.Graph()
g2.add_node(0)
g2.add_node(1)
g2.add_node(2)
g2.add_edge(0, 1)
g2.add_edge(1, 2)

# 0 --- 1
#  \  /
#   2
g3 = nx.Graph()
g3.add_node(0)
g3.add_node(1)
g3.add_node(2)
g3.add_edge(0, 1)
g3.add_edge(0, 2)
g3.add_edge(1, 2)

# define trivial node and edge kernelets
knode = Constant(1.0)
kedge = Constant(1.0)

# compose the marginalized graph kernel and compute pairwise similarity
mlgk = MarginalizedGraphKernel(knode, kedge, q=0.05)

R = mlgk([Graph.from_networkx(g) for g in [g1, g2, g3]])

# normalize the similarity matrix
d = np.diag(R)**-0.5
K = np.diag(d).dot(R).dot(np.diag(d))

# all entries should be approximately 1 plus round-off error
print(K)

Exptected output:

[[1.         0.99999963 1.00000005]
 [0.99999963 1.         0.99999958]
 [1.00000005 0.99999958 1.        ]]