bluuebunny/crossref_metadata_2025 huggingface dataset:
MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators
Authors: Wang Dingmin , Hu Pan , Wałęga Przemysław Andrzej , Grau Bernardo Cuenca
Published: July 2022

DatalogMTL is an extension of Datalog with operators from metric temporal logic which has received significant attention in recent years. It is a highly expressive knowledge representation language that is well-suited for applications in temporal ontology-based query answering and stream processing. Reasoning in DatalogMTL is, however, of high computational complexity, making implementation challenging and hindering its adoption in applications. In this paper, we present a novel approach for practical reasoning in DatalogMTL which combines materialisation (a.k.a. forward chaining) with automata-based techniques. We have implemented this approach in a reasoner called MeTeoR and evaluated its performance using a temporal extension of the Lehigh University Benchmark and a benchmark based on real-world meteorological data. Our experiments show that MeTeoR is a scalable system which enables reasoning over complex temporal rules and datasets involving tens of millions of temporal facts.
Residual Similarity Based Conditional Independence Test and Its Application in Causal Discovery
Authors: Zhang Hao , Zhou Shuigeng , Zhang Kun , Guan Jihong
Published: July 2022

Recently, many regression based conditional independence (CI) test methods have been proposed to solve the problem of causal discovery. These methods provide alternatives to test CI by first removing the information of the controlling set from the two target variables, and then testing the independence between the corresponding residuals Res1 and Res2. When the residuals are linearly uncorrelated, the independence test between them is nontrivial. With the ability to calculate inner product in high-dimensional space, kernel-based methods are usually used to achieve this goal, but still consume considerable time. In this paper, we investigate the independence between two linear combinations under linear non-Gaussian structural equation model. We show that the dependence between the two residuals can be captured by the difference between the similarity of (Res1, Res2) and that of (Res1, Res3) (Res3 is generated by random permutation) in high-dimensional space. With this result, we design a new method called SCIT for CI test, where permutation test is performed to control Type I error rate. The proposed method is simpler yet more efficient and effective than the existing ones. When applied to causal discovery, the proposed method outperforms the counterparts in terms of both speed and Type II error rate, especially in the case of small sample size, which is validated by our extensive experiments on various datasets.
FisheyeHDK: Hyperbolic Deformable Kernel Learning for Ultra-Wide Field-of-View Image Recognition
Authors: Ahmad Ola , Lecue Freddy
Published: July 2022

Conventional convolution neural networks (CNNs) trained on narrow Field-of-View (FoV) images are the state-of-the art approaches for object recognition tasks. Some methods proposed the adaptation of CNNs to ultra-wide FoV images by learning deformable kernels. However, they are limited by the Euclidean geometry and their accuracy degrades under strong distortions caused by fisheye projections. In this work, we demonstrate that learning the shape of convolution kernels in non-Euclidean spaces is better than existing deformable kernel methods. In particular, we propose a new approach that learns deformable kernel parameters (positions) in hyperbolic space. FisheyeHDK is a hybrid CNN architecture combining hyperbolic and Euclidean convolution layers for positions and features learning. First, we provide intuition of hyperbolic space for wide FoV images. Using synthetic distortion profiles, we demonstrate the effectiveness of our approach. We select two datasets - Cityscapes and BDD100K 2020 - of perspective images which we transform to fisheye equivalents at different scaling factors (analogue to focal lengths). Finally, we provide an experiment on data collected by a real fisheye camera. Validations and experiments show that our approach improves existing deformable kernel methods for CNN adaptation on fisheye images.
Entropy-Based Logic Explanations of Neural Networks
Authors: Barbiero Pietro , Ciravegna Gabriele , Giannini Francesco , Lió Pietro , Gori Marco , Melacci Stefano
Published: July 2022

Explainable artificial intelligence has rapidly emerged since lawmakers have started requiring interpretable models for safety-critical domains. Concept-based neural networks have arisen as explainable-by-design methods as they leverage human-understandable symbols (i.e. concepts) to predict class memberships. However, most of these approaches focus on the identification of the most relevant concepts but do not provide concise, formal explanations of how such concepts are leveraged by the classifier to make predictions. In this paper, we propose a novel end-to-end differentiable approach enabling the extraction of logic explanations from neural networks using the formalism of First-Order Logic. The method relies on an entropy-based criterion which automatically identifies the most relevant concepts. We consider four different case studies to demonstrate that: (i) this entropy-based criterion enables the distillation of concise logic explanations in safety-critical domains from clinical data to computer vision; (ii) the proposed approach outperforms state-of-the-art white-box models in terms of classification accuracy.
DPNAS: Neural Architecture Search for Deep Learning with Differential Privacy
Authors: Cheng Anda , Wang Jiaxing , Zhang Xi Sheryl , Chen Qiang , Wang Peisong , Cheng Jian
Published: July 2022

