<p>I am looking for a heuristic for a graph matching problem as follows.</p>

<p>Given two graphs: <span class="math-container">$A$</span> (consisting of nodes <span class="math-container">$a_i$</span>) and <span class="math-container">$B$</span> (consisting of nodes <span class="math-container">$b_i$</span>). Typically the size of <span class="math-container">$B$</span> is larger than that of <span class="math-container">$A$</span>.</p>

<p>Each node and edge in two graphs has weight. The task is to match graph <span class="math-container">$A$</span> to graph <span class="math-container">$B$</span>, <em>i.e</em>., find a set of nodes and links in <span class="math-container">$B$</span> to map each node and link of <span class="math-container">$A$</span>, such as the host node/link in <span class="math-container">$B$</span> has larger weight than the corresponding node/link of <span class="math-container">$A$</span>.</p>

<p>The following figure illustrates two possible cases (or solution) of mapping (matching):</p>

<ul>
<li><p><strong>Case 1</strong>: One-to-one mapping: Each node or edge of <span class="math-container">$A$</span> needs only one node or link of <span class="math-container">$B$</span> to map. Here the nodes <span class="math-container">$a_1, a_2, a_3$</span> are mapped on to <span class="math-container">$b_1, b_2, b_3$</span>, and the edges <span class="math-container">$a_1a_2, a_2a_3$</span> are mapped onto <span class="math-container">$b_1b_2$</span> and <span class="math-container">$b_2b_3$</span> respectively. </p>

<ul>
<li>Constraints are satisfied: For nodes: <span class="math-container">$b_1 &gt; a_1$</span>, <span class="math-container">$b_2 &gt; a_2$</span>, <span class="math-container">$b_3 &gt; a_3$</span>. For edges: <span class="math-container">$b_1b_2 &gt; a_1a_2$</span> and <span class="math-container">$b_2b_3 &gt; a_2a_3$</span>.</li>
</ul></li>
<li><p><strong>Case 2</strong>: One-to-many mapping: One needs more than 1 node/edge of <span class="math-container">$B$</span> to host a node/edge of <span class="math-container">$A$</span>. In the example, <span class="math-container">$a_1$</span> is mapped on to <span class="math-container">$b_1$</span> and <span class="math-container">$b_4$</span>, <span class="math-container">$a_2, a_3$</span> are mapped onto <span class="math-container">$b_2, b_3$</span>. For the edges: <span class="math-container">$a_1a_2$</span> is mapped onto <span class="math-container">$b_1b_2$</span> and <span class="math-container">$b_4b_2$</span>, and <span class="math-container">$a_2a_3$</span> is mapped onto <span class="math-container">$b_2b_3$</span>. </p>

<ul>
<li>Constraints are satisfied: For nodes: <span class="math-container">$b_1 + b_4 = 11 &gt; a_1$</span>, <span class="math-container">$b_2 &gt; a_2$</span>, <span class="math-container">$b_3 &gt; a_3$</span>. For edges: <span class="math-container">$b_1b_2 + b_4b_2 = 8 &gt; a_1a_2$</span> and <span class="math-container">$b_2b_3 &gt; a_2a_3$</span>.</li>
</ul></li>
</ul>

<p>Heuristics for Case 1 have been well studied, <em>e.g</em>., using <em>eigendecomposition</em> to solve the <em>Weighted Graph Matching Problem</em> (<a href="http://www.indiana.edu/~pcl/rgoldsto/papers/weighted%20graph%20match2.pdf" rel="nofollow noreferrer">WGMP</a>). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?</p>

<p><img src="https://i.sstatic.net/A9lOS.png" alt="Example figure"> </p>

CC BY-SA 4.0
2019-08-14T20:41:59.400Z
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
CC BY-SA 4.0
2019-08-14T20:51:55.253Z
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
CC BY-SA 4.0
2019-08-14T21:09:03.523Z
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
<graph-theory><graph-algorithms><matching><heuristics>
Matching of two weighted graphs allowing one-to-many mapping
Trung
# Matching of two weighted graphs allowing one-to-many mapping

(Asked by: username_0 on 2019-08-05)

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](http://www.indiana.edu/~pcl/rgoldsto/papers/weighted%20graph%20match2.pdf)). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?

![Example figure](https://i.sstatic.net/A9lOS.png)

**Tags:** graph-theory, graph-algorithms, matching, heuristics
> **Comments:**
> **username_1**: 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" ?  
> **username_1**: 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?  
> **username_1**: 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  

---

## 0 answers

