bluuebunny/crossref_metadata_2025 huggingface dataset:
Discovering Collaborative Signals for Next POI Recommendation with Iterative Seq2Graph Augmentation
Authors: Li Yang , Chen Tong , Luo Yadan , Yin Hongzhi , Huang Zi
Published: August 2021

Being an indispensable component in location-based social networks, next point-of-interest (POI) recommendation recommends users unexplored POIs based on their recent visiting histories. However, existing work mainly models check-in data as isolated POI sequences, neglecting the crucial collaborative signals from cross-sequence check-in information. Furthermore, the sparse POI-POI transitions restrict the ability of a model to learn effective sequential patterns for recommendation. In this paper, we propose Sequence-to-Graph (Seq2Graph) augmentation for each POI sequence, allowing collaborative signals to be propagated from correlated POIs belonging to other sequences. We then devise a novel Sequence-to-Graph POI Recommender (SGRec), which jointly learns POI embeddings and infers a user's temporal preferences from the graph-augmented POI sequence. To overcome the sparsity of POI-level interactions, we further infuse category-awareness into SGRec with a multi-task learning scheme that captures the denser category-wise transitions. As such, SGRec makes full use of the collaborative signals for learning expressive POI representations, and also comprehensively uncovers multi-level sequential patterns for user preference modelling. Extensive experiments on two real-world datasets demonstrate the superiority of SGRec against state-of-the-art methods in next POI recommendation.
Neural Regret-Matching for Distributed Constraint Optimization Problems
Authors: Deng Yanchen , Yu Runsheng , Wang Xinrun , An Bo
Published: August 2021

Distributed constraint optimization problems (DCOPs) are a powerful model for multi-agent coordination and optimization, where information and controls are distributed among multiple agents by nature. Sampling-based algorithms are important incomplete techniques for solving medium-scale DCOPs. However, they use tables to exactly store all the information (e.g., costs, confidence bounds) to facilitate sampling, which limits their scalability. This paper tackles the limitation by incorporating deep neural networks in solving DCOPs for the first time and presents a neural-based sampling scheme built upon regret-matching. In the algorithm, each agent trains a neural network to approximate the regret related to its local problem and performs sampling according to the estimated regret. Furthermore, to ensure exploration we propose a regret rounding scheme that rounds small regret values to positive numbers. We theoretically show the regret bound of our algorithm and extensive evaluations indicate that our algorithm can scale up to large-scale DCOPs and significantly outperform the state-of-the-art methods.
Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
Authors: Shi Yunsheng , Huang Zhengjie , Feng Shikun , Zhong Hui , Wang Wenjing , Sun Yu
Published: August 2021

Graph neural network (GNN) and label propagation algorithm (LPA) are both message passing algorithms, which have achieved superior performance in semi-supervised classification. GNN performs feature propagation by a neural network to make predictions, while LPA uses label propagation across graph adjacency matrix to get results. However, there is still no effective way to directly combine these two kinds of algorithms. To address this issue, we propose a novel Unified Message Passaging Model (UniMP) that can incorporate feature and label propagation at both training and inference time. First, UniMP adopts a Graph Transformer network, taking feature embedding and label embedding as input information for propagation. Second, to train the network without overfitting in self-loop input label information, UniMP introduces a masked label prediction strategy, in which some percentage of input label information are masked at random, and then predicted. UniMP conceptually unifies feature propagation and label propagation and is empirically powerful. It obtains new state-of-the-art semi-supervised classification results in Open Graph Benchmark (OGB).
Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees
Authors: Shi Yuxuan , Cheng Gong , Tran Trung-Kien , Tang Jie , Kharlamov Evgeny
Published: August 2021

Exploring complex structured knowledge graphs (KGs) is challenging for non-experts as it requires knowledge of query languages and the underlying structure of the KGs. Keyword-based exploration is a convenient paradigm, and computing a group Steiner tree (GST) as an answer is a popular implementation. Recent studies suggested improving the cohesiveness of an answer where entities have small semantic distances from each other. However, how to efficiently compute such an answer is open. In this paper, to model cohesiveness in a generalized way, the quadratic group Steiner tree problem (QGSTP) is formulated where the cost function extends GST with quadratic terms representing semantic distances. For QGSTP we design a branch-and-bound best-first (B3F) algorithm where we exploit combinatorial methods to estimate lower bounds for costs. This exact algorithm shows practical performance on medium-sized KGs.
Cooperative Joint Attentive Network for Patient Outcome Prediction on Irregular Multi-Rate Multivariate Health Data
Authors: Tan Qingxiong , Ye Mang , Wong Grace Lai-Hung , Yuen PongChi
Published: August 2021