Training deep neural networks (DNNs) for meaningful differential privacy (DP) guarantees severely degrades model utility. In this paper, we demonstrate that the architecture of DNNs has a significant impact on model utility in the context of private deep learning, whereas its effect is largely unexplored in previous studies. In light of this missing, we propose the very first framework that employs neural architecture search to automatic model design for private deep learning, dubbed as DPNAS. To integrate private learning with architecture search, a DP-aware approach is introduced for training candidate models composed on a delicately defined novel search space. We empirically certify the effectiveness of the proposed framework. The searched model DPNASNet achieves state-of-the-art privacy/utility trade-offs, e.g., for the privacy budget of (epsilon, delta)=(3, 1e-5), our model obtains test accuracy of 98.57% on MNIST, 88.09% on FashionMNIST, and 68.33% on CIFAR-10. Furthermore, by studying the generated architectures, we provide several intriguing findings of designing private-learning-friendly DNNs, which can shed new light on model design for deep learning with differential privacy.
Online Certification of Preference-Based Fairness for Personalized Recommender Systems
Authors: Do Virginie , Corbett-Davies Sam , Atif Jamal , Usunier Nicolas
Published: July 2022

Recommender systems are facing scrutiny because of their growing impact on the opportunities we have access to. Current audits for fairness are limited to coarse-grained parity assessments at the level of sensitive groups. We propose to audit for envy-freeness, a more granular criterion aligned with individual preferences: every user should prefer their recommendations to those of other users. Since auditing for envy requires to estimate the preferences of users beyond their existing recommendations, we cast the audit as a new pure exploration problem in multi-armed bandits. We propose a sample-efficient algorithm with theoretical guarantees that it does not deteriorate user experience. We also study the trade-offs achieved on real-world recommendation datasets.
Recovering the Propensity Score from Biased Positive Unlabeled Data
Authors: Gerych Walter , Hartvigsen Thomas , Buquicchio Luke , Agu Emmanuel , Rundensteiner Elke
Published: July 2022

Positive-Unlabeled (PU) learning methods train a classifier to distinguish between the positive and negative classes given only positive and unlabeled data. While traditional PU methods require the labeled positive samples to be an unbiased sample of the positive distribution, in practice the labeled sample is often a biased draw from the true distribution. Prior work shows that if we know the likelihood that each positive instance will be selected for labeling, referred to as the propensity score, then the biased sample can be used for PU learning. Unfortunately, no prior work has been proposed an inference strategy for which the propensity score is identifiable. In this work, we propose two sets of assumptions under which the propensity score can be uniquely determined: one in which no assumption is made on the functional form of the propensity score (requiring assumptions on the data distribution), and the second which loosens the data assumptions while assuming a functional form for the propensity score. We then propose inference strategies for each case. Our empirical study shows that our approach significantly outperforms the state-of-the-art propensity estimation methods on a rich variety of benchmark datasets.
DiPS: Differentiable Policy for Sketching in Recommender Systems
Authors: Ghosh Aritra , Mitra Saayan , Lan Andrew
Published: July 2022

In sequential recommender system applications, it is important to develop models that can capture users' evolving interest over time to successfully recommend future items that they are likely to interact with. For users with long histories, typical models based on recurrent neural networks tend to forget important items in the distant past. Recent works have shown that storing a small sketch of past items can improve sequential recommendation tasks. However, these works all rely on static sketching policies, i.e., heuristics to select items to keep in the sketch, which are not necessarily optimal and cannot improve over time with more training data. In this paper, we propose a differentiable policy for sketching (DiPS), a framework that learns a data-driven sketching policy in an end-to-end manner together with the recommender system model to explicitly maximize recommendation quality in the future.
We also propose an approximate estimator of the gradient for optimizing the sketching algorithm parameters that is computationally efficient. We verify the effectiveness of DiPS on real-world datasets under various practical settings and show that it requires up to 50% fewer sketch items to reach the same predictive quality than existing sketching policies.
Partial Multi-Label Learning via Large Margin Nearest Neighbour Embeddings
Authors: Gong Xiuwen , Yuan Dong , Bao Wei
Published: July 2022

To deal with ambiguities in partial multi-label learning (PML), existing popular PML research attempts to perform disambiguation by direct ground-truth label identification. However, these approaches can be easily misled by noisy false-positive labels in the iteration of updating the model parameter and the latent ground-truth label variables. When labeling information is ambiguous, we should depend more on underlying structure of data, such as label and feature correlations, to perform disambiguation for partially labeled data. Moreover, large margin nearest neighbour (LMNN) is a popular strategy that considers data structure in classification. However, due to the ambiguity of labeling information in PML, traditional LMNN cannot be used to solve the PML problem directly. In addition, embedding is an effective technology to decrease the noise information of data. Inspried by LMNN and embedding technology, we propose a novel PML paradigm called Partial Multi-label Learning via Large Margin Nearest Neighbour Embeddings (PML-LMNNE), which aims to conduct disambiguation by projecting labels and features into a lower-dimension embedding space and reorganize the underlying structure by LMNN in the embedding space simultaneously. An efficient algorithm is designed to implement the proposed method and the convergence rate of the algorithm is analyzed. Moreover, we present a theoretical analysis of the generalization error bound for the proposed PML-LMNNE, which shows that the generalization error converges to the sum of two times the Bayes error over the labels when the number of instances goes to infinity. Comprehensive experiments on artificial and real-world datasets demonstrate the superiorities of the proposed PML-LMNNE.
Semi-supervised Conditional Density Estimation with Wasserstein Laplacian Regularisation
Authors: Graffeuille Olivier , Koh Yun Sing , Wicker Jörg , Lehmann Moritz K
Published: July 2022

