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) Fast Gradient Sign Method (2) Jacobian-based Saliency Map Attack (3) DeepFool (4) Universal Adversarial Perturbations
Optional reading:
1. The Limitations of Deep Learning in Adversarial Settings [pdf]
2. Why deep-learning AIs are so easy to fool [nature article]
Jianzhu Ma
02/20 Graphical Models I (1) General concepts (2) Exact inference (3) Sum-product algorithm (4) Max-product algorithm (5) Conditional Random Fields
Optional textbooks:
(1) “Probabilistic Graphical Models” by By Daphne Koller and Nir Friedman
(2) “Graphical Models, Exponential Families, and Variational Inference” by Martin J. Wainwright and Michael I. Jordan
(3) Chapter 8 of “Pattern Recognition and Machine Learning” by Christopher M. Bishop
Jianzhu Ma
02/25 Graphical Models II (1) Structure learning (2) Gaussian Graphical Model (3) Pseudo-likelihood approximation (4) Protein contact prediction (5) Deep-Learning-based structure learning
Optional reading:
(1) Sparse Inverse Covariance Estimation with the Graphical Lasso [pdf]
(2) High-Dimensional Graphs and Variable Selection with the Lasso [pdf]
(3) Protein 3D Structure Computed from Evolutionary Sequence Variation [pdf]
(4) AlphaFold: Using AI for scientific discovery [BLOG POST]
(5) Foldit computer game [link]
Jianzhu Ma
02/27 Large-scale Graphs Reading:
(1) Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud [pdf]
(2) GraphLab: A New Framework For Parallel Machine Learning [pdf]
(3) GraphChi: Large-Scale Graph Computation on Just a PC [pdf]
(4) Software demo [download]
Rajat Verma, Jiqian Dong
03/03 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]
Juan Shu, Qian Zhang, Jiajun Liang
03/05 Network Embedding II Reading:
(1) node2vec: Scalable Feature Learning for Networks [pdf]
(2) struc2vec: Learning Node Representations from Structural Identity [pdf]
(3) Inductive Representation Learning on Large Graphs [pdf]
Optional reading:
Learning Role-based Graph Embeddings [pdf]
Vinith Budde, Susheel Suresh
03/10 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]
Optional reading:
Mining Knowledge Graphs from Text [Tutorial]
Xiaonan Jing, Abida Sanjana, Amira Mamoun
03/12 Deep Learning on Graphs (1) General concepts (2) The graph neural network model (3) Popular datasets (4) Gated Graph Sequence Neural Networks
Optional reading:
(1) The graph neural network model [pdf]
(2) Gated Graph Sequence Neural Networks [https:arxiv.orgpdf1511.05493.pdf [pdf]
Jianzhu Ma
03/24 Deep Reinforcement Learning (1) Basic reinforcement learning (2) Applications (3) Q-learning (4) Policy Gradient (5) Actor-Critic Algorithm
Optional reading:
(1) Yuyi Li: Deep reinforcement learning [pdf]
Jianzhu Ma
03/26 Graph Convolutional Networks I Reading:
(1) Spectral networks and locally connected networks on graphs [pdf]
(2) Deep Convolutional Networks on Graph-Structured Data [pdf]
Matthew Muhoberac, Adam Johnston, Connor Beveridge
03/31 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]
Jiang Nan, Pang Qiyuan, Liang Senwei, Xue Jiawei
04/02 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]
Omar Eldaghar, Evzenie Coupkova
04/07 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]
Jungeum Kim, Jiacheng Li
04/09 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]
Xiao Wang, Maria Pacheco, Sean T Flannery
04/14 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]
Zhi Huang, Xiaoyu Xiang
04/16 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]
Kendal Graham Norman, Arvind Sundaram
04/21 Project presentations TBD Students
04/23 Project presentations TBD Students
04/28 Project presentations TBD Students
04/30 Project presentations TBD Students