Incorrect GED result on synthetic experiment

[henrykenlay]

Thank you for writing this library, it's very useful. I'm trying to use gedlibpy to compute GED on small graphs. I'm doing an experiment where I perturb a graph by deleting an edge and checking to see if gedlibpy would compute the GED to be one. I'm using ANCHOR_AWARE_GED which returns a lower and upper bound (if it doesn't time out). These bounds are equal, so if I'm understanding the gedlibpy.get_lower_bound and gedlibpy.get_upper_bound functions correctly (true lower and upper bounds to the GED) these should be equal to 1. However, this is not the case. Below is some code to demonstrate.

import sys
sys.path.append('/home/ubuntu/research/gedlib/gedlibpy')
import librariesImport  
import gedlibpy 
import numpy as np
import networkx as nx
import scipy.sparse as sp

def remove_edge(graph: nx.graph) -> nx.graph:
    """Deletes an edge at random"""
    edge_idx = np.random.choice(range(graph.number_of_edges()))
    u, v = list(graph.edges())[edge_idx]
    graph.remove_edge(u, v)
    return graph

def tosparse(graph: nx.graph) -> sp.graph:
    return nx.to_scipy_sparse_matrix(graph).tolil()

def register_ged_graph(graph: sp.spmatrix) -> int:
    """Register a graph to use with the gedlibpy library."""
    us, vs = graph.nonzero()
    nodes = set(us)
    id = gedlibpy.add_graph('', '')
    for node in nodes:
        gedlibpy.add_node(id, str(node), {})
    for u, v in zip(us, vs):
        gedlibpy.add_edge(id, str(u), str(v), {}, ignore_duplicates=True)
    return id

def anchor_aware_ged(graph1, graph2, edit_cost='CONSTANT', timeout=0.2):
    lower, upper = _anchor_aware_ged(graph1, graph2, edit_cost, timeout)
    while lower != upper:
        lower, upper = _anchor_aware_ged(graph1, graph2, edit_cost, timeout)
    return lower, upper

def _anchor_aware_ged(graph1, graph2, edit_cost='CONSTANT', timeout=None):
    graph1_id = register_ged_graph(graph1)
    graph2_id = register_ged_graph(graph2)
    gedlibpy.set_edit_cost(edit_cost)
    gedlibpy.init()
    options = f'--time-limit {timeout}' if timeout is not None else ''
    gedlibpy.set_method('ANCHOR_AWARE_GED', options)
    gedlibpy.init_method()
    gedlibpy.run_method(graph1_id, graph2_id)
    lower, upper = gedlibpy.get_lower_bound(graph1_id, graph2_id), gedlibpy.get_upper_bound(graph1_id, graph2_id)
    gedlibpy.clear_graph(graph1_id)
    gedlibpy.clear_graph(graph2_id)
    return lower, upper

distances = []
for _ in range(10):
    g1 = nx.barabasi_albert_graph(20, 2)
    g2 = g1.copy()
    g2 = remove_edge(g2)
    lower, upper = anchor_aware_ged(tosparse(g1), tosparse(g2))
    assert lower == upper
    print(lower, end=' ')

I restart the GED computation if it times out so the lower and upper bound are always equal as checked by the assert statement. The output is 19.0 9.0 19.0 13.0 19.0 11.0 17.0 19.0 23.0 3.0 instead of the expected 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0. Is there an issue in how I'm using the library or my understanding of gedlibpy.get_lower_bound and gedlibpy.get_upper_bound? Thanks.

[weathon]

This should be posted on the main library
https://github.com/dbblumenthal/gedlib

[weathon]

I tried to remove an edge but there is no issue for me

[weathon]

I think I run into the same issue actually