benedekrozemberczki/GEMSEC benedekrozemberczki/GEMSEC

  • Stars
    star
    244
  • Rank 160,219 (Top 4 %)
  • Language
    Python
  • License
    GNU General Publi...
  • Created over 6 years ago
  • Updated over 1 year ago
Twitter logo Share LinkedIn logo Share Facebook logo Share
benedekrozemberczki/GEMSEC
github

benedekrozemberczki

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

The TensorFlow reference implementation of 'GEMSEC: Graph Embedding with Self Clustering' (ASONAM 2019).

Graph Embedding with Self Clustering

Arxiv codebeat badge repo size benedekrozemberczki

GEMSEC is a graph embedding algorithm which learns an embedding and clustering jointly. The procedure places nodes in an abstract feature space where the vertex features minimize the negative log likelihood of preserving sampled vertex neighborhoods while the nodes are clustered into a fixed number of groups in this space. GEMSEC is a general extension of earlier work in the domain as it is an augmentation of the core optimization problem of sequence based graph embedding procedures and it is agnostic of the neighborhood sampling strategy (first/second-order random walks).

GEMSEC is available in the NetworkX extension package Karate Club.

The second-order random walks sampling methods were taken from the reference implementation of Node2Vec.

This repository provides a reference implementation for GEMSEC as described in the paper:

GEMSEC: Graph Embedding with Self Clustering. Benedek Rozemberczki, Ryan Davies, Rik Sarkar and Charles Sutton . ASONAM, 2019. https://arxiv.org/abs/1802.03997

The datasets are also available on SNAP.

Table of Contents

  1. Citing
  2. Requirements
  3. Datasets
  4. Logging
  5. Options
  6. Examples

Citing

If you find GEMSEC useful in your research, please consider citing the following paper:

>@inproceedings{rozemberczki2019gemsec,    
                title={{GEMSEC: Graph Embedding with Self Clustering}},    
                author={Rozemberczki, Benedek and Davies, Ryan and Sarkar, Rik and Sutton, Charles},    
                booktitle={Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2019},    
                pages={65-72},    
                year={2019},    
                organization={ACM}    
                }

Requirements

The codebase is implemented in Python 3.5.2 | Anaconda 4.2.0 (64-bit). Package versions used for development are just below.

networkx          2.4
tqdm              4.19.5
numpy             1.13.3
pandas            0.20.3
tensorflow-gpu    1.12.0
jsonschema        2.6.0
texttable         1.5.1
python-louvain    0.11

Datasets

The code takes an input graph in a csv file. Every row indicates an edge between two nodes separated by a comma. The first row is a header. Nodes should be indexed starting with 0. Sample graphs for the `Facebook Politicians` and `Facebook Companies` datasets are included in the `data/` directory.

Logging

The models are defined in a way that parameter settings and cluster quality is logged in every single epoch. Specifically we log the followings:

1. Hyperparameter settings.     We save each hyperparameter used in the experiment.
2. Cost per epoch.              Embedding, clustering and regularization cost are stored depending on the model type.
3. Cluster quality.             Measured by modularity. We calculate it both for the classical and neural clusterings per epoch.
4. Runtime.                     We measure the time needed for optimization and data generation per epoch -- measured by seconds.

Options

Learning of the embedding is handled by the src/embedding_clustering.py script which provides the following command line arguments.

Input and output options

  --input                STR      Input graph path.                              Default is `data/politician_edges.csv`.
  --embedding-output     STR      Embeddings path.                               Default is `output/embeddings/politician_embedding.csv`.
  --cluster-mean-output  STR      Cluster centers path.                          Default is `output/cluster_means/politician_means.csv`.
  --log-output           STR      Log path.                                      Default is `output/logs/politician.log`.
  --assignment-output    STR      Node-cluster assignment dictionary path.       Default is `output/assignments/politician.json`.
  --dump-matrices        BOOL     Whether the trained model should be saved.     Default is `True`.
  --model                STR      The model type.                                Default is `GEMSECWithRegularization`.

Random walk options

  --walker   STR         Random walker order (first/second).              Default is `first`.
  --P        FLOAT       Return hyperparameter for second-order walk.     Default is 1.0
  --Q        FLOAT       In-out hyperparameter for second-order walk.     Default is 1.0.

Skipgram options

  --dimensions               INT        Number of dimensions.                              Default is 16.
  --random-walk-length       INT        Length of random walk per source.                  Default is 80.
  --num-of-walks             INT        Number of random walks per source.                 Default is 5.
  --window-size              INT        Window size for proximity statistic extraction.    Default is 5.
  --distortion               FLOAT      Downsampling distortion.                           Default is 0.75.
  --negative-sample-number   INT        Number of negative samples to draw.                Default is 10.

