CS 59000: Graphs in Machine Learning (Spring 2020)

Course Information

When: Tu/Th 3:00 pm – 4:15 pm.
Where: Felix Haas Hall G066.
Instructor: Jianzhu Ma, majianzhu@purdue.edu.
Office Hour: Wed. 4:30 pm – 5:45 pm.or by appointment (send e-mail) Where: TBD
Online discussion is available at Blackboard (mycourses.purdue.edu).

Course description:

Graphs are a ubiquitous data structure and employed extensively within computer science and related fields. A lot of real world applications can be readily modeled as graphs such as recommender systems, social networks, single molecular and protein interactions networks. Graphs are not only useful as structured knowledge repositories: they also play a very important role in modern machine learning. This course will cover both conventional algorithms and the most recent research on analysis of graphs from a machine learning perspective. The topics that we will cover include: basic graph algorithms such as graph clustering, summarization, anomaly detection and more advanced research topics such as network embedding, graphical neural networks and deep reinforcement learning on graphs.

Classes consist of both instructor and student presentations (see Syllabus). For the first part, the instructor will introduce the basic concepts, algorithms and computational tools. For the second part, students are expected to read and present research papers on most recent deep learning research on graphs and present their own projects.


Students are expected to have the following background:

  • Basic programming skills to write a reasonably non-trivial computer program in Python or C (e.g., CS 38003 or equivalent are recommended).

  • Undergraduate or graduate level machine learning courses (e.g., CS 37300 and CS 578 are sufficient).

  • Students without this background should discuss their preparation with the instructor. The introduction session in the first week of the class will give an overview of the expected background.

Target Students

This course is targeted primarily to senior undergraduate and graduate students in computer science departments. It is also useful to graduate students who are interested in applying machine learning methods to their own research areas including Life Sciences, Health Sciences, Material Sciences and Social Sciences.

Optional textbooks

  • “Networks: An Introduction” by MarkNewman

  • “Network Biology:” section in Topology of molecular interaction networks

  • “Python for Graph and Network Analysis” by Mohammed Zuhair, AI-Taie, and Seifedine Kadry

  • “Complex Network Analysis in Python” by Dmitry Zinoviev

  • “Deep Learning” by Ian Goodfellow, Yoshua Bengio, and Aaron Courville

Presentations (50% of grade)

Please make an appointment with the instructor one week before your presentation. Besides the models and algorithms of the paper, please clearly state what is the role of ‘GRAPHS’ in the work you present. If you want to change your presentation date, please arrange a swap with another student and notify me at least two weeks in advance.

Final projects (50% of grade)

Each student will pick a project related to graphs and machine learning. Here are some possible directions:

  • An interesting mathematical problems around a paper.

  • Adopting a developed computational framework on a new dataset.

  • Following-up experiments of an existing work to understand its important properties.

  • Simple extension of an existing machine learning model, such as unsigned network to signed network, trees to DAGs, shallow neural networks to deep neural networks.

  • Using graphs to model a problem in your own research area.

Please turn in a two-page project proposal before Mar 20th 23:59pm. I will give feedback on the proposal as soon as possible. Please turn in a final report before May 1st 23:59pm.

Syllabus (tentative)

