bluuebunny/crossref_metadata_2025 huggingface dataset:
PathLAD+: An Improved Exact Algorithm for Subgraph Isomorphism Problem
Authors: Wang Yiyuan , Jin Chenghou , Cai Shaowei , Lin Qingwei
Published: August 2023

The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers design various algorithms for solving SIP. In this work, we propose three main heuristics and develop an improved exact algorithm for SIP. First, we design a probing search procedure to try whether the search procedure can successfully obtain a solution at first sight. Second, we design a novel matching ordering as a value-ordering heuristic, which uses some useful information obtained from the probing search procedure to preferentially select some promising target vertices. Third, we discuss the characteristics of different propagation methods in the context of SIP and present an adaptive propagation method to make a good balance between these methods. Experimental results on a broad range of real-world benchmarks show that our proposed algorithm performs better than state-of-the-art algorithms for the SIP.
Stability and Generalization of lp-Regularized Stochastic Learning for GCN
Authors: Liu Shiyu , Wei Linsen , Lv Shaogao , Li Ming
Published: August 2023

Graph convolutional networks (GCN) are viewed as one of the most popular representations among the variants of graph neural networks over graph data and have shown powerful performance in empirical experiments. That l2-based graph smoothing enforces the global smoothness of GCN, while (soft) l1-based sparse graph learning tends to promote signal sparsity to trade for discontinuity. This paper aims to quantify the trade-off of GCN between smoothness and sparsity, with the help of a general lp-regularized (1<p<= 2) stochastic learning proposed within. While stability-based generalization analyses have been given in prior work for a second derivative objectiveness function, our lp-regularized learning scheme does not satisfy such a smooth condition. To tackle this issue, we propose a novel SGD proximal algorithm for GCNs with an inexact operator. For a single-layer GCN, we establish an explicit theoretical understanding of GCN with the lp-regularized stochastic learning by analyzing the stability of our SGD proximal algorithm. We conduct multiple empirical experiments to validate our theoretical findings.
The Hardness of Reasoning about Probabilities and Causality
Authors: van der Zander Benito , Bläser Markus , Liśkiewicz Maciej
Published: August 2023

We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective.

We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference.

The main contribution of this work is establishing the exact computational complexity of these satisfiability problems.

We introduce a new natural complexity class, named succ∃R, which can be viewed as a succinct variant of the well-studied class ∃R, and show that these problems are complete for succ∃R.

Our results imply even stronger limitations on the use of algorithmic methods for reasoning about probabilities and causality than previous state-of-the-art results that rely only on the NP- or ∃R-completeness of the satisfiability problems for some restricted languages.
Max Markov Chain
Authors: Zhang Yu , Bucklew Mitchell
Published: August 2023

In this paper, we introduce Max Markov Chain (MMC), a novel model for sequential data with sparse correlations among the state variables.

It may also be viewed as a special class of approximate models for High-order Markov Chains (HMCs).

MMC is desirable for domains where the sparse correlations are long-term and vary in their temporal stretches.

Although generally intractable, parameter optimization for MMC can be solved analytically.

However, based on this result,

we derive an approximate solution that is highly efficient empirically.

When compared with HMC and approximate HMC models, MMC

combines better sample efficiency, model parsimony, and an outstanding computational advantage.

Such a quality allows MMC to scale to large domains

where the competing models would struggle to perform.

We compare MMC with several baselines with synthetic and real-world datasets to demonstrate MMC as a valuable alternative for stochastic modeling.
MMPN: Multi-supervised Mask Protection Network for Pansharpening
Authors: Chen Changjie , Yang Yong , Huang Shuying , Tu Wei , Wan Weiguo , Wei Shengna
Published: August 2023

Pansharpening is to fuse a panchromatic (PAN) image with a multispectral (MS) image to obtain a high-spatial-resolution multispectral (HRMS) image. The deep learning-based pansharpening methods usually apply the convolution operation to extract features and only consider the similarity of gradient information between PAN and HRMS images, resulting in the problems of edge blur and spectral distortion in the fusion results. To solve this problem, a multi-supervised mask protection network (MMPN) is proposed to prevent spatial information from being damaged and overcome spectral distortion in the learning process. Firstly, by analyzing the relationships between high-resolution images and corresponding degraded images, a mask protection strategy (MPS) for edge protection is designed to guide the recovery of fused images. Then, based on the MPS, an MMPN containing four branches is constructed to generate the fusion and mask protection images. In MMPN, each branch employs a dual-stream multi-scale feature fusion module (DMFFM), which is built to extract and fuse the features of two input images. Finally, different loss terms are defined for the four branches, and combined into a joint loss function to realize network training. Experiments on simulated and real satellite datasets show that our method is superior to state-of-the-art methods both subjectively and objectively.
TeSTNeRF: Text-Driven 3D Style Transfer via Cross-Modal Learning
Authors: Chen Jiafu , Ji Boyan , Zhang Zhanjie , Chu Tianyi , Zuo Zhiwen , Zhao Lei , Xing Wei , Lu Dongming
Published: August 2023

