OpenRaiser/Intern-Atlas huggingface dataset:
Joint position and trajectory optimization of flying base station in 5G cellular networks, based on users' current and predicted location
Venue: arXiv cs.NI 2022
Year: 2022

Nowadays, Unmanned Aerial Vehicles (UAVs) have been significantly improved, and one of their most important applications is to provide temporary coverage for cellular users. Static Base Station cannot service all users due to temporary crashes because of temporary events such as ground BS breakdowns, bad weather conditions, natural disasters, transmission errors, etc., drones equipped with small cellular BS. The Drone Base Station is immediately sent to the target location and establishes the necessary communication links without requiring any predetermined infrastructure and covers that area. Finding the optimal location and the appropriate number (DBS) of drone-BS in this area is a challenge. Therefore, in this paper, the optimal location and optimal number of DBSs are distributed in the current state of the users and the subsequent user states determined by the prediction. Finally, the DBS transition is optimized from the current state to the predicted future locations. The simulation results show that the proposed method can provide acceptable coverage on the network.
MetaKG: Meta-learning on Knowledge Graph for Cold-start Recommendation
Venue: arXiv cs.IR 2022
Year: 2022

A knowledge graph (KG) consists of a set of interconnected typed entities and their attributes. Recently, KGs are popularly used as the auxiliary information to enable more accurate, explainable, and diverse user preference recommendations. Specifically, existing KG-based recommendation methods target modeling high-order relations/dependencies from long connectivity user-item interactions hidden in KG. However, most of them ignore the cold-start problems (i.e., user cold-start and item cold-start) of recommendation analytics, which restricts their performance in scenarios when involving new users or new items. Inspired by the success of meta-learning on scarce training samples, we propose a novel meta-learning based framework called MetaKG, which encompasses a collaborative-aware meta learner and a knowledge-aware meta learner, to capture meta users' preference and entities' knowledge for cold-start recommendations. The collaborative-aware meta learner aims to locally aggregate user preferences for each user preference learning task. In contrast, the knowledge-aware meta learner is to globally generalize knowledge representation across different user preference learning tasks. Guided by two meta learners, MetaKG can effectively capture the high-order collaborative relations and semantic representations, which could be easily adapted to cold-start scenarios. Besides, we devise a novel adaptive task scheduler which can adaptively select the informative tasks for meta learning in order to prevent the model from being corrupted by noisy tasks. Extensive experiments on various cold-start scenarios using three real data sets demonstrate that our presented MetaKG outperforms all the existing state-of-the-art competitors in terms of effectiveness, efficiency, and scalability.
GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs
Venue: arXiv cs.LG 2022
Year: 2022

We argue that when comparing two graphs, the distribution of node structural features is more informative than global graph statistics which are often used in practice, especially to evaluate graph generative models. Thus, we present GraphDCA - a framework for evaluating similarity between graphs based on the alignment of their respective node representation sets. The sets are compared using a recently proposed method for comparing representation spaces, called Delaunay Component Analysis (DCA), which we extend to graph data. To evaluate our framework, we generate a benchmark dataset of graphs exhibiting different structural patterns and show, using three node structure feature extractors, that GraphDCA recognizes graphs with both similar and dissimilar local structure. We then apply our framework to evaluate three publicly available real-world graph datasets and demonstrate, using gradual edge perturbations, that GraphDCA satisfyingly captures gradually decreasing similarity, unlike global statistics. Finally, we use GraphDCA to evaluate two state-of-the-art graph generative models, NetGAN and CELL, and conclude that further improvements are needed for these models to adequately reproduce local structural features.
Predicting Voting Outcomes in the Presence of Communities, Echo Chambers and Multiple Parties
Venue: arXiv cs.SI 2022
Year: 2022

A recently proposed graph-theoretic metric, the influence gap, has shown to be a reliable predictor of the effect of social influence in two-party elections, albeit only tested on regular and scale-free graphs. Here, we investigate whether the influence gap is able to predict the outcome of multi-party elections on networks exhibiting community structure, i.e., made of highly interconnected components, and therefore more resembling of real-world interaction. To encode communities we build on the classical model of caveman graphs, which we extend to a richer graph family that displays different levels of homophily, i.e., how much connections and opinions are intertwined. First, we study the predictive power of the influence gap in the presence of communities. We show that when there is no clear initial majority the influence gap is not a good predictor of the election outcome. When we instead allow for varying majorities, although the influence gap improves as a predictor, counting the initial partisan majority does consistently better, across all levels of homophily. Second, we study the combined effect of the more predictive metrics, as function of the homophily levels. Using regression models, we demonstrate that the influence gap combined with the initial votes count does increase the overall predictive power for some levels of homophily. Third, we study elections with more than two parties. Specifically, we extend the definition of the influence gap to any number of parties, considering various generalisations, and show that the initial votes count has an even higher predictive power when compared to influence gap than it did in the two-party case.
Data Consistency for Weakly Supervised Learning
Venue: arXiv cs.LG 2022
Year: 2022