Conditional Density Estimation (CDE) has wide-reaching applicability to various real-world problems, such as spatial density estimation and environmental modelling. CDE estimates the probability density of a random variable rather than a single value and can thus model uncertainty and inverse problems. This task is inherently more complex than regression, and many algorithms suffer from overfitting, particularly when modelled with few labelled data points. For applications where unlabelled data is abundant but labelled data is scarce, we propose Wasserstein Laplacian Regularisation, a semi-supervised learning framework that allows CDE algorithms to leverage these unlabelled data. The framework minimises an objective function which ensures that the learned model is smooth along the manifold of the underlying data, as measured by Wasserstein distance. When applying our framework to Mixture Density Networks, the resulting semi-supervised algorithm can achieve similar performance to a supervised model with up to three times as many labelled data points on baseline datasets. We additionally apply our technique to the problem of remote sensing for chlorophyll-a estimation in inland waters.
iDECODe: In-Distribution Equivariance for Conformal Out-of-Distribution Detection
Authors: Kaur Ramneet , Jha Susmit , Roy Anirban , Park Sangdon , Dobriban Edgar , Sokolsky Oleg , Lee Insup
Published: July 2022

Machine learning methods such as deep neural networks (DNNs), despite their success across different domains, are known to often generate incorrect predictions with high confidence on inputs outside their training distribution. The deployment of DNNs in safety-critical domains requires detection of out-of-distribution (OOD) data so that DNNs can abstain from making predictions on those. A number of methods have been recently developed for OOD detection, but there is still room for improvement. We propose the new method iDECODe, leveraging in-distribution equivariance for conformal OOD detection. It relies on a novel base non-conformity measure and a new aggregation method, used in the inductive conformal anomaly detection framework, thereby guaranteeing a bounded false detection rate. We demonstrate the efficacy of iDECODe by experiments on image and audio datasets, obtaining state-of-the-art results. We also show that iDECODe can detect adversarial examples. Code, pre-trained models, and data are available at https://github.com/ramneetk/iDECODe.
Deep Reinforcement Learning Policies Learn Shared Adversarial Features across MDPs
Authors: Korkmaz Ezgi
Published: July 2022

The use of deep neural networks as function approximators has led to striking progress for reinforcement learning algorithms and applications. Yet the knowledge we have on decision boundary geometry and the loss landscape of neural policies is still quite limited. In this paper, we propose a framework to investigate the decision boundary and loss landscape similarities across states and across MDPs. We conduct experiments in various games from Arcade Learning Environment, and discover that high sensitivity directions for neural policies are correlated across MDPs. We argue that these high sensitivity directions support the hypothesis that non-robust features are shared across training environments of reinforcement learning agents. We believe our results reveal fundamental properties of the environments used in deep reinforcement learning training, and represent a tangible step towards building robust and reliable deep reinforcement learning agents.
Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
Authors: Lechner Mathias , Žikelić Đorđe , Chatterjee Krishnendu , Henzinger Thomas A.
Published: July 2022

We consider the problem of formally verifying almost-sure (a.s.) asymptotic stability in discrete-time nonlinear stochastic control systems. While verifying stability in deterministic control systems is extensively studied in the literature, verifying stability in stochastic control systems is an open problem. The few existing works on this topic either consider only specialized forms of stochasticity or make restrictive assumptions on the system, rendering them inapplicable to learning algorithms with neural network policies.
In this work, we present an approach for general nonlinear stochastic control problems with two novel aspects: (a) instead of classical stochastic extensions of Lyapunov functions, we use ranking supermartingales (RSMs) to certify a.s. asymptotic stability, and (b) we present a method for learning neural network RSMs.
We prove that our approach guarantees a.s. asymptotic stability of the system and
provides the first method to obtain bounds on the stabilization time, which stochastic Lyapunov functions do not.
Finally, we validate our approach experimentally on a set of nonlinear stochastic reinforcement learning environments with neural network policies.
Cross-Lingual Adversarial Domain Adaptation for Novice Programming
Authors: Mao Ye , Khoshnevisan Farzaneh , Price Thomas , Barnes Tiffany , Chi Min
Published: July 2022

