# Intelligent Tutoring System: Experience of Linking Software Engineering and
Programming Teaching

Zhiyu Fan<EMAIL_ADDRESS>National University of SingaporeSingapore
,  Yannic Noller<EMAIL_ADDRESS>Singapore University of Technology and
DesignSingapore ,  Ashish Dandekar<EMAIL_ADDRESS>National
University of SingaporeSingapore and  Abhik Roychoudhury
<EMAIL_ADDRESS>National University of SingaporeSingapore

###### Abstract.

The increasing number of computer science students pushes lecturers and tutors
of first-year programming courses to their limits. Existing systems that
handle automated grading primarily focus on the automation of test case
executions in the context of programming assignments. However, they cannot
provide customized feedback about the students’ errors, and hence, cannot
replace the help of tutors. Based on the research advances in recent years
specifically in automated program repair and synthesis, we have built an
intelligent tutoring system that has the capability of providing automated
feedback. Furthermore, we designed a Software Engineering course that guides
third-year undergraduate students in incrementally developing such a system
over several years. Each year, students will make contributions that improve
the current implementation, while at the same time, we can deploy the current
system for usage by first year students for learning programming. This paper
describes our teaching concept, the intelligent tutoring system architecture,
and our experience with the stakeholders. This software engineering project
for the students has the key advantage that the users of the system are
available in-house (i.e., students, tutors, and lecturers from the first-year
programming courses). This helps to organize requirements engineering sessions
and builds awareness about their contribution to a ”to–be–deployed” software
project. In this multi-year teaching effort, we have incrementally built a
tutoring system for first-year programming courses.

software engineering, education, automated program repair, intelligent tutor

††ccs: Software and its engineering††ccs: Applied computing Education

##  1\. Introduction

In Computer Science (CS) education, we face the issue of the increasing number
of enrolments in the past years (Singer, 2019). Therefore, it becomes
increasingly difficult to keep up with high-quality and individual learning
support, particularly for novice students (Zhang et al., 2022; Mirhosseini et
al., 2023). Mirhosseini et al. (Mirhosseini et al., 2023) recently conducted
an interview study with CS instructors to identify their biggest pain points.
Amongst others, they identified that CS instructors struggle with no or
limited Teaching Assistant (TA) support and the generally time-consuming task
of providing student feedback and assignment grading. Therefore, CS
instructors would greatly benefit from automating tutoring activities to
support TAs in their responsibilities. Another typical problem in CS education
is the provision of Software Engineering (SE) projects. Software engineering
is typically a compulsory course in the university’s curriculum for computer
science students, and it is often followed or accompanied by development
projects, in which students can collect hands-on experience in software
development in a team going beyond a programming exercise. Such projects come
with inherent difficulties like acquiring industry partners and the dilemma
that such software projects are often under- or over-specified. Additionally,
such projects are often one-time efforts within one team or one course, and
students cannot experience the evolution of a software system.

In this work, we report our experience in tackling these two problems in CS
education by building an Intelligent Tutoring System (ITS) with and for
students. As a multi-year research and teaching effort, we combine third-year
SE teaching and first-year programming teaching via a long-term, practical,
self-sustained software system. We use the latest research results in
automated program repair (APR), e.g., techniques like Clara (Gulwani et al.,
2018), SarfGen (Wang et al., 2018), and Refactory (Hu et al., 2019), to build
such intelligent tutoring system that can be deployed in first-year
programming courses. Figure 1 shows the general idea of such a system.

Figure 1.  General idea of an intelligent tutoring system that supports
students and tutors in CS-1 programming courses.

It can provide automated and individual feedback for student code submissions
and grading support for tutors and lecturers. Further, we involve third-year
undergraduate students in the incremental development of such a system. We
offer various SE projects for the students in our advanced SE course. In this
course, the students can choose from a wide range of projects, which
essentially represent the development or extension of ITS components. Based on
the nature of the overall project, we can conduct requirements engineering
activities (e.g., surveys, interviews, and user studies) in-house because the
various stakeholders are available in the university context. Each student
project has the chance to contribute to the overall long-running SE project
and eventually impact the learning experience of hundreds of other CS
students. In our experience, this creates additional motivation because the
effort is not lost, and they can relate to the users because they (at some
point in their studies) also faced the challenges of learning programming.
Based on our experience with around 125 undergraduate students who helped
develop the system throughout two years of teaching, the students enjoyed the
course project. In particular, they liked the potential reuse of their
implementation in the real deployment of the ITS. They also enjoyed the fact
that there is already a system, which they have to extend (i.e., also the
added complexity in understanding the already existing design and codebase).
Our user studies revealed that in the current version of the ITS, the students
and tutors benefit the most from the error localization capabilities, which
pinpoint the student’s error to the specific lines in their submission. It
helps the students find their errors and allows the tutors quickly understand
the problems in the student submissions. In particular, for the students, the
auto-generated feedback can help them to understand their problems and correct
their mistakes. The students reported that they see the potential of ITS to
provide automated, and hence, always available feedback. We also received new
requirements that can further help to improve the current implementation,
e.g., more error explanations and integration into other learning platforms,
as well as feedback about non-functional properties and advanced visualization
and interaction features. Overall, more than 78% of our participants would
like the ITS to be deployed in their next programming course.

Throughout the two years we have taught this SE course, we learned that
students prefer certain types of projects (e.g., in our case, they preferred
front-end projects and avoided the projects about core APR capabilities),
which influenced how we organized the project selection. Further, we noticed
that students benefit from the additional help from graduate-level mentors.
Our course not only impacts the first-year programming courses in our
university but also has the potential to impact other universities which adopt
a similar teaching concept linking the teaching of software engineering with
the teaching of programming. In the future, we plan to conduct more user
studies to explore learning success across university boundaries.

#### Core Contributions

In summary, we make the following core contributions:

  * •

We present our teaching concept that involves the incremental development of
an Intelligent Tutoring System (ITS) spanning multiple semesters.

  * •

We share our experience with the user (i.e., student) engagements, where more
than 78% of them want to see the ITS deployed in their next programming
course.

  * •

We suggest a pathway for linking the teaching of software engineering project
with the teaching of programming.

#### Paper Structure

We first present the research background and discuss the related work in
Section 2, then we describe our teaching concept and detailed course
arrangement in Section 3. Section 4 explains the overall architecture of our
ITS, and Section 5 highlights the system’s key student-facing functionalities:
feedback and grading. Section 6 reports the results of our user study, and
Section 7 discusses our insights from the ongoing deployments in a CS-1
course. Finally, we reflect on the challenges in organizing the course in
Section 8 and share our future vision in Section 9.

##  2\. Related Work

#### Capstone Software Engineering Projects

Project-based software engineering courses are essential for students to get
training for professional software development skills like architecture
design, team management, software maintenance, etc. Students are often
required to work as a team to develop software either from industrial partners
or simulated real-world topics via semester-long projects (Johns-Boast and
Flint, 2013; Spichkova, 2019; Bruegge et al., 2015; Tenhunen et al., 2023;
Delgado et al., 2017). However, there exist certain barriers and challenges to
this teaching setting. For example, continuously collecting project topics
from industry companies and establishing an efficient communication channel
between stakeholders (students and company clients) are challenging tasks for
the instructor. More importantly, the students work on different project
topics each year, which means they usually do not have a general picture of
the entire system, therefore they cannot experience the evolution of a
software system.

In this work, our focus is presenting the idea of having an in-house, long-
running, sustainable software engineering project in the university context.
This kind of long-running SE project shares characteristics with other
community-driven course concepts (Anderson et al., 2023). Our proposed
teaching concept is however novel in the sense that it links the teaching of
software engineering courses and the teaching of introductory programming
courses. This is done by developing an intelligent tutoring system. Students
not only get training for software development but also gain exposure to the
latest research in the software engineering community.

#### Automated Program Repair for Feedback Generation

Automated program repair (APR) (Nguyen et al., 2013; Le Goues et al., 2011;
Mechtaev et al., 2016) is a technique that is designed to automatically
provide program patches to reduce developers’ manual debugging burden. Prior
research (Yi et al., 2017) has shown the possibility of applying APR
techniques in introductory programming courses. Over the last decade, a number
of CS-1 specific APR tools have been introduced to rectify programming
mistakes and provide feedback for novice programmers. AutoGrader (Singh et
al., 2013) takes in a reference solution and manually-curated program error
model to automatically synthesize patches for common mistakes in students’
incorrect programs. Clara and SarfGen (Gulwani et al., 2018; Wang et al.,
2018) assume the availability of multiple reference solutions and repair
students’ incorrect programs at the basic-block level by editing students’
faulty statements with expression ingredients from reference solutions.
Refactory (Hu et al., 2019) addresses the assumption of having multiple
reference solutions by using refactoring rules to automatically produce more
semantically equivalent but syntactically different reference solutions based
on a single reference solution. Verifix (Ahmed et al., 2022) aims to improve
the trustworthiness of generated patches and performs program equivalence
verification to guarantee the correctness of the generated feedback. There are
also works specifically designed for repairing syntax issues (such as
compilation errors) in students’ submissions (Ahmed et al., 2018; Yasunaga and
Liang, 2021), whereas our ITS primarily focuses on the repair of programmign
errors made by the student.

Despite these tools having shown promising results in CS-1 teaching (Yi et
al., 2017; Kurniawan et al., 2023), their research outcomes have different
focus that cannot be best utilized in a single system. Our Intelligent
Tutoring System represents an evolving platform that can integrate the latest
research results in APR for education.

Figure 2. Concept of a long-running software engineering project that is
incrementally improved by short-running projects inside a teaching
environment.

