Search

The distribution of the incubation period of the novel coronavirus disease that emerged in 2019 (COVID-19) has crucial clinical implications for understanding this disease and devising effective disease-control measures. Qin et al. (2020) designed a cross-sectional and forward follow-up study to collect the duration times between a specific observation time and the onset of COVID-19 symptoms for a number of individuals. They further proposed a mixture forward-incubation-time epidemic model, which is a mixture of an incubation-period distribution and a forward time distribution, to model the collected duration times and to estimate the incubation-period distribution of COVID-19. In this paper, we provide sufficient conditions for the identifiability of the unknown parameters in the mixture forward-incubation-time epidemic model when the incubation period follows a two-parameter distribution. Under the same setup, we propose a likelihood ratio test (LRT) for testing the null hypothesis that the mixture forward-incubation-time epidemic model is a homogeneous exponential distribution. The testing problem is non-regular because a nuisance parameter is present only under the alternative. We establish the limiting distribution of the LRT and identify an explicit representation for it. The limiting distribution of the LRT under a sequence of local alternatives is also obtained. Our simulation results indicate that the LRT has desirable type I errors and powers, and we analyze a COVID-19 outbreak dataset from China to illustrate the usefulness of the LRT., 34 pages, 2 figures, 2 tables

Sliced inverse regression (SIR, Li 1991) is a pioneering work and the most recognized method in sufficient dimension reduction. While promising progress has been made in theory and methods of high-dimensional SIR, two remaining challenges are still nagging high-dimensional multivariate applications. First, choosing the number of slices in SIR is a difficult problem, and it depends on the sample size, the distribution of variables, and other practical considerations. Second, the extension of SIR from univariate response to multivariate is not trivial. Targeting at the same dimension reduction subspace as SIR, we propose a new slicing-free method that provides a unified solution to sufficient dimension reduction with high-dimensional covariates and univariate or multivariate response. We achieve this by adopting the recently developed martingale difference divergence matrix (MDDM, Lee & Shao 2018) and penalized eigen-decomposition algorithms. To establish the consistency of our method with a high-dimensional predictor and a multivariate response, we develop a new concentration inequality for sample MDDM around its population counterpart using theories for U-statistics, which may be of independent interest. Simulations and real data analysis demonstrate the favorable finite sample performance of the proposed method.

Directional tests to compare incomplete undirected graphs are developed in the general context of covariance selection for Gaussian graphical models. The exactness of the underlying saddlepoint approximation is proved for chordal graphs and leads to exact control of the size of the tests, given that the only approximation error involved is due to the numerical calculation of two scalar integrals. Although exactness is not guaranteed for non-chordal graphs, the ability of the saddlepoint approximation to control the relative error leads the directional test to overperform its competitors even in these cases. The accuracy of our proposal is verified by simulation experiments under challenging scenarios, where inference via standard asymptotic approximations to the likelihood ratio test and some of its higher-order modifications fails. The directional approach is used to illustrate the assessment of Markovian dependencies in a dataset from a veterinary trial on cattle. A second example with microarray data shows how to select the graph structure related to genetic anomalies due to acute lymphocytic leukemia.

Blockwise missing data occurs frequently when we integrate multisource or multimodality data where different sources or modalities contain complementary information. In this paper, we consider a high-dimensional linear regression model with blockwise missing covariates and a partially observed response variable. Under this framework, we propose a computationally efficient estimator for the regression coefficient vector based on carefully constructed unbiased estimating equations and a blockwise imputation procedure, and obtain its rate of convergence. Furthermore, building upon an innovative projected estimating equation technique that intrinsically achieves bias-correction of the initial estimator, we propose a nearly unbiased estimator for each individual regression coefficient, which is asymptotically normally distributed under mild conditions. Based on these debiased estimators, asymptotically valid confidence intervals and statistical tests about each regression coefficient are constructed. Numerical studies and application analysis of the Alzheimer's Disease Neuroimaging Initiative data show that the proposed method performs better and benefits more from unsupervised samples than existing methods., Comment: V2: 40 pages, 2 figures. Accepted at Statistica Sinica

In an attempt to improve the utilization efficiency of multi-energy coupling in park-level integrated energy system (PIES), promote wind power consumption and reduce carbon emissions, a low-carbon economic operation optimization model of PIES integrating flexible load and carbon trading mechanism is constructed. Firstly, according to the characteristics of load response, the demand response is divided into four types: which can be shifted, transferred, reduced and replaced. Secondly, the PIES basic architecture is given by considering the combined heat and power generation coupling equipment, new energy and flexible load in the park. Finally, introducing the ladder-type carbon trading mechanism into the system and minimize the total operating cost, the low-carbon economic operation optimization model of PIES is established. The YALMIP toolbox and CPLEX solver are used to solve the example, the simulation results show that the participation of electrical and thermal coupled scheduling and flexible electric or thermal loads can significantly reduce the system operating cost, reduce the load peak-to-valley difference and relieve peak power consumption pressure., Comment: accepted by Energy Reports

The initial alignment provides an accurate attitude for SINS (strapdown inertial navigation system). By further estimating the IMU's bias and misalignment angle, the recursive Bayesian filter is accurate. However, the prior heading error has significant influence on the convergence speed and accuracy. In addition, the accuracy will be limited by its iteration at a single time-step. Coarse alignment method OBA (optimization-based alignment) uses MLE (maximum likelihood estimation) to find the optimal attitude quickly. However, few methods consider the IMU bias and misalignment angle, which will reduce the attitude accuracy. In this paper, a unified method based on FGO (Factor graph optimization) and IBF (inertial base frame) is proposed. The attitude is estimated by MLE, IMU bias and misalignment angle are estimated by MAP estimation. The state of all time steps is optimized together to further improve the accuracy. Physical experiments on the rotation MEMS SINS show that the heading accuracy of this method is improved in limited alignment time., 8 pages, This article has been accepted for publication in IEEE Transactions on Industrial Electronics

