Publications

Generalization Limits of Graph Neural Networks in Identity Effects Learning
Giuseppe Alessio D'inverno
Simone Brugiapaglia
Mirco Ravanelli
Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven learning on various graph domains. They are usually based on a … (voir plus)message-passing mechanism and have gained increasing popularity for their intuitive formulation, which is closely linked to the Weisfeiler-Lehman (WL) test for graph isomorphism to which they have been proven equivalent in terms of expressive power. In this work, we establish new generalization properties and fundamental limits of GNNs in the context of learning so-called identity effects, i.e., the task of determining whether an object is composed of two identical components or not. Our study is motivated by the need to understand the capabilities of GNNs when performing simple cognitive tasks, with potential applications in computational linguistics and chemistry. We analyze two case studies: (i) two-letters words, for which we show that GNNs trained via stochastic gradient descent are unable to generalize to unseen letters when utilizing orthogonal encodings like one-hot representations; (ii) dicyclic graphs, i.e., graphs composed of two cycles, for which we present positive existence results leveraging the connection between GNNs and the WL test. Our theoretical analysis is supported by an extensive numerical study.
2025-01-01
Neural Networks (publié)
doi.org
arxiv.org
Ex Post Conditions for the Exactness of Optimal Power Flow Conic Relaxations
Jean-Luc Lupien
Antoine Lesage-Landry
Convex relaxations of the optimal power flow (OPF) problem provide an efficient alternative to solving the intractable alternating current (… (voir plus)AC) optimal power flow. The conic subset of OPF convex relaxations, in particular, greatly accelerate resolution while leading to high-quality approximations that are exact in several scenarios. However, the sufficient conditions guaranteeing exactness are stringent, e.g., requiring radial topologies. In this short communication, we present two equivalent ex post conditions for the exactness of any conic relaxation of the OPF. These rely on obtaining either a rank-1 voltage matrix or self-coherent cycles. Instead of relying on sufficient conditions a priori, satisfying one of the presented ex post conditions acts as an exactness certificate for the computed solution. The operator can therefore obtain an optimality guarantee when solving a conic relaxation even when a priori exactness requirements are not met. Finally, we present numerical examples from the MATPOWER library where the ex post conditions hold even though the exactness sufficient conditions do not, thereby illustrating the use of the conditions.
2025-01-01
Electric Power Systems Research (publié)
doi.org
arxiv.org
A stochastic integer programming approach to reserve staff scheduling with preferences
Carl Perreault‐Lafleur
Margarida Carvalho
Guy Desaulniers
2025-01-01
Int. Trans. Oper. Res. (publié)
doi.org
arxiv.org
Towards Enhancing the Reproducibility of Deep Learning Bugs: An Empirical Study
Mehil B. Shah
Mohammad Masudur Rahman
Foutse Khomh
2025-01-01
Empir. Softw. Eng. (publié)
doi.org
arxiv.org
Combining supervised learning and local search for the multicommodity capacitated fixed-charge network design problem
Charly Robinson La Rocca
Jean-François Cordeau
Emma Frejinger
The multicommodity capacitated fixed-charge network design problem has been extensively studied in the literature due to its wide range of a… (voir plus)pplications. Despite the fact that many sophisticated solution methods exist today, finding high-quality solutions to large-scale instances remains challenging. In this paper, we explore how a data-driven approach can help improve upon the state of the art. By leveraging machine learning models, we attempt to reveal patterns hidden in the data that might be difficult to capture with traditional optimization methods. For scalability, we propose a prediction method where the machine learning model is called at the level of each arc of the graph. We take advantage of off-the-shelf models trained via supervised learning to predict near-optimal solutions. Our experimental results include an algorithm design analysis that compares various integration strategies of predictions within local search algorithms. We benchmark the ML-based approach with respect to the state-of-the-art heuristic for this problem. The findings indicate that our method can outperform the leading heuristic on sets of instances sampled from a uniform distribution.
2024-12-01
Transportation Research Part E: Logistics and Transportation Review (publié)
doi.org
arxiv.org
Adversarial Bounding Boxes Generation (ABBG) Attack against Visual Object Trackers
Fatemeh Nourilenjan Nokabadi
Jean-Francois Lalonde
Christian Gagné
Adversarial perturbations aim to deceive neural networks into predicting inaccurate results. For visual object trackers, adversarial attacks… (voir plus) have been developed to generate perturbations by manipulating the outputs. However, transformer trackers predict a specific bounding box instead of an object candidate list, which limits the applicability of many existing attack scenarios. To address this issue, we present a novel white-box approach to attack visual object trackers with transformer backbones using only one bounding box. From the tracker predicted bounding box, we generate a list of adversarial bounding boxes and compute the adversarial loss for those bounding boxes. Experimental results demonstrate that our simple yet effective attack outperforms existing attacks against several robust transformer trackers, including TransT-M, ROMTrack, and MixFormer, on popular benchmark tracking datasets such as GOT-10k, UAV123, and VOT2022STS.
2024-11-26
ArXiv (prépublication)
arxiv.org
arxiv.org
Tracing Optimization for Performance Modeling and Regression Detection
Kaveh Shahedi
Heng Li
Maxime Lamothe
Foutse Khomh
Software performance modeling plays a crucial role in developing and maintaining software systems. A performance model analytically describe… (voir plus)s the relationship between the performance of a system and its runtime activities. This process typically examines various aspects of a system's runtime behavior, such as the execution frequency of functions or methods, to forecast performance metrics like program execution time. By using performance models, developers can predict expected performance and thereby effectively identify and address unexpected performance regressions when actual performance deviates from the model's predictions. One common and precise method for capturing performance behavior is software tracing, which involves instrumenting the execution of a program, either at the kernel level (e.g., system calls) or application level (e.g., function calls). However, due to the nature of tracing, it can be highly resource-intensive, making it impractical for production environments where resources are limited. In this work, we propose statistical approaches to reduce tracing overhead by identifying and excluding performance-insensitive code regions, particularly application-level functions, from tracing while still building accurate performance models that can capture performance degradations. By selecting an optimal set of functions to be traced, we can construct optimized performance models that achieve an R-2 score of up to 99% and, sometimes, outperform full tracing models (models using non-optimized tracing data), while significantly reducing the tracing overhead by more than 80% in most cases. Our optimized performance models can also capture performance regressions in our studied programs effectively, demonstrating their usefulness in real-world scenarios. Our approach is fully automated, making it ready to be used in production environments with minimal human effort.
2024-11-26
ArXiv (prépublication)
arxiv.org
arxiv.org
Evaluating the effectiveness of the Smart About Meds (SAM) mobile application among patients discharged from hospital: protocol of a randomised controlled trial
Robyn Tamblyn
Bettina Habib
David Buckeridge
Daniala L Weir
Elizaveta Frolova
Rolan Alattar
Jessica Rogozinsky
Caroline Beauchamp
Rosalba Pupo
Susan J Bartlett
Emily McDonald
2024-11-24
BMJ Open (publié)
doi.org
Gaps Between Research and Practice When Measuring Representational Harms Caused by LLM-Based Systems
Emma Harvey
Emily Sheng
Su Lin Blodgett
Alexandra Chouldechova
Jean Garcia-Gathright
Alexandra Olteanu
Hanna Wallach
To facilitate the measurement of representational harms caused by large language model (LLM)-based systems, the NLP research community has p… (voir plus)roduced and made publicly available numerous measurement instruments, including tools, datasets, metrics, benchmarks, annotation instructions, and other techniques. However, the research community lacks clarity about whether and to what extent these instruments meet the needs of practitioners tasked with developing and deploying LLM-based systems in the real world, and how these instruments could be improved. Via a series of semi-structured interviews with practitioners in a variety of roles in different organizations, we identify four types of challenges that prevent practitioners from effectively using publicly available instruments for measuring representational harms caused by LLM-based systems: (1) challenges related to using publicly available measurement instruments; (2) challenges related to doing measurement in practice; (3) challenges arising from measurement tasks involving LLM-based systems; and (4) challenges specific to measuring representational harms. Our goal is to advance the development of instruments for measuring representational harms that are well-suited to practitioner needs, thus better facilitating the responsible development and deployment of LLM-based systems.
2024-11-23
ArXiv (prépublication)
arxiv.org
arxiv.org
Caustics: A Python Package for Accelerated Strong Gravitational Lensing Simulations
Connor Stone
Alexandre Adam
Adam Coogan
M. J. Yantovski-Barth
Andreas Filipp
Landung Setiawan
Cordero Core
Ronan Legin
Charles Wilson
Gabriel Missael Barco
Yashar Hezaveh
Laurence Perreault-Levasseur
2024-11-22
Journal of Open Source Software (publié)
doi.org
arxiv.org
"It was 80% me, 20% AI": Seeking Authenticity in Co-Writing with Large Language Models
Angel Hsing-Chi Hwang
Q. V. Liao
Su Lin Blodgett
Alexandra Olteanu
Adam Trischler
2024-11-20
ArXiv (prépublication)
arxiv.org
arxiv.org
Effectiveness of primary repair for low anorectal malformations in Uganda.
Felix Oyania
Sarah Ullrich
Zane Hellmann
Caroline Q. Stephens
Meera Kotagal
Sarah Jane Commander
Amy M. Shui
Martin Situma
Charles Newton Odongo
Olivia Kituuka
Francis Bajunirwe
Doruk Ozgediz
Dan Poenaru
2024-11-19
Pediatric Surgery International (publié)
doi.org