Difference between ShortestPath and ShortestPathAttr

[kaidi-g]

What's the difference between ShortestPath and ShortestPathAttr. I do not understand what the description "The Graph labels are considered as attributes" mean. Can any examples be provided to illustrate it? Thank you very much!

[giannisnik]

Hi @kaidi-g ,

The main difference is that ShortestPathAttr is designed for graphs whose nodes are annotated with continuous attributes (i.e., vectors), while ShortestPath for graphs whose nodes are annotated with discrete labels or unlabeled graphs.

For instance, in the example below, each node is annotated with a vector (e.g., node 1 of graph G1 is annotated with [1.2, 0.5]):

from grakel.graph import Graph
from grakel.kernels import ShortestPathAttr

edges = {1: [2, 3], 2: [1], 3: [1]}
node_attributes = {1: [1.2, 0.5], 2: [2.8, -0.6], 3: [0.7, 1.1]}
G1 = Graph(edges, node_labels=node_attributes)

edges = {1: [2, 3], 2: [1,3], 3: [1,2]}
node_attributes = {1: [1.4, 0.2], 2: [3.1, -0.4], 3: [1.2, 0.9]}
G2 = Graph(edges, node_labels=node_attributes)

Gs = [G1, G2]

sp = ShortestPathAttr()
K = sp.fit_transform(Gs)

In the next example, the nodes of the two graphs are annotated with discrete labels (e.g., node 1 of graph G1 is annotated with 'a'):

from grakel.graph import Graph
from grakel.kernels import ShortestPath

edges = {1: [2, 3], 2: [1], 3: [1]}
node_labels = {1: 'a', 2: 'b', 3: 'a'}
G1 = Graph(edges, node_labels=node_labels)

edges = {1: [2, 3], 2: [1,3], 3: [1,2]}
node_labels = {1: 'a', 2: 'b', 3: 'b'}
G2 = Graph(edges, node_labels=node_labels)

Gs = [G1, G2]

sp = ShortestPath()
K = sp.fit_transform(Gs)

Thus, in the first example, we use the ShortestPathAttr kernel, while in the second example, the ShortestPath kernel. Keep in mind that ShortestPathAttr is computationally very expensive and does not scale to large graphs/datasets.

[kaidi-g]

Oh, I've got it! Thank you very much for your detailed reply! @giannisnik