Smoke and mirrors in causal downstream tasks - Cadei, Riccardo; Lindorfer, Lukas; Cremer, Sylvia; Schmid, Cordelia; Locatello, Francesco (ICML 2024 Workshop AI4Science)
Machine Learning and AI have the potential to transform data-driven scientific discovery, enabling accurate predictions for several scientific phenomena. As many scientific questions are inherently causal, this paper looks at the causal inference task of treatment effect estimation, where the outcome of interest is recorded in high-dimensional observations in a Randomized Controlled Trial (RCT). Despite being the simplest possible causal setting and a perfect fit for deep learning, we theoretically find that many common choices in the literature may lead to biased estimates. To test the practical impact of these considerations, we recorded ISTAnt, the first real-world benchmark for causal inference downstream tasks on high-dimensional observations as an RCT studying how garden ants (Lasius neglectus) respond to microparticles applied onto their colony members by hygienic grooming. Comparing 6 480 models fine-tuned from state-of-the-art visual backbones, we find that the sampling and modeling choices significantly affect the accuracy of the causal estimate, and that classification accuracy is not a proxy thereof. We further validated the analysis, repeating it on a synthetically generated visual data set controlling the causal model. Our results suggest that future benchmarks should carefully consider real downstream scientific questions, especially causal ones. Further, we highlight guidelines for representation learning methods to help answer causal questions in the sciences.

Predicting the geolocation of tweets using transformer models on customized data - Lutsai, Kateryna; Lampert, Christoph (Journal of Spatial Information Science)
This research is aimed to solve the tweet/user geolocation prediction task and provide a flexible methodology for the geo-tagging of textual big data. The suggested approach implements neural networks for natural language processing (NLP) to estimate the location as coordinate pairs (longitude, latitude) and two-dimensional Gaussian Mixture Models (GMMs). The scope of proposed models has been finetuned on a Twitter dataset using pretrained Bidirectional Encoder Representations from Transformers (BERT) as base models. Performance metrics show a median error of fewer than 30 km on a worldwide-level, and fewer than 15 km on the US-level datasets for the models trained and evaluated on text features of tweets' content and metadata context. Our source code and data are available at https://github.com/K4TEL/geo-twitter.git.

Complex rotational dynamics of the neutron star in Hercules X-1 revealed by X-ray polarization - Heyl, Jeremy; Doroshenko, Victor; González-Caniulef, Denis; Caiazzo, Ilaria; Poutanen, Juri; Mushtukov, Alexander; Tsygankov, Sergey S.; Kirmizibayrak, Demet; Bachetti, Matteo; Pavlov, George G.; Forsblom, Sofia V.; Malacaria, Christian; et al. (Nature Astronomy)
In an accreting X-ray pulsar, a neutron star accretes matter from a companion star through an accretion disk. The magnetic field of the rotating neutron star disrupts the inner edge of the disk, funnelling the gas to flow onto the poles on its surface. Hercules X-1 is a prototypical persistent X-ray pulsar about 7 kpc from Earth. Its emission varies on three distinct timescales: the neutron star rotates every 1.2 s, it is eclipsed by its companion each 1.7 d, and the system exhibits a superorbital period of 35 d, which has remained stable since its discovery. Several lines of evidence point to the source of this variation as the precession of the accretion disk or that of the neutron star. Despite the many hints over the past 50 yr, the precession of the neutron star itself has yet not been confirmed or refuted. X-ray polarization measurements (probing the spin geometry of Her X-1) with the Imaging X-ray Polarimetry Explorer suggest that free precession of the neutron star crust sets the 35 d period; this has the important implication that its crust is somewhat asymmetric by a few parts per ten million.

Optimal summary statistics for X-ray polarization - Heyl, Jeremy; González-Caniulef, Denis; Caiazzo, Ilaria (The Open Journal of Astrophysics)
We develop two new highly efficient estimators to measure the polarization (Stokes parameters) in experiments that constrain the position angle of individual photons such as scattering and gas-pixel-detector polarimeters, and analyse in detail a previously proposed estimator. All three of these estimators are at least fifty percent more efficient on typical datasets than the standard estimator used in the field. We present analytic estimates of the variance of these estimators and numerical experiments to verify these estimates. Two of the three estimators can be calculated quickly and directly through summations over the measurements of individual photons.

