OpenRaiser/Intern-Atlas huggingface dataset:
STEC-IoT: A Security Tactic by Virtualizing Edge Computing on IoT
Venue: arXiv cs.NI 2022
Year: 2022

To a large extent, the deployment of edge computing (EC) can reduce the burden of the explosive growth of the Internet of things. As a powerful hub between the Internet of things and cloud servers, edge devices make the transmission of cloud to things no longer complicated. However, edge nodes are faced with a series of problems, such as large number, a wide range of distribution, and complex environment, the security of edge computing should not be underestimated. Based on this, we propose a tactic to improve the safety of edge computing by virtualizing edge nodes. In detail, first of all, we propose a strategy of edge node partition, virtualize the edge nodes dealing with different types of things into various virtual networks, which are deployed between the edge nodes and the cloud server. Second, considering that different information transmission has different security requirement, we propose a security tactic based on security level measurement. Finally, through simulation experiments, we compare with the existing advanced algorithms which are committed to virtual network security, and prove that the model proposed in this paper has definite progressiveness in enhancing the security of edge computing.
Anchor Graph Structure Fusion Hashing for Cross-Modal Similarity Search
Venue: arXiv cs.CV 2022
Year: 2022

Cross-modal hashing still has some challenges needed to address: (1) most existing CMH methods take graphs as input to model data distribution. These methods omit to consider the correlation of graph structure among multiple modalities; (2) most existing CMH methods ignores considering the fusion affinity among multi-modalities data; (3) most existing CMH methods relax the discrete constraints to solve the optimization objective, significantly degrading the retrieval performance. To solve the above limitations, we propose a novel Anchor Graph Structure Fusion Hashing (AGSFH). AGSFH constructs the anchor graph structure fusion matrix from different anchor graphs of multiple modalities with the Hadamard product, which can fully exploit the geometric property of underlying data structure. Based on the anchor graph structure fusion matrix, AGSFH attempts to directly learn an intrinsic anchor graph, where the structure of the intrinsic anchor graph is adaptively tuned so that the number of components of the intrinsic graph is exactly equal to the number of clusters. Besides, AGSFH preserves the anchor fusion affinity into the common binary Hamming space. Furthermore, a discrete optimization framework is designed to learn the unified binary codes. Extensive experimental results on three public social datasets demonstrate the superiority of AGSFH.
Constant Approximating Parameterized $k$-SetCover is W[2]-hard
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we prove that it is W[2]-hard to approximate k-SetCover within any constant ratio. Our proof is built upon the recently developed threshold graph composition technique. We propose a strong notion of threshold graphs and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time $o\left(\frac{\log n}{\log \log n}\right)$ ratio approximation algorithms for the non-parameterized k-SetCover problem with $k$ as small as $O\left(\frac{\log n}{\log \log n}\right)^3$, assuming W[1]$\neq$FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.
A.I. and Data-Driven Mobility at Volkswagen Financial Services AG
Venue: arXiv cs.AI 2022
Year: 2022

Machine learning is being widely adapted in industrial applications owing to the capabilities of commercially available hardware and rapidly advancing research. Volkswagen Financial Services (VWFS), as a market leader in vehicle leasing services, aims to leverage existing proprietary data and the latest research to enhance existing and derive new business processes. The collaboration between Information Systems and Machine Learning Lab (ISMLL) and VWFS serves to realize this goal. In this paper, we propose methods in the fields of recommender systems, object detection, and forecasting that enable data-driven decisions for the vehicle life-cycle at VWFS.
Agree to Disagree: Diversity through Disagreement for Better Transferability
Venue: arXiv cs.LG 2022
Year: 2022

Gradient-based learning algorithms have an implicit simplicity bias which in effect can limit the diversity of predictors being sampled by the learning procedure. This behavior can hinder the transferability of trained models by (i) favoring the learning of simpler but spurious features -- present in the training data but absent from the test data -- and (ii) by only leveraging a small subset of predictive features. Such an effect is especially magnified when the test distribution does not exactly match the train distribution -- referred to as the Out of Distribution (OOD) generalization problem. However, given only the training data, it is not always possible to apriori assess if a given feature is spurious or transferable. Instead, we advocate for learning an ensemble of models which capture a diverse set of predictive features. Towards this, we propose a new algorithm D-BAT (Diversity-By-disAgreement Training), which enforces agreement among the models on the training data, but disagreement on the OOD data. We show how D-BAT naturally emerges from the notion of generalized discrepancy, as well as demonstrate in multiple experiments how the proposed method can mitigate shortcut-learning, enhance uncertainty and OOD detection, as well as improve transferability.
Revisiting QMIX: Discriminative Credit Assignment by Gradient Entropy Regularization
Venue: arXiv cs.AI 2022
Year: 2022

