Algorithm Anti-Differentiation: A case study with PageRank, min-cuts, and flow
David F. Gleich
Michael W. Mahoney
These are the computational codes and data that go along with the ICML 2014 paper
David F. Gleich and Michael Mahoney Algorithm Anti-Differentiation: A case study with min-cuts, spectral, and flow In Proceedings of the International Conference on Machine Learning, 2014.
figure_1_example.mProduce the vectors for Figure 1 in the ICML paper
example_netscience.mProduce the netscience Figures for the ICML paper
demos/simple_example.mA simple example suitable for live demos
acl_method.mAn implementation of the Andersen-Chung-Lang push method to compute a PageRank vector
flow_improve.mAn algorithm for the FlowImprove method of Andersen and Lang
prl1_gurobi.mUse gurobi to solve an l1-PageRank problem
prcut_gurobi.mUse gurobi to solve a min-cut on the PageRank cut graph
cut_graph.mConstruct the cut-graph for FlowImiprove
general_cut_graph.mConstruct the PageRank cut-graph for general constructions.
gmatrices.mReturn a struct of all the matrices associated with a graph.
igraph_draw.mUse igraph via python to layout a graph
incidence_matrix.mCreate the node-edge indicence matrix for a graph
laplacian.mConsruct the Laplacian matrix of a graph
load_graph.mLoad one of the datasets and avoid icky path problems
nlaplacian.mConstruct the normalized Laplacian of a graph
normout.mCompute a row-stochastic matrix from an adjacency matrix.
set_figure_size.mThe most useful script to make Matlab figures look good
setup_paths.mAdd all the required libraries to the matlab path, and the code itself
wadjacency.mConstruct the weighted adjacency matrix of a graph
test_prcut_gurobi.mMake sure gurobi and CVX agree for the prcut problem
test_prl1_gurobi.mMake sure gurobi and CVX agree for the prl1 problem
This directory contains a whole bunch of scripts that we developed while working out the theory. Think of this as a lab-notebook for what we looked at before the full picture came together.