Intriguing properties of robust classification - Prach, Bernd; Lampert, Christoph (arXiv)
Despite extensive research since the community learned about adversarial examples 10 years ago, we still do not know how to train high-accuracy classifiers that are guaranteed to be robust to small perturbations of their inputs. Previous works often argued that this might be because no classifier exists that is robust and accurate at the same time. However, in computer vision this assumption does not match reality where humans are usually accurate and robust on most tasks of interest. We offer an alternative explanation and show that in certain settings robust generalization is only possible with unrealistically large amounts of data. More precisely we find a setting where a robust classifier exists, it is easy to learn an accurate classifier, yet it requires an exponential amount of data to learn a robust classifier. Based on this theoretical result, we explore how well robust classifiers generalize on datasets such as CIFAR-10. We come to the conclusion that on this datasets, the limitation of current robust models also lies in the generalization, and that they require a lot of data to do well on the test set. We also show that the problem is not in the expressiveness or generalization capabilities of current architectures, and that there are low magnitude features in the data which are useful for non-robust generalization but are not available for robust classifiers.

Banded square root matrix factorization for differentially private model training - Kalinin, Nikita; Lampert, Christoph (38th Annual Conference on Neural Information Processing Systems)
Current state-of-the-art methods for differentially private model training are based on matrix factorization techniques. However, these methods suffer from high computational overhead because they require numerically solving a demanding optimization problem to determine an approximately optimal factorization prior to the actual model training. In this work, we present a new matrix factorization approach, BSR, which overcomes this computational bottleneck. By exploiting properties of the standard matrix square root, BSR allows to efficiently handle also large-scale problems. For the key scenario of stochastic gradient descent with momentum and weight decay, we even derive analytical expressions for BSR that render the computational overhead negligible. We prove bounds on the approximation quality that hold both in the centralized and in the federated learning setting. Our numerical experiments demonstrate that models trained using BSR perform on par with the best existing methods, while completely avoiding their computational overhead.

Average gradient outer product as a mechanism for deep neural collapse - Beaglehole, Daniel; Súkeník, Peter; Mondelli, Marco; Belkin, Mikhail (38th Annual Conference on Neural Information Processing Systems)
Deep Neural Collapse (DNC) refers to the surprisingly rigid structure of the data representations in the final layers of Deep Neural Networks (DNNs). Though the phenomenon has been measured in a variety of settings, its emergence is typically explained via data-agnostic approaches, such as the unconstrained features model. In this work, we introduce a data-dependent setting where DNC forms due to feature learning through the average gradient outer product (AGOP). The AGOP is defined with respect to a learned predictor and is equal to the uncentered covariance matrix of its input-output gradients averaged over the training dataset. The Deep Recursive Feature Machine (Deep RFM) is a method that constructs a neural network by iteratively mapping the data with the AGOP and applying an untrained random feature map. We demonstrate empirically that DNC occurs in Deep RFM across standard settings as a consequence of the projection with the AGOP matrix computed at each layer. Further, we theoretically explain DNC in Deep RFM in an asymptotic setting and as a result of kernel learning. We then provide evidence that this mechanism holds for neural networks more generally. In particular, we show that the right singular vectors and values of the weights can be responsible for the majority of within-class variability collapse for DNNs trained in the feature learning regime. As observed in recent work, this singular structure is highly correlated with that of the AGOP.

Neural collapse versus low-rank bias: Is deep neural collapse really optimal? - Súkeník, Peter; Lampert, Christoph; Mondelli, Marco (38th Annual Conference on Neural Information Processing Systems)
Deep neural networks (DNNs) exhibit a surprising structure in their final layer known as neural collapse (NC), and a growing body of works has currently investigated the propagation of neural collapse to earlier layers of DNNs – a phenomenon called deep neural collapse (DNC). However, existing theoretical results are restricted to special cases: linear models, only two layers or binary classification. In contrast, we focus on non-linear models of arbitrary depth in multi-class classification and reveal a surprising qualitative shift. As soon as we go beyond two layers or two classes, DNC stops being optimal for the deep unconstrained features model (DUFM) – the standard theoretical framework for the analysis of collapse. The main culprit is a low-rank bias of multi-layer regularization schemes: this bias leads to optimal solutions of even lower rank than the neural collapse. We support our theoretical findings with experiments on both DUFM and real data, which show the emergence of the low-rank structure in the solution found by gradient descent.

