OpenRaiser/Intern-Atlas huggingface dataset:
Noisy Boolean Hidden Matching with Applications
Venue: arXiv cs.DS 2022
Year: 2022

The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et. al. [STOC'07], has played an important role in the streaming lower bounds for graph problems such as triangle and subgraph counting, maximum matching, MAX-CUT, Schatten $p$-norm approximation, maximum acyclic subgraph, testing bipartiteness, $k$-connectivity, and cycle-freeness. The one-way communication complexity of the Boolean Hidden Matching problem on a universe of size $n$ is $Θ(\sqrt{n})$, resulting in $Ω(\sqrt{n})$ lower bounds for constant factor approximations to several of the aforementioned graph problems. The related (and, in fact, more general) Boolean Hidden Hypermatching (BHH) problem introduced by Verbin and Yu [SODA'11] provides an approach to proving higher lower bounds of $Ω(n^{1-1/t})$ for integer $t\geq 2$. Reductions based on Boolean Hidden Hypermatching generate distributions on graphs with connected components of diameter about $t$, and basically show that long range exploration is hard in the streaming model of computation with adversarial arrivals. In this paper we introduce a natural variant of the BHM problem, called noisy BHM (and its natural noisy BHH variant), that we use to obtain higher than $Ω(\sqrt{n})$ lower bounds for approximating several of the aforementioned problems in graph streams when the input graphs consist only of components of diameter bounded by a fixed constant. We also use the noisy BHM problem to show that the problem of classifying whether an underlying graph is isomorphic to a complete binary tree in insertion-only streams requires $Ω(n)$ space, which seems challenging to show using BHM or BHH alone.
Temporal Nuances of Coordination Network Semantics
Venue: arXiv cs.SI 2022
Year: 2022

Current network-based methods for detecting coordinated inauthentic behaviour on social media focus primarily on inferring links between accounts based on common "behavioural traces" [19], such as retweeting the same tweet or posting the same URL. Assuming the goal of coordination is amplification, boosting a message within a constrained period, most approaches use a temporal window to ensure the co-activity occurs within a specific timeframe [9, 14, 19, 24]. Real-world application requires considering near real-time processing, creating performance requirements, which also highlight gaps in the semantics of coordination in the literature. These methods could all exploit temporal elements of coordinated activity. We describe preliminary research regarding coordination network semantics, coordination network construction, relevant observations in three political Twitter datasets and the role of cheerleaders in revealing social bots.
DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
Venue: arXiv cs.DS 2022
Year: 2022

