OpenRaiser/Intern-Atlas huggingface dataset:
MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems
Venue: arXiv cs.DM 2021
Year: 2021

Let $V$ be a set of $n$ vertices, ${\cal M}$ a set of $m$ labels, and let $\mathbf{R}$ be an $m \times n$ matrix of independent Bernoulli random variables with success probability $p$. A random instance $G(V,E,\mathbf{R}^T\mathbf{R})$ of the weighted random intersection graph model is constructed by drawing an edge with weight $[\mathbf{R}^T\mathbf{R}]_{v,u}$ between any two vertices $u,v$ for which this weight is larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given $G(V,E,\mathbf{R}^T\mathbf{R})$ we wish to find a partition of $V$ into two sets so that the total weight of the edges having one endpoint in each set is maximized. We initially prove concentration of the weight of a maximum cut of $G(V,E,\mathbf{R}^T\mathbf{R})$ around its expected value, and then show that, when the number of labels is much smaller than the number of vertices, a random partition of the vertices achieves asymptotically optimal cut weight with high probability (whp). Furthermore, in the case $n=m$ and constant average degree, we show that whp, a majority type algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we highlight a connection between the computational problem of finding a weighted maximum cut in $G(V,E,\mathbf{R}^T\mathbf{R})$ and the problem of finding a 2-coloring with minimum discrepancy for a set system $Σ$ with incidence matrix $\mathbf{R}$. We exploit this connection by proposing a (weak) bipartization algorithm for the case $m=n, p=\frac{Θ(1)}{n}$ that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in $Σ$. Finally, we prove that, whp this 2-coloring corresponds to a bipartition with maximum cut-weight in $G(V,E,\mathbf{R}^T\mathbf{R})$.
Existence and Size of the Giant Component in Inhomogeneous Random K-out Graphs
Venue: arXiv cs.IT 2021
Year: 2021

Random K-out graphs are receiving attention as a model to construct sparse yet well-connected topologies in distributed systems including sensor networks, federated learning, and cryptocurrency networks. In response to the growing heterogeneity in emerging real-world networks, where nodes differ in resources and requirements, inhomogeneous random K-out graphs, denoted by $H(n;μ,K_n)$, were proposed recently. Motivated by practical settings where establishing links is costly and only a bounded choice of $K_n$ is feasible ($K_n = O(1)$), we study the size of the largest connected sub-network of $H(n;μ,K_n)$, We first show that the trivial condition of $K_n \geq 2$ for all $n$ is sufficient to ensure that $H(n;μ,K_n)$, contains a giant component of size $n-O(1)$ whp. Next, to model settings where nodes can fail or get compromised, we investigate the size of the largest connected sub-network in $H(n;μ,K_n)$, when $d_n$ nodes are selected uniformly at random and removed from the network. We show that if $d_n=O(1)$, a giant component of size $n- \OO(1)$ persists for all $K_n \geq 2$ whp. Further, when $d_n=o(n)$ nodes are removed from $H(n;μ,K_n)$, the remaining nodes contain a giant component of size $n(1-o(1))$ whp for all $K_n \geq 2$. We present numerical results to demonstrate the size of the largest connected component when the number of nodes is finite.
Multi-domain semantic segmentation with pyramidal fusion
Venue: arXiv cs.CV 2021
Year: 2021

We present our submission to the semantic segmentation contest of the Robust Vision Challenge held at ECCV 2020. The contest requires submitting the same model to seven benchmarks from three different domains. Our approach is based on the SwiftNet architecture with pyramidal fusion. We address inconsistent taxonomies with a single-level 193-dimensional softmax output. We strive to train with large batches in order to stabilize optimization of a hard recognition problem, and to favour smooth evolution of batchnorm statistics. We achieve this by implementing a custom backward step through log-sum-prob loss, and by using small crops before freezing the population statistics. Our model ranks first on the RVC semantic segmentation challenge as well as on the WildDash 2 leaderboard. This suggests that pyramidal fusion is competitive not only for efficient inference with lightweight backbones, but also in large-scale setups for multi-domain application.
Ideological differences in engagement in public debate on Twitter
Venue: arXiv cs.SI 2021
Year: 2021