Due to the dynamic health status of patients and discrepant stability of physiological variables, health data often presents as irregular multi-rate multivariate time series (IMR-MTS) with significantly varying sampling rates. Existing methods mainly study changes of IMR-MTS values in the time domain, without considering their different dominant frequencies and varying data quality. Hence, we propose a novel Cooperative Joint Attentive Network (CJANet) to analyze IMR-MTS in frequency domain, which adaptively handling discrepant dominant frequencies while tackling diverse data qualities caused by irregular sampling. In particular, novel dual-channel joint attention is designed to jointly identify important magnitude and phase signals while detecting their dominant frequencies, automatically enlarging the positive influence of key variables and frequencies. Furthermore, a new cooperative learning module is introduced to enhance information exchange between magnitude and phase channels, effectively integrating global signals to optimize the network. A frequency-aware fusion strategy is finally designed to aggregate the learned features. Extensive experimental results on real-world medical datasets indicate that CJANet significantly outperforms existing methods and provides highly interpretable results.
Preference-Adaptive Meta-Learning for Cold-Start Recommendation
Authors: Wang Li , Jin Binbin , Huang Zhenya , Zhao Hongke , Lian Defu , Liu Qi , Chen Enhong
Published: August 2021

In recommender systems, the cold-start problem is a critical issue. To alleviate this problem, an emerging direction adopts meta-learning frameworks and achieves success. Most existing works aim to learn globally shared prior knowledge across all users so that it can be quickly adapted to a new user with sparse interactions. However, globally shared prior knowledge may be inadequate to discern users’ complicated behaviors and causes poor generalization. Therefore, we argue that prior knowledge should be locally shared by users with similar preferences who can be recognized by social relations. To this end, in this paper, we propose a Preference-Adaptive Meta-Learning approach (PAML) to improve existing meta-learning frameworks with better generalization capacity. Specifically, to address two challenges imposed by social relations, we first identify reliable implicit friends to strengthen a user’s social relations based on our defined palindrome paths. Then, a coarse-fine preference modeling method is proposed to leverage social relations and capture the preference. Afterwards, a novel preference-specific adapter is designed to adapt the globally shared prior knowledge to the preference-specific knowledge so that users who have similar tastes share similar knowledge. We conduct extensive experiments on two publicly available datasets. Experimental results validate the power of social relations and the effectiveness of PAML.
Federated Learning with Fair Averaging
Authors: Wang Zheng , Fan Xiaoliang , Qi Jianzhong , Wen Chenglu , Wang Cheng , Yu Rongshan
Published: August 2021

Fairness has emerged as a critical problem in federated learning (FL). In this work, we identify a cause of unfairness in FL -- conflicting gradients with large differences in the magnitudes. To address this issue, we propose the federated fair averaging (FedFV) algorithm to mitigate potential conflicts among clients before averaging their gradients. We first use the cosine similarity to detect gradient conflicts, and then iteratively eliminate such conflicts by modifying both the direction and the magnitude of the gradients. We further show the theoretical foundation of FedFV to mitigate the issue conflicting gradients and converge to Pareto stationary solutions. Extensive experiments on a suite of federated datasets confirm that FedFV compares favorably against state-of-the-art methods in terms of fairness, accuracy and efficiency. The source code is available at https://github.com/WwZzz/easyFL.
Spatial-Temporal Sequential Hypergraph Network for Crime Prediction with Dynamic Multiplex Relation Learning
Authors: Xia Lianghao , Huang Chao , Xu Yong , Dai Peng , Bo Liefeng , Zhang Xiyue , Chen Tianyi
Published: August 2021

Crime prediction is crucial for public safety and resource optimization, yet is very challenging due to two aspects: i) the dynamics of criminal patterns across time and space, crime events are distributed unevenly on both spatial and temporal domains; ii) time-evolving dependencies between different types of crimes (e.g., Theft, Robbery, Assault, Damage) which reveal fine-grained semantics of crimes. To tackle these challenges, we propose Spatial-Temporal Sequential Hypergraph Network (ST-SHN) to collectively encode complex crime spatial-temporal patterns as well as the underlying category-wise crime semantic relationships. In specific, to handle spatial-temporal dynamics under the long-range and global context, we design a graph-structured message passing architecture with the integration of the hypergraph learning paradigm. To capture category-wise crime heterogeneous relations in a dynamic environment, we introduce a multi-channel routing mechanism to learn the time-evolving structural dependency across crime types. We conduct extensive experiments on two real-word datasets, showing that our proposed ST-SHN framework can significantly improve the prediction performance as compared to various state-of-the-art baselines. The source code is available at https://github.com/akaxlh/ST-SHN.
Choosing the Right Algorithm With Hints From Complexity Theory
Authors: Wang Shouda , Zheng Weijie , Doerr Benjamin
Published: August 2021