ISTAnt - Cadei, Riccardo; Locatello, Francesco; Cremer, Sylvia M; Lindorfer, Lukas; Schmid, Cordelia
ISTAnt is a new ecological dataset for social immunity and represents the first real-world benchmark for causal inference downstream tasks on high-dimensional observations. It analyzes grooming behavior in the ant Lasius neglectus in groups of three worker ants. The workers for the experiment were obtained from their laboratory stock colony, which had been collected from the field in 2022 in the Botanical Garden Jena, Germany. Ant collection and all experimental work were performed in compliance with international, national and institutional regulations and ethical guidelines. For the experiment, the body surface of one of the three ants was treated with a suspension of either of two microparticle types (diameter ~5 µm) to induce grooming by the two nestmates, which were individually color-coded by application of a dot of blue or orange paint, respectively. The three ants were housed in small plastic containers (diameter 28mm, height 30mm) with moistened, plastered ground and the interior walls covered with PTFE (polytetrafluoroethane) to hamper climbing by the ants. Filming occurred in a temperature- and humidity-controlled room at 23°C within a custom-made filming box with controlled lighting and ventilation conditions. We set up nine ant groups at a time (always containing both treatments) and placed them randomly on positions 1-9 marked on the floor in a 3x3 grid, about 3mm from each other. The experiment was performed on two consecutive days. Videos were acquired using a USB camera (FLIR blackfly S BFS-U3-120S4C, Teledyne FLIR) with a high-performance lens (HP Series 25mm Focal Length, Edmund optics 86-572) in OBS studio 29.0.0 \citep{bailey2017obs} at a framerate of 30 FPS and a resolution of 2500x2500 pixels. From each original video (105x105 mm), we generated nine individual videos .mkv (each ~32x32 mm, 770x770 pixels) by determining exact coordinates per container from one frame in GIMP 2.10.36 and cropping of the videos with FFmpeg 6.1.1. Annotation was performed over two consecutive days by three observers who had not been involved in the experimental setup or recording and were unaware of the treatment assignments to ensure bias-free behavioral annotation. They annotated the behavior of the ants during video observations, using custom-made software that saves the start and end frames of behaviors marked in a .csv file (see 'annotations' folder). In one of the videos, one of the nestmates' legs got inadvertently stuck to its body surface during the color-coding, interfering with its behavior, so the video was discarded. This left 44 videos from 5 independent setups (n=24 of treatment 1 and n=20 of treatment 2) of 10 minutes each for a total of 792 000 annotated frames (see 'video' folder). For each video, we provide the following information: the number of the set to which it belongs (1-5); the number of the position within the set reflecting the position of the ant group under the camera (1-9), for which we also provide ‘coordinates’ in the 3x3 grid (taking values -1/0/1 for both X and Y axis); treatment (1 or 2); the hour of the day when the recording was started (in 24h CEST); experimental day (A or B); the top left coordinate of the cropping square from the original video (CropX/CropY); the person annotating the video (given as A, B, C); the date of annotation (1: first day, 2: second day) and in which order the videos were annotated by each person, both reflecting a possible training effect of the person (see 'experiments_settings.csv' file).

Improved convergence of score-based diffusion models via prediction-correction - Pedrotti, Francesco; Maas, Jan; Mondelli, Marco (Transactions on Machine Learning Research)
Score-based generative models (SGMs) are powerful tools to sample from complex data distributions. Their underlying idea is to (i) run a forward process for time T1 by adding noise to the data, (ii) estimate its score function, and (iii) use such estimate to run a reverse process. As the reverse process is initialized with the stationary distribution of the forward one, the existing analysis paradigm requires T1→∞. This is however problematic: from a theoretical viewpoint, for a given precision of the score approximation, the convergence guarantee fails as T1 diverges; from a practical viewpoint, a large T1 increases computational costs and leads to error propagation. This paper addresses the issue by considering a version of the popular predictor-corrector scheme: after running the forward process, we first estimate the final distribution via an inexact Langevin dynamics and then revert the process. Our key technical contribution is to provide convergence guarantees which require to run the forward process only for a fixed finite time T1. Our bounds exhibit a mild logarithmic dependence on the input dimension and the subgaussian norm of the target distribution, have minimal assumptions on the data, and require only to control the L2 loss on the score approximation, which is the quantity minimized in practice.

