OpenRaiser/Intern-Atlas huggingface dataset:
Inferring Substitutable and Complementary Products with Knowledge-Aware Path Reasoning based on Dynamic Policy Network
Venue: arXiv cs.AI 2021
Year: 2021

Inferring the substitutable and complementary products for a given product is an essential and fundamental concern for the recommender system. To achieve this, existing approaches take advantage of the knowledge graphs to learn more evidences for inference, whereas they often suffer from invalid reasoning for lack of elegant decision making strategies. Therefore, we propose a novel Knowledge-Aware Path Reasoning (KAPR) model which leverages the dynamic policy network to make explicit reasoning over knowledge graphs, for inferring the substitutable and complementary relationships. Our contributions can be highlighted as three aspects. Firstly, we model this inference scenario as a Markov Decision Process in order to accomplish a knowledge-aware path reasoning over knowledge graphs. Secondly,we integrate both structured and unstructured knowledge to provide adequate evidences for making accurate decision-making. Thirdly, we evaluate our model on a series of real-world datasets, achieving competitive performance compared with state-of-the-art approaches. Our code is released on https://gitee.com/yangzijing flower/kapr/tree/master.
Polynomial Turing Kernels for Clique with an Optimal Number of Queries
Venue: arXiv cs.CC 2021
Year: 2021

A polynomial Turing kernel for some parameterized problem $P$ is a polynomial-time algorithm that solves $P$ using queries to an oracle of $P$ whose sizes are upper-bounded by some polynomial in the parameter. Here the term "polynomial" refers to the bound on the query sizes, as the running time of any kernel is required to be polynomial. One of the most important open goals in parameterized complexity is to understand the applicability and limitations of polynomial Turing Kernels. As any fixed-parameter tractable problem admits a Turing kernel of some size, the focus has mostly being on determining which problems admit such kernels whose query sizes can be indeed bounded by some polynomial. In this paper we take a different approach, and instead focus on the number of queries that a Turing kernel uses, assuming it is restricted to using only polynomial sized queries. Our study focuses on one the main problems studied in parameterized complexity, the Clique problem: Given a graph $G$ and an integer $k$, determine whether there are $k$ pairwise adjacent vertices in $G$. We show that Clique parameterized by several structural parameters exhibits the following phenomena: - It admits polynomial Turing kernels which use a sublinear number of queries, namely $O(n/\log^c n)$ queries where $n$ is the total size of the graph and $c$ is any constant. This holds even for a very restrictive type of Turing kernels which we call OR-kernels. - It does not admit polynomial Turing kernels which use $O(n^{1-ε})$ queries, unless NP$\subseteq$coNP/poly. For proving the second item above, we develop a new framework for bounding the number of queries needed by polynomial Turing kernels. This framework is inspired by the standard lower bounds framework for Karp kernels, and while it is quite similar, it still requires some novel ideas to allow its extension to the Turing setting.
The Connection between Out-of-Distribution Generalization and Privacy of ML Models
Venue: arXiv cs.LG 2021
Year: 2021

With the goal of generalizing to out-of-distribution (OOD) data, recent domain generalization methods aim to learn "stable" feature representations whose effect on the output remains invariant across domains. Given the theoretical connection between generalization and privacy, we ask whether better OOD generalization leads to better privacy for machine learning models, where privacy is measured through robustness to membership inference (MI) attacks. In general, we find that the relationship does not hold. Through extensive evaluation on a synthetic dataset and image datasets like MNIST, Fashion-MNIST, and Chest X-rays, we show that a lower OOD generalization gap does not imply better robustness to MI attacks. Instead, privacy benefits are based on the extent to which a model captures the stable features. A model that captures stable features is more robust to MI attacks than models that exhibit better OOD generalization but do not learn stable features. Further, for the same provable differential privacy guarantees, a model that learns stable features provides higher utility as compared to others. Our results offer the first extensive empirical study connecting stable features and privacy, and also have a takeaway for the domain generalization community; MI attack can be used as a complementary metric to measure model quality.
Human in the Loop for Machine Creativity
Venue: arXiv cs.HC 2021
Year: 2021

