bluuebunny/crossref_metadata_2025 huggingface dataset:
GOCPT: Generalized Online Canonical Polyadic Tensor Factorization and Completion
Authors: Yang Chaoqi , Qian Cheng , Sun Jimeng
Published: July 2022

Low-rank tensor factorization or completion is well-studied and applied in various online settings, such as online tensor factorization (where the temporal mode grows) and online tensor completion (where incomplete slices arrive gradually). However, in many real-world settings, tensors may have more complex evolving patterns: (i) one or more modes can grow; (ii) missing entries may be filled; (iii) existing tensor elements can change. Existing methods cannot support such complex scenarios. To fill the gap, this paper proposes a Generalized Online Canonical Polyadic (CP) Tensor factorization and completion framework (named GOCPT) for this general setting, where we maintain the CP structure of such dynamic tensors during the evolution. We show that existing online tensor factorization and completion setups can be unified under the GOCPT framework. Furthermore, we propose a variant, named GOCPTE, to deal with cases where historical tensor elements are unavailable (e.g., privacy protection), which achieves similar fitness as GOCPT but with much less computational cost. Experimental results demonstrate that our GOCPT can improve fitness by up to 2.8% on the JHU Covid data and 9.2% on a proprietary patient claim dataset over baselines. Our variant GOCPTE shows up to 1.2% and 5.5% fitness improvement on two datasets with about 20% speedup compared to the best model.
Table2Graph: Transforming Tabular Data to Unified Weighted Graph
Authors: Zhou Kaixiong , Liu Zirui , Chen Rui , Li Li , Choi Soo-Hyun , Hu Xia
Published: July 2022

Learning useful interactions between input features is crucial for tabular data modeling. Recent efforts start to explicitly model the feature interactions with graph, where each feature is treated as an individual node. However, the existing graph construction methods either heuristically formulate a fixed feature-interaction graph based on specific domain knowledge, or simply apply attention function to compute the pairwise feature similarities for each sample. While the fixed graph may be sub-optimal to downstream tasks, the sample-wise graph construction is time-consuming during model training and inference. To tackle these issues, we propose a framework named Table2Graph to transform the feature interaction modeling to learning a unified graph. Represented as a probability adjacency matrix, the unified graph learns to model the key feature interactions shared by the diverse samples in the tabular data. To well optimize the unified graph, we employ the reinforcement learning policy to capture the key feature interactions stably. A sparsity constraint is also proposed to regularize the learned graph from being overly-sparse/smooth. The experimental results in a variety of real-world applications demonstrate the effectiveness and efficiency of our Table2Graph, in terms of the prediction accuracy and feature interaction detection.
Spiking Graph Convolutional Networks
Authors: Zhu Zulun , Peng Jiaying , Li Jintang , Chen Liang , Yu Qi , Luo Siqiang
Published: July 2022

Graph Convolutional Networks (GCNs) achieve an impressive performance due to the remarkable representation ability in learning the graph information. However, GCNs, when implemented on a deep network, require expensive computation power, making them difficult to be deployed on battery-powered devices. In contrast, Spiking Neural Networks (SNNs), which perform a bio-fidelity inference process, offer an energy-efficient neural architecture. In this work, we propose SpikingGCN, an end-to-end framework that aims to integrate the embedding of GCNs with the biofidelity characteristics of SNNs. The original graph data are encoded into spike trains based on the incorporation of graph convolution. We further model biological information processing

by utilizing a fully connected layer combined with neuron nodes. In a wide range of scenarios (e.g., citation networks, image graph classification, and recommender systems), our experimental results show that the proposed method could gain competitive performance against state-of-the-art approaches. Furthermore, we show that SpikingGCN on a neuromorphic chip can bring a clear advantage of energy efficiency into graph data analysis, which demonstrates its great potential to construct environment-friendly machine learning models.
Personalized Federated Learning With a Graph
Authors: Chen Fengwen , Long Guodong , Wu Zonghan , Zhou Tianyi , Jiang Jing
Published: July 2022

Knowledge sharing and model personalization are two key components in the conceptual framework of personalized federated learning (PFL). Existing PFL methods focus on proposing new model personalization mechanisms while simply implementing knowledge sharing by aggregating models from all clients, regardless of their relation graph. This paper aims to enhance the knowledge-sharing process in PFL by leveraging the graph-based structural information among clients. We propose a novel structured federated learning (SFL) framework to learn both the global and personalized models simultaneously using client-wise relation graphs and clients' private data. We cast SFL with graph into a novel optimization problem that can model the client-wise complex relations and graph-based structural topology by a unified framework. Moreover, in addition to using an existing relation graph, SFL could be expanded to learn the hidden relations among clients. Experiments on traffic and image benchmark datasets can demonstrate the effectiveness of the proposed method.
Computing Concept Referring Expressions for Queries on Horn ALC Ontologies
Authors: Illich Moritz , Glimm Birte
Published: July 2022