Single-pixel imaging (SPI) is a novel optical imaging technique by replacing the pixelated sensor array in a conventional camera with a single-pixel detector. In previous works, SPI is usually used for capturing object images or performing image processing tasks. In this work, we propose a SPI scheme for processing other types of data in addition to images. An Ising machine model is implemented optically with SPI for solving combinational optimization problems including number partition and graph maximum cut. Simulated and experimental results show that our proposed scheme can optimize the Hamiltonian function with evolutionary illumination patterns.

Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter $k$, the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized $d$-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Formally, GPIS is defined as follows: GPIS oracle for a $d$-uniform hypergraph $\mathcal{H}$ takes as input $d$ pairwise disjoint non-empty subsets $A_1, \ldots, A_d$ of vertices in $\cal H$ and answers whether there is a hyperedge in $\mathcal{H}$ that intersects each set $A_i$, where $i \in \{1, \, 2, \, \ldots, d\}$. } For $d=2$, the GPIS oracle is nothing but BIS oracle. We show that $d$-Hitting-Set, the hitting set problem for $d$-uniform hypergraphs, can be solved using $\widetilde{\mathcal{O}}_d(k^{d} \log n)$ GPIS queries. Additionally, we also showed that $d$-Decesion-Hitting-Set, the decision version of $d$-Hitting-Set can be solved with $\widetilde{\mathcal{O}}_d\left( \min \left\{ k^d\log n, k^{2d^2} \right\} \right)$ {\sc GPIS} queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves $d$-Decesion-Hitting-Set requires $\Omega \left( \binom{k+d}{d} \right)$ GPIS queries., Comment: 22 pages. A preliminary version has appeared in ISAAC'19 and the full version has been accepted in JCSS

Motivated by results on the rationality of equivariant Hilbert series of some hierarchical models in algebraic statistics we introduce the Segre product of formal languages and apply it to establish rationality of equivariant Hilbert series in new cases. To this end we show that the Segre product of two regular languages is again regular. We also prove that every filtration of algebras given as a tensor product of families of algebras with rational equivariant Hilbert series has a rational equivariant Hilbert series. The term equivariant is used broadly to include the action of the monoid of nonnegative integers by shifting variables. Furthermore, we exhibit a filtration of shift invariant monomial algebras that has a rational equivariant Hilbert series, but whose presentation ideals do not stabilize., 26 pages, comments are welcome!

Let $G$ be a connected graph. The eccentricity of a path $P$, denoted by ecc$_G(P)$, is the maximum distance from $P$ to any vertex in $G$. In the \textsc{Central path} (CP) problem our aim is to find a path of minimum eccentricity. This problem was introduced by Cockayne et al., in 1981, in the study of different centrality measures on graphs. They showed that CP can be solved in linear time in trees, but it is known to be NP-hard in many classes of graphs such as chordal bipartite graphs, planar 3-connected graphs, split graphs, etc. We investigate the path eccentricity of a connected graph~$G$ as a parameter. Let pe$(G)$ denote the value of ecc$_G(P)$ for a central path $P$ of $G$. We obtain tight upper bounds for pe$(G)$ in some graph classes. We show that pe$(G) \leq 1$ on biconvex graphs and that pe$(G) \leq 2$ on bipartite convex graphs. Moreover, we design algorithms that find such a path in linear time. On the other hand, by investigating the longest paths of a graph, we obtain tight upper bounds for pe$(G)$ on general graphs and $k$-connected graphs. Finally, we study the relation between a central path and a longest path in a graph. We show that on trees, and bipartite permutation graphs, a longest path is also a central path. Furthermore, for superclasses of these graphs, we exhibit counterexamples for this property.

For unweighted graphs, finding isometric embeddings is closely related to decompositions of $G$ into Cartesian products of smaller graphs. When $G$ is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of $G$. When $G$ is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of $G$. Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph $G$, where $G$ satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any $m$-edge, $n$-vertex graph with positive integer edge weights can be factored in $O(m^2)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O(m^2+n^2\log\log n)$ time. We also show that a pseudofactorization for such a graph can be computed in $O(mn)$ time, plus the time to solve APSP, resulting in an $O(mn+n^2\log\log n)$ running time., Comment: 37 pages, 10 figures

In this paper, we consider the contextual variant of the MNL-Bandit problem. More specifically, we consider a dynamic set optimization problem, where a decision-maker offers a subset (assortment) of products to a consumer and observes the response in every round. Consumers purchase products to maximize their utility. We assume that a set of attributes describe the products, and the mean utility of a product is linear in the values of these attributes. We model consumer choice behavior using the widely used Multinomial Logit (MNL) model and consider the decision maker problem of dynamically learning the model parameters while optimizing cumulative revenue over the selling horizon $T$. Though this problem has attracted considerable attention in recent times, many existing methods often involve solving an intractable non-convex optimization problem. Their theoretical performance guarantees depend on a problem-dependent parameter which could be prohibitively large. In particular, existing algorithms for this problem have regret bounded by $O(\sqrt{\kappa d T})$, where $\kappa$ is a problem-dependent constant that can have an exponential dependency on the number of attributes. In this paper, we propose an optimistic algorithm and show that the regret is bounded by $O(\sqrt{dT} + \kappa)$, significantly improving the performance over existing methods. Further, we propose a convex relaxation of the optimization step, which allows for tractable decision-making while retaining the favourable regret guarantee., Comment: Accepted to be published at Elsevier European Journal of Operational Research (EJOR)