Choosing a suitable algorithm from the myriads of different search heuristics is difficult when faced with a novel optimization problem. In this work, we argue that the purely academic question of what could be the best possible algorithm in a certain broad class of black-box optimizers can give fruitful indications in which direction to search for good established optimization heuristics. We demonstrate this approach on the recently proposed DLB benchmark, for which the only known results are O(n^3) runtimes for several classic evolutionary algorithms and an O(n^2 log n) runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only O(n^2) suggests the Metropolis algorithm as an interesting candidate and we prove that it solves the DLB problem in quadratic time. Since we also prove that better runtimes cannot be obtained in the class of unary unbiased algorithms, we shift our attention to algorithms that use the information of more parents to generate new solutions. An artificial algorithm of this type having an O(n log n) runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time O(n log n). Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes.
Human-AI Collaboration with Bandit Feedback
Authors: Gao Ruijiang , Saar-Tsechansky Maytal , De-Arteaga Maria , Han Ligong , Lee Min Kyung , Lease Matthew
Published: August 2021

Human-machine complementarity is important when neither the algorithm nor the human yield dominant performance across all instances in a given domain. Most research on algorithmic decision-making solely centers on the algorithm's performance, while recent work that explores human-machine collaboration has framed the decision-making problems as classification tasks. In this paper, we first propose and then develop a solution for a novel human-machine collaboration problem in a bandit feedback setting. Our solution aims to exploit the human-machine complementarity to maximize decision rewards. We then extend our approach to settings with multiple human decision makers. We demonstrate the effectiveness of our proposed methods using both synthetic and real human responses, and find that our methods outperform both the algorithm and the human when they each make decisions on their own. We also show how personalized routing in the presence of multiple human decision-makers can further improve the human-machine team performance.
A Game-Theoretic Account of Responsibility Allocation
Authors: Baier Christel , Funke Florian , Majumdar Rupak
Published: August 2021

When designing or analyzing multi-agent systems, a fundamental problem is responsibility ascription: to specify which agents are responsible for the joint outcome of their behaviors and to which extent. We model strategic multi-agent interaction as an extensive form game of imperfect information and define notions of forward (prospective) and backward (retrospective) responsibility. Forward responsibility identifies the responsibility of a group of agents for an outcome along all possible plays, whereas backward responsibility identifies the responsibility along a given play. We further distinguish between strategic and causal backward responsibility, where the former captures the epistemic knowledge of players along a play, while the latter formalizes which players – possibly unknowingly – caused the outcome. A formal connection between forward and backward notions is established in the case of perfect recall. We further ascribe quantitative responsibility through cooperative game theory. We show through a number of examples that our approach encompasses several prior formal accounts of responsibility attribution.
Intensional and Extensional Views in DL-Lite Ontologies
Authors: Console Marco , De Giacomo Giuseppe , Lenzerini Maurizio , Namici Manuel
Published: August 2021

The use of virtual collections of data is often essential in several

data and knowledge management tasks. In the literature, the standard

way to define virtual data collections is via views, i.e., virtual

relations defined using queries. In data and knowledge bases, the

notion of views is a staple of data access, data integration and

exchange, query optimization, and data privacy. In this work, we

study views in Ontology-Based Data Access (OBDA) systems.

OBDA is a powerful paradigm for accessing data through an

ontology, i.e., a conceptual specification of the domain of interest

written using logical axioms. Intuitively, users of an OBDA system

interact with the data only through the ontology's conceptual lens. We

present a novel framework to express natural and sophisticated forms

of views in OBDA systems and introduce fundamental reasoning tasks for

these views. We study the computational complexity of these tasks and

present classes of views for which these tasks are tractable or at

least decidable.
Abductive Knowledge Induction from Raw Data
Authors: Dai Wang-Zhou , Muggleton Stephen
Published: August 2021

For many reasoning-heavy tasks with raw inputs, it is challenging to design an appropriate end-to-end pipeline to formulate the problem-solving process. Some modern AI systems, e.g., Neuro-Symbolic Learning, divide the pipeline into sub-symbolic perception and symbolic reasoning, trying to utilise data-driven machine learning and knowledge-driven problem-solving simultaneously. However, these systems suffer from the exponential computational complexity caused by the interface between the two components, where the sub-symbolic learning model lacks direct supervision, and the symbolic model lacks accurate input facts. Hence, they usually focus on learning the sub-symbolic model with a complete symbolic knowledge base while avoiding a crucial problem: where does the knowledge come from? In this paper, we present Abductive Meta-Interpretive Learning (MetaAbd) that unites abduction and induction to learn neural networks and logic theories jointly from raw data. Experimental results demonstrate that MetaAbd not only outperforms the compared systems in predictive accuracy and data efficiency but also induces logic programs that can be re-used as background knowledge in subsequent learning tasks. To the best of our knowledge, MetaAbd is the first system that can jointly learn neural networks from scratch and induce recursive first-order logic theories with predicate invention.
HyperLDLf: a Logic for Checking Properties of Finite Traces Process Logs
Authors: De Giacomo Giuseppe , Felli Paolo , Montali Marco , Perelli Giuseppe
Published: August 2021