In cooperative multi-agent systems, agents jointly take actions and receive a team reward instead of individual rewards. In the absence of individual reward signals, credit assignment mechanisms are usually introduced to discriminate the contributions of different agents so as to achieve effective cooperation. Recently, the value decomposition paradigm has been widely adopted to realize credit assignment, and QMIX has become the state-of-the-art solution. In this paper, we revisit QMIX from two aspects. First, we propose a new perspective on credit assignment measurement and empirically show that QMIX suffers limited discriminability on the assignment of credits to agents. Second, we propose a gradient entropy regularization with QMIX to realize a discriminative credit assignment, thereby improving the overall performance. The experiments demonstrate that our approach can comparatively improve learning efficiency and achieve better performance.
The no-free-lunch theorems of supervised learning
Venue: arXiv cs.LG 2022
Year: 2022

The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. But how could this leave room for a learning theory, that shows that some algorithms are better than others? Drawing parallels to the philosophy of induction, we point out that the no-free-lunch results presuppose a conception of learning algorithms as purely data-driven. On this conception, every algorithm must have an inherent inductive bias, that wants justification. We argue that many standard learning algorithms should rather be understood as model-dependent: in each application they also require for input a model, representing a bias. Generic algorithms themselves, they can be given a model-relative justification.
Sparse superposition codes under VAMP decoding with generic rotational invariant coding matrices
Venue: arXiv cs.IT 2022
Year: 2022

Sparse superposition codes were originally proposed as a capacity-achieving communication scheme over the gaussian channel, whose coding matrices were made of i.i.d. gaussian entries.We extend this coding scheme to more generic ensembles of rotational invariant coding matrices with arbitrary spectrum, which include the gaussian ensemble as a special case. We further introduce and analyse a decoder based on vector approximate message-passing (VAMP).Our main findings, based on both a standard replica symmetric potential theory and state evolution analysis, are the superiority of certain structured ensembles of coding matrices (such as partial row-orthogonal) when compared to i.i.d. matrices, as well as a spectrum-independent upper bound on VAMP's threshold. Most importantly, we derive a simple "spectral criterion " for the scheme to be at the same time capacity-achieving while having the best possible algorithmic threshold, in the "large section size" asymptotic limit. Our results therefore provide practical design principles for the coding matrices in this promising communication scheme.
New hard benchmark functions for global optimization
Venue: arXiv cs.NE 2022
Year: 2022

In this paper, we present some new unimodal, multimodal, and noise test functions to assess the performance of global optimization algorithms. All the test functions are multidimensional problems. The 2-dimension landscape of the proposed functions has been graphically presented in 3D space to show their geometry, however these functions are more complicated in dimensions greater than 3. To show the hardness of these functions, we have made an experimental study with some powerful algorithms such as CEC competition winners: LSHADE, MadDe, and LSHADE-SPACMA algorithms. Besides the novel algorithm, Tangent search algorithm (TSA) and its modified Tangent search algorithm (mTSA) were also used in the experimental study. The results found demonstrate the hardness of the proposed functions. The code sources of the proposed test functions are available on Matlab Exchange website. https://www.mathworks.com/matlabcentral/fileexchange/106450-new-hard-benchmark-functions-for-global-optimization?s_tid=srchtitle
Task Modifiers for HTN Planning and Acting
Venue: arXiv cs.AI 2022
Year: 2022

The ability of an agent to change its objectives in response to unexpected events is desirable in dynamic environments. In order to provide this capability to hierarchical task network (HTN) planning, we propose an extension of the paradigm called task modifiers, which are functions that receive a task list and a state and produce a new task list. We focus on a particular type of problems in which planning and execution are interleaved and the ability to handle exogenous events is crucial. To determine the efficacy of this approach, we evaluate the performance of our task modifier implementation in two environments, one of which is a simulation that differs substantially from traditional HTN domains.
Automated Discovery of Geometrical Theorems in GeoGebra
Venue: arXiv cs.CG 2022
Year: 2022

We describe a prototype of a new experimental GeoGebra command and tool, Discover, that analyzes geometric figures for salient patterns, properties, and theorems. This tool is a basic implementation of automated discovery in elementary planar geometry. The paper focuses on the mathematical background of the implementation, as well as methods to avoid combinatorial explosion when storing the interesting properties of a geometric figure.
"I feel invaded, annoyed, anxious and I may protect myself": Individuals' Feelings about Online Tracking and their Protective Behaviour across Gender and Country
Venue: arXiv cs.HC 2022
Year: 2022

