IE532: Handouts

0. Homework 0 (no need to turn in)

0. Introduction (Jupyter NB)

1. Eulerian cycle and minimum spanning tree [ Slides]

   1. Eulerian cycle exercise [ Jupyter NB , html ] is due September 6th Wednesday midnight via email to the TA

   2. Minimum spanning tree exercise [ Jupyter NB , 1mst_data.csv , html ] is due September 13th Wednesday midnight via email to the TA

2. Matching and stable marriage problem [Slides]

   1. Stable marriage exercise [ Jupyter NB , matching.py , html ] is due September 24th Sunday midnight via email to the TA

3. Paths, trees, and connectivity [ Slides ]

   1. shortest paths exercise [ zip file containing the Jupyter NB ] is due October 1st Sunday midnight via Compass

4. Random walk and graph Laplacian [ Slides ]

5. Supervised Learning [ Slides ], simple spiral example [ Spiral example Jupyter NB ], real-time examples [ 2-d example ]

   1. linear regression and logistic regression exercise [ Jupyter NB ] is due Sunday Oct 22nd midnight via Compass

   2. neural network exercise [ Jupyter NB ] is due Sunday Oct 29th midnight via Compass

6. Graph Neural Network [ Slides ]

   1. graph neural network exercise [ Jupyter NB ] is due Sunday Nov 5th midnight via Compass

7. Generative adversarial networks [ Slides ]

8. Network flow and maximum flow problem [ Slides ]

9. Linear Programming

10. Online Algorithms

11. Cake Cutting

12. Submodular functions

Additional reading that might be helpful in the project:

1. ‘‘Semi-supervised classification with graph convolutional networks’’ by TN Kipf, M Welling ICLR2017

2. ‘‘Variational Graph Auto-Encoders’’ by T N. Kipf, M Welling arXiv

3. ‘‘A note on learning algorithms for quadratic assignment with graph neural networks’’ by A Nowak, S Villar, AS Bandeira, J Bruna arXiv

4. ‘‘Community Detection with Graph Neural Networks’’ by J Bruna, X Li arXiv

5. ‘‘Fast Incremental and Personalized PageRank’’ by Bahman Bahmani, Abdur Chowdhury, Ashish Goel arXiv

6. ‘‘Personalized PageRank Estimation and Search: A Bidirectional Approach’’ by Peter Lofgren, Siddhartha Banerjee, Ashish Goel arXiv

7. ‘‘FrogWild! – Fast PageRank Approximations on Graph Engines’’ by Ioannis Mitliagkas, Michael Borokhovich, Alexandros G. Dimakis, Constantine Caramanis arXiv

8. ‘‘Neural Message Passing for Quantum Chemistry’’, Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, George E. Dahl arXiv

9. ‘‘Graph2Seq: Scalable Learning Dynamics for Graphs’’, OpenReview