##  3\. Experience in Software Engineering Teaching

In this section, we first discuss our teaching concept at a high level
(Section 3.1), then share our course arrangement in detail for others to adapt
(Section 3.2).

###  3.1. Teaching Concept

Our teaching concept combines lectures about the foundations of software
engineering with hands-on project experience. The goal is to deepen the
understanding of software engineering and practice the already learned
principles in a realistic environment. In the lectures, we teach foundations
with a focus on requirements, modeling notations, software architecture and
design, software testing, debugging, and foundations of static program
analysis. We also teach non-functional properties like performance and
security aspects of software (e.g., software timing analysis and taint
analysis). The project focuses on contributing to a more significant, long-
running software engineering project to allow the students to go beyond
programming-in-the-small. The project aims to develop a functional and ready-
to-use intelligent tutoring system incrementally. Developing such a system in
the context of a SE course is particularly interesting because (1) the third-
year students who develop the system can relate to the users (first-year
students) since they once had to learn programming, and (2) all project
stakeholders are available in the university. The presence of stakeholders
allows embedding requirements elicitation as part of the SE project class.

Figure 2 illustrates the project evolution over multiple years. Before we
started any development, we collected initial requirements (step 1) from the
lecturers of some first-year programming courses. In step 2, we developed a
baseline codebase, which included designing the artifact and the desired
workflow. This first version already defined interfaces between components and
provided common data structures. The baseline also included a prototypical
implementation for most of the initially planned components to test their
feasibility. Having the baseline provides the students with additional
requirements like the existing architecture, which should not be changed. On
the other hand, it also provides them with existing functionalities similar to
a real-world long-running SE project.

For our third-year course (step 3), we design multiple short-running SE
projects based on the feedback from first year course instructor in the
requirement elicitation session of our course, and these projects essentially
representing the implementation variants of existing or new components. For
example, in the first year, we mainly had projects to build program analysis
capabilities. We further designed projects to extend core features like
Automated Feedback and Automated Grading in the second year.

After our course, we evaluate all projects and integrate the best
contributions into our baseline implementation (step 5). Therefore, over the
years, the baseline will grow and improve. At the same time, we also deploy
the increments of the system in its real-world context, i.e., with users from
first-year programming courses, and collect additional feedback and
requirements from students and tutors (step 4). To keep the implementation
standards high and to ensure that our architecture and design can cope with
the increasing codebase and the possibly new and changing requirements, we
constantly maintain and improve the implementation (step 6).

Overall, our SE project course is structured so that the teaching of SE
projects is accomplished over multiple years via a real-life SE project. This
project builds an intelligent tutoring system for teaching programming. In the
first offering of the course, many system components are not entirely built
yet, but these components get built and improved by offering the course over
multiple years.

Table 1. Course assignment overview that accompanies the major project milestones. ID | Topic | Details
---|---|---
1 | Requirements Analysis & Elicitation |  10cmPreparations and questions for the interview session with the customer.
2 | Requirements Modeling |  10cmRequirement modeling with UML Use Case and Activity diagrams.
3 | Architectural Drivers and Architecture Variants |  11cmDiscussion of architecture variants and the requirements that influence architectural design.
4 | Strategy and Project Planning |  10cmProject-specific planning including a Gantt-Chart and a resource plan.
5 | Detailed Design |  10cmStructural and behavioral design of the students’ implementation with UML models
6 | Intermediate Deliverable |  11cmTowards the middle of the course, we ask the students to submit a minimal project implementation and a report with their project plans and various models.
7 | Validation (i.e., Unit Testing) |  10cmTest case design and test report.
8 | Presentation & Final Artifact |  10cmAt the end of the course, all teams need to present their project and submit their code.
9 | Final Report |  11cmAfter the presentation, the students additionally need to submit a final report, including a retrospective of their project and design decisions.

###  3.2. Course Curriculum

The course curriculum focuses on the main activities in SE. Furthermore, we
introduce selected relevant SE topics for our project, e.g., automated program
repair, static analysis, and fault localization. Each lecture is separated
into two parts: (a) the teaching of foundations in the aforementioned areas,
and (b) the teaching of project-specific knowledge and corresponding
applications.

#### Requirements Analysis and Modeling

The course starts with a focus on requirements engineering, their elicitation,
and modeling. Therefore, we invite stakeholders like lecturers and teaching
assistants from the first-year programming courses to an interview session
with the third-year students. This interview session is prepared with
corresponding assignments about question design and followed up with
requirements modeling exercises using UML Use Cases. We also teach other means
for requirements modeling, e.g., with finite state machines and sequence
diagrams.

#### Software Architecture and Design

Afterwards, we introduce general principles for software architecture design
and modeling. The project-specific part of the lecture introduces the existing
architecture and its components, including the available interfaces, which
need to be used by the students in their own implementations. We further
discuss architecture variants of the existing architecture to discuss pro and
contra of the made design decisions.

Our baseline Java implementation already provides the students with elementary
classes and functionalities, which they can and need to reuse. To illustrate
the fine-grained design, we first introduce relevant design principles and
patterns that occur in our implementation. We do not give a comprehensive
introduction to design patterns because there is another dedicated software
design course in our institution. Instead, we only introduce the most relevant
design aspects to enable the students to work on the projects.

#### Project Planning and Implementation

As part of the assignments, the students have to submit a project plan.
Therefore, we also introduce the basics of project planning, work package
design, and milestone and resource planning, including necessary models like
Gantt-Charts. The coding itself is a major part of the project and is mostly
supported by the mentors in project-specific meetings. The lecture introduces
general principles like Clean Code and testing and debugging techniques meant
to help the students in their concrete implementation efforts.

#### Testing, Debugging, and Integration

As automated testing and debugging is a major part of an intelligent tutoring
system, we also introduce several validation concepts and debugging
techniques. In particular, we teach foundations in test-suite estimation,
functional testing, whitebox testing, structural testing, dataflow testing,
and mutation testing. To this end, we also introduce the basics of static
analysis like control-flow graphs (CFGs) and Define-Use Analysis (DUA).
Furthermore, we discuss the basics of debugging with the TRAFFIC principle and
delta debugging and dive deeper into the basics of static and dynamic slicing
and statistical fault localization. Towards the end of the curriculum, we also
discuss integration testing strategies and the related challenges.

#### Project-Specific Topics

In addition to the foundations in general software engineering, we teach the
background in automated program repair and provide an overview of existing
solutions for ITS components. Depending on the advertised projects, we also
discuss more specialized topics like taint analysis and Worst-Case Execution
Time (WCET) analysis to ensure the students have the relevant background and
material to work on their projects.

#### Labs and Assignments

Each week in our curriculum is accompanied by a lecture and a lab session. The
labs are used to meet in smaller groups of students and discuss their
assignments. The assignments track the major milestones in the students’
projects (see Table 1).

#### Team Management

We ask the students to form groups of 3-4 people to work on the project. We
allow them to search for their team members instead of a random assignment by
the teaching team. We prepare an ungraded Assignment 0 for the project
selection, which provides an overview and additional references for all
available projects for the specific year. Each team can bid for three
projects, while the teaching team allocates the final project. We encourage
each team to join the same lab sessions to maximize the possibility of team
interaction. Additionally, each team meets weekly with a graduate-level mentor
focusing on the team’s planning, design, and implementation progress. The
mentors also have access to the team’s code repository to provide feedback.

The course aims for enabling the students to advance their skills in software
development and grasp a deeper understanding of fundamental SE concepts. All
student projects eventually contribute to an intelligent tutoring system,
whose details are discussed in the following section.

Figure 3. Illustrates the general workflow of the Intelligent Tutoring System.

##  4\. Intelligent Tutoring System (ITS)

The architecture and design of our intelligent tutoring system (ITS) are
inspired by existing research (Gulwani et al., 2018; Wang et al., 2018; Ahmed
et al., 2022; Hu et al., 2019) in this area. Figure 3 shows the overview of
components and the intended workflow. All components provide interfaces so
that components can be implemented independently. In the following, we discuss
each component’s purpose and illustrate the workflow. For our example, we use
the program in Figure 4(a) as the reference implementation that the lecturer
would provide. It is the solution for a simple assignment that requires
reading a number $n$ from the console and compute
$\sum_{i=1}^{n}\sum_{j=1}^{i}j$, which then should be printed again on the
console. Figure 4(b) shows an incorrect student submission with an error in
the loop condition in line 7. In addition to the programs, we also assume to
have some tests, which can be used to assess the correctness of the student
submission. In this example, we only have some concrete inputs of interest
$n\in\\{2,4,10,3,1,20\\}$, and the correct behavior can be extracted from the
reference implementation.

⬇

1 #include <stdio.h>

2 int main()

3 {

4 int i,j,n,sum=0;

5 scanf("%d",&n);

6 for(i=1;i<=n;i++)

7 {

8 for(j=1;j<=i;j++)

9 {

10 sum+=j;

11 }

12 }

13 printf("%d",sum);

14 return 0;

15 }

(a) Reference Program

⬇

1 #include <stdio.h>

2 int main(){

3 int i,j,N,sum;

4 sum=0;

5 scanf("%d",&N);

6 for(i=1;i<=N;i++){

7 for(j=1;j<=N;j++){

8 sum=sum+j;

9 }

10 }

11 printf("%d",sum);

12 return 0;

13 }

(b) Incorrect Student Submission

(c) Simplified illustration of the CFG-based internal program representation
of the code in Figure 4(a).

Figure 4. Listings and CFG used in the example to illustrate the workflow in
Figure 3.

#### 1) Parser

