Code for experimentation on graph scattering transforms. If any part of this code is used, the following paper must be cited:
F. Gama, J. Bruna, and A. Ribeiro, "Stability of graph scattering transforms," in 33rd Conf. Nerual Inform. Process. Syst. Vancouver, BC: Neural Inform. Process. Syst. Foundation, 8-14 Dec. 2019.
Any questions, comments or suggestions, please e-mail Fernando Gama at [email protected]. The specific random seeds used to get the results that appear in the paper can be obtained by request.
Graph scattering transform depend on a multi-resolution graph wavelet filter bank. This code implements three different wavelet filter banks, namely:
- Diffusion wavelets (Geometric scattering):
F. Gao, G. Wolf, and M. Hirn, "Geometric scattering for graph data analysis," in 36th Int. Conf. Mach. Learning, Long Beach, CA, 15-9 June 2019, pp. 1–10.
F. Gama, A. Ribeiro, and J. Bruna, "Diffusion Scattering Transforms on Graphs," in 7th Int. Conf. Learning Representations. New Orleans, LA: Assoc. Comput. Linguistics, 6-9 May 2019, pp. 1–12.
R. R. Coifman and M. Maggioni, "Diffusion wavelets," Appl. Comput. Harmonic Anal., vol. 21, no. 1, pp. 53–94, July 2006.
- Monic polynomials interpolated by a cubic polynomial:
D. K. Hammond, P. Vandergheynst, and R. Gribonval, "Wavelets on graphs via spectral graph theory," Appl. Comput. Harmonic Anal., vol. 30, no. 2, pp. 129–150, March 2011.
- Tight frames of Hann wavelets:
D. I. Shuman, C. Wiesmeyr, N. Holighaus, and P. Vandergheynst, "Spectrum-adapted tight graph wavelet and vertex-frequency frames," IEEE Trans. Signal Process., vol. 63, no. 16, pp. 4223–4235, Aug. 2015.
- Additionally, this code allows for comparison with a trainable GNN, in particular, a GIN:
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?" in 7th Int. Conf. Learning Representations. New Orleans, LA: Assoc. Comput. Linguistics, 6-9 May 2019, pp. 1–17.
F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, "Convolutional neural network architectures for signals supported on graphs," IEEE Trans. Signal Process., vol. 67, no. 4, pp. 1034–1049, Feb. 2019.
Three experiments are run.
1. The first one, under the name GSTsmallWorld.py is a synthetic experiment on a small world graph. The objective of this experiment is to showcase the effect of the stability bound on graph scattering transform under a controlled environment.
D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks," Nature, vol. 393, no. 6684, pp. 440–442, June 1998.
2. The second one, on the file GSTauthorship.py considers the problem of authorship attribution. It demonstrates the richness of the graph scattering representation on a real dataset. The dataset is available under datasets/authorshipData/ and the following paper must be cited whenever such dataset is used
S. Segarra, M. Eisen, and A. Ribeiro, "Authorship attribution through function word adjacency networks," IEEE Trans. Signal Process., vol. 63, no. 20, pp. 5464–5478, Oct. 2015.
3. The third and last one, on the file GSTfacebook.py studies the problem of source localization on a subnetwork of a Facebook graph. This experiment is meant to also show the richness of the graph scattering representation under a real graph perturbation, with a synthetic signal defined on top of it. The original dataset is available here, and use of this dataset must cite the following paper
J. McAuley and J. Leskovec, "Learning to discover social circles in Ego networks," in 26th Neural Inform. Process. Syst. Stateline, TX: NIPS Foundation, 3-8 Dec. 2012.
The code is written in Python3. Details as follows.
The following Python libraries are required: os, numpy, matplotlib, pickle, datetime, sklearn, torch, hdf5storage, urllib, gzip, shutil and scipy, as well as a LaTeX installation.
The three main files GSTauthorship.py, GSTfacebook.py and GSTsmallWorld.py consists of the three main experiments. The first lines of code on each of those files (after importing the corresponding libraries) have the main parameters defined, which could be edited for running experiment under a different set of hyperparameters.
The directory Modules/ contains the implemented graph scattering transforms. In most cases, it has a function that just compute the corresponding equation, a wavelet function that computes the graph wavelet filter bank, and a graph scattering transform class that computes the entire representation. Additionally, the directory Modules/ contains architectures.py which has the basic definition of a GNN, and model.py which provides the class that binds together the architecture, optimizer and loss function of a trainable GNN, as well as the methods for training and evaluating.
Under Utils/ there are four modules containing utilitary classes and functions, such as those handling trainable GNNs graphML.py, the graph graphTools.py, handling the data dataTools.py and some miscellaneous tools miscTools.py.
The code runs by simply executing python GSTsmallWorld.py or any of the two other experiments (assuming python is the command for Python3). For running the authorship attribution experiment, the .rar files on datasets/ have to be uncompressed. For obtaining the entire Facebook graph, a connection to the internet is required since the dataset is download from its source.
October 27, 2019: Upload corresponding to the revised version of the paper, camera-ready for NeurIPS 2019. Main changes include the implementation of the geometric scattering as well as the addition of a trainable GNN (GIN). Also, bugs put forward by other users have been addressed.
June 12, 2019: First upload corresponding to the original submission of the paper to NeurIPS 2019 (arXiv:1906.04784v1).