Classical instance queries over an ontology only consider explicitly named individuals. Concept referring expressions (CREs) also allow for returning answers in the form of concepts that describe implicitly given individuals in terms of their relation to an explicitly named one. Existing approaches, e.g., based on tree automata, can neither be integrated into state-of-the-art OWL reasoners nor are they directly amenable for an efficient implementation. To address this, we devise a novel algorithm that uses highly optimized OWL reasoners as a black box. In addition to the standard criteria of singularity and certainty for CREs, we devise and consider the criterion of uniqueness of CREs for Horn ALC ontologies. The evaluation of our prototypical implementation shows that computing CREs for the most general concept (Top) can be done in less than one minute for ontologies with thousands of individuals and concepts.
Simple and Effective Relation-based Embedding Propagation for Knowledge Representation Learning
Authors: Wang Huijuan , Dai Siming , Su Weiyue , Zhong Hui , Fang Zeyang , Huang Zhengjie , Feng Shikun , Chen Zeyu , Sun Yu , Yu Dianhai
Published: July 2022

Relational graph neural networks have garnered particular attention to encode graph context in knowledge graphs (KGs). Although they achieved competitive performance on small KGs, how to efficiently and effectively utilize graph context for large KGs remains an open problem. To this end, we propose the Relation-based Embedding Propagation (REP) method. It is a post-processing technique to adapt pre-trained KG embeddings with graph context. As relations in KGs are directional, we model the incoming head context and the outgoing tail context separately. Accordingly, we design relational context functions with no external parameters. Besides, we use averaging to aggregate context information, making REP more computation-efficient. We theoretically prove that such designs can avoid information distortion during propagation. Extensive experiments also demonstrate that REP has significant scalability while improving or maintaining prediction quality. Particularly, it averagely brings about 10% relative improvement to triplet-based embedding methods on OGBL-WikiKG2 and takes 5%-83% time to achieve comparable results as the state-of-the-art GC-OTE.
Not a Number: Identifying Instance Features for Capability-Oriented Evaluation
Authors: Burnell Ryan , Burden John , Rutar Danaja , Voudouris Konstantinos , Cheke Lucy , Hernández-Orallo José
Published: July 2022

In AI evaluation, performance is often calculated by averaging across various instances. But to fully understand the capabilities of an AI system, we need to understand the factors that cause its pattern of success and failure. In this paper, we present a new methodology to identify and build informative instance features that can provide explanatory and predictive power to analyse the behaviour of AI systems more robustly. The methodology builds on these relevant features that should relate monotonically with success, and represents patterns of performance in a new type of plots known as ‘agent characteristic grids’. We illustrate this methodology with the Animal-AI competition as a representative example of how we can revisit existing competitions and benchmarks in AI—even when evaluation data is sparse. Agents with the same average performance can show very different patterns of performance at the instance level. With this methodology, these patterns can be visualised, explained and predicted, progressing towards a capability-oriented evaluation rather than relying on a less informative average performance score.
Non-Cheating Teaching Revisited: A New Probabilistic Machine Teaching Model
Authors: Ferri Cèsar , Hernández-Orallo José , Telle Jan Arne
Published: July 2022

Over the past decades in the field of machine teaching, several restrictions have been introduced to avoid ‘cheating’, such as collusion-free or non-clashing teaching. However, these restrictions forbid several teaching situations that we intuitively consider natural and fair, especially those ‘changes of mind’ of the learner as more evidence is given, affecting the likelihood of concepts and ultimately their posteriors. Under a new generalised probabilistic teaching, not only do these non-cheating constraints look too narrow but we also show that the most relevant machine teaching models are particular cases of this framework: the consistency graph between concepts and elements simply becomes a joint probability distribution. We show a simple procedure that builds the witness joint distribution from the ground joint distribution. We prove a chain of relations, also with a theoretical lower bound, on the teaching dimension of the old and new models. Overall, this new setting is more general than the traditional machine teaching models, yet at the same time more intuitively capturing a less abrupt notion of non-cheating teaching.
Robust Reinforcement Learning as a Stackelberg Game via Adaptively-Regularized Adversarial Training
Authors: Huang Peide , Xu Mengdi , Fang Fei , Zhao Ding
Published: July 2022

Robust Reinforcement Learning (RL) focuses on improving performances under model errors or adversarial attacks, which facilitates the real-life deployment of RL agents. Robust Adversarial Reinforcement Learning (RARL) is one of the most popular frameworks for robust RL. However, most of the existing literature models RARL as a zero-sum simultaneous game with Nash equilibrium as the solution concept, which could overlook the sequential nature of RL deployments, produce overly conservative agents, and induce training instability. In this paper, we introduce a novel hierarchical formulation of robust RL -- a general-sum Stackelberg game model called RRL-Stack -- to formalize the sequential nature and provide extra flexibility for robust training. We develop the Stackelberg Policy Gradient algorithm to solve RRL-Stack, leveraging the Stackelberg learning dynamics by considering the adversary's response. Our method generates challenging yet solvable adversarial environments which benefit RL agents' robust learning. Our algorithm demonstrates better training stability and robustness against different testing conditions in the single-agent robotics control and multi-agent highway merging tasks.
Thompson Sampling for Bandit Learning in Matching Markets
Authors: Kong Fang , Yin Junming , Li Shuai
Published: July 2022