Student modeling sits at the epicenter of adaptive learning technology. In contrast to the voluminous work on student modeling for well-defined domains such as algebra, there has been little research on student modeling in programming (SMP) due to data scarcity caused by the unbounded solution spaces of open-ended programming exercises. In this work, we focus on two essential SMP tasks: program classification and early prediction of student success and propose a Cross-Lingual Adversarial Domain Adaptation (CrossLing) framework that can leverage a large programming dataset to learn features that can improve SMP's build using a much smaller dataset in a different programming language. Our framework maintains one globally invariant latent representation across both datasets via an adversarial learning process, as well as allocating domain-specific models for each dataset to extract local latent representations that cannot and should not be united. By separating globally-shared representations from domain-specific representations, our framework outperforms existing state-of-the-art methods for both SMP tasks.
CC-CERT: A Probabilistic Approach to Certify General Robustness of Neural Networks
Authors: Pautov Mikhail , Tursynbek Nurislam , Munkhoeva Marina , Muravev Nikita , Petiushko Aleksandr , Oseledets Ivan
Published: July 2022

In safety-critical machine learning applications, it is crucial to defend models against adversarial attacks --- small modifications of the input that change the predictions. Besides rigorously studied $\ell_p$-bounded additive perturbations, semantic perturbations (e.g. rotation, translation) raise a serious concern on deploying ML systems in real-world. Therefore, it is important to provide provable guarantees for deep learning models against semantically meaningful input transformations. In this paper, we propose a new universal probabilistic certification approach based on Chernoff-Cramer bounds that can be used in general attack settings. We estimate the probability of a model to fail if the attack is sampled from a certain distribution. Our theoretical findings are supported by experimental results on different datasets.
FedSoft: Soft Clustered Federated Learning with Proximal Local Updating
Authors: Ruan Yichen , Joe-Wong Carlee
Published: July 2022

Traditionally, clustered federated learning groups clients with the same data distribution into a cluster, so that every client is uniquely associated with one data distribution and helps train a model for this distribution. We relax this hard association assumption to soft clustered federated learning, which allows every local dataset to follow a mixture of multiple source distributions. We propose FedSoft, which trains both locally personalized models and high-quality cluster models in this setting. FedSoft limits client workload by using proximal updates to require the completion of only one optimization task from a subset of clients in every communication round. We show, analytically and empirically, that FedSoft effectively exploits similarities between the source distributions to learn personalized and cluster models that perform well.
Verification of Neural-Network Control Systems by Integrating Taylor Models and Zonotopes
Authors: Schilling Christian , Forets Marcelo , Guadalupe Sebastián
Published: July 2022

We study the verification problem for closed-loop dynamical systems with neural-network controllers (NNCS). This problem is commonly reduced to computing the set of reachable states. When considering dynamical systems and neural networks in isolation, there exist precise approaches for that task based on set representations respectively called Taylor models and zonotopes. However, the combination of these approaches to NNCS is non-trivial because, when converting between the set representations, dependency information gets lost in each control cycle and the accumulated approximation error quickly renders the result useless. We present an algorithm to chain approaches based on Taylor models and zonotopes, yielding a precise reachability algorithm for NNCS. Because the algorithm only acts at the interface of the isolated approaches, it is applicable to general dynamical systems and neural networks and can benefit from future advances in these areas. Our implementation delivers state-of-the-art performance and is the first to successfully analyze all benchmark problems of an annual reachability competition for NNCS.
HoD-Net: High-Order Differentiable Deep Neural Networks and Applications
Authors: Shen Siyuan , Shao Tianjia , Zhou Kun , Jiang Chenfanfu , Luo Feng , Yang Yin
Published: July 2022

We introduce a deep architecture named HoD-Net to enable high-order differentiability for deep learning. HoD-Net is based on and generalizes the complex-step finite difference (CSFD) method. While similar to classic finite difference, CSFD approaches the derivative of a function from a higher-dimension complex domain, leading to highly accurate and robust differentiation computation without numerical stability issues. This method can be coupled with backpropagation and adjoint perturbation methods for an efficient calculation of high-order derivatives. We show how this numerical scheme can be leveraged in challenging deep learning problems, such as high-order network training, deep learning-based physics simulation, and neural differential equations.
Robust Optimal Classification Trees against Adversarial Examples
Authors: Vos Daniël , Verwer Sicco
Published: July 2022

Decision trees are a popular choice of explainable model, but just like neural networks, they suffer from adversarial examples. Existing algorithms for fitting decision trees robust against adversarial examples are greedy heuristics and lack approximation guarantees. In this paper we propose ROCT, a collection of methods to train decision trees that are optimally robust against user-specified attack models. We show that the min-max optimization problem that arises in adversarial learning can be solved using a single minimization formulation for decision trees with 0-1 loss. We propose such formulations in Mixed-Integer Linear Programming and Maximum Satisfiability, which widely available solvers can optimize. We also present a method that determines the upper bound on adversarial accuracy for any model using bipartite matching. Our experimental results demonstrate that the existing heuristics achieve close to optimal scores while ROCT achieves state-of-the-art scores.
Sample-Efficient Reinforcement Learning via Conservative Model-Based Actor-Critic
Authors: Wang Zhihai , Wang Jie , Zhou Qi , Li Bin , Li Houqiang
Published: July 2022