Temporal logics over finite traces, such as LTLf and its extension LDLf, have been adopted in several areas, including Business Process Management (BPM), to check properties of processes whose executions have an unbounded, but finite, length. These logics express properties of single traces in isolation, however, especially in BPM it is also of interest to express properties over the entire log, i.e., properties that relate multiple traces of the log at once. In the case of infinite-traces, HyperLTL has been proposed to express these ``hyper'' properties. In this paper, motivated by BPM, we introduce HyperLDLf, a logic that extends LDLf with the hyper features of HyperLTL. We provide a sound, complete and computationally optimal technique, based on DFAs manipulation, for the model checking problem in the relevant case where the set of traces (i.e., the log) is a regular language. We illustrate how this form of model checking can be used for verifying log of business processes and for advanced forms of process mining.
Updating the Belief Promotion Operator
Authors: Grimaldi Daniel A. , Martinez M. Vanina , Rodriguez Ricardo O.
Published: August 2021

In this note, we introduce the local version of the operator for belief promotion proposed by Schwind et al. We propose a set of postulates and provide a representation theorem that characterizes the proposal. This family of operators is related to belief promotion in the same way that updating is related to revision, and we provide several results that allow us to show this relationship formally. Furthermore, we also show the relationship of the proposed operator with features of credibility-limited revision theory.
Using Platform Models for a Guided Explanatory Diagnosis Generation for Mobile Robots
Authors: Habering Daniel , Hofmann Till , Lakemeyer Gerhard
Published: August 2021

Plan execution on a mobile robot is inherently error-prone, as the robot

needs to act in a physical world which can never be completely

controlled by the robot. If an error occurs during execution, the true

world state is unknown, as a failure may have unobservable consequences.

One approach to deal with such failures is diagnosis, where the true

world state is determined by identifying a set of faults based on sensed

observations. In this paper, we present a novel approach to explanatory

diagnosis, based on the assumption that most failures occur due to some

robot hardware failure. We model the robot platform components with

state machines and formulate action variants for the robots' actions,

modelling different fault modes. We apply diagnosis as

planning with a top-k planning approach to determine possible diagnosis

candidates and then use active diagnosis to find out which of those

candidates is the true diagnosis. Finally, based on the platform model,

we recover from the occurred failure such that the robot can continue to

operate. We evaluate our approach in a logistics robots scenario by

comparing it to having no diagnosis and diagnosis without platform

models, showing a significant improvement to both alternatives.
Reasoning about Beliefs and Meta-Beliefs by Regression in an Expressive Probabilistic Action Logic
Authors: Liu Daxin , Lakemeyer Gerhard
Published: August 2021

In a recent paper Belle and Lakemeyer proposed the logic DS, a probabilistic extension of a modal variant of the situation calculus with a model of belief based on weighted possible worlds. Among other things, they were able to precisely capture the beliefs of a probabilistic knowledge base in terms of the concept of only-believing. While intuitively appealing, the logic has a number of shortcomings. Perhaps the most severe is the limited expressiveness in that degrees of belief are restricted to constant rational numbers, which makes it impossible to express arbitrary belief distributions.

In this paper we will address this and other shortcomings by extending the language and modifying the semantics of belief and only-believing. Among other things, we will show that belief retains many but not all of the properties of DS. Moreover, it turns out that only-believing arbitrary sentences, including those mentioning belief, is uniquely satisfiable in our logic. For an interesting class of knowledge bases we also show how reasoning about beliefs and meta-beliefs after performing noisy actions and sensing can be reduced to reasoning about the initial beliefs of an agent using a form of regression.
Unsupervised Knowledge Graph Alignment by Probabilistic Reasoning and Semantic Embedding
Authors: Qi Zhiyuan , Zhang Ziheng , Chen Jiaoyan , Chen Xi , Xiang Yuejia , Zhang Ningyu , Zheng Yefeng
Published: August 2021

Knowledge Graph (KG) alignment is to discover the mappings (i.e., equivalent entities, relations, and others) between two KGs. The existing methods can be divided into the embedding-based models, and the conventional reasoning and lexical matching based systems. The former compute the similarity of entities via their cross-KG embeddings, but they usually rely on an ideal supervised learning setting for good performance and lack appropriate reasoning to avoid logically wrong mappings; while the latter address the reasoning issue but are poor at utilizing the KG graph structures and the entity contexts. In this study, we aim at combining the above two solutions and thus propose an iterative framework named PRASE which is based on probabilistic reasoning and semantic embedding. It learns the KG embeddings via entity mappings from a probabilistic reasoning system named PARIS, and feeds the resultant entity mappings and embeddings back into PARIS for augmentation. The PRASE framework is compatible with different embedding-based models, and our experiments on multiple datasets have demonstrated its state-of-the-art performance.
Kemeny Consensus Complexity
Authors: Fitzsimmons Zack , Hemaspaandra Edith
Published: August 2021