This article analyses public debate on Twitter via network representations of retweets and replies. We argue that tweets observable on Twitter have both a direct and mediated effect on the perception of public opinion. Through the interplay of the two networks, it is possible to identify potentially misleading representations of public opinion on the platform. The method is employed to observe public debate about two events: The Saxon state elections and violent riots in the city of Leipzig in 2019. We show that in both cases, (i) different opinion groups exhibit different propensities to get involved in debate, and therefore have unequal impact on public opinion. Users retweeting far-right parties and politicians are significantly more active, hence their positions are disproportionately visible. (ii) Said users act significantly more confrontational in the sense that they reply mostly to users from different groups, while the contrary is not the case.
A Design Framework for Strongly $χ^2$-Private Data Disclosure
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study a stochastic disclosure control problem using information-theoretic methods. The useful data to be disclosed depend on private data that should be protected. Thus, we design a privacy mechanism to produce new data which maximizes the disclosed information about the useful data under a strong $χ^2$-privacy criterion. For sufficiently small leakage, the privacy mechanism design problem can be geometrically studied in the space of probability distributions by a local approximation of the mutual information. By using methods from Euclidean information geometry, the original highly challenging optimization problem can be reduced to a problem of finding the principal right-singular vector of a matrix, which characterizes the optimal privacy mechanism. In two extensions we first consider a scenario where an adversary receives a noisy version of the user's message and then we look for a mechanism which finds $U$ based on observing $X$, maximizing the mutual information between $U$ and $Y$ while satisfying the privacy criterion on $U$ and $Z$ under the Markov chain $(Z,Y)-X-U$.
A Software-Defined Networking Solution for Transparent Session and Service Continuity in Dynamic Multi-Access Edge Computing
Venue: arXiv cs.NI 2021
Year: 2021

Multi-Access Edge Computing (MEC) will allow implementing low-latency services that have been unfeasible so far. The European Telecommunications Standards Institute (ETSI) and the 3rd Generation Partnership Project (3GPP) are working towards the standardization of MEC in 5G networks and the corresponding solutions for routing user traffic to applications in local area networks. Nevertheless, there are neither practical implementations for dynamically relocating applications from the core to a MEC host nor from one MEC host to another ensuring service continuity. In this paper we propose a solution based on Software-Defined Networking (SDN) to create a new instance of the IP anchor point to dynamically redirect User Equipment (UE) traffic to a new physical location (e.g. an edge infrastructure). We also present a novel approach that leverages SDN to replicate the previous context of the connection in the new instance of the IP anchor point, thus guaranteeing Session and Service Continuity (SSC), and compare it with alternative state replication strategies. This approach can be used to implement edge services in 4G or 5G networks.
Detection of AI-Synthesized Speech Using Cepstral & Bispectral Statistics
Venue: arXiv cs.LG 2021
Year: 2021

Digital technology has made possible unimaginable applications come true. It seems exciting to have a handful of tools for easy editing and manipulation, but it raises alarming concerns that can propagate as speech clones, duplicates, or maybe deep fakes. Validating the authenticity of a speech is one of the primary problems of digital audio forensics. We propose an approach to distinguish human speech from AI synthesized speech exploiting the Bi-spectral and Cepstral analysis. Higher-order statistics have less correlation for human speech in comparison to a synthesized speech. Also, Cepstral analysis revealed a durable power component in human speech that is missing for a synthesized speech. We integrate both these analyses and propose a machine learning model to detect AI synthesized speech.
TiVGAN: Text to Image to Video Generation with Step-by-Step Evolutionary Generator
Venue: arXiv cs.CV 2021
Year: 2021

Advances in technology have led to the development of methods that can create desired visual multimedia. In particular, image generation using deep learning has been extensively studied across diverse fields. In comparison, video generation, especially on conditional inputs, remains a challenging and less explored area. To narrow this gap, we aim to train our model to produce a video corresponding to a given text description. We propose a novel training framework, Text-to-Image-to-Video Generative Adversarial Network (TiVGAN), which evolves frame-by-frame and finally produces a full-length video. In the first phase, we focus on creating a high-quality single video frame while learning the relationship between the text and an image. As the steps proceed, our model is trained gradually on more number of consecutive frames.This step-by-step learning process helps stabilize the training and enables the creation of high-resolution video based on conditional text descriptions. Qualitative and quantitative experimental results on various datasets demonstrate the effectiveness of the proposed method.
Evaluating the Security and Economic Effects of Moving Target Defense Techniques on the Cloud
Venue: arXiv cs.CR 2021
Year: 2021

Moving Target Defense (MTD) is a proactive security mechanism which changes the attack surface aiming to confuse attackers. Cloud computing leverages MTD techniques to enhance cloud security posture against cyber threats. While many MTD techniques have been applied to cloud computing, there has not been a joint evaluation of the effectiveness of MTD techniques with respect to security and economic metrics. In this paper, we first introduce mathematical definitions for the combination of three MTD techniques: \emph{Shuffle}, \emph{Diversity}, and \emph{Redundancy}. Then, we utilize four security metrics including system risk, attack cost, return on attack, and reliability to assess the effectiveness of the combined MTD techniques applied to large-scale cloud models. Secondly, we focus on a specific context based on a cloud model for E-health applications to evaluate the effectiveness of the MTD techniques using security and economic metrics. We introduce (1) a strategy to effectively deploy Shuffle MTD technique using a virtual machine placement technique and (2) two strategies to deploy Diversity MTD technique through operating system diversification. As deploying Diversity incurs cost, we formulate the \emph{Optimal Diversity Assignment Problem (O-DAP)} and solve it as a binary linear programming model to obtain the assignment which maximizes the expected net benefit.
On the implementation of a global optimization method for mixed-variable problems
Venue: arXiv cs.LG 2021
Year: 2021