Optimal Transport on Quantum Structures
The flourishing theory of classical optimal transport concerns mass transportation at minimal cost. This book introduces the reader to optimal transport on quantum structures, i.e., optimal transportation between quantum states and related non-commutative concepts of mass transportation. It contains lecture notes on classical optimal transport and Wasserstein gradient flows dynamics and quantum optimal transport quantum couplings and many-body problems quantum channels and qubits These notes are based on lectures given by the authors at the "Optimal Transport on Quantum Structures" School held at the Erdös Center in Budapest in the fall of 2022. The lecture notes are complemented by two survey chapters presenting the state of the art in different research areas of non-commutative optimal transport.

Modular completely Dirichlet forms as squares of derivations - Wirth, Melchior (International Mathematics Research Notices)
We prove that certain closable derivations on the GNS Hilbert space associated with a non-tracial weight on a von Neumann algebra give rise to GNS-symmetric semigroups of contractive completely positive maps on the von Neumann algebra.

Assessing the precision of morphogen gradients in neural tube development - Zagorski, Marcin; Brandenberg, Nathalie; Lutolf, Matthias; Tkačik, Gašper; Bollenbach, Mark Tobias; Briscoe, James; Kicheva, Anna (Nature Communications)

Measuring stellar surface rotation and activity with the PLATO mission. I. Strategy and application to simulated light curves - Breton, S. N.; Lanza, A. F.; Messina, S.; Pagano, I.; Bugnet, Lisa Annabelle; Corsaro, E.; García, R. A.; Mathur, S.; Santos, A. R. G.; Aigrain, S.; Amard, L.; Brun, A. S.; et al. (Astronomy and Astrophysics)
The Planetary Transits and Oscillations of stars mission (PLATO) will allow us to measure surface rotation and monitor photometric activity of tens of thousands of main sequence solar-type and subgiant stars. This paper is the first of a series dedicated to the preparation of the analysis of stellar surface rotation and photospheric activity with the near-future PLATO data. We describe in this work the strategy that will be implemented in the PLATO pipeline to measure stellar surface rotation, photometric activity, and long-term modulations. The algorithms are applied on both noise-free and noisy simulations of solar-type stars, which include activity cycles, latitudinal differential rotation, and spot evolution. PLATO simulated systematics are included in the noisy light curves. We show that surface rotation periods can be recovered with confidence for most of the stars with only six months of observations and that the recovery rate of the analysis significantly improves as additional observations are collected. This means that the first PLATO data release will already provide a substantial set of measurements for this quantity, with a significant refinement on their quality as the instrument obtains longer light curves. Measuring the Schwabe-like magnetic activity cycle during the mission will require that the same field be observed over a significant timescale (more than four years). Nevertheless, PLATO will provide a vast and robust sample of solar-type stars with constraints on the activity-cycle length. Such a sample is lacking from previous missions dedicated to space photometry.

Expander hierarchies for normalized cuts on graphs - Hanauer, Kathrin; Henzinger, Monika H; Münk, Robin; Räcke, Harald; Vötsch, Maximilian (Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining)
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.

Coupling of twelve putative chromosomal inversions maintains a strong barrier to gene flow between snail ecotypes - Le Moan, Alan; Stankowski, Sean; Rafajlović, Marina; Ortega-Martinez, Olga; Faria, Rui; Butlin, Roger K; Johannesson, Kerstin (Evolution Letters)
Chromosomal rearrangements can lead to the coupling of reproductive barriers, but whether and how they contribute to the completion of speciation remains unclear. Marine snails of the genus Littorina repeatedly form hybrid zones between populations segregating for multiple inversion arrangements, providing opportunities to study their barrier effects. Here, we analyzed 2 adjacent transects across hybrid zones between 2 ecotypes of Littorina fabalis (“large” and “dwarf”) adapted to different wave exposure conditions on a Swedish island. Applying whole-genome sequencing, we found 12 putative inversions on 9 of 17 chromosomes. Nine of the putative inversions reached near differential fixation between the 2 ecotypes, and all were in strong linkage disequilibrium. These inversions cover 20% of the genome and carry 93% of divergent single nucleotide polymorphisms (SNPs). Bimodal hybrid zones in both transects indicated that the 2 ecotypes of Littorina fabalis maintain their genetic and phenotypic integrity following contact. The bimodality reflects the strong coupling between inversion clines and the extension of the barrier effect across the whole genome. Demographic inference suggests that coupling arose during a period of allopatry and has been maintained for > 1,000 generations after secondary contact. Overall, this study shows that the coupling of multiple chromosomal inversions contributes to strong reproductive isolation. Notably, 2 of the putative inversions overlap with inverted genomic regions associated with ecotype differences in a closely related species (Littorina saxatilis), suggesting the same regions, with similar structural variants, repeatedly contribute to ecotype evolution in distinct species.