In many applications, training machine learning models involves using large amounts of human-annotated data. Obtaining precise labels for the data is expensive. Instead, training with weak supervision provides a low-cost alternative. We propose a novel weak supervision algorithm that processes noisy labels, i.e., weak signals, while also considering features of the training data to produce accurate labels for training. Our method searches over classifiers of the data representation to find plausible labelings. We call this paradigm data consistent weak supervision. A key facet of our framework is that we are able to estimate labels for data examples low or no coverage from the weak supervision. In addition, we make no assumptions about the joint distribution of the weak signals and true labels of the data. Instead, we use weak signals and the data features to solve a constrained optimization that enforces data consistency among the labels we generate. Empirical evaluation of our method on different datasets shows that it significantly outperforms state-of-the-art weak supervision methods on both text and image classification tasks.
The amazing mixed polynomial closure and its applications to two-variable first-order logic
Venue: arXiv cs.FL 2022
Year: 2022

Polynomial closure is a standard operator which is applied to a class of regular languages. In the paper, we investigate three restrictions called left (LPol), right (RPol) and mixed polynomial closure (MPol). The first two were known while MPol is new. We look at two decision problems that are defined for every class C. Membership takes a regular language as input and asks if it belongs to C. Separation takes two regular languages as input and asks if there exists a third language in C including the first one and disjoint from the second. We prove that LPol, RPol and MPol preserve the decidability of membership under mild hypotheses on the input class, and the decidability of separation under much stronger hypotheses. We apply these results to natural hierarchies. First, we look at several language theoretic hierarchies that are built by applying LPol, RPol and MPol recursively to a single input class. We prove that these hierarchies can actually be defined using almost exclusively MPol. We also consider quantifier alternation hierarchies for two-variable first-order logic and prove that one can climb them using MPol. The result is generic in the sense that it holds for most standard choices of signatures. We use it to prove that for most of these choices, membership is decidable for all levels in the hierarchy. Finally, we prove that separation is decidable for the hierarchy of two-variable first-order logic equipped with only the linear order.
Topological Authentication Technique In Topologically Asymmetric Cryptosystem
Venue: arXiv cs.CR 2022
Year: 2022

Making topological authentication from theory to practical application is an important and challenging task. More and more researchers pay attention on coming quantum computation, privacy data protection, lattices and cryptography. Research show the advantages of topological authentications through graph operations, various matrices, graph colorings and graph labelings are: related with two or more different mathematical areas, be not pictures, there are huge number of colorings and labelings, rooted on modern mathematics, diversity of asymmetric ciphers, simplicity and convenience, easily created, irreversibility, computational security, provable security, and so on. Topological authentications based on various graph homomorphisms, degree-sequence homomorphisms, graph-set homomorphisms. Randomly topological coding and topological authentications are based on Hanzi authentication, randomly adding-edge-removing operation, randomly leaf-adding algorithms, graph random increasing techniques, operation graphic lattice and dynamic networked models and their spanning trees and maximum leaf spanning trees. Realization of topological authentication is an important topic, we study: number-based strings generated from colored graphs, particular graphs (complete graphs, trees, planar graphs), some methods of generating public-keys. some techniques of topologically asymmetric cryptosystem are: W-type matching labelings, dual-type labelings, reciprocal-type labelings, topological homomorphisms, indexed colorings, graphic lattices, degree-sequence lattices, every-zero Cds-matrix groups of degree-sequences, every-zero graphic groups, graphic lattices having coloring closure property, self-similar networked lattices.
Spotting Anomalous Trades in NFT Markets: The Case of NBA Topshot
Venue: arXiv cs.SI 2022
Year: 2022