Text-driven 3D style transfer aims at stylizing a scene according to the text and generating arbitrary novel views with consistency. Simply combining image/video style transfer methods and novel view synthesis methods results in flickering when changing viewpoints, while existing 3D style transfer methods learn styles from images instead of texts. To address this problem, we for the first time design an efficient text-driven model for 3D style transfer, named TeSTNeRF, to stylize the scene using texts via cross-modal learning: we leverage an advanced text encoder to embed the texts in order to control 3D style transfer and align the input text and output stylized images in latent space. Furthermore, to obtain better visual results, we introduce style supervision, learning feature statistics from style images and utilizing 2D stylization results to rectify abrupt color spill. Extensive experiments demonstrate that TeSTNeRF significantly outperforms existing methods and provides a new way to guide 3D style transfer.
Discrete Diffusion Probabilistic Models for Symbolic Music Generation
Authors: Plasser Matthias , Peter Silvan , Widmer Gerhard
Published: August 2023

Denoising Diffusion Probabilistic Models (DDPMs) have made great strides in generating high-quality samples in both discrete and continuous domains.

However, Discrete DDPMs (D3PMs) have yet to be applied to the domain of Symbolic Music.

This work presents the direct generation of Polyphonic Symbolic Music using D3PMs.

Our model exhibits state-of-the-art sample quality, according to current quantitative evaluation metrics, and allows for flexible infilling at the note level.

We further show, that our models are accessible to post-hoc classifier guidance, widening the scope of possible applications.

However, we also cast a critical view on quantitative evaluation of music sample quality via statistical metrics, and present a simple algorithm that can confound our metrics with completely spurious, non-musical samples.
Learn and Sample Together: Collaborative Generation for Graphic Design Layout
Authors: Weng Haohan , Huang Danqing , Zhang Tong , Lin Chin-Yew
Published: August 2023

