[expand]

[expand all]

[collapse all]

Overview

This is on Network Science, Graph Mining and Graph Learning. Networks model relationships in complex systems, from hyperlinks between webpages, 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.

• Seminar Course: Please note that about half of the class is paper discussions and student presentations.
• Prerequisites: This course requires programming skills (Python) and basic knowledge of linear algebra. Basic familiarity with Machine Learning is also needed to grasp some of the topics discussed in the course but it is not required for succeeding in the course.

Textbooks

• [NI] Networks: An Introduction by M.E.J. Newman, available online
• [NS] Network Science by Albert-Barabasi, available online
• [WH] Graph Representation Learning Book by William L. Hamilton, available online
• Note: We cover some chapters from these books, as well as recent surveys, and conference papers.

Schedule

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

Thu., Sep. 29, 2022
Topic: class cancelled,

Tue., Oct. 4, 2022
Topic: Node Embedding, slides
Reading: WH chapter 3
Thu., Oct. 6, 2022
Topic: Graph Neural Networks, slides
Reading: WH chapter 5
Tue., Oct. 11, 2022
Note: No Class, Fall Reading Break, see McGill's Academic calendar
Thu., Oct. 13, 2022
Note: No Class, Make up day for Monday Oct. 11, see McGill's Academic calendar
Fri., Oct. 14, 2022
Topic: Anomalies in Graphs, slides
Tue., Oct. 18, 2022
Topic: Temporal Graphs, slides
Thu., Oct. 20, 2022
Topic: Social Graphs, slides
Tue., Oct. 25, 2022
Topic: Graph Neural Networks cont. slides
Thu., Oct. 27, 2022
Topic: Project Proposal Presentations: 4 minute each
Tue., Nov. 1, 2022
Topic: Advanced Applications of GNNs

Thu., Nov. 3, 2022
Topic: Project Proposal Presentations cont. & Paper presentation
- Link Prediction Based on Graph Neural Networks
Tue., Nov. 8, 2022
Topic: Paper Presentations
- Motifs in Temporal Networks
- Motif Prediction with Graph Neural Networks
- Self-supervised Learning on Graphs: Deep Insights and New Directions
- Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism
Thu., Nov. 10, 2022
Topic: Project Progress Presentations
Timing: 4 minute per member {single person: 4 minutes, 2 person projects: 8 minutes}
Tue., Nov. 15, 2022
Topic: Paper Presentations
- Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum
- Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
- Pre-Training Graph Neural Networks for Generic Structural Feature Extraction

Thu., Nov. 17, 2022
Topic: Paper Presentations
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Network Motifs: Simple Building Blocks of Complex Networks
- CGC: Contrastive Graph Clustering for Community Detection and Tracking

Tue., Nov. 22, 2022
Topic: Paper Presentations
- ROLAND: Graph Learning Framework for Dynamic Graphs
- Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
- Bag of Tricks for Node Classification with Graph Neural Networks
Thu., Nov. 24, 2022
Topic: Paper Presentations
- GraphWorld: Fake Graphs Bring Real Insights for GNNs
- Temporal Walk Centrality: Ranking Nodes in Evolving Networks
- Graph-Enhanced Exploration for Goal Oriented Reinforcement Learning
Tue., Nov. 29, 2022
Topic: Project Presentations [Remote/Zoom Class]
Timing: 8 minute per member {single person: 8 minutes, 2 person projects: 8 minutes}>
Thu., Dec. 1, 2022
Topic: Project Presentations [Remote/Zoom Class]
Timing: 8 minute per member {single person: 8 minutes, 2 person projects: 16 minutes}
• Please note that this schedule is tentative.

Deadlines

• assignment 1 due on Sep. 20th
• assignment 2 due on Oct. 4th
• assignment 3 due on Oct. 21st
• project proposal slides due on Oct. 26th
• Proposal presentations are scheduled for Oct. 27th
• project proposal due on Oct. 28th
• Reviews (first round) are due on Nov. 4th
• project progress slides due on Nov. 9th
• Progress presentations are scheduled for Nov. 10th
• project progress report due on Nov. 11th
• Reviews (second round) are due on Nov. 19th [extended]
• project final report slides due on Nov. 28th
• Project presentations are scheduled for Nov. 29th & Dec. 1st [divided alphabetically]
• project final report due on Dec. 5th
• Reviews (third round) are due on Dec. 14th
• [Optional] project revised report and rebuttal are due on Dec. 20th
• Please note that these dates are tentative and 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 on Dec. 20th is optional, in case you are not happy with your grade/review and want to provide a rebuttal or an improved report. This one has the same late policy as the assignments, if 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 cannot find someone to cover for you, you need to contact me so that we can find other arrangements. Other than special situations, and if we can not fit you in the schedule, you might 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 timing of 12 minutes +-2 minutes. (total of 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 findings, 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.

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 will 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. In the second half of the course, we will move to paper discussions and research projects, designed as an intro to research in network science.

Resources

• Stanford Large Network Dataset Collection [Benchmark Datasets]
• Network Repository [Data + Interactive Visualization and Stats]
• The KONECT Project [Data + Basic Statistics]
• The Colorado Index of Complex Networks (ICON) [Varied Graph Data]
• Open Graph Benchmark [Large Graph Data]
• Networkx [Python Graph Library]
• Deep Graph Library [Benchmark Data + Graph ML Library]
• Pytorch Geometric [Benchmark Data + Graph ML Library]
• Papers with Code on Graph Related Tasks

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 or reuse any images, wordings, etc. other than technical terms, with appropriate citations. Plagiarism, if detected, results in your grade being withheld and the case will be reported 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 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 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 last years?
Very similar, please check 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.
• 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 will move on to the 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 will 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].
• Is remote or hybrid participation available?
McGill's current instruction to instructors is that all courses have to be in person and hybrid should not be an option. However, participation in this course is not graded or part of the assessment (beyond assigned presentations). Lecture recordings will be available, but the quality depends on what the classroom's equipment allows. For the assigned presentations, you can also choose to submit a pre-recorded video and answer the questions remotely. So in case of illness or difficulty, not attending class physically will not directly impact your grade in this course.