We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the number of asymmetric edges in a given minimum spanning arborescence. Both algorithms are also stated in the form of additive lossy kernelizations, which allows to combine them with known polynomial time approximations for ATSP. Further, we combine them with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. We complement our results by experimental evaluations, which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.

We describe a practical algorithm for computing normal forms for semigroups and monoids with finite presentations satisfying so-called small overlap conditions. Small overlap conditions are natural conditions on the relations in a presentation, which were introduced by J. H. Remmers and subsequently studied extensively by M. Kambites. Presentations satisfying these conditions are ubiquitous; Kambites showed that a randomly chosen finite presentation satisfies the $C(4)$ condition with probability tending to 1 as the sum of the lengths of relation words tends to infinity. Kambites also showed that several key problems for finitely presented semigroups and monoids are tractable in $C(4)$ monoids: the word problem is solvable in $O(\min\{|u|, |v|\})$ time in the size of the input words $u$ and $v$; the uniform word problem for $\langle A|R\rangle$ is solvable in $O(N ^ 2 \min\{|u|, |v|\})$ where $N$ is the sum of the lengths of the words in $R$; and a normal form for any given word $u$ can be found in $O(|u|)$ time. Although Kambites' algorithm for solving the word problem in $C(4)$ monoids is highly practical, it appears that the coefficients in the linear time algorithm for computing normal forms are too large in practice. In this paper, we present an algorithm for computing normal forms in $C(4)$ monoids that has time complexity $O(|u| ^ 2)$ for input word $u$, but where the coefficients are sufficiently small to allow for practical computation. Additionally, we show that the uniform word problem for small overlap monoids can be solved in $O(N \min\{|u|, |v|\})$ time., Comment: 31 pages, 6 figures (some further minor corrections from the referee are resolved, to appear in Journal of Algebra)

A $k$-edge-weighting of $G$ is a mapping $\omega:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting of $G$ naturally induces a vertex-colouring $\sigma_{\omega}:V(G)\longrightarrow \mathbb{N}$ given by$\sigma_{\omega}(v)=\sum_{u\in N_G(v)}\omega(vu)$ for every $v\in V(G)$. The edge-weighting $\omega$ is neighbour sum distinguishing if it yields a proper vertex-colouring $\sigma_{\omega}$, \emph{i.e.}, $\sigma_{\omega}(u)\neq \sigma_{\omega}(v)$ for every edge $uv$ of $G$.We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(\Delta(G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.

This paper proposes a novel kernel-based optimization scheme to handle tasks in the analysis, e.g., signal spectral estimation and single-channel source separation of 1D non-stationary oscillatory data. The key insight of our optimization scheme for reconstructing the time-frequency information is that when a nonparametric regression is applied on some input values, the output regressed points would lie near the oscillatory pattern of the oscillatory 1D signal only if these input values are a good approximation of the ground-truth phase function. In this work, Gaussian Process (GP) is chosen to conduct this nonparametric regression: the oscillatory pattern is encoded as the Pattern-inducing Points (PiPs) which act as the training data points in the GP regression; while the targeted phase function is fed in to compute the correlation kernels, acting as the testing input. Better approximated phase function generates more precise kernels, thus resulting in smaller optimization loss error when comparing the kernel-based regression output with the original signals. To the best of our knowledge, this is the first algorithm that can satisfactorily handle fully non-stationary oscillatory data, close and crossover frequencies, and general oscillatory patterns. Even in the example of a signal {produced by slow variation in the parameters of a trigonometric expansion}, we show that PiPs admits competitive or better performance in terms of accuracy and robustness than existing state-of-the-art algorithms.

Traditional machine learning techniques have been widely used to establish the trust management systems. However, the scale of training dataset can significantly affect the security performances of the systems, while it is a great challenge to detect malicious nodes due to the absence of labeled data regarding novel attacks. To address this issue, this paper presents a generative adversarial network (GAN) based trust management mechanism for Industrial Wireless Sensor Networks (IWSNs). First, type-2 fuzzy logic is adopted to evaluate the reputation of sensor nodes while alleviating the uncertainty problem. Then, trust vectors are collected to train a GAN-based codec structure, which is used for further malicious node detection. Moreover, to avoid normal nodes being isolated from the network permanently due to error detections, a GAN-based trust redemption model is constructed to enhance the resilience of trust management. Based on the latest detection results, a trust model update method is developed to adapt to the dynamic industrial environment. The proposed trust management mechanism is finally applied to secure clustering for reliable and real-time data transmission, and simulation results show that it achieves a high detection rate up to 96%, as well as a low false positive rate below 8%.

Neural closure models have recently been proposed as a method for efficiently approximating small scales in multiscale systems with neural networks. The choice of loss function and associated training procedure has a large effect on the accuracy and stability of the resulting neural closure model. In this work, we systematically compare three distinct procedures: "derivative fitting", "trajectory fitting" with discretise-then-optimise, and "trajectory fitting" with optimise-then-discretise. Derivative fitting is conceptually the simplest and computationally the most efficient approach and is found to perform reasonably well on one of the test problems (Kuramoto-Sivashinsky) but poorly on the other (Burgers). Trajectory fitting is computationally more expensive but is more robust and is therefore the preferred approach. Of the two trajectory fitting procedures, the discretise-then-optimise approach produces more accurate models than the optimise-then-discretise approach. While the optimise-then-discretise approach can still produce accurate models, care must be taken in choosing the length of the trajectories used for training, in order to train the models on long-term behaviour while still producing reasonably accurate gradients during training. Two existing theorems are interpreted in a novel way that gives insight into the long-term accuracy of a neural closure model based on how accurate it is in the short term., Comment: 24 pages and 9 figures. Submitted to Computers and Mathematics with Applications. For associated code, see https://github.com/HugoMelchers/neural-closure-models

Human trafficking, the commercial exploitation of individuals, is a gross violation of human rights and harms societies, economies, health and development. The related disciplines of Operations Management (OM), Analytics, and Operations Research (OR) are uniquely positioned to support trafficking prevention and intervention efforts by efficiently evaluating a plethora of decision alternatives, and providing quantitative, actionable insights. As operations and analytical efforts in the counter-trafficking field emerge, it is imperative to grasp subtle yet distinctive nuances associated with human trafficking. This note is intended to inform those practitioners working in the field by highlighting key features of human trafficking activity. We grouped nine themes around three broad categories: (1) representation of human trafficking, (2) consideration of survivors and communities, and (3) analytics related. These insights are derived from our collective experience in working in this area and substantiated by domain expertise.

In this work we propose an extension of physics informed supervised learning strategies to parametric partial differential equations. Indeed, even if the latter are indisputably useful in many applications, they can be computationally expensive most of all in a real-time and many-query setting. Thus, our main goal is to provide a physics informed learning paradigm to simulate parametrized phenomena in a small amount of time. The physics information will be exploited in many ways, in the loss function (standard physics informed neural networks), as an augmented input (extra feature employment) and as a guideline to build an effective structure for the neural network (physics informed architecture). These three aspects, combined together, will lead to a faster training phase and to a more accurate parametric prediction. The methodology has been tested for several equations and also in an optimal control framework.

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid =_3 \right)$, where $f$ is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of $f$. The constraint function can take both positive and negative values, allowing for cancellations. The dichotomy extends easily to rational valued functions of the same type. In addition, we discover a new phenomenon: there is a set $\mathcal{F}$ with the property that for every $f \in \mathcal{F}$ the problem $\operatorname{Holant}\left(f\mid =_3 \right)$ is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by $\left[\begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix}\right]$ to FKT together with an independent global argument., Accepted by FCT 2021

