Differentiable Task Graph Learning: Procedural Activity Representation and Online Mistake Detection from Egocentric Videos
Authors: Luigi Seminara
Giovanni Maria Farinella
Antonino Furnari
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Task Graph
Procedural Sequences
Online Mistake Detection
Video Understanding
Primary area: machine_vision
TL;DR: Differentiable learning of task graphs of procedural activities from action sequences, enabling end-to-end models with emerging video understanding capabilities, tested on online mistake action detection in procedural egocentric videos.

Abstract: Procedural activities are sequences of key-steps aimed at achieving specific goals. They are crucial to build intelligent agents able to assist users effectively. In this context, task graphs have emerged as a human-understandable representation of procedural activities, encoding a partial ordering over the key-steps. While previous works generally relied on hand-crafted procedures to extract task graphs from videos, in this paper, we propose an approach based on direct maximum likelihood optimization of edges' weights, which allows gradient-based learning of task graphs and can be naturally plugged into neural network architectures. Experiments on the CaptainCook4D dataset demonstrate the ability of our approach to predict accurate task graphs from the observation of action sequences, with an improvement of +16.7% over previous approaches. Owing to the differentiability of the proposed framework, we also introduce a feature-based approach, aiming to predict task graphs from key-step textual or video embeddings, for which we observe emerging video understanding abilities. Task graphs learned with our approach are also shown to significantly enhance online mistake detection in procedural egocentric videos, achieving notable gains of +19.8% and +7.5% on the Assembly101-O and EPIC-Tent-O datasets. Code for replicating the experiments is available at https://github.com/fpv-iplab/Differentiable-Task-Graph-Learning.

Differentiable Task Graph Learning: Procedural Activity Representation and Online Mistake Detection from Egocentric Videos
Luigi Seminara
Giovanni Maria Farinella Antonino Furnari
Department of Mathematics and Computer Science, University of Catania, Italy antonino... wtt.aaaa....uur.roaroooaaaa it
luigi.seminaran seminara@phd. unict. {giovanni. boooaann..arinellll.. a
Abstract
Procedural activities are sequences of key-steps aimed at achieving specific goals. They are crucial to build intelligent agents able assist users effectively. In this context, task graphs have emerged procedural activities, encoding a partial ordering over the key-steps. While previous works generally relied hand-crafted procedures to extract task graphs from videos, in this paper, we propose an approach based on direct maximum likelihood optimization of edges' weights, which allows gradient-based learning of task graphs and can be naturally plugged into neural network architectures. Experiments on the CaptainCook4D dataset demonstrate the ability of our approach to predict accurate task graphs from the observation of action sequences, with an improvement +16. +16.7% over previous approaches. Owing the differentiability of the proposed framework, we also introduce feature- -ased approach, aiming to predict task graphs from key-step textual video embeddings, for which observe emerging video understanding abilities. Task graphs learned with our approach are also shown significantly enhance online mistake detection procedural egocentric videos, achieving notable gains of +19.8% and +7 7.55% on the Assembly 101-O and EPIC-Tent-O datasets. Code for replicating the experiments is available https: //github. com fpv wwwppp//iifferntiabbbbb.a Task Graph Learning
wumman-understandee
representation of
Introduction
Procedural activities are fundamental for humans to organize tasks, improve efficiency, and ensuring consistency in the desired outcomes, but require time and effort to be learned and achieved effectively. This makes the design of artificial intelligent agents able assist users to correctly perform task appealing 31. Achieving these abilities requires building flexible representation of a procedure, encapsulating knowledge on the partial ordering of key-steps arising from the specific context at hand. For example, virtual assistant needs to understand that it is necessary to break eggs before mixing them that the bike's brakes need to released before removing the wheel. Importantly, for system to be scalable, this representation should be automatically learned from observations (e.g.. humans making recipe many times) rather than explicitly programmed by an expert.
Previous approaches focused on directly tackling tasks requiring procedural knowledge such as action anticipation [16 34) and mistake detection 37
15] without developing explicit representations of the procedure. Other works proposed neural models able to develop implicit
representations of the procedure by learning how to recover missing actions 43
28 discover key-
steps [1] 4 [5), or grounding them to video [10 25 A different approach 3
10 [8]
consists in
representing the structure procedure the form of a task graph, i.e., a Directed Acyclic Graph
(DAG) in which nodes represent key-steps, and directed edges impose partial ordering over key-steps,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Graph
Learned Adjacency Matrix
Training Sequencee
KG
K
KG
Get Bow!
K
Ki
positive gradients
Concet key Wie
X2
Tink Crapt Nanmium Likelnood Lons PiK,i
Kg
K1
Mixture
Pour
Mix
K
gradients
(a) Example Task Graph
(b) Task Graph Learning as Maximum Likellihood Estimation
Figure 1: (a) An example task graph encoding dependencies in "mix eggs" procedure. (b) We learn task graph which encodes partial ordering between actions (left), represented as an adjacency matrix Z (center), from input action sequences (right). The proposed Task Graph Maximum Likelihood (TGML) loss directly supervises the entries of the adjacency matrix Z generating gradients to maxi- mize the probability of edges from past nodes (K3, K1) to the current node (K2), while minimizing the probability of edges from past nodes to future nodes (K4, K₃) in a contrastive manner.
encoding dependencies between them (see Figure a Graphs provide an explicit representation which is readily interpretable by humans and easy to incorporate downstream tasks such as detecting
mistakes or validating the execution of procedure. While graphs have been historically used to
represent constraints in complex tasks and design optimal sub-tasks scheduling (38), graph-based representations mined from videos [3, key-step sequences [39] [00] or external knowledge bases [44] have only recently emerged as a powerful representation of procedural activities able to support downstream tasks such key-step recognition forecasting 3 44). Despite these efforts, current
methods rely on meticulously crafted graph mining procedures rather than setting graph generation in learning framework, limiting the inclusion of task graph representations in end-to-end systems.
In this work, we propose a novel approach to learn task graphs from demonstrations in the form of sequences of key-steps performed by real users in video while executing procedure. Given a directed graph represented as an adjacency matrix and set of key-step sequences, we provide an estimate of the likelihood of observing the set of sequences given the constraints encoded in the graph. We hence formulate task graph learning under the well-understood framework of Maximum Likelihood (ML) estimation, and propose a novel differentiable Task Graph Maximum Likelihood (TGML) loss function which can be naturally plugged into any neural-based architecture for direct optimization of task graph from data. Intuitively, our TGML loss generates positive gradients to strengthen the weights of directed edges B - when observing the < A..,,A..... B structure, while pushing down the weights of all other edges in contrastive manner (see Figure I b)). To evaluate the effectiveness of the proposed framework, we propose two approaches to task graph learning. The first approach, called "Direct Optimization (DO)". uses the proposed TGML loss to directly optimize the weights of the adjacency matrix, which constitute the only parameters of the model. The output of the optimization procedure is the learned graph. The second approach, termed Task Graph Transformer (TGT) is a feature-based model which uses a transformer encoder and a relation head to predict the adjacency matrix from either text or video key-step embeddings.
We validate the ability of our framework to learn meaningful task graphs on the CaptainCook4D dataset [30]. Comparisons with state-of-the-an approaches show superior performance of both proposed approaches on task graph generation, with boosts of up to +16.7% over prior methods. On the same dataset, we show that our feature-based approach implicitly gains video understanding abilities on two fundamental tasks [46]: pairwise ordering and future prediction. We finally assess the usefulness of the learned graph-based representation on the downstream task of online mistake detection in procedural egocentric videos. To tackle this task, we observe that procedural errors mainly arise from the execution of given key-step without the correct execution of its pre-conditions. We hence design an approach which uses the learned graph to check whether pre-conditions for the current action are satisfied, signaling a mistake when they are not, obtaining significant gains of +19.8% and +7.5% in the online mistake detection benchmark recently introduced in 13] on Assembly 101 [37 and EenC-Tent [19, showcasing the relevance and quality of the learned graph- representations.
SSee the supplementary material for more details.

---

The contributions of this work are the following: 1) We introduce a novel framework for learning task graphs from action sequences, which relies on maximum likelihood estimation to provide differentiable loss function which can be included in end-to-end models and optimized with gra- dient descent; 2) We propose two approaches to task graph learning based on direct optimization of the adjacency matrix and processing key-step text or video embeddings, which offer signifi- cant improvements over previous methods in task graph generation and shows emerging video understanding abilities; 3) We showcase the usefulness of task graphs in general, and the learned graph-based representations in particular, on the downstream task of online mistake detection from video, where we improve over competitors. The code to replicate the experiments is available at htappp////ttttttooooooooooppp/fa Task braph- Learning
2 Related Work
Procedure Understanding Previous investigations considered different tasks related to procedure understanding, such as inferring key-steps from video in an unsupervised way [45] 47 5
grounding key-steps in procedural video
25
10 27,, recognizing the performed procedure 24).
inferring key-step orderings [ 25
10
43 and procedure structure verification [28]. Recently, task
graphs, mined from video or external knowledge such WikiHow articles, have been investigated as
a powerful representation of procedures and proved advantageous for learning representations useful for downstream tasks such as key-step recognition and forecasting (4 3).
Differently from previous works 28 43 we aim to develop an explicit and human readable repre-
sentation of the procedure which can be directly plugged in to enable downstream tasks [3) rather than an implicit representation obtained with pre-training objective 44 28) As a departure from previous paradigms which carefully designed task graph construction procedures 3 44 39 20), we
frame task prediction in general learning framework, enabling models to learn task graphs directly from input sequences, and propose differentiable loss function based maximum likelihood.
Task Graph Construction A line of works investigated the construction of task graphs from natural language descriptions of procedures (e.g.. recipes) using rule-based graph parsing [36] 10]. defining probabilistic models [23), fine-tuning language models [5), or proposing learning-bast based approaches [10] involving parsers and taggers trained on text corpora of recipes 8 42). While these approaches do not require any action sequence as input, they depend on the availability of text corpora including procedural knowledge, such recipes, which often fail encapsulate the variety of ways in which the procedure may be executed BI. Other works proposed hand-crafted approaches to infer task graphs observing sequences of actions depicting task executions 20 39]. Recent work designed procedures to mine task graphs from videos and textual descriptions of key-steps [ or cross-referencing visual and textual representations from corpora of procedural text and videos 44
Differently from previous efforts, we rely on action sequences, grounded in video, rather than natural language descriptions of procedures or recipes [35] [0] and frame task graph generation learning problem, providing a differentiable objective rather than resorting to hand-designed algorithms and task extraction procedures (20 39 3 44
Despite the interest in procedural learning. mistake detection has been systematically investigated only recently. Some methods considered fully supervised scenarios which mistakes are explicitly labeled in video and mistake detection is performed offline [37 41 30 Other approaches considered weak supervision, with mistakes being labeled only at the video level [15). Finer-grade spatial and temporal annotations are exploited in [7] to build knowledge graphs, which are then leveraged to perform mistake detection. Recently, the authors of [3 proposed an online mistake detection benchmark incorporating videos from the Assembly 101
Online Mistake Detection in Procedural Videos
37 and EPIC-Tent [19] datasets, as well as PREGO, an approach to online mistake detection in procedural egocentric videos.
Rather than addressing online mistake detection with implicit representations [33 or carefully designed knowledge bases [37, we design simple approach which relies on learned explicit task graph representations. As we show in the experiments, this leads to obtain significant performance gains over previous methods, even when the predicted graphs are suboptimal, while best results are obtained with task graphs learned within the proposed framework.
3

---

3 Technical Approach
3.1 Task Graph Maximum Likelihood Learning Framework
Preliminaries Let = {Ko = S, Ki...., Kn, Kn+1 = E] be the set of key-steps involved in the procedure, where S and E are placeholder "start" and "end" key-steps denoting the start and end of the procedure. We define the task graph as a directed acyclic graph, i.c., a tuple G = (K, A, w). where K is the set of nodes (the key-steps), A = XC x i is the set of possible directed edges indicating ordering constraints between pairs of key-steps, and w : A - [o, 1] is a function assigning a score to each of the edges in A. An edge (K, K2) E A (also denoted as K; - K2) indicates that K is a pre-condition of K2 (for instance mix 7 crack egg) with score w(,,, Ky). We assume normalized weights for outgoing edges, i.e. Es w(K,, K2) IVi. We also represent the graph G as the adjacency matrix Z E [0, 1](+t))((==2) where Zig w(K,, K2). ). For ease of notation, we will denote the graph G A,w),, w) simply with its adjacency matrix Z in the rest of the paper. showing possible orderings of the key-steps KC is available, where the generic sequence y E ) is defined as set of indexes to key-steps K,, i.c., ..M.1...mm+11111... >, with yt E {O......Y n + 1}. We further assume that each sequence starts with key-step S and ends with key-step E, i.e., yo = 0 and ym++ n + F Band note that different sequences ش and yاأر have in general different lengths. Since we are interested in modeling kty-step orderings, we assume that sequences do not contain repetitions | We frame task graph learning as determining an adjacency matrix 2 such that sequences in y can seen as topological sorts of 2. A principled way to approach this problem to provide an estimate of the likelihood Z))|Z) and choose the maximum likelihood estimate 2 = arg max P()|
We assume that set of N sequences y ( 1k=1 1==
y =< yo...... 1/s..................
Modeling Sequence Likelihood for an Unweighted Graph Let us consider the special case of an unweighted graph, i.e., 2 E {0, 10 (](())))x(x33) We wish to estimate Z)y the likelihood of the generic sequence y y' given graph Z. Formally, let Y, be the random variable related to the event "key-step Ky, appears at position in sequence y". We can factorize the conditional probability P(y|Z) as:
P(ylZ) = P(Y....... Yml P(Y|Z). P(Y,
P(Y (Y....., -M- Z). (I)
We assume that the probability of observing given key-step Kg, at position t in depends on the previously observed key-steps (Ky........ Ky,), but not on their ordering. i.e., the probability of observing given key-step depends on whether its pre-conditions are satisfied, regardless of the order in which they have been satisfied. Under this assumption, we write P(Y
Yo. Z) simply as P(K Kyy, y 1...., Ky,: Z). Without loss of generality, in the following, we denote the current key-step as K; = Ky, the indexes of key-steps observed at time I as J = O(y, 1) (,t- ). and the corresponding set of observed key-steps as K2 {K,li J.. Similarly, we define J == - t) {0, ..... n + 1) \ tl,,t) and K5 the sets of indexes and corresponding key- steps unobserved at position f, i.e., those which do not appear before yt in the sequence. Given the factorization above, we are hence interested in estimating the general term P(K,,
Kyn)
P). We can estimate the probability of observing key-step K; given the set of observed key- steps Ky and the constraints imposed by 2. following Laplace's 's classic definition of probability (26) as "the ratio of the number of favorable cases to the number of possible cases". Specifically, if we
were to randomly sample key-step from K. following the constraints of Z. and having observed key-steps Kj, sampling K; would be favorable case if all pre-conditions of K; were satisfied, i.c.,
if Ejer Zij = (there are no pre-conditions in unobserved key-steps Kz). Similarly, sampling a key-steps K₂ is a "possible case" if ΣSer Znj = O. We can hence define the probability of observing key-step K; after observing all key-steps K2 in a sequence as follows:
number of favorable cases
I(EjE3 Zzz 0)
P(K,KK,, Z) number of possible cases ENED I(EjeS Zmz= = 0)
(2)
where 1(-) denotes the indicator function, and in the denominator, we are counting the number of key-steps that have not appeared yet are "possible cases" under the given graph Z. Likelihood P(rlZ)
can be obtained by plugging Eq. (2) into Eq. (I]
In practice, we prepend/append S and E to each sequence.
'Since sequences may in practice contain repetitions, we map each sequence containing repetitions to multiple sequences with repetitions (e.g., ABCAD
BCA)).

