snapvx-performance.py

import numpy as np
from snapvx import *
from cvxpy import *
import time

np.random.seed(123)

num_nodes = 2000
node_deg = 3

snapGraph = GenRndDegK(num_nodes, node_deg)
target = numpy.random.randn(num_nodes)

# --
# Solve w/ snapvx

gvx = TGraphVX(snapGraph)

for i in range(num_nodes):
    x = Variable(1, name='x')
    gvx.SetNodeObjective(i, square(norm(x - target[i])))

def netLasso(src, dst, data):
    return (norm1(src['x'] - dst['x']), [])

gvx.AddEdgeObjectives(netLasso)

t = time.time()
gvx.Solve(UseADMM=False)
time.time() - t 
# 11 seconds

# --
# Solve directly w/ CVXPY

edges = np.array([(e.GetSrcNId(), e.GetDstNId()) for e in snapGraph.Edges()])

X = Variable(num_nodes, 1, name='x')

mse = square(norm(X - target))
las = norm1(X[edges[:,0]] - X[edges[:,1]])
prob = Problem(Minimize(mse + las))

t = time.time()
_ = prob.solve()
time.time() - t 
# 1 second

# --
# What's going on?

X2 = [Variable(1, name='x') for _ in range(num_nodes)]

mse = sum([square(norm(X2[i] - target[i])) for i in range(num_nodes)])
las = sum([norm1(X2[i] - X2[j]) for i,j in edges])
prob = Problem(Minimize(mse + las))

t = time.time()
_ = prob.solve()
time.time() - t 
# 11 seconds

# Appears that using a single Nx1 variable is much faster than N 1x1 variables
# `snapvx` does the latter, even when `useClustering=True`