I am looking for a heuristic for a graph matching problem as follows.

Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than that of $A$.

Each node and edge in two graphs has weight. The task is to match graph $A$ to graph $B$, i.e., find a set of nodes and links in $B$ to map each node and link of $A$, such as the host node/link in $B$ has larger weight than the corresponding node/link of $A$.

The following figure illustrates two possible cases (or solution) of mapping (matching):

  • Case 1: One-to-one mapping: Each node or edge of $A$ needs only one node or link of $B$ to map. Here the nodes $a_1, a_2, a_3$ are mapped on to $b_1, b_2, b_3$, and the edges $a_1a_2, a_2a_3$ are mapped onto $b_1b_2$ and $b_2b_3$ respectively.

    • Constraints are satisfied: For nodes: $b_1 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 > a_1a_2$ and $b_2b_3 > a_2a_3$.
  • Case 2: One-to-many mapping: One needs more than 1 node/edge of $B$ to host a node/edge of $A$. In the example, $a_1$ is mapped on to $b_1$ and $b_4$, $a_2, a_3$ are mapped onto $b_2, b_3$. For the edges: $a_1a_2$ is mapped onto $b_1b_2$ and $b_4b_2$, and $a_2a_3$ is mapped onto $b_2b_3$.

    • Constraints are satisfied: For nodes: $b_1 + b_4 = 11 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 + b_4b_2 = 8 > a_1a_2$ and $b_2b_3 > a_2a_3$.

Heuristics for Case 1 have been well studied, e.g., using eigendecomposition to solve the Weighted Graph Matching Problem (WGMP). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?

Example figure

  • $\begingroup$ The constraints aren't clear yet -- for case 1, is it that every vertex $a_i$ maps to some distinct vertex $f(a_i) \in V(B)$ such that for every $i$, $w(f(a_i)) \ge w(a_i)$ and for every edge $a_ia_j \in E(A)$, $w(f(a_i)f(a_j)) \ge w(a_ia_j)$, and these are the only constraints? Because this is NP-hard when all weights in $A$ and $B$ are 1, as it's the Subgraph Isomorphism problem. $\endgroup$ – j_random_hacker Aug 5 '19 at 17:38
  • 1
    $\begingroup$ For the mapping to distinct vertices question: Not necessary. A node in $A$ can be mapped to multiple nodes in $B$, and vice versa: multiple nodes in $A$ can be mapped to one node in $B$. But there must be an internal link (loopback) of the mapped node $B$ (i.e., edge $b_ib_i$) to host the links between the nodes of $A$. I neglected this scenario in the problem statement for the sake of simplicity. $\endgroup$ – Trung Aug 5 '19 at 23:14
  • 1
    $\begingroup$ For the question about the additional edge $b_1b_3$: No, it does not affect the solution. The shaded subgraph solution is still validated. $\endgroup$ – Trung Aug 5 '19 at 23:15
  • 1
    $\begingroup$ Trung and @j_random_hacker, there is a lot of back-and-forth in the comments here and I cannot completely follow which parts have been clarified in the question and which ones not. Can you try editing the question such that all comments are addressed and delete (or flag for deletion) the comments that are obsolete? Thanks. $\endgroup$ – Discrete lizard Aug 7 '19 at 6:11
  • 1
    $\begingroup$ It is not exactly clear to me what sort of solution to the problem you want. Yes, you want a heuristic, but what sort of heuristic? I think it would help if you edit your question to briefly describe your current MILP approach and why it doesn't satisfy you. (it seems to be the case it isn't fast enough for your dataset, but there may be more issues). It can also help if you can briefly describe describe the actual problem that leads you to look for such a matching. It may be possible that something else is much easier to compute here and would work as well. $\endgroup$ – Discrete lizard Aug 7 '19 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.