Graph matching only handles node-induced sub-graph isomorphisms

[gabbard]

We identify objects by matching "perceptual patterns" represented as graphs against a graph representation of the learner's perception using the VF2 sub-graph isomorphism algorithm. The implementation we borrowed from NetworkX and altered only handles node-induced isomorphism. In such isomorphisms, we align a set of nodes between the pattern and the target graph and require that all edges between the nodes in the pattern must have aligned edges in the target and vice-versa.

This can be a problem if additional edges are present in the target graph. For example, imagine that a concrete perception has more relationships between a target's axes than are specified in the pattern; we would still want this to match, but the extra edges would block a node-induced isomorphism.

We could switch to trying an edge-induced isomorphism algorithm, which aligns edges rather than nodes. Or we could make some sort of modification to our current algorithm to allow extra edges on the graph side.

I don't think this is an immediate problem, but it may become a problem as we enrich the perceptual representation with "noise" features.

[j6k4m8]

You may want to check out GraphMatcher#subgraph_monomorphisms_iter() which is a direct drop-in replacement for GraphMatcher#subgraph_isomorphisms_iter() but returns a list of monomorphisms rather than isomorphisms (in other words, allows other edges in the induced subgraph).

[gabbard]

@j6k4m8 : Thanks! @spigo900 , can you look into @j6k4m8 's suggestion?

[spigo900]

@gabbard This appears to be a new feature in NetworkX 2.4. NetworkX's code for it is here.

[gabbard]

@spigo900 : Thanks. Updating the version of NetworkX we use should not be a problem. Can you briefly summarize the different between subgraph_monomorphisms_iter and what we are doing currently?

[spigo900]

@gabbard It looks like the only important difference between their code and ours is that they set self.test = 'mono' in subgraph_monomorphisms_iter().

