Weighted, Node- and Edge-Labeled 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
55
56
57
58
59
60
61
#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''An example of similarity comparison between both node- and edge-labeled,
weighted graphs using the marginalized graph kernel.

This is the scenario that takes full advantage of the marginalized graph
kernel frame.
'''
import numpy as np
import networkx as nx
from graphdot import Graph
from graphdot.kernel.marginalized import MarginalizedGraphKernel
from graphdot.kernel.basekernel import TensorProduct
from graphdot.kernel.basekernel import SquareExponential
from graphdot.kernel.basekernel import KroneckerDelta

# {1.0, 1} --{1.5}[1.0]-- {2.0, 1}
g1 = nx.Graph()
g1.add_node(0, radius=1.0, category=1)
g1.add_node(1, radius=2.0, category=1)
g1.add_edge(0, 1, w=1.0, length=1.5)

# {1.0, 1} --{1.5}[1.0]-- {2.0, 1} --{2.0}[2.0]-- {1.0, 2}
g2 = nx.Graph()
g2.add_node(0, radius=1.0, category=1)
g2.add_node(1, radius=2.0, category=1)
g2.add_node(2, radius=1.0, category=2)
g2.add_edge(0, 1, w=1.0, length=1.5)
g2.add_edge(1, 2, w=2.0, length=2.0)

# {1.0, 1} --{1.5}[1.0]-- {2.0, 1}
#     \                    /
#      \                 /
#   {2.0}[0.5]      1.0}[2.0]
#        \           /
#         \        /
#          {1.0, 2}
g3 = nx.Graph()
g3.add_node(0, radius=1.0, category=1)
g3.add_node(1, radius=2.0, category=1)
g3.add_node(2, radius=1.0, category=2)
g3.add_edge(0, 1, w=1.0, length=1.5)
g3.add_edge(0, 2, w=0.5, length=2.0)
g3.add_edge(1, 2, w=2.0, length=1.0)

# define node and edge kernelets
knode = TensorProduct(radius=SquareExponential(1.0),
                      category=KroneckerDelta(0.5))

kedge = TensorProduct(length=SquareExponential(1.0))

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

R = mlgk([Graph.from_networkx(g, weight='w') 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))

print(K)

Exptected output:

[[1.         0.50970827 0.52433483]
 [0.50970827 1.         0.71869168]
 [0.52433483 0.71869168 1.        ]]