Model options

  --initial-learning-rate   FLOAT    Initial learning rate.                                        Default is 0.001.
  --minimal-learning-rate   FLOAT    Final learning rate.                                          Default is 0.0001.
  --annealing-factor        FLOAT    Annealing factor for learning rate.                           Default is 1.0.
  --initial-gamma           FLOAT    Initial clustering weight coefficient.                        Default is 0.1.
  --final-gamma             FLOAT    Final clustering weight coefficient.                          Default is 0.5.  
  --lambd                   FLOAT    Smoothness regularization penalty.                            Default is 0.0625.
  --cluster-number          INT      Number of clusters.                                           Default is 20.
  --overlap-weighting       STR      Weight construction technique for regularization.             Default is `normalized_overlap`.
  --regularization-noise    FLOAT    Uniform noise max and min on the feature vector distance.     Default is 10**-8.

Examples

The following commands learn a graph embedding and cluster center and writes them to disk. The node representations are ordered by the ID.

Creating a GEMSEC embedding of the default dataset with the default hyperparameter settings. Saving the embedding, cluster centres and the log file at the default path.

$ python src/embedding_clustering.py

Creating a DeepWalk embedding of the default dataset with the default hyperparameter settings. Saving the embedding, cluster centres and the log file at the default path.

$ python src/embedding_clustering.py --model DeepWalk

Turning off the model saving.

$ python src/embedding_clustering.py --dump-matrices False

Creating an embedding of an other dataset the Facebook Companies. Saving the output and the log in a custom place.

$ python src/embedding_clustering.py --input data/company_edges.csv  --embedding-output output/embeddings/company_embedding.csv --log-output output/cluster_means/company_means.csv --cluster-mean-output output/logs/company.json

Creating a clustered embedding of the default dataset in 32 dimensions, 20 sequences per source node with length 160 and 10 cluster centers.

$ python src/embedding_clustering.py --dimensions 32 --num-of-walks 20 --random-walk-length 160 --cluster-number 10

License

More Repositories

1

awesome-graph-classification

A collection of important graph embedding, classification and representation learning papers with implementations.
Python
4,666
star
2

pytorch_geometric_temporal

PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models (CIKM 2021)
Python
2,455
star
3

awesome-decision-tree-papers

A collection of research papers on decision, classification and regression trees with implementations.
Python
2,248
star
4

awesome-community-detection

A curated list of community detection research papers with implementations.
Python
2,224
star
5

karateclub

Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs (CIKM 2020)
Python
2,065
star
6

awesome-fraud-detection-papers

A curated list of data mining papers about fraud detection.
Python
1,481
star
7

CapsGNN

A PyTorch implementation of "Capsule Graph Neural Network" (ICLR 2019).
Python
1,216
star
8

awesome-gradient-boosting-papers

A curated list of gradient boosting research papers with implementations.
Python
966
star
9

graph2vec

A parallel implementation of "graph2vec: Learning Distributed Representations of Graphs" (MLGWorkshop 2017).
Python
860
star
10

ClusterGCN

A PyTorch implementation of "Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks" (KDD 2019).
Python
757
star
11

littleballoffur

Little Ball of Fur - A graph sampling extension library for NetworKit and NetworkX (CIKM 2020)
Python
676
star
12

SimGNN

A PyTorch implementation of "SimGNN: A Neural Network Approach to Fast Graph Similarity Computation" (WSDM 2019).
Python
657
star
13

awesome-monte-carlo-tree-search-papers

A curated list of Monte Carlo tree search papers with implementations.
Python
565
star
14

datasets

A repository of pretty cool datasets that I collected for network science and machine learning research.
551
star
15

GraphWaveletNeuralNetwork

A PyTorch implementation of "Graph Wavelet Neural Network" (ICLR 2019)
Python
548
star
16

MixHop-and-N-GCN

An implementation of "MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing" (ICML 2019).
Python
395
star
17

APPNP

A PyTorch implementation of "Predict then Propagate: Graph Neural Networks meet Personalized PageRank" (ICLR 2019).
Python
351
star
18

AttentionWalk

A PyTorch Implementation of "Watch Your Step: Learning Node Embeddings via Graph Attention" (NeurIPS 2018).
Python
309
star
19

SGCN

A PyTorch implementation of "Signed Graph Convolutional Network" (ICDM 2018).
Python
262
star
20

GAM

A PyTorch implementation of "Graph Classification Using Structural Attention" (KDD 2018).
Python
261
star
21

SEAL-CI

A PyTorch implementation of "Semi-Supervised Graph Classification: A Hierarchical Graph Perspective" (WWW 2019)
Python
204
star
22

shapley

