# Introduction to Graph Matching


```python
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
```

The graph matching problem (GMP), is meant to find an alignment of nodes between two graphs that minimizes the number of edge disagreements between those two graphs. Therefore, the GMP can be formally written as an optimization problem: 

\begin{equation}
\begin{aligned}
\min & {\;-trace(APB^T P^T)}\\
\text{s.t. } & {\;P \: \epsilon \: \mathcal{P}} \\
\end{aligned}
\end{equation}

Where $\mathcal{P}$ is the set of possible permutation matrices.

The Quadratic Assignment problem is a combinatorial opimization problem, modeling following the real-life problem: 

"Consider the problem of allocating a set of facilities to a set of locations, with the
cost being a function of the distance and flow between the facilities, plus costs associated
with a facility being placed at a certain location. The objective is to assign each facility
to a location such that the total cost is minimized." [1]

When written as an optimization problem, the QAP is represented as:

\begin{equation}
\begin{aligned}
\min & {\; trace(APB^T P^T)}\\
\text{s.t. } & {\;P \: \epsilon \: \mathcal{P}} \\
\end{aligned}
\end{equation}

Since the GMP objective function is the negation of the QAP objective function, any algorithm that solves one can solve the other. 


This class is an implementation of the Fast Approximate Quadratic Assignment Problem (FAQ), an algorithm designed to efficiently and accurately solve the QAP, as well as GMP. 

[1] Optimierung, Diskrete & Er, Rainer & Ela, A & Burkard, Rainer & Dragoti-Cela, Eranda & Pardalos, Panos & Pitsoulis, Leonidas. (1998). The Quadratic Assignment Problem. Handbook of Combinatorial Optimization. 10.1007/978-1-4613-0303-9_27. 


```python
from graspy.match import GraphMatch as GMP
from graspy.simulations import er_np
```

For the sake of this tutorial, we will use FAQ to solve the GMP for two graphs where we know a solution exists. 
Below, we sample a binary graph (undirected and no self-loops) $G_1 \sim ER_{NP}(50, 0.3)$.
Then, we randomly shuffle the nodes of $G_1$ to initiate $G_2$.
The number of edge disagreements as a result of the node shuffle is printed below.


```python
n = 50
p = 0.3

np.random.seed(1)
G1 = er_np(n=n, p=p)
node_shuffle_input = np.random.permutation(n)
G2 = G1[np.ix_(node_shuffle_input, node_shuffle_input)]
print("Number of edge disagreements: ", np.sum(abs(G1-G2)))
```

## Visualize the graphs using heat mapping


```python
from graspy.plot import heatmap
heatmap(G1, cbar=False, title = 'G1 [ER-NP(50, 0.3) Simulation]')
heatmap(G2, cbar=False, title = 'G2 [G1 Randomly Shuffled]')
```

Below, we create a model to solve GMP. The model is then fitted for the two graphs $G_1$ and $G_2$. One of the option for the algorithm is the starting position of $P$. In this case, the class default of barycenter intialization is used, or the flat doubly stochastic matrix. The number of edge disagreements is printed below. With zero edge disagreements, we see that FAQ is successful in unshuffling the graph.


```python
gmp = GMP()
gmp = gmp.fit(G1,G2)
G2 = G2[np.ix_(gmp.perm_inds_, gmp.perm_inds_)]
print("Number of edge disagreements: ", np.sum(abs(G1-G2)))
```


```python
heatmap(G1, cbar=False, title = 'G1[ER-NP(50, 0.3) Simulation]')
heatmap(G2, cbar=False, title = 'G2[ER-NP(50, 0.3) Randomly Shuffled] unshuffled')
```

fa0aed45832dadc3771c7338cfefd896513e665c
ipynb
Jupyter Notebook
docs/tutorials/matching/faq.ipynb
spencer-loggia/graspologic
cf7ae59289faa8f5538e335e2859cc2a843f2839
MIT
docs/tutorials/matching/faq.ipynb
spencer-loggia/graspologic
cf7ae59289faa8f5538e335e2859cc2a843f2839
MIT
docs/tutorials/matching/faq.ipynb
spencer-loggia/graspologic
cf7ae59289faa8f5538e335e2859cc2a843f2839
MIT
Qwen/Qwen-72B
1. YES
2. YES