The computational study of election problems generally focuses on questions related to the winner or set of winners of an election. But social preference functions such as Kemeny rule output a full ranking of the candidates (a consensus). We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is coNP-complete. We also study the natural question of the complexity of manipulative actions that have a specific consensus as a goal. Though determining whether a ranking is a Kemeny consensus is hard, the optimal action for manipulators is to simply vote their desired consensus. We provide evidence that this simplicity is caused by the combination of election system (Kemeny), manipulative action (manipulation), and manipulative goal (consensus). In the process we provide the first completeness results at the second level of the polynomial hierarchy for electoral manipulation and for optimal solution recognition.
Ranking Extensions in Abstract Argumentation
Authors: Skiba Kenneth , Rienstra Tjitze , Thimm Matthias , Heyninck Jesse , Kern-Isberner Gabriele
Published: August 2021

Extension-based semantics in abstract argumentation provide a criterion to determine whether a set of arguments is acceptable or not. In this paper, we present the notion of extension-ranking semantics, which determines a preordering over sets of arguments, where one set is deemed more plausible than another if it is somehow more acceptable. We obtain extension-based semantics as a special case of this new approach, but it also allows us to make more fine-grained distinctions, such as one set being "more complete'' or "more admissible'' than another. We define a number of general principles to classify extension-ranking semantics and develop concrete approaches. We also study the relation between extension-ranking semantics and argument-ranking based semantics, which rank individual arguments instead of sets of arguments.
Physics-informed Spline Learning for Nonlinear Dynamics Discovery
Authors: Sun Fangzheng , Liu Yang , Sun Hao
Published: August 2021

Dynamical systems are typically governed by a set of linear/nonlinear differential equations. Distilling the analytical form of these equations from very limited data remains intractable in many disciplines such as physics, biology, climate science, engineering and social science. To address this fundamental challenge, we propose a novel Physics-informed Spline Learning (PiSL) framework to discover parsimonious governing equations for nonlinear dynamics, based on sparsely sampled noisy data. The key concept is to (1) leverage splines to interpolate locally the dynamics, perform analytical differentiation and build the library of candidate terms, (2) employ sparse representation of the governing equations, and (3) use the physics residual in turn to inform the spline learning. The synergy between splines and discovered underlying physics leads to the robust capacity of dealing with high-level data scarcity and noise. A hybrid sparsity-promoting alternating direction optimization strategy is developed for systematically pruning the sparse coefficients that form the structure and explicit expression of the governing equations. The efficacy and superiority of the proposed method have been demonstrated by multiple well-known nonlinear dynamical systems, in comparison with two state-of-the-art methods.
Skeptical Reasoning with Preferred Semantics in Abstract Argumentation without Computing Preferred Extensions
Authors: Thimm Matthias , Cerutti Federico , Vallati Mauro
Published: August 2021

We address the problem of deciding skeptical acceptance wrt. preferred semantics of an argument in abstract argumentation frameworks, i.e., the problem of deciding whether an argument is contained in all maximally admissible sets, a.k.a. preferred extensions. State-of-the-art algorithms solve this problem with iterative calls to an external SAT-solver to determine preferred extensions. We provide a new characterisation of skeptical acceptance wrt. preferred semantics that does not involve the notion of a preferred extension. We then develop a new algorithm that also relies on iterative calls to an external SAT-solver but avoids the costly part of maximising admissible sets. We present the results of an experimental evaluation that shows that this new approach significantly outperforms the state of the art. We also apply similar ideas to develop a new algorithm for computing the ideal extension.
Abstract Argumentation Frameworks with Domain Assignments
Authors: Vassiliades Alexandros , Patkos Theodore , Flouris Giorgos , Bikakis Antonis , Bassiliades Nick , Plexousakis Dimitris
Published: August 2021

Argumentative discourse rarely consists of opinions whose claims apply universally. As with logical statements, an argument applies to specific objects in the universe or relations among them, and may have exceptions. In this paper, we propose

an argumentation formalism that allows associating arguments with a domain of application. Appropriate semantics are given, which formalise the notion of partial argument acceptance, i.e. the set of objects or relations that an argument can be applied

to. We show that our proposal is in fact equivalent to the standard Argumentation Frameworks of Dung, but allows a more intuitive and compact expression of some core concepts of commonsense and non-monotonic reasoning, such as the scope of an argument, exceptions, relevance and others.
Towards Understanding the Spectral Bias of Deep Learning
Authors: Cao Yuan , Fang Zhiying , Wu Yue , Zhou Ding-Xuan , Gu Quanquan
Published: August 2021

