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