<p>According to Umeyama, the weighted graph matching problem can be formulated as</p>

<p>$min_P || PA_GP^T - A_H ||$</p>

<p>s.t. $P$ is a permutation matrix.</p>

<p>where $A_G$ and $A_H$ are n-by-n matrices</p>

<p>If we relax $P$ to be doubly stochastic matrix, how will the cost function looks like?</p>

<p>Concave? Non-convex with multiple local minimums? Or any other shape?</p>

CC BY-SA 3.0
2013-03-12T18:55:54.300Z
Could you maybe explain how this formulation works?
usul
CC BY-SA 3.0
2013-03-14T08:48:03.637Z
@usul Sure no problem.
Consider two networks with adjacency matrix $A_G$ and $A_H$
$||A_G-B_H||_F$ is the network distance of the two networks under the mapping: node $i$ in network $A_G$ maps to node $i$ in network $A_H$ for all $i$.

Since $P$ is a permutation matrix, minimizing over $P$ means that consider all the possible permutation/mapping, select the one that can produce the shortest network distance.
Rein
CC BY-SA 3.0
2013-03-14T14:48:05.477Z
OK, thanks. And what is network distance? (Googling didn't help me much, haha.)
usul
CC BY-SA 3.0
2013-03-15T03:26:08.530Z
@usul It is a distance metric to quantify how "dissimilar" the two networks are.
Rein
CC BY-SA 3.0
2013-03-15T09:39:30.860Z
Sure, but I mean how is it calculated?
usul
CC BY-SA 3.0
2013-03-18T06:03:23.587Z
@usul In this case the frobenius norm of the difference of two adjacency matrix is used.
Rein
<graph-theory><optimization>
What is the shape of cost function of weighted graph matching problem?
Rein
# What is the shape of cost function of weighted graph matching problem?

(Asked by: username_0 on 2013-03-12)

According to Umeyama, the weighted graph matching problem can be formulated as

$min\_P || PA\_GP^T - A\_H ||$

s.t. $P$ is a permutation matrix.

where $A\_G$ and $A\_H$ are n-by-n matrices

If we relax $P$ to be doubly stochastic matrix, how will the cost function looks like?

Concave? Non-convex with multiple local minimums? Or any other shape?

**Tags:** graph-theory, optimization
> **Comments:**
> **username_1**: Could you maybe explain how this formulation works?  
> **username_0**: @usul Sure no problem. Consider two networks with adjacency matrix $A_G$ and $A_H$ $||A_G-B_H||_F$ is the network distance of the two networks under the mapping: node $i$ in network $A_G$ maps to node $i$ in network $A_H$ for all $i$.  Since $P$ is a permutation matrix, minimizing over $P$ means that consider all the possible permutation/mapping, select the one that can produce the shortest network distance.  
> **username_1**: OK, thanks. And what is network distance? (Googling didn't help me much, haha.)  
> **username_0**: @usul It is a distance metric to quantify how "dissimilar" the two networks are.  
> **username_1**: Sure, but I mean how is it calculated?  
> **username_0**: @usul In this case the frobenius norm of the difference of two adjacency matrix is used.  

---

## 0 answers

