GraphMatching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Matching\n",
    "\n",
    "In this notebook we show how to use qFGW to perform graph matching on TOSCA meshes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import ot \n",
    "import time\n",
    "import os\n",
    "from quantizedGW import * "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Centaur meshes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('data/centaurs.pkl','rb') as handle:\n",
    "    centaurs = pickle.load(handle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Parameters\n",
    "k = 100  #number of partition representatives\n",
    "dims = 64 #number of bins to use for Weisfeiler-Lehman (WL) histogram\n",
    "wl_steps = 1 #number of WL steps\n",
    "distribution_exponent = 1 # probability vector based on degree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15768"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(centaurs[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Partitioning with 100 blocks in each partition\n",
      "Starting with Graph 0\n",
      "Partition+Featurize completed in 7.458827972412109 seconds\n",
      "Distance primitives computed in 121.63416600227356 seconds\n",
      "Starting with Graph 1\n",
      "Partition+Featurize completed in 10.056394100189209 seconds\n",
      "Distance primitives computed in 107.38030409812927 seconds\n"
     ]
    }
   ],
   "source": [
    "dataset = partition_featurize_graphlist_fpdwl(centaurs,k=k,dims=dims,wl_steps=wl_steps,\n",
    "                                    distribution_offset=0,distribution_exponent=distribution_exponent,verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time for Matching: 0.4366021156311035 seconds\n",
      "CPU times: user 951 ms, sys: 126 ms, total: 1.08 s\n",
      "Wall time: 437 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "coup = compress_fgw_from_dicts(dataset[0],dataset[1],alpha=0.5,beta=0.5,verbose = False, return_dense = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.lines.Line2D at 0x7fdc640ccc50>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQ4AAAD8CAYAAACGnEoDAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAXnElEQVR4nO3dfaxdVZnH8e/P1iKItIXWUsGkVTpOQMcBbniJE4eAQinEOglq0UhBlGQA3zPSChGHFwNq5CUqyAjaGqQg4kgEZa4I40wihVuQdyqXtmCbQguFMkoEi8/8sddtTw/33HvWOfu83t8nubn77L3PXmude85z115rn/0oIjAzy/G6TlfAzHqPA4eZZXPgMLNsDhxmls2Bw8yyOXCYWb6I6KkfYD6wGhgGljR4jLcCdwCPAA8Dn03r9wQGgcfT7+lpvYDLU5kPAAdVHGtx2v9xYPE45U4C7gN+kR7PBVam414PTEnrd0mPh9P2ORXHWJrWrwaOGaOsacCNwGPAo8DhrWof8Pn0Oj4EXAe8ocy2AdcAm4CHKtaV1hbgYODB9JzLa5T3jfRaPgD8DJhWR71Hfa9WvTZrqsuq2O+LQAAzSmybSvkcdjoQZH7gJwFPAG8DpgD3A/s3cJzZIy868CbgD8D+wNdH/sDAEuDitLwA+GX6wx0GrKx4865Jv6en5eljlPsF4MfsCBw3AIvS8pXAv6bl04Er0/Ii4Pq0vH9q8y7pzfcEMKlGWcuAT6blKRSBpPT2AfsAa4FdK9p0cpltA94LHMTOH+TS2gLcnfZVeu6/jVLe0cDktHxxRXmj1psx3qtVr83Pga9RFTgo/rndBjzJjsBRRtuOnYiB43DgtorHS4GlJRz358D7Kf47zE7rZgOr0/L3gBMr9l+dtp8IfK9i/U77VZWxL3A7cCTwi/SHfLbizbi9bekNc3hanpz2U3V7K/erKmsqxYdZVetLbx9F4PhjetNOTm07puy2AXPY+YNcSlvStscq1p+Ytu1UXlWb/wW4drT34Ei9qfFerfF3/+/qsih6i+8G1rEjcJTStjI+i702xjHyJh2xPq1rmKQ5wIEUXcdZEbExbXoamDVOuTn1uRT4EvC39Hgv4IWI2DbKc7cfN23fmvavt7y5wGbgB5Luk/R9SW9sRfsiYgPwTeApYGOq66oWtm1EWW3ZJy3XWy7AJyj+ezdS3mh/970rDy5pIbAhIu6vKrcdbatLrwWOUknaHfgp8LmIeLFyWxQhupTr8SUdD2yKiFVlHK8Okym62ldExIHAnym689uV1T5J04GFFMHqLcAbKc7t26bMv9V4JJ0NbAOubdHxdwO+DHylFccvS68Fjg0U534j9k3rskl6PUXQuDYibkqrn5E0O22fTTFoNVa59dbnPcAHJK0DVlCcrlwGTJM0eZTnbj9u2j4VeC6jvPXA+ohYmR7fSBFIWtG+9wFrI2JzRPwVuCm1t1VtG1FWWzak5XHLlXQycDzwsRSsGinvOV772jxdsd/bKYLw/en9si9wr6S9W9m2bGWc77Trh+I/6Zr0wo4MOB3QwHEELAcurVr/DXYecPt6Wj6OnQel7k7r96QYS5ieftYCe45T9hHsGBz9CTsPIJ6els9g5wHEG9LyAew8ELeG2oOj/wO8Iy1/NbWt9PYBh1LMqOyWnr8M+HTZbeO1YxyltYXXDiAuGKW8+RSzcDOr2j9qvRnjvTrKa3MOtcdT1rFjjKOUtpXyWex0MGjgQ7+AYhbkCeDsBo/xTxRd2weA36efBRTnn7dTTGn9uuLFF/CdVOaDwEDFsT5BMdU1DJxSR9lHsCNwvC39YYfTm2mXtP4N6fFw2v62iuefneqxmjFGyIF/BIZSG/8zvaFa0j7g3ymmKh8CfpQ+RKW1jWKKdyPwV4re1KlltgUYSHV/Avh2jfKGKcYRRt4vV9ZR71Hfq1WvzVPVZY0ROMpoWynTsUoHNzOrW6+NcZhZF3DgMLNsDhxmls2Bw8yydU3gkDRf0mpJw5KWjP8MM+uUrggckiZRTDMdS/GloRMl7T/Oc05rR93aXVa7y+vntrW7vH5uW7WuCBzAIcBwRKyJiFcorq5cOM5z2vmitfsP5Lb1Znn93LaddEvgKP3La2bWOl1xAZikE4D5EfHJ9PjjwKERcWbVfqeRouzrdt3j4MlT39z2uvard+0ztS3lbN68mZkzZ7alrHaX18qyHtywtSXHhdp/+1WrVj0bEaM2aPJoKzugri84RcRVwFUAu8yeF7MXX9qWyk0EQxcd1+kq2BjmLLmlZceu9beX9GSt53TLqco9wDxJcyVNofjy080drpOZ1dAVPY6I2CbpTIq7J00CromIhztcLTOroSsCB0BE3Arc2ul6mNn4uuVUxcx6iAOHmWXrmlMVM+uM6hmbdXXMsLnHYajTFbCe4x5HH5ix+xSGznl/p6thE4gDR4+rp1tpVjYHjh7mUwxrhZExjymz9ju41j4OHF3EvQfrKmP8Z/LgqJllc+Aws2wOHGaWzYHDzLI5cJhZNgcOM8vmwGFm2Rw4zCybA4eZZXPgMLNsDhxmlq3h76pIeiuwHJgFBHBVRFwmaU/gemAOsA74cEQ8L0nAZcAC4CXg5Ii4Nx1rMXBOOvQFEbGs0Xr1skZvgT/ytfqBCwZ59k+v1L2/WaOa+ZLbNuCLEXGvpDcBqyQNAicDt0fERSl59BLgLIq8sPPSz6HAFcChKdCcCwxQBKBVkm6OiOebqNuE8uyfXskKOtX7C1jrL9hZhoZPVSJi40iPISL+D3iUIm3jQmCkx7AM+GBaXggsj8JdwDRJs4FjgMGI2JKCxSAwv9F6Wb7O5/KzXlPKGIekOcCBwEpgVkRsTJuepjiVgdr5YevOGyvpNElDkobKqLeZNabpwCFpd+CnwOci4sXKbVEkpi3tH1pEXBURAxExUNYxzSxfU4FD0uspgsa1EXFTWv1MOgUh/d6U1tfKD1tX3lgz6x4NB440S3I18GhEfKti083A4rS8GPh5xfqTVDgM2JpOaW4DjpY0XdJ04Oi0zsySGbtP6XQVdtJMj+M9wMeBIyX9Pv0sAC4C3i/pceB96TEU6R3XAMPAfwCnA0TEFuB8isTT9wDnpXVmlnTb9HnD07ER8b/UvivhUaPsH8AZNY51DXBNo3Uxs/bylaNmls2Bw6xHdFM6DKdHMOsR413d2+hXFhrhHoeZZXPgMLNsDhxmls2Bw8yyOXCYWTYHDuuqaT7rDZ6O7QOVWe7nLrmlrq8j++Y91gwHjh422i0AHQysHRw4esw6BwbrAh7j6CEOGtYtHDjM+kS99+wo494ePlUx6xM59+xo9nst7nGYWTb3OHpIswmbzMriwDEBjJawaaxgUkZGOGeV629NBw5Jk4AhYENEHC9pLrAC2AtYBXw8Il6RtAtFysiDgeeAj0TEunSMpcCpwKvAZyLCNytusepgUvkBrucDP9oxGq1Ht3Lwq62MHsdnKbK47ZEeXwxcEhErJF1JERCuSL+fj4j9JC1K+31E0v7AIuAA4C3AryX9XUS8WkLdslROd7bzpijdoIwgUKZuuAK22QDazwGlqcAhaV/gOOBC4AspZcKRwEfTLsuAr1IEjoVpGeBG4Ntp/4XAioh4GVgraRg4BPhdM3Wz3tFMwCo7fWW9Aase3dybalazsyqXAl8C/pYe7wW8EBHb0uPKdI7bUz2m7VvT/nWngDRrNefRrU/DPQ5JxwObImKVpCNKq9HYZZ4GnAYwZe/92lGkWVNGelP9dtrSbEKmD0haRzEYeiRwGUUW+pGAVJnOcXuqx7R9KsUgad0pIJ071npVv522NBw4ImJpROwbEXMoBjd/ExEfA+4ATki7VaeAHEkNeULaP9L6RZJ2STMy84C7G62XmbVeK67jOAtYIekC4D6K/LKk3z9Kg59bKIINEfGwpBuAR4BtwBmdmFGx3lU9uOp7jbReKYEjIu4E7kzLayhmRar3+QvwoRrPv5BiZsasaR7gHN/IpQeNzmj5ytGk27KBm7XDWLdq0MXHr6q1bcIEDt/Lwjpt4ILBvplZmTCBwyaW0brgnf7n0U8zK/5avZllc+Aws2wOHGaWzYHDrI266RvIzZgQgcOZyszK1bOzKu/aZypDLRwlrzUCn/MfY7xR/H7572MTz4TocZhZuRw4zCybA4eZZXPgMLNsPTs4ajaWfrvjVrdxj8P6koNGa7nHkWnG7lPqzrVh7dHpL69NRA4cmcr8TzaR87hYb/Opipllc+Aws2xNBQ5J0yTdKOkxSY9KOlzSnpIGJT2efk9P+0rS5ZKGJT0g6aCK4yxO+z8uaXHtEs2sGzTb47gM+FVE/D3wboocskuA2yNiHnB7egxwLEXqg3kUSZWuAJC0J3AucCjFTY7PHQk2ZtadGg4ckqYC7yWlP4iIVyLiBYpcsMvSbsuAD6blhcDyKNxFkbhpNnAMMBgRWyLieWAQmN9ovcys9ZrpccwFNgM/kHSfpO9LeiMwKyI2pn2eBmal5Vo5Yp071qzHNBM4JgMHAVdExIHAn9lxWgJAytRWWpoLSadJGpI0tHnz5rIO2xV8zxDrJc0EjvXA+ohYmR7fSBFInkmnIKTfm9L2WjliG8odO3PmzCaq3n3WXnQc69KP9a9+uTCw4QvAIuJpSX+U9I6IWA0cRZHG8RGKHLEX8drcsWdKWkExELo1IjZKug34WsWA6NHA0kbrZf2jH4Nov1wK3+yVo58GrpU0BVgDnELRi7lB0qnAk8CH0763AguAYeCltC8RsUXS+cA9ab/zImJLk/Uy67h+DHwjVAxD9J6BgYEYGhrqdDVawpefj69V334t+7Xv5eAhaVVEDIy2zd9VsZ7UK1nRqgNRLweSSr7k3MyyOXCYWTYHDjPL5sBhZtkcOMwsmwOHmWVz4DCzbA4cZpbNF4BZzxrtKk/nU2kPX3Le5Xz5eWOavUJz4ILBllyd2ktXjvqSc7NM7rWMzWMcZpbNgcPMsjlwmFk2Bw4zy+bAYWbZHDjMLJsDh5llazZ37OclPSzpIUnXSXqDpLmSVqYcsdenGxkjaZf0eDhtn1NxnKVp/WpJxzTZJjNrsWZSQO4DfAYYiIh3ApOARcDFwCURsR/wPHBqesqpwPNp/SVpPyTtn553AEXqx+9KmtRovcys9Zo9VZkM7CppMrAbsBE4kiI5E7w2d+xITtkbgaMkKa1fEREvR8RaivQJhzRZLzNroYYDR0RsAL4JPEURMLYCq4AXImJb2q0yD+z2HLFp+1ZgLzJyx/ZzCkizXtLwd1VS5rWFFMmnXwB+QouzzEfEVcBVUHzJrZVltUOrvkhlr/1yoL81W65mTlXeB6yNiM0R8VfgJuA9wLR06gI754HdniM2bZ8KPEdG7th+46DRPn6ty9VM4HgKOEzSbmmsYiR37B3ACWmf6tyxi9PyCcBvUjb7m4FFadZlLjAPuLuJeplZizWTdHqlpBuBe4FtwH0UpxG3ACskXZDWXZ2ecjXwI0nDwBaKmRQi4mFJN1AEnW3AGRHxaqP1MrPWa+p+HBFxLnBu1eo1jDIrEhF/AT5U4zgXAhc2Uxczax9fOWpm2Rw4zCybA4eZZXPgMLNsDhxmls2Bw8yyOXCYWTYHDjPL5sDRQesuOq6nMnuZjXDgMLNsTgFpE8ZYeXjd88vjHoeZZXPgMLNsDhxmls2BowvM2H1Kp6tglkXFTbh6z8DAQAwNDXW6GqUZa+CuWa263+ZEvmfqRBhMlbQqIgZG2+ZZlS4x1hux0aDS6jd3o8GolUHS2sOnKmaWbdzAIekaSZskPVSxbk9Jg5IeT7+np/WSdHlK5/iApIMqnrM47f+4pMUV6w+W9GB6zuXpxsdm1sXq6XH8kNfmS1kC3B4R84Db02OAYynuUj4POA24AopAQ3Fv0kMp7kd67kiwSft8quJ5Lc3NMlE4+lorjTvGERG/rUwQnSwEjkjLy4A7gbPS+uUp7cFdkqZJmp32HYyILQCSBoH5ku4E9oiIu9L65RQpI3/ZTKMmuokwcGed1egYx6yI2JiWnwZmpeVa6RzHWr9+lPXWIE/tWjs0PTiaehdtmdN17tjxOc2htUOjgeOZdApC+r0pra+VznGs9fuOsn5UEXFVRAxExMDMmTMbrLqZNavRwFGZzrE6zeNJaXblMGBrOqW5DTha0vQ0KHo0cFva9qKkw9JsykkVx7I+5YHb3jfu4Kik6ygGN2dIWk8xO3IRcIOkU4EngQ+n3W8FFgDDwEvAKQARsUXS+cA9ab/zRgZKgdMpZm52pRgU9cBolX4b7FxbZ3t8oVj38iXn1pM6HVT6LZiPZqxLzn3lqJllc+Aws2wOHGaWzYHDzLI5cJhZNgcOM8vmwGFm2XwHsC7R6esSGtGqWxL2gmb/XqL+C+G6kXsc1rCJer/RMvTmZZc7uMdhTWn2P+9E7rX0Mvc4rKPca+lN7nFYTxK9390f6a31Yq/LgcN6UuXAYi8OLFfqxV6XT1XMLJsDh5llc+Aws2wOHGaWzYOjZl2g1gBvt95pzIHDel5ZH65en51pp0Zzx35D0mMpP+zPJE2r2LY05YFdLemYivXz07phSUsq1s+VtDKtv16SMwqZdblGc8cOAu+MiH8A/gAsBZC0P7AIOCA957uSJkmaBHyHIrfs/sCJaV+Ai4FLImI/4Hng1KZaZGYtN27giIjfAluq1v1XRGxLD+9iR1KlhcCKiHg5ItZSpEk4JP0MR8SaiHgFWAEsTLlUjgRuTM9fRpE71sy6WBmzKp9gRy6U3NyxewEvVAShMXPHOgWkWXdoKnBIOhvYBlxbTnXG5hSQZt2h4VkVSScDxwNHxY6sTrVyxFJj/XPANEmTU69jzNyxZtYdGgockuYDXwL+OSJeqth0M/BjSd8C3gLMA+6m+DLjPElzKQLDIuCjERGS7gBOoBj3qMxDa202Mq2ZMy1ZayrUU5vlaOR1bMe1H/VMx14H/A54h6T1KV/st4E3AYOSfi/pSoCIeBi4AXgE+BVwRkS8mnoTZ1Ikn34UuCHtC3AW8AVJwxRjHleX2kKrS+Wbrd6k0GPtN2P3+mbV693Puotzx3aRuUtu6cg9Jrr16sR265deUll/z7Fyx/rK0S7S6M1r++UNb73DX3Izs2wOHGaWzYHDzLJ5jKMPrLvouKxxjl68OW47zNh9Sk/e/7MTHDj6hGdGmjd0zvs90Fwnn6qYWTYHDjPL5sBhZtk8xmFWIXesaOCCwQk5oOrAYdaE6tmpiTK46lMVM8vmwGFm2Rw4zCybA4eZZXPgMLNsDhxmls2Bw8yyjXsdh6RrKO5mviki3lm17YvAN4GZEfFsSrB0GbAAeAk4OSLuTfsuBs5JT70gIpal9QdTZIvbFbgV+GzUcT/DBzds7eo589xvrI48x6xZOe870did5+q5AOyHFDcnXr5TgdJbgaOBpypWH0txZ/N5wKHAFcChkvYEzgUGgABWSbo5Ip5P+3wKWEkROOazI8GTmbVQsHOgqfeWCw2lgEwuoUiRUNk7WAgsj8JdFDlTZgPHAIMRsSUFi0Fgftq2R0TclXoZy3EKSLOOqffy+YbGOCQtBDZExP1Vm3JTQO6TlqvXm1kXyw4cknYDvgx8pfzqjFv29tyx7S7bzHZopMfxdmAucL+kdRRpG++VtDe1U0COtX7fUdaPqjJ3bAP1NrOSZAeOiHgwIt4cEXMiYg7F6cVBEfE0RQrIk1Q4DNgaERspMrgdLWm6pOkUg6q3pW0vSjoszcichFNAmnW9eqZjrwOOAGZIWg+cGxG10jTeSjEVO0wxHXsKQERskXQ+cE/a77yIGBlwPZ0d07G/xDMqZh01MssyZe/9Dq61T8+mgNxl9ryYvfjSTlejVL6OY2Lq1uuRNi77HC9vfHzUFMG+ctTMsjlwmFk23zrQrMNyTlG75bTGPQ4zy+YeRxt40NP6jQOHWQ+p/ifUqVMXBw6zHtEt4xvgMQ4za4ADh5llc+Aws2we42iD8c5NPetivcY9DjPL5h5HF6hntNy9Eusm7nGYWTYHDjPL5sBhZtkcOMwsmwOHmWVz4DCzbD17z9FJu02NyVPf3NBzX3l6eBWMfTPWbjNS5xaYATzbomNPtPJaWla736/btm7i1Ze2jnrP0Z4NHJKG2pVfpZ1ltbu8fm5bu8vr57ZV86mKmWVz4DCzbL0cOK7q07LaXV4/t63d5fVz23bSs2McZtY5vdzjMLMOceAws2wOHGaWzYHDzLI5cJhZtv8HTW0tmVBZPEQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.spy(coup)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}