Graph data processing course (Fall 2017)

Description

The goal of the graph data processing (GDP) course is to provide a broad introduction to effective graph algorithms in data science and network analysis.

The course features two modules:

The network science module. Here we look as the analysis of networks from the perspective of network science. The lectures will follow chapters 2, 3, 4, 5, and 10 from Barabasi’s Network Science (NS) book. Some questions we will answer are:

  • How are networks formed?
  • Can we model them effectively and what network properties can be predicted accurately?
  • What is the role of hubs in information spreading and why are epidemics so difficult to contain?

The learning on graphs module. A major effort will be given to show that existing data analysis techniques can be extended (and enhanced) on graphs. To do so, we will present strong mathematical tools based on linear and non-linear graph spectral harmonic analysis. Some key points covered are:

  • How can graphs combat the curse of dimensionality?
  • Why is the graph spectrum important?
  • How to solve graph problems related to unsupervised and supervised learning, recommendation, visualization?

The course is given in the University of Rennes in the fall of 2017. It builds on the EPFL course ‘A Network Tour of Data Science‘ given by Prof. Pascal Frossard and Prof. Pierre Vandergheynst in 2017 (and earlier by Xavier Bresson), as well as on Prof. Barabási’s class on Network Science.

  • keywords: learning on graphs, graph-structured data, data science
  • prerequisites: Graph theory, signal processing, convex optimization, basic probability theory
  • instructor:  Dr. Andreas Loukas
  • advisor: Prof. Pierre Vandergheynst

Course schedule & syllabus

  • 05/12/2017: Introduction (read chapter 2 of the NS book)
  • 07/12/2017: Random networks (read chapter 3 of the NS book)
  • 12/12/2017: Scale-free networks (read chapter 4 of the NS book)
  • 14/12/2017: Network formation models (read chapter 5 of the NS book)
  • 19/12/2017: Spreading phenomena and network epidemics (read chapter 10 of the NS book, skip 10.D)
  • — Christmas break —
  • 09/01/2018: Elements of spectral graph theory (chapters 1 (up to and including 1.4) and 2 (up to and including 2.3) from Fan Chung’s lectures.)
  • 11/01/2018: Unsupervised learning with graphs: spectral clustering (read von Luxburg’s tutorial.)
  • 16/01/2018: Unsupervised learning with graphs: dimensionality reduction (papers on ISOMAP, Laplacian Eigenmaps, and LLE )
  • 18/01/2018: Project presentation
  • 23/01/2018: Graph signal processing
  • 25/01/2018: Written exam

The course takes place in room E110, building B02B, Beaulieu, Rennes.

Final grade = 0.5 project grade + 0.5 written exam grade.

Additional material

If you are motivated to learn more, in addition to the project papers, you may consider the following references:

  • The “Spectral Graph Theory” chapter from David Spielman’s book.

(to be updated)

Project

In a nutshell: the objective is to grasp, implement, and present the essence of a state-of-the-art paper in the field.

  • Group of 2 persons. Each team selects one paper (see list below).
  • Understand main concepts and proofs.
  • Evaluate proposed algorithm (or provided prediction) with real data.
  • Give a 10 minute presentation that illustrates your findings (understanding and experiments)

Guidelines

  • An in depth treatment of the core idea is preferred, rather than an exhaustive account – use your judgement (if in doubt, ask)
  • Feel free to use available libraries. If a pre-existing algorithm implementation is used, the grading will focus on other aspects of the effort (e.g., depth of proof comprehension, extensive evaluation with multiple datasets, ideas for extension, presentation of related work).
  • Be critical!

Deliverable

  • Present your findings in a blog style notebook including an easily accessible description of the ideas, proofs, and performed experiments (using Jupyter notebook is suggested).
  • Send the code at my email.

List of Papers

Papers will be assigned in a first come first served basis! Leave a comment below to claim yours.

Related to module 1:

Related to module 2:

Advanced topics (intended for PhD students or the adventurous):

Resources

Advertisements

7 Comments

  1. article : “Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions”

    Group : Clément LEROY, Christophe GENEVEY

  2. Article: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
    Group: Arthur Queffelec and Raphael Truffet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s