Skip to main content

Cutnorm approximation via Gaussian Rounding and Optimization with Orthogonality Constraints

Project description

Approximation via Gaussian Rounding and Optimization with Orthogonality Constraints

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.

Installation

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

$ pip install cutnorm

Example Usage

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

[ALON2004]

Noga Alon and Assaf Naor. 2004. Approximating the cut-norm via Grothendieck’s inequality. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC ‘04). ACM, New York, NY, USA, 72-80. DOI: http://dx.doi.org/10.1145/1007352.1007371

[WEN2013]

Zaiwen Wen and Wotao Yin. 2013. A feasible method for optimization with orthogonality constraints. Math. Program. 142, 1-2 (December 2013), 397-434. DOI: https://doi.org/10.1007/s10107-012-0584-1

[LOVASZ2009]

Lovasz, L. 2009. Very large graphs. ArXiv:0902.0132 [Math]. Retrieved from http://arxiv.org/abs/0902.0132

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

cutnorm-0.1.9.tar.gz (13.9 kB view details)

Uploaded Source

File details

Details for the file cutnorm-0.1.9.tar.gz.

File metadata

  • Download URL: cutnorm-0.1.9.tar.gz
  • Upload date:
  • Size: 13.9 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for cutnorm-0.1.9.tar.gz
Algorithm Hash digest
SHA256 227b7940fa8d7df64e5fc5629467c9511c7f1f3b5fd75bc32890fbd4e373e7c9
MD5 dc7557dd67ccfe224accef854804618c
BLAKE2b-256 c1d5072190d7c916b8acf651e2127abd970541b8c58faf66198e76d259eec3e6

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page