Time Topic Contents Presenter
01/14 Introduction (1) Motivation (2) Syllabus and grading policy (3) Random graphs (4) Paper presentations Jianzhu Ma
01/16 Network Visualization (1) Cytoscape (2) HiView (3) NDEx Jianzhu Ma
01/21 Introduction to Deep Learning (1) Basic concepts, MLP (2) CNN (3) RNN (4) LSTM (5) Resnet (6) GNN Jianzhu Ma
01/23 Network Motifs (1) Network motifs in biological networks (2) G-tries algorithm Jianzhu Ma
01/28 PageRank (1) PageRank algorithm (2) Personalized PageRank and Random Walk algorithm (3) Random Walk in Cancer Jianzhu Ma
01/30 Network Community Detection I (1) Bron-Kerbosch algorithm (2) Kernighan-Lin algorithm (3) Louvain algorithm Jianzhu Ma
02/04 Network Community Detection II (1) Spectual clustering (2) Spectual modularity maximization (3) Hierarchical graph clustering
Optional reading:
Awesome community detection algorithms [github]
Jianzhu Ma
02/06 Network Alignment (1) PathBLAST (2) IsoRank (3) Representation-based network alignments
Optional Reading:
(1) REGAL: Representation Learning-based Graph Alignment [pdf]
(2) Deep Adversarial Network Alignment [pdf]
Jianzhu Ma
02/11 Structural Roles in Network (1) Roles and Communities (2) ReFeX (3) RolX
Optional Reading:
(1) From Community to Role-based Graph Embeddings [pdf]
(2) Role Discovery in Networks [pdf]
(3) Introduction to social network methods Chapter 14 [url]
Jianzhu Ma
02/13 Graph Summarization (1) Graph Dedensification (2) Vocabulary-based Summarization (3) SlashBurn algorithm (4) TimeCrunch algorithm
(1) VOG: Summarizing and Understanding Large Graphs [pdf]
(2) SlashBurn: Graph Compression and Mining beyond Caveman Communities [pdf]
(3) Latent Network Summarization: Bridging Network Embedding and Summarization [pdf]
Jianzhu Ma
02/18 Adversarial Attacks and Defenses (1) White-box attack algorithm (2) Black-box attack algorithm
Optional reading:
Why deep-learning AIs are so easy to fool [nature article]
Jianzhu Ma
02/20 Graphical Model I TBD Jianzhu Ma
02/25 Graphical Model II TBD Jianzhu Ma
02/27 Knowledge Graph Construction TBD Jianzhu Ma
03/03 Large-scale Graphs Reading:
(1) GraphChi: Large-Scale Graph Computation on Just a PC [pdf]
(2) Software demo [download]
03/05 Network Embedding I Reading:
(1) DeepWalk: Online Learning of Social Representations [pdf]
(2) Don't Walk, Skip! Online Learning of Multi-scale Network Embeddings [pdf]
(3) LINE: Large-scale Information Network Embedding [pdf]
Optional reading:
Efficient Estimation of Word Representations in Vector Space [pdf]
03/10 Network Embedding II Reading:
(1) node2vec: Scalable Feature Learning for Networks [pdf]
(2) struc2vec: Learning Node Representations from Structural Identity [pdf]
Optional reading:
Learning Role-based Graph Embeddings [pdf]
03/12 Network Embedding III Reading:
(1) Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks [pdf]
(2) Continuous-Time Dynamic Network Embeddings [pdf]
(3) Recurrent Marked Temporal Point Processes: Embedding Event History to Vector [pdf]
03/24 Learning on Knowledge Graphs Reading:
(1) TransE paper: Translating Embeddings for Modeling Multi-relational Data [pdf]
(2) TransH paper: Knowledge Graph Embedding by Translating on Hyperplanes [pdf]
(3) TransR paper: Learning Entity and Relation Embeddings for Knowledge Graph Completion [pdf]
03/26 Deep Learning on Graphs (1) Graph Laplacian (2) The graph neural network model
Optional reading:
(1) The graph neural network model [pdf]
Jianzhu Ma
03/31 Deep Reinforcement Learning Optional reading:
(1) Yuyi Li: Deep reinforcement learning [pdf]
Jianzhu Ma
04/02 Graph Convolutional Networks I Reading:
(1) Spectral networks and locally connected networks on graphs [pdf]
(2) Deep Convolutional Networks on Graph-Structured Data [pdf]
04/07 Graph Convolutional Networks II Reading:
(1) Semi-Supervised Classification with Graph Convolutional Networks [pdf]
(2) Modeling Relational Data with Graph Convolutional Networks [pdf]
(3) Column Networks for Collective Classification [pdf]
04/09 Generative Models of Graphs Reading:
(1) Learning Deep Generative Models of Graphs [pdf]
(2) GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models [pdf]
(3) Junction tree variational autoencoder for molecular graph generation [pdf]
04/14 Adversarial Attack on Graphs Reading:
(1) Adversarial Attacks on Neural Networks for Graph Data [pdf]
(2) Investigating Robustness and Interpretability of Link Prediction via Adversarial Modifications [pdf]
Optional reading:
(1) Adversarial Attack on Graph Structured Data [pdf]
(2) Adversarial Attacks on Node Embeddings via Graph Poisoning [pdf]
(3) Attacking Graph Convolutional Networks via Rewiring [pdf]
04/16 Higher-order Networks Reading:
(1) Structural deep embedding for hypernetworks [pdf]
(2) Hyper2vec: Biased random walk for hyper-network embedding [pdf]
(3) Hyper-SAGNN: a self-attention based graph neural network for hypergraphs [pdf]
04/21 Deep Reinforcement Learning on Graphs I Reading:
(1) NerveNet: Learning Structured Policy with Graph Neural Networks [pdf]
(2) Playing Text-Adventure Games with Graph-Based Deep Reinforcement Learning [pdf]
04/23 Deep Reinforcement Learning on Graphs II Reading:
(1) Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation [pdf]
(2) MolGAN: An implicit generative model for small molecular graphs [pdf]
(3) Learning Multimodal Graph-to-Graph Translation for Molecular Optimization [pdf]
04/28 Project presentations TBD Students
04/30 Project presentations TBD Students