# collapse
import sys
sys.path
sys.path.insert(0, '/Users/asaadeldin/Downloads/GitHub/scipy')
from scipy.optimize import quadratic_assignment

# collapse
%pylab inline
import pandas as pd
from graspy.utils import pass_to_ranks
import seaborn as sns

Populating the interactive namespace from numpy and matplotlib

Experiment Summary

If $A_i$ is the adjacency matrix at time index $i$, then with $n$ time indices, for $i = [1, n-1]$ do $GM(A_i, A_{i+1})$, where $A_i$ and $A_{i+1}$ are pre-matched based on the known 1-1 correspondance.

For each graph pair, run $GM$ $t = 20$ times, with each $t$ corresponding to a different random permutation on $A_{i+1}$.

Internally in GM, $A_{i+1}$ is shuffled, that is $A_{i+1}' = Q A_{i+1} Q^T,$ where $Q$ is sampled uniformly from the set of $m x m$ permutations matrices, where $m$ is the size of the vertex set.

$GM$ is run from the barycenter ($\gamma = 0$).

Compare the objective function values of the matrices with the known matching ($trace (A_i A_{i+1}^T)$) and the average objective function resulting from $t$ runs of $GM(A_i, A_{i+1})$

# collapse
def load_adj(file):
    df = pd.read_csv(f'org_sig1_max/{file}.csv', names = ['from', 'to', 'weight'])
    return df

# collapse
times = [1,4,11,17,25,34,45,48,52,55,63,69,70,76,80,83,90,97,103,111,117,129,130,132,139,140,146,153,160,167,
         174,181,188,192,195,202,209,216,223,229]

# collapse
from scipy.stats import sem
t = 20
ofvs = np.zeros((len(times)-1,3)) # [opt_ofv, gm_ofv]
for i in range(len(times)-1):
    # constructing the adjacency matrices
    Ael = load_adj(times[i])
    Bel = load_adj(times[i+1])
    nodes = np.concatenate((Ael['from'],Ael['to'],Bel['from'],Bel['to']), axis=0)
    nodes = list(set(nodes))
    n = len(nodes)
    A = np.zeros((n,n))
    B = np.zeros((n,n))
    row_list_A = [nodes.index(x) for x in Ael['from']]
    col_list_A = [nodes.index(x) for x in Ael['to']]
    A[row_list_A, col_list_A] = Ael['weight']
    row_list_B = [nodes.index(x) for x in Bel['from']]
    col_list_B = [nodes.index(x) for x in Bel['to']]
    B[row_list_B, col_list_B] = Bel['weight']
    A = pass_to_ranks(A)
    B = pass_to_ranks(B)
    gm_ofvs = np.zeros(t)
    for j in range(t):
        gmp = {'maximize':True}
        res = quadratic_assignment(A,B, options=gmp)
        gm_ofvs[j] = res.fun
        
    gm_ofv = np.mean(gm_ofvs)
    gm_error = sem(gm_ofvs)
    opt_ofv = (A*B).sum()
    ofvs[i,:] = [opt_ofv, gm_ofv, 2*gm_error]

# collapse
sns.set_context('paper')
sns.set(rc={'figure.figsize':(12,8)})
plt.scatter(np.arange(len(times)-1), ofvs[:,0], label = 'opt ofv')
#plt.scatter(np.arange(len(times)), ofvs[:,1], label = 'gm ofv')
plt.errorbar(np.arange(len(times)-1),ofvs[:,1], ofvs[:,2],label = 'average gm ofv +/- 2 s.e.',marker='o', fmt = ' ' ,capsize=3, elinewidth=1, markeredgewidth=1,color='orange')
plt.legend()
plt.ylabel('objective function value')
plt.xlabel('time stamp (A_x & A_{x+1})')

Text(0.5, 0, 'time stamp (A_x & A_{x+1})')

Extremely low variance above (error bars not visible)

# collapse
plt.scatter(np.arange(len(times)-1), ofvs[:,1]/ofvs[:,0])
plt.hlines(1,0,40,linestyles='dashed', color = 'red', label='y=1 (above means gm maximes ofv more)')
plt.legend()
plt.xlabel('Time Stamp')
plt.ylabel('gm_ofv / pre-matched_ofv')

Text(0, 0.5, 'gm_ofv / pre-matched_ofv')

# collapse
df = pd.DataFrame(ofvs,columns=["Pre Matched OFV","Avergae GM OFV", "2*s.e. GM OFV"])
print(df)

    Pre Matched OFV  Avergae GM OFV  2*s.e. GM OFV
0         77.778503       83.203695   6.520387e-15
1        102.363435      105.635371   6.520387e-15
2        539.611816      586.160090   5.216310e-14
3        184.831288      198.412628   2.608155e-14
4        159.324311      203.971815   0.000000e+00
5        984.399156     1152.762630   1.043262e-13
6       1089.477143     1119.627925   0.000000e+00
7       1259.423017     1290.748354   2.086524e-13
8       1585.077755     1730.198821   0.000000e+00
9       1842.297675     2111.213946   2.086524e-13
10      2144.029010     2320.060471   2.086524e-13
11      2031.803286     2092.043201   2.086524e-13
12      1956.629442     2111.907016   2.086524e-13
13      2449.635493     2580.498796   0.000000e+00
14      2488.814694     2536.434492   2.086524e-13
15      2435.361725     2648.848434   2.086524e-13
16      2450.644416     2909.986251   0.000000e+00
17      2799.810641     3086.113044   4.173048e-13
18      2795.063975     3051.412096   2.086524e-13
19      3093.261915     3183.004837   4.173048e-13
20      3483.603820     3653.248466   0.000000e+00
21      3788.502289     3834.393669   2.086524e-13
22      3837.060440     3977.016536   4.173048e-13
23      3625.742003     3800.326356   0.000000e+00
24      3067.810931     3308.850782   2.086524e-13
25      3440.573652     3634.710350   0.000000e+00
26      4605.778803     4669.727638   4.173048e-13
27      4541.053424     4634.822284   4.173048e-13
28      4305.613442     4587.914977   4.173048e-13
29      4103.909802     4283.742180   4.173048e-13
30      3897.553992     4100.491185   4.173048e-13
31      3744.066025     3871.777437   2.086524e-13
32      3206.210282     3391.022125   0.000000e+00
33      3073.053348     3358.433002   4.173048e-13
34      3177.553500     3395.320322   0.000000e+00
35      3332.128518     3368.928739   2.086524e-13
36      3180.781410     3517.218062   0.000000e+00
37      3385.105045     3510.301189   0.000000e+00
38      3229.233901     3407.950538   2.086524e-13