Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering

Related tags

Deep Learning SLQ
Overview

SLQ

code for SLQ project, see our arXiv paper

@Article{Liu-preprint-slq,
  author     = {Meng Liu and David F. Gleich},
  journal    = {arXiv},
  title      = {Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering},
  year       = {2020},
  pages      = {2006.08569},
  volume     = {cs.SI},
  arxiv      = {http://arxiv.org/abs/2006.08569},
  mysoftware = {https://github.com/MengLiuPurdue/SLQ},
}

To run our code, simply include("SLQ.jl") This has minimal dependencies. Then to run the code on an Erdos-Renyi graph, run

using SparseArrays
# make an Erdos Renyi graph
A = triu(sprand(100,100,8/100),1)
A = max.(A,A') # symmetrize
fill!(A.nzval, 1) # set all values to 1. 
G = SLQ.graph(A) # convert an adjacency matrix into a graph
SLQ.slq_diffusion(SLQ.graph(A), 
	[1], # seed set
	 0.1, # value of gamma (regularization on seed) 
	 0.1, # value of kappa (sparsity regularization)
	 0.5, # value of rho (KKT apprx-val)
    SLQ.loss_type(1.4,0.0) # the loss-type, this is a 1.4-norm without huber)

SLQ via CVX

We need cvxpy. This can be installed in Julia's conda-forge environment. We try to do this when you include("SLQcvx.jl"). CVX does not support the q-huber penalties. This should just work.

Additional experiemtns with other dependencies

We need localgraphclustering for comparisons with CRD.

Install localgraphclustering

On my mac, with a homebrew install of Python, I just ran

pip3 install localgraphclustering --user

And then everything should just work. This will install localgraphclustering for the system python3. But then we use PyCall conda and just point it at the needed directory. Try include("CRD.jl").

Experiments

  • Visualization of image boundaries: experiment-image-boundary.jl
  • Visualization of effects in grid graph: experiment-grid-vis.jl
  • Experiment on LFR graphs: experiment-sparsity-runtime.jl and results analysis visualization-running-time.jl
  • Experiment on Facebook graphs: experiment-faebook.jland results analysis visualization-facebook-comapct.jl (this makes a lot of images) and a table to put into a latex document.
  • Experiment on DBLP and LiveJournal graphs: experiment-huge-graph.jl and results analysis visualization-huge-graph-compact.jl
  • Experiemnt on varying seeds in appendix: experiment-vary-seeds.jl
You might also like...
A strongly-typed genetic programming framework for Python

monkeys "If an army of monkeys were strumming on typewriters they might write all the books in the British Museum." monkeys is a framework designed to

 GrailQA: Strongly Generalizable Question Answering
GrailQA: Strongly Generalizable Question Answering

GrailQA is a new large-scale, high-quality KBQA dataset with 64,331 questions annotated with both answers and corresponding logical forms in different syntax (i.e., SPARQL, S-expression, etc.). It can be used to test three levels of generalization in KBQA: i.i.d., compositional, and zero-shot.

UniMoCo: Unsupervised, Semi-Supervised and Full-Supervised Visual Representation Learning
UniMoCo: Unsupervised, Semi-Supervised and Full-Supervised Visual Representation Learning

UniMoCo: Unsupervised, Semi-Supervised and Full-Supervised Visual Representation Learning This is the official PyTorch implementation for UniMoCo pape

Code for CoMatch: Semi-supervised Learning with Contrastive Graph Regularization

CoMatch: Semi-supervised Learning with Contrastive Graph Regularization (Salesforce Research) This is a PyTorch implementation of the CoMatch paper [B

This is the repository for the NeurIPS-21 paper [Contrastive Graph Poisson Networks: Semi-Supervised Learning with Extremely Limited Labels].

CGPN This is the repository for the NeurIPS-21 paper [Contrastive Graph Poisson Networks: Semi-Supervised Learning with Extremely Limited Labels]. Req

A Sklearn-like Framework for Hyperparameter Tuning and AutoML in Deep Learning projects. Finally have the right abstractions and design patterns to properly do AutoML. Let your pipeline steps have hyperparameter spaces. Enable checkpoints to cut duplicate calculations. Go from research to production environment easily.
Source codes for the paper "Local Additivity Based Data Augmentation for Semi-supervised NER"

LADA This repo contains codes for the following paper: Jiaao Chen*, Zhenghui Wang*, Ran Tian, Zichao Yang, Diyi Yang: Local Additivity Based Data Augm

Wanli Li and Tieyun Qian: Exploit a Multi-head Reference Graph for Semi-supervised Relation Extraction, IJCNN 2021

MRefG Wanli Li and Tieyun Qian: "Exploit a Multi-head Reference Graph for Semi-supervised Relation Extraction", IJCNN 2021 1. Requirements To reproduc

Hybrid CenterNet - Hybrid-supervised object detection / Weakly semi-supervised object detection
Hybrid CenterNet - Hybrid-supervised object detection / Weakly semi-supervised object detection

Hybrid-Supervised Object Detection System Object detection system trained by hybrid-supervision/weakly semi-supervision (HSOD/WSSOD): This project is

Owner
Meng Liu
Meng Liu
Awesome Deep Graph Clustering is a collection of SOTA, novel deep graph clustering methods

ADGC: Awesome Deep Graph Clustering ADGC is a collection of state-of-the-art (SOTA), novel deep graph clustering methods (papers, codes and datasets).

yueliu1999 297 Dec 27, 2022
sssegmentation is a general framework for our research on strongly supervised semantic segmentation.

sssegmentation is a general framework for our research on strongly supervised semantic segmentation.

null 445 Jan 2, 2023
Graph Regularized Residual Subspace Clustering Network for hyperspectral image clustering

Graph Regularized Residual Subspace Clustering Network for hyperspectral image clustering

Yaoming Cai 5 Jul 18, 2022
This is the repository for the AAAI 21 paper [Contrastive and Generative Graph Convolutional Networks for Graph-based Semi-Supervised Learning].

CG3 This is the repository for the AAAI 21 paper [Contrastive and Generative Graph Convolutional Networks for Graph-based Semi-Supervised Learning]. R

null 12 Oct 28, 2022
End-to-end face detection, cropping, norm estimation, and landmark detection in a single onnx model

onnx-facial-lmk-detector End-to-end face detection, cropping, norm estimation, and landmark detection in a single onnx model, model.onnx. Demo You can

atksh 42 Dec 30, 2022
Paddle implementation for "Cross-Lingual Word Embedding Refinement by ℓ1 Norm Optimisation" (NAACL 2021)

L1-Refinement Paddle implementation for "Cross-Lingual Word Embedding Refinement by ℓ1 Norm Optimisation" (NAACL 2021) ?? A more detailed readme is co

Lincedo Lab 4 Jun 9, 2021
A PyTorch implementation of "Semi-Supervised Graph Classification: A Hierarchical Graph Perspective" (WWW 2019)

SEAL ⠀⠀⠀ A PyTorch implementation of Semi-Supervised Graph Classification: A Hierarchical Graph Perspective (WWW 2019) Abstract Node classification an

Benedek Rozemberczki 202 Dec 27, 2022
Project looking into use of autoencoder for semi-supervised learning and comparing data requirements compared to supervised learning.

Project looking into use of autoencoder for semi-supervised learning and comparing data requirements compared to supervised learning.

Tom-R.T.Kvalvaag 2 Dec 17, 2021
Python Implementation of algorithms in Graph Mining, e.g., Recommendation, Collaborative Filtering, Community Detection, Spectral Clustering, Modularity Maximization, co-authorship networks.

Graph Mining Author: Jiayi Chen Time: April 2021 Implemented Algorithms: Network: Scrabing Data, Network Construbtion and Network Measurement (e.g., P

Jiayi Chen 3 Mar 3, 2022
Named Entity Recognition with Small Strongly Labeled and Large Weakly Labeled Data

Named Entity Recognition with Small Strongly Labeled and Large Weakly Labeled Data arXiv This is the code base for weakly supervised NER. We provide a

Amazon 92 Jan 4, 2023