The reference program and the submitted (incorrect) program are given to the
Parser component. For each program, it generates the corresponding internal
program representation. This representation is based on the Control-Flow Graph
(CFG). Finally, the results are passed to the Syntactic Alignment component.
The objective of the Parser components is to enable the other internal parts
of the Intelligent Tutoring System to work independently from a specific
programming language. The simplified illustration of the internal CFG-based
program representation for the reference program is shown in Figure 4(c). Note
that the (incorrect) student submission has the same structure, i.e., the same
number of basic blocks, although a different content in the blocks.

#### 2) Syntactic Alignment

The Syntactic Alignment component takes the two Program objects and identifies
the matching basic blocks. Therefore, it aligns the two programs with regard
to their CFG representation. Moreover, it maps the existing variables for each
function inside the programs. The results can later be used to detect (error)
locations where the reference and submitted programs behave differently.
Additionally, this information helps to attempt the repair/fix of the
submitted program by reusing information from the reference program. Our
current baseline implementation follows the approach by (Gulwani et al.,
2018), which attempts to match the two programs based on their control flow
and their variables. In our example, the structure is the same, so the mapping
is straightforward. Internally, we keep a mapping for each function and its
basic blocks:

$main:\\{1=1,2=2,3=3,4=4,5=5,6=6,7=7\\}$

To build the variable mapping, we use a Define-Use Analysis (DUA) (also see
(Hu et al., 2019)). The resulting variable matching is

$main=\\{i=i,sum=sum,j=j,n=N\\}$

#### 3) Error Localizer

The Error Localizer component identifies locations that show erroneous
behavior in the submitted program. This enables others components to formulate
a repair/fix. The Error Localizer component has access to the Interpreter
component to execute test cases while observing the values of variables at
specific locations. It can use the Interpreter to detect semantic differences
between the reference and submitted programs. For our example, we use a trace-
based error localizer. It uses the Interpreter to execute the inputs for both
programs and compares the resulting execution traces. For the input $n=2$, our
Error Localizer identifies a value mismatch at location 4. It also detects
which variable or expression holds the first observation of this mismatch: the
loop condition in line 7 in the student’s submission, j<=N.

#### 4) Interpreter

The Interpreter component allows the execution of a program in its CFG-based
representation without any compilation or execution on the actual system. It
generates an execution trace with the sequence of executed basic blocks and a
memory object, which holds the variable values at specific locations.

#### 5) Repair

The Repair component attempts to fix the submitted program. For example, it
can use the mapping to the reference program (see step 2) and the identified
error locations (see step 3) to generate so-called local repairs that modify
single statements in the submitted program. Multiple local repairs can be
combined to represent more complex changes. The repair process results in a
list of plausible repair candidates. It can also use the Interpreter component
to extract more information from the (correct) reference program. For our
example, we use an ILP-based repair implementation similar to (Gulwani et al.,
2018). It uses the reference implementation information to search for a
minimal change to transform the student’s program into the reference program.
The local repair with the smallest repair cost is to change the condition
location 6 from j <= N to j <= i. Additionally, we already integrated other
repair strategies like Refactory (Hu et al., 2019) and particularly allow the
use of multiple reference implementations to maximize the chances of
structural matching between the student’s submission and the reference
solution.

#### 6) Feedback

With all the collected intermediate information from previous components, the
Feedback component generates a natural language explanation to guide students
to correct their mistakes.

#### 7) Auto-Grading

The Auto-Grading component integrates recent research on the concept graph of
CS-1 programming assignment (Fan et al., 2023). More details appear in the
following section.

Note that all these components can and are developed in various variants. For
example, our current baseline implementation includes a C and Python Parser to
support multiple languages. The Error Localizer can compare execution traces
for concrete inputs or perform statistical fault localization. The Repair
component can follow various strategies, e.g., an optimization-based repair
approach like in (Gulwani et al., 2018) or a synthesis-based approach like in
(Hu et al., 2019). Therefore, the platform we are developing is not only
interesting for educational purposes but can also integrate new research
advances.

##  5\. Student Feedback and Grading

In this section, we elaborate the key student-facing functionalities of the
intelligent tutoring system:

  * •

providing feedback to struggling student attempts, and

  * •

auto-grading of student assignments.

#### Student Feedback

The ITS provides feedback to student programming attempts. The feedback is a
repair of the student program, vis-a-vis the reference solution, based on the
patch locations and candidates produced by repair engines (e.g., Clara and
Refactory (Gulwani et al., 2018; Hu et al., 2019)) in our Repair components.
We initially started with a pattern-based approach, where the Feedback
component translates the error type and error location using pre-defined
feedback templates. For the example in Figure 4(b), the ITS produces the
following feedback to give hints on the incorrectly used loop condition. We
intentionally hid the fix patch because we aimed to help the students think
instead of explicitly showing the answer.

* At line 7: Error with loop condition. Wrong variables in the condition. Variables [i, j] should be checked in the loop condition.

However, the pattern-based approach may not be comprehensive enough and is
limited when handling multiple and sophisticated errors. Therefore, we further
incorporate the ability of LLM to curate organized human-readable feedback
because of their promising performance in text generation (Chen et al., 2021)
in the second year of our course. We provide the error locations and error
types generated by Repair component as prompt ingredients and follow a few-
shot prompting strategy (Brown et al., 2020) to tune the LLM (e.g., ChatGPT)
to produce feedback as a human tutor.

#### Automated Grading

Test-suite based automated grading suffers from the problem that a small
mistake by the student can cause many test cases to fail. To provide better
support for tutors, we integrate an auto-grading capability, which aims to
test the conceptual understanding of the student and awards grades accordingly
(Fan et al., 2023). This is achieved by constructing a concept graph from the
student’s attempt and comparing it with the concept graph of the instructor’s
reference solution. The aim is to automatically determine which of the
ingredient concepts being tested by the programming assignment are correctly
understood by the student. Given the instructor-provided reference solutions
and students’ incorrect solutions, we apply the abstraction rules to convert
students’ concrete implementation to conceptual understandings and compare
them against the conceptual requirements in reference solutions. Based on the
result, the Auto-Grading component generates a grading report for the tutor.
It assesses the student’s submission by their missing or improperly used
programming concepts to address the over-penalty issue (Fan et al., 2023) in
the conventional test-based assessment.

Figure 5. Participants’ Self-Assessed Experience

##  6\. Experience in CS-1 Teaching

After a year of course iteration and system development, we successfully
developed an end-to-end ITS that automatically generates customized feedback
for students and tutors. In this section, we share our initial experiences of
using the ITS from the viewpoint of our customers – students and tutors based
on two institutional review board (IRB)-approved studies.

###  6.1. Study Methodology

#### Participants Background

In total, we recruited 15 students and 8 tutors from the CS-1 programming
courses at our institution. The students are all from the same programming
course. We scheduled the study in the middle of this course so that the
students already obtained fundamental programming knowledge but are still in
the progress of learning programming. Therefore, we have an interesting
scenario where the ITS is deployed to students with little programming
experience (see Figure 5). Our tutor participants are senior undergraduates
from CS-1 programming courses. Based on their self-assessment, we had
experienced tutors who, have prior experience of tutor duty at least once. All
participants were compensated with $10.

#### Study with Students

The student study focused on understanding how the ITS can help students.
Therefore, we conducted a controlled experiment and, based on their experience
(see Figure 5), we equally divided the student participants into two groups, A
and B. The participants are instructed to solve programming tasks using an
institution-internal submission system that allows them to run provided test
cases. For each task, they had 20 minutes and were allowed to make any number
of submission attempts. Additionally, group A had access to the ITS, i.e.,
these students were able to receive additional feedback. Before they started
with the programming tasks, we briefly introduced the ITS to ensure they could
use it. Overall, the study was structured in three parts: (1) a background
survey, (2) the programming tasks, and (3) a feedback survey. Through parts 1
and 3, we collected additional expectations and feedback for the ITS. So that
the students from group B also can provide feedback on the idea of an ITS, we
provided group B with a brief introduction to ITS after they solved their
programming tasks. After the study, we clarified any related questions for
both groups.

#### Study with Tutors

The tutor study focused on understanding the needs of tutors and their
feedback on the current deployment of the ITS. The study was structured in
three parts: (1) a background survey, (2) the grading of programming tasks
with the help of the ITS, and (3) a structured interview about their
experience. After part 1, we also provided tutors with a brief introduction to
the ITS.

(a) General programming difficulties for students.

(b) Student’s difficulties in improving their incorrect submission.

(c) Features that an ITS should provide to aid tutors.

(d) Usefulness of features that tutors expect.

Figure 6. General Challenges for Students and Tutor’s Expectations.

#### Programming Tasks

We have chosen four entry-level programming tasks covering various programming
topics. Table 2 shows the details of each task and their respective topics. We
selected these programming tasks for two reasons: (1) they were taken from
past mid-term exams of the CS-1 course, which accurately represent the
practical challenges students may face, and (2) they followed the weekly
course curriculum, which teaches new programming concepts to students.

Table 2. Subjects of programming tasks in our surveys Tasks | Description | Topic
---|---|---
Remove Extras | Remove duplicate elements from tuple |  2cmFor loop, Tuple manipulation
Reverse String I | Iteratively reverse a string |  2cmFor loop, String manipulation
Reverse String II | Recursively reverse a string |  2cmRecursion
Reverse Numbers | Iteratively reverse an integer |  2cmWhile loop

###  6.2. Result Analysis