---

can Observed sequence
Graph
Adjacency Matrix "
C
Goal: Estimate
Observed Key-steps
P(K S,SSAA,, B,D. C.E.S. 2)) P(S PLA S P,
A
0.7
0
0.1
0.1-
6.1
0
B
0.05
0
0.4
0.1
0
Fensbiitty
PLE.S.A.,,D,CCEE..
C
0.7
0.2
0:05
0.05
0.95
Example: estimate
9.05
6.1
0.35
0.55
P(D 2)
C
0
0:05
0:05
0.05
0.1
Observed
Future
P(D 8, A, B,
RORAB 22 U..)
K.D.A.
1.8
0.31
Figure 2: Given a sequence < S.A.B.D.CEE,. and a graph G with adjacency matrix Z. our goal is to estimate the likelihood P(< S,A, >> (Z). which can be done by factorizing the expression into simpler terms. The figure shows an example of computation P(DIS, A, B, Z) as the ratio of the "feasibility of sampling key-step D, having observed key-steps S, A, and B" to the sum of all feasibility scores for unobserved symbols. Feasibility values are computed by summing weights of edges D + X for all observed key-steps X.
probability
To enable gradicnt- based learning, we consider the general case of continuous adjacency matrix Z [0, (mx++))x(++2), We generalize the concept of "possible cases" discussed in the previous section with the concept of "feasibility of sampling a given key-step K,, having observed a set key-steps K5, given graph Z", which we define the sum of all weights of edges between observed key-steps K and K;; f(Ks|K, Z) Σjeソ Zij- Intuitively, key-step k; has many satisfied pre-conditions, we are more likely to sample as the next key-step. We hence define P(Kg Z) as "the ratio the feasibility of sampling K; to the sum of the feasibilities of sampling any unobserved key-step""
Modeling Sequence Likelihood for a Weighted Graph
J(K, Z)
ΣJEs Zig
P(K, 7)
f(K
ΣnE Ejer Zhj
Figure 2 illustrrates the computation of the likelihood in Eq. (3) Plugging Eq. 3 into Eq. ① estimate the likelihood of a sequence y given graph as:
lvl
EsEo(y)) Zuo
= P(SIZ)=((SII)
II
P(K 9. | (o( 2) = II
(4)
Enedly Ejeo(H)) Zng
1=1
t=1
Where we set P(K 12) = P(S as sequences always start with the start node
Task Graph Maximum Likelihood Loss Function Assuming that sequences y( E y are indepen- dent and identically distributed, we define the likelihood of ) given graph Z as follows:
D
D by (*)
Ejeong() Zyri
P( = II
(
18) 2)
II II
(5)
EnEO(y Ejeo( Znj
1=1
k=1 t=1
We can find the optimal graph by maximizing the likelihood in Eq. 5 which is equivalent to minimizing the negative ligeliidd - log P(Y, Z), leading to formulating the following loss:
M (0)
2(,
Σ
Σ
(log Σ Znu - B log Σ Znd
(6)
(M .t)
(ED (*)
where / is hyper-parameter We refer to Eq. O6) the Task Graph Maximum Likelihood (TGML) loss function. Since Eq. (6) differentiable with respect to all Zi values, we can learn the adjacency matrix Z by minimizing the loss with gradient descent to find the estimated graph Z = argz max L(), Z). Eq. O works contrastive loss in which the first logarithmic term aims
5

---

Teee End Tie byy
He 9.80 8..0
(ee Am
lerss Feet
Encodar
LSTE
00
Figure 3: Our Task Graph Transformer (TGT) takes as input either D D-dimensional text embeddings extracted from key-step names or video embeddings extracted from key-step segments. In both cases, we extract features with pre-trained EgoV model. For video embeddings, multiple embeddings can refer to the same action, so we randomly select one for each key-step (RS blocks). Learnable start (S) and end (E) embeddings are also included. Key-step embeddings are processed using transformer encoder and regularized with a distinctiveness cross-entropy to prevent representation collapse. The output embeddings are processed by our relation head, which concatenates vectors across all (n +2) possible node pairs, producing (n + 2) x (n + 2) x 2D relation vectors. These vectors are then processed by relation transformer, which progressively maps them an (n+22 2) x (n + 2) adjacency matrix. The model is supervised with input sequences using our proposed Task Graph Maximum Likelihood (TGML) loss.
to maximize, every step of each imput sequence, the weights Z of edges Ky, + K, going from the current key-step Ky, to all previously observed key-steps Ky. while the second logarithmic term (contrastive term) aims minimize the weights of edges K₁, + K2 between key-steps yet to appear K₁, and already observed key-steps Kj. The hyper-parameter, 3 regulates the influence of the summation in the contrastive term which, including many more addends, can dominate gradient updates. As in other contrastive learning frameworks [29 33), our approach only includes positives and negatives and it does explicitly consider anchor examples.
3.2 Models
Direct Optimization (DO) The first model aims to directly optimize the parameters of the adjacency matrix by performing gradient descent on the TGML loss (Eq. (6)). We define the parameters of this model an edge scoring matrix A (1++2)x(++2) where n is the number of key-steps, plus the placeholder start (S) and end (F) nodes, and A,j is a score assigned to edge K; + Kj- To prevent the model from learning edge weights eluding the assumptions of directed acyclic graphs, we mask black cells in Figure 2 with -o. To constrain the elements of Z in the [0, 1] range and obtain normalized weights, we sormmax-normalize the rows of the scoring matrix obtain the adjacency matrix Z = so tmax((A) Note that elements masked with -o will be automatically mapped to by the softmax function similarly to 40). We train this model by performing batch gradient descent directly on the score matrix A with the proposed TGML loss. We train a separate model per procedure, as each procedure associated a different task graph. As many applications require an unweighted graph, we binarize the adjacency matrix with the threshold n. where is the number of nodes. We also employ post-processing stage which we remove redundant edges, loops, and add obvious missing connections to S and F. nodes
Task Graph Transformer (TGT) Figure illustrates the proposed model, which termed Task Graph Transformer (TGT). The proposed model can take as input either D-dimensional embeddings of textual descriptions of key-steps or D-dimensional video embeddings of key-step segments extracted from video. In the first case, the model takes as input the same set of embeddings at each forward pass, while in the second case, at each forward pass, we randomly sample a video embedding per key-step from the training videos (hence each key-step embedding can be sampled from different video). We also include two D-dimensional learnable embeddings for the S and nodes. All key-step embeddings are processed by transformer encoder, which outputs D-dimensional vectors enriched with information from other embeddings. To prevent representation collapse, we apply a regularization loss encouraging distinctiveness between pairs of different nodes. Let X be the matrix of embeddings produced by the transformer model. We L2 n-oommaalize features, then compute
See the supplementary material for more details.

---

Table 1: Task graph generation results CaptainCook4D. Best results are in bold, second best results are underlined, best results among competitors are highlighted. Confi- dence interval bounds computed at 90% conf. for runs.
We compare the abilities of our TGT model trained on visual features to generalize two fundamental video understanding tasks, i.e., pairwise order- ing and future prediction. Despite not being explicitly trained for these tasks, our model exhibits video understanding abilities, surpassing the baseline.
Table 2:
Method
Precision
Recall
Fi
MSGI 39
11.9
14.0
12.8
LLM
52.9
57.4
55.0
Count-Based 3
66.7
55.6
60.6
Method
Ordering
Fut. Pred.
MSG² 20
70.9
71.6
71.1
TGT-text (Ours)
79.9
18.8
81.9 16.9
80.8
Random
50.0
50.0
DO (Ours)
86.4 11.5
89.7 111.5
87.8 11.5
TGT-video
77.3
74.3
Improvement
+15.5
+18.1
+16.7
Improvement
+27.3
+24.3
exp(T) exxxx) as in [33 To prevent the transformer encoder from mapping distinct key-step embeddings to similar representations, we enforce the values outside the diagonal of Y to be smaller than the values in the diagonal. This is done by encouraging each row of the matrix Y to be close to a one-hot vector with cross-entropy loss. Regularized embeddings are finally passed through relation transformer head which considers possible pairs of embeddings and concatenates them in (n + 2) x (n + 2) x 2D matrix It of relation vectors. For instance, Ri (i,, the concatenation of vectors X [i] and X [J] Relation vectors are passed to a transformer layer which aims to mine relationships among relation vectors, followed by multilayer perceptron to reduce dimensionality to 16 units and another pair of transformer layer and multilayer perceptron to map relation vectors to scalar values, which are reshaped to size (n + 2) x (n + 2) to form the score matrix We hence apply the same optimization procedure as the DO method to supervise the whole architecture.
pairwise cosine similarities Y = X XT
Experiments and Results
4.1 Graph Generation
Problem Setup We evaluate the ability of our approach to learn task graph representations CaptainCook4D [30], a dataset of egocentric videos of 24 cooking procedures performed by volunteers. Each procedure is accompanied by task graph describing key-steps constraints. We tackle task graph generation as a weakly supervised learning problem which models have to generate valid graphs by only observing labeled action sequences (weak supervision) rather than relying on task graph annotations (strong supervision), which are not available at training time. All models trained on videos that free from ordering errors missing steps to provide likely representation of procedures. We use the two proposed methods in the previous section to learn 24 task graph models, per procedure, and report average performance across procedures.
Compared Approaches We compare our methods with previous approaches to task graph generation, and in particular with MSGI [39] and MSG 220] which are approaches for task graph generation based on Inductive Logic Programming (ILP). We also consider the recent approach proposed which generates graph by counting co-occurrences of matched video segments. Since we assume labeled actions to be available at training time, we do not perform video matching and use ground truth segment matching provided by the annotations. This approach is referred to "Count-Based" Given the popularity of large language models as reasoning modules, we also consider a baseline which uses a large language mode to generate task graph from key-step descriptions, without any We refer to this model as "LLM"..
access to key-step sequences! @
Graph Generation Results Results in Table I highhlght the complexity of the task, with classic approaches based on inductive logic, such as MSGI, achieving poor performance (12.8 F1), language models and count-based statistics reconstructing only basic elements of the graph (55.0 and 60.6 Fi for LLM and Count- respectively). and even more recent methods based on inductive logic and heuristics only partially predicting the graph (71.1 F of MSG2). The proposed Direct Optimization
We base experiments ChatGPT (I].

---

(DO) approach outperforms all other methods, achieving the highest scores across all measures, with improvements in the [+15.5, +18.1] range with respect to the best competitor MSG². This result highlights the effectiveness of the proposed framework to learn task graph representations from key-step sequences, especially considering the simplicity of the DO method, which performs gradient descent directly on the adjacency matrix. We obtain a slightly higher recall as compared to the precision (89.7 7 vs 86.4), showing that our approach tends to retrieve most ground truth edges, while hallucinating some pre-conditions, probably due to the dataset being unbalanced towards the most common ways of completing a procedure. Second best results are consistently obtained by our ceature-based TGT approach, showing the generality of our learning framework and the potential of integrating it into complex neural architectures. Tight confidence intervals for DO highlight the stability of the proposed loss. The lower performance of TGT, as compared to DO, may be due to the relatively small size of the dataset, which makes it hard for complex architecture to generalize.
Video Understanding Results Table Tableerrepe reports the performance of TGT trained on videos on two fundamental video understanding tasks [46] of pairwise clip ordering and future prediction g For pairwise ordering, we feed our TGT model with video embeddings of two clips and sort them according to the predicted adjacency matrix, placing first the clip identified as a pre-condition. For future predictions, given an anchor clip, we have choose which among two other clips is the correct future. Despite TGT not being explicitly trained for pairwise ordering and future predictions, exhibits emerging video understanding abilities, surpassing the random baseline.
4.2
Online Mistake Detection
Problem Setup We follow the PREGO benchmark and used the datasets (A (Assembly 101-0 and EPIC- Tent-O) recently proposed in [13. in which models are tasked to perform online action detection from procedural egocentric videos. To evaluate the usefulness of task graphs on this downstream task, design a system which flags the current action as mistake if its pre-conditions in the predicted graph do not appear in previously observed actions. G
Competitors We compare our approach with respect to the PREGO model proposed in [3. which detects mistakes based on the comparison between the currently observed action and an action predicted by forecasting module. We note that PREGO is based an implicit representation of the procedure (the forecasting module), while our approach is based on the explicit task graph representation, learned with the proposed framework. We also compare our approach with respect to baselines based on all graph prediction approaches compared in Table to assess how the ability to predict accurate graphs affects downstream performance. For all methods, we report results based on ground truth action segments and on action sequences predicted by a MiniRoad 2 instance, a state-of-the-arr online action detection module trained on each target dataset.
Results Results in Table 3 highlight the usefulness of the learned task graphs for downstream applications. The proposed DO method achieves significant gains over prior art with improvements of +19.8 and +7.5 in average Fi score on Assembly 101-O and EPIC-Tent-O respectively when ground truth action sequences are considered to make predictions. While TGT is the second-best performer on Assembly 101-O, it obtains best results on EPIC-Tent-O O (64.1 vs 58.3 in average F, score). This is due to the nature of action annotations in the two datasets. Indeed, while key-step names are informative in EPIC-Tent (e.g., "Place Vent Cover", "Open Stake Bag". , or "Spread Tent"), "screw chassis").
they are less distinctive in Assembly 101 (e.g.. "attach cabin". "attach interior", This highlights the flexibility of the proposed learning framework which can work in purely abstract, symbolic settings, with the DO approach, but can also leverage semantics with TGT when beneficial. Interestingly, the second best performers are graph-based approaches, with M SG2 achieving an average Fi of 56.1 on Assembly101-O and the simple Count-Based approach obtaining an average Fi score of 56.6 on EPIC-Tent-O O. In contrast, PREGO obtains average F1 scores of 39.4 and 32. on Assembly101-6 and EPIC-Tent-C respectively, suggesting the potential of explicit graph-based representations for mistake detection, versus the implicit one of PREGO. Breaking down performance into correct and mistake F, scores reveal some degree of unbalance of our approaches and the main competitor MSG² towards identifying correct actions rather than mistakes. This suggests that the related graph-based representations tend to detect some spurious pre-conditions, probably due to the limited demonstrations included in the videos, while the implicit PREGO model exhibits skew with respect to mistakes. Further breaking down F1 scores into related precision and recall values
Seee the supplementary material for more details.
8

---

Table Online mistake detection results, Results obtained with ground truth action sequences are denoted with while results obtained on predicted action sequences are denoted with +
Assembly101-O
EPIC-Tent-O
Avg
Correct
Mistake
Avg
Correct
Mistake
Method
Fi
Fi
Pres
Rec
F
Prec
Rec
Fi
Fi
Prec
Roc
Fi
Prec
Rec
Bount-Basede
3
26.0
9.2
488
X5.7
42.8
97.8
27.4
56.6
92.5
92.8
92.2
20.7
20.0
21.4
LLM"
29.3
15.1
8.3
87.2
43.4
96.7
27.9
47.7
86.3
82.4
90.6
9.1
13.3
6.9
MSGI
39
33.1
22.7
13.1
43.5
93.4
28.3
44.5
66.9
22.0
PREGO
13
39.4
32.6
89.7
19.9
46.3
30.7
94.0
32.1
45.0
95.7
29.4
19.1
10.7
86.7
MSG
20
56.1
63.9
$1.5
84.2
48.2
73.6
35.8
54.1
92.9
94.1
91.7
15.4
13.3
18.2
TGT-texi (Ours)
62.8
69.8
56.8
90.6
55.7
84.1
41.7
64.1
93.8
94,1
93.5
34.5
33.3
35.7
DO (Ours)'
75.9
90.2
98.2
61.6
46.7
58.3
93.5
23.11
Improvement
+19.8
+26.3
+13.4
+7.5
+0,9
+12.5
Count-Based
23.2
2.6
43,9
40.4
59.2
21.6
LLM
28.
15.1
7.8
65.5
42.3
89.5
27.7
35.9
61.6
46.7
90.4
10.2
.4.00
5.8
MSGI+
39
28.4
14.0
7.8
67.9
42.7
90.7
28.0
40.4
59,2
42.9
95.5
21.6
80.0
12.5
PREGO
13
32.5
23.1
13.9
41.8
27.8
29.4
41.6
17.2
MSG
20
46.2
59.1
51.2
70.0
33.2
44.5
26.5
45.2
67.5
52.4
95.1
22.9
73.3
13.6
TGT-text (Ours)+
53.0
67.8
62.3
74.5
38.2
46.2
32.6
43.8
69.5
55.8
92.1
18.2
53.3
11.0
DO (Ours)+
53.5
78.9
85.0
73.5
28.1
22.5
37.3
46.5
69.3
$4.4
95.2
23.7
73.3
14.1
Improvement*
+7.3
+1..8
-5.7
+1.3
+1.2
+1.2
highlights that the main failure modes are due to large imbalances between precision and recall. For instance, the Count-Ban Based method achieves precision of only 4.8 with a recall of 85.7 in predicting correct segments on Assembly 101-O. In contrast, the proposed approach obtains balanced precision and recall values in detecting correct segments in Assembly 101-O (98. 2/83.4) and EPIC-Tent-O (94.1/93.5), and detecting mistakes in EPIC-Tent-O (33.3/35.7), while the prediction of mistakes on Assembly101 101mmlly011- is more skewed (46.7/90.4). Results based on action sequences predicted from video (bottom part of Table 3 highlight the challenging nature of the task when considering noisy action sequences (see Figure 4). While the explicit task graph representation may not accurately reflect the predicted noisy action sequences, we still observe improvements over previous approaches of +7.3 and +1.3 in average Fi score in Assembly 101-O and competitors are still graph-baser methods, such as MSG and the Count- Based approach, with significant improvements over the implicit representation of the PREGO model (32.5 average Fi versus 53.5 5 of the proposed DO model). Also, in this case, we observe that wraph-based methods tend to be skewed towards detecting correct action sequences. In this regard, our TGT model only achieves 38.2 in mistake F1 score, drop in 5.7 points over the best performer, the Count-Base Based method, which, on the other hand, only achieves Fj score of 2.6 when predicting correct segments.
Remarkably, best
Limitations
The proposed approach requires the availability of key-step sequences, common assumption of works addressing other video understanding tasks 6 22 19 18] While our method is applicable any fully supervised video understanding dataset, future works should focus on overcoming such limitation and taking advantage of the vast amount of unlaheled video and textual data sets. While the proposed TGT method has shown promising results when trained directly on video features, the investigation of task graph learning in the absence of labeled key-step sequences is beyond the scope of this paper. We noted reduced ability of our approach work with noisy action sequences and tendency to hallucinate pre-conditions, likely due to the limited expressivity of key-step sequences arising from videos showing the most common ways perform a procedure. The performance of our designed system to detect mistakes is influenced by the quality of action recognition (see Figure 4). If the action recognition module fails to detect an action, the method may incorrectly signal missing pre-condition. Conversely, if an action is falsely detected as performed, the method may fail to signal an actual mistake. Future improvements in online action recognition will enhance the robustness of our method. Furthermore, approach does not explicitly model "optional"

---

Cend
1.0
T0AB
4201
Figure 4: To further investigate the effect of noise, we conducted an analysis based on the controlled perturbation of ground truth action sequences, with the aim simulate noise in the action detection process. At inference, we perturbed each key-step with a probability a (the "perturbation rate"), with three kinds of perturbations: insert (inserting a key-step with random action class), delete (deleting a key-step), or replace (randomly changing the class of a key-step). The plots show the trend of the Fl score (Average, Correct, and Mistake) the perturbation rate increases in the case of Assembly 101-O (left) and EPIC-Tent-O (right). Results suggest that the proposed approach can still bring benefits even in the presence of imperfect action detections, with the average F1 score dropping down 10 15 points with moderate noise level of 20%.
key-steps, which can lead to incorrect error signaling if optional steps treated as mandatory. This issue could potentially be addressed through the integration of specialized modules capable of detecting optional nodes. Another limitation of task graph representations, both in this work and in
prior approaches (3] 44
39 20], their inability to explicitly model repeatable key-steps. Recent
18 have introduced "repeatable" node attribute task graphs, but this extension is based on manual annotations, and the automatic learning of such attributes from data remains an open problem. Despite this limitation, the proposed error detection model demonstrates an ability to handle cases where key-steps may recur (e.g.. spreading peanut butter). At test time, pre-conditions of key-steps are verified via the predicted task graph, earlier in the sequence. Nevertheless, more effective modeling of repeatable key-steps, especially in contexts where specific repetitions are required (e.g., "cut three slices of bread"), remains an important area for future research. Future work should explore methods for incorporating these requirements into task graph learning frameworks. Our method follows the setup of PREGO [K], which defines the Assembly 101-O and EPIC-Tent-O datasets as curated versions of their originals to account for open-set procedural errors such as "order", "omission", "correction", and "repetition" mistakes. These are procedural mistakes, as distinguished from "proficiency errors" described in prior works [18. The proposed method focuses on procedural mistakes the abstract level of executed actions, and thus, would not be directly applicable to proficiency error detection. In real-world systems, this limitation could be mitigated by integrating subsystems that specialize in detecting different types of errors. Developing an integrated approach that addresses both procedural and proficiency errors is a promising direction for future research.
advancements such
if key-step has appeared
Conclusion
We considered the problem of learning task graph representations of procedures from video demon- strations. Framing task graph learning as maximum likelihood estimation problem, we pro- posed differentiable loss which allows direct optimization of the adjacency matrix through gradient descent and can be plugged into more complex neural network architectures. Exper- iments on three datasets show that the proposed approach can learn accurate task graphs, de- velop video understanding abilities, and improve the downstream task of online mistake detec- tion surpassing state of the art methods. We release our code at the following URI:: hhtpps //github. thub. httpp-ppppb/iifeeeiiiaabb... Task- Graph-Learms
10

---

7 Acknowledgments
This research is supported in part by the PNRR PhD scholarship "Digital Innovation: Models, Systems and Applications" DM 118/2023, by the project Future Artificial Intelligence Research (FAIR) PNRR MUR Cod. PE0000013- CUP: E63C2200944006, and by the Research Program PIAno di inCEntivi per la Ricerca di Ateneo 2020/2022 Linea di Intervento 3 "Starting Grant" EVIPORES Project University of Catania.
We thank the authors of [13] and particular Alessandro Flaborea and Guido D' D'Amely for sharing the code to replicate experiments in the PREGO benchmark.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Lconi Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[2] Joungbin An, Hyolim Kang, Su Ho Han, Ming-Hsuan Yang. and Seon Joo Kim. Miniroad: Minimal mn framework for online action detection. In Proceedings the IEEF/CVF International Conference on Computer Vision, pages 10341-10350, 2023.
[3] Kumar Ashutosh, Santhosh Kumar Ramakrishnan, Triantafyllos Afouras, and Kristen Grauman. Vidco- mined task graphs for keystep recognition instructional videos. Advances in Neural Information Processing Systems, 36, 2024.
[4] Siddhant Bansal, Chetan Arora, and CV Jawahar. My view is best view: Procedure learning from egocentric videos. In European Conference on Computer Vision, pages 657-675. Springer, 2022.
[5] Siddhant Bansal, Chetan Arora, and CV Jawahar. United we stand, divided we fall: Unitygraph for unsupervised procedure learning from videos. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 6509-6519, 2024.
[6] Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem, and Juan Carlos Niebles. Activitynet: A large-scale video benchmark for human activity understanding. In Proceedings of the ieee conference on computer vision and pattern recognition, pages 961-970, 2015.
[7] Guodong Ding, Fadime Sener, Shugao Ma, and Angela Yao. Every mistake counts in assembly. arXiv preprint a3X14:2307.16453, 2023.
[8] Lucia Donatelli, Theresa Schmidt, Debanjali Biswas, Arne Köhn, Fangzhou Zhai, and Alexander Koller. Aligning actions across recipe graphs. In Proceedings of the 2021 conference on empirical methods in natural language processing, pages 6930-6942, 2021.
[9] Mikita Dvornik. Isma Hadji. Konstantinos G Derpanis, Animesh Garg, and Allan Jepson. Drop-dtw: Aligning common signal between sequences while dropping outliers. Advances Neural Information Processing Systems, 34: 14:11782-13399, 2021.
[10] Nikita Dvoriik, Isma Hadji, Hai Pham, Dhaivat Bhatt, Brais Martinez, Afsanch Fazly, and Allan Jepson. Graph2vid: Flow graph to video grounding for weakly- seakly-sueeriieed multi-step localization. In Proceedings of the European Conference Computer Vision (ECCV), 2022.
[11] Nikita Dvomik, Isma Hadji, Ran Zhang, Konstantinos G Derpanis, Richard P Wildes, and Allan D Jepson. Stepformer: Self-supervised step discovery and localization in instructional videos. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages
2023.
[12] Ehsan Elhamifar and Dat Huynh. Self-supervised multi-task procedure learning from instructional videos. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVII 16, pages 557-573. Springer, 2020.
[13] Alessandro Flaborea, Guido Maria D' Amely di Melendugno, Leonardo Plini, Luca Scofano, Edoardo Matteis, Antonino Furnari, Giovanni Maria Farinella, and Fabio Galasso. Prego: online mistake detection in procedural egocentric videos. In International Conference on Computer Vision and Patter Recognition (CVPR), 2024.
[14] Antonino Furnari and Giovanni Maria Farinella. Rolling-une unrolling Istms for action anticipation from first- pestoperson video. IEEE transactions on pattern analysis and machine intelligence, 43(11):4021 4036. 2020.

---

[15] Reza Ghoddoosian, 1sht Dwivedi, Nakul Agarwal, and Behzad Dariush. mentation and unseen error detection in anomalous instructional videos. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10128-10138, 2023.
action seg-
[16] Rohit Girdhar and Kristen Grauman. Anticipative video transformer. In Proceedings of the IEEE/CVF international conference computer vision, pages 13505-13515, 2021.
[17] Kristen Grauman, Andrew Westhury, Eugene Byre, Zachary Chavis, Antonino Furnari, Rohit Girdhar, Jackson Hamburger, Hao Jiang, Miao Liu, Xingyu Liu, et al. Ego4d: Around the world in 3,000 hours of egocentric video. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 18955-19012, 2022.
[18] Kristen Grauman, Andrew Westbury, Lorenzo Torresani, Kris Kitani, Jitendra Malik, Triantafyllos Afouras, Kumar Ashutosh, Vijay Baiyya, Siddhant Bansal, Bikram Boote, et al. Ego-exo4d: Understanding skilled human activity from first-and third-person perspectives. arXiv preprint arXiv:2311.18259 2023.
[19] Youngkyoon Jang, Brian Sullivan, Casimir Ludwig, lain Gilchrist, Dima Damen, and Walterio Mayol- Cuevas. Epic-tent: An egocentric video dataset for camping tent assembly. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 0- 0, 2019.
[20] Yunseok Jang, Sungryull Sohn, Lajanugen Logeswaran, Tiange Luo, Moontae Lee, and Honglak Lee. Multimodal subtask graph generation from instructional videos. arXiv preprint arX6v:2302.08667, 2023,
[21] Takeo Kanade and Martial Hebert. First-person vision. Proceedings of the IEEE, 100(6))2442-245555 2012.
[22] Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al. The kinetics human action video dataset. arXiv preprint xxXiv:1705.06900 2017.
[23] Chloé Kiddon, Ganesa Thandavam Ponnuraj, Luke Zettlemoyer, and Yejin Choi. Mise place: Unsuper- vised interpretation of instructional recipes. Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 0922,92,22 2015.
[24] Xudong Lin, Fabio Petroni, Gedas Bertasius, Marcus Rohrbach, Shih-Fu Chang, and Lorenzo Torresani. Learning to recognize procedural activities with distant supervision. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13853-13863, 2022.
[25] Zijia Lu and Ehsan Elhamifar. Set-supervised action learning in procedural task videos via pairwise order consistency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 19903-19913 2022.
[26] Pierre Simon Marquis de Laplace. Théorie analytique des probabilités, volume 7. Courcier, 1820.
[27] Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisserman. End-to-end learning of visual representations from uncurated instructional videos. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9879-9888 9889, 2020.
[28] Medhini Narasimhan, Licheng Yu, Sean Bell, Ning Zhang, and Trevor Darrell. Learning and verification of task structure in instructional videos. arXiv preprint arXiv:2303.1 13519, 2023.
[29] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint 1xXiv:8807003444 2018.
[30] Rohith Peddi, Shivvrat Arya, Bharath Challa, Likhitha Pallapothula, Akshay Vyas, Jikai Wang, Qifan Zhang, Vasundhara Komaragiri, Eric Ragan, Nicholas Ruozzi, et al. Captaincook44: dataset for understanding errors in procedural activities. arXiv preprini 23Xi:2312214556: 2023.
[31] Chiara Plizzari, Gabriele Goletto, Antonino Furnari, Siddhant Bansal, Francesco Ragusa, Giovanni Maria Farinella, Dima Damen, and Tatiana Tommasi, An outlook into the future of egocentric vision. International Journal fn Computer Vision, 2023.
[32] Shraman Pramanick, Yale Song, Sayan Nag, Kevin Qinghong Lin, Hardik Shah, Mike Zheng Shou, Rama Chellappa, and Pengchuan Zhang. Egovipy2: Egocentric video- Iano-lang pre-training with fusion in the backbone, In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5285-520 1185-5297,050 2023.
[33] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748 8763. PMLR, 2021.
12

---

[34] Debaditya Roy, Ramanathan Rajendiran, and Basura Fernando. Interaction region visual transformer for egocentric action anticipation. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 6740-6750, 2024.
[35] Keisuke Sakaguchi, Chandra Bhagavatula. Ronan Le Bras, Niket Tandon, Peter Clark, and Yejin Choi. proScript: Partially ordered scripts generation.
Marie-Francine Moens. Xuanjing Huang. Lucia Specia, and Scott Wen-tau Yih, editors, Findings of the Association for Computational Linguistics: EMNLP 2021. pages 2138-2149, Punta Cana, Dominican Republic, November 2021, Association for Computational Linguisties.
[36] Pol Schumacher, Mirjam Minor, Kirstin Walter, and Ralph Bergmann. Extraction of procedural knowl- edge from the web: A comparison of two workflow extraction approaches. In Proceedings of the 2 International Conference on World Wide Web, pages 739-747, 2012.
[37] Fadime Sener, Dibyadip Chatterjee, Daniel Shelepov, Kun He, Dipika Singhania, Robert Wang. and Angela Yao. Assembly101: large-scale multi-view video datasct for understanding procedural activities. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 21096-
21106, 2022.
[38] Steven S Skiena. The algorithm design manual, volume Springer, 1998.
[39] Sungryull Sohn, Hyunjae Woo, Jongwook Choi, Honglak Lee. Meta reinforcement learning with autonomous inference subtask dependencies. arXiv preprint wrXiv:2001.00244 2020.
[40] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[41] Xin Wang, Tacin Kwon, Mahdi Rad, Bowen Pan, Ishani Chakraborty, Sean Andrist, Dan Bohus, Ashley Feniello, Bugra Tekin, Felipe Vieira Frujeri, et al. Holoassist: an egocentric human interaction dataset for interactive ai assistants in the real world. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 20270-20281, 2023.
[42] Yoko Yamakata, Shinsuke Mori, and John A Carroll. English recipe flow graph corpus. In Proceedings of the Twelfth Language Resources and Evaluation Conference, pages 5187-5194, 2020.
[43] Yiwu Zhong, Licheng Yu, Yang Bai, Shangwen Li, Xucting Yan, and Yin Li. Learnnng procedure- video representation from instructional videos and their narrations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14825-14835. 2023.
[44] Honglu Zhou, Roberto Martin Martin-Martin, Mubbasir Kapadia, Silvio Savarese, and Juan Carlos Niebles. Procedure-aware pretraining instructional video understanding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10727-10738. 2023.
[45] Luowei Zhou, Chenliang Xu, and Jason Corso. Towards automatic learning of procedures from web instructional videos. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[46] Yipin Zhou and Tamara Berg. Temporal perception and prediction ego-centric video. Proceedings of the IEEE International Conference on Computer Vision, pages 4498-4506, 2015.
[47] Dimitri Zhukow, Jean- nan-Baapistt Alayrac, Ramazan Gokberk Cinbis, David Fouhey, Ivan Laptev, and Josef Sivic. Cross-task weakly supervised learning from instructional videos. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 3537 3545, 2019.
13

---

Get a Bowl
Add Water
Add Milk
Crack Egg
Mix Eggs
Pour Mixture
Figure 5: Example of a task graph where each node represents key-step in the procedure, with directed edges indicating the necessary preconditions for each step.
A
Task Graph
An example of task graph is illustrated in Figure task graph is Directed Acyelic Graph (DAG) where nodes represent key-steps and directed edges impose a partial order on these steps, indicating the necessary preconditions for each node. For example, the key-step "Mix" has preconditions such as "Add Water", "Add Milk", and "Crack Egg". This formulation task graphs is not a novel contribution of this paper but was originally introduced in (18).
B Evaluation Measures
This appendix details the evaluation measures used to assess performance experimentally for the two considered tasks of task graph generation and online mistake detection.
Task Graph Generation Task graph generation is evaluated by comparing generated graph G = (K,, A) with ground truth graph G (K.. Since task graphs aim encode ordering constraints between pairs of nodes, we evaluate task graph generation as the problem of identifying valid pre-conditions (hence valid graph edges) among possible ones. We hence adopt classic detection evaluation measures such precision, recall, and Fi score. In this context, we define True Positives (TP) as edges included in both the predicted and ground truth graph (Eq. (7)), False Positives (FP) all edges included in the predicted graph, but not in the ground truth graph (Eq. (8). and False Negatives (FN) as all edges included in the ground truth graph, but not the predicted one (Eq. Note that true negatives not required to compute precision, recall and Fi score.
TP=AnA
(7)
=P=AA FP=AAA
(8)
FN = A
(9)
Online Mistake Detection follow previous works on mistake detection from procedural
egocentric videos 337 13 and evaluate online mistake detection with standard precision, recall, and F, scores. We break down metries by the "correct" and "mistake" classes, as well as report average values.
14

---

C Implementation Details
This appendix provides implementation details to replicate the experiments discussed in Section
C.1 Data Augmentation
In procedural tasks, it is common for certain actions to be repeated multiple times throughout the execution of task. For example, in the EPIC-Tent dataset [19], an operation such as "reading the instructions" may be performed repeatedly at any point during the task. To model key-step orderings within the framework of topological sorts, our approach assumes that sequences should not contain such repetitions. Since repetitions denote that specific action can appear at different stages of procedure, we expand each sequence with repetitions to all distinct sequences obtained by dropping repeated actions. This data augmentation strategy enhances the robustness our model on Assembly 101 [37] and EPIC-Tent [19], while it was not necessary for the CaptainCook4D dataset (30,, as sequences do not contain any repetitions.
C.2
Early Stopping
The learning process was conducted without the use of a validation set. To avoid overfitting and saving computation we defined a "Sequence Accuracy (SA)" score used to determine when the model reaches learning plateau. We early stop models when an SA value at least 0.95 is reached, and the model shows no SA improvement for 25 consecutive epochs. The SA score is follows:
1
1 SA
Σ yEY
Σ T=
c(ui, ul: i), pred(v))
(10)
V
y
where y defined sequences in the training set, y is a sequence from V. yi is the i-th element of sequence y. y|: are the predecessors of the i-th element in the sequence y, and pred(y:, Z) are the predicted predecessors for y: from the current binarized adjacency matrix Z. The function c is defined
if yl: i] 0 and |pred 2) =
clyi, ul: i), pred(y: Z)) =
Iula]) v.. ppredly.22 2)] | a]] > O and [pred Z) > 0
(11)
otherwise
The SA score measures the compatibility of each sequence with the current task graph based on the ratio correctly predicted predecessors of the current symbol yı of the sequence the total number of predicted predecessors for y/: in the current task graph.
C.3 Hyperparameters
Table 4 details the hyperparameters employed in the experiments for task graph generation on the CaptainCook4D dataset 30). During the training of TGT, utilized pre-trained Ego VLPV [2] on Ego-Exo4D 18] to extract text and video embeddings. The temperature value used in the cross-entropy distinctiveness loss from an initial value of 1.0 to a final value of 0.05, with updates occurring every 100 epochs. This gradual decrease in B mimics the warm-up strategy of (40, enabling smoother optimization early in training and leading to improved convergence as training progresses.
set to 0.9 as in [33]. The parameter linearly annealed
Table 5 details the hyperparameters employed in the experiments for task graph generation the Assembly 101-O and EPIC-Tent-O datasets. For the downstream task of online mistake detection within the DO model framework, we extended the maximum training epochs to 1200, particularly for Assembly101 101-O. This change was necessary because, even after 1000 epochs, the model continued to exhibit many cycles among its 86 nodes. Extending the number of epochs allows the model additional time to learn and minimize these cycles, which crucial given the complexity of the graph. In the TGT configuration, we reduced the dropout rate, while the parameter was gradually annealed from an initial value of 1.0 to 0.55 to prevent overfitting.
The reader is referred to the code for additional implementation details.
15

---

Table 4: List of hyppe-parameeees used in the mod- els training process for task graph generation us- ing CaptainCook4D 30).
Table 5: List of nyper-parament used in the mod- els training process for task graph generation us- ing Assembly101-O and EPIC-Tent-O.
Value
Value
pepeeeparameter
DO
TGT
DO
TGT
Learning Rate
0.1
0.000001
Learning Rate
0.1
0.000001
Max Epochs
1000
3000
Max Epochs
1200
1200
Optimizer
Adam
Adam
Optimizer
Adam
Adam
B
0.005
1.0 ~ 0.05
0.005
1.0 ~ 0.55
Dropout Rate
0.25
Dropout Rate
0.1
C.4 LLM Prompt
Below the prompt that was employed to instruct the model on its task, which involves identifying pre-conditions for given procedural steps.
would like you to learn to answer questions by telling me the steps that need to be performed before a given one.
The questions refer to procedural activities and these are of the following type:
Q Which of the following key steps is pre-condition for the current key step "add brownie mix"?
add oil
add water
break eggs
mix all the contents
mix eggs
pour the mixture in the tray
spray oil on the tray
None of the above
Your task is to your immense knowledge and your immense ability to tell which preconditions are among those listed that must necessarily be carried out before the key step indicated in quotes in the question.
You have to give me the answers and a very brief explanation of why you chose them.
Provide correct preconditions answer inside JSDN format like this:
"add brownie mix": ["add oil", "add water", "break eggs"]
C.5 Data Split
The CaptainCook4D dataset (30) comprises various error types, including order errors, timing errors, temperature errors, preparation errors, missing steps errors, measurement errors, and technique errors. Of these, missing steps and order errors directly impact the sequence integrity. Consequently, for our task graph generation, we utilized only those sequences of actions free from these specifie types of errors. ( statistics on the CaptainCook4D subsets used for task graph generation.
For Online Mistake Detection, considered the datasets defined by the authors of PREGO 13
In the context of pairwise ordering and forecasting, we employed the subset the CaptainCook4D dataset designated for task graph generation (refer to Table () and divided it into training and
16

---

Table 6: A detailed breakdown of the data used from the CaptainCook44 dataset 30 for the task graph generation. This table categorizes each scenario by the number of videos, segments, and total duration in hours. The "Total" row aggregates the dataset characteristics.
Scenario
Videos
Segments
Duration
Microwave Egg Sandwich
60
0.9h
Dressed Up Meatballs
128
2.7h
Microwave Mug Pizza
84
1.2h
Ramen
11
165
2.7h
Coffee
144
2.2h
Breakfast Burritos
8
88
1.5h
Spiced Hot Chocolate
49
0,9h
Microwave French Toast
11
121
2.2h
Pinwheels
95
0,8h
Tomato Mozzarella Salad
13
117
1.3h
Butter Corn Cup
60
1.4h
Tomato Chutney
95
2.6h
Scrambled Eggs
138
2.6h
Cucumber Raita
12
132
2.7h
Zoodles
78
1.1h
Sauted Mushrooms
126
2.9h
Blender Banana Pancakes
10
140
2.4h
Herb Omelet with Fried Tomatoes
120
2.4h
Broccoli Stir Fry
10
250
5.2h
Pan Fried Tofu
171
3.6h
Mug Cake
180
3.0h
Cheese Pimiento
77
1.6h
Spicy Tuna Avocado Wraps
153
2.6h
Caprese Bruschetta Total
88
2.4h
194
2859
53.0h
testing sets. This division was carefully managed to ensure that 50% of the scenarios were equally represented in both the training and testing sets.
C.6 Pairwise ordering and future prediction
We setup the pairwise ordering and future prediction video understanding tasks following 46
Pairwise Ordering Models take as input two randomly shuffled video clips and are tasked with recognizing the correct ordering between key-steps. We sample consecutive triplets of labeled segments from test videos, discard the middle one, and consider the first and third ones as input pair. We evaluate models using accuracy.
Future Prediction Models take as input anchor video clip and two randomly shuffled video clips and are tasked to select which of the two clips is the correct future the anchor clip. We sample all consecutive triplets of labeled segments from test videos and consider the middle clip as anchor and the remaining two clips as the two options. We evaluate models using accuracy.
Model We trained our TGT model using video embeddings extracted with pre-trained ELoV [32] on Ego-Exo4D [8]. During the training process, multiple vidco embeddings associated with the same key-step across the training sequences, one embedding per key-step is randomly selected. The model is trained for task graph generation on the training video and tested for pairwise ordering and future prediction the test set.
For pairwise ordering, we feed our model with two clips and obtain a 4 x adjacency matrix, where the nodes represent START, A, B, END. We establish the order between A and B based the fulfillment of least one of the following conditions: (a) if the weight of the edge A - is greater than the weight of the edge B - A, we conclude that A precedes B; (b) by analyzing the sequences
17

---

Table 7: Performance comparison between the single TGT-text model trained across all Captain- Cook4D procedures and the unified model. The confidence intervals in the single models indicate that the unified method performs comparably to training individual models for each procedure.
Method
Precision
Recall
F1
TGT-text (single)
79.9 28.8
81.9 +6.9
80.8 +8.0
TGT-text (unified)
61.5 #12.0
68.2 +10.3
64.5 +11.9
< START, A, B. END > and < START, B, A, END >, we calculate their probabilities using Eq. ④ If P(< START, A, B, END >| Z) is greater than P( START, B, A, END > Z). we infer that A precedes B; (c) if the weight of the edge END - B is greater than that of END - A, it implies that is a necessary precondition for concluding the procedure, indicating that B follows A, and consequently, A precedes B, If none of these conditions hold, we determine that B precedes A.
For future prediction, we feed three clips and obtain a represent START, A, anchor, B, and END. We hence inspect the weights of edges anchor + A and anchor + and choose as the future clip, the one related the smallest weight (a small weight indicates that the selected clip is not precondition). Another method to determine the future clip by calculating the probabilities of the sequences < START, A, anchor, B, END > and < START, B, anchor, A, END > using Eq. greater than Pi< START, B, anchor, A, END Z), we infer that the sequence involving before B is more probable, indicating that B is the future clip for anchor. Conversely, if the probability of the second sequence greater, then deemed the future clip for anchor.
adjacency matrix, where the nodes
4 If P(< START, A, anchor, B, END > Z) is
C.7 Scalability of Task Graph Transformer (TGT)
The Direct Optimization (DO) approach requires a separate training session for each procedure. Task Graph Transformer (TGT) offers more flexibility by allowing different sets of key-step embeddings at each forward pass, ideally enhancing scalability. Leveraging this capability, we trained a single TGT text model for all CaptainCook4D procedures. This was achievable due to TGT's ability to handle varying embeddings per forward pass, enabling simultaneous optimization across multiple procedures during training. As shown in Table 7 the confidence intervals of both the single and unified models highlight some performance variance. The unified model exhibits lower average precision, recall, and Fl scores compared the individually trained models, with a larger confidence interval. However, the results suggest that TGT-text models can still generalize across diverse procedures, reducing training complexity while maintaining reasonable performance.
C.8 Graph Post- Post-processing
We binarize the adjacency matrix with the threshold n. where n the number of nodes. After this thresholding phase, it is possible to encounter situations like the one illustrated in Figure where node A depends on nodes and C, and node B depends on node C. Due the transitivity of the pre-conditions, we can remove the edge connecting node A to node C, as node B must precede node A. Sometimes, it may occur that a node does not serve as a pre-condition for any other node; in such cases, the END) node should be directly connected to this node. Conversely, if a node has no pre-conditions, an edge is added from the current node to the START node.
At the end of the training process, obtaining a graph containing cycles is also possible. In such cases, all cycles within the graph are considered, and the edge with the lowest score within each cycle is removed. This method ensures that the graph remains a Directed Acyclic Graph (DAG).
C.9 Details Online Mistake Detection
Given the noisy sequences in Assembly 101 [37 and EPIC-Tent [19. a distinct approach was adopted during the post-processing phase of task graph generation. Specifically, if key-step in the task graph has only two pre-conditions and one is the START node, the other pre-condition will be removed regardless of its score, otherwise we apply the transitivity dependences reduction aforementioned. This approach allows for a graph with fewer pre-conditions in the initial steps.
18

---

c
C
B
B
A
A
(a)
(b)
Figure 6: An example of transitive dependency between nodes. In (a) node A depends on and C, but B depends C, in this case, remove the edge between A and C for transitivity and obtain the graph in (b).
Nekion
Figure 7: A success (left) and failure (right) case on EPIC-Tent-O, Past key-steps' colors match nodes' colors. On the left, the current key-step "Pickup/Open Stakebag" is correctly evaluated as a mistake because the step "Pickup/Place Ventcover" is precondition of the current key-step, but it is not included among the previous key-steps. On the right, "Pickup/Open Supportbag" incorrectly evaluated as mistake because the step "Spread Tent" is precondition of the current key-step, but is not included among the previous key-steps. This is due to the fact that our method wrongly predicted "Spread Tent" as pre-condition of "Pickup/Open Supportbag", probably due to the two actions often occurring in this order.
In the case of Assembly 101, which includes multiple procedural tasks, opted to consider single task graph that summarizes all the procedures, rather than generating individual graphs for each.
C.10 Qualitative Examples
Figures 8 31 report qualitative examples of prediction using our Direct Optimization (DO) method on the procedures of CaptainCook4D. The task graphs must be read in bottom-up manner, where the START node (bottom) is at the lowest position and represents the first node with no preconditions, while the END node (up) the final step of the procedure.
Figure 7 reports a qualitative analysis of the generated task graph for detecting the mistakes on EPIC-Tent-O.
C.11 Experiments Compute Resources
The experiments involving the training of the DO model on symbolic data from the CaptainCook4D dataset proved to be highly efficient. We were able to generate all the task graphs in approximately half an hour using Tesla VI00S-PCI GPU. This GPÚ allowed us to run up training processes simultaneously. In contrast, training the TGT models for all scenarios in the CaptainCook4D dataset required about 24 hours, with the same GPU supporting the concurrent training of up to 2 models. Additionally, once the task graphs were obtained, executing the PREGO benchmarks for mistake detection was significantly faster, requiring online action prediction, which could be performed in real-time Tesla VI00S-PCI GPU.
19

---

D
Societal Impact
Reconstructing task graphs from procedural videos may enable the construction of agents able to assist users during the execution of the task. Learning task graphs from videos may be affected by geographical cultural biases appearing in the data (e.g.. specific ways of performing given tasks), which may limit the quality of the feedback returned to the user, potentially leading to harm. We expect that training data of sufficient quality should limit such risks.
High
(b)
Figure 8: (a) Ground truth task graph and (b) predicted task graph of the scenario Breakfast Burritos.
(a)
(b)
Figure 9: (a) Ground truth task graph and (b) predicted task graph of the scenario Breakfast Burritos.
(b)
Figure 10: (a) Ground truth task graph and (b) predicted task graph of the scenario Cheese Pimiento.
20

---

(b)
Figure 11: (a) Ground truth task graph and (b) predicted task graph of the scenario Coffee.
(b)
Figure 12: (a) Ground truth task graph and (b) predicted task graph of the scenario Cucumber Raita.
(a)
(b)
Figure 13: (a) Ground truth task graph and (b) predicted task graph of the scenario Dressed Up Meatballs.
(b)
Figure 14: (a) Ground truth task graph and (b) predicted task graph of the scenario Broccoli Stir Fry.
21

---

(b)
Figure 15: (a) Ground truth task graph and (b) predicted task graph of the scenario Caprese Bruschetta.
P
Code
MIG lays aumoiiiiii
(a)
(b)
Figure 16: (a) Ground truth task graph and (b) predicted task graph of the scenario Zoodles.
(a)
(b)
Figure 17: (a) Ground truth task graph and (b) predicted task graph of the scenario Microwave Mug Pizza.
22

---

(a)
(b)
Figure 18 (a) Ground truth task graph and (b) predicted task graph of the scenario Herb Omelet with Fried Tomatoes.
(a)
(b)
Figure 19: (a) Ground truth task graph and (b) predicted task graph of the scenario Microwave Egg Sandwich.
(a)
(b)
Figure 20: (a) Ground truth task graph and (b) predicted task graph of the scenario Microwave French Toast.
23

---

(b)
Figure 21: (a) Ground truth task graph and (b) predicted task graph of the scenario Mug Cake.
seveectoss mere
Intte
(b)
Figure 22: (a) Ground truth task graph and (b) predicted task graph of the scenario Pan Fried Tofu.
24

---

(b)
Figure 23: (a) Ground truth task graph and (b) predicted task graph of the scenario Pinwheels.
Figure 24: (a) Ground truth task graph and (b) predicted task graph of the scenario Spicy Tuna Avocado Wraps.
AiL
(a)
(b)
Figure 25: (a) Ground truth task graph and (b) predicted task graph of the scenario Spiced Hot Chocolate.
25

---

[
(b)
Figure 26: (a) Ground truth task graph and (b) predicted task graph of the scenario Tomato Mozzarella Salad.
DXU
Hal diiiin all
perget cand callvoe with pepirtool
Foadieed dovu
(a)
(b)
Figure 27: (a) Ground truth task graph and (b) predicted task graph of the scenario Salted Mushrooms.
(b)
Figure 28: (a) Ground truth task graph and (b) predicted task graph of the scenario Ramen.
26

---

Haslt centects
ubbed Ioa jus bove
Edtadd-birari Loen jaka Dua L0
ASS-Ad 1 taagpec rakt kon!
Kimnowae Microaee
steates
sirti
peopes
leapees
Morworelerrrrr casile
stn excruscno
Than-Tave the trass care by potling it receing under cold nater
Iaa Dan de paliin ralag
Meesem Messar 2 ape tonee
STAET
(b)
Figure 29: (a) Ground truth task graph and (b) predicted task graph of the scenario Butter Corn Cup.
(b)
Figure 30: (a) Ground truth task graph and (b) predicted task graph of the scenario Scrambled Eggs.
27

---

AND
EN
Tran of bast
Talo parc the
Add Sellegg
AAR Eigioall par
Ado-dd tomatoo jom the
Aot 10 silk phi
JV Ael Vtep cot paodle tithe por
Aik-old Lhgg red dld poinder
Lower best
SActAGerr for
#k/Wies suatirrd caccures cends beglo io sicin ald clind palli
SEE (it unlaelitiipe
Hodl Lik alt
beaterebe
pescedioo puts
Chey-Cap copply anyst Seal
Take
Freiiiss Large patc
Feet/eal Elage patk
(b)
Figure 31: (a) Ground truth task graph and (b) predicted task graph of the scenario Tomato Chutney.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: we introduce novel approach to build task graphs using a differentiable loss function. The usefulness of the learned representation is assessed three datasets the tasks of task graph generation, and online mistake detection. Technical descriptions are reported in Section and experiments reported in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: the limitations discussed in Section 5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
29

---

Answer: [NA]
Justification: the paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Section 3 presents the description of our differentiable loss function and describes the proposed models. Experiments in Section 4 and the supplementary material contain descriptions for reproducibility. We release preliminary version of our code in the supplementary and we will publicly release the final code to replicate the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
30

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: We use publicly available datasets and provide details on data splits in share preliminary version of our code in the supplementary material and plan to release the final code replicate all experiments.
We
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.com
Seegli/c/uuides//ddeubbb.m.. oow.ssabbbbsiooooiooooooo.o.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
Sww.leee/ooSSSemiiseeee cettsummiissooonll wassonoooicyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We report implementation details and hyper- parameters in Section C of the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Results in Table report the bounds of confidence intervals computed at a 90% confidence level. These intervals derived using bootstrapping, where resample the results from 5 runs with different random initializations to estimate the distribution of the performance metrics. We report the average performance ã across the 5 runs with the corresponding standard deviation a. The confidence bounds are obtained by repeatedly resampling the data and calculating the desired percentiles from the empirical distribution.
Justification:
Guidelines:
31

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report details on computational requirements run the experiments in Section C.1I of the supplementary material.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/://ooorrrp...cc////t/aaas
Answer: [Yes]
Justification: We used public datasets which have been collected by the related authors following the recommendations provided by their institutions. The datasets have not been deprecated. We do not re-distribute any of the used data.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
32

---

Answer: [Yes]
Justification:
We discuss societal impact in Section of of the supplementary material.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have referenced the data used for the experiments and followed the related licenses. Licenses are available at the respective authors' pages.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
33

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce a new loss function for task graph generation and two new models (see Section 3).
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
34

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "2abTRgCETQ", "reviewer": "Reviewer_pcHQ", "summary": "The paper proposes a differentiable loss function based on the maximum likelihood of generating task graphs from video features. The two proposed methods (DO and TGT) show strong performance, verifying their effectiveness in generating task graphs. Moreover, the predicted graphs are evaluated on downstream tasks to demonstrate the influence of explicit graph representations for general video understanding.", "questions": "See weaknesses. My concern is the potential limitation for applications to long-form daily-life procedure activities where repetition is crucial.", "limitations": "Yes, the authors have discussed the limitations of this work, which is insightful and can facilitate future works of task graphs for video understanding.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In general, I like the paper from every perspective. It advances the progress of using task graphs for video understanding.\n\n- The paper is well-written and easy to understand.\n- The literature survey is comprehensive enough, which helps readers easily understand the motivation and the problem setting.\n- The experimental comparison is extensive enough, including a rich set of recent baselines that vary from different types of task graph generation.\n- The two proposed methods show strong performance on the evaluated datasets, verifying the effectiveness of the proposed differentiable task graph generation.  \n- The generated explicit task graph representation is also evaluated on the downstream tasks.\n- The discussed limitations, e.g., the assumption of availability of key-step sequences, are insightful and are critical to the future development of task graphs for video understanding.", "weaknesses": "- L140 describes that the authors separate sequences if the key-step repetition is available. I am wondering if this will limit the applications for some daily scenarios where a key step needs to be conducted many times, e.g., spreading peanut butter multiple times.\n\n- In L329, it would be nice to have a reference of those action recognition works that assume key-step sequences are available.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of the paper and for providing constructive feedback and suggestions for improvement. In the following, we report our answers to the reviewer's specific queries.\n\n## Q1: L140 describes that the authors separate sequences if the key-step repetition is available. I am wondering if this will limit the applications for some daily scenarios where a key step needs to be conducted many times, e.g., spreading peanut butter multiple times.\n\nAs correctly observed by the reviewer, in order to model action sequences as topological sorts of a directed acyclic graph (the task-graph), *at training time*, we assume that sequences do not contain repetitions and map all those sequences which may contain some repetitions to sequences where each action appears only once (e.g., ABCAD → (ABCD, BCAD) - see footnote 2, page 4). \n\nWe would like to note that the limited ability of task graphs to explicitly model repeatable key-steps is a current limitation of the task-graph representation, also affecting previous approaches which do not explicitly model key-step repetitions [1, 2, 3, 4]. Limited work towards modeling key-step repetitions has been very recently reported in [9], where the classic task-graph definition has been extended to also include a \"repeatable\" node attribute. It is worth noting, however, that the work of [9] is only carried out in the context of the manual labeling of task-graphs (i.e., \"repeatable\" attributes are manually added - not computed), while it is still unclear how such attributes should be effectively learned from data.\n\nDespite this limitation, our error detection model still correctly handles all those cases in which it is possible to execute a key-step multiple times (e.g., spreading peanut butter). Indeed, at test time, it will always be possible to verify the pre-conditions of a key-step through the predicted task-graph, even if that key step has previously appeared in the sequence.\n\nNevertheless, we believe that a better and more native modeling of key-step repetitions (e.g., to handle cases in which some key-steps may need to be executed exactly $n$ times in a correct procedure - \"cut three slices of bread\") is an interesting venue for future works and extensions to the proposed learning framework and plan to include the discussion above in the \"limitations\" paragraph of the manuscript.\n\n[1] Ashutosh, Kumar, et al. \"Video-mined task graphs for keystep recognition in instructional videos.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Zhou, Honglu, et al. \"Procedure-aware pretraining for instructional video understanding.\" *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2023.\n\n[3] Sohn, Sungryull, et al. \"Meta reinforcement learning with autonomous inference of subtask dependencies.\" arXiv preprint arXiv:2001.00248 (2020).\n\n[4] Jang, Yunseok, et al. \"Multimodal subtask graph generation from instructional videos.\" arXiv preprint arXiv:2302.08672 (2023).\n\n## Q2: In L329, it would be nice to have a reference of those action recognition works that assume key-step sequences are available.\n\nWe thank the reviewer for their suggestion. Video understanding methods focusing on action analysis, such as action recognition and temporal action detection, assume that the start and end times of actions, as well as their categories, are marked in videos. All these datasets can be exploited within our framework to learn task-graph representations of the considered activities. We will revise the paper to clarify this point and will add references to the following works proposing datasets and formalizing tasks with such characteristics:\n\n[5] Caba Heilbron, Fabian, et al. \"Activitynet: A large-scale video benchmark for human activity understanding.\" Proceedings of the ieee conference on computer vision and pattern recognition. 2015.\n\n[6] Kay, Will, et al. \"The kinetics human action video dataset.\" arXiv preprint arXiv:1705.06950 (2017).\n\n[7] Jang, Youngkyoon, et al. “Epic-tent: An egocentric video dataset for camping tent assembly.” Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops. 2019.\n\n[8] Grauman, Kristen, et al. \"Ego4d: Around the world in 3,000 hours of egocentric video.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.\n\n[9] Grauman, Kristen, et al. \"Ego-exo4d: Understanding skilled human activity from first-and third-person perspectives.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RGejPkLeTr", "reviewer": "Reviewer_PJ9t", "summary": "This paper introduced a learning-based task graph generation for procedural actions and mistake detection. Compared to previous approaches which usually consider natural language based descriptions, the proposed approach aims to use backward propagation to adaptively optimize procedural action sequences. To the reviewer, the introduced approach is much more flexible compared to other \"hard-coded\" language-based descriptions. In summary, this papers introduced a simple yet inspiring approach for graph generation.", "questions": "Please refer to weakness for details.", "limitations": "The limitations that the authors introduced are reasonable considering current submission, and they do not have any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed optimization based graph generation seems inspiring and novel. Unlike other existing hand-crafted methods, learning-based graph generation can be end-to-end trained with task model parameters. This has the potentials in significantly boosting model performances, since the graph is no longer hard-coded, which makes models able to automatically search for the optimal correlations.\n2. The methodology is mostly clear and easy to follow. The authors well demonstrate how to establish and end-to-end optimize trainable graphs. \n3. The experimental results are quite promising in the experiment sections, and the improvements are non-trivial and encouraging.", "weaknesses": "1. The explanations of contrastive loss are somehow hard to follow. For typical contrastive learning, to push away or to pull close the distances always require positive/negative and anchor samples. The authors are expected to provide more detailed discussions to help readers understand.\n2. In line 140, the authors make an assumption that no repetitive actions exists in sequences, without any further discussions. It is suggested that authors could provide more explanations on why they have this assumption and what impact this assumption causes to the proposed approach.\n3. It is suggested that how the video and text embeddings are sent to the overall framework should be clearly demonstrated in the Figure 3. In the current submitted version, it is somehow confusing to the readers how the video features are considered into the training process.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of our work and for their supportive remarks and constructive feedback. In the following, we report our replies to the reviewer's specific queries.\n\n## Q1: The explanations of contrastive loss are somehow hard to follow. For typical contrastive learning, to push away or to pull close the distances always require positive/negative and anchor samples. The authors are expected to provide more detailed discussions to help readers understand.\n\nOur loss function is defined following the Maximum Likelihood framework, hence, by optimizing it, we aim to obtain the graph which maximizes the probability of the sequences observed in the training set. For better interpretability of the mechanism by which the proposed learning framework allows to obtain meaningful graph presentations, we noted that the derived maximum-likelihood loss function reported in Eq. (6) also has a contrastive interpretation in which edges between the currently observed key-step and all key-steps appearing before the current one in a given sequence are considered as positive examples of dependencies, while edges between future key-steps and the currently observed ones are considered as negative examples of dependencies. By maximizing the weight of positive dependencies (term in cyan in Eq. (6)) and minimizing the weight of negative dependencies (term in green in Eq. (6)), we aim to learn informative key-step dependencies (the current step depends on the past ones), beyond all obvious dependencies (all future key-steps depend on all past key-steps). As in other contrastive learning frameworks [1, 2], our approach only includes positives and negatives and it does not explicitly consider anchor examples. We agree with the reviewer on the lack of clarity and will add this more detailed discussion in the paper.\n\n[1] Oord, A. van den, et al.\"Representation learning with contrastive predictive coding.\" arXiv preprint arXiv:1807.03748 (2018).\n\n[2] Radford, Alec, et al. \"Learning transferable visual models from natural language supervision.\" International conference on machine learning. PMLR, 2021.\n\n## Q2: ﻿﻿﻿In line 140, the authors make an assumption that no repetitive actions exists in sequences, without any further discussions. It is suggested that authors could provide more explanations on why they have this assumption and what impact this assumption causes to the proposed approach.\n\nWe model the task-graph as a directed acyclic graph in which key-steps are nodes and edges represent dependencies. To define our learning framework in the context of Maximum Likelihood, we interpret each action sequence as a possible topological sort of the graph. Since topological sorts cannot contain repetitions [3], we then assume that our *training* action sequences do not contain repetitions. Practically, we map each sequence with repetitions to multiple sequences with no repetitions as described at page 4, footnote 2 (e.g., ABCAD → (ABCD, BCAD)).\n\nWhen defined as directed acyclic graphs, task-graphs have a limited ability to model key-step repetition, which is common to other works [4-6]. While future works should focus on overcoming such limitations, we observe that our approach to mistake detection can still be used in all those cases in which a key-step can be arbitrarily repeated (e.g., spread peanut butter), as repetitions are not removed at inference and pre-conditions can still be checked even for repeated key-steps.\n\nThe reviewer is also referred to the reply to Q1 of reviewer 1 for an in-depth discussion on how our method deals with key-step repetitions and how future works can improve on this aspect.\n\n[3] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). *Introduction to algorithms*. MIT press.\n\n[4] Ashutosh, Kumar, et al. \"Video-mined task graphs for keystep recognition in instructional videos.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[5] Zhou, Honglu, et al. \"Procedure-aware pretraining for instructional video understanding.\" *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2023.\n\n[6] Grauman, Kristen, et al. \"Ego-exo4d: Understanding skilled human activity from first-and third-person perspectives.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.\n\n## Q3: ﻿﻿﻿It is suggested that how the video and text embeddings are sent to the overall framework should be clearly demonstrated in the Figure 3. In the current submitted version, it is somehow confusing to the readers how the video features are considered into the training process\n\nOur Task Graph Transformer (TGT) approach can take as input either D-dimensional text embeddings or video embeddings extracted from key-step segments. Text embeddings are extracted from key-step names, whereas video embeddings are extracted from key-step video segments. In both cases, we use a pre-trained EgoVLPv2 model. When using text embeddings, at each forward pass, the TGT takes as input the same batch of $n$ text embeddings and outputs the $(n + 2) \\times (n + 2)$ adjacency matrix, which is optimized with the proposed loss function. When training with video embeddings, since more than one embedding (hence more than one video segment) can be associated to a given key-step, at each forward pass, we randomly sample one embedding per key-step, thus obtaining a set of $n$ embeddings which is used to generate the $(n+2) \\times (n+2)$ adjacency matrix, supervised with the proposed loss. We would like to note that we either train our model using only text embeddings or only video embeddings. We will clarify these points in the paper and we have revised Figure 3 to be more detailed and accurate. The reviewer is referred to Figure 1 in the PDF file attached to the author rebuttal for details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bWB0EBECas", "reviewer": "Reviewer_tC41", "summary": "The paper presents a novel approach to learning task graphs from procedural activities observed in egocentric videos. Task graphs represent the partial ordering of key-steps needed to complete a task and are crucial for developing intelligent agents that can assist users. The proposed method utilizes direct maximum likelihood optimization of edge weights, enabling gradient-based learning that can be integrated into neural network architectures. The study demonstrates significant improvements in task graph prediction accuracy and online mistake detection using datasets like CaptainCook4D, Assembly 101, and EPIC-Tent.\n\nThe main motivation behind this work is twofold. Firstly, it aims to enhance the ability of intelligent systems to assist users in performing complex tasks by automatically learning flexible and accurate task graph representations from video observations, rather than relying on manually crafted procedures. Secondly, the authors seek to explicitly model task graphs to provide a more interpretable and human-understandable representation of procedural activities.\n\nThe authors introduce two primary approaches for task graph learning: Direct Optimization (DO) and Task Graph Transformer (TGT). The DO method uses the Task Graph Maximum Likelihood (TGML) loss to directly optimize the adjacency matrix representing the task graph. This optimization is performed using gradient descent, making the process straightforward and effective. On the other hand, the TGT model employs a transformer encoder to process key-step text or video embeddings and predict the adjacency matrix from these embeddings. This model includes a regularization loss to maintain distinctiveness among embeddings, ensuring accurate and meaningful task graph generation.", "questions": "Please see Weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main contributions of the paper are as follows:\n\n1. **Approach:** This paper presents an new error detection approach via learning task graphs by directly optimizing a maximum likelihood objective. This approach enables gradient-based task graph learning, allowing task graph methods to be applied to the problem of mistake detection in programs.\n2. **Performance:** The proposed methods achieve superior performance in task graph generation and mistake detection compared to existing methods.\n3. **Code Availability**: The availability of code for replication enhances the study's transparency and usability.", "weaknesses": "1. **Dependence on Labeled Key-Step Sequences:** The method proposed in this work relies on action recognition models or Ground-truth Key-Step Labels. On the one hand, this will bring additional performance overhead, and on the other hand, relying on other action recognition models may introduce noise when errors occur during recognition. It's uncertain whether it will also affect the results of mistake detection. More discussions on these issues are needed.\n\n2. **Limitation in Versatility and Scalability:** In this approach, a new model (task graph) needs to be trained for each new sequence of actions in order to achieve mistake detection. This method to some extent limits the versatility and scalability of the model, as retraining is required for each new task. Additionally, it seems that the proposed method has no versatility on order-unrelated mistakes, such as technique/measurement errors, which are highlighted in latest datasets (e.g., HoloAssist-ICCV23[1], CaptainCook4D-ICML23[2], EgoPER-CVPR24[3])\n\n3. **Insufficient Qualitative Analysis**: The paper only provides one qualitative result on generated task graph in Figure 5. However, there is no qualitative analysis of the generated task graphs for detecting the mistakes. Also, it is suggested to provide discussions on the corner cases that may be challenging for the proposed method, which would bring insightful observations for the error detection community.\n\n[1] Wang, Xin, et al. \"Holoassist: an egocentric human interaction dataset for interactive ai assistants in the real world.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023.\n[2] Peddi, Rohith, et al. \"CaptainCook4D: A dataset for understanding errors in procedural activities.\" arXiv preprint arXiv:2312.14556 (2023).\n[3] Lee, Shih-Po, et al. \"Error detection in egocentric procedural task videos.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.\n\nSuggestions for authors: \nMy main concerns are about:\n- The versatility of the proposed method for various types of mistakes.\n- The detailed qualitative analysis on generated graphs when used to detect mistakes.\nPlease do read the weakness carefully, I would consider to raise my rating if my concerns are well addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Q1: Dependence on Action Recognition Models\n**Computational Overhead** while it is true that the action recognition model introduces a computational overhead, at inference, our approach is a lightweight module on top of the detected actions which can be easily plugged into systems already including an action recognition system to tackle other tasks, such as checking whether an action has been performed to provide guidance with Augmented Reality. It is also worth noting that compute-efficient online action recognition system such as MiniROAD [1] are available in the literature. \n\n**Noise in Action Detections** Table 3 of the paper shows that our model works even in the presence of imperfect predictions. To further investigate the effect of noise, we conducted an analysis based on the controlled perturbation of ground truth action sequences, with the aim to simulate noise in the action detection process. At inference, we perturbate each key-step with a probability $\\alpha$ (the \"perturbation rate\"), with three kinds of perturbations: insert (inserting a new key-step with a random action class), delete (deleting a key-step), or  replace (randomly changing the class of a key-step). For each prediction, we perform a replace with probability $\\alpha$ on the current key-step, then for each previous key-step we perform either a replace, delete or insert with probability $\\alpha$. The results presented in Figure 2 of the attached PDF show that, while our approach is affected by noise in the predictions of the action recognition system, it still exhibits a certain degree of robustness. Error bars on 5 runs.\n\n[1] An, Joungbin et al. Miniroad: Minimal RNN framework for online action detection. ICCV 2023\n\n## Q2: ﻿﻿﻿Limitation in Versatility and Scalability\n**On Scalability:** While DO requires a new training for each procedure as correctly observed by the reviewer, TGT can take different sets of key-step emebddings at each forward pass, hence ideally enabling better scalability. This aspect was not assessed in the original paper, and we thank the reviewer for their insightful comment and opportunity to better explore this point. We performed two experiments. \n- In the first experiment, we trained a single TGT-text model for all CaptainCook4D procedures. This is possible thanks to the ability of TGT to receive a different set of embeddings at each forward pass, allowing to alternate the optimization of the different procedures during training. As highlighted in Table 1 of the attached PDF, our unified model brings small improvements over the single models ($72.1 \\to 74.9$ F1) while reducing training time by a factor of $\\approx 24$ (the number of procedures), thus improving scalability. \n- In the *second experiment*, we assess the transfer learning abilities of TGT. We followed a \"leave-one-out\" scheme in which we train the TGT on all procedures except one, and then fine-tune the model on $5$ sequences for the held-out procedure (hence a $5$-shot regime). The results of this experiment reported in Table 2 of the attached PDF show that our approach greatly improves over competitors which are unable to leverage transfer learning. Due to time constraints we only considered 5 procedures but will extend to all scenarios in the camera ready.\n\n**On Versatility:** We followed the setup of PREGO [2], which defines the Assembly101-O and EPIC-tent-O datasets as curated versions of the original datasets to account for open-set procedural errors. The procedural errors considered by the authors of [2] are those involving \"order\", \"omission\", \"correction\" and \"repetition\", which are considered to be procedural mistakes, in contrast to \"proficiency errors\" as described in [3]. As correctly observed by the reviewer, being designed to address procedural mistakes at the abstract level of the executed actions, our method would not be directly applicable to the detection of proficiency errors. In a real system, we expect that this limitation  can be overcome by integrating different subsystems responsible for handling different types of mistakes, while an integrated approach would still be possible and a good venue for future works. We will add this discussion in the \"limitations\" paragraph of the paper.\n\n[2] Flaborea, Alessandro et al. PREGO: online mistake detection in PRocedural EGOcentric videos. CVPR 2024\n\n[3] Grauman, Kristen et al. Ego-exo4d: Understanding skilled human activity from first-and third-person perspectives. CVPR 2024\n\n## Q3: Insufficient Qualitative Analysis\n**Qualitative Examples** We will add more qualitative examples of generated graphs in the style of that reported in Figure 5 of the supplementary material. For reference, the supplementary material contains all task-graphs predicted on CaptainCook4D. We will base our illustrations on those examples.  We will also include qualitative examples of mistake detections produced by the proposed model. Please see Figure 3 of the attached PDF for a qualitative example on EPIC-Tent. We will add other similar examples also based on Assembly101.\n\n**Corner Cases** We will discuss corner cases in the \"limitations\" section of the main paper. The performance of our method depends on the quality of recognized actions. If the action recognition module fails to detect an action, our method may incorrectly signal a missing pre-condition. Conversely, if it detects an action that wasn't performed, our method may miss signaling a mistake. We expect improvements in online action recognition to enhance our method's robustness. Our method does not explicitly model \"optional\" key-steps, which can lead to incorrect mistake signaling if optional steps are treated as mandatory. This issue could be resolved with specialized modules to detect optional nodes. Our approach works at an abstract level, focusing on whether an action has been performed rather than how it has been performed, leaving room for improvement in handling incomplete or sub-optimally performed actions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful comments and constructive feedback.

All reviewers appreciated the proposed method. **pcHQ** highlighted that our method demonstrates strong performance on the analyzed datasets, confirming the effectiveness of differentiable task graph generation. **PJ9t** found our approach to task graph generation inspiring and innovative, particularly appreciating our ability to establish end-to-end optimized trainable task graphs. **tC41** acknowledged that our method represents a novel and promising approach to address the problem of error detection through task graph learning.

Furthermore, all reviewers expressed satisfaction with the experiments conducted and the performance achieved with our method. **pcHQ** highlighted that *“the experimental comparison is extensive enough, including a rich set of recent baselines that vary from different types of task graph generation”* and appreciated the evaluation of the proposed representation on downstream tasks. **PJ9t** stated that *“the experimental results are quite promising in the experiment sections, and the improvements are non-trivial and encouraging”*. **tC41** wrote that *“the proposed methods achieve superior performance in task graph generation and mistake detection compared to existing methods”*.

We are particularly pleased to read that **pcHQ** found our paper *“well-written and easy to understand”*, with a *“comprehensive literature survey”*, hence clearly stating the positioning with respect to prior works and with insightful discussed limitations; **PJ9t** considered our method *“mostly clear and easy to follow”*; and **tC41** appreciated *“the availability of code for replication”*, which is a recognition of our commitment to transparency and reproducibility of research.

Besides this positive feedback, reviewers also identified areas of improvement for the proposed work. We addressed the comments of each reviewer below and believe that their feedback has been extremely useful in improving various aspects of our work. In short:

- (**pcHQ**, Q1 - **PJ9t**, Q2) We elaborated on the ability of our approach to handle key-step repetitions and how this affects mistake detection. We highlighted that this is a common limitation of methods based on task-graph and that our mistake detection algorithm is not affected by key-step repetitions in most cases;
- (**pcHQ**, Q2) We improved presentation by adding references where needed, as suggested by reviewers, and particularly on those tasks considering a similar setup to ours in which fine-grained key-step annotations are available in videos;
- (**PJ9t**, Q1) We clarified the description of the contrastive loss in terms of positives and negatives. We clarified that our loss is defined based on the Maximum Likelihood principle, but it can still be interpreted as a form of contrastive loss for more insights into the learning mechanism;
- (**PJ9t**, Q3) We improved Figure 3 to better clarify how text and video embeddings are handled in the proposed TGT architecture. The revised figure with its caption is reported in Figure 1 in the PDF attached to this rebuttal, and will be included in the final version of the paper;
- (**PJ9t**, Q3) We discussed how the performance of the proposed system depends on the performance of the underlying action recognition system, both from the point of view of the computational overhead and from the point of view of the effect of noisy action prediction. This latter point has been addressed by performing controlled experiments in which action recognition noise is simulated by perturbing ground truth annotations. The results of these experiments are reported in Figure 2 of the attached PDF and highlight that the proposed method exhibits a certain degree of robustness with respect to noise in the detected actions;
- (**tC41**, Q1) We discussed the versatility and scalability of the proposed approach, reporting new experiments assessing the generalization and transfer learning abilities of the proposed TGT method. The results of these experiments are reported in Tables 1 and 2 of the attached PDF and show that 1) TGT allows to replace several models (one per procedure) with a unified one, and 2) TGT exhibits transfer learning abilities enabling few-shot learning;
- (**tC41**, Q2) We will improve the qualitative analysis by adding more examples of generated graphs in the text based on the predicted graphs included in the supplementary material, and by adding qualitative mistake detection results. We report two instances of such qualitative examples in Figure 3 of the attached PDF and plan to add more examples in the final version of the paper. We also reported a discussion of corner cases, better highlighting the limitations of the proposed approach. We will add this discussion to the paper.

Overall, we believe that the revision process improved the quality of the paper and we are grateful to the reviewers for their feedback. The reviewers and area chair are referred to the individual rebuttals and to the attached PDF for more details on the points briefly discussed above.

Meta-review: The paper proposes to extract task graphs from egocentric procedure videos with annotated key steps, where the task graph defines the partial ordering of steps for the successful completion of the procedure. All reviewers recognized the innovation of the differentiable loss function for graph learning, as well as the strong empirical results for task graph generation and online mistakes detection. They also raised questions on the ability to model repeatable steps and the dependency of annotated steps, both of which have been addressed in the rebuttal. After the rebuttal and discussion, the reviewers unanimously recommend acceptance of the paper. The authors are encouraged to incorporate part of the rebuttal into the main paper.
Decision: Accept (spotlight)