An intriguing phenomenon observed during training neural networks is the spectral bias, which states that neural networks are biased towards learning less complex functions. The priority of learning functions with low complexity might be at the core of explaining the generalization ability of neural networks, and certain efforts have been made to provide a theoretical explanation for spectral bias. However, there is still no satisfying theoretical result justifying the underlying mechanism of spectral bias. In this paper, we give a comprehensive and rigorous explanation for spectral bias and relate it with the neural tangent kernel function proposed in recent work. We prove that the training process of neural networks can be decomposed along different directions defined by the eigenfunctions of the neural tangent kernel, where each direction has its own convergence rate and the rate is determined by the corresponding eigenvalue. We then provide a case study when the input data is uniformly distributed over the unit sphere, and show that lower degree spherical harmonics are easier to be learned by over-parameterized neural networks. Finally, we provide numerical experiments to demonstrate the correctness of our theory. Our experimental results also show that our theory can tolerate certain model misspecification in terms of the input data distribution.
Understanding Structural Vulnerability in Graph Convolutional Networks
Authors: Chen Liang , Li Jintang , Peng Qibiao , Liu Yang , Zheng Zibin , Yang Carl
Published: August 2021

Recent studies have shown that Graph Convolutional Networks (GCNs) are vulnerable to adversarial attacks on the graph structure. Although multiple works have been proposed to improve their robustness against such structural adversarial attacks, the reasons for the success of the attacks remain unclear. In this work, we theoretically and empirically demonstrate that structural adversarial examples can be attributed to the non-robust aggregation scheme (i.e., the weighted mean) of GCNs. Specifically, our analysis takes advantage of the breakdown point which can quantitatively measure the robustness of aggregation schemes. The key insight is that weighted mean, as the basic design of GCNs, has a low breakdown point and its output can be dramatically changed by injecting a single edge. We show that adopting the aggregation scheme with a high breakdown point (e.g., median or trimmed mean) could significantly enhance the robustness of GCNs against structural attacks. Extensive experiments on four real-world datasets demonstrate that such a simple but effective method achieves the best robustness performance compared to state-of-the-art models.
Monte Carlo Filtering Objectives
Authors: Chen Shuangshuang , Ding Sihao , Karayiannidis Yiannis , Björkman Mårten
Published: August 2021

Learning generative models and inferring latent trajectories have shown to be challenging for time series due to the intractable marginal likelihoods of flexible generative models. It can be addressed by surrogate objectives for optimization. We propose Monte Carlo filtering objectives (MCFOs), a family of variational objectives for jointly learning parametric generative models and amortized adaptive importance proposals of time series. MCFOs extend the choices of likelihood estimators beyond Sequential Monte Carlo in state-of-the-art objectives, possess important properties revealing the factors for the tightness of objectives, and allow for less biased and variant gradient estimates. We demonstrate that the proposed MCFOs and gradient estimations lead to efficient and stable model learning, and learned generative models well explain data and importance proposals are more sample efficient on various kinds of time series data.
Few-Shot Learning with Part Discovery and Augmentation from Unlabeled Images
Authors: Chen Wentao , Si Chenyang , Wang Wei , Wang Liang , Wang Zilei , Tan Tieniu
Published: August 2021

Few-shot learning is a challenging task since only few instances are given for recognizing an unseen class. One way to alleviate this problem is to acquire a strong inductive bias via meta-learning on similar tasks. In this paper, we show that such inductive bias can be learned from a flat collection of unlabeled images, and instantiated as transferable representations among seen and unseen classes. Specifically, we propose a novel part-based self-supervised representation learning scheme to learn transferable representations by maximizing the similarity of an image to its discriminative part. To mitigate the overfitting in few-shot classification caused by data scarcity, we further propose a part augmentation strategy by retrieving extra images from a base dataset. We conduct systematic studies on miniImageNet and tieredImageNet benchmarks. Remarkably, our method yields impressive results, outperforming the previous best unsupervised methods by 7.74% and 9.24% under 5-way 1-shot and 5-way 5-shot settings, which are comparable with state-of-the-art supervised methods.
Time-Aware Multi-Scale RNNs for Time Series Modeling
Authors: Chen Zipeng , Ma Qianli , Lin Zhenxi
Published: August 2021

Multi-scale information is crucial for modeling time series. Although most existing methods consider multiple scales in the time-series data, they assume all kinds of scales are equally important for each sample, making them unable to capture the dynamic temporal patterns of time series. To this end, we propose Time-Aware Multi-Scale Recurrent Neural Networks (TAMS-RNNs), which disentangle representations of different scales and adaptively select the most important scale for each sample at each time step. First, the hidden state of the RNN is disentangled into multiple independently updated small hidden states, which use different update frequencies to model time-series multi-scale information. Then, at each time step, the temporal context information is used to modulate the features of different scales, selecting the most important time-series scale. Therefore, the proposed model can capture the multi-scale information for each time series at each time step adaptively. Extensive experiments demonstrate that the model outperforms state-of-the-art methods on multivariate time series classification and human motion prediction tasks. Furthermore, visualized analysis on music genre recognition verifies the effectiveness of the model.
Isotonic Data Augmentation for Knowledge Distillation
Authors: Cui Wanyun , Yan Sen
Published: August 2021