NMR and single-molecule FRET insights into fast protein motions and their relation to function - Schanda, Paul; Haran, Gilad (Annual Review of Biophysics)
Proteins often undergo large-scale conformational transitions, in which secondary and tertiary structure elements (loops, helices, and domains) change their structures or their positions with respect to each other. Simple considerations suggest that such dynamics should be relatively fast, but the functional cycles of many proteins are often relatively slow. Sophisticated experimental methods are starting to tackle this dichotomy and shed light on the contribution of large-scale conformational dynamics to protein function. In this review, we focus on the contribution of single-molecule Förster resonance energy transfer and nuclear magnetic resonance (NMR) spectroscopies to the study of conformational dynamics. We briefly describe the state of the art in each of these techniques and then point out their similarities and differences, as well as the relative strengths and weaknesses of each. Several case studies, in which the connection between fast conformational dynamics and slower function has been demonstrated, are then introduced and discussed. These examples include both enzymes and large protein machines, some of which have been studied by both NMR and fluorescence spectroscopies.

Fabricable 3D wire art - Tojo, Kenji; Shamir, Ariel; Bickel, Bernd; Umetani, Nobuyuki (SIGGRAPH '24: ACM SIGGRAPH 2024 Conference Papers)
This paper presents a computational method for automatically creating fabricable 3D wire sculptures from various input modalities, including 3D models, images, and even text. There are several challenges to wire art creation. For example, artists must express the desired visual as a sparse wire representation. It is also difficult to manually bend wires in the air without guidance to fabricate the designed 3D curves. Our workflow solves these challenges by using two core techniques. First, we present an algorithm that automatically generates a fabricable 3D curve representation of the target based on a loss function that measures the semantic distance between the rendered curve and the target. The loss function can be defined using different pre-trained vision-language neural networks to generate wire art from different input types. The loss function is then optimized using differentiable rendering specifically targeting 3D parametric curves. Our method can incorporate various fabrication constraints on the wire as additional regularization terms in the optimization process. Second, we present an algorithm to generate a 3D printable jig structure that can be used to fabricate the generated wire path. The major challenge in the jig generation stems from the design of an intersection-free surface mesh for 3D printing, which we address with our inflation algorithm. The experimental results indicate that our method can handle a wider range of input types and can produce physically fabricable wire shapes compared to previous wire generation methods. Various wire arts have been fabricated using our 3D-printed jig to demonstrate its effectiveness in 3D wire bending.

An empirical study of consensus protocols’ DoS resilience - Giuliari, Giacomo; Sonnino, Alberto; Frei, Marc; Streun, Fabio; Kokoris Kogias, Eleftherios; Perrig, Adrian (Proceedings of the 19th ACM Asia Conference on Computer and Communications Security)
With the proliferation of blockchain technology in high-value sectors, consensus protocols are becoming critical infrastructures. The rapid innovation cycle in Byzantine fault tolerant (BFT) consensus protocols has culminated in HotStuff, which provides linear message complexity in the partially synchronous setting. To achieve this, HotStuff leverages a leader that collects, aggregates, and broadcasts the messages of other validators. This paper analyzes the security implications of such approaches in practice, from the perspective of liveness and availability. By implementing attacks in a globally-distributed testbed, we show that state-of-the-art leader-based protocols are vulnerable to denial-of-service (DoS) attacks on the leader. Our attacks, demonstrated on committees of up to 64 validators, manage to disrupt liveness within seconds, using only a few tens of Mbps of attack bandwidth per validator. Crucially, the cost and effectiveness of the attacks are independent of the committee size. Based on the outcome of these experiments, we then propose and test effective mitigations. Our findings show that advancements in both protocol design and network-layer defenses can greatly improve the practical resilience of BFT consensus protocols.

Eight-partitioning points in 3D, and efficiently too - Aronov, Boris; Basit, Abdul; Ramesh, Indu; Tasinato, Gianluca; Wagner, Uli (40th International Symposium on Computational Geometry)
An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).