We recorded the submitted solutions and their timestamps for each programming
task of non-duplicate students’ attempts. Students were considered to have
_solved_ a task if their attempts passed all test cases. In total, we received
128 attempts for the four programming tasks; 65 by Group A and 63 by Group B.
For all open-ended questions, we conducted a qualitative content analysis
coding (Schreier, 2012) that summarizes the themes and opinions. First, one
author performed the analysis and coding steps; afterwards, another author
reviewed them. Finally, after a discussion, we completed the analysis.

(a) Students’ feedback of ITS

(b) Tutors’ feedback of how ITS helped them.

(c) Tutors’ overall satisfaction with ITS.

(d) Tutor’s desire for feedback on other non-functional properties.

Figure 7. Results from Study Surveys and Interviews.

###  6.3. User Evaluation Result for Students

#### Students’ Expectations

Based on the Background (Part 1) survey, we identified the main challenges for
novice programmers and their expectations for an ITS (see Figures 6(a) and
6(b)). Their general underlying difficulties in learning programming are (1)
understanding programming tasks and starting to program, (2) debugging the
code and rectifying identified errors, (3) translating their solution strategy
into actual code, (4) having trouble with the syntax of a specific programming
language, and (5) getting the program right in the first place. In addition,
we asked the students more specifically about the difficulties the ITS can
address. Generally, they confirmed that their main difficulties are with (1)
figuring out what goes wrong in the program and (2) finding the error
location. Only half of them (7/15) mentioned that identifying a fix is a
problem.

#### Students’ Performance

Table 3 presents the quantitative results of the students’ performances in the
two controlled groups. Specifically, we focus on students who failed on their
first attempt. The second column represents the average number of students’
attempts for each task if their first attempt failed. The third column
represents the rectification rate (X/Y) of students who failed to solve a
particular task on the first attempt; X represents the number of students who
eventually rectified their solutions, and Y represents the number of students
who failed to solve a task on the first attempt. The column ”Avg Rectifying
Time” indicates the duration taken by a student to correct an incorrect
solution for a programming task.

Table 3. The average number of failed attempts, rectification rates, average rectifying time of failed attempts in minutes. A, B represents Group A and Group B. Tasks |  2.5cmAvg # Failed Attempts |  2cmRectification Rate |  1.8cmAvg Rectifying Time (mins)
---|---|---|---
| A | B | A | B | A | B
Task 1 | 4.8 | 4 | 4/5 | 0/2 | 7 | -
Task 2 | 1.9 | 5.5 | 7/7 | 3/4 | 9.2 | 9.3
Task 3 | 2.3 | 2.8 | 5/5 | 2/4 | 4.6 | 2.5
Task 4 | 2.3 | 3.1 | 5/6 | 5/7 | 4.5 | 11.3
Total | 2.7 | 3.7 | 21/23 | 10/17 | 6.7 | 8.9

#### Fewer attempts, higher accuracy

As shown in Table 3, students who received assistance from ITS (Group A)
solved more programming tasks with fewer attempts compared to students without
ITS (Group B). Although Group A students made more attempts than Group B
students for Task 1, it is important to note that the two students in Group B
who failed Task 1 could not rectify their solution. Therefore, the fewer
average attempts made by Group B students may be due to a lack of knowledge on
how to fix their solutions after a few attempts, resulting in giving up on the
task. On average, Group A students made 2.7 failed attempts compared to 3.7
for Group B students, indicating that Group A students submitted slightly
fewer attempts during the experiment. Even though the difference in attempts
is not very significant, Group A students had a higher success rate in
rectifying their solutions; they successfully fixed 21 (91.3%) out of the 23
failed attempts. While Group B students had a higher success rate on their
first attempt, they struggled more when they failed on their first attempt,
only succeeding in fixing 10/17 (58.8%), demonstrating the effectiveness of
ITS guidance.

Regarding rectifying time, Group A students outperformed Group B, with an
average of 6.7 minutes to repair one incorrect solution, compared to Group B’s
average of 8.9 minutes. Note that the average rectifying time for task 1 in
Group B is not available since no student could rectify their incorrect
attempts. Moreover, the average rectifying time for Group B is significantly
lower for Task 3 (2.5 minutes) because the two incorrect solutions were almost
correct. One student used the wrong function name in the recursive call, and
the other made an error in concatenating when returning the recursive case.
These mistakes were easily identified with the test cases, reducing the
rectifying time. Our supplemental material includes more details about the
attempts and feedback.

#### Usefulness of ITS

Figure 7(a) shows feedback survey results for students, where we queried their
satisfaction with the ITS. We were particularly interested in their feedback
regarding the usefulness of the features, such as highlighting the potential
error lines in the code editor and showing hints about error categories for
their mistakes. The results of the questions indicated that most Group A
students found the ITS helpful and were satisfied with its performance. For
example, over 80% of the students responded positively to the usefulness of
highlighted lines and mistake categories for their code. Furthermore, over 73%
of the students would like the ITS deployed in their programming course.
However, we found that one student showed negative feedback toward all
questions. This student failed to solve any tasks with correct syntax and
struggled to find proper solution strategies. As a result, the ITS could not
generate any feedback, as it could not explain the student’s intuition at this
stage. While this particular experience highlights the limitations of the ITS,
the overall positive feedback from the other students supports the potential
of ITS in enhancing CS-1 programming education.

Students’ Performances: The collected performance results support that the ITS
indeed helps the students to take _fewer_ attempts to solve _more_ programming
tasks in a _shorter_ time.

###  6.4. User Evaluation Result for Tutors

#### Tutors’ Expectations about the ITS

Similar to the students, we also asked tutors to identify their general
difficulties and expected features (see Figure 6(c)). They are primarily
concerned about generating the actual feedback for students, for which they
first need to identify the semantic and syntax errors in the submission.
Generating high-quality feedback becomes increasingly difficult because of the
large number of submissions that tutors have to handle. Error localization
techniques are helpful as they can help tutors to pinpoint erroneous code
areas faster than going through the complete submission themselves. Once
identified, fixing the actual error or grading the overall submission appears
to be less of a problem for them. Therefore, the most useful feature from the
already implemented ones also mentioned by the students (see Figure 6(d)) is
the error localization and explanation. Although we observed the students’
demand for addressing compilation/syntax mistakes, tutors showed low interest
in compilation error repair, which shows the discrepancy in requirements
between tutors and students. Tutors prefer feedback on semantic errors over
syntactic errors.

Tutors’ Expectations: Tutors mostly expect support in error localization and
explanation, and need less support for fix suggestions, particularly for
syntax errors.

#### Tutors’ Satisfaction with the ITS

We interviewed the tutors after they finished the grading activity of student
submissions in Section 6.3. Figure 7(b) shows that for all tutors, the ITS’s
currently available error localization capabilities are indeed most beneficial
for them. Most of them mentioned that the ITS helps them to speed up their
work in understanding the student’s errors (5/8) and formulating their own
feedback (6/8). However, none of them found that the feedback given by the ITS
can be directly used or can directly determine the mark of the student. Note
that the ITS had no automated grading capabilities at the time of the study.
Overall, the participants presented varying opinions about the usefulness of
the feedback (see Figure 7(c)). The tutors noticed that the given feedback is
biased towards only having one reference solution: the suggested
feedback/repair of a submission can be non-minimal if the student submission
follows a different strategy. We plan to address this limitation by fully
integrating the approach by Refactory (Hu et al., 2019), which generates
additional semantically equivalent but structurally different reference
solutions via refactoring. The overall satisfaction with the tool is diverse,
mainly ascribed to the limited feedback capabilities. Still, almost all of the
tutors (7/8) would like to see an ITS deployment in their next programming
course, primarily because of the strong support for error localization, which
provides a good starting point for understanding the student’s problem and
grading. Furthermore, most of the tutors (5/8) see the additional help by the
ITS as an improvement on the already available information from failing test
cases. As potential additions, the tutors mentioned that the ITS would benefit
from better feedback and error visualization, as well as feedback on non-
functional properties (see Figure 7(d)).

Tutors’ Experiences: The tutors reported that the ITS can help them handle
their grading tasks faster via its automated error localization capability.
Despite their concerns regarding the current feedback and grading
capabilities, they identified ITS as helpful and would like to use it in their
next CS-1 course.

##  7\. Ongoing deployment

In addition to the observations from the conducted user studies, we also
gained experiences by integrating the ITS into the programming learning
platform at our institution. After two years of development, it is currently
used in a CS-1 programming course to aid the human tutors in their manual
feedback and grading efforts. So far, we received qualitative positive
comments from the tutors: ”Automated, 24 hours and always readily available.”.
During this deployment, we experienced organizational and technical challenges
that may also affect the wider deployment of ITS. For example, in each
deployment, we must carefully adapt the ITS to the specific teaching setup of
the different CS-1 programming courses. This involves the used programming
language, the leveraged coding editors or learning management platforms for
integration, and the support for specific assignment types (e.g., GUI
programming). These are particularly important because the expectations and
pedagogical strategies differ for students in various departments. Please note
that this deployment in the CS-1 course is ongoing.

##  8\. Challenges and Lessons Learned

To further share our experience with our combined research and teaching
effort, we report the challenges we faced and the lessons learned concerning
the organizational and technical aspects.

#### Incentives for Stakeholders

