Search

In recent years, spatio-temporal graph neural networks (GNNs) have attracted considerable interest in the field of time series analysis, due to their ability to capture dependencies among variables and across time points. The objective of the presented systematic literature review is hence to provide a comprehensive overview of the various modeling approaches and application domains of GNNs for time series classification and forecasting. A database search was conducted, and over 150 journal papers were selected for a detailed examination of the current state-of-the-art in the field. This examination is intended to offer to the reader a comprehensive collection of proposed models, links to related source code, available datasets, benchmark models, and fitting results. All this information is hoped to assist researchers in future studies. To the best of our knowledge, this is the first systematic literature review presenting a detailed comparison of the results of current spatio-temporal GNN models in different domains. In addition, in its final part this review discusses current limitations and challenges in the application of spatio-temporal GNNs, such as comparability, reproducibility, explainability, poor information capacity, and scalability.

Automatically crafting test scenarios for REST APIs helps deliver more reliable and trustworthy web-oriented systems. However, current black-box testing approaches rely heavily on the information available in the API's formal documentation, i.e., the OpenAPI Specification (OAS for short). While useful, the OAS mostly covers syntactic aspects of the API (e.g., producer-consumer relations between operations, input value properties, and additional constraints in natural language), and it lacks a deeper understanding of the API business logic. Missing semantics include implicit ordering (logic dependency) between operations and implicit input-value constraints. These limitations hinder the ability of black-box testing tools to generate truly effective test cases automatically. This paper introduces DeepREST, a novel black-box approach for automatically testing REST APIs. It leverages deep reinforcement learning to uncover implicit API constraints, that is, constraints hidden from API documentation. Curiosity-driven learning guides an agent in the exploration of the API and learns an effective order to test its operations. This helps identify which operations to test first to take the API in a testable state and avoid failing API interactions later. At the same time, experience gained on successful API interactions is leveraged to drive accurate input data generation (i.e., what parameters to use and how to pick their values). Additionally, DeepREST alternates exploration with exploitation by mutating successful API interactions to improve test coverage and collect further experience. Our empirical validation suggests that the proposed approach is very effective in achieving high test coverage and fault detection and superior to a state-of-the-art baseline.

Nested conditions are used, among other things, as a graphical way to express first order formulas ruling the applicability of a graph transformation rule to a given match. In this paper, we propose (for the first time) a notion of structural morphism among nested conditions, consistent with the entailment of the corresponding formulas. This reveals a structural weakness of the existing definition of nested conditions, which we overcome by proposing a new notion of span-based nested conditions, embedding the original ones. We also introduce morphisms for the latter, showing that those form a richer structure by organising the various models in a number of categories suitably related by functors.

Homogeneous matroids are characterized by the property that strength equals fractional arboricity, and arise in the study of base modulus [22]. For graphic matroids, Cunningham [9] provided efficient algorithms for calculating graph strength, and also for determining minimum cost reinforcement to achieve a desired strength. This paper extends this latter problem by focusing on two optimal strategies for transforming a matroid into a homogeneous one, by either increasing or decreasing element weights. As an application to graphs, we give algorithms to solve this problem in the context of spanning trees.

There are numerous randomized algorithms to generate spanning trees in a given ambient graph; several target the uniform distribution on trees (UST), while in practice the fastest and most frequently used draw random weights on the edges and then employ a greedy algorithm to choose the minimum-weight spanning tree (MST). Though MST is a workhorse in applications, the mathematical properties of random MST are far less explored than those of UST. In this paper we develop tools for the quantitative study of random MST. We consider the standard case that the weights are drawn i.i.d. from a single distribution on the real numbers, as well as successive generalizations that lead to \emph{product measures}, where the weights are independently drawn from arbitrary distributions.