Artificial intelligence (AI) is increasingly utilized in synthesizing visuals, texts, and audio. These AI-based works, often derived from neural networks, are entering the mainstream market, as digital paintings, songs, books, and others. We conceptualize both existing and future human-in-the-loop (HITL) approaches for creative applications and to develop more expressive, nuanced, and multimodal models. Particularly, how can our expertise as curators and collaborators be encoded in AI models in an interactive manner? We examine and speculate on long term implications for models, interfaces, and machine creativity. Our selection, creation, and interpretation of AI art inherently contain our emotional responses, cultures, and contexts. Therefore, the proposed HITL may help algorithms to learn creative processes that are much harder to codify or quantify. We envision multimodal HITL processes, where texts, visuals, sounds, and other information are coupled together, with automated analysis of humans and environments. Overall, these HITL approaches will increase interaction between human and AI, and thus help the future AI systems to better understand our own creative and emotional processes.
Enabling On-Device Training of Speech Recognition Models with Federated Dropout
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning can be used to train machine learning models on the edge on local data that never leave devices, providing privacy by default. This presents a challenge pertaining to the communication and computation costs associated with clients' devices. These costs are strongly correlated with the size of the model being trained, and are significant for state-of-the-art automatic speech recognition models. We propose using federated dropout to reduce the size of client models while training a full-size model server-side. We provide empirical evidence of the effectiveness of federated dropout, and propose a novel approach to vary the dropout rate applied at each layer. Furthermore, we find that federated dropout enables a set of smaller sub-models within the larger model to independently have low word error rates, making it easier to dynamically adjust the size of the model deployed for inference.
From Weighted Conditionals of Multilayer Perceptrons to Gradual Argumentation and Back
Venue: arXiv cs.AI 2021
Year: 2021

A fuzzy multipreference semantics has been recently proposed for weighted conditional knowledge bases, and used to develop a logical semantics for Multilayer Perceptrons, by regarding a deep neural network (after training) as a weighted conditional knowledge base. This semantics, in its different variants, suggests some gradual argumentation semantics, which are related to the family of the gradual semantics studied by Amgoud and Doder. The relationships between weighted conditional knowledge bases and MLPs extend to the proposed gradual semantics to capture the stationary states of MPs, in agreement with previous results on the relationship between argumentation frameworks and neural networks. The paper also suggests a simple way to extend the proposed semantics to deal attacks/supports by a boolean combination of arguments, based on the fuzzy semantics of weighted conditionals, as well as an approach for defeasible reasoning over a weighted argumentation graph, building on the proposed gradual semantics.
Bisimulations for Neural Network Reduction
Venue: arXiv cs.LG 2021
Year: 2021

We present a notion of bisimulation that induces a reduced network which is semantically equivalent to the given neural network. We provide a minimization algorithm to construct the smallest bisimulation equivalent network. Reductions that construct bisimulation equivalent neural networks are limited in the scale of reduction. We present an approximate notion of bisimulation that provides semantic closeness, rather than, semantic equivalence, and quantify semantic deviation between the neural networks that are approximately bisimilar. The latter provides a trade-off between the amount of reduction and deviations in the semantics.
Explanation as a process: user-centric construction of multi-level and multi-modal explanations
Venue: arXiv cs.AI 2021
Year: 2021

In the last years, XAI research has mainly been concerned with developing new technical approaches to explain deep learning models. Just recent research has started to acknowledge the need to tailor explanations to different contexts and requirements of stakeholders. Explanations must not only suit developers of models, but also domain experts as well as end users. Thus, in order to satisfy different stakeholders, explanation methods need to be combined. While multi-modal explanations have been used to make model predictions more transparent, less research has focused on treating explanation as a process, where users can ask for information according to the level of understanding gained at a certain point in time. Consequently, an opportunity to explore explanations on different levels of abstraction should be provided besides multi-modal explanations. We present a process-based approach that combines multi-level and multi-modal explanations. The user can ask for textual explanations or visualizations through conversational interaction in a drill-down manner. We use Inductive Logic Programming, an interpretable machine learning approach, to learn a comprehensible model. Further, we present an algorithm that creates an explanatory tree for each example for which a classifier decision is to be explained. The explanatory tree can be navigated by the user to get answers of different levels of detail. We provide a proof-of-concept implementation for concepts induced from a semantic net about living beings.
A simple equivariant machine learning method for dynamics based on scalars
Venue: arXiv cs.LG 2021
Year: 2021

Physical systems obey strict symmetry principles. We expect that machine learning methods that intrinsically respect these symmetries should have higher prediction accuracy and better generalization in prediction of physical dynamics. In this work we implement a principled model based on invariant scalars, and release open-source code. We apply this Scalars method to a simple chaotic dynamical system, the springy double pendulum. We show that the Scalars method outperforms state-of-the-art approaches for learning the properties of physical systems with symmetries, both in terms of accuracy and speed. Because the method incorporates the fundamental symmetries, we expect it to generalize to different settings, such as changes in the force laws in the system.
MPD: Moving Target Defense through Communication Protocol Dialects
Venue: arXiv cs.CR 2021
Year: 2021