The problem of two-sided matching markets has a wide range of real-world applications and has been extensively studied in the literature. A line of recent works have focused on the problem setting where the preferences of one-side market participants are unknown a priori and are learned by iteratively interacting with the other side of participants. All these works are based on explore-then-commit (ETC) and upper confidence bound (UCB) algorithms, two common strategies in multi-armed bandits (MAB). Thompson sampling (TS) is another popular approach, which attracts lots of attention due to its easier implementation and better empirical performances. In many problems, even when UCB and ETC-type algorithms have already been analyzed, researchers are still trying to study TS for its benefits. However, the convergence analysis of TS is much more challenging and remains open in many problem settings. In this paper, we provide the first regret analysis for TS in the new setting of iterative matching markets. Extensive experiments demonstrate the practical advantages of the TS-type algorithm over the ETC and UCB-type baselines.
Rethinking the Setting of Semi-supervised Learning on Graphs
Authors: Li Ziang , Ding Ming , Li Weikai , Wang Zihan , Zeng Ziyu , Cen Yukuo , Tang Jie
Published: July 2022

We argue that the present setting of semisupervised learning on graphs may result in unfair comparisons, due to its potential risk of over-tuning hyper-parameters for models. In this paper, we highlight the significant influence of tuning hyper-parameters, which leverages the label information in the validation set to improve the performance. To explore the limit of over-tuning hyperparameters, we propose ValidUtil, an approach to fully utilize the label information in the validation set through an extra group of hyper-parameters. With ValidUtil, even GCN can easily get high accuracy of 85.8% on Cora.

To avoid over-tuning, we merge the training set and the validation set and construct an i.i.d. graph benchmark (IGB) consisting of 4 datasets. Each dataset contains 100 i.i.d. graphs sampled from a large graph to reduce the evaluation variance. Our experiments suggest that IGB is a more stable benchmark than previous datasets for semisupervised learning on graphs. Our code and data are released at https://github.com/THUDM/IGB/.
Contrastive Multi-view Hyperbolic Hierarchical Clustering
Authors: Lin Fangfei , Bai Bing , Bai Kun , Ren Yazhou , Zhao Peng , Xu Zenglin
Published: July 2022

Hierarchical clustering recursively partitions data at an increasingly finer granularity. In real-world applications, multi-view data have become increasingly important. This raises a less investigated problem, i.e., multi-view hierarchical clustering, to better understand the hierarchical structure of multi-view data. To this end, we propose a novel neural network-based model, namely Contrastive Multi-view Hyperbolic Hierarchical Clustering(CMHHC). It consists of three components, i.e., multi-view alignment learning, aligned feature similarity learning, and continuous hyperbolic hierarchical clustering. First, we align sample-level representations across multiple views in a contrastive way to capture the view-invariance information. Next, we utilize both the manifold and Euclidean similarities to improve the metric property. Then, we embed the representations into a hyperbolic space and optimize the hyperbolic embeddings via a continuous relaxation of hierarchical clustering loss. Finally, a binary clustering tree is decoded from optimized hyperbolic embeddings. Experimental results on five real-world datasets demonstrate the effectiveness of the proposed method and its components.
Composing Neural Learning and Symbolic Reasoning with an Application to Visual Discrimination
Authors: Murali Adithya , Sehgal Atharva , Krogmeier Paul , Madhusudan P.
Published: July 2022

We consider the problem of combining machine learning models to perform higher-level cognitive tasks with clear specifications. We propose the novel problem of Visual Discrimination Puzzles (VDP) that requires finding interpretable discriminators that classify images according to a logical specification. Humans can solve these puzzles with ease and they give robust, verifiable, and interpretable discriminators as answers. We propose a compositional neurosymbolic framework that combines a neural network to detect objects and relationships with a symbolic learner that finds interpretable discriminators. We create large classes of VDP datasets involving natural and artificial images and show that our neurosymbolic framework performs favorably compared to several purely neural approaches.
Phragmén Rules for Degressive and Regressive Proportionality
Authors: Jaworski Michał , Skowron Piotr
Published: July 2022

