GraphWave

Spectral Wavelets for learning structural signatures in complex networks

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
• files:
  • characteristic_functions.py: functions for computing the characteristic functions.
  • 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:

• networkx: allows easy manipulation and plotting of graph objects (more information in the Networkx website).
• pyemd: module for computing Earth Mover distances (for trying out other distances between diffusion distributions. More information in the pyemd website)

Also, need standard packages: scipy, sklearn, seaborn for analyzing and plotting results.

Note: heat diffusion scaling wavelets can also be computed with the Graph Signal Processing toolbox pygsp (accessible through the EPFL website ), which, beyond structural similarities, has plenty of extremely useful features for handling signals on graphs.

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_alg(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