liwzhi/graphwave

GraphWave

Spectral Wavelets for learning structural signatures in complex networks

(Update: 10/31/17: this repository is in the process of being cleaned up and made more ''user-friendly'. While we are trying to make this cleaning process as fast as possible, we apologize for the broken modules paths and bugs in the meanwhile)

This folder contains the code for GraphWave, an algorithm for computing structural signatures for nodes in a network using heat spectral wavelets. This code folder is organized as follows:

• shapes/: contains the functions for generating (more or less) regular graphs and shapes
• performance_evaluation/: functions computing different metrics for assessing the quality of the embeddings generated by GraphWave
• test_perturbation_synthetic/: set of ipython notebooks for running the synthetic experiments described in the paper.
• utils/: set of helper functions
• distances/: functions for computing distances between embeddings
• files:
  • characteristic_functions.py: functions for computing the characteristic functions.
  • heat_diffusion.py: function for computing the heat kernel signatures.
  • graphwave.py: wrapper function for computing the embeddings.

 

 

Prerequisites

GraphWave was written for Python 2.7 and requires the installation of the following Python libraries:

• pygsp: module for computing the wavelets (from the EPFL website ). To install, simply run in your local terminal:

$ pip install pygsp

• networkx: allows easy manipulation and plotting of graph objects (more information in the Networkx website).

Installation can be done via pip or conda:

$ pip install networkx

or

$ conda install networkx

• pyemd: module for computing Earth Mover distances (for trying out other distances between diffusion distributions. More information in the pyemd website) Installation can also be done via pip by running:

$ pip install pyemd

• scipy, sklearn, seaborn: for analyzing and plotting results

 

 

Running Graphwave

A full example on how to use GraphWave is provided in the ''Using GraphWave.ipynb" of this directory. In a nutshell:

• input: nx (or pygsp) Graph structure
• compute the heat wavelets
• embed the distributions in Euclidean space using the characteristic function
• output: signatures, which can be used in one's favorite Machine Learning framework.

For a given graph G (of type pygsp or nx),GraphWave structural signatures can be simply computing by calling:

>from graphwave import graphwave

>chi,heat_print, taus=graphwave(G, 'automatic', verbose=False)

Authors

• Anonymous at this time

Acknowledgements

We would like to thank the authors of struc2vec for the open access of the implementation of their method, as well as Lab41 for its open-access implementation of RolX.

License

This project is licensed under the MIT License - see the LICENSE.md file for details

=======

graphwave

5d0c25e5cc6baee37b445b1c0d232dc0d7e43e52