We study two concepts of proportionality in the model of approval-based committee elections. In degressive proportionality small minorities of voters are favored in comparison with the standard linear proportionality. Regressive proportionality, on the other hand, requires that larger subdivisions of voters are privileged. We introduce a new family of rules that broadly generalize Phragmén's Sequential Rule spanning the spectrum between degressive and regressive proportionality. We analyze and compare the two principles of proportionality assuming the voters and the candidates can be represented as points in an Euclidean issue space.
Memory Augmented State Space Model for Time Series Forecasting
Authors: Sun Yinbo , Ma Lintao , Liu Yu , Wang Shijun , Zhang James , Zheng YangFei , Yun Hu , Lei Lei , Kang Yulin , Ye Llinbao
Published: July 2022

State space model (SSM) provides a general and flexible forecasting framework for time series. Conventional SSM with fixed-order Markovian assumption often falls short in handling the long-range temporal dependencies and/or highly non-linear correlation in time-series data, which is crucial for accurate forecasting. To this extend, we present External Memory Augmented State Space Model (EMSSM) within the sequential Monte Carlo (SMC) framework. Unlike the common fixed-order Markovian SSM, our model features an external memory system, in which we store informative latent state experience, whereby to create ``memoryful" latent dynamics modeling complex long-term dependencies. Moreover, conditional normalizing flows are incorporated in our emission model, enabling the adaptation to a broad class of underlying data distributions. We further propose a Monte Carlo Objective that employs an efficient variational proposal distribution, which fuses the filtering and the dynamic prior information, to approximate the posterior state with proper particles. Our results demonstrate the competitiveness of forecasting performance of our proposed model comparing with other state-of-the-art SSMs.
Learning Mixture of Neural Temporal Point Processes for Multi-dimensional Event Sequence Clustering
Authors: Zhang Yunhao , Yan Junchi , Zhang Xiaolu , Zhou Jun , Yang Xiaokang
Published: July 2022

Multi-dimensional event sequence clustering applies to many scenarios e.g. e-Commerce and electronic health. Traditional clustering models fail to characterize complex real-world processes due to the strong parametric assumption. While Neural Temporal Point Processes (NTPPs) mainly focus on modeling similar sequences instead of clustering. To fill the gap, we propose Mixture of Neural Temporal Point Processes (NTPP-MIX), a general framework that can utilize many existing NTPPs for multi-dimensional event sequence clustering. In NTPP-MIX, the prior distribution of coefficients for cluster assignment is modeled by a Dirichlet distribution. When the assignment is given, the conditional probability of a sequence is modeled by the mixture of a series of NTPPs. We combine variational EM algorithm and Stochastic Gradient Descent (SGD) to efficiently train the framework. In E-step, we fix parameters for NTPPs and approximate the true posterior with variational distributions. In M-step, we fix variational distributions and use SGD to update parameters of NTPPs. Extensive experimental results on four synthetic datasets and three real-world datasets show the effectiveness of NTPP-MIX against state-of-the-arts.
Learning Mixtures of Random Utility Models with Features from Incomplete Preferences
Authors: Zhao Zhibing , Liu Ao , Xia Lirong
Published: July 2022

Random Utility Models (RUMs), which subsume Plackett-Luce model (PL) as a special case, are among the most popular models for preference learning. In this paper, we consider RUMs with features and their mixtures, where each alternative has a vector of features, possibly different across agents. Such models significantly generalize the standard PL and RUMs, but are not as well investigated in the literature. We extend mixtures of RUMs with features to models that generate incomplete preferences and characterize their identifiability. For PL, we prove that when PL with features is identifiable, its MLE is consistent with a strictly concave objective function under mild assumptions, by characterizing a bound on root-mean-square-error (RMSE), which naturally leads to a sample complexity bound. We also characterize identifiability of more general RUMs with features and propose a generalized RBCML to learn them. Our experiments on synthetic data demonstrate the effectiveness of MLE on PL with features with tradeoffs between statistical efficiency and computational efficiency. Our experiments on real-world data show the prediction power of PL with features and its mixtures.
Towards Controlling the Transmission of Diseases: Continuous Exposure Discovery over Massive-Scale Moving Objects
Authors: Li Ke , Chen Lisi , Shang Shuo , Wang Haiyan , Liu Yang , Kalnis Panos , Yao Bin
Published: July 2022

Infectious diseases have been recognized as major public health concerns for decades. Close contact discovery is playing an indispensable role in preventing epidemic transmission. In this light, we study the continuous exposure search problem: Given a collection of moving objects and a collection of moving queries, we continuously discover all objects that have been directly and indirectly exposed to at least one query over a period of time. Our problem targets a variety of applications, including but not limited to disease control, epidemic pre-warning, information spreading, and co-movement mining. To answer this problem, we develop an exact group processing algorithm with optimization strategies. Further, we propose an approximate algorithm that substantially improves the efficiency without false dismissal. Extensive experiments offer insight into effectiveness and efficiency of our proposed algorithms.
FOGS: First-Order Gradient Supervision with Learning-based Graph for Traffic Flow Forecasting
Authors: Rao Xuan , Wang Hao , Zhang Liang , Li Jing , Shang Shuo , Han Peng
Published: July 2022

