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$ You say "larger than" and you are using strict inequalities b_2 > a_2 but I see the weight of a_2 as 5 and b_2 also as 5. Do you mean "at least as large as" ? $\endgroup$ – JimN Aug 14 '19 at 20:41
  • $\begingroup$ In your examples, your edge mappings could be induced from your vertex maps. Are you allowing the possibility of having nodes {b_1,b_4} to map to {a_1} while having edges {b1b2, b4b2} mapped-to from edge {a2a3}? If your edge relationships are forced from your node map, then you should define this as just looking for a node to nodeSet mapping. e.g. Graph isomorphism is defined as a mapping from nodes to nodes which respects edge properties... does your problem need to be definable in terms of mapping subgraphs to subgraphs, or can you frame it as a mapping from nodes to node-sets? $\endgroup$ – JimN Aug 14 '19 at 20:51
  • $\begingroup$ This is more of a bin packing problem than a graph matching problem. An algorithm that solves your problem could be used to solve bin packing or subset sum by building two graphs with no edges. Bin packing is NP-hard even for 2 bins (like subset sum with target sum T/2). There are lots of interesting heuristics in bin packing literature related to queuing theory (each of your B-nodes is a processor and each A-node is a job, you have to assign a job to a processor. There are 'online' algorithms which involve processing jobs as they come in, without knowing what jobs come later. Plenty of others $\endgroup$ – JimN Aug 14 '19 at 21:09

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.