We study the average number $\mathcal{A}(G)$ of colors in the non-equivalent colorings of a graph $G$. We show some general properties of this graph invariant and determine its value for some classes of graphs. We then conjecture several lower bounds on $\mathcal{A}(G)$ and prove that these conjectures are true for specific classes of graphs such as triangulated graphs and graphs with maximum degree at most 2., 20 pages, 2 figures

We offer a new perspective on risk aggregation with FGM copulas. Along the way, we discover new results and revisit existing ones, providing simpler formulas than one can find in the existing literature. This paper builds on two novel representations of FGM copulas based on symmetric multivariate Bernoulli distributions and order statistics. First, we detail families of multivariate distributions with closed-form solutions for the cumulative distribution function or moments of the aggregate random variables. We order aggregate random variables under the convex order and provide methods to compute the cumulative distribution function of aggregate rvs when the marginals are discrete. Finally, we discuss risk-sharing and capital allocation, providing numerical examples for each.

The growing complexity of spatial and structural information in 3D data makes data inspection and visualization a challenging task. We describe a method to create a planar embedding of 3D treelike structures using their skeleton representations. Our method maintains the original geometry, without overlaps, to the best extent possible, allowing exploration of the topology within a single view. We present a novel camera view generation method which maximizes the visible geometric attributes (segment shape and relative placement between segments). Camera views are created for individual segments and are used to determine local bending angles at each node by projecting them to 2D. The final embedding is generated by minimizing an energy function (the weights of which are user adjustable) based on branch length and the 2D angles, while avoiding intersections. The user can also interactively modify segment placement within the 2D embedding, and the overall embedding will update accordingly. A global to local interactive exploration is provided using hierarchical camera views that are created for subtrees within the structure. We evaluate our method both qualitatively and quantitatively and demonstrate our results by constructing planar visualizations of line data (traced neurons) and volume data (CT vascular and bronchial data).

The California Consumer Privacy Act (CCPA) provides California residents with a range of enhanced privacy protections and rights. Our research investigated the extent to which Android app developers comply with the provisions of the CCPA that require them to provide consumers with accurate privacy notices and respond to "verifiable consumer requests" (VCRs) by disclosing personal information that they have collected, used, or shared about consumers for a business or commercial purpose. We compared the actual network traffic of 109 apps that we believe must comply with the CCPA to the data that apps state they collect in their privacy policies and the data contained in responses to "right to know" requests that we submitted to the app's developers. Of the 69 app developers who substantively replied to our requests, all but one provided specific pieces of personal data (as opposed to only categorical information). However, a significant percentage of apps collected information that was not disclosed, including identifiers (55 apps, 80%), geolocation data (21 apps, 30%), and sensory data (18 apps, 26%) among other categories. We discuss improvements to the CCPA that could help app developers comply with "right to know" requests and other related regulations., Appears in Issue 3 of 23rd Privacy Enhancing Technologies Symposium (PETS 23)

We propose a survey of the research contributions on the field of Educational Timetabling with a specific focus on "standard" formulations and the corresponding benchmark instances. We identify six of such formulations and we discuss their features, pointing out their relevance and usability. Other available formulations and datasets are also reviewed and briefly discussed. Subsequently, we report the main state-of-the-art results on the selected benchmarks, in terms of solution quality (upper and lower bounds), search techniques, running times, statistical distributions, and other side settings.

In this work, we present a novel method called WSDesc to learn 3D local descriptors in a weakly supervised manner for robust point cloud registration. Our work builds upon recent 3D CNN-based descriptor extractors, which leverage a voxel-based representation to parameterize local geometry of 3D points. Instead of using a predefined fixed-size local support in voxelization, we propose to learn the optimal support in a data-driven manner. To this end, we design a novel differentiable voxelization layer that can back-propagate the gradient to the support size optimization. To train the extracted descriptors, we propose a novel registration loss based on the deviation from rigidity of 3D transformations, and the loss is weakly supervised by the prior knowledge that the input point clouds have partial overlap, without requiring ground-truth alignment information. Through extensive experiments, we show that our learned descriptors yield superior performance on existing geometric registration benchmarks., Comment: To appear in IEEE TVCG