Traffic flow forecasting plays a vital role in the transportation domain.

Existing studies usually manually construct correlation graphs and design sophisticated models for learning spatial and temporal features to predict future traffic states.

However, manually constructed correlation graphs cannot accurately extract the complex patterns hidden in the traffic data.

In addition, it is challenging for the prediction model to fit traffic data due to its irregularly-shaped distribution.

To solve the above-mentioned problems, in this paper, we propose a novel learning-based method to learn a spatial-temporal correlation graph, which could make good use of the traffic flow data.

Moreover, we propose First-Order Gradient Supervision (FOGS), a novel method for traffic flow forecasting.

FOGS utilizes first-order gradients, rather than specific flows, to train prediction model, which effectively avoids the problem of fitting irregularly-shaped distributions. Comprehensive numerical evaluations on four real-world datasets reveal that the proposed methods achieve state-of-the-art performance and significantly outperform the benchmarks.
A Unified Strategy for Multilingual Grammatical Error Correction with Pre-trained Cross-Lingual Language Model
Authors: Sun Xin , Ge Tao , Ma Shuming , Li Jingjing , Wei Furu , Wang Houfeng
Published: July 2022

Synthetic data construction of Grammatical Error Correction (GEC) for non-English languages relies heavily on human-designed and language-specific rules, which produce limited error-corrected patterns. In this paper, we propose a generic and language-independent strategy for multilingual GEC, which can train a GEC system effectively for a new non-English language with only two easy-to-access resources: 1) a pre-trained cross-lingual language model (PXLM) and 2) parallel translation data between English and the language.

Our approach creates diverse parallel GEC data without any language-specific operations by taking the non-autoregressive translation generated by PXLM and the gold translation as error-corrected sentence pairs. Then, we reuse PXLM to initialize the GEC model and pre-train it with the synthetic data generated by itself, which yields further improvement. We evaluate our approach on three public benchmarks of GEC in different languages. It achieves the state-of-the-art results on the NLPCC 2018 Task 2 dataset (Chinese) and obtains competitive performance on Falko-Merlin (German) and RULEC-GEC (Russian). Further analysis demonstrates that our data construction method is complementary to rule-based approaches.
Automated Synthesis of Mechanisms
Authors: Mittelmann Munyque , Maubert Bastien , Murano Aniello , Perrussel Laurent
Published: July 2022

Mechanism Design aims to design a game so that a desirable outcome is reached regardless of agents' self-interests. In this paper, we show how this problem can be rephrased as a synthesis problem, where mechanisms are automatically synthesized from a partial or complete specification in a high-level logical language. We show that Quantitative Strategy Logic is a perfect candidate for specifying mechanisms as it can express complex strategic and quantitative properties. We solve automated mechanism design in two cases: when the number of actions is bounded, and when agents play in turn.
Explaining the Behaviour of Hybrid Systems with PDDL+ Planning
Authors: Aineto Diego , Onaindia Eva , Ramirez Miquel , Scala Enrico , Serina Ivan
Published: July 2022

The aim of this work is to explain the observed behaviour of a hybrid system (HS). The explanation problem is cast as finding a trajectory of the HS that matches some observations. By using the formalism of hybrid automata (HA), we characterize the explanations as the language of a network of HA that comprises one automaton for the HS and another one for the observations, thus restricting the behaviour of the HS exclusively to trajectories that explain the observations. We observe that this problem corresponds to a reachability problem in model-checking, but that state-of-the-art model checkers struggle to find concrete trajectories. To overcome this issue we provide a formal mapping from HA to PDDL+ and show how to use an off-the-shelf automated planner. An experimental analysis over domains with piece-wise constant, linear and nonlinear dynamics reveals that the proposed PDDL+ approach is much more efficient than solving directly the explanation problem with model-checking solvers.
A Native Qualitative Numeric Planning Solver Based on AND/OR Graph Search
Authors: Zeng Hemeng , Liang Yikun , Liu Yongmei
Published: July 2022

Qualitative numeric planning (QNP) is classical planning extended with non-negative real variables that can be increased or decreased by some arbitrary amount. Existing approaches for solving QNP problems are exclusively based on compilation to fully observable nondeterministic planning (FOND) problems or FOND+ problems, i.e., FOND problems with explicit fairness assumptions. However, the FOND-compilation approaches suffer from some limitations, such as difficulties to generate all strong cyclic solutions for FOND problems or introducing a great many extra variables and actions. In this paper, we propose a simpler characterization of QNP solutions and a new approach to solve QNP problems based on directly searching for a solution, which is a closed and terminating subgraph that contains a goal node, in the AND/OR graphs induced by QNP problems. Moreover, we introduce a pruning strategy based on termination tests on subgraphs. We implemented a native solver DSET based on the proposed approach and compared the performance of it with that of the two compilation-based approaches. Experimental results show that DSET is faster than the FOND-compilation approach by one order of magnitude, and comparable with the FOND+-compilation approach.
HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem
Authors: Wu Jun , Li Chu-Min , Zhou Yupeng , Yin Minghao , Xu Xin , Niu Dangdang
Published: July 2022

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with extensive applications, which extends the DTKC search problem by taking into account the weight of vertices. In this paper, we formulate DTKWC search problem using mixed integer linear program constraints and propose an efficient hybrid evolutionary algorithm (HEA-D) that combines a clique-based crossover operator and an effective simulated annealing-based local optimization procedure to find high-quality local optima. The experimental results show that HEA-D performs much better than the existing methods on two representative real-world benchmarks.
Hidden 1-Counter Markov Models and How to Learn Them
Authors: Kurucan Mehmet , Özbaltan Mete , Schewe Sven , Wojtczak Dominik
Published: July 2022

