Spring 2021 CMSE 890-001 Syllabus

I. General Information

A. Course Information

  • Course title: Spectral Graph Theory and Related Topics
  • CMSE 890-001
  • 3 Credits
  • Lectures: Tuesday and Thursdays, 12:40pm – 2:00pm (Eastern)
  • Course location: Online via Zoom and Slack; recorded lectures will be posted on MSU’s MediaSpace (registered students should have received invites; if you have not, email me)
  • Course website: https://matthewhirn.com/teaching/spring-2021-cmse-890-001/
  • Spring 2021
  • Pre-requisites: Undergraduate level linear algebra, undergraduate level graph theory, programming experience at the level of CMSE 201/202

B. Contact Information

  • Instructor: Matthew Hirn
  • he/him/his
  • Office hours: Wednesday, 4:30pm – 5:30pm, and by appointment.
  • Office hours will be conducted via Zoom and Slack
  • Email: mhirn@msu.edu
  • Website: https://matthewhirn.com/

C. Course Description and Overview

Almost any data set can be modelled as a graph (i.e., a set of vertices or nodes, and edges connecting the vertices). Many modern data sets have natural graph interpretations, such as social networks and molecules in chemistry, to name a few. But even for those data sets that do not a priori lend themselves to a graphical interpretation, one can often define a data graph by measuring similarities between data points. It is thus useful to be able to analyze graphs and to extract information from them, as this information can give insights into complex data when the graph is derived from the data. Spectral graph theory is the study of combinatorial properties of graphs (e.g., the “structure” of graphs) via algebraic properties of associated matrices, and in particular the eigenvectors and eigenvalues of these matrices. This can lead to surprising and beautiful results, but which are also very practical; for example, many powerful clustering algorithms are based on spectral graph theory; spectral graph theory can also help us to approximate large, dense graphs with sparse graphs, which can be very useful in the era of Big Data; and spectral graph theory can help us “draw” a graph in two dimensions, allowing us to visualize data. We will cover such topics in this course, as well as others. As the course progresses, I hope to also cover related topics such as graph signal processing and graph convolutional networks.

Course lectures will be given live, online via Zoom. We will also use Slack to support class communication, such as posing questions during class or office hours and for announcements. Lectures will also be recorded and posted on MSU’s MediaSpace for asynchronous viewing, and lecture notes will be posted on the course website. One’s course grade will be determined by homework assignments, which will be a mix of pen and paper exercises and programming exercises. There will not be a final exam.

D. Required Textbooks and Course Materials

  • Spectral and Algebraic Graph Theory, by Dan Spielman (available here)

E. Supplemental Textbooks and Course Materials

  • Combinatorics and Graph Theory, by Harris, Hirst, and Mossinghoff (listed here, should be available online through the MSU library)

F. In-Class Zoom Etiquette

Lectures will be conducted live online via Zoom. During lecture please adhere to the following rules:

  • Keep yourself muted unless you are asking a question
  • You may keep your video on or turn it off, your choice
  • If you have a question, you have a few options:
    • Unmute yourself and ask your question verbally
    • In the course Slack, type your question in the #in-class-discussion channel, which I will monitor during class
  • I would prefer you not use the Zoom chat for asking questions, as I will not be monitoring that during class

G. Slack

We will use Slack in the course. You should have been invited to the course Slack; if you have not, please email me. The three main channels in the course Slack are:

  • #general: I will use this channel for course wide announcements
  • #in-class-discussion: We will use this channel for typed questions and comments during class
  • #homework: Everyone can use this channel to discuss the homework problems, including posing and answering questions

II. Instructional Objectives

A. Objectives

To understand the theory and applications of spectral graph theory; to be able to derive new theoretical results based upon techniques and results developed in class; to be able to program algorithms based upon spectral graph theory; to give one the foundation required to use this material in one’s research.

B. Assignment Descriptions

Assignments will be given out approximately weekly and will be a mix of pen and paper mathematical exercises meant to test your theoretical understanding of the material, and programming exercises meant to sharpen your skills using spectral graph theory in practice and to illustrate the role of spectral graph theory in applications. Generally, you will have one week to complete each assignment. New assignments will be posted over the weekend and will be due the following Friday by 11:59pm. Assignments should be emailed directly to the instructor at mhirn@msu.edu.

