GEM: Graph Embedding Methods

GEM is a Python module that implements many graph (a.k.a. network) embedding algorithms. GEM is distributed under BSD license.

The module was developed and is maintained by Palash Goyal.

Implemented Methods

GEM implements the following graph embedding techniques:

• Laplacian Eigenmaps
• Locally Linear Embedding
• Graph Factorization
• Higher-Order Proximity preserved Embedding (HOPE)
• Structural Deep Network Embedding (SDNE)
• node2vec

A survey of these methods can be found in Graph Embedding Techniques, Applications, and Performance: A Survey.

Graph Format

We store all graphs using the DiGraph as directed weighted graph in python package networkx. The weight of an edge is stored as attribute "weight". We save each edge in undirected graph as two directed edges.

The graphs are saved using nx.write_gpickle in the networkx format and can be loaded by using nx.read_gpickle.

Repository Structure

• gem/embedding: existing approaches for graph embedding, where each method is a separate file
• gem/evaluation: evaluation tasks for graph embedding, including graph reconstruction, link prediction, node classification and visualization
• gem/utils: utility functions for graph manipulation, evaluation and etc.
• gem/data: input test graph (currently has Zachary's Karate graph)
• gem/c_src: source files for methods implemented in C++
• gem/c_ext: Python interface for source files in c_src using Boost.Python

Dependencies

GEM is tested to work on Python 2.7 and Python 3.6

The required dependencies are: Numpy >= 1.12.0, SciPy >= 0.19.0, Networkx >= 1.11, Scikit-learn >= 0.18.1.

To run SDNE, GEM requires Theano >= 0.9.0 and Keras = 2.0.2.

In case of Python 3, make sure it was compiled with ./configure --enable-shared, and that you have /usr/local/bin/python in your LD_LIBRARY_PATH

Install

The package uses setuptools, which is a common way of installing python modules. To install in your home directory, use:

    python setup.py install --user

To install for all users on Unix/Linux:

    sudo python setup.py install

You also can use python3 instead of python

Usage

Run the methods on Karate graph and evaluate them on graph reconstruction:

import matplotlib.pyplot as plt

from gem.utils import graph_util, plot_util
from gem.evaluation import visualize_embedding as viz
from gem.evaluation import evaluate_graph_reconstruction as gr
from time import time

from gem.embedding.gf       import GraphFactorization
from gem.embedding.hope     import HOPE
from gem.embedding.lap      import LaplacianEigenmaps
from gem.embedding.lle      import LocallyLinearEmbedding
from gem.embedding.node2vec import node2vec
from gem.embedding.sdne     import SDNE

# File that contains the edges. Format: source target
# Optionally, you can add weights as third column: source target weight
edge_f = 'gem/data/karate.edgelist'
# Specify whether the edges are directed
isDirected = True

# Load graph
G = graph_util.loadGraphFromEdgeListTxt(edge_f, directed=isDirected)
G = G.to_directed()

models = []
# You can comment out the methods you don't want to run
models.append(GraphFactorization(d=2, max_iter=100000, eta=1*10**-4, regu=1.0))
models.append(HOPE(d=4, beta=0.01))
models.append(LaplacianEigenmaps(d=2))
models.append(LocallyLinearEmbedding(d=2))
models.append(node2vec(d=2, max_iter=1, walk_len=80, num_walks=10, con_size=10, ret_p=1, inout_p=1))
models.append(SDNE(d=2, beta=5, alpha=1e-5, nu1=1e-6, nu2=1e-6, K=3,n_units=[50, 15,], rho=0.3, n_iter=50, xeta=0.01,n_batch=500,
                modelfile=['./intermediate/enc_model.json', './intermediate/dec_model.json'],
                weightfile=['./intermediate/enc_weights.hdf5', './intermediate/dec_weights.hdf5']))

for embedding in models:
    print ('Num nodes: %d, num edges: %d' % (G.number_of_nodes(), G.number_of_edges()))
    t1 = time()
    # Learn embedding - accepts a networkx graph or file with edge list
    Y, t = embedding.learn_embedding(graph=G, edge_f=None, is_weighted=True, no_python=True)
    print (embedding._method_name+':\n\tTraining time: %f' % (time() - t1))
    # Evaluate on graph reconstruction
    MAP, prec_curv, err, err_baseline = gr.evaluateStaticGraphReconstruction(G, embedding, Y, None)
    # Visualize
    viz.plot_embedding2D(embedding.get_embedding(), di_graph=G, node_colors=None)
    plt.show()

Cite

@article{goyal2017graph,
  title={Graph Embedding Techniques, Applications, and Performance: A Survey},
  author={Goyal, Palash and Ferrara, Emilio},
  journal={arXiv preprint arXiv:1705.02801},
  year={2017}
}