We describe the optimization algorithm implemented in the open-source derivative-free solver RBFOpt. The algorithm is based on the radial basis function method of Gutmann and the metric stochastic response surface method of Regis and Shoemaker. We propose several modifications aimed at generalizing and improving these two algorithms: (i) the use of an extended space to represent categorical variables in unary encoding; (ii) a refinement phase to locally improve a candidate solution; (iii) interpolation models without the unisolvence condition, to both help deal with categorical variables, and initiate the optimization before a uniquely determined model is possible; (iv) a master-worker framework to allow asynchronous objective function evaluations in parallel. Numerical experiments show the effectiveness of these ideas.
A Class of Optimal Structures for Node Computations in Message Passing Algorithms
Venue: arXiv cs.IT 2021
Year: 2021

Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ and $\mathbf{y} = (y_1, y_2, \ldots, y_n)$, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing $\mathbf{y}$ from $\mathbf{x}$, where each $y_j, j = 1, 2, \ldots, n$ is computed via a binary tree with leaves $\mathbf{x}$ excluding $x_j$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is $3n - 6$, and if a structure has such complexity, its minimum latency is $δ+ \lceil \log(n-2^δ) \rceil$ with $δ= \lfloor \log(n/2) \rfloor$, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is $\lceil \log(n-1) \rceil$, and if a structure has such latency, its minimum complexity is $n \log(n-1)$ when $n-1$ is a power of two. Third, given $(n, τ)$ with $τ\geq \lceil \log(n-1) \rceil$, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most $τ$. Our construction method runs in $O(n^3 \log^2(n))$ time, and the obtained structure has complexity at most (generally much smaller than) $n \lceil \log(n) \rceil - 2$.
DEFECTCHECKER: Automated Smart Contract Defect Detection by Analyzing EVM Bytecode
Venue: arXiv cs.SE 2021
Year: 2021

Smart contracts are Turing-complete programs running on the blockchain. They are immutable and cannot be modified, even when bugs are detected. Therefore, ensuring smart contracts are bug-free and well-designed before deploying them to the blockchain is extremely important. A contract defect is an error, flaw or fault in a smart contract that causes it to produce an incorrect or unexpected result, or to behave in unintended ways. Detecting and removing contract defects can avoid potential bugs and make programs more robust. Our previous work defined 20 contract defects for smart contracts and divided them into five impact levels. According to our classification, contract defects with seriousness level between 1-3 can lead to unwanted behaviors, e.g., a contract being controlled by attackers. In this paper, we propose DefectChecker, a symbolic execution-based approach and tool to detect eight contract defects that can cause unwanted behaviors of smart contracts on the Ethereum blockchain platform. DefectChecker can detect contract defects from smart contracts bytecode. We compare DefectChecker with key previous works, including Oyente, Mythril and Securify by using an open-source dataset. Our experimental results show that DefectChecker performs much better than these tools in terms of both speed and accuracy. We also applied DefectChecker to 165,621 distinct smart contracts on the Ethereum platform. We found that 25,815 of these smart contracts contain at least one of the contract defects that belongs to impact level 1-3, including some real-world attacks.
Anomaly Detection With Partitioning Overfitting Autoencoder Ensembles
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose POTATOES (Partitioning OverfiTting AuTOencoder EnSemble), a new method for unsupervised outlier detection (UOD). More precisely, given any autoencoder for UOD, this technique can be used to improve its accuracy while at the same time removing the burden of tuning its regularization. The idea is to not regularize at all, but to rather randomly partition the data into sufficiently many equally sized parts, overfit each part with its own autoencoder, and to use the maximum over all autoencoder reconstruction errors as the anomaly score. We apply our model to various realistic datasets and show that if the set of inliers is dense enough, our method indeed improves the UOD performance of a given autoencoder significantly. For reproducibility, the code is made available on github so the reader can recreate the results in this paper as well as apply the method to other autoencoders and datasets.
DV-ConvNet: Fully Convolutional Deep Learning on Point Clouds with Dynamic Voxelization and 3D Group Convolution
Venue: arXiv cs.CV 2021
Year: 2021