III. Course Schedule

  • January 11-15: Reading and reflection week
  • January 19: First lecture
  • January 29: First homework assignment due (subsequent homework assignments generally due every Friday thereafter)
  • March 2-3: Break days
  • April 21: Last day of classes
  • April 22-23: Study days
  • April 26-30: Finals week

IV. Grading Policy

Grades will be based upon homework assignments. Each problem will be given a point total, indicating the amount of points a correct solution to the problem is worth. One’s grade will be calculated by adding up the total points obtained and dividing by the total possible points across all problems during the semester. We will use the following grading policy:

  • > 90: 4.0
  • 85 – 90: 3:5
  • 80 – 85: 3.0
  • 75 – 80: 2.5
  • 70 – 75: 2.0
  • 65 – 70: 1.5
  • 60 – 65: 1.0
  • < 60: 0.0

Students may work together and discuss homework assignments, but each student must write up or code up their own solutions and turn them in. Students should indicate on their assignments who (if anyone) they worked with.

There will be no midterm/final exam, although the last homework assignment may be due the week of finals (to be determined).

If, due to extenuating circumstances (e.g., illness, religious observance, job interview, etc) you cannot complete a homework assignment by its due date, please contact me in advance of the due date to make alternate arrangements.

V. Course Polices, Syllabus Statements, and Resources for Students

A. Attendance Policy

Registered students are expected to attend the live Zoom lectures, unless circumstances dictate otherwise (e.g., time zone differences, illness, internet outage, etc).

B. Spartan Code of Honor Academic Pledge

As a Spartan, I will strive to uphold values of the highest ethical standard. I will practice honesty in my work, foster honesty in my peers, and take pride in knowing that honor in ownership is worth more than grades. I will carry these values beyond my time as a student at Michigan State University, continuing the endeavor to build personal integrity in all that I do.

C. Relationship Violence and Sexual Misconduct

Michigan State University is committed to fostering a culture of caring and respect that is free of relationship violence and sexual misconduct, and to ensuring that all affected individuals have access to services.  For information on reporting options, confidential advocacy and support resources, university policies and procedures, or how to make a difference on campus, visit the Title IX website at civilrights.msu.edu.

Limits to confidentiality.  Assignments submitted for this class are generally considered confidential pursuant to the University’s student record policies.  However, students should be aware that University employees, including instructors, may not be able to maintain confidentiality when it conflicts with their responsibility to report certain issues to protect the health and safety of MSU community members and others.  As the instructor, I must report the following information to other University offices (including the Department of Police and Public Safety) if you share it with me:

  • Suspected child abuse/neglect, even if this maltreatment happened when you were a child;
  • Allegations of sexual assault, relationship violence, stalking, or sexual harassment; and
  • Credible threats of harm to oneself or to others.

These reports may trigger contact from a campus official who will want to talk with you about the incident that you have shared.  In almost all cases, it will be your decision whether you wish to speak with that individual.  If you would like to talk about these events in a more confidential setting, you are encouraged to make an appointment with the MSU Counseling and Psychiatric Services.

D. RCPD Disability Accommodations Statement

Michigan State University is committed to providing equal opportunity for participation in all programs, services and activities. Requests for accommodations by persons with disabilities may be made by contacting the Resource Center for Persons with Disabilities at 517-884-RCPD or on the web at rcpd.msu.edu. Once your eligibility for an accommodation has been determined, you will be issued a verified individual services accommodation (“VISA”) form. Please present this form to me at the start of the term and/or two weeks prior to the accommodation date (test, project, etc). Requests received after this date will be honored whenever possible.

E. Mental Health

Mental health concerns or stressful events may lead to diminished academic performance or reduce a student’s ability to participate in daily activities. Services are available to assist you with addressing these and other concerns you may be experiencing. You can learn more about the broad range of confidential mental health services available on campus via the Counseling & Psychiatric Services (CAPS) website at www.caps.msu.edu.

F. Tolerance and Civility

MSU strives to build an academic community with living and learning environments that expects tolerance of viewpoints and civility toward others, whether at public forums, athletic events, in residential communities, classrooms or laboratories.

We call upon all who participate in university events to promote tolerance and civil behavior and to hold themselves to high standards that reflect the university’s commitment to respect viewpoints that may be different from their own. Only by respecting individuals with diverse perspectives and ideas can we build an environment of civility that is conducive to advancing knowledge and transforming lives.

G. Commercialization of Lecture Notes

Commercialization of lecture notes and university-provided course materials is not permitted in this course.