What is the certificate good for?

[pkel]

I found pynauty via https://stackoverflow.com/a/14574330 where somebody claims that any two isomorphic graphs yield the same certificate. Is this correct?

The inverse relation (any two graphs with the same certificate are isomorphic) seems to be false. The following snippet produces an example. Is this intended? Your documentation does not describe what a certificate is and how it should be used, so I cannot tell!

from pynauty import *

ad = {0: [], 1: [0], 2: [0], 3: [0]}
vc1 = [{1}, {2, 3}, {0}]
vc2 = [{1, 2}, {3}, {0}]

g1 = Graph(4, True, ad, vc1)
g2 = Graph(4, True, ad, vc2)

if isomorphic(g1, g2):
    print("graphs are isomorphic")
else:
    print("graphs are not isomorphic")

if certificate(g1) == certificate(g2):
    print("certificates are equal")
else:
    print("certificates are different")

[pdobsan]

On Wed, Aug 16, 2023 at 12:50:08AM -0700, Patrik Keller wrote: claims that any two isomorphic graphs yield the same certificate. Is this correct?

Yes.

The inverse relation (any two graphs with the same certificate are isomorphic) seems to be false.

Yes.

Your documentation does not describe what a certificate is and how it should be used, so I cannot tell!

The certificate nauty's internal binary representation of the canonical graph. The current git repo of pynauty contains a canon_graph(cert) function which can transform it into Graph (python). It is a dev version and does not work with colored graphs. For further details consult nauty's docs.

[pkel]

The certificate nauty's internal binary representation of the canonical
graph.

If the certificate is the canonical form of the graph, then two graphs with the same certificate must be isomorphic. The above code snippet produces a counter example on my machine, so there must be a bug?

[enjoysmath]

Yes, what the f*ck. Shouldn't the two graphs be isomorphic then? Or what the hell is the canonicalization good for!

[gilleain]

Can you not just set the initial partition for refinement to be the vertex colors? Something like this : https://github.com/gilleain/moleculegen/blob/master/src/main/java/group/graph/GraphDiscretePartitionRefiner.java#L64-L85

[MarioVX]

The inverse relation (any two graphs with the same certificate are isomorphic) seems to be false.
Yes.

Eh, this is a huge dealbreaker. The whole point of the certificate is to provide exactly this inverse guarantee!
If this is the binary representation of the canonical graph and it ignores vertex coloring, the function straight up doesn't do what it says on these instances - it's useless.

Perhaps this can be fixed by augmenting the "certificate" with a tuple of the vertex colors (indices of the sets containing each vertex in the vertex_coloring list) in the order of the canonical labeling? Like this:

def canon_color(graph:pynauty.Graph) -> tuple[int]:
    vc = graph.vertex_coloring
    cl = pynauty.canon_label(graph)
    out = [0,] * len(cl)
    for c in range(len(vc)):
        for v in vc[c]:
            out[cl.index(v)] = c
    return tuple(out)

def actual_certificate(graph:pynauty.Graph):
    return pynauty.certificate(graph), canon_color(graph)

It works to correctly distinguish @pkel 's counter example and shouldn't distinguish isomorphic graphs.
If I understood the underlying problem correctly, the canonization itself does respect the provided coloring, but it doesn't store said coloring in its binary representation. So if two differently-colored graphs result in the same canonical adjacency matrix, they get the same certificate. In that case anything logically equivalent to the above code should catch exactly these cases. Note that nauty assumes colors to be unique (i.e. the vertex_coloring list to be ordered), so we need not consider isomorphisms between the colors.

Can anyone do a proper high-performance, minimal memory footprint implementation of this and contribute it?

One might compress the canon_color tuple for C = len(vc) different colors by storing it as a single integer sum out_i * C^i for example, stuff like that.

[enjoysmath]

I agree. Nauty is the only option available to developers. And it doesn't do what it advertised. Conspiracy!

…

On Mon, Jul 1, 2024 at 5:03 AM MarioVX ***@***.***> wrote: The inverse relation (any two graphs with the same certificate are isomorphic) seems to be false. Yes. Eh, this is a *huge* dealbreaker. The whole point of the certificate is to provide exactly this inverse guarantee! If this is the binary representation of the canonical graph and it ignores vertex coloring, the function straight up doesn't do what it says on these instances - it's useless. Perhaps this can be fixed by augmenting the "certificate" with a tuple of the vertex colors (indices of the sets containing each vertex in the vertex_coloring list) in the order of the canonical labeling? Like this: `def canon_color(graph:pynauty.Graph) -> tuple[int]: vc = graph.vertex_coloring cl = pynauty.canon_label(graph) out = [0,] * len(cl) for c in range(len(vc)): for v in vc[c]: out[cl.index(v)] = c return tuple(out) def actual_certificate(graph:pynauty.Graph): return pynauty.certificate(graph), canon_color(graph)` It works to correctly distinguish @pkel <https://github.com/pkel> 's counter example and shouldn't distinguish isomorphic graphs. If I understood the underlying problem correctly, the canonization itself does respect the provided coloring, but it doesn't store said coloring in its binary representation. So if two differently-colored graphs result in the same canonical adjacency matrix, they get the same certificate. In that case anything logically equivalent to the above code should catch exactly these cases. Note that nauty assumes colors to be unique (i.e. the vertex_coloring list to be ordered), so we need not consider isomorphisms between the colors. Can anyone do a proper high-performance, minimal memory footprint implementation of this and contribute it? One might compress the canon_color tuple for C = len(vc) different colors by storing it as a single integer sum out_i * C^i for example, stuff like that. — Reply to this email directly, view it on GitHub <#33 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAMIF55QROTLONVPBH2KONLZKFVSXAVCNFSM6AAAAABKFYOEU2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMBQGQYDKMJZHE> . You are receiving this because you commented.Message ID: ***@***.***>