This package computes the approximations to the cutnorm of matrices using some of the techniques detailed by Alon and Noar [ALON2004] and a fast optimization algorithm by Wen and Yin [WEN2013].

Read the documentation.

Use pip to install the package. Install from terminal as follows:

$ pip install cutnorm

Given the adjacency matrices of two simple graphs A and B, we wish to compute a norm for the difference matrix (A - B) between the two graphs. An obvious display of the advantages of using a cutnorm over l1 norm is to consider the value of the norms on Erdos-Renyi random graphs.

Given two Erdos-Renyi random graphs with constant n and p=0.5, the edit distance (l1 norm) of the difference (after normalization) is 0.5 with large probability. An l1 norm of 1 implies the two matrices are completely different, 0 implies identity, and 0.5 is somewhere in between. However, these two graphs have the same global structure. As n approaches infinity, A and B converges to the same graphon object that is 0.5 everywhere. The edit distance fails as a notion of 'distance' between the two graphs in the perspective of global structural similarity as discussed by Lovasz [LOVASZ2009]. The cutnorm is a measure of distance that reflects global structural similarity. In fact, the cutnorm of the difference for this example approaches 0 as n grows.

Below is an example of using the cutnorm package and tools.

import numpy as np
from cutnorm import compute_cutnorm, tools

# Generate Erdos Renyi Random Graph (Simple/Undirected)
n = 100
p = 0.5
erdos_renyi_a = tools.sbm.erdos_renyi(n, p, symmetric=True)
erdos_renyi_b = tools.sbm.erdos_renyi(n, p, symmetric=True)

# Compute l1 norm
normalized_diff = (erdos_renyi_a - erdos_renyi_b) / n**2
l1 = np.linalg.norm(normalized_diff.flatten(), ord=1)

# Compute cutnorm
cutn_round, cutn_sdp, info = compute_cutnorm(erdos_renyi_a, erdos_renyi_b)

print("l1 norm: ", l1)  # prints l1 norm value near ~0.5
print("cutnorm rounded: ",
      cutn_round)  # prints cutnorm rounded solution near ~0
print("cutnorm sdp: ", cutn_sdp)  # prints cutnorm sdp solution near ~0