We have three main user groups: the students who receive feedback, the tutors
who can use the ITS to better understand the students’ errors and get grading
support, and the lecturers who provide the inputs like assignments and
reference implementations. Lecturers are naturally concerned about deploying
more tools, including the potential negative effects on the learning outcome
caused by inaccurate output. To gradually convince the lecturers, we decided
to first focus on a targeted deployment for tutors. For tutors, an imperfect
output is less critical and still can provide helpful guidance to them and
help us to get feedback continuously. In contrast to the lecturers, the tutors
have a generally more positive attitude regarding the ITS; they are willing to
join longer interviews to share their experience in the tutoring process and
their requirements. As a result, we have been able to successfully invite
tutors to our requirements elicitation sessions as well as to our user
studies. To engage with first-year students, we designed a user study that not
only has a monetary reimbursement but also provides additional programming
training and an extra tutorial after the user study to explain the programming
tasks to them individually. The third-year students who develop the components
in our course showed great interest in our project because it is (or will be)
deployed in a real context and because they like working on a larger project
with existing parts. Overall, it is a valuable experience for them, as shown
by the following student quotes about the question of what they liked the most
in the course:

“The project component – It’s really interesting, and I like that it will
actually be used. I think that makes it one of the most interesting modules
I’ve taken so far. It’s very cool to understand the reasoning for design
details with the teaching team that actually built it.”

“Participation in an actual to–be–deployed software project is exciting and
makes your effort somewhat worthwhile.”

#### Project Preferences

In the first instance of our course, we allowed students to pick projects on
their own. Therefore, we ended up with an imbalanced selection of projects.
Students tended to prefer a project with more explicit requirements, e.g., a
Parser component, instead of a Repair project that involves more research. In
the second instance, we therefore only allowed bidding on projects while the
teaching team made the final decision.

#### Mentoring support for third-year students

In the second instance of our course, we had dedicated, experienced mentors
(i.e., graduate students) who helped the student groups organize their
efforts. While we did not observe the students without mentors in our first-
course instance perform poorly, we still experienced that the additional
mentorship helped them get the best out of their project. This is not only
helpful to improve our system but also creates a better project experience for
them.

#### Managing Software Evolution

Overall, we experienced that our general approach is feasible and helps both
the third-year and the first-year students. However, we have also seen that we
must invest significant time from our side in managing the software evolution.
This includes selecting and integrating the best projects, maintaining the
code base, updating the design to cater to new requirements, and implementing
new components to check their feasibility before we can offer them as a
project in the course.

##  9\. Impact and Vision for the future

In this work, we presented our concept for linking the teaching of software
engineering projects with the teaching of programming and introduced our
intelligent tutoring system (ITS). Further, we discussed our experiences using
the ITS in our course and the observations from the user studies. In the
following two sections, we discuss the observed impact of our work and provide
a concluding outlook for intelligent tutoring in the AI era.

#### Impact: Teachers, Students, Research

Based on our experience, the presented ITS impacts several aspects of
programming. With our long-running teaching effort, we incrementally develop
and improve the ITS into a usable product. We change how first-year students
learn programming and support teachers in the introductive CS courses.
Furthermore, we provide the platform for senior students to practice software
engineering in a realistic scenario. Additionally, they are encouraged to work
on research-oriented topics by selecting the corresponding projects. Overall,
we received positive feedback in our user studies: from the 23 students and
tutors, more than 78% would like to see the ITS deployed in their next
programming course. Moreover, the ITS helps to integrate the latest research
in educational APR and related topics. Our teaching innovation can also impact
students from other universities as they adopt our concept and join the ITS
development team. In fact, we have already successfully exported the ITS
teaching concept to another university.

#### Intelligent Tutoring in AI Era

With the shift from manual programming to AI-assisted programming, CS
education must also be innovated. We think the ITS represents a well-suited
platform to help students learn an effective way of using AI-based code
generation tools like GitHub Copilot and ChatGPT. Therefore, instead of
exposing the student directly to the AI assistant, the ITS can moderate the
prompts and explain the generated code, achieving a three-way interaction
between the student, ITS, and AI assistant (see Figure 8).

Figure 8. Envisioned three-way interaction between Student, ITS, and AI
Assistant.

Based on the student’s performance, mistakes, and interaction with the AI
assistant, the ITS can learn a model of the student’s current mental model.
This can be achieved by mapping the student’s mistakes and questions to the
underlying programming concepts.

## Acknowledgments

We would like to thank all students, tutors and lecturers who have supported
our work in various ways, for more than two years in two offerings of the
course. This work was partially supported by a Singapore Ministry of Education
(MoE) Tier 3 grant ”Automated Program Repair”, MOE-MOET32021-0001.

## References

  * (1)
  * Ahmed et al. (2022) Umair Z. Ahmed, Zhiyu Fan, Jooyong Yi, Omar I. Al-Bataineh, and Abhik Roychoudhury. 2022.  Verifix: Verified Repair of Programming & Assignments.  _ACM Trans. Softw. Eng. Methodol._ 31, 4, Article 74 (jul 2022), 31 pages.  https://doi.org/10.1145/3510418
  * Ahmed et al. (2018) Umair Z. Ahmed, Pawan Kumar, Amey Karkare, Purushottam Kar, and Sumit Gulwani. 2018.  Compilation Error Repair: For the Student Programs, from the Student Programs. In _Proceedings of the 40th International Conference on Software Engineering: Software Engineering Education and Training_ (Gothenburg, Sweden) _(ICSE-SEET ’18)_. Association for Computing Machinery, New York, NY, USA, 78–87.  https://doi.org/10.1145/3183377.3183383
  * Anderson et al. (2023) Boyd Anderson, Martin Henz, and Kok-Lim Low. 2023.  Community-Driven Course and Tool Development for CS1. In _Proceedings of the 54th ACM Technical Symposium on Computer Science Education V. 1_ (Toronto ON, Canada) _(SIGCSE 2023)_. Association for Computing Machinery, New York, NY, USA, 834–840.  https://doi.org/10.1145/3545945.3569740
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Bruegge et al. (2015) Bernd Bruegge, Stephan Krusche, and Lukas Alperowitz. 2015.  Software engineering project courses with industrial clients.  _ACM Transactions on Computing Education (TOCE)_ 15, 4 (2015), 1–31.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Delgado et al. (2017) David Delgado, Alejandro Velasco, Jairo Aponte, and Andrian Marcus. 2017.  Evolving a project-based software engineering course: A case study. In _2017 IEEE 30th Conference on Software Engineering Education and Training (CSEE &T)_. IEEE, 77–86.
  * Fan et al. (2023) Zhiyu Fan, Shin Hwei Tan, and Abhik Roychoudhury. 2023.  Concept-Based Automated Grading of CS-1 Programming Assignments. In _Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis_ (Seattle, WA, USA) _(ISSTA 2023)_. Association for Computing Machinery, New York, NY, USA, 199–210.  https://doi.org/10.1145/3597926.3598049
  * Gulwani et al. (2018) Sumit Gulwani, Ivan Radiček, and Florian Zuleger. 2018.  Automated Clustering and Program Repair for Introductory Programming Assignments. In _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Philadelphia, PA, USA) _(PLDI 2018)_. Association for Computing Machinery, New York, NY, USA, 465–480.  https://doi.org/10.1145/3192366.3192387
  * Hu et al. (2019) Yang Hu, Umair Z. Ahmed, Sergey Mechtaev, Ben Leong, and Abhik Roychoudhury. 2019.  Re-Factoring Based Program Repair Applied to Programming Assignments. In _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. 388–398.  https://doi.org/10.1109/ASE.2019.00044
  * Johns-Boast and Flint (2013) Lynette Johns-Boast and Shayne Flint. 2013.  Simulating industry: An innovative software engineering capstone design course. In _2013 IEEE Frontiers in Education Conference (FIE)_. IEEE, 1782–1788.
  * Kurniawan et al. (2023) Oka Kurniawan, Christopher M. Poskitt, Ismam Al Hoque, Norman Tiong Seng Lee, Cyrille Jégourel, and Nachamma Sockalingam. 2023.  How Helpful do Novice Programmers Find the Feedback of an Automated Repair Tool?  arXiv:2310.00954 [cs.CY]
  * Le Goues et al. (2011) Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2011.  Genprog: A generic method for automatic software repair.  _Ieee transactions on software engineering_ 38, 1 (2011), 54–72.
  * Mechtaev et al. (2016) Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016.  Angelix: Scalable multiline program patch synthesis via symbolic analysis. In _Proceedings of the 38th international conference on software engineering_. 691–701.
  * Mirhosseini et al. (2023) Samim Mirhosseini, Austin Z. Henley, and Chris Parnin. 2023.  What Is Your Biggest Pain Point? An Investigation of CS Instructor Obstacles, Workarounds, and Desires. In _Proceedings of the 54th ACM Technical Symposium on Computer Science Education V. 1_ (Toronto ON, Canada) _(SIGCSE 2023)_. Association for Computing Machinery, New York, NY, USA, 291–297.  https://doi.org/10.1145/3545945.3569816
  * Nguyen et al. (2013) Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. 2013.  Semfix: Program repair via semantic analysis. In _2013 35th International Conference on Software Engineering (ICSE)_. IEEE, 772–781.
  * Schreier (2012) Margrit Schreier. 2012.  _Qualitative content analysis in practice_.  Sage publications.
  * Singer (2019) Natasha Singer. 2019.  The Hard Part of Computer Science? Getting Into Class.  https://www.nytimes.com/2019/01/24/technology/computer-science-courses-college.html Accessed: 16-March-2023.
  * Singh et al. (2013) Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. 2013.  Automated feedback generation for introductory programming assignments. In _Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation_. 15–26.
  * Spichkova (2019) Maria Spichkova. 2019.  Industry-oriented project-based learning of software engineering. In _2019 24th International conference on engineering of complex computer systems (ICECCS)_. IEEE, 51–60.
  * Tenhunen et al. (2023) Saara Tenhunen, Tomi Männistö, Matti Luukkainen, and Petri Ihantola. 2023.  A systematic literature review of capstone courses in software engineering.  _Information and Software Technology_ (2023), 107191.
  * Wang et al. (2018) Ke Wang, Rishabh Singh, and Zhendong Su. 2018.  Search, Align, and Repair: Data-Driven Feedback Generation for Introductory Programming Exercises. In _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Philadelphia, PA, USA) _(PLDI 2018)_. Association for Computing Machinery, New York, NY, USA, 481–495.  https://doi.org/10.1145/3192366.3192384
  * Yasunaga and Liang (2021) Michihiro Yasunaga and Percy Liang. 2021.  Break-it-fix-it: Unsupervised learning for program repair. In _International Conference on Machine Learning_. PMLR, 11941–11952.
  * Yi et al. (2017) Jooyong Yi, Umair Z Ahmed, Amey Karkare, Shin Hwei Tan, and Abhik Roychoudhury. 2017.  A feasibility study of using automated program repair for introductory programming assignments. In _Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering_. 740–751.
  * Zhang et al. (2022) Jialu Zhang, José Cambronero, Sumit Gulwani, Vu Le, Ruzica Piskac, Gustavo Soares, and Gust Verbruggen. 2022.  Repairing Bugs in Python Assignments Using Large Language Models.  _arXiv preprint arXiv:2209.14876_ (2022).