The official implementation of "The Shapley Value of Classifiers in Ensemble Games" (CIKM 2021).
Python
203
star
23

Splitter

A Pytorch implementation of "Splitter: Learning Node Representations that Capture Multiple Social Contexts" (WWW 2019).
Python
203
star
24

DANMF

A sparsity aware implementation of "Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection" (CIKM 2018).
Python
194
star
25

GraphWaveMachine

A scalable implementation of "Learning Structural Node Embeddings Via Diffusion Wavelets (KDD 2018)".
Python
176
star
26

role2vec

A scalable Gensim implementation of "Learning Role-based Graph Embeddings" (IJCAI 2018).
Python
158
star
27

MUSAE

The reference implementation of "Multi-scale Attributed Node Embedding". (Journal of Complex Networks 2021)
Python
136
star
28

EdMot

An implementation of "EdMot: An Edge Enhancement Approach for Motif-aware Community Detection" (KDD 2019)
Python
128
star
29

M-NMF

An implementation of "Community Preserving Network Embedding" (AAAI 2017)
Python
119
star
30

diff2vec

Reference implementation of Diffusion2Vec (Complenet 2018) built on Gensim and NetworkX.
Python
117
star
31

LabelPropagation

A NetworkX implementation of Label Propagation from a "Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks" (Physical Review E 2008).
Python
111
star
32

walklets

A lightweight implementation of Walklets from "Don't Walk Skip! Online Learning of Multi-scale Network Embeddings" (ASONAM 2017).
Python
98
star
33

tigerlily

TigerLily: Finding drug interactions in silico with the Graph.
Jupyter Notebook
95
star
34

BANE

A sparsity aware implementation of "Binarized Attributed Network Embedding" (ICDM 2018).
Python
85
star
35

EgoSplitting

A NetworkX implementation of "Ego-splitting Framework: from Non-Overlapping to Overlapping Clusters" (KDD 2017).
Python
80
star
36

ASNE

A sparsity aware and memory efficient implementation of "Attributed Social Network Embedding" (TKDE 2018).
Python
77
star
37

TENE

A sparsity aware implementation of "Enhanced Network Embedding with Text Information" (ICPR 2018).
Python
71
star
38

SINE

A PyTorch Implementation of "SINE: Scalable Incomplete Network Embedding" (ICDM 2018).
Python
69
star
39

RolX

An alternative implementation of Recursive Feature and Role Extraction (KDD11 & KDD12)
Python
58
star
40

GraRep

A SciPy implementation of "GraRep: Learning Graph Representations with Global Structural Information" (WWW 2015).
Python
58
star
41

PDN

The official PyTorch implementation of "Pathfinder Discovery Networks for Neural Message Passing" (WebConf '21)
Python
55
star
42

TADW

An implementation of "Network Representation Learning with Rich Text Information" (IJCAI '15).
Python
54
star
43

spatiotemporal_datasets

Spatiotemporal datasets collected for network science, deep learning and general machine learning research.
43
star
44

NMFADMM

A sparsity aware implementation of "Alternating Direction Method of Multipliers for Non-Negative Matrix Factorization with the Beta-Divergence" (ICASSP 2014).
Python
40
star
45

FEATHER

The reference implementation of FEATHER from the CIKM '20 paper "Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models".
Python
40
star
46

BoostedFactorization

An implementation of "Multi-Level Network Embedding with Boosted Low-Rank Matrix Approximation" (ASONAM 2019).
Python
33
star
47

resolutions-2019

A list of data mining and machine learning papers that I implemented in 2019.
20
star
48

OrbitalFeatures

A sparsity aware implementation of "Biological Network Comparison Using Graphlet Degree Distribution" (Bioinformatics 2007)
Python
19
star
49

FSCNMF

An implementation of "Fusing Structure and Content via Non-negative Matrix Factorization for Embedding Information Networks".
Python
18
star
50

GRAF

Inner product natural graph factorization machine used in 'GEMSEC: Graph Embedding with Self Clustering' .
Python
10
star
51

HullCoverConditionedUnitDiskGraph

A generator for unit disk graphs conditioned on concave hull cover.
Python
8
star
52

AV_Ultimate_Student_Hunt

Solution for the Ultimate Student Hunt Challenge (1st place).
R
8
star
53

NestedSubtreeHash

A distributed implementation of "Nested Subtree Hash Kernels for Large-Scale Graph Classification Over Streams" (ICDM 2012).
Python
7
star
54

Societe-General

Solution for ENS - Societe Generale Challenge (1st place).
R
5
star
55

resolutions-2020

4
star
56

graphmining.ai

Benedek Rozemberczki Personal Webpage
4
star
57

benedekrozemberczki

3
star