Model-based reinforcement learning algorithms, which aim to learn a model of the environment to make decisions, are more sample efficient than their model-free counterparts. The sample efficiency of model-based approaches relies on whether the model can well approximate the environment. However, learning an accurate model is challenging, especially in complex and noisy environments. To tackle this problem, we propose the conservative model-based actor-critic (CMBAC), a novel approach that achieves high sample efficiency without the strong reliance on accurate learned models. Specifically, CMBAC learns multiple estimates of the Q-value function from a set of inaccurate models and uses the average of the bottom-k estimates---a conservative estimate---to optimize the policy. An appealing feature of CMBAC is that the conservative estimates effectively encourage the agent to avoid unreliable “promising actions”---whose values are high in only a small fraction of the models. Experiments demonstrate that CMBAC significantly outperforms state-of-the-art approaches in terms of sample efficiency on several challenging control tasks, and the proposed method is more robust than previous methods in noisy environments.
Distributed Randomized Sketching Kernel Learning
Authors: Yin Rong , Liu Yong , Meng Dan
Published: July 2022

We investigate the statistical and computational requirements for distributed kernel ridge regression with randomized sketching (DKRR-RS) and successfully achieve the optimal learning rates with only a fraction of computations. More precisely, the proposed DKRR-RS combines sparse randomized sketching, divide-and-conquer and KRR to scale up kernel methods and successfully derives the same learning rate as the exact KRR with greatly reducing computational costs in expectation, at the basic setting, which outperforms previous state of the art solutions. Then, for the sake of the gap between theory and experiments, we derive the optimal learning rate in probability for DKRR-RS to reflect its generalization performance. Finally, to further improve the learning performance, we construct an efficient communication strategy for DKRR-RS and demonstrate the power of communications via theoretical assessment. An extensive experiment validates the effectiveness of DKRR-RS and the communication strategy on real datasets.
TS2Vec: Towards Universal Representation of Time Series
Authors: Yue Zhihan , Wang Yujing , Duan Juanyong , Yang Tianmeng , Huang Congrui , Tong Yunhai , Xu Bixiong
Published: July 2022

This paper presents TS2Vec, a universal framework for learning representations of time series in an arbitrary semantic level. Unlike existing methods, TS2Vec performs contrastive learning in a hierarchical way over augmented context views, which enables a robust contextual representation for each timestamp. Furthermore, to obtain the representation of an arbitrary sub-sequence in the time series, we can apply a simple aggregation over the representations of corresponding timestamps. We conduct extensive experiments on time series classification tasks to evaluate the quality of time series representations. As a result, TS2Vec achieves significant improvement over existing SOTAs of unsupervised time series representation on 125 UCR datasets and 29 UEA datasets. The learned timestamp-level representations also achieve superior results in time series forecasting and anomaly detection tasks. A linear regression trained on top of the learned representations outperforms previous SOTAs of time series forecasting. Furthermore, we present a simple way to apply the learned representations for unsupervised anomaly detection, which establishes SOTA results in the literature. The source code is publicly available at https://github.com/yuezhihan/ts2vec.
ProtGNN: Towards Self-Explaining Graph Neural Networks
Authors: Zhang Zaixi , Liu Qi , Wang Hao , Lu Chengqiang , Lee Cheekong
Published: July 2022

Despite the recent progress in Graph Neural Networks (GNNs), it remains challenging to explain the predictions
made by GNNs. Existing explanation methods mainly focus on post-hoc explanations where another explanatory model is employed to provide explanations for a trained GNN. The fact that post-hoc methods fail to reveal the original reasoning process of GNNs raises the need of building GNNs with built-in interpretability. In this work, we propose Prototype Graph Neural Network (ProtGNN), which combines prototype learning with GNNs and provides a new perspective on the explanations of GNNs. In ProtGNN, the explanations are naturally derived from the case-based reasoning process and are actually used during classification. The prediction of ProtGNN is obtained by comparing the inputs to a few learned prototypes in the latent space.
Furthermore, for better interpretability and higher efficiency, a novel conditional subgraph sampling module is incorporated to indicate which part of the input graph is most similar to each prototype in ProtGNN+. Finally, we evaluate our method on a wide range of datasets and perform concrete case studies. Extensive results show that ProtGNN and ProtGNN+ can provide inherent interpretability while achieving accuracy on par with the non-interpretable counterparts.
Pretrained Cost Model for Distributed Constraint Optimization Problems
Authors: Deng Yanchen , Kong Shufeng , An Bo
Published: July 2022