Knowledge distillation uses both real hard labels and soft labels predicted by teacher model as supervision. Intuitively, we expect the soft label probabilities and hard label probabilities to be concordant. However, in the real knowledge distillations, we found critical rank violations between hard labels and soft labels for augmented samples. For example, for an augmented sample x = 0.7 * cat + 0.3 * panda, a meaningful soft label distribution should have the same rank: P(cat|x)>P(panda|x)>P(other|x). But real teacher models usually violate the rank: P(tiger|x)>P(panda|x)>P(cat|x). We attribute the rank violations to the increased difficulty of understanding augmented samples for the teacher model. Empirically, we found the violations injuries the knowledge transfer. In this paper, we denote eliminating rank violations in data augmentation for knowledge distillation as isotonic data augmentation (IDA). We use isotonic regression (IR) -- a classic statistical algorithm -- to eliminate the rank violations. We show that IDA can be modeled as a tree-structured IR problem and gives an O(c*log(c)) optimal algorithm, where c is the number of labels. In order to further reduce the time complexity of the optimal algorithm, we also proposed a GPU-friendly approximation algorithm with linear time complexity. We have verified on variant datasets and data augmentation baselines that (1) the rank violation is a general phenomenon for data augmentation in knowledge distillation. And (2) our proposed IDA algorithms effectively increases the accuracy of knowledge distillation by solving the ranking violations.
Graph-Free Knowledge Distillation for Graph Neural Networks
Authors: Deng Xiang , Zhang Zhongfei
Published: August 2021

Knowledge distillation (KD) transfers knowledge from a teacher network to a student by enforcing the student to mimic the outputs of the pretrained teacher on training data. However, data samples are not always accessible in many cases due to large data sizes, privacy, or confidentiality. Many efforts have been made on addressing this problem for convolutional neural networks (CNNs) whose inputs lie in a grid domain within a continuous space such as images and videos, but largely overlook graph neural networks (GNNs) that handle non-grid data with different topology structures within a discrete space. The inherent differences between their inputs make these CNN-based approaches not applicable to GNNs. In this paper, we propose to our best knowledge the first dedicated approach to distilling knowledge from a GNN without graph data. The proposed graph-free KD (GFKD) learns graph topology structures for knowledge transfer by modeling them with multinomial distribution. We then introduce a gradient estimator to optimize this framework. Essentially, the gradients w.r.t. graph structures are obtained by only using GNN forward-propagation without back-propagation, which means that GFKD is compatible with modern GNN libraries such as DGL and Geometric. Moreover, we provide the strategies for handling different types of prior knowledge in the graph data or the GNNs. Extensive experiments demonstrate that GFKD achieves the state-of-the-art performance for distilling knowledge from GNNs without training data.
Jointly Learning Prices and Product Features
Authors: Emamjomeh-Zadeh Ehsan , Paes Leme Renato , Schneider Jon , Sivan Balasubramanian
Published: August 2021

Product Design is an important problem in marketing research where a firm tries

to learn what features of a product are more valuable to consumers. We study

this problem from the viewpoint of online learning: a firm repeatedly interacts

with a buyer by choosing a product configuration as well as a price and

observing the buyer's purchasing decision. The goal of the firm is to maximize

revenue throughout the course of $T$ rounds by

learning the buyer's preferences.

We study both the case of a set of discrete products and the case of a continuous set of

allowable product features. In both cases we provide nearly tight

upper and lower regret bounds.
Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation
Authors: Guan Yue , Zhang Qifan , Tsiotras Panagiotis
Published: August 2021

We explore the use of policy approximations to reduce the computational cost of learning Nash equilibria in zero-sum stochastic games. We propose a new Q-learning type algorithm that uses a sequence of entropy-regularized soft policies to approximate the Nash policy during the Q-function updates. We prove that under certain conditions, by updating the entropy regularization, the algorithm converges to a Nash equilibrium. We also demonstrate the proposed algorithm's ability to transfer previous training experiences, enabling the agents to adapt quickly to new environments. We provide a dynamic hyper-parameter scheduling scheme to further expedite convergence. Empirical results applied to a number of stochastic games verify that the proposed algorithm converges to the Nash equilibrium, while exhibiting a major speed-up over existing algorithms.
Surprisingly Popular Voting Recovers Rankings, Surprisingly!
Authors: Hosseini Hadi , Mandal Debmalya , Shah Nisarg , Shi Kevin
Published: August 2021

The wisdom of the crowd has long become the de facto approach for eliciting information from individuals or experts in order to predict the ground truth. However, classical democratic approaches for aggregating individual \emph{votes} only work when the opinion of the majority of the crowd is relatively accurate. A clever recent approach, \emph{surprisingly popular voting}, elicits additional information from the individuals, namely their \emph{prediction} of other individuals' votes, and provably recovers the ground truth even when experts are in minority. This approach works well when the goal is to pick the correct option from a small list, but when the goal is to recover a true ranking of the alternatives, a direct application of the approach requires eliciting too much information. We explore practical techniques for extending the surprisingly popular algorithm to ranked voting by partial votes and predictions and designing robust aggregation rules. We experimentally demonstrate that even a little prediction information helps surprisingly popular voting outperform classical approaches.
SalientSleepNet: Multimodal Salient Wave Detection Network for Sleep Staging
Authors: Jia Ziyu , Lin Youfang , Wang Jing , Wang Xuehui , Xie Peiyi , Zhang Yingbin
Published: August 2021