Ensembles of networks arise in various fields where multiple independent networks are observed on the same set of nodes, for example, a collection of brain networks constructed on the same brain regions for different individuals. However, there are few models that describe both the variations and characteristics of networks in an ensemble at the same time. In this paper, we propose to model the ensemble of networks using a Dirichlet Process Mixture of Exponential Random Graph Models (DPM-ERGMs), which divides the ensemble into different clusters and models each cluster of networks using a separate Exponential Random Graph Model (ERGM). By employing a Dirichlet process mixture, the number of clusters can be determined automatically and changed adaptively with the data provided. Moreover, in order to perform full Bayesian inference for DPM-ERGMs, we employ the intermediate importance sampling technique inside the Metropolis-within-slice sampling scheme, which addressed the problem of sampling from the intractable ERGMs on an infinite sample space. We also demonstrate the performance of DPM-ERGMs with both simulated and real datasets.

Catastrophic forgetting (CF) happens whenever a neural network overwrites past knowledge while being trained on new tasks. Common techniques to handle CF include regularization of the weights (using, e.g., their importance on past tasks), and rehearsal strategies, where the network is constantly re-trained on past data. Generative models have also been applied for the latter, in order to have endless sources of data. In this paper, we propose a novel method that combines the strengths of regularization and generative-based rehearsal approaches. Our generative model consists of a normalizing flow (NF), a probabilistic and invertible neural network, trained on the internal embeddings of the network. By keeping a single NF throughout the training process, we show that our memory overhead remains constant. In addition, exploiting the invertibility of the NF, we propose a simple approach to regularize the network's embeddings with respect to past tasks. We show that our method performs favorably with respect to state-of-the-art approaches in the literature, with bounded computational power and memory overheads., Comment: arXiv admin note: substantial text overlap with arXiv:2007.02443