3D point cloud interpretation is a challenging task due to the randomness and sparsity of the component points. Many of the recently proposed methods like PointNet and PointCNN have been focusing on learning shape descriptions from point coordinates as point-wise input features, which usually involves complicated network architectures. In this work, we draw attention back to the standard 3D convolutions towards an efficient 3D point cloud interpretation. Instead of converting the entire point cloud into voxel representations like the other volumetric methods, we voxelize the sub-portions of the point cloud only at necessary locations within each convolution layer on-the-fly, using our dynamic voxelization operation with self-adaptive voxelization resolution. In addition, we incorporate 3D group convolution into our dense convolution kernel implementation to further exploit the rotation invariant features of point cloud. Benefiting from its simple fully-convolutional architecture, our network is able to run and converge at a considerably fast speed, while yields on-par or even better performance compared with the state-of-the-art methods on several benchmark datasets.
Collaborative Management of Benchmark Instances and their Attributes
Venue: arXiv cs.AI 2021
Year: 2021

Experimental evaluation is an integral part in the design process of algorithms. Publicly available benchmark instances are widely used to evaluate methods in SAT solving. For the interpretation of results and the design of algorithm portfolios their attributes are crucial. Capturing the interrelation of benchmark instances and their attributes is considerably simplified through our specification of a benchmark instance identifier. Thus, our tool increases the availability of both by providing means to manage and retrieve benchmark instances by their attributes and vice versa. Like this, it facilitates the design and analysis of SAT experiments and the exchange of results.
Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding
Venue: arXiv cs.CR 2021
Year: 2021

Recent advances in natural language generation have introduced powerful language models with high-quality output text. However, this raises concerns about the potential misuse of such models for malicious purposes. In this paper, we study natural language watermarking as a defense to help better mark and trace the provenance of text. We introduce the Adversarial Watermarking Transformer (AWT) with a jointly trained encoder-decoder and adversarial training that, given an input text and a binary message, generates an output text that is unobtrusively encoded with the given message. We further study different training and inference strategies to achieve minimal changes to the semantics and correctness of the input text. AWT is the first end-to-end model to hide data in text by automatically learning -- without ground truth -- word substitutions along with their locations in order to encode the message. We empirically show that our model is effective in largely preserving text utility and decoding the watermark while hiding its presence against adversaries. Additionally, we demonstrate that our method is robust against a range of attacks.
Faster motif counting via succinct color coding and adaptive sampling
Venue: arXiv cs.DS 2021
Year: 2021

We address the problem of computing the distribution of induced connected subgraphs, aka \emph{graphlets} or \emph{motifs}, in large graphs. The current state-of-the-art algorithms estimate the motif counts via uniform sampling, by leveraging the color coding technique by Alon, Yuster and Zwick. In this work we extend the applicability of this approach, by introducing a set of algorithmic optimizations and techniques that reduce the running time and space usage of color coding and improve the accuracy of the counts. To this end, we first show how to optimize color coding to efficiently build a compact table of a representative subsample of all graphlets in the input graph. For $8$-node motifs, we can build such a table in one hour for a graph with $65$M nodes and $1.8$B edges, which is $2000$ times larger than the state of the art. We then introduce a novel adaptive sampling scheme that breaks the "additive error barrier" of uniform sampling, guaranteeing multiplicative approximations instead of just additive ones. This allows us to count not only the most frequent motifs, but also extremely rare ones. For instance, on one graph we accurately count nearly $10.000$ distinct $8$-node motifs whose relative frequency is so small that uniform sampling would literally take centuries to find them. Our results show that color coding is still the most promising approach to scalable motif counting.
Achieving anonymity via weak lower bound constraints for k-median and k-means
Venue: arXiv cs.DS 2021
Year: 2021

We study $k$-clustering problems with lower bounds, including $k$-median and $k$-means clustering with lower bounds. In addition to the point set $P$ and the number of centers $k$, a $k$-clustering problem with (uniform) lower bounds gets a number $B$. The solution space is restricted to clusterings where every cluster has at least $B$ points. We demonstrate how to approximate $k$-median with lower bounds via a reduction to facility location with lower bounds, for which $O(1)$-approximation algorithms are known. Then we propose a new constrained clustering problem with lower bounds where we allow points to be assigned multiple times (to different centers). This means that for every point, the clustering specifies a set of centers to which it is assigned. We call this clustering with weak lower bounds. We give a $(6.5+ε)$-approximation for $k$-median clustering with weak lower bounds and an $O(1)$-approximation for $k$-means with weak lower bounds. We conclude by showing that at a constant increase in the approximation factor, we can restrict the number of assignments of every point to $2$ (or, if we allow fractional assignments, to $1+ε$). This also leads to the first bicritera approximation algorithm for $k$-means with (standard) lower bounds where bicriteria is interpreted in the sense that the lower bounds are violated by a constant factor. All algorithms in this paper run in time that is polynomial in $n$ and $k$ (and $d$ for the Euclidean variants considered).