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 email) 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.
Prerequisites:
Students are expected to have the following background:
Basic programming skills to write a reasonably nontrivial 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, AITaie, 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.
Followingup 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 twopage 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) Gtries 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) BronKerbosch algorithm (2) KernighanLin 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) Representationbased network alignments Optional Reading: (1) REGAL: Representation Learningbased 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 Rolebased 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) Vocabularybased Summarization (3) SlashBurn algorithm (4) TimeCrunch algorithm Reading: (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) Whitebox attack algorithm (2) Blackbox attack algorithm Optional reading: Why deeplearning 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  Largescale Graphs  Reading: (1) GraphChi: LargeScale Graph Computation on Just a PC [pdf] (2) Software demo [download]  Students 
03/05  Network Embedding I  Reading: (1) DeepWalk: Online Learning of Social Representations [pdf] (2) Don't Walk, Skip! Online Learning of Multiscale Network Embeddings [pdf] (3) LINE: Largescale Information Network Embedding [pdf] Optional reading: Efficient Estimation of Word Representations in Vector Space [pdf]  Students 
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 Rolebased Graph Embeddings [pdf]  Students 
03/12  Network Embedding III  Reading: (1) Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks [pdf] (2) ContinuousTime Dynamic Network Embeddings [pdf] (3) Recurrent Marked Temporal Point Processes: Embedding Event History to Vector [pdf]  Students 
03/24  Learning on Knowledge Graphs  Reading: (1) TransE paper: Translating Embeddings for Modeling Multirelational 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]  Students 
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 GraphStructured Data [pdf]  Students 
04/07  Graph Convolutional Networks II  Reading: (1) SemiSupervised Classification with Graph Convolutional Networks [pdf] (2) Modeling Relational Data with Graph Convolutional Networks [pdf] (3) Column Networks for Collective Classification [pdf]  Students 
04/09  Generative Models of Graphs  Reading: (1) Learning Deep Generative Models of Graphs [pdf] (2) GraphRNN: Generating Realistic Graphs with Deep Autoregressive Models [pdf] (3) Junction tree variational autoencoder for molecular graph generation [pdf]  Students 
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]  Students 
04/16  Higherorder Networks  Reading: (1) Structural deep embedding for hypernetworks [pdf] (2) Hyper2vec: Biased random walk for hypernetwork embedding [pdf] (3) HyperSAGNN: a selfattention based graph neural network for hypergraphs [pdf]  Students 
04/21  Deep Reinforcement Learning on Graphs I  Reading: (1) NerveNet: Learning Structured Policy with Graph Neural Networks [pdf] (2) Playing TextAdventure Games with GraphBased Deep Reinforcement Learning [pdf]  Students 
04/23  Deep Reinforcement Learning on Graphs II  Reading: (1) Graph Convolutional Policy Network for GoalDirected Molecular Graph Generation [pdf] (2) MolGAN: An implicit generative model for small molecular graphs [pdf] (3) Learning Multimodal GraphtoGraph Translation for Molecular Optimization [pdf]  Students 
04/28  Project presentations  TBD  Students 
04/30  Project presentations  TBD  Students 