We introduce hidden 1-counter Markov models (H1MMs) as an attractive sweet spot between standard hidden Markov models (HMMs) and probabilistic context-free grammars (PCFGs). Both HMMs and PCFGs have a variety of applications, e.g., speech recognition, anomaly detection, and bioinformatics. PCFGs are more expressive than HMMs, e.g., they are more suited for studying protein folding or natural language processing. However, they suffer from slow parameter fitting, which is cubic in the observation sequence length. The same process for HMMs is just linear using the well-known forward-backward algorithm. We argue that by adding to each state of an HMM an integer counter, e.g., representing the number of clients waiting in a queue, brings its expressivity closer to PCFGs. At the same time, we show that parameter fitting for such a model is computationally inexpensive: it is bi-linear in the length of the observation sequence and the maximal counter value, which grows slower than the observation length. The resulting model of H1MMs allows us to combine the best of both worlds: more expressivity with faster parameter fitting.
DPVI: A Dynamic-Weight Particle-Based Variational Inference Framework
Authors: Zhang Chao , Li Zhijian , Du Xin , Qian Hui
Published: July 2022

The recently developed Particle-based Variational Inference (ParVI) methods drive the empirical distribution of a set of fixed-weight particles towards a given target distribution by iteratively updating particles' positions. However, the fixed weight restriction greatly confines the empirical distribution's approximation ability, especially when the particle number is limited. In this paper, we propose to dynamically adjust particles' weights according to a Fisher-Rao reaction flow. We develop a general Dynamic-weight Particle-based Variational Inference (DPVI) framework according to a novel continuous composite flow, which evolves the positions and weights of particles simultaneously. We show that the mean-field limit of our composite flow is actually a Wasserstein-Fisher-Rao gradient flow of the associated dissimilarity functional. By using different finite-particle approximations in our general framework, we derive several efficient DPVI algorithms. The empirical results demonstrate the superiority of our derived DPVI algorithms over their fixed-weight counterparts.
Music-to-Dance Generation with Optimal Transport
Authors: Wu Shuang , Lu Shijian , Cheng Li
Published: July 2022

Dance choreography for a piece of music is a challenging task, having to be creative in presenting distinctive stylistic dance elements while taking into account the musical theme and rhythm. It has been tackled by different approaches such as similarity retrieval, sequence-to-sequence modeling and generative adversarial networks, but their generated dance sequences are often short of motion realism, diversity and music consistency. In this paper, we propose a Music-to-Dance with Optimal Transport Network (MDOT-Net) for learning to generate 3D dance choreographies from music. We introduce an optimal transport distance for evaluating the authenticity of the generated dance distribution and a Gromov-Wasserstein distance to measure the correspondence between the dance distribution and the input music. This gives a well defined and non-divergent training objective that mitigates the limitation of standard GAN training which is frequently plagued with instability and divergent generator loss issues. Extensive experiments demonstrate that our MDOT-Net can synthesize realistic and diverse dances which achieve an organic unity with the input music, reflecting the shared intentionality and matching the rhythmic articulation. Sample results are found at https://www.youtube.com/watch?v=dErfBkrlUO8.
Quantifying Health Inequalities Induced by Data and AI Models
Authors: Wu Honghan , Sylolypavan Aneeta , Wang Minhong , Wild Sarah
Published: July 2022

AI technologies are being increasingly tested and applied in critical environments including healthcare. Without an effective way to detect and mitigate AI induced inequalities, AI might do more harm than good, potentially leading to the widening of underlying inequalities. This paper proposes a generic allocation-deterioration framework for detecting and quantifying AI induced inequality. Specifically, AI induced inequalities are quantified as the area between two allocation-deterioration curves. To assess the framework’s performance, experiments were conducted on ten synthetic datasets (N>33,000) generated from HiRID - a real-world Intensive Care Unit (ICU) dataset, showing its ability to accurately detect and quantify inequality proportionally to controlled inequalities. Extensive analyses were carried out to quantify health inequalities (a) embedded in two real-world ICU datasets; (b) induced by AI models trained for two resource allocation scenarios. Results showed that compared to men, women had up to 33% poorer deterioration in markers of prognosis when admitted to HiRID ICUs. All four AI models assessed were shown to induce significant inequalities (2.45% to 43.2%) for non-White compared to White patients. The models exacerbated data embedded inequalities significantly in 3 out of 8 assessments, one of which was >9 times worse.
Capturing Homomorphism-Closed Decidable Queries with Existential Rules (Extended Abstract)
Authors: Bourgaux Camille , Carral David , Krötzsch Markus , Rudolph Sebastian , Thomazo Michaël
Published: July 2022

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms.