# Search for the rare decays $B^{0}_{(s)}\to\mu^{+}\mu^{-}$ at LHCb

CPPM, Aix-Marseille Université, CNRS/IN2P3, Marseille, France
E-mail On behalf of the LHCb collaboration

###### Abstract:

A search for the $B_{s}\to\mu^{+}\mu^{-}$ and $B_{d}\to\mu^{+}\mu^{-}$ decays
is presented using $\sim 300$ pb-1 of $pp$ collisions at $\sqrt{s}$ = 7 TeV
collected by the LHCb experiment at the Large Hadron Collider at CERN. The
measured upper limit for the branching ratio of the $B_{s}\to\mu^{+}\mu^{-}$
decay is $\cal B$($B_{s}\to\mu^{+}\mu^{-}$)$<1.3\ (1.6)\times 10^{-8}$ at 90 %
(95 %) confidence level (CL), while in the case of the
$B_{d}\to\mu^{+}\mu^{-}$ decay the measured upper limit is $\cal
B$($B_{d}\to\mu^{+}\mu^{-}$)$<4.2\ (5.1)\times 10^{-9}$ at 90 % (95 %) CL. A
combination with the 2010 dataset results in $\cal
B$($B_{s}\to\mu^{+}\mu^{-}$)$<1.2\ (1.5)\times 10^{-8}$ at 90 % (95 %) CL.

##  1 Introduction

Measurements at low energies may provide interesting indirect constraints on
the masses of particles that are too heavy to be produced directly. This is
particularly true for Flavour Changing Neutral Currents (FCNC) processes which
are highly suppressed in the Standard Model (SM) and can only occur through
higher order diagrams. The SM prediction for the branching ratios ($\cal B$)
of the FCNC decays $B_{s}\to\mu^{+}\mu^{-}$ and $B_{d}\to\mu^{+}\mu^{-}$ have
been computed to be $(3.2\pm 0.2)\times 10^{-9}$ and $(0.10\pm 0.01)\times
10^{-9}$ respectively [1]. However New Physics (NP) contributions can
significantly enhance these values.

The best published limits from the Tevatron at $95\%$ CL are obtained using
6.1 fb-1 by the D0 collaboration [2], and using 2 fb-1 by the CDF
collaboration [3]. The CDF collaboration has also presented a preliminary
result [4] with 6.9 fb-1 in which an excess of
$B_{s}\to\mu^{+}\mu^{-}$candidates is reported, compatible with a $\cal
B$($B_{s}\to\mu^{+}\mu^{-}$)= $(1.8^{+1.1}_{-0.9})\times 10^{-8}$.

The LHCb collaboration has previously obtained the limits $\cal
B$($B_{s}\to\mu^{+}\mu^{-}$)$<5.4\times 10^{-8}$ and $\cal
B$($B_{d}\to\mu^{+}\mu^{-}$)$<1.5\times 10^{-8}$ at 95$\%$ CL based on 37 pb-1
of luminosity collected in the 2010 run [5]. We present here a measurement
based on 300 pb-1 of integrated luminosity collected between March and June
2011.

##  2 Analysis strategy

The general structure of the analysis is similar to the one described in Ref.
[5] and is detailed in Ref. [6].

The selection procedure treats signal and control/normalization channels in
the same way in order to minimize the systematic uncertainties. Assuming the
SM branching ratio and the $b\bar{b}$ cross-section, measured within the LHCb
acceptance, of $\sigma_{b\overline{b}}=75\pm 14\,\mu$b [7], approximately
$3.4~{}(0.32)$ $B^{0}_{s}\to\mu^{+}\mu^{-}$ ($B^{0}\to\mu^{+}\mu^{-}$) events
are expected to be reconstructed and selected in the analysed sample.

After the selection, each event is given a probability to be signal or
background in a two-dimensional space defined by two independent likelihoods:
the invariant mass and the output of a Boosted Decision Tree (BDT) from the
TMVA package [8]. The combination of variables entering the BDT is optimized
using Monte Carlo (MC) simulation. The following variables have been used: the
$B$ lifetime, impact parameter and transverse momentum of the $B$, the minimum
impact parameter significance of the muons, the distance of closest approach
between the two muons, the degree of isolation of the two muons with respect
to any other track in the event, the cosine of the polarization angle, the $B$
isolation and the minimum $p_{T}$ of the muons. The BDT distribution is then
transformed in order to be flat for the signal and peaked at 0 for the
background.

The calibration of the invariant mass and the BDT likelihoods are obtained
from data using control samples. The signal BDT shape is obtained from
$B^{0}_{(s)}\to h^{+}h^{-}$ events free from trigger biases while the
background shape is obtained using sideband $B^{0}_{(s)}\to\mu^{+}\mu^{-}$
candidates. The resulting distributions are shown in Fig. 1.

Figure 1: BDT calibration for signal and background.

The parameters describing the invariant mass line shape of the signal are
extracted from data using control samples. The average mass values are
obtained from $B^{0}\to K^{+}\pi^{-}$ and $B^{0}_{s}\to K^{+}K^{-}$ exclusive
samples. The $B^{0}_{s}$ and $B^{0}$ mass resolutions are estimated by
interpolating the ones obtained with the dimuon resonances ($J/\psi,\psi(2S)$
and $\Upsilon(1S,2S,3S)$) and cross-checked via a fit to the invariant mass
distribution of the $B^{0}_{(s)}\to h^{+}h^{-}$ inclusive decays and of the
$B^{0}\to K^{+}\pi^{-}$ exclusive decay. The interpolation yields
$\sigma(B)=24.6\pm 0.2_{\rm stat}\pm 1.0_{\rm syst}$.

The number of expected signal events is obtained by normalizing to channels of
known branching ratios, $B^{+}\\!\to J/\psi K^{+}$, $B^{0}_{s}\\!\to
J/\psi\phi$, and $B^{0}\\!\to K^{+}\pi^{-}$, that are selected in a way as
similar as possible to the signal.

The probability for a background event to have a given BDT and invariant mass
value is obtained by a fit of the mass distribution of events in the mass
sidebands, in bins of BDT. Different fit functions and mass ranges are used to
compute the systematics uncertainties. The two-dimensional space formed by the
invariant mass and BDT is binned, and for each bin we compute how many events
are observed in data, how many signal events are expected for a given $\cal B$
hypothesis and luminosity, and how many background events are expected for a
given luminosity. The compatibility of the observed distribution of events in
all bins with the expected one for a given $\cal B$ hypothesis is computed
using the CLs method [9], which allows to exclude a given hypothesis at a
given confidence level.

In order to avoid unconscious biases, the data in the mass region defined by
$M_{B^{0}}-60\,{\rm MeV}/c^{2}$ and $M_{B^{0}_{s}}+60\,{\rm MeV}/c^{2}$ have
been blinded until the completion of the analysis.

##  3 Results

Figure 2: Distribution of selected dimuon events in the invariant mass vs BDT
plane. The orange short-dashed (green long-dashed) lines indicate the $\pm
60\,{\rm MeV}/c^{2}$ search window around the $B^{0}_{s}$ ($B^{0}$).

The distribution of events in the invariant mass versus BDT plane is reported
Fig. 2. The expected limit at 90 (95) % CL for the $B_{s}\to\mu^{+}\mu^{-}$ is
$0.8~{}(1.0)\times 10^{-8}$ in the case of background only hypothesis. When
adding signal events according to the SM branching fraction, these limits
become $1.2~{}(1.5)\times 10^{-8}$. The observed values for the
$B_{s}\to\mu^{+}\mu^{-}$channel is $1.3~{}(1.6)\times 10^{-8}$ with a CLb
value of 0.80. The observed events are in good agreement with the background
expectations and the presence of $B_{s}\to\mu^{+}\mu^{-}$events according to
SM predictions.

For the $B_{d}\to\mu^{+}\mu^{-}$, the expected limit at 90 (95) % CL is
$2.4~{}(3.1)\times 10^{-9}$ in the case of background only hypothesis. The
observed values is $4.2~{}(5.2)\times 10^{-9}$ with a CLb value of 0.79. The
comparison of the observed distribution of events with the expected background
distribution results in a p-value (1-$\textrm{CL}_{\textrm{b}}$) of 20 % (21
%) for the $B_{s}\to\mu^{+}\mu^{-}$ ($B_{d}\to\mu^{+}\mu^{-}$) decays. In the
case of $B_{d}\to\mu^{+}\mu^{-}$, the slightly low p-value is due to an excess
of the observed events in the most sensitive BDT bin with respect to the
background expectations. A larger data sample will allow to clarify the
situation. In the case of $B_{s}\to\mu^{+}\mu^{-}$, when a signal is included
at the level expected in the Standard Model, the p-value increases to 50 %.