Sleep staging is fundamental for sleep assessment and disease diagnosis. Although previous attempts to classify sleep stages have achieved high classification performance, several challenges remain open: 1) How to effectively extract salient waves in multimodal sleep data; 2) How to capture the multi-scale transition rules among sleep stages; 3) How to adaptively seize the key role of specific modality for sleep staging. To address these challenges, we propose SalientSleepNet, a multimodal salient wave detection network for sleep staging. Specifically, SalientSleepNet is a temporal fully convolutional network based on the $U^2$-Net architecture that is originally proposed for salient object detection in computer vision. It is mainly composed of two independent $U^2$-like streams to extract the salient features from multimodal data, respectively. Meanwhile, the multi-scale extraction module is designed to capture multi-scale transition rules among sleep stages. Besides, the multimodal attention module is proposed to adaptively capture valuable information from multimodal data for the specific sleep stage. Experiments on the two datasets demonstrate that SalientSleepNet outperforms the state-of-the-art baselines. It is worth noting that this model has the least amount of parameters compared with the existing deep neural network models.
Residential Electric Load Forecasting via Attentive Transfer of Graph Neural Networks
Authors: Lin Weixuan , Wu Di
Published: August 2021

An accurate short-term electric load forecasting is critical for modern electric power systems' safe and economical operation.

Electric load forecasting can be formulated as a multi-variate time series problem. Residential houses in the same neighborhood may be affected by similar factors and share some latent spatial dependencies. However, most of the existing works on electric load forecasting fail to explore such dependencies. In recent years, graph neural networks (GNNs) have shown impressive success in modeling such dependencies. However, such GNN based models usually would require a large amount of training data. We may have a minimal amount of data available to train a reliable forecasting model for houses in a new neighborhood area. At the same time, we may have a large amount of historical data collected from other houses that can be leveraged to improve the new neighborhood's prediction performance. In this paper, we propose an attentive transfer learning-based GNN model that can utilize the learned prior knowledge to improve the learning process in a new area. The transfer process is achieved by an attention network, which generically avoids negative transfer by leveraging knowledge from multiple sources.

Extensive experiments have been conducted on real-world data sets. Results have shown that the proposed framework can consistently outperform baseline models in different areas.
A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism
Authors: Iwase Tatsuya , Stein Sebastian , Gerding Enrico H.
Published: August 2021

Ridesharing has great potential to improve transportation efficiency while reducing congestion and pollution. To realize this potential, mechanisms are needed that allocate vehicles optimally and provide the right incentives to riders. However, many existing approaches consider restricted settings (e.g.,

only one rider per vehicle

or a common origin for all riders). Moreover,

naive applications of standard approaches, such as the Vickrey-Clarke-Groves or greedy mechanisms, cannot achieve a polynomial-time, truthful, individually rational and budget balanced mechanism. To address this, we formulate a general ridesharing problem and apply mechanism design to develop a novel mechanism which satisfies all four properties and whose social cost is within 8.6% of the optimal on average.
Temporal and Object Quantification Networks
Authors: Mao Jiayuan , Luo Zhezheng , Gan Chuang , Tenenbaum Joshua B. , Wu Jiajun , Kaelbling Leslie Pack , Ullman Tomer D.
Published: August 2021

We present Temporal and Object Quantification Networks (TOQ-Nets), a new class of neuro-symbolic networks with a structural bias that enables them to learn to recognize complex relational-temporal events. This is done by including reasoning layers that implement finite-domain quantification over objects and time. The structure allows them to generalize directly to input instances with varying numbers of objects in temporal sequences of varying lengths. We evaluate TOQ-Nets on input domains that require recognizing event-types in terms of complex temporal relational patterns. We demonstrate that TOQ-Nets can generalize from small amounts of data to scenarios containing more objects than were present during training and to temporal warpings of input sequences.
Stochastic Shortest Path with Adversarially Changing Costs
Authors: Rosenberg Aviv , Mansour Yishay
Published: August 2021

Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. In this paper we present the adversarial SSP model that also accounts for adversarial changes in the costs over time, while the underlying transition function remains unchanged. Formally, an agent interacts with an SSP environment for K episodes, the cost function changes arbitrarily between episodes, and the transitions are unknown to the agent. We develop the first algorithms for adversarial SSPs and prove high probability regret bounds of square-root K assuming all costs are strictly positive, and sub-linear regret in the general case. We are the first to consider this natural setting of adversarial SSP and obtain sub-linear regret for it.