Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COMP9312 Data Analytics for Graphs
Course Details & Outcomes
Course Description
Graphs are ubiquitous and are widely used to capture relationships between different entities in real-world applications. However, compared with traditional sequential data (e.g. text and audio), the unstructured property and the sparsity make processing big graphs very challenging. The course will introduce a series of data structures and algorithms for graph processing in terms of database (i.e., big data) and deep learning. Fundamental methods and the state-of-the-art research works will be integrated. The course will serve as a launching pad for those interested in graph analytics, big data processing and graph neural networks.
Data structures and algorithms are the building blocks of many complex systems and software. Certain fundamental graph algorithms such as Dijkstra's algorithm and depth-first search have been covered by many text books and compulsory courses. They may be discussed in terms of pseudocode and time complexity. This course will start from studying how to efficiently implement the fundamental algorithms in big graphs. Then, the course explores more challenging and more complex algorithms step-by-step. When dealing with big graphs, we may consider various scenarios such as external memory solutions, distributed solutions, multi-core solutions, etc.
The course also puts some attention to graph neural networks, which is a hotspot in the area of AI and deep learning. The course will not study theoretical details about machine learning and deep learning but just introduce several representative graph neural networks. The students will play with basic graph learning tasks and understand learning-based techniques for graph problems such as link prediction and node classification.
Course Aims
The course aims to reinforce students' understanding of important graph algorithms and data structures, as well as building their capabilities in designing algorithms for big data processing. In particular, the course will improve students' ability to analyze time complexity, identify potential optimisations, and work on real problems. At the end of this course, you should be in a position where you could write efficient code to solve a complex graph problem. Some of you might even be at the stage where you could do research in the area of big graph processing and graph-based interdisciplinary problems.
Course Learning Outcomes
| Course Learning Outcomes |
|---|
| CLO1 : Evaluate data structures to store and represent graphs |
| CLO2 : Analyze fundamental graph traversal techniques |
| CLO3 : Analyze cohesive subgraph models and their representative computation algorithms |
| CLO4 : Understand basic machine learning methods |
| CLO5 : Apply techniques for graph neural networks |
| Course Learning Outcomes | Assessment Item |
|---|---|
| CLO1 : Evaluate data structures to store and represent graphs |
|
| CLO2 : Analyze fundamental graph traversal techniques |
|
| CLO3 : Analyze cohesive subgraph models and their representative computation algorithms |
|
| CLO4 : Understand basic machine learning methods |
|
| CLO5 : Apply techniques for graph neural networks |
|
Learning and Teaching Technologies
Moodle - Learning Management System
Assessments
Assessment Structure
| Assessment Item | Weight | Relevant Dates |
|---|---|---|
|
Assignment 1
Assessment FormatIndividual
|
15% |
Start DateWeek 2
Due DateWeek 4: 17 June - 23 June
|
|
Project 1
Assessment FormatIndividual
|
25% |
Start DateWeek 5
Due DateWeek 8: 15 July - 21 July
|
|
Assignment 2
Assessment FormatIndividual
|
10% |
Start DateWeek 9
Due DateWeek 10: 29 July - 04 August
|
|
Final Exam
Assessment FormatIndividual
|
50% |
Due DateDuring Exam Period
|
Assessment Details
-
Assignment 1
Assessment Overview
You are expected to prepare a document to answer 6--10 written questions in 2 weeks. The questions include analysing the time complexity of given code, presenting the intermediate process of certain algorithms, and designing solutions for small real problems.
The assessment paper will be provided via Webcms with notification emails. You are expected to submit solutions on Moodle. Marking will be against specific criteria in a marking guide. Results and formal feedback on your assessment task will be provided within two weeks of the relevant submission date through Moodle.
Course Learning Outcomes
- CLO1 : Evaluate data structures to store and represent graphs
- CLO2 : Analyze fundamental graph traversal techniques
-
Project 1
Assessment Overview
You are expected to design solutions for 2 or 3 real graph problems in 4 weeks. For each problem, you need to provide a Python implementation of your solution with an additional documentation to describe your idea and analyse your algorithm (e.g., time complexity and index space complexity).
The assessment paper will be provided via Webcms with notification emails. You are expected to submit solutions on Moodle. Marking will be against specific criteria in a marking guide. Results and formal feedback on your assessment task will be provided within two weeks of the relevant submission date through Moodle.
Course Learning Outcomes
- CLO1 : Evaluate data structures to store and represent graphs
- CLO2 : Analyze fundamental graph traversal techniques
- CLO3 : Analyze cohesive subgraph models and their representative computation algorithms
-
Assignment 2
Assessment Overview
You are expected to prepare a document to answer 5--8 written questions in two weeks. The questions include presenting the intermediate process of certain algorithms and justifying claims about certain graph concepts.
The assessment paper will be provided via Webcms with notification emails. You are expected to submit solutions on Moodle. Marking will be against specific criteria in a marking guide. Results and formal feedback on your assessment task will be provided within two weeks of the relevant submission date through Moodle.
Course Learning Outcomes
- CLO4 : Understand basic machine learning methods
- CLO5 : Apply techniques for graph neural networks
-
Final Exam
Assessment Overview
The final exam contains 8--10 questions. The questions are of various types, such as designing solutions for real problems and analyzing time complexity.
The exam will be held in the UNSW exam period.
Course Learning Outcomes
- CLO1 : Evaluate data structures to store and represent graphs
- CLO2 : Analyze fundamental graph traversal techniques
- CLO3 : Analyze cohesive subgraph models and their representative computation algorithms
- CLO4 : Understand basic machine learning methods
- CLO5 : Apply techniques for graph neural networks
General Assessment Information
Grading Basis
Standard
Course Schedule
| Teaching Week/Module | Activity Type | Content |
|---|---|---|
| Week 1 : 27 May - 2 June | Lecture |
Course Introduction & Graph Storage |
| Week 2 : 3 June - 9 June | Lecture |
Graph Storage & Graph Traversal |
| Week 3 : 10 June - 16 June | Lecture |
Graph Traversal |
| Week 4 : 17 June - 23 June | Lecture |
Graph Traversal & Reachability |
| Week 5 : 24 June - 30 June | Lecture |
Shortest Distance & Path |
| Week 7 : 8 July - 14 July | Lecture |
Subgraph Query Processing |
| Week 8 : 15 July - 21 July | Lecture |
Distributed Graph Systems & Deep Learning Basics |
| Week 9 : 22 July - 28 July | Lecture |
Node Embedding & Graph Neural Networks |
| Week 10 : 29 July - 4 August | Lecture |
Graph Neural Networks & Graph Database |
Attendance Requirements
Please note that lecture recordings are not available for this course. Students are strongly encouraged to attend all classes and contact the Course Authority to make alternative arrangements for classes missed.
Course Resources
Prescribed Resources
Lectures
Reference Python Codes
Tutorials
Private Help Sessions
Recommended Resources
Textbook: Introduction to Algorithms by Cormen Thomas H
Course Evaluation and Development
In past feedback, some students mentioned that the algorithm for reachability query processing is not clear enough. In this term, we have revised the slides by adding more examples.