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
characteristic_functions.py: functions for computing the characteristic functions.
graphwave.py: wrapper function for computing the embeddings.
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.
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)
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.
This project is licensed under the MIT License - see the LICENSE.md file for details