CPSC 534L: Computing and Learning from Graphs 

                   Laks V.S. Lakshmanan

Classes :

Sept.-Dec. 2025, MW  11:00 am - 12:30 pm, 2175 West Mall, SWNG Room 208.

First lecture : Monday, Sept. 8.

Quick Jumps:

Description
Outline
Marking Scheme
Instructions and Tips on Paper Presentations
Guidelines for Speakers and Discussion Leaders
Evaluation of Presentations and Discussion Leadership
Project Deadlines and Deliverables

Assignments and project talk schedule will be made available from the class piazza page. 

Prerequisites:  No formal prerequisites, but ... a working knowledge of graphs, algorithms, basic theory, basic data mining, machine learning, very basic DB will be assumed.

Description: Networked information structures or graphs are ubiquitous and arise in numerous applications. Examples include homogeneous information networks such as online social networks, citation graphs of publications, collaboration graphs, road networks, and commodity distribution networks, as well as heterogeneous information networks consisting, e.g., of people, resources, and their artifacts, network representations of text corpora, biological networks, and brain networks.  Conducting analysis, mining, learning, and optimization on very large networks is an important part of harnessing Big Data. In an apparently different trend, recommender and collaborative tagging/rating/reviewing systems have gained tremendous popularity. There is growing evidence that recommendations serve as a compelling and complementary alternative to search over large repositories of information. Indeed, an integrated paradigm that combines search with recommendations will significantly boost the quality of resource discovery. Knowledge Graphs (Knowledge Bases) have emerged as a complementary paradigm for information/resource discovery: they represent knowledge glaned from unstructured and structured data in the form of ( subject, predicate, object ) triples, facilitating efficient question answering. An important concern in solving problems of optimization, search, and recommendation, is fairness, which asks whether all groups, including minorities and protected groups, are treated in an equitable way. 

In this course, we will focus on key data mining, learning, and computational problems in large graph structured information systems. Our scope will include the technical aspects of modeling, searching, learning, and optimization motivated by challenging research problems that arise in their context and on designing and analyzing algorithms for solving those problems. We will also discuss modeling and computational challenges brought forth by fairness considerations. 

We will be using Piazza for all online discussion related to the course as well as for managing all submissions, announcements, and class resources. Sign up here . See CPSC534L HOME for a detailed description of the class format and related information.

Click   here   for the Intro slides.  

Outline:

• Intro. to Networks: different perspectives and terminologies, centrality, focus of this course.
• Structural Analysis over Networks:
  • Team Formation.
  • Community detection – General.
  • k-core and k-truss. k-core and k-truss decomposition.
  • k-core/k-truss communities. 
• Infection, Influence & Information Propagation:  single and multiple campaigns; revenue maximization, misinformation (fake news) mitigation, detecting and combating filter bubbles / echo chambers. 
• Recommender Systems: Overview of Content-based vs. Collaborative Filtering; Memory-based vs. Model-based (e.g., Matrix Factorization, Graph Neural Nets); Strategic/Holistic Recommendations. 
• Knowledge Graphs: Construction, Augmentation, Completion, and Attacks. 

   

  Time permitting -- Fair Optimization. 

   

   

Marking Scheme: 

• Homework Assignments: 20%.
• Class Participation: 5%
• Paper Presentation/Discussion and Reports: 30%
• Course Project: 45% (typically teams of 2-3).