Course: Computation & Machine Learning on Graphs
Course Information:
When: TTh 15:00-16:15
Where: LWSN B134
Zoom: https://purdue-edu.zoom.us/j/9874334092?pwd=MVRVcHhjQXFac0VYUHcwUzdHK2tFUT09 (We always do in-person unless special things happen)
Instructor: Pan Li
Office Hour: 16:15 - 16:45 after Tuesday's lecture
(There will be no lectures on 10/11, 11/22, 11/24, 11/29 and 12/01. Here, 11/29 and 12/01 are reserved for course project preparation.)
Project teammate search is on Brightspace
Content:
Networks/Graphs are a nature tool for modeling structured data that represents complex social, technological and scientific systems. Coupled with the emergence of large-scale structured data, this course focuses on the computational and algorithmic approaches to analyze graphs and networks. Students are introduced to cutting-edge machine learning techniques apt to reveal insights on the social, technological, and scientific worlds, by means of studying their underlying network structure and interconnections.
Topics include (tentative): Properties of large-scale networks; Random graph models; Spectral graph theory and community detection; Higher-order structures in networks; Network embedding; Graph isomorphism and graph matching; Graph neural networks.
Prerequisites
Students are expected to have the following background:
Knowledge of basic computer science principles, sufficient to write a reasonably non-trivial computer program (CS 15900, CS 18200, CS 25100); Confidence in learning and using the packages in tensorflow, pytorch, networkx.
Familiarity with the basic probability theory (MA 41600);
Familiarity with the basic linear algebra (MA 26200, MA 26500)
Evaluation
Homework: 10% * 2 = 20%
Midterm: 20%
Course project: 60%
Proposal: 20% ; Project milestone: 10%; Final report: 50%; Presentation: 20%
Lectures (tentative, may be updated)
Introduction & Basic Concepts of Graphs
Random Graphs I & Probabilistic Analysis
- Review proof technique
- [LECTURE] Evolution of Random Graphs, Saberi.
- On the Evolution of Random Graphs, Erdős and Rényi, 1960.
- [BOOK] Random graphs, Bollobás, 2001;
Random Graphs II & Real Network Properties
- Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure, Choromański et al, 2013.
- The degree sequence of a scale-free random graph process, Bollobás, 2001
- Kronecker Graphs: An Approach to Modeling Networks, Leskovec, 2010
Community detection I & Spectral Clustering
- [LECTURE] Strong and Weak Ties, Kleinberg
- A Tutorial on Spectral Clustering, Luxburg, 2007
- On Spectral Clustering: Analysis and an algorithm, Ng et al. 2002
Community detection II & Spectral Graph Theory
- [LECTURE] Lectures on Spectral Graph Theory, Chung
- Circular Law
Random Walks & PageRanks
- [LECTURE] Lecture Notes on Random Walks, Kleinberg,
- Random walks on graphs: A survey, Lovász, 1970
- PageRank beyond the web, Gleich, 2015
- Heat kernel based community detection, Kloster and Gleich, 2014
- Optimizing generalized pagerank methods for seed-expansion community detection, Li et al., 2019
Semi-supervised learning & Graph Regularization
- Semi-supervised learning using gaussian fields and harmonic functions, Zhu et al., 2003
- Learning with Local and Global Consistency, Zhou et al., 2004
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters, Leskovec et al., 2009
- Anti-differentiating approximation algorithms: A case study with min-cuts, spectral, and flow, Gleich and Mahoney, 2014
GNN I – Convolution, GCN, ChevNet
- The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, Shuman et al., 2013
- Spectral Networks and Deep Locally Connected Networks on Graphs, Bruna et al., 2013
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering, Defferrard et al., 2016
- Semi-Supervised Classification with Graph Convolutional Networks, Kipf et al., 2017
GNN II - Message Passing, MPNN, GraphSAGE
- Factor graphs and the sum-product algorithm, Kschischang et al., 2001
- Neural message passing for quantum chemistry, Gilmer et al., 2017
- Inductive representation learning on large graphs, Hamilton et al., 2017
- Graph attention networks, Veličković et al., 2018
GNN III - Efficient mini-batch training
- Graph convolutional neural networks for web-scale recommender systems, Ying et al., 2018
- Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks, Chiang et al. 2019
- Graphsaint: Graph sampling based inductive learning method, Zeng et al., 2020
Graph node embedding
- Distributed Representations of Words and Phrases and their Compositionality, Mikolov et al., 2013
- Deepwalk: Online learning of social representations, Perozzi et al., 2014
- Node2vec: Scalable feature learning for networks, Grover and Leskovec, 2016
- On the Dimensionality of Word Embedding, Yin and Shen, 2018
Link prediction and node-pair loss
- The link‐prediction problem for social networks, Liben and Kleinberg, 2007
- Low-rank matrix completion using alternating minimization, Jain et al., 2013
- A short introduction to learning to rank, Li, 2011
- Variational graph auto-encoders, Kipf and Welling, 2017
- Translating Embeddings for Modeling Multi-relational Data, Bordes et al, 2013
Lecture for GNN IV, V, VI, kernels
GNN IV - Invariance
- Deep Sets, Zaheer et al., 2017
- Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs, Murphy, et al., 2019
GNN V - Graph Isomorphism & Representation power
- How Powerful are Graph Neural Networks? Xu et al., 2019
- On the equivalence between graph isomorphism testing and function approximation with GNNs, Chen et al., 2019
- Provably powerful graph networks, Maron et al., 2019
- Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks, Morris et al. 2019
GNN VI - Invited lecture
- Link prediction based on graph neural networks Zhang and Chen, 2019
- Inductive matrix completion based on graph neural networks Zhang and Chen, 2020
- D-vae: A variational autoencoder for directed acyclic graphs, Zhang and Chen, 2019
Graph kernels
- Shortest-path kernels on graphs, Borgwardt & Kriegel, 2005
- Efficient graphlet kernels for large graph comparison, Shervashidze et al., 2009
- Weisfeiler-lehman graph kernels, Shervashidze et al., 2011
Motifs & Graphlets, Node Structural Role
- Network Motifs: Simple Building Blocks of Complex Networks, Miro et al. 2002
- Rolx: structural role extraction & mining in large graphs, Henderson et al. 2012
- struc2vec: Learning Node Representations from Structural Identity, Ribeiro et al. 2017
- Learning structural node embeddings via diffusion wavelets, Donnat et al. 2018
GNN VII & Distance Encoding
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning, Li et al. 2020
- Adaptive Universal Generalized PageRank Graph Neural Network, Chien et al. 2020
- Revisiting graph neural networks and distance encoding from a practical view, Yin et al. 2020
GNN VII & Generative Models
GNN VIII & Attack and Defense
Higher-order graphs/Hypergraphs
Homework
Homework 1: TBD
Homework 2: TBD