This paper is an extended abstract of our eponymous publication at KR 2021 where we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.
Abstraction for Deep Reinforcement Learning
Authors: Shanahan Murray , Mitchell Melanie
Published: July 2022

We characterise the problem of abstraction in the context of deep reinforcement learning. Various well established approaches to analogical reasoning and associative memory might be brought to bear on this issue, but they present difficulties because of the need for end-to-end differentiability. We review developments in AI and machine learning that could facilitate their adoption.
Data Valuation in Machine Learning: "Ingredients", Strategies, and Open Challenges
Authors: Sim Rachael Hwee Ling , Xu Xinyi , Low Bryan Kian Hsiang
Published: July 2022

Data valuation in machine learning (ML) is an emerging research area that studies the worth of data in ML. Data valuation is used in collaborative ML to determine a fair compensation for every data owner and in interpretable ML to identify the most responsible, noisy, or misleading training examples. This paper presents a comprehensive technical survey that provides a new formal study of data valuation in ML through its “ingredients” and the corresponding properties, grounds the discussion of common desiderata satisfied by existing data valuation strategies on our proposed ingredients, and identifies open research challenges for designing new ingredients, data valuation strategies, and cost reduction techniques.
On the Opportunity of Causal Learning in Recommendation Systems: Foundation, Estimation, Prediction and Challenges
Authors: Wu Peng , Li Haoxuan , Deng Yuhao , Hu Wenjie , Dai Quanyu , Dong Zhenhua , Sun Jie , Zhang Rui , Zhou Xiao-Hua
Published: July 2022

Recently, recommender system (RS) based on causal inference has gained much attention in the industrial community, as well as the states of the art performance in many prediction and debiasing tasks. Nevertheless, a unified causal analysis framework has not been established yet. Many causal-based prediction and debiasing studies rarely discuss the causal interpretation of various biases and the rationality of the corresponding causal assumptions. In this paper, we first provide a formal causal analysis framework to survey and unify the existing causal-inspired recommendation methods, which can accommodate different scenarios in RS. Then we propose a new taxonomy and give formal causal definitions of various biases in RS from the perspective of violating the assumptions adopted in causal analysis. Finally, we formalize many debiasing and prediction tasks in RS, and summarize the statistical and machine learning-based causal estimation methods, expecting to provide new research opportunities and perspectives to the causal RS community.
Manipulating Elections by Changing Voter Perceptions
Authors: Wu Junlin , Estornell Andrew , Kong Lecheng , Vorobeychik Yevgeniy
Published: July 2022

The integrity of elections is central to democratic systems. However, a myriad of malicious actors aspire to influence election outcomes for financial or political benefit. A common means to such ends is by manipulating perceptions of the voting public about select candidates, for example, through misinformation. We present a formal model of the impact of perception manipulation on election outcomes in the framework of spatial voting theory, in which the preferences of voters over candidates are generated based on their relative distance in the space of issues. We show that controlling elections in this model is, in general, NP-hard, whether issues are binary or real-valued. However, we demonstrate that critical to intractability is the diversity of opinions on issues exhibited by the voting public. When voter views lack diversity, and we can instead group them into a small number of categories---for example, as a result of political polarization---the election control problem can be solved in polynomial time in the number of issues and candidates for arbitrary scoring rules.
Fast and Fine-grained Autoscaler for Streaming Jobs with Reinforcement Learning
Authors: Xing Mingzhe , Mao Hangyu , Xiao Zhen
Published: July 2022

On computing clusters, the autoscaler is responsible for allocating resources for jobs or fine-grained tasks to ensure their Quality of Service. Due to a more precise resource management, fine-grained autoscaling can generally achieve better performance. However, the fine-grained autoscaling for streaming jobs needs intensive computation to model the complicated running states of tasks, and has not been adequately studied previously. In this paper, we propose a novel fine-grained autoscaler for streaming jobs based on reinforcement learning. We first organize the running states of streaming jobs as spatio-temporal graphs. To efficiently make autoscaling decisions, we propose a Neural Variational Subgraph Sampler to sample spatio-temporal subgraphs. Furthermore, we propose a mutual-information-based objective function to explicitly guide the sampler to extract more representative subgraphs. After that, the autoscaler makes decisions based on the learned subgraph representations. Experiments conducted on real-world datasets demonstrate the superiority of our method over six competitive baselines.
Towards Contextually Sensitive Analysis of Memes: Meme Genealogy and Knowledge Base
Authors: Sherratt Victoria
Published: July 2022

