ke function to detect edge labels in subgraph_matching kernel not working.

[georgia-max]

Describe the bug
I am trying to get the similarity scores between the two graphs using the SubgraphMatching Kernel, that take into account both node labels and edge labels : SubgraphMatching(normalize=True, ke=custom_edge_kernel, kv = custom_label_kernel)

This should result in a score that is not equal to 1 since one of the edge_labels is different. However, I am getting a score of 1.

To Reproduce

from grakel import Graph
from grakel.kernels import SubgraphMatching

# Define a custom edge kernel function
def custom_edge_kernel(label1, label2):
    # Example: Assign partial similarity for mismatched labels
    print(label1, label2)
    if label1 == label2:
        return 1  # Perfect match
    else:
        return 0.5  # Partial similarity for mismatched labels
def custom_label_kernel(label1, label2):
    # Example: Assign partial similarity for mismatched labels
    # print(label1, label2)
    if label1 == label2:
        return 1  # Perfect match
    else:
        return 0.5  # Partial similarity for mismatched labels

# Define two graphs with labeled edges and nodes
graph1 = {
    "edge": {(0, 1):1, (1, 2):1},
    # "edge": {0:{1:1}, 1:{2:1}},
    "node_labels": {0: 'A', 1: 'B', 2: 'A'},
    "edge_labels": {(0, 1): 'X', (1, 2): 'Z'}  # Edge labels
}

graph2 = {
    "edge": {(0, 1):1, (1, 2):1},
    # "edge": {0:{1:1}, 1:{2:1}},

    "node_labels": {0: 'A', 1: 'B', 2: 'A'},
    "edge_labels": {(0, 1): 'X', (1, 2): 'Y'}  # Note: Different edge label 'Z'
}

# Create Graph objects
G1 = Graph(
    initialization_object = graph1["edge_labels"], 
    node_labels=graph1["node_labels"], 
    edge_labels=graph1["edge_labels"], 
    graph_format="all"
)
G2 = Graph(
    initialization_object = graph2["edge_labels"], 
    node_labels=graph2["node_labels"], 
    edge_labels=graph2["edge_labels"], 
    graph_format="all"
)


# Initialize Subgraph Matching Kernel with custom edge kernel
sm_kernel = SubgraphMatching(normalize=True, ke=custom_edge_kernel, kv = custom_label_kernel)

# Compute the kernel matrix
K = sm_kernel.fit_transform([G1, G2])

# Output the kernel matrix
print("Kernel Matrix:")
print(K)

my result running the code is:

Kernel Matrix: [[1. 1.] [1. 1.]]

[Astromis]

@georgia-max

Hello. Wondered by this issue. Sad that maintainer still haven't answered.

My investigation leads me to this part of code from here

You see that the edge kernel computes if the edge is somewhat called "c-edge". The root of this definition is in this paper.

Though for now I don't have the understanding what it means and why not all differences are significant but besides the issue I can assume that the test graph you provided is too small and simple so it is covered by two conditions before the KE calculation. I verified it by printing the values from value.

[giannisnik]

Hi @georgia-max and @Astromis ,

This happens because the SubgraphMatching Kernel expects directed graphs as input. While your graphs are undirected, you have not added the reverse edges. Thus, if you also add edges (1,0) and (2,1) in the dictionaries of the two graphs, the off-diagonal values of the kernel matrix are smaller than 1. See the example below.

from grakel import Graph
from grakel.kernels import SubgraphMatching

# Define a custom edge kernel function
def custom_edge_kernel(label1, label2):
    # Example: Assign partial similarity for mismatched labels
    print(label1, label2)
    if label1 == label2:
        return 1  # Perfect match
    else:
        return 0.5  # Partial similarity for mismatched labels
def custom_label_kernel(label1, label2):
    # Example: Assign partial similarity for mismatched labels
    # print(label1, label2)
    if label1 == label2:
        return 1  # Perfect match
    else:
        return 0.5  # Partial similarity for mismatched labels

# Define two graphs with labeled edges and nodes
graph1 = {
    "edge": {(0, 1):1, (1, 2):1, (1, 0):1, (2, 1):1},
    # "edge": {0:{1:1}, 1:{2:1}},
    "node_labels": {0: 'A', 1: 'B', 2: 'A'},
    "edge_labels": {(0, 1): 'X', (1, 2): 'Z', (1, 0): 'X', (2, 1): 'Z'}  # Edge labels
}

graph2 = {
    "edge": {(0, 1):1, (1, 2):1, (1, 0):1, (2, 1):1},
    # "edge": {0:{1:1}, 1:{2:1}},

    "node_labels": {0: 'A', 1: 'B', 2: 'A'},
    "edge_labels": {(0, 1): 'X', (1, 2): 'Y', (1, 0): 'X', (2, 1): 'Y'}  # Note: Different edge label 'Z'
}

# Create Graph objects
G1 = Graph(
    initialization_object = graph1["edge_labels"], 
    node_labels=graph1["node_labels"], 
    edge_labels=graph1["edge_labels"], 
    graph_format="all"
)
G2 = Graph(
    initialization_object = graph2["edge_labels"], 
    node_labels=graph2["node_labels"], 
    edge_labels=graph2["edge_labels"], 
    graph_format="all"
)


# Initialize Subgraph Matching Kernel with custom edge kernel
sm_kernel = SubgraphMatching(normalize=True, ke=custom_edge_kernel, kv = custom_label_kernel)

# Compute the kernel matrix
K = sm_kernel.fit_transform([G1, G2])

# Output the kernel matrix
print("Kernel Matrix:")
print(K)

Then, the resulting matrix is:

Kernel Matrix:
[[1.      0.90625]
 [0.90625 1.     ]]