Graph neural networks form a class of deep learning architectures specifically designed to work with graph-structured data. As such, they share the inherent limitations and problems of deep learning, especially regarding the issues of explainability and trustworthiness. We propose $\mu\mathcal{G}$, an original domain-specific language for the specification of graph neural networks that aims to overcome these issues. The language's syntax is introduced, and its meaning is rigorously defined by a denotational semantics. An equivalent characterization in the form of an operational semantics is also provided and, together with a type system, is used to prove the type soundness of $\mu\mathcal{G}$. We show how $\mu\mathcal{G}$ programs can be represented in a more user-friendly graphical visualization, and provide examples of its generality by showing how it can be used to define some of the most popular graph neural network models, or to develop any custom graph processing application.

We study nested conditions, a generalization of first-order logic to a categorical setting, and provide a tableau-based (semi-decision) procedure for checking (un)satisfiability and finite model generation. This generalizes earlier results on graph conditions. Furthermore we introduce a notion of witnesses, allowing the detection of infinite models in some cases. To ensure completeness, paths in a tableau must be fair, where fairness requires that all parts of a condition are processed eventually. Since the correctness arguments are non-trivial, we rely on coinductive proof methods and up-to techniques that structure the arguments. We distinguish between two types of categories: categories where all sections are isomorphisms, allowing for a simpler tableau calculus that includes finite model generation; in categories where this requirement does not hold, model generation does not work, but we still obtain a sound and complete calculus.

When can two sequential steps performed by a computing device be considered (causally) independent? This is a relevant question for concurrent and distributed systems, since independence means that they could be executed in any order, and potentially in parallel. Equivalences identifying rewriting sequences which differ only for independent steps are at the core of the theory of concurrency of many formalisms. We investigate the issue in the context of the double pushout approach to rewriting in the general setting of adhesive categories. While a consolidated theory exists for linear rules,which can consume, preserve and generate entities, this paper focuses on left-linear rules which may also "merge" parts of the state. This is an apparently minimal, yet technically hard enhancement,since a standard characterisation of independence that - in the linear case - allows one to derive a number of properties, essential in the development of a theory of concurrency, no longer holds. The paper performs an in-depth study of the notion of independence for left-linear rules: it introduces a novel characterisation of independence, identifies well-behaved classes of left-linear rewriting systems,and provides some fundamental results including a Church-Rosser property and the existence of canonical equivalence proofs for concurrent computations. These results properly extends the class of formalisms that can be modelled in the adhesive framework

We provide a worldline representation of the one-loop effective action for a Dirac particle coupled to external scalar, pseudoscalar, vector and axialvector fields. Extending previous work by two of the authors on the pure vector-axialvector case to all four couplings, it allows one to treat the real and the imaginary parts of the effective action in a unified manner, at the price of having a non-Hermitian Hamiltonian. Unlike existing worldline representations, our new worldline action contains terms with an odd number of Grassmann fields, leading to ordering problems that in the worldline formalism are usually encountered only in curved space. Drawing on the highly developed technology for worldline path-integrals in gravity, we employ the Time Slicing regularisation of the path integral which comes about with a specific ``counterterm Lagrangian'', which we calculate once and for all and non-perturbatively, to provide unambiguous rules to treat products of distributions occurring in some diagrams of the one-dimensional worldline theory. We then employ the usual worldline machinery to lay out the rules for the calculation of the effective action itself as well as the corresponding one-loop amplitudes. We test the formalism on the calculation of various heat-kernel coefficients, self energies and scattering amplitudes, including the Higgs decay into two photons or gluons and the PCAC relation. In all cases we find perfect agreement with more established approaches., Comment: 32 pages, 1 figure