As online communication grows, memes have continued to evolve and circulate as succinct multimodal forms of communication. However, computational approaches applied to meme-related tasks lack the same depth and contextual sensitivity of non-computational approaches and struggle to interpret intra-modal dynamics and referentiality. This research proposes to a ‘meme genealogy’ of key features and relationships between memes to inform a knowledge base constructed from meme-specific online sources and embed connotative meaning or contextual information in memes. The proposed methods provide a basis to train contextually sensitive computational models for analysing memes and applications in semi-automated meme annotation.
Karakteristik Biodegradable Foam Berbasis Pati Singkong Dengan Variasi Penambahan Tepung Ampas Tebu dan Polyvinyl Alcohol
Authors: Rusdianto Andrew Setiawan , Amilia Winda , Choiron Miftahul , Wiyono Andi Eko , Hidayati Ucik Nurul
Published: July 2022

Biodegradable foam is a type of environmentally friendly packaging made from biopolymers in the form of starch that can be degraded naturally. This study aims to determine the characteristics of biodegradable foam and its prototype made from cassava starch as a biopolymer substitute for synthetic polymers by adding variations of bagasse flour to compact the structure and polyvinyl alcohol (PVA) which functions to reduce water absorption. The stages of making biodegradable foam are started by making bagasse flour, making biodegradable foam sheets using the baking process, and making a prototype bowl of biodegradable foam. The making of this biodegradable foam consists of 6 formulas by adding variations of bagasse flour (5%, 10%, 15%) and PVA (20%, 40%) from 36 grams of starch mass. The tests carried out were in the form of water absorption, biodegradation, thickness, tensile strength, and density tests. The best treatment was found in the A3B1 formula which was used as the basis for making a prototype bowl of biodegradable foam. The addition of variations of bagasse flour and PVA had a significant effect on the characteristics of water absorption and biodegradation, while the other characteristics were only PVA which had a significant effect. The results of the best treatment as the basis for making a prototype bowl of biodegradable foam with water absorption characteristics of 25.93% and biodegradation of 45.95%.
Model Perilaku Keamanan Siber Pada Pengguna Sosial Media Pada Masa Pandemi Covid-19
Authors: Aini Ameilia Nur , Wahyudi Edy , Abdillah Imannurdin
Published: July 2022

The use of social media is very developed during the COVID-19 pandemic, this increases the risk of data leakage, most of which are caused by internal parties from social media users themselves. For that we need an instrument that can measure the behavior of users who are at risk of social media that is used to minimize the potential for such leaks. This research consists of three stages including a literature review on aspects that affect the security of the social media system. The second stage is the preparation of a questionnaire design regarding the risk of cyber attacks on social media. Then the third stage is testing the reliability and validity of the questionnaire. Based on the research, there are 4 aspects that affect the security of social media, namely the use of electronic devices, access to social media, internet behavior, and unusual events in health facilities. The developed questionnaire consists of 27 question items which are divided into these 4 aspects. In the overall validity test the items are valid (r count > r table). While the reliability test of the questionnaire was reliable with Cronbach's Alpha value of 0.867. The developed questionnaire design can be applied to assess the risk of cyber attacks on social media among workers. Further research is needed to implement the questionnaire design
Assessment of the effects of acid rain on the biosphere in Mosul City / Iraq
Authors: Alrawi Ayham T.
Published: July 2022

Acid rain is any precipitation with a very low pH, whereas normal rain water is slightly acidic with a pH range of 5-6, but the pH level of rain water falls below this range, becoming acid rain. It happens as a result of wet and dry deposition from the atmosphere of chemical pollutants emitted by various human activities. Dry deposition is more frequent and effective than wet deposition. It was found that the leading cause of acid rain is the emission of gaseous oxides of sulfur, nitrogen and carbon. These environmental pollutants come from various human activities such as the burning of fossil fuels, combustible waste, vehicle exhausts, thermal power projects, the combustion of vegetation and wastes of wars. These chemical pollutants interact with different precipitation such as; rain, cloud, fog and snow water, which is formed in the case of sulfuric, nitric and carbonic acids, then shows its impact on the lithosphere, water and atmosphere, in addition to its impact on other ecosystems such as; Forests, agricultural crops, soil, buildings and aquatic organisms, as well as human health. The risk of acid rain is controlled by reducing the emissions of gases to neutralize acidity which requires enacting laws and do enforce efforts to reduce pollution and control acid rain on all production projects. Our current study aims to assess the acidity of the rainwater, and it has been proven that the relative pH of the rainwater in the city of Mosul has decreased in the past two years (2020/2021-2021/2022) from (6.5 to 5.8), which requires knowing its causes, effects, and methods to limiting its consequences.