Kernel Density Estimation (KDE) is a nonparametric method for estimating the shape of a density function, given a set of samples from the distribution. Recently, locality-sensitive hashing, originally proposed as a tool for nearest neighbor search, has been shown to enable fast KDE data structures. However, these approaches do not take advantage of the many other advances that have been made in algorithms for nearest neighbor algorithms. We present an algorithm called Density Estimation from Approximate Nearest Neighbors (DEANN) where we apply Approximate Nearest Neighbor (ANN) algorithms as a black box subroutine to compute an unbiased KDE. The idea is to find points that have a large contribution to the KDE using ANN, compute their contribution exactly, and approximate the remainder with Random Sampling (RS). We present a theoretical argument that supports the idea that an ANN subroutine can speed up the evaluation. Furthermore, we provide a C++ implementation with a Python interface that can make use of an arbitrary ANN implementation as a subroutine for kernel density estimation. We show empirically that our implementation outperforms state of the art implementations in all high dimensional datasets we considered, and matches the performance of RS in cases where the ANN yield no gains in performance.
FedFog: Network-Aware Optimization of Federated Learning over Wireless Fog-Cloud Systems
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) is capable of performing large distributed machine learning tasks across multiple edge users by periodically aggregating trained local parameters. To address key challenges of enabling FL over a wireless fog-cloud system (e.g., non-i.i.d. data, users' heterogeneity), we first propose an efficient FL algorithm based on Federated Averaging (called FedFog) to perform the local aggregation of gradient parameters at fog servers and global training update at the cloud. Next, we employ FedFog in wireless fog-cloud systems by investigating a novel network-aware FL optimization problem that strikes the balance between the global loss and completion time. An iterative algorithm is then developed to obtain a precise measurement of the system performance, which helps design an efficient stopping criteria to output an appropriate number of global rounds. To mitigate the straggler effect, we propose a flexible user aggregation strategy that trains fast users first to obtain a certain level of accuracy before allowing slow users to join the global training updates. Extensive numerical results using several real-world FL tasks are provided to verify the theoretical convergence of FedFog. We also show that the proposed co-design of FL and communication is essential to substantially improve resource utilization while achieving comparable accuracy of the learning model.
Stable graphs of bounded twin-width
Venue: arXiv cs.LO 2022
Year: 2022

We prove that every class of graphs $\mathscr C$ that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth and of bounded cliquewidth. It also implies that monadically stable classes of bounded twin-widthare linearly $χ$-bounded.
Contrastive Learning for Robust Android Malware Familial Classification
Venue: arXiv cs.CR 2022
Year: 2022

Due to its open-source nature, Android operating system has been the main target of attackers to exploit. Malware creators always perform different code obfuscations on their apps to hide malicious activities. Features extracted from these obfuscated samples through program analysis contain many useless and disguised features, which leads to many false negatives. To address the issue, in this paper, we demonstrate that obfuscation-resilient malware family analysis can be achieved through contrastive learning. The key insight behind our analysis is that contrastive learning can be used to reduce the difference introduced by obfuscation while amplifying the difference between malware and other types of malware. Based on the proposed analysis, we design a system that can achieve robust and interpretable classification of Android malware. To achieve robust classification, we perform contrastive learning on malware samples to learn an encoder that can automatically extract robust features from malware samples. To achieve interpretable classification, we transform the function call graph of a sample into an image by centrality analysis. Then the corresponding heatmaps can be obtained by visualization techniques. These heatmaps can help users understand why the malware is classified as this family. We implement \emph{IFDroid} and perform extensive evaluations on two datasets. Experimental results show that \emph{IFDroid} is superior to state-of-the-art Android malware familial classification systems. Moreover, \emph{IFDroid} is capable of maintaining a 98.4\% F1 on classifying 69,421 obfuscated malware samples.
Serverless Computing: A Security Perspective
Venue: arXiv cs.CR 2022
Year: 2022

Serverless Computing is a virtualisation-related paradigm that promises to simplify application management and to solve the last challenges in the field: scale down and easy to use. The implied cost reduction, coupled with a simplified management of underlying applications, are expected to further push the adoption of virtualisation-based solutions, including cloud-computing or telco-cloud solutions. However, in this quest for efficiency, security is not ranked among the top priorities, also because of the (misleading) belief that current solutions developed for virtualised environments could be applied (as is) to this new paradigm. Unfortunately, this is not the case, due to the highlighted idiosyncratic features of serverless computing. In this paper, we review the current serverless architectures, abstract and categorise their founding principles, and provide an in depth analyse of them from the point of view of security, referring to principles and practices of the cybersecurity domain. In particular, we show the security shortcomings of the analysed serverless architectural paradigms, point to possible countermeasures, and highlight a few research directions.
Keep That Card in Mind: Card Guessing with Limited Memory
Venue: arXiv cs.CC 2022
Year: 2022

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then the card is discarded from the deck. The Guesser receives a point for each correctly guessed card. With perfect memory, a Guesser can keep track of all cards that were played so far and pick at random a card that has not appeared so far, yielding in expectation $\ln n$ correct guesses. With no memory, the best a Guesser can do will result in a single guess in expectation. We consider the case of a memory bounded Guesser that has $m < n$ memory bits. We show that the performance of such a memory bounded Guesser depends much on the behavior of the Dealer. In more detail, we show that there is a gap between the static case, where the Dealer draws cards from a properly shuffled deck or a prearranged one, and the adaptive case, where the Dealer draws cards thoughtfully, in an adversarial manner. Specifically: 1. We show a Guesser with $O(\log^2 n)$ memory bits that scores a near optimal result against any static Dealer. 2. We show that no Guesser with $m$ bits of memory can score better than $O(\sqrt{m})$ correct guesses, thus, no Guesser can score better than $\min \{\sqrt{m}, \ln n\}$, i.e., the above Guesser is optimal. 3. We show an efficient adaptive Dealer against which no Guesser with $m$ memory bits can make more than $\ln m + 2 \ln \log n + O(1)$ correct guesses in expectation. These results are (almost) tight, and we prove them using compression arguments that harness the guessing strategy for encoding.
On Margins and Derandomisation in PAC-Bayes
Venue: arXiv cs.LG 2022
Year: 2022

We give a general recipe for derandomising PAC-Bayesian bounds using margins, with the critical ingredient being that our randomised predictions concentrate around some value. The tools we develop straightforwardly lead to margin bounds for various classifiers, including linear prediction -- a class that includes boosting and the support vector machine -- single-hidden-layer neural networks with an unusual \(\erf\) activation function, and deep ReLU networks. Further, we extend to partially-derandomised predictors where only some of the randomness is removed, letting us extend bounds to cases where the concentration properties of our predictors are otherwise poor.
Greedy structure learning from data that contain systematic missing values
Venue: arXiv cs.LG 2022
Year: 2022

Learning from data that contain missing values represents a common phenomenon in many domains. Relatively few Bayesian Network structure learning algorithms account for missing data, and those that do tend to rely on standard approaches that assume missing data are missing at random, such as the Expectation-Maximisation algorithm. Because missing data are often systematic, there is a need for more pragmatic methods that can effectively deal with data sets containing missing values not missing at random. The absence of approaches that deal with systematic missing data impedes the application of BN structure learning methods to real-world problems where missingness are not random. This paper describes three variants of greedy search structure learning that utilise pairwise deletion and inverse probability weighting to maximally leverage the observed data and to limit potential bias caused by missing values. The first two of the variants can be viewed as sub-versions of the third and best performing variant, but are important in their own in illustrating the successive improvements in learning accuracy. The empirical investigations show that the proposed approach outperforms the commonly used and state-of-the-art Structural EM algorithm, both in terms of learning accuracy and efficiency, as well as both when data are missing at random and not at random.
Massive MIMO Communication with Intelligent Reflecting Surface
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies the feasibility of deploying intelligent reflecting surfaces (IRSs) in massive MIMO (multiple-input multiple-output) systems to improve the performance of users in the service dead zone. To reduce the channel training overhead, we advocate a novel protocol for the uplink communication in the IRS-assisted massive MIMO systems. Under this protocol, the IRS reflection coefficients are optimized based on the channel covariance matrices, which are generally fixed for many coherence blocks, to boost the long-term performance. Then, given the IRS reflecting coefficients, the BS beamforming vectors are designed in each coherence block based on the effective channel of each user, which is the superposition of its direct and reflected user-IRS-BS channels, to improve the instantaneous performance. Since merely the user effective channels are estimated in each coherence block, the training overhead of this protocol is the same as that in the legacy wireless systems without IRSs. Moreover, in the asymptotic regime that the numbers of IRS elements and BS antennas both go to infinity with a fixed ratio, we manage to first characterize the minimum mean-squared error (MMSE) estimators of the user effective channels and then quantify the closed-form user achievable rates as functions of channel covariance matrices with channel training overhead and estimation error taken into account. Interestingly, it is shown that the properties of channel hardening and favorable propagation still hold for the user effective channels, and satisfactory user rates are thus achievable even if simple BS beamforming solutions, e.g., maximal-ratio combining, are employed. Finally, thanks to the rate characterization, we design a low-complexity algorithm to optimize the IRS reflection coefficients based on channel covariance matrices.
ADAST: Attentive Cross-domain EEG-based Sleep Staging Framework with Iterative Self-Training
Venue: arXiv cs.LG 2022
Year: 2022

Sleep staging is of great importance in the diagnosis and treatment of sleep disorders. Recently, numerous data-driven deep learning models have been proposed for automatic sleep staging. They mainly train the model on a large public labeled sleep dataset and test it on a smaller one with subjects of interest. However, they usually assume that the train and test data are drawn from the same distribution, which may not hold in real-world scenarios. Unsupervised domain adaption (UDA) has been recently developed to handle this domain shift problem. However, previous UDA methods applied for sleep staging have two main limitations. First, they rely on a totally shared model for the domain alignment, which may lose the domain-specific information during feature extraction. Second, they only align the source and target distributions globally without considering the class information in the target domain, which hinders the classification performance of the model while testing. In this work, we propose a novel adversarial learning framework called ADAST to tackle the domain shift problem in the unlabeled target domain. First, we develop an unshared attention mechanism to preserve the domain-specific features in both domains. Second, we design an iterative self-training strategy to improve the classification performance on the target domain via target domain pseudo labels. We also propose dual distinct classifiers to increase the robustness and quality of the pseudo labels. The experimental results on six cross-domain scenarios validate the efficacy of our proposed framework and its advantage over state-of-the-art UDA methods. The source code is available at https://github.com/emadeldeen24/ADAST.
1-convex extensions of incomplete cooperative games and the average value
Venue: arXiv cs.GT 2022
Year: 2022

The model of incomplete cooperative games incorporates uncertainty into the classical model of cooperative games by considering a partial characteristic function. Thus the values for some of the coalitions are not known. The main focus of this paper is the class of 1-convex cooperative games under this framework. We are interested in two heavily intertwined questions. First, given an incomplete game, in which ways can we fill in the missing values to obtain a classical 1-convex game? Such complete games are called \emph{1-convex extensions}. For the class of minimal incomplete games (in which precisely the values of singletons and grand coalitions are known), we provide an answer in terms of a description of the set of 1-convex extensions. The description employs extreme points and extreme rays of the set. Second, how to determine in a rational, fair, and efficient way the payoffs of players based only on the known values of coalitions? Based on the description of the set of 1-convex extensions, we introduce generalisations of three solution concepts (values) for complete games, namely the $τ$-value, the Shapley value and the nucleolus. We consider two variants where we compute the centre of gravity of either extreme games or of a combination of extreme games and extreme rays. We show that all of the generalised values coincide for minimal incomplete games which allows to introduce the \emph{average value}. For this value, we provide three different axiomatisations based on axiomatic characterisations of the $τ$-value and the Shapley value for classical cooperative games. Finally, we turn our attention to \emph{incomplete games with defined upper vector}, asking the same questions and this time arriving to different conclusions. This provides a benchmark to test our tools and knowledge of the average value.
Aligning Correlation Information for Domain Adaptation in Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Domain adaptation (DA) approaches address domain shift and enable networks to be applied to different scenarios. Although various image DA approaches have been proposed in recent years, there is limited research towards video DA. This is partly due to the complexity in adapting the different modalities of features in videos, which includes the correlation features extracted as long-term dependencies of pixels across spatiotemporal dimensions. The correlation features are highly associated with action classes and proven their effectiveness in accurate video feature extraction through the supervised action recognition task. Yet correlation features of the same action would differ across domains due to domain shift. Therefore we propose a novel Adversarial Correlation Adaptation Network (ACAN) to align action videos by aligning pixel correlations. ACAN aims to minimize the distribution of correlation information, termed as Pixel Correlation Discrepancy (PCD). Additionally, video DA research is also limited by the lack of cross-domain video datasets with larger domain shifts. We, therefore, introduce a novel HMDB-ARID dataset with a larger domain shift caused by a larger statistical difference between domains. This dataset is built in an effort to leverage current datasets for dark video classification. Empirical results demonstrate the state-of-the-art performance of our proposed ACAN for both existing and the new video DA datasets.
Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent
Venue: arXiv cs.LG 2022
Year: 2022

Data representation techniques have made a substantial contribution to advancing data processing and machine learning (ML). Improving predictive power was the focus of previous representation techniques, which unfortunately perform rather poorly on the interpretability in terms of extracting underlying insights of the data. Recently, the Kolmogorov model (KM) was studied, which is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. The existing KM learning algorithms using semi-definite relaxation with randomization (SDRwR) or discrete monotonic optimization (DMO) have, however, limited utility to big data applications because they do not scale well computationally. In this paper, we propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. To make our method more scalable to large-dimensional problems, we propose two acceleration schemes, namely, the eigenvalue decomposition (EVD) elimination strategy and an approximate EVD algorithm. Furthermore, a thresholding technique by exploiting the error bound analysis and leveraging the normalized Minkowski $\ell_1$-norm, is provided for the selection of the number of iterations of the approximate EVD algorithm. When applied to big data applications, it is demonstrated that the proposed method can achieve compatible training/prediction performance with significantly reduced computational complexity; roughly two orders of magnitude improvement in terms of the time overhead, compared to the existing KM learning algorithms. Furthermore, it is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds $80\%$.
Dual Training of Energy-Based Models with Overparametrized Shallow Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Energy-based models (EBMs) are generative models that are usually trained via maximum likelihood estimation. This approach becomes challenging in generic situations where the trained energy is non-convex, due to the need to sample the Gibbs distribution associated with this energy. Using general Fenchel duality results, we derive variational principles dual to maximum likelihood EBMs with shallow overparametrized neural network energies, both in the feature-learning and lazy linearized regimes. In the feature-learning regime, this dual formulation justifies using a two time-scale gradient ascent-descent (GDA) training algorithm in which one updates concurrently the particles in the sample space and the neurons in the parameter space of the energy. We also consider a variant of this algorithm in which the particles are sometimes restarted at random samples drawn from the data set, and show that performing these restarts at every iteration step corresponds to score matching training. These results are illustrated in simple numerical experiments, which indicates that GDA performs best when features and particles are updated using similar time scales.