Communication protocol security is among the most significant challenges of the Internet of Things (IoT) due to the wide variety of hardware and software technologies involved. Moving target defense (MTD) has been adopted as an innovative strategy to solve this problem by dynamically changing target system properties and configurations to obfuscate the attack surface. Nevertheless, the existing work of MTD primarily focuses on lower-level properties (e.g., IP addresses or port numbers), and only a limited number of variations can be generated based on these properties. In this paper, we propose a new approach of MTD through communication protocol dialects (MPD) - which dynamically customizes a communication protocol into various protocol dialects and leverages them to create a moving target defense. Specifically, MPD harnesses a dialect generating function to create protocol dialects and then a mapping function to select one specific dialect for each packet during communication. To keep different network entities in synchronization, we also design a self-synchronization mechanism utilizing a pseudo-random number generator with the input of a pre-shared secret key and previously sent packets. We implement a prototype of MPD and evaluate its feasibility on standard network protocol (i.e., File Transfer Protocol) and internet of things protocol (i.e., Message Queuing Telemetry Transport). The results indicate that MPD can create a moving target defense with protocol dialects to effectively address various attacks - including the denial of service attack and malicious packet modifications - with negligible overhead.
AS-Level BGP Community Usage Classification
Venue: arXiv cs.NI 2021
Year: 2021

BGP communities are a popular mechanism used by network operators for traffic engineering, blackholing, and to realize network policies and business strategies. In recent years, many research works have contributed to our understanding of how BGP communities are utilized, as well as how they can reveal secondary insights into real-world events such as outages and security attacks. However, one fundamental question remains unanswered: "Which ASes tag announcements with BGP communities and which remove communities in the announcements they receive?" A grounded understanding of where BGP communities are added or removed can help better model and predict BGP-based actions in the Internet and characterize the strategies of network operators. In this paper we develop, validate, and share data from the first algorithm that can infer BGP community tagging and cleaning behavior at the AS-level. The algorithm is entirely passive and uses BGP update messages and snapshots, e.g. from public route collectors, as input. First, we quantify the correctness and accuracy of the algorithm in controlled experiments with simulated topologies. To validate in the wild, we announce prefixes with communities and confirm that more than 90% of the ASes that we classify behave as our algorithm predicts. Finally, we apply the algorithm to data from four sets of BGP collectors: RIPE, RouteViews, Isolario, and PCH. Tuned conservatively, our algorithm ascribes community tagging and cleaning behaviors to more than 13k ASes, the majority of which are large networks and providers. We make our algorithm and inferences available as a public resource to the BGP research community.
How Tertiary Studies perform Quality Assessment of Secondary Studies in Software Engineering
Venue: arXiv cs.SE 2021
Year: 2021

Context: Tertiary studies are becoming increasingly popular in software engineering as an instrument to synthesise evidence on a research topic in a systematic way. In order to understand and contextualize their findings, it is important to assess the quality of the selected secondary studies. Objective: This paper aims to provide a state of the art on the assessment of secondary studies' quality as conducted in tertiary studies in the area of software engineering, reporting the frameworks used as instruments, the facets examined in these frameworks, and the purposes of the quality assessment. Method: We designed this study as a systematic mapping responding to four research questions derived from the objective above. We applied a rigorous search protocol over the Scopus digital library, resulting in 47 papers after application of inclusion and exclusion criteria. The extracted data was synthesised using content analysis. Results: A majority of tertiary studies perform quality assessment. It is not often used for excluding studies, but to support some kind of investigation. The DARE quality assessment framework is the most frequently used, with customizations in some cases to cover missing facets. We outline the first steps towards building a new framework to address the shortcomings identified. Conclusion: This paper is a step forward establishing a foundation for researchers in two different ways. As authors of tertiary studies, understanding the different possibilities in which they can perform quality assessment of secondary studies. As readers, having an instrument to understand the methodological rigor upon which tertiary studies may claim their findings.
Stable Prediction on Graphs with Agnostic Distribution Shift
Venue: arXiv cs.LG 2021
Year: 2021

