[expand]

[expand all]

[collapse all]

Overview

An introduction to Network Science, this is a half lecture half seminar course. Networks model the relationships in complex systems, from hyperlinks between web pages, and co-authorships between research scholars to biological interactions between proteins and genes, and synaptic links between neurons. Network Science is an interdisciplinary research area involving researchers from Physics, Computer Science, Sociology, Math and Statistics, with applications in a wide range of domains including Biology, Medicine, Political Science, Marketing, Ecology, Criminology, etc. In this course, we will cover the basic concepts and techniques used in Network Science, review the state of the art techniques, and discuss the most recent developments.
Prerequisites
This course requires programming skills (Python) and basic knowledge of linear algebra. This is a seminar based course, and a decent Internet connection is also required to be able to engage with the class if connecting remotely. Basic familiarity with Machine Learning is helpful but not necessary.

Textbooks

• [NI] Networks: An Introduction by M.E.J. Newman, available online
• [NS] Network Science by Albert-Barabasi, available online
• [NC] Networks, Crowds and Markets by D. Easley and J. Kleinberg, available online
• [MD] Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman, Jeff Ullman, available online
• note: we cover some chapters from these books, as well as recent surveys, and conference papers

Schedule

Thu., Sep. 2, 2021
Topic: Introduction, slides
Tue., Sep. 7, 2021
Topic: Background, slides,
Reading: NI chapter 6, NS chapter 2
Thu., Sep. 9, 2021
Topic: Patterns, slides
Reading: NI chapter 10, NS chapter 4
Tue., Sep. 14, 2021
Topic: Models, slides
Reading: NI chapters 11-13, NS chapter 3 & 5
Note: Add/Drop deadline, see McGill's Academic calendar
Thu., Sep. 16, 2021
Topic: Measures, slides
Reading: NI chapters 7-9, NS chapter 7
Tue., Sep. 21, 2021
Topic: Modules, slides
Reading: NI chapters 14, NS chapter 9
Thu., Sep. 23, 2021
Topic: Dynamics, slides
Reading: NI chapter 16-17, NS chapter 6, 8 & 10
Tue., Sep. 28, 2021
Topic: Dynamics cont., slides
Reading: NI chapter 16-17, NS chapter 6, 8 & 10
Thu., Sep. 30, 2021
Topic: Prediction, slides

Tue., Oct. 5, 2021
Topic: Graph Embeddings, slides
Thu., Oct. 7, 2021
Topic: Graph Embeddings cont., slides
Tue., Oct. 12, 2021
Note: No Class, Fall Reading Break, see McGill's Academic calendar
Thu., Oct. 14, 2021
Note: No Class, Make up day for Monday Oct. 11, see McGill's Academic calendar
Fri., Oct. 15, 2021
Topic: Anomalies, Guest Lecture by Andy, slides
Note: Makeup Day for Oct. 12, see McGill's Academic calendar
Tue., Oct. 19, 2021
Topic: Project Proposal Presentations
Thu., Oct. 21, 2021
Topic: Social Graphs, Guest Lecture by Kellin Pelrine, slides
Tue., Oct. 26, 2021
Topic: Knowledge Graphs, Guest Lecture by Michael Galkin, slides
Thu., Oct. 28, 2021
Topic: Paper Presentations
- Scale-free networks are rare
- Graphs over time: densification laws, shrinking diameters and possible explanations
- Network Motifs: Simple Building Blocks of Complex Networks
- Motifs in Temporal Networks
Tue., Nov. 2, 2021
Topic: Paper Presentations
- Finding and evaluating community structure in networks
- Fast unfolding of communities in large networks
- Link communities reveal multiscale complexity in networks
- Structure and inference in annotated networks
Thu., Nov. 4, 2021
Topic: Project Progress Presentations
Tue., Nov. 9, 2021
Topic: Paper Presentations
- Fraudar: Bounding graph fraud in the face of camouflage
- Oddball: Spotting anomalies in weighted graphs
- RolX: Structural Role Extraction & Mining in Large Graphs
- GraphScope: Parameter-free Mining of Large Time-evolving Graphs
Thu., Nov. 11, 2021
Topic: Paper Presentations
- Weisfeiler-Lehman Neural Machine for Link Prediction
- Linearized and Single-Pass Belief Propagation
- Fast Incremental and Personalized PageRank
Tue., Nov. 16, 2021
Topic: Paper Presentations
- node2vec: Scalable Feature Learning for Networks
- DeepWalk: Online Learning of Social Representations
- LINE: Large-scale Information Network Embedding
- Network Embedding as Matrix Factorization
Thu., Nov. 18, 2021
Topic: Paper Presentations
- Semi-supervised classification with graph convolutional networks
- Simplifying Graph Convolutional Networks
- Inductive Representation Learning on Large Graphs
- Graph Attention Networks
Tue., Nov. 23, 2021
Topic: Paper Presentations
- Benchmarking Graph Neural Networks
- Link Prediction Based on Graph Neural Networks
- Understanding Negative Sampling in Graph Representation Learning
Thu., Nov. 25, 2021
Topic: Paper Presentations
- Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
- Convolutional Networks on Graphs for Learning Molecular Fingerprints
- Graph Convolutional Networks for Text Classification
- Graph Convolutional Networks for Hyperspectral Image Classification
Tue., Nov. 30, 2021
Topic: Project Presentations
Thu., Dec. 2, 2021
Topic: Project Presentations