Non-Fungible Token (NFT) markets are one of the fastest growing digital markets today, with the sales during the third quarter of 2021 exceeding $10 billions! Nevertheless, these emerging markets - similar to traditional emerging marketplaces - can be seen as a great opportunity for illegal activities (e.g., money laundering, sale of illegal goods etc.). In this study we focus on a specific marketplace, namely NBA TopShot, that facilitates the purchase and (peer-to-peer) trading of sports collectibles. Our objective is to build a framework that is able to label peer-to-peer transactions on the platform as anomalous or not. To achieve our objective we begin by building a model for the profit to be made by selling a specific collectible on the platform. We then use RFCDE - a random forest model for the conditional density of the dependent variable - to model the errors from the profit models. This step allows us to estimate the probability of a transaction being anomalous. We finally label as anomalous any transaction whose aforementioned probability is less than 1%. Given the absence of ground truth for evaluating the model in terms of its classification of transactions, we analyze the trade networks formed from these anomalous transactions and compare it with the full trade network of the platform. Our results indicate that these two networks are statistically different when it comes to network metrics such as, edge density, closure, node centrality and node degree distribution. This network analysis provides additional evidence that these transactions do not follow the same patterns that the rest of the trades on the platform follow. However, we would like to emphasize here that this does not mean that these transactions are also illegal. These transactions will need to be further audited from the appropriate entities to verify whether or not they are illicit.
NEWSKVQA: Knowledge-Aware News Video Question Answering
Venue: arXiv cs.CV 2022
Year: 2022

Answering questions in the context of videos can be helpful in video indexing, video retrieval systems, video summarization, learning management systems and surveillance video analysis. Although there exists a large body of work on visual question answering, work on video question answering (1) is limited to domains like movies, TV shows, gameplay, or human activity, and (2) is mostly based on common sense reasoning. In this paper, we explore a new frontier in video question answering: answering knowledge-based questions in the context of news videos. To this end, we curate a new dataset of 12K news videos spanning across 156 hours with 1M multiple-choice question-answer pairs covering 8263 unique entities. We make the dataset publicly available. Using this dataset, we propose a novel approach, NEWSKVQA (Knowledge-Aware News Video Question Answering) which performs multi-modal inferencing over textual multiple-choice questions, videos, their transcripts and knowledge base, and presents a strong baseline.
Ontology-based Attack Graph Enrichment
Venue: arXiv cs.CR 2022
Year: 2022

Attack graphs provide a representation of possible actions that adversaries can perpetrate to attack a system. They are used by cybersecurity experts to make decisions, e.g., to decide remediation and recovery plans. Different approaches can be used to build such graphs. We focus on logical attack graphs, based on predicate logic, to define the causality of adversarial actions. Since networks and vulnerabilities are constantly changing (e.g., new applications get installed on system devices, updated services get publicly exposed, etc.), we propose to enrich the attack graph generation approach with a semantic augmentation post-processing of the predicates. Graphs are now mapped to monitoring alerts confirming successful attack actions and updated according to network and vulnerability changes. As a result, predicates get periodically updated, based on attack evidences and ontology enrichment. This allows to verify whether changes lead the attacker to the initial goals or to cause further damage to the system not anticipated in the initial graphs. We illustrate the approach under the specific domain of cyber-physical security affecting smart cities. We validate the approach using existing tools and ontologies.
Integrating question answering and text-to-SQL in Portuguese
Venue: arXiv cs.CL 2022
Year: 2022

Deep learning transformers have drastically improved systems that automatically answer questions in natural language. However, different questions demand different answering techniques; here we propose, build and validate an architecture that integrates different modules to answer two distinct kinds of queries. Our architecture takes a free-form natural language text and classifies it to send it either to a Neural Question Answering Reasoner or a Natural Language parser to SQL. We implemented a complete system for the Portuguese language, using some of the main tools available for the language and translating training and testing datasets. Experiments show that our system selects the appropriate answering method with high accuracy (over 99\%), thus validating a modular question answering strategy.
Towards automated Capability Assessment leveraging Deep Learning
Venue: arXiv cs.GR 2022
Year: 2022

Aiming for a higher economic efficiency in manufacturing, an increased degree of automation is a key enabler. However, assessing the technical feasibility of an automated assembly solution for a dedicated process is difficult and often determined by the geometry of the given product parts. Among others, decisive criterions of the automation feasibility are the ability to separate and isolate single parts or the capability of component self-alignment in final position. To assess the feasibility, a questionnaire based evaluation scheme has been developed and applied by Fraunhofer researchers. However, the results strongly depend on the implicit knowledge and experience of the single engineer performing the assessment. This paper presents NeuroCAD, a software tool that automates the assessment using voxelization techniques. The approach enables the assessment of abstract and production relevant geometries features through deep-learning based on CAD files.
Disentangle Saliency Detection into Cascaded Detail Modeling and Body Filling
Venue: arXiv cs.CV 2022
Year: 2022