In the process of graphic layout generation, user specifications including element attributes and their relationships are commonly used to constrain the layouts (e.g.,"put the image above the button''). It is natural to encode spatial constraints between elements using a graph. This paper presents a two-stage generation framework: a spatial graph generator and a subsequent layout decoder which is conditioned on the previous output graph. Training the two highly dependent networks separately as in previous work, we observe that the graph generator generates out-of-distribution graphs with a high frequency, which are unseen to the layout decoder during training and thus leads to huge performance drop in inference. To coordinate the two networks more effectively, we propose a novel collaborative generation strategy to perform round-way knowledge transfer between the networks in both training and inference. Experiment results on three public datasets show that our model greatly benefits from the collaborative generation and has achieved the state-of-the-art performance. Furthermore, we conduct an in-depth analysis to better understand the effectiveness of graph condition modeling.
HDFormer: High-order Directed Transformer for 3D Human Pose Estimation
Authors: Chen Hanyuan , He Jun-Yan , Xiang Wangmeng , Cheng Zhi-Qi , Liu Wei , Liu Hanbing , Luo Bin , Geng Yifeng , Xie Xuansong
Published: August 2023

Human pose estimation is a challenging task due to its structured data sequence nature. Existing methods primarily focus on pair-wise interaction of body joints, which is insufficient for scenarios involving overlapping joints and rapidly changing poses. To overcome these issues, we introduce a novel approach, the High-order Directed Transformer (HDFormer), which leverages high-order bone and joint relationships for improved pose estimation. Specifically, HDFormer incorporates both self-attention and high-order attention to formulate a multi-order attention module. This module facilitates first-order "joint-joint", second-order "bone-joint", and high-order "hyperbone-joint" interactions, effectively addressing issues in complex and occlusion-heavy situations. In addition, modern CNN techniques are integrated into the transformer-based architecture, balancing the trade-off between performance and efficiency. HDFormer significantly outperforms state-of-the-art (SOTA) models on Human3.6M and MPI-INF-3DHP datasets, requiring only 1/10 of the parameters and significantly lower computational costs. Moreover, HDFormer demonstrates broad real-world applicability, enabling real-time, accurate 3D pose estimation. The source code is in https://github.com/hyer/HDFormer.
DiffuseStyleGesture: Stylized Audio-Driven Co-Speech Gesture Generation with Diffusion Models
Authors: Yang Sicheng , Wu Zhiyong , Li Minglei , Zhang Zhensong , Hao Lei , Bao Weihong , Cheng Ming , Xiao Long
Published: August 2023

The art of communication beyond speech there are gestures. The automatic co-speech gesture generation draws much attention in computer animation. It is a challenging task due to the diversity of gestures and the difficulty of matching the rhythm and semantics of the gesture to the corresponding speech. To address these problems, we present DiffuseStyleGesture, a diffusion model based speech-driven gesture generation approach. It generates high-quality, speech-matched, stylized, and diverse co-speech gestures based on given speeches of arbitrary length. Specifically, we introduce cross-local attention and self-attention to the gesture diffusion pipeline to generate better speech matched and realistic gestures. We then train our model with classifier-free guidance to control the gesture style by interpolation or extrapolation. Additionally, we improve the diversity of generated gestures with different initial gestures and noise. Extensive experiments show that our method outperforms recent approaches on speech-driven gesture generation. Our code, pre-trained models, and demos are available at https://github.com/YoungSeng/DiffuseStyleGesture.
Fairness and Representation in Satellite-Based Poverty Maps: Evidence of Urban-Rural Disparities and Their Impacts on Downstream Policy
Authors: Aiken Emily , Rolf Esther , Blumenstock Joshua
Published: August 2023

Poverty maps derived from satellite imagery are increasingly used to inform high-stakes policy decisions, such as the allocation of humanitarian aid and the distribution of government resources. Such poverty maps are typically constructed by training machine learning algorithms on a relatively modest amount of ``ground truth" data from surveys, and then predicting poverty levels in areas where imagery exists but surveys do not. Using survey and satellite data from ten countries, this paper investigates disparities in representation, systematic biases in prediction errors, and fairness concerns in satellite-based poverty mapping across urban and rural lines, and shows how these phenomena affect the validity of policies based on predicted maps. Our findings highlight the importance of careful error and bias analysis before using satellite-based poverty maps in real-world policy decisions.
Disentangling Societal Inequality from Model Biases: Gender Inequality in Divorce Court Proceedings
Authors: Dutta Sujan , Srivastava Parth , Solunke Vaishnavi , Nath Swaprava , KhudaBukhsh Ashiqur R.
Published: August 2023

Divorce is the legal dissolution of a marriage by a court. Since this is usually an unpleasant outcome of a marital union, each party may have reasons to call the decision to quit which is generally documented in detail in the court proceedings. Via a substantial corpus of 17,306 court proceedings, this paper investigates gender inequality through the lens of divorce court proceedings. To our knowledge, this is the first-ever large-scale computational analysis of gender inequality in Indian divorce, a taboo-topic for ages. While emerging data sources (e.g., public court records made available on the web) on sensitive societal issues hold promise in aiding social science research, biases present in cutting-edge natural language processing (NLP) methods may interfere with or affect such studies. A thorough analysis of potential gaps and limitations present in extant NLP resources is thus of paramount importance. In this paper, on the methodological side, we demonstrate that existing NLP resources required several non-trivial modifications to quantify societal inequalities. On the substantive side, we find that while a large number of court cases perhaps suggest changing norms in India where women are increasingly challenging patriarchy, AI-powered analyses of these court proceedings indicate striking gender inequality with women often subjected to domestic violence.
Machine Learning Driven Aid Classification for Sustainable Development
Authors: Lee Junho , Song Hyeonho , Lee Dongjoon , Kim Sundong , Sim Jisoo , Cha Meeyoung , Park Kyung-Ryul
Published: August 2023

This paper explores how machine learning can help classify aid activities by sector using the OECD Creditor Reporting System (CRS). The CRS is a key source of data for monitoring and evaluating aid flows in line with the United Nations Sustainable Development Goals (SDGs), especially SDG17 which calls for global partnership and data sharing. To address the challenges of current labor-intensive practices of assigning the code and the related human inefficiencies, we propose a machine learning solution that uses ELECTRA to suggest relevant five-digit purpose codes in CRS for aid activities, achieving an accuracy of 0.9575 for the top-3 recommendations. We also conduct qualitative research based on semi-structured interviews and focus group discussions with SDG experts who assess the model results and provide feedback. We discuss the policy, practical, and methodological implications of our work and highlight the potential of AI applications to improve routine tasks in the public sector and foster partnerships for achieving the SDGs.
Interpret ESG Rating’s Impact on the Industrial Chain Using Graph Neural Networks
Authors: Liu Bin , He Jiujun , Li Ziyuan , Huang Xiaoyang , Zhang Xiang , Yin Guosheng
Published: August 2023

We conduct a quantitative analysis of the development of the industry chain from the environmental, social, and governance (ESG) perspective, which is an overall measure of sustainability. Factors that may impact the performance of the industrial chain have been studied in the literature, such as government regulation, monetary policy, etc. Our interest lies in how the sustainability change (i.e., ESG shock) affects the performance of the industrial chain. To achieve this goal, we model the industrial chain with a graph neural network (GNN) and conduct node regression on two financial performance metrics, namely, the aggregated profitability ratios and operating margin. To quantify the effects of ESG, we propose to compute the interaction between ESG shocks and industrial chain features with a cross-attention module, and then filter the original node features in the graph regression. Experiments on two real datasets demonstrate that (i) there are significant effects of ESG shocks on the industrial chain, and (ii) model parameters including regression coefficients and the attention map can explain how ESG shocks affect the performance of the industrial chain.
Coupled Point Process-based Sequence Modeling for Privacy-preserving Network Alignment
Authors: Luo Dixin , Cheng Haoran , Li Qingbin , Xu Hongteng
Published: August 2023

Network alignment aims at finding the correspondence of nodes across different networks, which is significant for many applications, e.g., fraud detection and crime network tracing across platforms.

In practice, however, accessing the topological information of different networks is often restricted and even forbidden, considering privacy and security issues.

Instead, what we observed might be the event sequences of the networks' nodes in the continuous-time domain.

In this study, we develop a coupled neural point process-based (CPP) sequence modeling strategy, which provides a solution to privacy-preserving network alignment based on the event sequences.

Our CPP consists of a coupled node embedding layer and a neural point process module.

The coupled node embedding layer embeds one network's nodes and explicitly models the alignment matrix between the two networks.

Accordingly, it parameterizes the node embeddings of the other network by the push-forward operation.

Given the node embeddings, the neural point process module jointly captures the dynamics of the two networks' event sequences.

We learn the CPP model in a maximum likelihood estimation framework with an inverse optimal transport (IOT) regularizer.

Experiments show that our CPP is compatible with various point process backbones and is robust to the model misspecification issue, which achieves encouraging performance on network alignment.

The code is available at https://github.com/Dixin-s-Lab/CNPP.
Group Sparse Optimal Transport for Sparse Process Flexibility Design
Authors: Luo Dixin , Yu Tingting , Xu Hongteng
Published: August 2023

As a fundamental problem in Operations Research, sparse process flexibility design (SPFD) aims to design a manufacturing network across industries that achieves a trade-off between the efficiency and robustness of supply chains.

In this study, we propose a novel solution to this problem with the help of computational optimal transport techniques.

Given a set of supply-demand pairs, we formulate the SPFD task approximately as a group sparse optimal transport (GSOT) problem, in which a group of couplings between the supplies and demands is optimized with a group sparse regularizer.

We solve this optimization problem via an algorithmic framework of alternating direction method of multipliers (ADMM), in which the target network topology is updated by soft-thresholding shrinkage, and the couplings of the OT problems are updated via a smooth OT algorithm in parallel.

This optimization algorithm has guaranteed convergence and provides a generalized framework for the SPFD task, which is applicable regardless of whether the supplies and demands are balanced.

Experiments show that our GSOT-based method can outperform representative heuristic methods in various SPFD tasks.

Additionally, when implementing the GSOT method, the proposed ADMM-based optimization algorithm is comparable or superior to the commercial software Gurobi.

The code is available at https://github.com/Dixin-s-Lab/GSOT.
Fighting against Organized Fraudsters Using Risk Diffusion-based Parallel Graph Neural Network
Authors: Ma Jiacheng , Li Fan , Zhang Rui , Xu Zhikang , Cheng Dawei , Ouyang Yi , Zhao Ruihui , Zheng Jianguang , Zheng Yefeng , Jiang Changjun
Published: August 2023

Medical insurance plays a vital role in modern society, yet organized healthcare fraud causes billions of dollars in annual losses, severely harming the sustainability of the social welfare system. Existing works mostly focus on detecting individual fraud entities or claims, ignoring hidden conspiracy patterns. Hence, they face severe challenges in tackling organized fraud. In this paper, we proposed RDPGL, a novel Risk Diffusion-based Parallel Graph Learning approach, to fighting against medical insurance criminal gangs. In particular, we first leverage a heterogeneous graph attention network to encode the local context from the beneficiary-provider graph. Then, we devise a community-aware risk diffusion model to infer the global context of organized fraud behaviors with the claim-claim relation graph. The local and global representations are parallel concatenated together and trained simultaneously in an end-to-end manner. Our approach is extensively evaluated on a real-world medical insurance dataset. The experimental results demonstrate the superiority of our proposed approach, which could detect more organized fraud claims with relatively high precision compared with state-of-the-art baselines.
Balancing Social Impact, Opportunities, and Ethical Constraints of Using AI in the Documentation and Vitalization of Indigenous Languages
Authors: Pinhanez Claudio S. , Cavalin Paulo , Vasconcelos Marisa , Nogima Julio
Published: August 2023

In this paper we discuss how AI can contribute to support the documentation and vitalization of Indigenous languages and how that involves a delicate balancing of ensuring social impact, exploring technical opportunities, and dealing with ethical constraints. We start by surveying previous work on using AI and NLP to support critical activities of strengthening Indigenous and endangered languages and discussing key limitations of current technologies. After presenting basic ethical constraints of working with Indigenous languages and communities, we propose that creating and deploying language technology ethically with and for Indigenous communities forces AI researchers and engineers to address some of the main shortcomings and criticisms of current technologies. Those ideas are also explored in the discussion of a real case of development of large language models for Brazilian Indigenous languages.
Evaluating GPT-3 Generated Explanations for Hateful Content Moderation
Authors: Wang Han , Hee Ming Shan , Awal Md Rabiul , Choo Kenny Tsu Wei , Lee Roy Ka-Wei
Published: August 2023

Recent research has focused on using large language models (LLMs) to generate explanations for hate speech through fine-tuning or prompting. Despite the growing interest in this area, these generated explanations' effectiveness and potential limitations remain poorly understood. A key concern is that these explanations, generated by LLMs, may lead to erroneous judgments about the nature of flagged content by both users and content moderators. For instance, an LLM-generated explanation might inaccurately convince a content moderator that a benign piece of content is hateful. In light of this, we propose an analytical framework for examining hate speech explanations and conducted an extensive survey on evaluating such explanations. Specifically, we prompted GPT-3 to generate explanations for both hateful and non-hateful content, and a survey was conducted with 2,400 unique respondents to evaluate the generated explanations. Our findings reveal that (1) human evaluators rated the GPT-generated explanations as high quality in terms of linguistic fluency, informativeness, persuasiveness, and logical soundness, (2) the persuasive nature of these explanations, however, varied depending on the prompting strategy employed, and (3) this persuasiveness may result in incorrect judgments about the hatefulness of the content. Our study underscores the need for caution in applying LLM-generated explanations for content moderation. Code and results are available at https://github.com/Social-AI-Studio/GPT3-HateEval.
Explainable Multi-Agent Reinforcement Learning for Temporal Queries
Authors: Boggess Kayla , Kraus Sarit , Feng Lu
Published: August 2023

As multi-agent reinforcement learning (MARL) systems are increasingly deployed throughout society, it is imperative yet challenging for users to understand the emergent behaviors of MARL agents in complex environments. This work presents an approach for generating policy-level contrastive explanations for MARL to answer a temporal user query, which specifies a sequence of tasks completed by agents with possible cooperation. The proposed approach encodes the temporal query as a PCTL* logic formula and checks if the query is feasible under a given MARL policy via probabilistic model checking. Such explanations can help reconcile discrepancies between the actual and anticipated multi-agent behaviors. The proposed approach also generates correct and complete explanations to pinpoint reasons that make a user query infeasible. We have successfully applied the proposed approach to four benchmark MARL domains (up to 9 agents in one domain). Moreover, the results of a user study show that the generated explanations significantly improve user performance and satisfaction.
User-Centric Democratization towards Social Value Aligned Medical AI Services
Authors: Zhang Zhaonian , Jiang Richard
Published: August 2023

Democratic AI, aiming at developing AI systems aligned with human values, holds promise for making AI services accessible to people. However, concerns have been raised regarding the participation of non-technical individuals, potentially undermining the carefully designed values of AI systems by experts. In this paper, we investigate Democratic AI, define it mathematically, and propose a user-centric evolutionary democratic AI (u-DemAI) framework. This framework maximizes the social values of cloud-based AI services by incorporating user feedback and emulating human behavior in a community via a user-in-the-loop iteration. We apply our framework to a medical AI service for brain age estimation and demonstrate that non-expert users can consistently contribute to improving AI systems through a natural democratic process. The u-DemAI framework presents a mathematical interpretation of Democracy for AI, conceptualizing it as a natural computing process. Our experiments successfully show that involving non-tech individuals can help improve performance and simultaneously mitigate bias in AI models developed by AI experts, showcasing the potential for Democratic AI to benefit end users and regain control over AI services that shape various aspects of our lives, including our health.
AI and Decision Support for Sustainable Socio-Ecosystems
Authors: Justeau-Allaire Dimitri
Published: August 2023

The conservation and the restoration of biodiversity, in accordance with human well-being, is a necessary condition for the realization of several Sustainable Development Goals. However, there is still an important gap between biodiversity research and the management of natural areas. This research project aims to reduce this gap by proposing spatial planning methods that robustly and accurately integrate socio-ecological issues. Artificial intelligence, and notably Constraint Programming, will play a central role and will make it possible to remove the methodological obstacles that prevent us from properly addressing the complexity and heterogeneity of sustainability issues in the management of ecosystems. The whole will be articulated in three axes: (i) integrate socio-ecological dynamics into spatial planning, (ii) rely on adequate landscape metrics in spatial planning, (iii) scaling up spatial planning methods performances. The main study context of this project is the sustainable management of tropical forests, with a particular focus on New Caledonia and West Africa.
Online Certification of Preference-Based Fairness for Personalized Recommender Systems (Extended Abstract)
Authors: Do Virginie , Corbett-Davies Sam , Atif Jamal , Usunier Nicolas
Published: August 2023

Recommender systems are facing scrutiny because of their growing impact on the opportunities we have access to. Current audits for fairness are limited to coarse-grained parity assessments at the level of sensitive groups. We propose to audit for envy-freeness, a more granular criterion aligned with individual preferences: every user should prefer their recommendations to those of other users. Since auditing for envy requires to estimate the preferences of users beyond their existing recommendations, we cast the audit as a new pure exploration problem in multi-armed bandits. We propose a sample-efficient algorithm with theoretical guarantees that it does not deteriorate user experience. We also study the trade-offs achieved on real-world recommendation datasets.
FastGR: Global Routing on CPU-GPU with Heterogeneous Task Graph Scheduler (Extended Abstract)
Authors: Liu Siting , Pu Yuan , Liao Peiyu , Wu Hongzhong , Zhang Rui , Chen Zhitang , Lv Wenlong , Lin Yibo , Yu Bei
Published: August 2023

Running time is a key metric across the standard physical design flow stages. However, with the rapid growth in design sizes, routing runtime has become the runtime bottleneck in the physical design flow. To improve the effectiveness of the modern global router, we propose a global routing framework with GPU-accelerated routing algorithms and a heterogeneous task graph scheduler, called FastGR. Its runtime-oriented version FastGRL achieves 2.489× speedup compared with the state-of-the-art global router. Furthermore, the GPU-accelerated L-shape pattern routing used in FastGRL can contribute to 9.324× speedup over the sequential algorithm on CPU. Its quality-oriented version FastGRH offers further quality improvement over FastGRL with similar acceleration.
Bounding the Family-Wise Error Rate in Local Causal Discovery Using Rademacher Averages (Extended Abstract)
Authors: Simionato Dario , Vandin Fabio
Published: August 2023

Causal discovery from observational data provides candidate causal relationships that need to be validated with ad-hoc experiments. Such experiments usually require major resources, and suitable techniques should therefore be applied to identify candidate relations while limiting false positives.

Local causal discovery provides a detailed overview of the variables influencing a target, and it focuses on two sets of variables. The first one, the Parent-Children set, comprises all the elements that are direct causes of the target or that are its direct consequences, while the second one, called the Markov boundary, is the minimal set of variables for the optimal prediction of the target.

In this paper we present RAveL, the first suite of algorithms for local causal discovery providing rigorous guarantees on false discoveries. Our algorithms exploit Rademacher averages, a key concept in statistical learning theory, to account for the multiple-hypothesis testing problem in high-dimensional scenarios. Moreover, we prove that state-of-the-art approaches cannot be adapted for the task due to their strong and untestable assumptions, and we complement our analyses with extensive experiments, on synthetic and real-world data.
Efficient Global Robustness Certification of Neural Networks via Interleaving Twin-Network Encoding (Extended Abstract)
Authors: Wang Zhilu , Huang Chao , Zhu Qi
Published: August 2023

The robustness of deep neural networks in safety-critical systems has received significant interest recently, which measures how sensitive the model output is under input perturbations. While most previous works focused on the local robustness property, the studies of the global robustness property, i.e., the robustness in the entire input space, are still lacking. In this work, we formulate the global robustness certification problem for ReLU neural networks and present an efficient approach to address it. Our approach includes a novel interleaving twin-network encoding scheme and an over-approximation algorithm leveraging relaxation and refinement techniques. Its timing efficiency and effectiveness are evaluated and compared with other state-of-the-art global robustness certification methods, and demonstrated via case studies on practical applications.
Temporal Knowledge Graph Completion: A Survey
Authors: Cai Borui , Xiang Yong , Gao Longxiang , Zhang He , Li Yunfeng , Li Jianxin
Published: August 2023

Knowledge graph completion (KGC) predicts missing links and is crucial for real-life knowledge graphs, which widely suffer from incompleteness.

KGC methods assume a knowledge graph is static, but that may lead to inaccurate prediction results because many facts in the knowledge graphs change over time.

Emerging methods have recently shown improved prediction results by further incorporating the temporal validity of facts; namely, temporal knowledge graph completion (TKGC).

With this temporal information, TKGC methods explicitly learn the dynamic evolution of the knowledge graph that KGC methods fail to capture.

In this paper, for the first time, we comprehensively summarize the recent advances in TKGC research.

First, we detail the background of TKGC, including the preliminary knowledge, benchmark datasets, and evaluation metrics.

Then, we summarize existing TKGC methods based on how the temporal validity of facts is used to capture the temporal dynamics.

Finally, we conclude the paper and present future research directions of TKGC.
Generalizing to Unseen Elements: A Survey on Knowledge Extrapolation for Knowledge Graphs
Authors: Chen Mingyang , Zhang Wen , Geng Yuxia , Xu Zezhong , Z. Pan Jeff , Chen Huajun
Published: August 2023

Knowledge graphs (KGs) have become valuable knowledge resources in various applications, and knowledge graph embedding (KGE) methods have garnered increasing attention in recent years. However, conventional KGE methods still face challenges when it comes to handling unseen entities or relations during model testing. To address this issue, much effort has been devoted to various fields of KGs. In this paper, we use a set of general terminologies to unify these methods and refer to them collectively as Knowledge Extrapolation. We comprehensively summarize these methods, classified by our proposed taxonomy, and describe their interrelationships. Additionally, we introduce benchmarks and provide comparisons of these methods based on aspects that are not captured by the taxonomy. Finally, we suggest potential directions for future research.
Game-theoretic Mechanisms for Eliciting Accurate Information
Authors: Faltings Boi
Published: August 2023

Artificial Intelligence often relies on information obtained from others through crowdsourcing, federated learning, or data markets. It is crucial to ensure that this data is accurate. Over the past 20 years, a variety of incentive mechanisms have been developed that use game theory to reward the accuracy of contributed data. These techniques are applicable to many settings where AI uses contributed data.

This survey categorizes the different techniques and their properties, and shows their limits and tradeoffs. It identifies open issues and points to possible directions to address these.
A Survey on Dataset Distillation: Approaches, Applications and Future Directions
Authors: Geng Jiahui , Chen Zongxiong , Wang Yuandou , Woisetschlaeger Herbert , Schimmler Sonja , Mayer Ruben , Zhao Zhiming , Rong Chunming
Published: August 2023

Dataset distillation is attracting more attention in machine learning as training sets continue to grow and the cost of training state-of-the-art models becomes increasingly high. By synthesizing datasets with high information density, dataset distillation offers a range of potential applications, including support for continual learning, neural architecture search, and privacy protection. Despite recent advances, we lack a holistic understanding of the approaches and applications. Our survey aims to bridge this gap by first proposing a taxonomy of dataset distillation, characterizing existing approaches, and then systematically reviewing the data modalities, and related applications. In addition, we summarize the challenges and discuss future directions for this field of research.
Graph-based Molecular Representation Learning
Authors: Guo Zhichun , Guo Kehan , Nan Bozhao , Tian Yijun , Iyer Roshni G. , Ma Yihong , Wiest Olaf , Zhang Xiangliang , Wang Wei , Zhang Chuxu , Chawla Nitesh V.
Published: August 2023

Molecular representation learning (MRL) is a key step to build the connection between machine learning and chemical science. In particular, it encodes molecules as numerical vectors preserving the molecular structures and features, on top of which the downstream tasks (e.g., property prediction) can be performed. Recently, MRL has achieved considerable progress, especially in methods based on deep molecular graph learning. In this survey, we systematically review these graph-based molecular representation techniques, especially the methods incorporating chemical domain knowledge. Specifically, we first introduce the features of 2D and 3D molecular graphs. Then we summarize and categorize MRL methods into three groups based on their input. Furthermore, we discuss some typical chemical applications supported by MRL. To facilitate studies in this fast-developing area, we also list the benchmarks and commonly used datasets in the paper. Finally, we share our thoughts on future research directions.
Curriculum Graph Machine Learning: A Survey
Authors: Li Haoyang , Wang Xin , Zhu Wenwu
Published: August 2023

Graph machine learning has been extensively studied in both academia and industry. However, in the literature, most existing graph machine learning models are designed to conduct training with data samples in a random order, which may suffer from suboptimal performance due to ignoring the importance of different graph data samples and their training orders for the model optimization status. To tackle this critical problem, curriculum graph machine learning (Graph CL), which integrates the strength of graph machine learning and curriculum learning, arises and attracts an increasing amount of attention from the research community. Therefore, in this paper, we comprehensively overview approaches on Graph CL and present a detailed survey of recent advances in this direction. Specifically, we first discuss the key challenges of Graph CL and provide its formal problem definition. Then, we categorize and summarize existing methods into three classes based on three kinds of graph machine learning tasks, i.e., node-level, link-level, and graph-level tasks. Finally, we share our thoughts on future research directions. To the best of our knowledge, this paper is the first survey for curriculum graph machine learning.
Diffusion Models for Non-autoregressive Text Generation: A Survey
Authors: Li Yifan , Zhou Kun , Zhao Wayne Xin , Wen Ji-Rong
Published: August 2023

Non-autoregressive (NAR) text generation has attracted much attention in the field of natural language processing, which greatly reduces the inference latency but has to sacrifice the generation accuracy. Recently, diffusion models, a class of latent variable generative models, have been introduced into NAR text generation, showing an improved text generation quality. In this survey, we review the recent progress in diffusion models for NAR text generation. As the background, we first present the general definition of diffusion models and the text diffusion models, and then discuss their merits for NAR generation. As the core content, we further introduce two mainstream diffusion models in existing work of text diffusion, and review the key designs of the diffusion process. Moreover, we discuss the utilization of pre-trained language models (PLMs) for text diffusion models and introduce optimization techniques for text data. Finally, we discuss several promising directions and conclude this paper. Our survey aims to provide researchers with a systematic reference of related research on text diffusion models for NAR generation. We also demonstrate our collection of text diffusion models at https://github.com/RUCAIBox/Awesome-Text-Diffusion-Models.
Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities
Authors: Salzman Oren , Felner Ariel , Hernández Carlos , Zhang Han , Chan Shao-Hung , Koenig Sven
Published: August 2023

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970's. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the sub-field of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.
State-wise Safe Reinforcement Learning: A Survey
Authors: Zhao Weiye , He Tairan , Chen Rui , Wei Tianhao , Liu Changliu
Published: August 2023

Despite the tremendous success of Reinforcement Learning (RL) algorithms in simulation environments, applying RL to real-world applications still faces many challenges. A major concern is safety, in another word, constraint satisfaction. State-wise constraints are one of the most common constraints in real-world applications and one of the most challenging constraints in Safe RL. Enforcing state-wise constraints is necessary and essential to many challenging tasks such as autonomous driving, robot manipulation. This paper provides a comprehensive review of existing approaches that address state-wise constraints in RL. Under the framework of State-wise Constrained Markov Decision Process (SCMDP), we will discuss the connections, differences, and trade-offs of existing approaches in terms of (i) safety guarantee and scalability, (ii) safety and reward performance, and (iii) safety after convergence and during training. We also summarize limitations of current methods and discuss potential future directions.
Timestamp-Supervised Action Segmentation from the Perspective of Clustering
Authors: Du Dazhao , Li Enhan , Si Lingyu , Xu Fanjiang , Sun Fuchun
Published: August 2023

Video action segmentation under timestamp supervision has recently received much attention due to lower annotation costs. Most existing methods generate pseudo-labels for all frames in each video to train the segmentation model. However, these methods suffer from incorrect pseudo-labels, especially for the semantically unclear frames in the transition region between two consecutive actions, which we call ambiguous intervals. To address this issue, we propose a novel framework from the perspective of clustering, which includes the following two parts. First, pseudo-label ensembling generates incomplete but high-quality pseudo-label sequences, where the frames in ambiguous intervals have no pseudo-labels. Second, iterative clustering iteratively propagates the pseudo-labels to the ambiguous intervals by clustering, and thus updates the pseudo-label sequences to train the model. We further introduce a clustering loss, which encourages the features of frames within the same action segment more compact. Extensive experiments show the effectiveness of our method.
Optimizing the Computation of Overriding in DLN (Extended Abstract)
Authors: Bonatti Piero A. , Petrova Iliana , Sauro Luigi
Published: August 2023

One of the factors that hinder the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. The family of nonmonotonic logics DLN is no exception to this behavior.

We address this issue by introducing two provably correct and complete optimizations for reasoning in DLN. The first optimization is a module extractor that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The second, called optimistic evaluation, aims at exploiting incremental reasoning in a better way.

Extensive experimental evaluation shows that the optimized DLN reasoning is often compatible with interactive query answering, thus bringing nonmonotonic description logics closer to practical applications.
Interpretable Local Concept-based Explanation with Human Feedback to Predict All-cause Mortality (Extended Abstract)
Authors: El Shawi Radwa , Al-Mallah Mouaz
Published: August 2023

Machine learning models are incorporated in different fields and disciplines, some of which require high accountability and transparency, for example, the healthcare sector. A widely used category of explanation techniques attempts to explain models' predictions by quantifying the importance score of each input feature. However, summarizing such scores to provide human-interpretable explanations is challenging. Another category of explanation techniques focuses on learning a domain representation in terms of high-level human-understandable concepts and then utilizing them to explain predictions. These explanations are hampered by how concepts are constructed, which is not intrinsically interpretable. To this end, we propose Concept-based Local Explanations with Feedback (CLEF), a novel local model agnostic explanation framework for learning a set of high-level transparent concept definitions in high-dimensional tabular data that uses clinician-labeled concepts rather than raw features.