Distributed Constraint Optimization Problems (DCOPs) are an important subclass of combinatorial optimization problems, where information and controls are distributed among multiple autonomous agents. Previously, Machine Learning (ML) has been largely applied to solve combinatorial optimization problems by learning effective heuristics. However, existing ML-based heuristic methods are often not generalizable to different search algorithms. Most importantly, these methods usually require full knowledge about the problems to be solved, which are not suitable for distributed settings where centralization is not realistic due to geographical limitations or privacy concerns. To address the generality issue, we propose a novel directed acyclic graph representation schema for DCOPs and leverage the Graph Attention Networks (GATs) to embed graph representations. Our model, GAT-PCM, is then pretrained with optimally labelled data in an offline manner, so as to construct effective heuristics to boost a broad range of DCOP algorithms where evaluating the quality of a partial assignment is critical, such as local search or backtracking search. Furthermore, to enable decentralized model inference, we propose a distributed embedding schema of GAT-PCM where each agent exchanges only embedded vectors, and show its soundness and complexity. Finally, we demonstrate the effectiveness of our model by combining it with a local search or a backtracking search algorithm. Extensive empirical evaluations indicate that the GAT-PCM-boosted algorithms significantly outperform the state-of-the-art methods in various benchmarks.
Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs
Authors: Guo Mingyu , Li Jialiang , Neumann Aneta , Neumann Frank , Nguyen Hung
Published: July 2022

Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker's entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes.

We observe that practical Active Directory attack graphs have small maximum attack path length and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still w[1]-hard with respect to the defender's budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixed-parameter tractable algorithm.

We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires a small tree width. The other assumes a small number of splitting nodes (nodes with multiple out-going edges). Finally, the last algorithm is converted into a graph convolutional neural network based heuristic, which scales to larger graphs with more splitting nodes.
Generalization in Mean Field Games by Learning Master Policies
Authors: Perrin Sarah , Laurière Mathieu , Pérolat Julien , Élie Romuald , Geist Matthieu , Pietquin Olivier
Published: July 2022

Mean Field Games (MFGs) can potentially scale multi-agent systems to extremely large populations of agents. Yet, most of the literature assumes a single initial distribution for the agents, which limits the practical applications of MFGs. Machine Learning has the potential to solve a wider diversity of MFG problems thanks to generalizations capacities. We study how to leverage these generalization properties to learn policies enabling a typical agent to behave optimally against any population distribution. In reference to the Master equation in MFGs, we coin the term “Master policies” to describe them and we prove that a single Master policy provides a Nash equilibrium, whatever the initial distribution. We propose a method to learn such Master policies. Our approach relies on three ingredients: adding the current population distribution as part of the observation, approximating Master policies with neural networks, and training via Reinforcement Learning and Fictitious Play. We illustrate on numerical examples not only the efficiency of the learned Master policy but also its generalization capabilities beyond the distributions used for training.
DeepAuth: A DNN Authentication Framework by Model-Unique and Fragile Signature Embedding
Authors: Lao Yingjie , Zhao Weijie , Yang Peng , Li Ping
Published: July 2022

Along with the evolution of deep neural networks (DNNs) in many real-world applications, the complexity of model building has also dramatically increased. Therefore, it is vital to protect the intellectual property (IP) of the model builder and ensure the trustworthiness of the deployed models. Meanwhile, adversarial attacks on DNNs (e.g., backdoor and poisoning attacks) that seek to inject malicious behaviors have been investigated recently, demanding a means for verifying the integrity of the deployed model to protect the users. This paper presents a novel DNN authentication framework DeepAuth that embeds a unique and fragile signature to each protected DNN model. Our approach exploits sensitive key samples that are well crafted from the input space to latent space and then to logit space for producing signatures. After embedding, each model will respond distinctively to these key samples, which creates a model-unique signature as a strong tool for authentication and user identity. The signature embedding process is also designed to ensure the fragility of the signature, which can be used to detect malicious modifications such that an illegitimate user or an altered model should not have the intact signature. Extensive evaluations on various models over a wide range of datasets demonstrate the effectiveness and efficiency of the proposed DeepAuth.
Reconfiguring Shortest Paths in Graphs
Authors: Gajjar Kshitij , Jha Agastya Vibhuti , Kumar Manish , Lahiri Abhiruk
Published: July 2022

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time, so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) revamping road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem.

When modelled as graph problems, (a) is the most general case while (b), (c) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) and (d), we present efficient algorithms to solve the respective problems. We also generalise the problem to when at most k (for some k >= 2) contiguous vertices on a shortest path can be changed at a time.
On Probabilistic Generalization of Backdoors in Boolean Satisfiability
Authors: Semenov Alexander , Pavlenko Artem , Chivilikhin Daniil , Kochemazov Stepan
Published: July 2022