Online tracking is a primary concern for Internet users, yet previous research has not found a clear link between the cognitive understanding of tracking and protective actions. We postulate that protective behaviour follows affective evaluation of tracking. We conducted an online study, with N=614 participants, across the UK, Germany and France, to investigate how users feel about third-party tracking and what protective actions they take. We found that most participants' feelings about tracking were negative, described as deeply intrusive - beyond the informational sphere, including feelings of annoyance and anxiety, that predict protective actions. We also observed indications of a `privacy gender gap', where women feel more negatively about tracking, yet are less likely to take protective actions, compared to men. And less UK individuals report negative feelings and protective actions, compared to those from Germany and France. This paper contributes insights into the affective evaluation of privacy threats and how it predicts protective behaviour. It also provides a discussion on the implications of these findings for various stakeholders, make recommendations and outline avenues for future work.
Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response
Venue: arXiv cs.AI 2022
Year: 2022

In response to COVID-19, many countries have mandated social distancing and banned large group gatherings in order to slow down the spread of SARS-CoV-2. These social interventions along with vaccines remain the best way forward to reduce the spread of SARS CoV-2. In order to increase vaccine accessibility, states such as Virginia have deployed mobile vaccination centers to distribute vaccines across the state. When choosing where to place these sites, there are two important factors to take into account: accessibility and equity. We formulate a combinatorial problem that captures these factors and then develop efficient algorithms with theoretical guarantees on both of these aspects. Furthermore, we study the inherent hardness of the problem, and demonstrate strong impossibility results. Finally, we run computational experiments on real-world data to show the efficacy of our methods.
The Landscape of Distributed Complexities on Trees and Beyond
Venue: arXiv cs.DS 2022
Year: 2022

We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below $\log^* n$. Our contribution is threefold: Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity $o(\log^* n)$ has actually complexity $O(1)$. This result improves upon the previous speedup result from $o(\log \log^* n)$ to $O(1)$ by [Chang, Pettie, FOCS 2017]. In the related LCA and Volume models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020], we prove the same speedup from $o(\log^* n)$ to $O(1)$ for all bounded degree graphs. Similarly, we complete the classification of the LOCAL complexity landscape of oriented $d$-dimensional grids by proving that any LCL problem with local complexity $o(\log^* n)$ has actually complexity $O(1)$. This improves upon the previous speed-up from $o(\sqrt[d]{\log^* n})$ by Suomela in [Chang, Pettie, FOCS 2017].
Terrain parameter estimation from proprioceptive sensing of the suspension dynamics in offroad vehicles
Venue: arXiv cs.RO 2022
Year: 2022

Offroad vehicle movement has to contend with uneven and uncertain terrain which present challenges to path planning and motion control for both manned and unmanned ground vehicles. Knowledge of terrain properties can allow a vehicle to adapt its control and motion planning algorithms. Terrain properties, however, can change on time scales of days or even hours, necessitating their online estimation. The kinematics and, in particular the oscillations experienced by an offroad vehicle carry a signature of the terrain properties. These terrain properties can thus be estimated from proprioceptive sensing of the vehicle dynamics with an appropriate model and estimation algorithm. In this paper, we show that knowledge of the vertical dynamics of a vehicle due to its suspension can enable faster and more accurate estimation of terrain parameters. The paper considers a five degree of freedom model that combines the well known half-car and bicycle models. We show through simulation that the sinkage exponent, a parameter that can significantly influence the wheel forces from the terrain and thus greatly impact the vehicle trajectory, can be estimated from measurements of the vehicle's linear acceleration and rotational velocity, which can be readily obtained from an onboard IMU. We show that modelling the vertical vehicle dynamics can lead to significant improvement in both the estimation of terrain parameters and the prediction of the vehicle trajectory.
Coarsening the Granularity: Towards Structurally Sparse Lottery Tickets
Venue: arXiv cs.LG 2022
Year: 2022

The lottery ticket hypothesis (LTH) has shown that dense models contain highly sparse subnetworks (i.e., winning tickets) that can be trained in isolation to match full accuracy. Despite many exciting efforts being made, there is one "commonsense" rarely challenged: a winning ticket is found by iterative magnitude pruning (IMP) and hence the resultant pruned subnetworks have only unstructured sparsity. That gap limits the appeal of winning tickets in practice, since the highly irregular sparse patterns are challenging to accelerate on hardware. Meanwhile, directly substituting structured pruning for unstructured pruning in IMP damages performance more severely and is usually unable to locate winning tickets. In this paper, we demonstrate the first positive result that a structurally sparse winning ticket can be effectively found in general. The core idea is to append "post-processing techniques" after each round of (unstructured) IMP, to enforce the formation of structural sparsity. Specifically, we first "re-fill" pruned elements back in some channels deemed to be important, and then "re-group" non-zero elements to create flexible group-wise structural patterns. Both our identified channel- and group-wise structural subnetworks win the lottery, with substantial inference speedups readily supported by existing hardware. Extensive experiments, conducted on diverse datasets across multiple network backbones, consistently validate our proposal, showing that the hardware acceleration roadblock of LTH is now removed. Specifically, the structural winning tickets obtain up to {64.93%, 64.84%, 60.23%} running time savings at {36%~80%, 74%, 58%} sparsity on {CIFAR, Tiny-ImageNet, ImageNet}, while maintaining comparable accuracy. Code is at https://github.com/VITA-Group/Structure-LTH.
DeepSSN: a deep convolutional neural network to assess spatial scene similarity
Venue: arXiv cs.CV 2022
Year: 2022

