# Matching of two weighted graphs allowing one-to-many mapping

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?

• 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" ? – JimN Aug 14 '19 at 20:41
• 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? – JimN Aug 14 '19 at 20:51
• 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 – JimN Aug 14 '19 at 21:09