The paper proposes a probabilistic generalization of the well-known Strong Backdoor Set (SBS) concept applied to the Boolean Satisfiability Problem (SAT). We call a set of Boolean variables B a ρ-backdoor, if for a fraction of at least ρ of possible assignments of variables from B, assigning their values to variables in a Boolean formula in Conjunctive Normal Form (CNF) results in polynomially solvable formulas. Clearly, a ρ-backdoor with ρ=1 is an SBS. For a given set B it is possible to efficiently construct an (ε, δ)-approximation of parameter ρ using the Monte Carlo method. Thus, we define an (ε, δ)-SBS as such a set B for which the conclusion "parameter ρ deviates from 1 by no more than ε" is true with probability no smaller than 1 - δ. We consider the problems of finding the minimum SBS and the minimum (ε, δ)-SBS. To solve the former problem, one can use the algorithm described by R. Williams, C. Gomes and B. Selman in 2003. In the paper we propose a new probabilistic algorithm to solve the latter problem, and show that the asymptotic estimation of the worst-case complexity of the proposed algorithm is significantly smaller than that of the algorithm by Williams et al. For practical applications, we suggest a metaheuristic optimization algorithm based on the penalty function method to seek the minimal (ε, δ)-SBS. Results of computational experiments show that the use of (ε, δ)-SBSes found by the proposed algorithm allows speeding up solving of test problems related to equivalence checking and hard crafted and combinatorial benchmarks compared to state-of-the-art SAT solvers.
You Tube, We Comment: I Am a Singer and Geopolitical Encounters of Sinophone Communities
Authors: Guo Shaohua
Published: July 2022

This essay examines the reception of a top-rated reality show I Am a Singer among Sinophone communities on YouTube. Existing studies of YouTube focus on the burgeoning of participatory culture, the rise of microcelebrities, and fan labor. However, to date, little critical attention has been devoted to how YouTube constitutes a premium platform for the consumption of Chinese-language audiovisual content. Engaging in a close reading of user comments on YouTube, I analyze the ways in which Sinophone Internet users of divergent political stances defend their respective positions. While the exchange of viewpoints rarely fosters a change in political views, this process has nevertheless catalyzed productive conversations pertaining to issues about historical legacies and their relevance to contemporary society. The comment section thereby not only catalyzes public deliberation on a wide range of societal issues, but also exemplifies the role that popular culture plays in inspiring geopolitical imaginations beyond geographical boundaries.
Introduction to the Special Edition on Imagining Geopolitics across Media and Artforms
Authors: Kong Belinda , Guo Shaohua
Published: July 2022

This introduction provides an overview of the two main themes of this special issue—contemporary cultural engagements with Asian geopolitics, and the roles played by new media and genres in shaping these geopolitical imaginations—as well as summaries of the following six articles.
The learning of logarithmic functions by 12th-grade students based on modelling tasks
Authors: Araújo Samuel , Viseu Floriano , Soares Ana Jacinta , Leite Isabel
Published: July 2022

The relevance that the application of what is learned in Mathematics to everyday situations has in student learning has led us to develop an experiment on teaching the logarithmic function using modelling tasks. Based on this experiment, we intend to characterize the activities of 12th-grade students in the performance of modelling tasks concerning topics of logarithmic functions and identify the difficulties they may present while solving these tasks using a graphing calculator. When adopting a qualitative and interpretative approach, data were collected through students' written records while solving the proposed tasks using the graphing calculator. The results indicate that the students show that the modelling tasks promoted group work and their interest and participation in class. During the exploration of the tasks, students performed activities that result from the accomplishment of modelling phases such as understanding the statement of the task, organizing and analyzing data, building and validating the model that best fits the data, and exploring the model, either in the introduction of the logarithmic function and its derivative or in the consolidation of the acquired knowledge. In such activities, some students presented difficulties regarding the properties and characteristics of the logarithmic function and its graphic and symbolic representation. The phases of the modelling cycle also made it difficult for students to use the graphing calculator, namely in performing statistical regressions and setting the visualization window.
Investigation of noisy audio recordings of speech for processing in an automated system
Authors:   Samara State Technical University, Russian Federation, Volkov Nikita A. , Ivanov Andrei V. ,   Novosibirsk State Technical University, Russian Federation, Karpova Nadegda E. ,   Samara State Technical University, Russian Federation, Chuvakov Alexsander V. ,   Samara State Technical University, Russian Federation
Published: July 2022

This article discusses the possibility of processing sound from noise using a neural network that works with image recognition. To make sure of this, spectrograms of the recorded voice of the speaker with a duration of 10 seconds and spectrograms with white noise superimposed on the recorded audio track were considered. After analyzing the noisy audio track by a sub-jective method (listening to the audio track) and analyzing the spectrograms of the noisy audio track, it was revealed that the neural network will be able to recognize the differences in the images on which the noise is visible. This is necessary in order to further train the neural net-work to recognize the noise intensity of the audio track.
Dualistic relativity: Unification of Einstein’s Special Relativity and de Broglie’s Matter–Wave Theory
Authors: Xiaogang Ruan
Published: July 2022