Graph is a flexible and effective tool to represent complex structures in practice and graph neural networks (GNNs) have been shown to be effective on various graph tasks with randomly separated training and testing data. In real applications, however, the distribution of training graph might be different from that of the test one (e.g., users' interactions on the user-item training graph and their actual preference on items, i.e., testing environment, are known to have inconsistencies in recommender systems). Moreover, the distribution of test data is always agnostic when GNNs are trained. Hence, we are facing the agnostic distribution shift between training and testing on graph learning, which would lead to unstable inference of traditional GNNs across different test environments. To address this problem, we propose a novel stable prediction framework for GNNs, which permits both locally and globally stable learning and prediction on graphs. In particular, since each node is partially represented by its neighbors in GNNs, we propose to capture the stable properties for each node (locally stable) by re-weighting the information propagation/aggregation processes. For global stability, we propose a stable regularizer that reduces the training losses on heterogeneous environments and thus warping the GNNs to generalize well. We conduct extensive experiments on several graph benchmarks and a noisy industrial recommendation dataset that is collected from 5 consecutive days during a product promotion festival. The results demonstrate that our method outperforms various SOTA GNNs for stable prediction on graphs with agnostic distribution shift, including shift caused by node labels and attributes.
The similarity index of mathematical and other scientific publications with equations and formulas and the problem of self-plagiarism identification
Venue: arXiv cs.DL 2021
Year: 2021

The problems of estimating the similarity index of inhomogeneous scientific publications containing equations and formulas are discussed for the first time. It is shown that the presence of equations and formulas (as well as figures, drawings, and tables) is a complicating factor that significantly complicates the study of such texts. It has been proved that the method for determining the similarity index of publications, based on taking into account individual mathematical symbols and parts of equations and formulas, is ineffective and can lead to erroneous and even completely absurd conclusions. Possibilities of the most popular software systems Antiplagiat and iThenticate, currently used in scientific journals, are investigated for detecting plagiarism and self-plagiarism. The results of processing by the iThenticate system of specific examples and specific test problems containing equations and formulas are presented. It has been established that this software system, when analyzing heterogeneous texts, is often unable to distinguish self-plagiarism from pseudo-self-plagiarism, seeming real (but false and imaginary) self-plagiarism. A model complex situation is considered, in which the identification of self-plagiarism requires the involvement of highly qualified specialists of a narrow profile. Various ways to improve the work of software systems for comparing inhomogeneous texts are proposed. This article will be useful to researchers and university teachers in physics, mathematics, and engineering, programmers dealing with problems in image recognition and research topics of digital image processing, as well as a wide range of readers who are interested in issues of plagiarism and self-plagiarism.
ModeRNN: Harnessing Spatiotemporal Mode Collapse in Unsupervised Predictive Learning
Venue: arXiv cs.LG 2021
Year: 2021

Learning predictive models for unlabeled spatiotemporal data is challenging in part because visual dynamics can be highly entangled in real scenes, making existing approaches prone to overfit partial modes of physical processes while neglecting to reason about others. We name this phenomenon spatiotemporal mode collapse and explore it for the first time in predictive learning. The key is to provide the model with a strong inductive bias to discover the compositional structures of latent modes. To this end, we propose ModeRNN, which introduces a novel method to learn structured hidden representations between recurrent states. The core idea of this framework is to first extract various components of visual dynamics using a set of spatiotemporal slots with independent parameters. Considering that multiple space-time patterns may co-exist in a sequence, we leverage learnable importance weights to adaptively aggregate slot features into a unified hidden representation, which is then used to update the recurrent states. Across the entire dataset, different modes result in different responses on the mixtures of slots, which enhances the ability of ModeRNN to build structured representations and thus prevents the so-called mode collapse. Unlike existing models, ModeRNN is shown to prevent spatiotemporal mode collapse and further benefit from learning mixed visual dynamics.
Proposal of Analog In-Memory Computing with Magnified Tunnel Magnetoresistance Ratio and Universal STT-MRAM Cell
Venue: arXiv cs.ET 2021
Year: 2021

In-memory computing (IMC) is an effectual solution for energy-efficient artificial intelligence applications. Analog IMC amortizes the power consumption of multiple sensing amplifiers with analog-to-digital converter (ADC), and simultaneously completes the calculation of multi-line data with high parallelism degree. Based on a universal one-transistor one-magnetic tunnel junction (MTJ) spin transfer torque magnetic RAM (STT-MRAM) cell, this paper demonstrates a novel tunneling magnetoresistance (TMR) ratio magnifying method to realize analog IMC. Previous concerns include low TMR ratio and analog calculation nonlinearity are addressed using device-circuit interaction. Peripheral circuits are minimally modified to enable in-memory matrix-vector multiplication. A current mirror with feedback structure is implemented to enhance analog computing linearity and calculation accuracy. The proposed design maximumly supports 1024 2-bit input and 1-bit weight multiply-and-accumulate (MAC) computations simultaneously. The 2-bit input is represented by the width of the input (IN) pulses, while the 1-bit weight is stored in STT-MRAM and the x7500 magnified TMR (m-TMR) ratio is obtained by latching. The proposal is simulated using 28-nm CMOS process and MTJ compact model. The integral nonlinearity is reduced by 57.6% compared with the conventional structure. 9.47-25.4 TOPS/W is realized with 2-bit input, 1-bit weight and 4-bit output convolution neural network (CNN).