Fitness function from NodeClustering object versus from evaluation module

[deklanw]

When I do this

from cdlib import evaluation as ev

...

cs = al.infomap(g)
print(f"Average internal degree {ev.average_internal_degree(g, cs)}")
print(f"Average internal degree {cs.average_internal_degree()}")

I get identical results. When I change the algorithm like this:

from cdlib import evaluation as ev

...

cs = al.leiden(g)
print(f"Average internal degree {ev.average_internal_degree(g, cs)}")
print(f"Average internal degree {cs.average_internal_degree()}")

The latter is FitnessResult(min=0, max=0, score=0.0, std=0.0 while the former looks fine.

And, for other algorithms the latter seems to be giving an error! max_odf with the former method works fine, but with the latter it throws a ValueError.

Am I confused about something or is this a bug?

[Yquetzal]

Thanks for the feedback, I could not reproduce the problem with a first test like this:

g = nx.karate_club_graph()
cs = al.leiden(g)
print(f"Average internal degree {ev.average_internal_degree(g, cs)}")
print(f"Average internal degree {cs.average_internal_degree()}")

which gives:

<class 'networkx.classes.graph.Graph'> Average internal degree FitnessResult(min=2.3333333333333335, max=4.181818181818182, score=3.103787878787879, std=0.7758948002447444) <class 'networkx.classes.graph.Graph'> Average internal degree FitnessResult(min=2.3333333333333335, max=4.181818181818182, score=3.103787878787879, std=0.7758948002447444)

I tried converting to an igraph graph obect first, but the result was the same. Does my example works as expected on your configuration? If yes, can you provide some more details about your graph object?

[deklanw]

def bug_test(g):
    cs = al.leiden(g)

    print(ev.average_internal_degree(g,cs))
    print(cs.average_internal_degree())
    print()
    print(ev.max_odf(g, cs))
    print(cs.max_odf())

First one gives different results, second one throws

FitnessResult(min=34.16326530612245, max=105.67914438502673, score=67.92433161554104, std=23.965434465640367)
FitnessResult(min=0, max=0, score=0.0, std=0.0)

FitnessResult(min=196, max=311, score=241.8, std=44.839268504292086)
Traceback (most recent call last):
  File "cdlibtest.py", line 249, in <module>
    go()
  File "cdlibtest.py", line 241, in go
    bug_test(g)
  File "cdlibtest.py", line 227, in bug_test
    print(cs.max_odf())
  File "/home/deklan/.local/lib/python3.7/site-packages/cdlib/classes/node_clustering.py", line 282, in max_odf
    return evaluation.max_odf(self.graph, self, **kwargs)
  File "/home/deklan/.local/lib/python3.7/site-packages/cdlib/evaluation/fitness.py", line 441, in max_odf
    return __quality_indexes(graph, community, pq.PartitionQuality.max_odf, **kwargs)
  File "/home/deklan/.local/lib/python3.7/site-packages/cdlib/evaluation/fitness.py", line 40, in __quality_indexes
    values.append(scoring_function(graph, community))
  File "/home/deklan/.local/lib/python3.7/site-packages/pquality/PartitionQuality.py", line 150, in max_odf
    return max(__out_degree_fraction(g, coms))
ValueError: max() arg is an empty sequence

Graph is directed, unweighted (well, all edges weight 1.0), 1273 nodes, 69408 edges, from a graphml file loaded via networkx.

https://mega.nz/#!v8xEwS7S!AaSYNfcbo6ztXuCUomxYIAHCLu9YqK-BVE4FyRt8eAY

And, yes, your example works for me too

[deklanw]

I figured out that utils.nx_node_integer_mapping fixes it. However, I'm still getting different values between the two ways of calling the fitness functions. And, my original graph works too when I call the relabel, for some reason. Does the relabel function mutate the original graph?

    g = nx.readwrite.read_graphml(FILENAME)
    relabelled, label_map = utils.nx_node_integer_mapping(g)

    cs = al.leiden(g)
    print(f"Max Odf {ev.max_odf(g, cs)}")
    print(f"Max Odf {cs.max_odf()}")

    print()

    cs2 = al.leiden(relabelled)
    print(f"Max Odf {ev.max_odf(relabelled, cs2)}")
    print(f"Max Odf {cs2.max_odf()}")

Max Odf FitnessResult(min=333, max=390, score=365.0, std=25.44798616786798)
Max Odf FitnessResult(min=252, max=354, score=299.0, std=42.792522711333575)

Max Odf FitnessResult(min=333, max=389, score=365.0, std=25.775957790157864)
Max Odf FitnessResult(min=252, max=355, score=300.6, std=41.773675921565726)

If I comment out the relabel line, max_odf throws again for the original graph.

[Yquetzal]

I think that I found 2 problems. The first one is a bug in the conversion from nx to igraph, if the name of nodes are integers, because in the __from_nx_to_igraph, nodes are added using add_vertices, which expect string (not int). It then makes problem laters in the code, I think some confusions between node names and nodes ID. I propose below a fix transforming to string, although it will somewhat alter performances. @GiulioRossetti , what do you think of this fix?

The second problem is that in our interface with leiden algorithm (and several others I think), we systematically convert the graph to undirected. In your case, the graph is originally directed, so that might introduce changes too. One fix for that would be to systematically conserve the directionality. i.e., by default, the call to __from_nx_to_igraph would conserve directionality, instead of the current behavior where, if no information on directionality is explicitly provided, the graph is converted to undirected. @GiulioRossetti am I right? Should I change the function accordingly?

Proposed changes:

def __from_nx_to_igraph(g, directed=None):
    """
    :param g:
    :param directed:
    :return:
    """

    if ig is None:
        raise ModuleNotFoundError(
            "Optional dependency not satisfied: install igraph to use the selected feature.")

    ####ADD TO KEEP DIRECTIONALITY BY DEFAULT
    if directed is None: 
        directed = g.is_directed()

    gi = ig.Graph(directed=directed)

    #gi.add_vertices(list(g.nodes()))
    gi.add_vertices([str(n) for n in g.nodes()]) ## proposed changed
    gi.add_edges([(str(u),str(v)) for (u,v) in g.edges()]) ## proposed changed
    #gi.add_edges(list(g.edges()))
    edgelist = nx.to_pandas_edgelist(g)
    for attr in edgelist.columns[2:]:
        gi.es[attr] = edgelist[attr]

    return gi

[GiulioRossetti]

@Yquetzal I completely agree on both points. Indeed the performances will suffer a little bit while working with strings but, in the end, we are not aiming at being super efficient at the moment. We can live with it (at least for now).

Regarding directedness: yes this is a huge bug to fix. Assuming every cd algorithm working only on undirected graphs has a huge cost in terms of reliability of results. The only issue to address here - before changing the actual behavior - is: how to deal with algorithms that do not support directed networks when a digraph is considered as input? Should we:

• Raise an error?
• Raise a warning and convert the input to undirected?
• Silently convert to undirected?

Maybe the second option is the more conservative one...

[Yquetzal]

The problem with warnings is that it is easy to miss them, for instance if someone try to launch automatically a bunch of algorithms, some red prints for some methods might stay unseen. Errors are more safe... It would force people to be aware that they apply a method not designed to work with their network. Otherwise we could imagine adding a flag for auto-conversion to undirected, but that would probably be overcomplexifying for little benefits. @GiulioRossetti I let you the final decision, both solutions are fine for me. In any case, we will need to check every method to see if they do accept directed graphs or not ...

[Yquetzal]

Or if we do nothing but always keep the directed/unidrected property, then we can for now let each method handle it as they want, it might be incoherent since some methods might silently convert to undirected in their code, while some other might simply fail...

[GiulioRossetti]

@Yquetzal let's raise errors then, it seems the more "pythonic" way to proceed. If it has to fail, let it fail loudly.

Could you implement/test the fix in a new branch?

When everything is ready, we can define a proper Exception (GraphNotSupportedException or something alike) to raise in case the check on the input graph underline an incompatibility with the user-selected algorithm. This could be a way to make understandable for the end-user the nature of the issue (and standardize failures in the process).

[Yquetzal]

Sure I'll do it ASAP

[Yquetzal]

I proposed a fix, @GiulioRossetti could you check briefly ? 1)I've proposed a way to handle both problems, it was a little more tricky than originally expected, I explain in the comments of the pull. 2)To avoid confusion in the future, I changed all CD functions so that they always associate to the returned clustering the original graph, and not the converted one. 3)I tested what happens with directed graphs with the test function, out of 47 methods, 13 fail (some might convert in the background without telling), and of these 13, 6 fail with an obscure message (CONGA, DER, lfm, em, modularity_max, LEMON). For the others, some mention of the problem with direction appear.

[GiulioRossetti]

@Yquetzal I'll give it a look in the next few days!

Do you remember if all the 6 methods that fail with obscure messages are defined only for undirected graphs? I think so, but maybe it's better to check the papers to be sure... In that scenario, we can simply anticipate their obscure failure and throw a more informative message.

[Yquetzal]

I checked quickly, 5 of the 6 methods are defined for undirected network in the original article. The only problem is for "em" method, which is defined for directed too. As far as I understood the code, the problem comes from a division by zero due, I think, to nodes having 0 out-degrees. I could not understand in less than 5 minutes if the problem was in the implementation or in the article... I could not find the origin of the code for this method either ? I listed also if they accept weights...

CONGA => undirected, unweighted DER => Undirected, weighted lfm => unweighted, undirected (could be extended to directed, weighted…) em =>DIRECTED, extended to undirected modularity_max (greedy_modularity from networkx) => undirected, unweighted LEMON => Undirected, unweighted