mu-conductance low-rank SDP

This repo contains codes for the following ICML2023 paper:

Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming

If you feel it helpful for your research, please cite the paper mentioned above.

Environment

We use julia1.8 and we provide the Project.toml and Manifest.toml files for our environment. You should be able to activate it by typing activate . in Pkg REPL(i.e. ] activate .).

Datasets

The synthetic and real-world datasets we use are included in ./data/input except soc-LiveJournal because of size.

Alternatively, you can access them from (ca-HepPh, ca-AstroPh, facebook,deezer, email-Enron, dblp, soc-LiveJournal).

The small synthetic graphs can be generated by running syntheticgnr.jl, we attached one example in the file.

Dataloader

We use read_data.jl to load the adjacency matrix of a graph, e.g.

include("read_data.jl")
A = load_graph("email-Enron")
A = load_graph("ca-AstroPh")
A = load_graph("graph-2018-11-09.edges")

Solving low-rank SDP using Augmented Lagrangian Method

We use lrsdp_exp.jl to run experiments with regard to low-rank SDP, e.g.

julia -p 10 lrsdp_exp.jl --filename ca-HepPh

Here -p 10 specifies how many cores you want to use. For a complete list of arguments and their default values, please read args.jl. Also, we provide default configs for a set of datasets at /src/configs/lrsdp_config.toml.

Some interesting fields of results are KKT_dt(Running time of EIGVAL), ALM_dt(Running time of Augmented Lagrangian), objval(Objective Value), YS(Solution), dual_feasi(Violation of Dual feasibility).

Once you got results of low-rank SDP, you can plot them with running

include("myplot.jl")
lrsdpobjplot("ca-HepPh", [1e-5, 1e-4, 1e-3, 1e-2], 10)
savefig(figpath)

where the 2nd argument is a list of mus that you are interested in and the 3rd argument is the rank parameter of low-rank SDP.

Computing Network Community using seeded PageRank

We use ncp_exp.jl to generate NCPs, e.g.

julia -p 5 ncp_exp.jl --filename ca-HepPh --epsvals 1e-5 1e-6 1e-7 --setsizes 10 10 10

Here -p 5 specifies how many cores you want to use, --epsvals specifies which set of eps you want to run seeded PageRank(ACL) and --setsizes specifies number of seeds you want to run for each eps on one core. So in total, the command above will run 150 seeded PageRanks parallelly on 5 cores. If you do not provide epsvals and setsizes, then the default parameters provided in diffusions.jl will be used.

After getting the network community profile, you can simply call diffision_ncpplot from ncpplots.jl to visualize it.

To observe gap shrinking, just increase the number of eps you use and try more seeds. In general, the smaller the eps is, the less local the cut will be, but it will also be more time consuming.

k-core analysis

To analysze k-core of a network, you can simply call function kcore in read_data.jl on the adjacency matrix you have to get the k-core of a network. Then all low-rank SDP and network community computation follows.

SDP

You can solve the mu-conductance SDP with running for example

include("read_data.jl")
include("spectral.jl")
A, xy = load_graph_edge_xy(path2file)
xy = xy'
mu = 0.1

opt, X = spectral_balanced_cut3(A, mu; eps=1e-4, solver="SCS")

Further to visualize the rank-1 approximation of the solution on the graph, you can run

include("myplot.jl")
f = rank1_approx(X)
lxy = logpolar(xy)
plotgraph(A, lxy)
showvector(f)

Acknowledgement

Our hexbins.jl is copied from HexBinPlots.jl belonging to RalphAs and modified for our purpose, thanks for the great package.