Looking into this more, it looks like the _matcher.py code may be based on an earlier version of the 2.4 code and not on the 2.3 code. It includes, as far as I can tell, all of the required logic and is only lacking the client-facing methods related to monomorphisms. (Also, the docstrings still claim it doesn't support monomorphisms.) NetworkX 2.3's code for this doesn't include the logic for handling monomorphisms at all, while _matcher.py seems to include all the same logic as NetworkX 2.4.

Comparing with the 2.4 code, I didn't see any important difference (other than names) in the syntactic feasibility check, in initialize(), in match(), or in next_match_candidates(). The GraphMatchingState also seems to line up perfectly with DiGraphMatchingState.

The only differences I noticed were the expected ones; as follows:

1. The redefinition of semantic_feasibility().
2. _match_is_legal().
3. The extra debug code.
4. Allowing initial partial matchings to be passed.

[gabbard]

@spigo900 : Can you ensure that their definition of monomorphism matches our desired definition of edge-induced isomorphism (and summarize the two definitions for me)? I seem to recall looking at the monomorphism option when first implementing this and deciding it wasn't applicable to our use case for some reason.

[spigo900]

@gabbard Ah, I see. Sorry for the confusion. To be clear, what you're saying is that we want edge-induced isomorphism rather than non-induced subgraph isomorphism. In other words, we don't want to support patterns that have "orphan" nodes (ones with edges to no other vertices in the (sub)graph). That would make sense. In that case their definition does not match ours.

As I understand it, "monomorphism" in their definition means looking for a non-induced subgraph, which includes edge-induced isomorphisms but also things which are not edge-induced (because they include orphan nodes).

They claim that you can check for an edge-induced isomorphism using nx.line_graph() however I'm not sure whether (1) this gives you a match either in terms of the original graph or which can be translated back to such terms, OR (2) how one would use nx.line_graph() to do that.

My understanding of the definitions:

• Ours
  • An edge-induced subgraph isomorphism between G1 = (V1, E1) and G2 means there is some subset E' of the edges E1 such that G' = ({v in V : (v, u) in E' for some u OR (w, v) in E' for some w}, E') is isomorphic to G2.
  • A non-induced subgraph isomorphism between G1 = (V1, E1) and G2 means there are subsets V' of the vertices V1 and E' of the edges E1, such that E' only relates vertices in V' and G' = (V', E') is isomorphic to G2.
• Theirs
  • A non-induced subgraph isomorphism between G1 = (V1, E1) and G2 means there are subsets V' of the vertices V1 and E' of the edges E1, such that E' only relates vertices in V' and G' = (V', E') is isomorphic to G2.
  • Looking for a monomorphism means looking for a non-induced subgraph isomorphism

[gabbard]

@spigo900 : Can you clarify for me what orphan nodes are? How would they arise if we assume our "pattern graph" has a single connected component?

I agree that the nx.line_graph solution is too messy (and probably too slow) to bother with.

[gabbard]

@spigo900 : If I am reading your definitions correctly, it looks like non-induced subgraph isomorphism under Ours and Theirs is the same? Can you give an example showing the distinction between an edge-induced isomorphism and a non-induced one?

[spigo900]

@gabbard If our pattern graph has a single connected component (and at least two vertices) then the two should be equivalent. Plausibly pattern intersection might cause problems there? I'm not sure.

Yes, the "non-induced" definitions are the same, I think. Re: The distinction between edge-induced and non-induced, say you have a pair of graphs like this:

G1
1 -> 2
^    |
|    |
3 <--/

G2
1 -> 2


3

Then there's no edge-induced subgraph isomorphism between G1 and G2, because G2 has an orphan vertex (3), i.e. a vertex with no edges in or out. But when we take an edge-induced subgraph of G1, we include all and only the vertices that our chosen edges connect. (So in this case we could take any subset of the edges, but if we take say only the (1, 2) edge, then 3 won't appear in the edge-induced subgraph.)

Since the subgraph of G1 has only the vertices incident to some subset of its edges, we can never end up with a vertex that has no edges, so we can't have an edge-induced subgraph of G1 that's isomorphic to G2.

However, there is a non-induced subgraph isomorphism between G1 and G2. We can just match up the vertices with matching numbers. In this case (if I'm understand correctly) we have a monomorphism from G2 to G1.

[gabbard]

Got it. Since we expect both pattern and perception graphs to always have a single component, I think using monomorphisms will work. Can you:

(a) confirm that re-enabling the constraint in #673 causes a failure
(b) test if switching to monomorphisms passes all current unit tests
(c) confirm that the switch fixes the failure from (a)?

[spigo900]

@gabbard

• Re-enabling the partOf constraints for give, push, throw, and move does cause the corresponding tests to fail.
  • Oddly, it does not cause the test for take to fail even though it has a partOf constraint that was re-enabled.
  • test_throw and test_throw_animated fail for apparently unrelated reasons.
    • The _perceive_actions() method of the perception genreator doesn't like that the manipulator action description variables have more than one possible target.
    • Specifically, it fails because it finds three different possible manipulators for one of the variables: two hands and a dog head.
    • The same error happens without the monomorphism change.
  • It also causes test_recognize_in_transfer_of_possession to fail. It fails here because len(description_to_matched_node) is 2, not 4 as expected. I haven't investigated why this happens.
• Switching to monomorphism passes all but one test.
  • This is the failing test.
  • The failure appears to be spurious.
    • It's testing whether the perception graph pattern matching correctly fails on a syntactically infeasible match, but when we switch to monomorphism, the match that was previously syntactically infeasible (matching a pattern to a graph with "too many" edges) is now correct behavior.
    • I think we probably want to change the test to create the pattern from the "extra edges" graph (rather than from the original graph) and make sure it fails when we try to match that pattern against the original graph.
• The switch fixes the main failures from (a).
  • It does not fix the object recognizer failure. It does change the wrong len(...) slightly, from 2 to 3.
  • It doesn't solve the failure for test_throw and test_throw_animacy.

[gabbard]

@spigo900 : Thanks for the nice write-up.

• For the _perceive_actions failure - can you post a stack trace and link to the relevant code?
• I agree about revising the spurious failing test.
• Let me know what you find out when investigating the remaining problem.

[lichtefeld]

@spigo900 @gabbard The failing to choose with multiple possible manipulators is a known issue: #687

Making a reference so if it gets fixed here we can track and close the associated issue :)

[gabbard]

re: #687 - I wonder if we need to push binding these back to situation generation?

[lichtefeld]

@gabbard That was the solution discussed at the time, especially if we want better control over the left/right hand when throwing a ball.

[spigo900]

@gabbard I tracked down the "transfer of posession" test problem. In the scene, Dad gives a baby a chair. The perception generator seems to have decided that dad's hand (hand_0) is also a part of the baby.

(This causes the candidate baby subgraph to have too many nodes, so it gets rejected early as not matching the baby pattern, so we end up with not enough objects.)

I'll continue looking into this.

[spigo900]

@gabbard Found it. The method for binding the action object variables doesn't actually get any description of the relational conditions, so it ignores them. Thus the baby is found to have four identical hands (two of them actually belonging to dad) and it arbitrarily chooses the first.

(What distinguishes this from the throw crash situation, I think, is that in the other case the available manipulators are a dog head and two hands, and the two types of manipulators don't have identical features/properties.)

[gabbard]

@spigo900 : Thanks for tracking that down. Is it clear how to fix it or do you need guidance?

[spigo900]

@gabbard It's clear. From the discussion above, however, I was unsure though whether I should implement the direct solution for now if we might move variable binding earlier. (I think either should fix the test failures.)

Should I go ahead and implement the direct solution?

[gabbard]

@spigo900 : If we can hack around our current problems, we probably won't implement early variable binding before our next milestone, so go ahead with the direct solution.