Safe road crossing by autonomous wheelchairs can be affected by several environmental factors such as adverse weather conditions influencing the accuracy of artificial vision. Previous studies have addressed experimental evaluation of multi-sensor information fusion to support road-crossing decisions in autonomous wheelchairs. In this study, we focus on the fine-tuning of tracking performance and on its experimental evaluation against outdoor environmental factors such as fog, rain, darkness, etc. It is rather intuitive that those factors can negatively affect the tracking performance; therefore our aim is to provide an approach to quantify their effects in the reference scenario, in order to detect conditions of unacceptable accuracy. In those cases, warnings can be issued and system can be possibly reconfigured to reduce the reputation of less accurate sensors, and thus improve overall safety. Critical situations can be detected by the main sensors or by additional sensors, e.g., light sensors, rain sensors, etc. Results have been achieved by using an available laboratory dataset and by applying appropriate software filters; they show that the approach can be adopted to evaluate video tracking and event detection robustness against outdoor environmental factors in relevant operational scenarios., Comment: Submitted to the "27th IEEE International Conference on Intelligent Transportation Systems"

REST APIs have a pivotal role in accessing protected resources. Despite the availability of security testing tools, mass assignment vulnerabilities are common in REST APIs, leading to unauthorized manipulation of sensitive data. We propose a lightweight approach to mine the REST API specifications and identify operations and attributes that are prone to mass assignment. We conducted a preliminary study on 100 APIs and found 25 prone to this vulnerability. We confirmed nine real vulnerable operations in six APIs., Comment: EASE 2024

In this paper, we study extremal values for the determinant of the weighted graph Laplacian under simple nondegeneracy conditions on the weights. We derive necessary and sufficient conditions for the determinant of the Laplacian to be bounded away from zero and for the existence of a minimizing set of weights. These conditions are given both in terms of properties of random spanning trees and in terms of a type of density on graphs. These results generalize and extend the work of [7].

In this work, we explore the application of modulus in matroid theory, specifically, the modulus of the family of bases of matroids. This study not only recovers various concepts in matroid theory, including the strength, fractional arboricity, and principal partitions, but also offers new insights. In the process, we introduce the concept of a Beurling set. Additionally, our study revisits and provides an alternative approach to two of Edmonds's theorems related to the base packing and base covering problems. This is our stepping stone for establishing Fulkerson modulus duality for the family of bases. Finally, we provide a relationship between the base modulus of matroids and their dual matroids, and a complete understanding of the base $p$-modulus across all values of $p$.

Foundation models have exhibited unprecedented capabilities in tackling many domains and tasks. Models such as CLIP are currently widely used to bridge cross-modal representations, and text-to-image diffusion models are arguably the leading models in terms of realistic image generation. Image generative models are trained on massive datasets that provide them with powerful internal spatial representations. In this work, we explore the potential benefits of such representations, beyond image generation, in particular, for dense visual prediction tasks. We focus on the task of image segmentation, which is traditionally solved by training models on closed-vocabulary datasets, with pixel-level annotations. To avoid the annotation cost or training large diffusion models, we constraint our setup to be zero-shot and training-free. In a nutshell, our pipeline leverages different and relatively small-sized, open-source foundation models for zero-shot open-vocabulary segmentation. The pipeline is as follows: the image is passed to both a captioner model (i.e. BLIP) and a diffusion model (i.e., Stable Diffusion Model) to generate a text description and visual representation, respectively. The features are clustered and binarized to obtain class agnostic masks for each object. These masks are then mapped to a textual class, using the CLIP model to support open-vocabulary. Finally, we add a refinement step that allows to obtain a more precise segmentation mask. Our approach (dubbed FreeSeg-Diff), which does not rely on any training, outperforms many training-based approaches on both Pascal VOC and COCO datasets. In addition, we show very competitive results compared to the recent weakly-supervised segmentation approaches. We provide comprehensive experiments showing the superiority of diffusion model features compared to other pretrained models. Project page: https://bcorrad.github.io/freesegdiff/