In Hawking’s view physics has been broken up into many partial theories, while the ultimate goal of physicists is to unify them. The two basic theories of 20th-century physics, relativity theory and quantum theory, are based on completely different logical prerequisites and exactly separate: matter is described as particles in relativity theory and as waves in quantum mechanics. Here, based on the identical logical prerequisites, we unify Einstein’s special relativity (SR) and de Broglie’s matter-wave theory (MWT) into the theory of dualistic relativity (DR), taking a significant step toward the unification of relativity and quantum mechanics. From the definition of time, we derive the Lorentz transformation in differential form and establish the theory of DR, which generalizes the wave-particle duality of matter motion, and uniformly derives Einstein’s formula E=mc2, Planck’s equation E=hf, and de Broglie’s relation λ=h/p. From the logical prerequisite completely different from Einstein’s hypothesis of the invariance of light speed and along the logical path completely different from Einstein’s SR, we have deduced the whole theoretical system of Einstein’s SR and de Broglie’s MWT. In the theory of DR, the two great formulae originally separated, Einstein’s formula E=mc2 and Planck’s equation E=hf, become a pair of twin formulae unified in an identical theoretical system.
Marcadores del discurso como introductores de cita directa: aproximación sociopragmática en el corpus PRESEEA-Sevilla
Authors: Repede Doina
Published: July 2022

El objetivo de este trabajo consiste en llevar a cabo un estudio sobre los diferentes marcadores discursivos ‒pues, en plan, como (que), entonces, etc.‒ que se utilizan en el español hablado de la ciudad de Sevilla para introducir el discurso en estilo directo. Con este fin, manejamos las 72 entrevistas semidirigidas realizadas a informantes sevillanos ‒de nivel de instrucción alto, medio y bajo‒, recogidas entre 2009 y 2018, que conforman el corpus oral PRESEEA (Proyecto para el Estudio Sociolingüístico del español de España y de América) en la ciudad hispalense. Nos proponemos, así, realizar un análisis cualitativo y cuantitativo de los distintos valores de los marcadores discursivos que se relacionan en segundo nivel con la función marcación de cita. Asimismo, desde una metodología sociolingüística variacionista, nos centramos en la relación del empleo de estos marcadores con las variables sexo, edad y nivel de instrucción de los sujetos entrevistados.
[RETRACTED] https://www.facebook.com/DiaetoxilKapseln/ v1
Authors: not provided finneballor
Published: July 2022

[RETRACTED]

Diaetoxil Kapseln: Diaetoxil Kapseln verursacht keine Nebenwirkungen, hilft, überflüssige Pfunde loszuwerden, und in Kombination mit einer richtigen Ernährung und einem angemessenen Trainingsprogramm kurbelt es sanctum Stoffwechsel an, verbessert bite the dust Stimmung und reduziert ernährungsbedingte Müdigkeit. All kicks the bucket, um Diätetiker beim Abnehmen so gesund und komfortabel wie möglich zu halten. Read More@>>https://healthcare24hrs.com/diettoxil-capsule/ https://www.facebook.com/DiaetoxilKapseln/ https://www.outlookindia.com/business-spotlight/diaetoxil-kapseln-h%C3%B6hle-der-l%C3%B6wen-50-discount-not-fake-kaufen-erfahrungen-nebenwirkungen-and-test-news-203820 https://ipsnews.net/business/2022/06/03/diettoxil-reviews-diettoxil-erfahrungen-diaetoxil-kaufen-read-ingredients-benefits-price-buying/ http://ipsnews.net/business/2022/06/06/diaetoxil-reviews-hohle-der-lowen-diaetoxil-kapseln-dietoxil-read-benefits-where-to-buy/ https://ipsnews.net/business/2022/06/08/diaetoxil-kapseln-tablets-apotheke-stiftung-warentest-erleben-kaufen-pillen-zum-abnehmen/ https://ipsnews.net/business/2022/07/01/diaetoxil-avis-france-gelules-diaetoxil-erfahrungen-bezugsquellen-entgiftung-avis/ https://www.facebook.com/diaetoxiltest/ https://www.facebook.com/DietToxilCapsule/ https://www.facebook.com/DiaeToxilErfahrungen/ https://www.facebook.com/DiaetoxilStiftungWarentest/ https://www.facebook.com/DietToxil/ https://www.facebook.com/Diaetoxil-101494945945744 https://www.facebook.com/DiaeToxilReview/ https://www.facebook.com/DietToxilAustria/ https://www.facebook.com/DietToxilWeightloss/ https://www.facebook.com/DiaetoxilKaufen/ https://www.facebook.com/DiaetoxilErfahrungsberichte/ https://www.facebook.com/DiaeToxilReview/ https://www.facebook.com/DiaeToxilBewertungen/ https://www.facebook.com/DiaetoxilApotheke/ https://www.facebook.com/Diaetoxilkapselnavis/ https://www.facebook.com/Diaetoxil-Höhle-Der-Löwen-105672278839192
[RETRACTED] Simpli ACV Keto Gummies ( Warning! Update 2022 ) - Does it Really Work For Diet! v1
Authors: keto Gummies Acv
Published: July 2022

[RETRACTED]

Simpli ACV Keto Gummies