Spatial-query-by-sketch is an intuitive tool to explore human spatial knowledge about geographic environments and to support communication with scene database queries. However, traditional sketch-based spatial search methods perform insufficiently due to their inability to find hidden multi-scale map features from mental sketches. In this research, we propose a deep convolutional neural network, namely Deep Spatial Scene Network (DeepSSN), to better assess the spatial scene similarity. In DeepSSN, a triplet loss function is designed as a comprehensive distance metric to support the similarity assessment. A positive and negative example mining strategy using qualitative constraint networks in spatial reasoning is designed to ensure a consistently increasing distinction of triplets during the training process. Moreover, we develop a prototype spatial scene search system using the proposed DeepSSN, in which the users input spatial query via sketch maps and the system can automatically augment the sketch training data. The proposed model is validated using multi-source conflated map data including 131,300 labeled scene samples after data augmentation. The empirical results demonstrate that the DeepSSN outperforms baseline methods including k-nearest-neighbors, multilayer perceptron, AlexNet, DenseNet, and ResNet using mean reciprocal rank and precision metrics. This research advances geographic information retrieval studies by introducing a novel deep learning method tailored to spatial scene queries.
Providing Real-time Assistance for Repairing Runtime Exceptions using Stack Overflow Posts
Venue: arXiv cs.SE 2022
Year: 2022

Runtime Exceptions (REs) are an important class of bugs that occur frequently during code development. Traditional Automatic Program Repair (APR) tools are of limited use in this "in-development" use case, since they require a test-suite to be available as a patching oracle. Thus, developers typically tend to manually resolve their in-development REs, often by referring to technical forums, such as Stack Overflow (SO). To automate this manual process we extend our previous work, MAESTRO, to provide real-time assistance to developers for repairing Java REs by recommending a relevant patch-suggesting SO post and synthesizing a repair patch from this post to fix the RE in the developer's code. MAESTRO exploits a library of Runtime Exception Patterns (REPs) semi-automatically mined from SO posts, through a relatively inexpensive, one-time, incremental process. An REP is an abstracted sequence of statements that triggers a given RE. REPs are used to index SO posts, retrieve a post most relevant to the RE instance exhibited by a developer's code and then mediate the process of extracting a concrete repair from the SO post, abstracting out post-specific details, and concretizing the repair to the developer's buggy code. We evaluate MAESTRO on a published RE benchmark comprised of 78 instances. MAESTRO is able to generate a correct repair patch at the top position in 27% of the cases, within the top-3 in 40% of the cases and overall return a useful artifact in 81% of the cases. Further, the use of REPs proves instrumental to all aspects of MAESTRO's performance, from ranking and searching of SO posts to synthesizing patches from a given post. In particular, 45% of correct patches generated by MAESTRO could not be produced by a baseline technique not using REPs, even when provided with MAESTRO's SO-post ranking. MAESTRO is also fast, needing around 1 second, on average, to generate its output.
Boosting Graph Neural Networks by Injecting Pooling in Message Passing
Venue: arXiv cs.LG 2022
Year: 2022

There has been tremendous success in the field of graph neural networks (GNNs) as a result of the development of the message-passing (MP) layer, which updates the representation of a node by combining it with its neighbors to address variable-size and unordered graphs. Despite the fruitful progress of MP GNNs, their performance can suffer from over-smoothing, when node representations become too similar and even indistinguishable from one another. Furthermore, it has been reported that intrinsic graph structures are smoothed out as the GNN layer increases. Inspired by the edge-preserving bilateral filters used in image processing, we propose a new, adaptable, and powerful MP framework to prevent over-smoothing. Our bilateral-MP estimates a pairwise modular gradient by utilizing the class information of nodes, and further preserves the global graph structure by using the gradient when the aggregating function is applied. Our proposed scheme can be generalized to all ordinary MP GNNs. Experiments on five medium-size benchmark datasets using four state-of-the-art MP GNNs indicate that the bilateral-MP improves performance by alleviating over-smoothing. By inspecting quantitative measurements, we additionally validate the effectiveness of the proposed mechanism in preventing the over-smoothing issue.