Safe road-crossing by self-driving vehicles is a crucial problem to address in smart-cities. In this paper, we introduce a multi-sensor fusion approach to support road-crossing decisions in a system composed by an autonomous wheelchair and a flying drone featuring a robust sensory system made of diverse and redundant components. To that aim, we designed an analytical danger function based on explainable physical conditions evaluated by single sensors, including those using machine learning and artificial vision. As a proof-of-concept, we provide an experimental evaluation in a laboratory environment, showing the advantages of using multiple sensors, which can improve decision accuracy and effectively support safety assessment. We made the dataset available to the scientific community for further experimentation. The work has been developed in the context of an European project named REXASI-PRO, which aims to develop trustworthy artificial intelligence for social navigation of people with reduced mobility., Comment: 14 pages, 8 figures

We focus on a behavioral model, that has been recently proposed in the literature, whose rational can be traced back to the Half-Full/Half-Empty glass metaphor. More precisely, we generalize the Half-Full/Half-Empty approach to the context of positive and negative lotteries and give financial and behavioral interpretations of the Half-Full/Half-Empty parameters. We develop a portfolio selection model based on the Half-Full/Half-Empty strategy, resulting in a nonconvex optimization problem, which, nonetheless, is proven to be equivalent to an alternative Mixed-Integer Linear Programming formulation. By means of the ensuing empirical analysis, based on three real-world datasets, the Half-Full/Half-Empty model is shown to be very versatile by appropriately varying its parameters, and to provide portfolios displaying promising performances in terms of risk and profitability, compared with Prospect Theory, risk minimization approaches and Equally-Weighted portfolios.

The knowledge of Half-Heusler compounds have attracted much attention as materials for thermoelectric applications. In this work, we investigate, using first-principles calculations, the electronic, vibrational, and defect properties of TiXSn (X=Ni, Pd, Pt) half-Heusler compounds. The knowledge of such properties is vital for the understanding and improvement of thermoelectric transport properties of these materials. The band gap of the three compounds increase with the atomic number of the group 10 elements, in agreement with previous findings. The electronic effective masses of the three compounds are similar, while the heavy hole effective mass of TiPtSn is larger than those of the other two materials. Our calculations of the phonon dispersion included the calculation of the LO-TO splitting indicating that TiNiSn has a stronger ionic character and polar scattering of charge carriers by optical phonons in the case of low doping. Calculation of the formation energy of Ni interstitial defect in TiNiSn is very low, in agreement with previous results. Surprisingly, for the Pd interstitial in TiPdSn the formation energy is negative, suggesting that the full-Heusler structure can be more stable than the half-Heusler one. On the other hand, the formation energy of an interstitial in TiPtSn is significantly higher, suggesting smaller effects on both electronic structure and transport properties. The formation energy of all substitutional defects investigated are substantially higher than that of interstitial ones, suggesting that they should occur in very low concentrations., Comment: 7 pages, 7 figures

One of the main properties of modulus on graphs is Fulkerson duality. In this paper, we study Fulkerson duality for spanning tree modulus. We introduce a new notion of Beurling partition, and we identify two important ones, which correspond to the notion of strength and maximum denseness of an arbitrary graph. These special partitions, also give rise to two deflation processes that reveal a hierarchical structure for general graphs. While Fulkerson duality for spanning tree families can be deduced from a well-known result in combinatorics due to Chopra, we give an alternative approach based on a result of Nash-Williams and Tutte. Finally, we introduce the weighted variant of spanning tree modulus.

We show that capacity can be computed with locally Lipschitz functions in locally complete and separable metric spaces. Further, we show that if $(X,d,\mu)$ is a locally complete and separable metric measure space, then continuous functions are dense in the Newtonian space $N^{1,p}(X)$. Here the measure $\mu$ is Borel and is finite and positive on all metric balls. In particular, we don't assume properness of $X$, doubling of $\mu$ or any Poincar\'e inequalities. These resolve, partially or fully, questions posed by a number of authors, including J. Heinonen, A. Bj\"orn and J. Bj\"orn. In contrast to much of the past work, our results apply to locally complete spaces $X$ and dispenses with the frequently used regularity assumptions: doubling, properness, Poincar\'e inequality, Loewner property or quasiconvexity., Comment: 33 pages, edited slightly based on feedback from a referee