Let $\mathcal{G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of $\mathcal{G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to $\mathcal{G}.$ We denote by $\mathcal{A}_k (\mathcal{G})$ the set of all graphs that are $k$-apices of $\mathcal{G}.$ We prove that every graph in the obstruction set of $\mathcal{A}_k (\mathcal{G}),$ i.e., the minor-minimal set of graphs not belonging to $\mathcal{A}_k (\mathcal{G}),$ has size at most $2^{2^{2^{2^{\mathsf{poly}(k)}}}},$ where $\mathsf{poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of $\mathcal{G}.$ This bound drops to $2^{2^{\mathsf{poly}(k)}}$ when $\mathcal{G}$ excludes some apex graph as a minor., Comment: 48 pages and 12 figures. arXiv admin note: text overlap with arXiv:2004.12692

Steady-state visual evoked potential (SSVEP) is one of the most commonly used control signal in the brain-computer interface (BCI) systems. However, the conventional spatial filtering methods for SSVEP classification highly depend on the subject-specific calibration data. The need for the methods that can alleviate the demand for the calibration data become urgent. In recent years, developing the methods that can work in inter-subject classification scenario has become a promising new direction. As the popular deep learning model nowadays, Transformer has excellent performance and has been used in EEG signal classification tasks. Therefore, in this study, we propose a deep learning model for SSVEP classification based on Transformer structure in inter-subject classification scenario, termed as SSVEPformer, which is the first application of the transformer to the classification of SSVEP. Inspired by previous studies, the model adopts the frequency spectrum of SSVEP data as input, and explores the spectral and spatial domain information for classification. Furthermore, to fully utilize the harmonic information, an extended SSVEPformer based on the filter bank technology (FB-SSVEPformer) is proposed to further improve the classification performance. Experiments were conducted using two open datasets (Dataset 1: 10 subjects, 12-class task; Dataset 2: 35 subjects, 40-class task) in the inter-subject classification scenario. The experimental results show that the proposed models could achieve better results in terms of classification accuracy and information transfer rate, compared with other baseline methods. The proposed model validates the feasibility of deep learning models based on Transformer structure for SSVEP classification task, and could serve as a potential model to alleviate the calibration procedure in the practical application of SSVEP-based BCI systems.

We present a differentiable formulation of rigid-body contact dynamics for objects and robots represented as compositions of convex primitives. Existing optimization-based approaches simulating contact between convex primitives rely on a bilevel formulation that separates collision detection and contact simulation. These approaches are unreliable in realistic contact simulation scenarios because isolating the collision detection problem introduces contact location non-uniqueness. Our approach combines contact simulation and collision detection into a unified single-level optimization problem. This disambiguates the collision detection problem in a physics-informed manner. Compared to previous differentiable simulation approaches, our formulation features improved simulation robustness and a reduction in computational complexity by more than an order of magnitude. We illustrate the contact and collision differentiability on a robotic manipulation task requiring optimization-through-contact. We provide a numerically efficient implementation of our formulation in the Julia language called Silico.jl.

With the proliferation of mobile technology and IT development, people can use social network services at any place and anytime. Among many social network mining problems, identifying cohesive subgraphs attract many attentions from different fields due to its numerous applications. Among many cohesive subgraph models, k-core is the most widely used model due to its simple and intuitive structure. In this paper, we formulate (p,n)-core in signed networks by extending k-core. (p,n)-core simultaneously guarantees sufficient internal positive edges and deficient internal negative edges. We formally prove that finding an exact (p,n)-core is NP-hard. Hence, we propose three efficient and effective algorithms to find a solution. Using real-world and synthetic networks, we demonstrate the superiority of our proposed algorithms.

We introduce Private Collection Matching (PCM) problems, in which a client aims to determine whether a collection of sets owned by a server matches their interests. Existing privacy-preserving cryptographic primitives cannot solve PCM problems efficiently without harming privacy. We propose a modular framework that enables designers to build privacy-preserving PCM systems that output one bit: whether a collection of server sets matches the client's set. The communication cost of our protocols scales linearly with the size of the client's set and is independent of the number of server elements. We demonstrate the potential of our framework by designing and implementing novel solutions for two real-world PCM problems: determining whether a dataset has chemical compounds of interest, and determining whether a document collection has relevant documents. Our evaluation shows that we offer a privacy gain with respect to existing works at a reasonable communication and computation cost.

We introduce an extension to local principal component analysis for learning symmetric manifolds. In particular, we use a spectral method to approximate the Lie algebra corresponding to the symmetry group of the underlying manifold. We derive the sample complexity of our method for a variety of manifolds before applying it to various data sets for improved density estimation.

We uncover a new relation between Closeness centrality and the Condorcet principle. We define a Condorcet winner in a graph as a node that compared to any other node is closer to more nodes. In other words, if we assume that nodes vote on a closer candidate, a Condorcet winner would win a two-candidate election against any other node in a plurality vote. We show that Closeness centrality and its random-walk version, Random-Walk Closeness centrality, are the only classic centrality measures that are Condorcet consistent on trees, i.e., if a Condorcet winner exists, they rank it first. While they are not Condorcet consistent in general graphs, we show that Closeness centrality satisfies the Condorcet Comparison property that states that out of two adjacent nodes, the one preferred by more nodes has higher centrality. We show that Closeness centrality is the only regular distance-based centrality with such a property.

Resource provisioning plays a pivotal role in determining the right amount of infrastructure resource to run applications and target the global decarbonization goal. A significant portion of production clusters is now dedicated to long-running applications (LRAs), which are typically in the form of microservices and executed in the order of hours or even months. It is therefore practically important to plan ahead the placement of LRAs in a shared cluster so that the number of compute nodes required by them can be minimized to reduce carbon footprint and lower operational costs. Existing works on LRA scheduling are often application-agnostic, without particularly addressing the constraining requirements imposed by LRAs, such as co-location affinity constraints and time-varying resource requirements. In this paper, we present an affinity-aware resource provisioning approach for deploying large-scale LRAs in a shared cluster subject to multiple constraints, with the objective of minimizing the number of compute nodes in use. We investigate a broad range of solution algorithms which fall into three main categories: Application-Centric, Node-Centric, and Multi-Node approaches, and tune them for typical large-scale real-world scenarios. Experimental studies driven by the Alibaba Tianchi dataset show that our algorithms can achieve competitive scheduling effectiveness and running time, as compared with the heuristics used by the latest work including Medea and LraSched., 22 pages, 7 figures

The problem of finding a nonzero solution of a linear recurrence $Ly = 0$ with polynomial coefficients where $y$ has the form of a definite hypergeometric sum, related to the Inverse Creative Telescoping Problem of [14][Sec. 8], has now been open for three decades. Here we present an algorithm (implemented in a SageMath package) which, given such a recurrence and a quasi-triangular, shift-compatible factorial basis $\mathcal{B} = \langle P_k(n)\rangle_{k=0}^\infty$ of the polynomial space $\mathbb{K}[n]$ over a field $\mathbb{K}$ of characteristic zero, computes a recurrence satisfied by the coefficient sequence $c = \langle c_k\rangle_{k=0}^\infty$ of the solution $y_n = \sum_{k=0}^\infty c_kP_k(n)$ (where, thanks to the quasi-triangularity of $\mathcal{B}$, the sum on the right terminates for each $n \in \mathbb{N}$). More generally, if $\mathcal{B}$ is $m$-sieved for some $m \in \mathbb{N}$, our algorithm computes a system of $m$ recurrences satisfied by the $m$-sections of the coefficient sequence $c$. If an explicit nonzero solution of this system can be found, we obtain an explicit nonzero solution of $Ly = 0$., 62 pages

Feature related particle data analysis plays an important role in many scientific applications such as fluid simulations, cosmology simulations and molecular dynamics. Compared to conventional methods that use hand-crafted feature descriptors, some recent studies focus on transforming the data into a new latent space, where features are easier to be identified, compared and extracted. However, it is challenging to transform particle data into latent representations, since the convolution neural networks used in prior studies require the data presented in regular grids. In this paper, we adopt Geometric Convolution, a neural network building block designed for 3D point clouds, to create latent representations for scientific particle data. These latent representations capture both the particle positions and their physical attributes in the local neighborhood so that features can be extracted by clustering in the latent space, and tracked by applying tracking algorithms such as mean-shift. We validate the extracted features and tracking results from our approach using datasets from three applications and show that they are comparable to the methods that define hand-crafted features for each specific dataset.

Lifelong graph learning deals with the problem of continually adapting graph neural network (GNN) models to changes in evolving graphs. We address two critical challenges of lifelong graph learning in this work: dealing with new classes and tackling imbalanced class distributions. The combination of these two challenges is particularly relevant since newly emerging classes typically resemble only a tiny fraction of the data, adding to the already skewed class distribution. We make several contributions: First, we show that the amount of unlabeled data does not influence the results, which is an essential prerequisite for lifelong learning on a sequence of tasks. Second, we experiment with different label rates and show that our methods can perform well with only a tiny fraction of annotated nodes. Third, we propose the gDOC method to detect new classes under the constraint of having an imbalanced class distribution. The critical ingredient is a weighted binary cross-entropy loss function to account for the class imbalance. Moreover, we demonstrate combinations of gDOC with various base GNN models such as GraphSAGE, Simplified Graph Convolution, and Graph Attention Networks. Lastly, our k-neighborhood time difference measure provably normalizes the temporal changes across different graph datasets. With extensive experimentation, we find that the proposed gDOC method is consistently better than a naive adaption of DOC to graphs. Specifically, in experiments using the smallest history size, the out-of-distribution detection score of gDOC is 0.09 compared to 0.01 for DOC. Furthermore, gDOC achieves an Open-F1 score, a combined measure of in-distribution classification and out-of-distribution detection, of 0.33 compared to 0.25 of DOC (32% increase)., Accepted manuscript (after peer review, before copy-editing). Published article available at https://doi.org/10.1016/j.neunet.2023.04.022

Federated Learning (FL) has recently made significant progress as a new machine learning paradigm for privacy protection. Due to the high communication cost of traditional FL, one-shot federated learning is gaining popularity as a way to reduce communication cost between clients and the server. Most of the existing one-shot FL methods are based on Knowledge Distillation; however, {distillation based approach requires an extra training phase and depends on publicly available data sets or generated pseudo samples.} In this work, we consider a novel and challenging cross-silo setting: performing a single round of parameter aggregation on the local models without server-side training. In this setting, we propose an effective algorithm for Model Aggregation via Exploring Common Harmonized Optima (MA-Echo), which iteratively updates the parameters of all local models to bring them close to a common low-loss area on the loss surface, without harming performance on their own data sets at the same time. Compared to the existing methods, MA-Echo can work well even in extremely non-identical data distribution settings where the support categories of each local model have no overlapped labels with those of the others. We conduct extensive experiments on two popular image classification data sets to compare the proposed method with existing methods and demonstrate the effectiveness of MA-Echo, which clearly outperforms the state-of-the-arts. The source code can be accessed in \url{https://github.com/FudanVI/MAEcho}., Comment: Accepted in Neural Networks

Mixed-integer optimisation problems can be computationally challenging. Here, we introduce and analyse two efficient algorithms with a specific sequential design that are aimed at dealing with sampled problems within this class. At each iteration step of both algorithms, we first test the feasibility of a given test solution for each and every constraint associated with the sampled optimisation at hand, while also identifying those constraints that are violated. Subsequently, an optimisation problem is constructed with a constraint set consisting of the current basis -- namely, the smallest set of constraints that fully specifies the current test solution -- as well as constraints related to a limited number of the identified violating samples. We show that both algorithms exhibit finite-time convergence towards the optimal solution. Algorithm 2 features a neural network classifier that notably improves the computational performance compared to Algorithm 1. We quantitatively establish these algorithms' efficacy through three numerical tests: robust optimal power flow, robust unit commitment, and robust random mixed-integer linear program.

Recently, 3D deep learning models have been shown to be susceptible to adversarial attacks like their 2D counterparts. Most of the state-of-the-art (SOTA) 3D adversarial attacks perform perturbation to 3D point clouds. To reproduce these attacks in the physical scenario, a generated adversarial 3D point cloud need to be reconstructed to mesh, which leads to a significant drop in its adversarial effect. In this paper, we propose a strong 3D adversarial attack named Mesh Attack to address this problem by directly performing perturbation on mesh of a 3D object. In order to take advantage of the most effective gradient-based attack, a differentiable sample module that back-propagate the gradient of point cloud to mesh is introduced. To further ensure the adversarial mesh examples without outlier and 3D printable, three mesh losses are adopted. Extensive experiments demonstrate that the proposed scheme outperforms SOTA 3D attacks by a significant margin. We also achieved SOTA performance under various defenses. Our code is available at: https://github.com/cuge1995/Mesh-Attack., Comment: 8 pages, 6 figs

We develop and implement a novel fast bootstrap for dependent data. Our scheme is based on the i.i.d. resampling of the smoothed moment indicators. We characterize the class of parametric and semi-parametric estimation problems for which the method is valid. We show the asymptotic refinements of the proposed procedure, proving that it is higher-order correct under mild assumptions on the time series, the estimating functions, and the smoothing kernel. We illustrate the applicability and the advantages of our procedure for Generalized Empirical Likelihood estimation. As a by-product, our fast bootstrap provides higher-order correct asymptotic confidence distributions. Monte Carlo simulations on an autoregressive conditional duration model provide numerical evidence that the novel bootstrap yields higher-order accurate confidence intervals. A real-data application on dynamics of trading volume of stocks illustrates the advantage of our method over the routinely-applied first-order asymptotic theory, when the underlying distribution of the test statistic is skewed or fat-tailed.

Objectives: The purpose is to apply a previously validated deep learning algorithm to a new thyroid nodule ultrasound image dataset and compare its performances with radiologists. Methods: Prior study presented an algorithm which is able to detect thyroid nodules and then make malignancy classifications with two ultrasound images. A multi-task deep convolutional neural network was trained from 1278 nodules and originally tested with 99 separate nodules. The results were comparable with that of radiologists. The algorithm was further tested with 378 nodules imaged with ultrasound machines from different manufacturers and product types than the training cases. Four experienced radiologists were requested to evaluate the nodules for comparison with deep learning. Results: The Area Under Curve (AUC) of the deep learning algorithm and four radiologists were calculated with parametric, binormal estimation. For the deep learning algorithm, the AUC was 0.69 (95% CI: 0.64 - 0.75). The AUC of radiologists were 0.63 (95% CI: 0.59 - 0.67), 0.66 (95% CI:0.61 - 0.71), 0.65 (95% CI: 0.60 - 0.70), and 0.63 (95%CI: 0.58 - 0.67). Conclusion: In the new testing dataset, the deep learning algorithm achieved similar performances with all four radiologists. The relative performance difference between the algorithm and the radiologists is not significantly affected by the difference of ultrasound scanner., Comment: Clinical Imaging (2023)

As an important technology to ensure data security, consistency, traceability, etc., blockchain has been increasingly used in Internet of Things (IoT) applications. The integration of blockchain and edge computing can further improve the resource utilization in terms of network, computing, storage, and security. This paper aims to present a survey on the integration of blockchain and edge computing. In particular, we first give an overview of blockchain and edge computing. We then present a general architecture of an integration of blockchain and edge computing system. We next study how to utilize blockchain to benefit edge computing, as well as how to use edge computing to benefit blockchain. We also discuss the issues brought by the integration of blockchain and edge computing system and solutions from perspectives of resource management, joint optimization, data management, computation offloading and security mechanism. Finally, we analyze and summarize the existing challenges posed by the integration of blockchain and edge computing system and the potential solutions in the future.

We consider data with multiple observations or reports on a network in the case when these networks themselves are connected through some form of network ties. We could take the example of a cognitive social structure where there is another type of tie connecting the actors that provide the reports; or the study of interpersonal spillover effects from one cultural domain to another facilitated by the social ties. Another example is when the individual semantic structures are represented as semantic networks of a group of actors and connected through these actors' social ties to constitute knowledge of a social group. How to jointly represent the two types of networks is not trivial as the layers and not the nodes of the layers of the reported networks are coupled through a network on the reports. We propose to transform the different multiple networks using line graphs, where actors are affiliated with ties represented as nodes, and represent the totality of the different types of ties as a multilevel network. This affords studying the associations between the social network and the reports as well as the alignment of the reports to a criterion graph. We illustrate how the procedure can be applied to studying the social construction of knowledge in local flood management groups. Here we use multilevel exponential random graph models but the representation also lends itself to stochastic actor-oriented models, multilevel blockmodels, and any model capable of handling multilevel networks.

Head tracking in head-mounted displays (HMDs) enables users to explore a 360-degree virtual scene with free head movements. However, for seated use of HMDs such as users sitting on a chair or a couch, physically turning around 360-degree is not possible. Redirection techniques decouple tracked physical motion and virtual motion, allowing users to explore virtual environments with more flexibility. In seated situations with only head movements available, the difference of stimulus might cause the detection thresholds of rotation gains to differ from that of redirected walking. Therefore we present an experiment with a two-alternative forced-choice (2AFC) design to compare the thresholds for seated and standing situations. Results indicate that users are unable to discriminate rotation gains between 0.89 and 1.28, a smaller range compared to the standing condition. We further treated head amplification as an interaction technique and found that a gain of 2.5, though not a hard threshold, was near the largest gain that users consider applicable. Overall, our work aims to better understand human perception of rotation gains in seated VR and the results provide guidance for future design choices of its applications., Comment: Submitted to IEEE TVCG

We propose non-volatile memory (NVM) designs based on Piezoelectric Strain FET (PeFET) utilizing a piezoelectric/ferroelectric (PE/FE such as PZT) coupled with 2D Transition Metal Dichalcogenide (2D-TMD such as MoS2) transistor. The proposed NVMs store bit information in the form of polarization (P) of the FE/PE, use electric-field driven P-switching for write and employ piezoelectricity induced dynamic bandgap modulation of 2D-TMD channel for bit sensing. We analyze PeFET with COMSOL based 3D modeling showing that the circuit-driven optimization of PeFET geometry is essential to achieve effective hammer-and-nail effect and adequate bandgap modulation for NVM read. Our results show that distinguishability of binary states to up to 11X is achieved in PeFETs.We propose various flavors of PeFET NVMs, namely (a) high density (HD) NVM featuring a compact access-transistor-less bit-cell, (b) 1T-1PeFET NVM with segmented architecture, targeted for optimized write energy and latency and (c) cross-coupled (CC) NVM offering a trade-off between area and latency.PeFET NVMs offer up to 7X smaller cell area, 66% lower write energy, 87% lower read energy and 44% faster read compared to 2D-FET SRAM. This comes at the cost of high write latency in PeFET NVMs, which can be minimized by virtue of optimized PE geometry., 8 pages, 13 figures In the peer review process of the journal of IEEE Transactions on Electron Devices

We present a novel thermodynamic parameter estimation framework for energy-based surgery on live tissue, with direct applications to tissue characterization during electrosurgery. This framework addresses the problem of estimating tissue-specific thermodynamics in real-time, which would enable accurate prediction of thermal damage impact to the tissue and damage-conscious planning of electrosurgical procedures. Our approach provides basic thermodynamic information such as thermal diffusivity, and also allows for obtaining the thermal relaxation time and a model of the heat source, yielding in real-time a controlled hyperbolic thermodynamics model. The latter accounts for the finite thermal propagation time necessary for modeling of the electrosurgical action, in which the probe motion speed often surpasses the speed of thermal propagation in the tissue operated on. Our approach relies solely on thermographer feedback and a knowledge of the power level and position of the electrosurgical pencil, imposing only very minor adjustments to normal electrosurgery to obtain a high-fidelity model of the tissue-probe interaction. Our method is minimally invasive and can be performed in situ. We apply our method first to simulated data based on porcine muscle tissue to verify its accuracy and then to in vivo liver tissue, and compare the results with those from the literature. This comparison shows that parameterizing the Maxwell--Cattaneo model through the framework proposed yields a noticeably higher fidelity real-time adaptable representation of the thermodynamic tissue response to the electrosurgical impact than currently available. A discussion on the differences between the live and the dead tissue thermodynamics is also provided., Accepted for publication in the IEEE Transactions on Biomedical Engineering. Research reported in this publication was supported by the National Institute of Biomedical Imaging and Bioengineering of the National Institutes of Health under award number R01EB029766