Finally, the $B_{s}\to\mu^{+}\mu^{-}$ limit is combined with the one published
from the 2010 data to obtain $\cal B$($B_{s}\to\mu^{+}\mu^{-}$) ¡
$1.2~{}(1.5)\times 10^{-8}$ at 90 % (95 %) CL. This 90 % CL upper limit is
still 3.8 times above the standard model prediction.

## References

  * [1] A.J. Buras, G. Isidori and P. Paradisi, “EDMs vs CPV in $B_{s,d}$ mixing in two Higgs doublet models with MFV”, arXiv:1007.5291 [hep-ph] (2010).
  * [2] V. Abazov et al. [D0 Collaboration], “Search for the rare decay $B^{0}_{s}\to\mu^{+}\mu^{-}$”, Phys. Lett. B 693 (2010) 539.
  * [3] T. Aaltonen et al. [CDF Collaboration], “Search for $B_{s}\to\mu^{+}\mu^{-}$and $B_{d}\to\mu^{+}\mu^{-}$Decays with 2$\mbox{\,fb}^{-1}$ of $p\bar{p}$ Collisions” Phys. Rev. Lett. 100 (2008) 101802.
  * [4] T. Aaltonen et al. [CDF Collaboration], “Search for $B_{s}\to\mu^{+}\mu^{-}$and $B_{d}\to\mu^{+}\mu^{-}$Decays with CDF-II” , arXiv:1107.2304v1 [hep-ex] (2011).
  * [5] R. Aaji et al. [LHCb Collaboration], “Search for the rare decays $B^{0}_{s}\to\mu^{+}\mu^{-}$ and $B^{0}\to\mu^{+}\mu^{-}$”, Phys. Lett. B 699 (2011) 330.
  * [6] R. Aaji et al. [LHCb Collaboration], LHCb-CONF-2011-037.
  * [7] R. Aaij et al. [LHCb Collaboration], “Measurement of $\sigma$(pp $\rightarrow b\bar{b}$ X) at $\sqrt{s}$=7 TeV in the forward region”, Phys. Lett. B 694 (2010) 209.
  * [8] TMVA, Toolkit for Multi Variate analysis with ROOT, http://tmva.sourceforge.net.
  * [9] A. Read, “Presentation of Search Results: The $\textrm{CL}_{\textrm{s}}$ Technique”, J. Phys. G 28 (2002) 2693.


# Unsupervised Community Detection with Modularity-Based Attention Model

Ivan Lobov, Sergey Ivanov
Criteo
Paris, France
<EMAIL_ADDRESS>

###### Abstract

In this paper we take a problem of unsupervised nodes clustering on graphs and
show how recent advances in attention models can be applied successfully in a
”hard” regime of the problem. We propose an unsupervised algorithm that
encodes Bethe Hessian embeddings by optimizing soft modularity loss and argue
that our model is competitive to both classical and Graph Neural Network (GNN)
models while it can be trained on a single graph.

##  1 Introduction

Community detection on graphs is a task of learning similar classes of
vertices from the network’s topology. It is one of the central problems in
data mining and has found numerous applications in sociological studies
(Goldenberg et al. (2010)), DNA 3D folding (Cabreros et al. (2016)), product
recommendations (Clauset et al. (2004)), natural language processing (Ball et
al. (2011)) and more. It is not surprising that many fundamental results have
been obtained in recent years that shed the light on our understanding of the
solvability of this problem in general. Specifically, precise phase transition
and fundamental limits exist for one of the central graph generation models to
test community detection algorithms, the so-called Stochastic Block Model
SBM($n$, $p$, $W$) and its symmetric variant Symmetric Stochastic Block Model,
SSBM($n$, $k$, $A$, $B$) (Abbe (2018)). In this paper, we’ll be dealing with a
simpler case, SSBM.

The optimization of log-likelihood and modularity are equivalent in SSBM model
(Newman, 2013). Hence, we propose to use a generalization of modularity that
outputs the probability of each cluster for a node and is therefore
differentiable for a neural network model. Our model is based on the recent
advances in NLP where Transformer model (Vaswani et al. (2017)) with attention
mechanism shows superior results. We adopt the encoder part of Transformer to
transform initially obtained Bethe Hessian embeddings and then produce the
probability of each cluster for each node to optimize with our loss function.

Our contributions include:

  * •

