Features based Subgraph Isomorphism

[okpatil4u]

Thank you for sharing this work. Does this algorithm support feature based subgraph isomorphism ?

[j6k4m8]

Hi @okpatil4u! :) I wonder if you could explain what you mean by featured-based — does this refer to matching edge or node attributes as well as the network structure?

[okpatil4u]

Thanks for your reply @j6k4m8. Yes, I meant node and edge attributes.

[okpatil4u]

This is how I am adding the attributes

motif = nx.DiGraph() motif.add_node("A", feat=[1,2]) motif.add_node("B", feat=[4,4]) motif.add_node("C", feat=[9,6])

[j6k4m8]

@okpatil4u — this is an excellent question :)

This is an intended feature for this library, but we do not currently support attribute matching like this. (Actually the code is all there, but it is unused! More on that later.)

In the course of our work, we have developed DotMotif for this reason: DotMotif gives you even more control over subgraph monomorphism/isomorphism with a deliberate focus on attribute matching:

import networkx as nx

from dotmotif import GrandIsoExecutor, Motif

host = nx.DiGraph()
host.add_node("A", feat=[1,2])
host.add_node("B", feat=[4,4])
host.add_node("C", feat=[9,6])
nx.add_path(host, ["A", "B", "C", "A"])

motif = Motif("""
x -> y             # look for an edge between two nodes,
x.feat contains 6  # where the source node has an attribute 
                   # called "feat" that contains the number 6
""")

GrandIsoExecutor(graph=host).find(motif) # returns the list of results

The code above will return the following:

[{'x': 'C', 'y': 'A'}]

...which indicates that there is a valid motif mapping where motif node x is assigned to host node C, and motif node y is assigned to host node A.

---

Like I mentioned above, similar code exists but is unused in this library. If you are willing to modify code, you can change instances of this function call,

https://github.com/aplbrain/grandiso-networkx/blob/ac91751da0eaf6f8402b1518263fb1974175a485/grandiso/__init__.py#L154

to also call is_node_attr_match. But this is untested functionality at this time.

Does this answer your question? Happy to discuss more if helpful!

[okpatil4u]

Aah, now I understand. Thank you for the clarification. Closing the issue.

[j6k4m8]

Glad I could help! Please feel free to reopen or reach out if I can be helpful to you! I will also keep you updated once this functionality is added.