Expanding the pydelphin isomorphism check

PyDelphin Tools
1

I wrote a subclass of PyDelphin’s MRS called SEMENT that adds ltop so I can work with them compositionally.

I want to use is_isomorphic to check whether two SEMENTs I create are isomorphic. As it stands now, the function CAN take the SEMENTs, but since LTOP is just something I added the isomorphism check just ignores it (I think).

What would be involved in having the isomorphism check also consider the LTOP? I feel like it should be doable (maybe as a separate function that checks for isomorphism between SEMENTs specifically) because in theory the LTOP would just be another part of the graph but looking at the code I can’t immediately see how to make this change.

2

The MRS class already has a top attribute. In an MRS for a full sentence, this is the GTOP that is qeq to the graph’s top handle, but in principle it could also serve as an LTOP handle during MRS construction. Does this not work for you?

Well, yes, but it also ignores the existing top as well. I didn’t include it previously because it wasn’t necessary as the h0 qeq hX constraint on HCONS was enough to identify the top, but if top is only an EP’s label I can see why it might need to be included explicitly.

Before checking isomorphism, PyDelphin transforms the MRS into what it calls an “isograph”, which is a simplified form of the MRS graph of the form g[source][target] = edge_label. You can modify the _make_mrs_isograph() function after these lines:

by inserting something like:

    g["*top*"][x.top] = "TOP"

or if you want to use the code as-is, you could insert an ad hoc qeq like this:

from copy import deepcopy

def is_sement_isomorphic(s1: MRS, s2: MRS) -> bool:
    s1_ = deepcopy(s1)  # don't modify the original
    s2_ = deepcopy(s2)
    s1_.hcons.append(HCons.qeq("*top*", s1_.top))
    s2_.hcons.append(HCons.qeq("*top*", s2_.top))
    return is_isomorphic(s1_, s2_)

I haven’t tested the above, but the idea is that the explicit qeq will be picked up by the _make_mrs_isograph() function.

3

Thanks!
I suppose just using the existing TOP feature could work. Is it the case that after composition whatever the LTOP of the final stucture is will always end up being GTOP anyway? If so then I can adjust mine to just use TOP as LTOP.

Another slight caveat that I didn’t mention above because I wanted to deal with LTOP first is that my SEMENT object has two more attributes, eqs and holes. eqs is a list of tuples of variables that are identified with one another. Every time a hole is plugged by an argument another eq is added. Once I’m finished with composition I turn these into sets of equalities then just pick one to represent the set and overwrite where necessary.

So for example, if after I’m done with composition I have [(x1, x2), (x2, x3)] for my eqs list, I turn that into a set (x1, x2, x3) then search through the structure and change any instance of x2 or x3 to x1.

To be honest I’m not sure if this is the best way to do it, but I figured it was easier to just keep adding the eqs until the end and then do one overwrite operation instead of having to search through the eqs list every time to see if a variable can be added to an existing set.

But as far as the isomorphism check, I think dealing with it in that form would be a massive headache, so if I want to check if two SEMENTs are isomorphic would you suggest I do the eq overwrite before checking? That’s what I think seems best but I’d like some input.

Then lastly for holes I don’t even know where to begin there or if it matters for isomorphism checking. As it stands now, the holes list looks something like this for a SEMENT: {'ARG1': 'x1', 'ARG2': 'x2'}. Maybe this would be better to check in an ad hoc way, like “do they each have the same keys in the holes dict?” … then somehow get back the isographs and see if the variable mapping is correct for each hole.

4

I believe so. From Copestake et al. 2005 (Intro to MRS paper), section 4.3 (emphasis added):

In order to state the rules of combination involving handles, we will assume that MRSs have an extra attribute, the local top, or ltop, which will be the topmost label in an MRS which is not the label of a floating EP(i.e., not the label of a quantifier). […]. In an MRS corresponding to a complete utterance, the top handle will be qeq to the local top. We will assume that when an MRS is composed, the top handle for each phrase in the composition is the same: that is, the top handle we introduced in §4.1 is a ‘global’ top handle gtop, in contrast to the local top for the phrase, which is the label of the topmost EP in that phrase which is not a floating EP.

I’m not sure where in the grammar the QEQ is introduced, though.

Not sure about holes, but the eqs list sounds like HCONS. You could create a PyDelphin HCons object with the lheq relation instead of maintaining a separate list, if that interests you.

While we’re on the subject, you might find delphin.scope.conjoin() useful?

Yes, if you consider a structure with the eqs and a resolved one to be equivalent. The isomorphism check will consider lheq HCons for the “isograph” mentioned above and it will appear connected, but it will still have a different shape to one with resolved handles.

I’m afraid I can’t say what is appropriate here. If the roles and holes/variables appear in EP.args then I think they will be part of the isograph and thus the isomorphism comparisons.