A new model with attention mechanism that optimizes a soft modularity loss
function (and release the code to reproduce our
results111https://github.com/Ivanopolo/modnet).

  * •

A comparative study of classical algorithms and recent supervised graph neural
network and outline several advantages of the unsupervised model.

##  2 Related Work

SBM models have seen a resurged interest recently due to the conjecture of
(Decelle et al. (2011)) that hypotheses phase transition for weak recovery
case (the one we are interested in this paper) and the existence of the
information-computation gap for 4 communities in the symmetric case. It was
proved in (Massoulié (2014); Bordenave et al. (2015); Mossel et al. (2018))
that efficient algorithms exists when there are 2 communities and signal-to-
noise ratio is greater than one (KS threshold), while (Mossel et al. (2015))
shows that it is impossible to detect communities below this threshold for
2-community case. For more than 3 communities it was also proved that there
are non-efficient algorithms that can weakly recover communities strictly
below KS threshold (Abbe & Sandon (2015)). An extensive overview of the area
can be found in Abbe (2018).

Graph neural networks have been recently applied to solve community detection
problem with the current state-of-the-art LGNN model(Chen et al. (2019))
designed to extract high-order node interactions via Non-backtracking
operator. In parallel line of work, there are graph neural models based on
attention mechanisms (Veličković et al. (2018); Kool et al. (2019b)) that have
showed prominent results in other domains such as speech recognition and NLP.

##  3 SSBM Regimes

Signal-to-Noise Ratio (SNR) for SSBM($n$, $k$, $a/n$, $b/n$) model is defined
as:

$\text{SNR}=\frac{(a-b)^{2}}{k(a+(k-1)b)}$ (1)

It is known that for $k\geq 2$ and $\text{SNR}>1$ it is possible to detect
communities in polynomial-time (Abbe & Sandon (2016)). Moreover, when
$\text{SNR}\leq 1$ and $k=2$ the weak recovery of SSBM model is not possible
theoretically. However, it is also known that for $k\geq 4$ it is possible to
weakly recover in the setup of $\text{SNR}>\alpha$, where $\alpha<1$. This
means that there exists a computational threshold after which only
information-theoretical algorithms can recover communities. This gap between
what is possible to compute efficiently and what can be computed in general is
known as information-computation gap. In this work we compare two different
regimes: one regime that lies within a computation threshold and is achievable
by classical algorithms (associative case) and one regime for the information-
theoretical gap (disassociative case).

##  4 Approach

###  4.1 Loss

If we know the generative model from which a graph is produced, it is possible
to make statistical inference and evaluate the fitness of the estimated
parameters using model’s log likelihood. This approach assumes a hard
labelling of the nodes and therefore requires some form of relaxation to
obtain a differentiable loss function. It has been shown in (Newman, 2013)
that optimizing log-likelihood for the SSBM model is equivalent to the
modularity optimization, a popular heuristic approach to graph clustering. And
there exists (Havens et al., 2013) a generalization of modularity to soft
labelling which is well differentiable and can be directly used for learning.
We take a soft modularity $M$ as our loss function:

$M=-tr(UBU^{T})/||A||_{1}$

Where $U\in\mathbb{R}^{N\times C}$ is a matrix of probabilities of nodes
attribution to clusters (the number of which is a model hyperparameter),
$B=A-dd^{T}/||A||_{1}$, $d$ is a vector of node degrees, $A$ is the adjacency
matrix and $||A||_{1}=\sum{|A_{ij}|}$.
As the modularity might have multiple local optima, we found that it is
beneficial if we can include additional information about the graph as a prior
to steer the model in the right direction. We use a regularizer defined by:

$R=\left(\sum_{i}^{C}\left(\sum_{j}^{N}U_{ij}-\frac{1}{C}\right)^{2}\right)$

Where $C$ is the number of communities in the graph. The regularizer forces
the model to find communities of similar sizes as is expected in SSBM.

Our final loss is:

$\begin{cases}L_{a}=M+\lambda R,&\text{for associative communities}\\\
L_{d}=-M+\lambda R,&\text{for disassociative communities.}\end{cases}$ (2)

We use negation of modularity loss $M$ as modularity is negative for
disassociative case. The benefits of using this loss function are the
following: we do not require explicit labels for learning, the loss is
invariant under labels permutation and it is a consistent loss under SSBM with
soft community partitioning.

###  4.2 Model

Our network takes as input initialized node embeddings and consists of three
main blocks: projection into higher dimensions (done via a fully connected
network with skip connections (He et al., 2016) and batch norm (Ioffe &
Szegedy, 2015)), graph attention block and output prediction layer with a
fully connected layer and a softmax.

#### Node Embeddings

We initialize node embeddings with eigenvectors recovered as part of the Bathe
Hessian decomposition, a baseline algorithm described in Section 5.3.

#### Graph Attention

At every layer the attention is done over all neighbors of the node. The
Encoder module is described in (Kool et al., 2019a) which is a form of multi-
headed attention on neighbors of a node. It is particularly well-suited for
our initialization of the node embeddings; the key-value dot-products give the
model access to the community structure estimated by the Bethe Hessian
eigenvectors.

###  4.3 Training

Our model is an unsupervised model in a sense that it does not require any
labels from the original graph. We train the model separately on each graph
repeatedly trying to improve the soft modularity loss. Since the method does
not require a larger training set, it significantly reduces the training time.
For all the experiments reported, we trained a model with 2 layers, 3 heads of
attention, the size of all hidden layers equal to 48 and regularization
parameter $\lambda=0.5$.

##  5 Experiments

###  5.1 Datasets

We generate two datasets SBM($n$, $k$, $a/n$, $b/n$) that correspond to
associative and disassociative cases. For the disassociative dataset, we set
$a=0$ and $b=18$, which means that there are no links between vertices of the
same cluster. For the associative dataset, we set $a=21$ and $b=2$. All
datasets have $n=400$ vertices and $k=5$ communities. The parameters for the
disassociative case correspond to the information-theoretical gap, while for
associative case they correspond to the regime when belief propagation can
weakly recover the clustering efficiently. We generate 6000 graphs for
training dataset and 1000 for validation.

###  5.2 Evaluation Metrics

Overlap measures the intersection of the original assignment $y$ and the
predicted assignment $\hat{y}$ across all possible permutations from the
permutation group $S$ (Decelle et al. (2011)):

$O(y,\hat{y})=\max\limits_{\pi\in
S_{\hat{y}}}\frac{(1/n)\sum\limits_{u}\delta_{y(u),\pi(\hat{y}(u)})-1/c}{1-1/c}$

Where $n$ is the number of nodes in a graph, $c$ is the number of communities
and $\delta_{u,v}$ equals one when $u=v$ and zero, otherwise.

Mutual information is a similarity measure between two labels assignments $y$
and $\hat{y}$:

$I(y,\hat{y})=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{y(i)\cap\hat{y}(j)}{n}\log
n\frac{y(i)\cap\hat{y}(j)}{|y(i)||\hat{y}(j)|}$ (3)

We use a normalized version (Normalized Mutual Information, hence NMI) of (3)
by the arithmetic mean of the entropy for each assignment.
Modularity is a measure of fitness of our inference assuming the SSBM
generative model (it differs by a constant factor from the log likelihood). It
is positive for associative communities and negative for disassociative ones.

###  5.3 Baseline Methods

We compare our model with a state-of-the-art GNN model, LGNN, and several
classical baselines.
Bethe Hessian, introduced in Saade et al. (2014), is a spectral approximation
of Belief Propagation (BP), a classical algorithm for community detection, by
employing the Bethe Hessian operator:

$H=(r^{2}-1)\mathds{1}-rA+D,$

where $r$ is the largest eigenvalue of non-backtracking operator $B$, $A$ is
the adjacency matrix and $D$ is a diagonal matrix of degrees. We find the $k$
smallest algebraically eigenvectors of $H$ and find clusters using k-means
algorithm. We found that its results are more stable and often better in
practice than of BP.

Louvain Modularity (Blondel et al., 2008) is a popular baseline that greedily
updates the clusters if the modularity is improved. Since it does not control
the number of clusters and we often ended up with more clusters that in the
original graph, we did not compute the overlap metric for it (which requires
the same number of communities). We do not report results for the
disassociative case as the algorithm cannot find communities in this setting
by design, it can only merge nodes that are neighbors.

LGNN Chen et al. (2019) is a supervised community recovery algorithm based on
GNNs and that can learn operators of inter-graph node and edge connectivity
similar to laplacian for nodes or non-backtracking operator for edges.

#### GNN

Kipf & Welling (2017) In addition to the attention model, we also experiment
with GNN architecture that produces network embeddings that are trained using
our loss equation (2).

For our GNN and Attention models, we also have a choice of initialization of
embeddings. We add results for Random and Bethe-Hessian (BH) initialization.

###  5.4 Empirical Results

Results are presented in Tables 2 and 2. Note that in disassociative case, the
smaller value for modularity, the better; for all other metrics, the higher,
the better. True labels denote the optimal values for the datasets. Among our
4 proposed algorithms (at the bottom), Attention model with Bethe-Hessian
initialization is superior, showing that both the structure of the model and
the initialization of embeddings improve the quality on all metrics. Overall,
we can see that our modularity-based approach achieves competitive results for
the associative and disassociative dataset even compared with supervised LGNN.
Our model Attention-BH also achieves the top performance on modularity metric
among all algorithms as soft modularity is explicitly present in the loss
function. We can see that the loss function that we propose allows us to learn
as good or even better fit for the generative model (SSBM), which shows that
it can be efficiently used to find communities in a fully unsupervised way,
learning only on the current graph.

Table 1: Associative Dataset.
Algorithm | Modularity | Overlap | NMI
---|---|---|---
True Labels | 0.52 | 1.0 | 1.0
LGNN (supervised) | 0.50 | 0.80 | 0.67
Bethe Hessian | 0.52 | 0.85 | 0.69
Louvain Modularity | 0.48 | N/A | 0.48
GNN-Random | 0.47 | 0.53 | 0.48
GNN-BH | 0.49 | 0.66 | 0.61
Attention-Random | 0.42 | 0.36 | 0.27
Attention-BH | 0.51 | 0.78 | 0.67

Table 2: Disassociative Dataset.
Modularity | Overlap | NMI
---|---|---
-0.20 | 1.0 | 1.0
-0.16 | 0.24 | 0.13
-0.15 | 0.21 | 0.11
N/A | N/A | N/A
0 | 0.02 | 0.01
-0.16 | 0.2 | 0.1
-0.17 | 0.12 | 0.04
-0.18 | 0.22 | 0.11

##  6 Conclusion

In this work we propose a novel approach on how to recover communities in
unsupervised way and conduct experiments comparing to state-of-the-art
supervised neural models and unsupervised classical algorithms. Supervised
models achieves the state-of-the-art results but with the price of having more
parameters and longer training time. We believe it is interesting to combine
LGNN architecture with an unsupervised modularity loss as potential future
work.

## References

  * Abbe & Sandon (2016) E. Abbe and C. Sandon.  Crossing the ks threshold in the stochastic block model with information theory.  In _2016 IEEE International Symposium on Information Theory (ISIT)_ , pp. 840–844, 2016.
  * Abbe (2018) Emmanuel Abbe.  Community detection and stochastic block models: Recent developments.  _Journal of Machine Learning Research_ , 18(177):1–86, 2018.
  * Abbe & Sandon (2015) Emmanuel Abbe and Colin Sandon.  Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap.  _CoRR_ , abs/1512.09080, 2015.
  * Ball et al. (2011) Brian Ball, Brian Karrer, and M. E. J. Newman.  An efficient and principled method for detecting communities in networks.  _CoRR_ , abs/1104.3590, 2011.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ , 2008(10):P10008, 2008.
  * Bordenave et al. (2015) Charles Bordenave, Marc Lelarge, and Laurent Massoulie.  Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs.  In _Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)_ , FOCS ’15, 2015.
  * Cabreros et al. (2016) I. Cabreros, E. Abbe, and A. Tsirigos.  Detecting community structures in hi-c genomic data.  In _2016 Annual Conference on Information Science and Systems (CISS)_ , pp. 584–589, 2016.
  * Chen et al. (2019) Zhengdao Chen, Lisha Li, and Joan Bruna.  Supervised community detection with line graph neural networks.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=H1g0Z3A9Fm.
  * Clauset et al. (2004) Aaron Clauset, M. E. J. Newman, , and Cristopher Moore.  Finding community structure in very large networks.  _Physical Review E_ , 2004.
  * Decelle et al. (2011) Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborova.  Phase transition in the detection of modules in sparse networks.  2011\.
  * Goldenberg et al. (2010) Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, and Edoardo M. Airoldi.  A survey of statistical network models.  _Found. Trends Mach. Learn._ , 2(2), 2010.
  * Havens et al. (2013) Timothy C Havens, James C Bezdek, Christopher Leckie, Kotagiri Ramamohanarao, and Marimuthu Palaniswami.  A soft modularity function for detecting fuzzy communities in social networks.  _IEEE Transactions on Fuzzy Systems_ , 21(6):1170–1175, 2013.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Ioffe & Szegedy (2015) Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  _arXiv preprint arXiv:1502.03167_ , 2015.
  * Kipf & Welling (2017) Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Kool et al. (2019a) Wouter Kool, Herke van Hoof, and Max Welling.  Attention, learn to solve routing problems!  In _International Conference on Learning Representations_ , 2019a.  URL https://openreview.net/forum?id=ByxBFsRqYm.
  * Kool et al. (2019b) Wouter Kool, Herke van Hoof, and Max Welling.  Attention, learn to solve routing problems!  In _International Conference on Learning Representations_ , 2019b.  URL https://openreview.net/forum?id=ByxBFsRqYm.
  * Massoulié (2014) Laurent Massoulié.  Community detection thresholds and the weak ramanujan property.  In _Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing_ , STOC ’14, 2014.
  * Mossel et al. (2015) Elchanan Mossel, Joe Neeman, and Allan Sly.  Reconstruction and estimation in the planted partition model.  _Probability Theory and Related Fields_ , 2015.
  * Mossel et al. (2018) Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  _Combinatorica_ , 2018.
  * Newman (2013) Mark EJ Newman.  Spectral methods for community detection and graph partitioning.  _Physical Review E_ , 88(4):042822, 2013.
  * Saade et al. (2014) Alaa Saade, Florent Krzakala, and Lenka Zdeborová.  Spectral clustering of graphs with the bethe hessian.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’14, 2014.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , pp. 5998–6008, 2017.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  _International Conference on Learning Representations_ , 2018.