Salient object detection has been long studied to identify the most visually attractive objects in images/videos. Recently, a growing amount of approaches have been proposed all of which rely on the contour/edge information to improve detection performance. The edge labels are either put into the loss directly or used as extra supervision. The edge and body can also be learned separately and then fused afterward. Both methods either lead to high prediction errors near the edge or cannot be trained in an end-to-end manner. Another problem is that existing methods may fail to detect objects of various sizes due to the lack of efficient and effective feature fusion mechanisms. In this work, we propose to decompose the saliency detection task into two cascaded sub-tasks, \emph{i.e.}, detail modeling and body filling. Specifically, the detail modeling focuses on capturing the object edges by supervision of explicitly decomposed detail label that consists of the pixels that are nested on the edge and near the edge. Then the body filling learns the body part which will be filled into the detail map to generate more accurate saliency map. To effectively fuse the features and handle objects at different scales, we have also proposed two novel multi-scale detail attention and body attention blocks for precise detail and body modeling. Experimental results show that our method achieves state-of-the-art performances on six public datasets.
Physical Zero-knowledge Proofs for Flow Free, Hamiltonian Cycles, and Many-to-many k-disjoint Covering Paths
Venue: arXiv cs.CR 2022
Year: 2022

In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.
A Novel Ontology-guided Attribute Partitioning Ensemble Learning Model for Early Prediction of Cognitive Deficits using Quantitative Structural MRI in Very Preterm Infants
Venue: arXiv cs.LG 2022
Year: 2022

Structural magnetic resonance imaging studies have shown that brain anatomical abnormalities are associated with cognitive deficits in preterm infants. Brain maturation and geometric features can be used with machine learning models for predicting later neurodevelopmental deficits. However, traditional machine learning models would suffer from a large feature-to-instance ratio (i.e., a large number of features but a small number of instances/samples). Ensemble learning is a paradigm that strategically generates and integrates a library of machine learning classifiers and has been successfully used on a wide variety of predictive modeling problems to boost model performance. Attribute (i.e., feature) bagging method is the most commonly used feature partitioning scheme, which randomly and repeatedly draws feature subsets from the entire feature set. Although attribute bagging method can effectively reduce feature dimensionality to handle the large feature-to-instance ratio, it lacks consideration of domain knowledge and latent relationship among features. In this study, we proposed a novel Ontology-guided Attribute Partitioning (OAP) method to better draw feature subsets by considering the domain-specific relationship among features. With the better partitioned feature subsets, we developed an ensemble learning framework, which is referred to as OAP-Ensemble Learning (OAP-EL). We applied the OAP-EL to predict cognitive deficits at 2 years of age using quantitative brain maturation and geometric features obtained at term equivalent age in very preterm infants. We demonstrated that the proposed OAP-EL approach significantly outperformed the peer ensemble learning and traditional machine learning approaches.
The Rate-Distortion-Perception Tradeoff: The Role of Common Randomness
Venue: arXiv cs.IT 2022
Year: 2022

A rate-distortion-perception (RDP) tradeoff has recently been proposed by Blau and Michaeli and also Matsumoto. Focusing on the case of perfect realism, which coincides with the problem of distribution-preserving lossy compression studied by Li et al., a coding theorem for the RDP tradeoff that allows for a specified amount of common randomness between the encoder and decoder is provided. The existing RDP tradeoff is recovered by allowing for the amount of common randomness to be infinite. The quadratic Gaussian case is examined in detail.
Source Matching and Rewriting
Venue: arXiv cs.PL 2022
Year: 2022

A typical compiler flow relies on a uni-directional sequence of translation/optimization steps that lower the program abstract representation, making it hard to preserve higher-level program information across each transformation step. On the other hand, modern ISA extensions and hardware accelerators can benefit from the compiler's ability to detect and raise program idioms to acceleration instructions or optimized library calls. Although recent works based on Multi-Level IR (MLIR) have been proposed for code raising, they rely on specialized languages, compiler recompilation, or in-depth dialect knowledge. This paper presents Source Matching and Rewriting (SMR), a user-oriented source-code-based approach for MLIR idiom matching and rewriting that does not require a compiler expert's intervention. SMR uses a two-phase automaton-based DAG-matching algorithm inspired by early work on tree-pattern matching. First, the idiom Control-Dependency Graph (CDG) is matched against the program's CDG to rule out code fragments that do not have a control-flow structure similar to the desired idiom. Second, candidate code fragments from the previous phase have their Data-Dependency Graphs (DDGs) constructed and matched against the idiom DDG. Experimental results show that SMR can effectively match idioms from Fortran (FIR) and C (CIL) programs while raising them as BLAS calls to improve performance.