Deadlines

• assignment 1 due on Sep. 20th
• assignment 2 due on Oct. 4th
• assignment 3 due on Oct. 18th
• project proposal slides due on Oct. 18th
• project proposal due on Oct. 22th [extended]
• Reviews (first round) due on Oct. 29th [extended]
• project proposal slides due on Nov. 3rd
• project progress report due on Nov. 12th [extended]
• Reviews (second round) due on Nov. 19th [extended]
• project final report slides due on Nov. 29th
• project final report due on Dec. 7th
• Reviews (third round) due on Dec. 14th
• project revised report and rebuttal due on Dec. 20th
• note: dates are tentative, subject to change

Grading

• 10% reviewing assignments
• 10% presentations of assigned papers
• 30% assignments (3x10%)
• 50% project (10% proposal, 15% progress report, 25% final report)
• note: most of the grading is by peer-assessment
Late submission policy
All due dates are 11:59 pm in Montreal.
For assignments, 2^k% of the grade will be deducted per k days of delay.
Project deadlines are firm and no extension is possible [given the peer-review assessment, it is not possible to delay the submissions, but you will have ample time to improve and resubmit, so try to deposit a version by the checkpoints regardless of the stage your report is at]. The final deposit of Dec. 20th has the same late policy as the assignments, it you need extra time at that point.
For presentations, if you are going to miss your assigned class presentation, you need to arrange for another student to switch with you. If you can not find someone to cover for you, you need to contact me so that we can find other arrangements. Other than special situations, you most likely will lose the grade.

Presentation Guidelines

• Try to discuss the main idea and results. You don't need to be comprehensive and cover all the points in the paper. Only what you find interesting to share and the key contributions of the paper.
• You can also safely assume that the students know what we have discussed in the class, so you don't need to go over the basics, only what this paper adds to the class discussions.
• Target a timing of 12 minutes +-2 minutes. (total 15, including time for questions)
• Try to spend equal time (1-2 minutes) on problem def, motivation, main intuition, methodology, experiment setup (data, tasks, evaluation), main finding, and results

Project Guidelines

Template
use Standard ACM Conference Proceedings Template (For LaTeX users: unzip acmart.zip, make, and use sample-sigconf.tex as a template)
Proposal [2 pages]
Introduction and Motivation, Related Work, Problem Definition, Dataset Description
Progress report [4-5 pages]
(extended, improved proposal) + Methodology, Experiment Setup, and Preliminary results
Final report [8 pages + a reference only page]
(extended, improved progress report) + Final Results, Evaluation, Discussion, Conclusions
For examples see the reports from a similar course here
Project presentations
For the presentations, cover the same components in the report with roughly equal emphasis on each section, allocate some time for QA and feedback.
For proposals, this is pitching your project, what is motivating it, what is the graph you are going to look at, and how you are going to analyze it.
For examples of short presentations, see the videos for papers at virtual conferences, for example this year's KDD.

Course Structure

We have a mixed lecture-seminar style course. I will cover the fundamental and classic concepts related early in the course and we move on more seminar series on the most recent works related to the discussed topics later in the course. Early in the course, we will also have 3 sets of hands-on exercise problems (10% each) to implement basic algorithms and get accustomed to working with networked data. Later on, we move to the project, designed as an intro to research in network science.

Resources

• http://snap.stanford.edu/data/
• http://networkrepository.com/
• http://konect.cc/
• https://icon.colorado.edu/#!/

Academic Integrity

Except for the related work section of your project reports, all other parts should be 100% your own deductions, implementation, findings, and results. For the related work section, you may rephrase and summarize the findings of relevant prior work, and cite the corresponding paper. It is not acceptable to copy anything or reuse any wordings, other than technical terms, with appropriate citations. Plagiarism, if detected, not only will result in zero in your grade, but also a report to the university.

FAQ

• Do I have the prerequisites to take the course?
This course requires programming skills (Python) and basic knowledge of linear algebra. Basic familiarity with Machine Learning is helpful but not necessary. This is a research-oriented course and you need to be comfortable reading, presenting, and analyzing research articles. A decent Internet connection is also required to be able to engage with the class if connecting remotely.
• Do I need instructor's permission to take this course?
It is up to your judgment to see if your background is sufficient. If in doubt, please check some slides from the last year and see if you can follow them, see the list of paper presentations and skim through one, etc. There is no need to reach out to me for a permission; please reach out directly to the admins to help you register and cc me, in case you can not register directly.
• How similar is it to the last years?
Very similar, please check the last year's websites to get a glimpse of the slides, expectations, etc. We will have an updated version and not exactly the same materials but very similar overall. We have changed the course number from 596 to 599 to better reflect the workload, which is similar to other 4-credit courses, for example COMP 551.
• What would be the format of the course?
We have a mixed lecture-seminar style course. I will cover the textbook and basic concepts early in the course and we move on to seminar series on the most recent papers in the second half of the course.
• What do I need to do for this course?
Early in the course, we will have 3 sets of programming mini-projects to implement basic algorithms and get accustomed to working with networked data. Then, we move to the project [proposed by you], designed as an intro to research in network science, with multiple checkpoints. In addition, you will present 1 or 2 papers [assigned] in the class, and will provide feedback to your peers on their presentations and project reports. Please check below for more information [please note that everything below is tentative].