bluuebunny/crossref_metadata_2025 huggingface dataset:
Self-Supervised Graph Neural Networks via Diverse and Interactive Message Passing
Authors: Yang Liang , Chen Cheng , Li Weixun , Niu Bingxin , Gu Junhua , Wang Chuan , He Dongxiao , Guo Yuanfang , Cao Xiaochun
Published: July 2022

By interpreting Graph Neural Networks (GNNs) as the message passing from the spatial perspective, their success is attributed to Laplacian smoothing. However, it also leads to serious over-smoothing issue by stacking many layers. Recently, many efforts have been paid to overcome this issue in semi-supervised learning. Unfortunately, it is more serious in unsupervised node representation learning task due to the lack of supervision information. Thus, most of the unsupervised or self-supervised GNNs often employ \textit{one-layer GCN} as the encoder. Essentially, the over-smoothing issue is caused by the over-simplification of the existing message passing, which possesses two intrinsic limits: blind message and uniform passing. In this paper, a novel Diverse and Interactive Message Passing (DIMP) is proposed for self-supervised learning by overcoming these limits. Firstly, to prevent the message from blindness and make it interactive between two connected nodes, the message is determined by both the two connected nodes instead of the attributes of one node. Secondly, to prevent the passing from uniformness and make it diverse over different attribute channels, different propagation weights are assigned to different elements in the message. To this end, a natural implementation of the message in DIMP is the element-wise product of the representations of two connected nodes. From the perspective of numerical optimization, the proposed DIMP is equivalent to performing an overlapping community detection via expectation-maximization (EM). Both the objective function of the community detection and the convergence of EM algorithm guarantee that DMIP can prevent from over-smoothing issue. Extensive evaluations on node-level and graph-level tasks demonstrate the superiority of DIMP on improving performance and overcoming over-smoothing issue.
Multi-View Intent Disentangle Graph Networks for Bundle Recommendation
Authors: Zhao Sen , Wei Wei , Zou Ding , Mao Xianling
Published: July 2022

Bundle recommendation aims to recommend the user a bundle of items as a whole. Previous models capture user’s preferences on both items and the association of items. Nevertheless, they usually neglect the diversity of user’s intents on adopting items and fail to disentangle user’s intents in representations. In the real scenario of bundle recommendation, a user’s intent may be naturally distributed in the different bundles of that user (Global view). And a bundle may contain multiple intents of a user (Local view). Each view has its advantages for intent disentangling: 1) In the global view, more items are involved to present each intent, which can demonstrate the user’s preference under each intent more clearly. 2) The local view can reveal the association between items under each intent since the items within the same bundle are highly correlated to each other. To this end, in this paper we propose a novel model named Multi-view Intent Disentangle Graph Networks (MIDGN), which is capable of precisely and comprehensively capturing the diversity of user intent and items’ associations at the finer granularity. Specifically, MIDGN disentangles user’s intents from two different perspectives, respectively: 1) taking the Global view, MIDGN disentangles the user’s intent coupled with inter-bundle items; 2) taking the Local view, MIDGN disentangles the user’s intent coupled with items within each bundle. Meanwhile, we compare user’s intents disentangled from different views by a contrast method to improve the learned intents. Extensive experiments are conducted on two benchmark datasets and MIDGN outperforms the state-of-the-art methods by over 10.7% and 26.8%, respectively.
Diaformer: Automatic Diagnosis via Symptoms Sequence Generation
Authors: Chen Junying , Li Dongfang , Chen Qingcai , Zhou Wenxiu , Liu Xin
Published: July 2022

Automatic diagnosis has attracted increasing attention but remains challenging due to multi-step reasoning. Recent works usually address it by reinforcement learning methods. However, these methods show low efficiency and require task-specific reward functions. Considering the conversation between doctor and patient allows doctors to probe for symptoms and make diagnoses, the diagnosis process can be naturally seen as the generation of a sequence including symptoms and diagnoses. Inspired by this, we reformulate automatic diagnosis as a symptoms Sequence Generation (SG) task and propose a simple but effective automatic Diagnosis model based on Transformer (Diaformer). We firstly design the symptom attention framework to learn the generation of symptom inquiry and the disease diagnosis. To alleviate the discrepancy between sequential generation and disorder of implicit symptoms, we further design three orderless training mechanisms. Experiments on three public datasets show that our model outperforms baselines on disease diagnosis by 1%, 6% and 11.5% with the highest training efficiency. Detailed analysis on symptom inquiry prediction demonstrates that the potential of applying symptoms sequence generation for automatic diagnosis.
FactorVAE: A Probabilistic Dynamic Factor Model Based on Variational Autoencoder for Predicting Cross-Sectional Stock Returns
Authors: Duan Yitong , Wang Lei , Zhang Qizhong , Li Jian
Published: July 2022

As an asset pricing model in economics and finance, factor model has been widely used in quantitative investment. Towards building more effective factor models, recent years have witnessed the paradigm shift from linear models to more flexible nonlinear data-driven machine learning models. However, due to low signal-to-noise ratio of the financial data, it is quite challenging to learn effective factor models. In this paper, we propose a novel factor model, FactorVAE, as a probabilistic model with inherent randomness for noise modeling. Essentially, our model integrates the dynamic factor model (DFM) with the variational autoencoder (VAE) in machine learning, and we propose a prior-posterior learning method based on VAE, which can effectively guide the learning of model by approximating an optimal posterior factor model with future information. Particularly, considering that risk modeling is important for the noisy stock data, FactorVAE can estimate the variances from the distribution over the latent space of VAE, in addition to predicting returns. The experiments on the real stock market data demonstrate the effectiveness of FactorVAE, which outperforms various baseline methods.
SCIR-Net: Structured Color Image Representation Based 3D Object Detection Network from Point Clouds
Authors: He Qingdong , Zeng Hao , Zeng Yi , Liu Yijun
Published: July 2022

3D object detection from point clouds data has become an indispensable part in autonomous driving. Previous works for processing point clouds lie in either projection or voxelization. However, projection-based methods suffer from information loss while voxelization-based methods bring huge computation. In this paper, we propose to encode point clouds into structured color image representation (SCIR) and utilize 2D CNN to fulfill the 3D detection task. Specifically, we use the structured color image encoding module to convert the irregular 3D point clouds into a squared 2D tensor image, where each point corresponds to a spatial point in the 3D space. Furthermore, in order to fit for the Euclidean structure, we apply feature normalization to parameterize the 2D tensor image onto a regular dense color image. Then, we conduct repeated multi-scale fusion with different levels so as to augment the initial features and learn scale-aware feature representations for box prediction. Extensive experiments on KITTI benchmark, Waymo Open Dataset and more challenging nuScenes dataset show that our proposed method yields decent results and demonstrate the effectiveness of such representations for point clouds.
Solving PDE-Constrained Control Problems Using Operator Learning
Authors: Hwang Rakhoon , Lee Jae Yong , Shin Jin Young , Hwang Hyung Ju
Published: July 2022

The modeling and control of complex physical systems are essential in real-world problems. We propose a novel framework that is generally applicable to solving PDE-constrained optimal control problems by introducing surrogate models for PDE solution operators with special regularizers. The procedure of the proposed framework is divided into two phases: solution operator learning for PDE constraints (Phase 1) and searching for optimal control (Phase 2). Once the surrogate model is trained in Phase 1, the optimal control can be inferred in Phase 2 without intensive computations. Our framework can be applied to both data-driven and data-free cases. We demonstrate the successful application of our method to various optimal control problems for different control variables with diverse PDE constraints from the Poisson equation to Burgers' equation.
Contact-Distil: Boosting Low Homologous Protein Contact Map Prediction by Self-Supervised Distillation
Authors: Wang Qin , Chen Jiayang , Zhou Yuzhe , Li Yu , Zheng Liangzhen , Wang Sheng , Li Zhen , Cui Shuguang
Published: July 2022

Accurate protein contact map prediction (PCMP) is essential for precise protein structure estimation and further biological studies. Recent works achieve significant performance on this task with high quality multiple sequence alignment (MSA). However, the PCMP accuracy drops dramatically while only poor MSA (e.g., absolute MSA count less than 10) is available. Therefore, in this paper, we propose the Contact-Distil to improve the low homologous PCMP accuracy through knowledge distillation on a self-supervised model. Particularly, two pre-trained transformers are exploited to learn the high quality and low quality MSA representation in parallel for the teacher and student model correspondingly. Besides, the co-evolution information is further extracted from pure sequence through a pretrained ESM-1b model, which provides auxiliary knowledge to improve student performance. Extensive experiments show Contact-Distil outperforms previous state-of-the-arts by large margins on CAMEO-L dataset for low homologous PCMP, i.e., around 13.3% and 9.5% improvements against Alphafold2 and MSA Transformer respectively when MSA count less than 10.
Almost Full EFX Exists for Four Agents
Authors: Berger Ben , Cohen Avi , Feldman Michal , Fiat Amos
Published: July 2022

The existence of EFX allocations of goods is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. It is also known that EFX exists if one can leave n-1 items unallocated, where n is the number of agents.

We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.
Individual Representation in Approval-Based Committee Voting
Authors: Brill Markus , Israel Jonas , Micha Evi , Peters Jannik
Published: July 2022

When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents' opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are "represented" in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between "voter interval" and "candidate interval" preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.
Pizza Sharing Is PPA-Hard
Authors: Deligkas Argyrios , Fearnley John , Melissourgos Themistoklis
Published: July 2022

We study the computational complexity of computing solutions for the
straight-cut and square-cut pizza sharing problems. We show that finding an
approximate solution is PPA-hard for the straight-cut problem, and
PPA-complete for the square-cut problem, while finding an exact solution for
the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply
even when all mass distributions are unions of non-overlapping squares, and our
FIXP-hardness result applies even when all mass distributions are unions of
weighted squares and right-angled triangles. We also prove that decision variants
of the square-cut problem are hard: the approximate problem is
NP-complete, and the exact problem is ETR-complete.
Complexity of Deliberative Coalition Formation
Authors: Elkind Edith , Ghosh Abheek , Goldberg Paul
Published: July 2022

Elkind et al. (AAAI'21) introduced a model for deliberative coalition formation, where a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. In their model, agents and proposals are points in a metric space, agents' preferences are determined by distances, and agents deliberate by dynamically forming coalitions around proposals that they prefer over the status quo. The deliberation process operates via k-compromise transitions, where agents from k (current) coalitions come together to form a larger coalition in order to support a (perhaps new) proposal, possibly leaving behind some of the dissenting agents from their old coalitions. A deliberation succeeds if it terminates by identifying a proposal with the largest possible support. For deliberation in d dimensions, Elkind et al. consider two variants of their model: in the Euclidean model, proposals and agent locations are points in R^d and the distance is measured according to ||...||_2; and in the hypercube model, proposals and agent locations are vertices of the d-dimensional hypercube and the metric is the Hamming distance. They show that in the Euclidean model 2-compromises are guaranteed to succeed, but in the hypercube model for deliberation to succeed it may be necessary to use k-compromises with k >= d.
We complement their analysis by
(1) proving that in both models it is hard to find a proposal with a high degree of support, and even a 2-compromise transition may be hard to compute;
(2) showing that a sequence of 2-compromise transitions may be exponentially long;
(3) strengthening the lower bound on the size of the compromise for the d-hypercube model from d to 2^Ω(d).
The Price of Justified Representation
Authors: Elkind Edith , Faliszewski Piotr , Igarashi Ayumi , Manurangsi Pasin , Schmidt-Kraepelin Ulrike , Suksompong Warut
Published: July 2022

In multiwinner approval voting, the goal is to select k-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding 'good' committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.
Two-Price Equilibrium
Authors: Feldman Michal , Shabtai Galia , Wolfenfeld Aner
Published: July 2022

Walrasian equilibrium is a prominent market equilibrium notion, but rarely exists in markets with indivisible items.
We introduce a new market equilibrium notion, called two-price equilibrium (2PE). A 2PE is a relaxation of Walrasian equilibrium, where instead of a single price per item, every item has two prices: one for the item's owner and a (possibly) higher one for all other buyers.
Thus, a 2PE is given by a tuple (S,p_high,p_low) of an allocation S and two price vectors p_high,p_low, where every buyer i is maximally happy with her bundle S_i, given prices p_low for items in S_i and prices p_high for all other items.
2PE generalizes previous market equilibrium notions, such as conditional equilibrium, and is related to relaxed equilibrium notions like endowment equilibrium.
We define the discrepancy of a 2PE --- a measure of distance from Walrasian equilibrium --- as the sum of differences p_high_j-p_low_j over all items (normalized by social welfare).
We show that the social welfare degrades gracefully with the discrepancy; namely, the social welfare of a 2PE with discrepancy d is at least a fraction 1/d+1 of the optimal welfare.
We use this to establish welfare guarantees for markets with subadditive valuations over identical items.
In particular, we show that every such market admits a 2PE with at least 1/7 of the optimal welfare.
This is in contrast to Walrasian equilibrium or conditional equilibrium which may not even exist.
Our techniques provide new insights regarding valuation functions over identical items, which we also use to characterize instances that admit a WE.
Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem
Authors: Seddighin Masoud , Seddighin Saeed
Published: July 2022

In this work, we study the maximin share fairness notion for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than 1/2-MMS, the only positive result for the subadditive setting states that when the number of items is equal to m, there always exists an Ω(1/log m)-\MMS allocation. Since the number of items may be larger than the number of agents (n), such a bound can only imply a weak bound of Ω(1/(n log n))-MMS allocation in general.

In this work, we improve this gap exponentially to an Ω(1/(log n log log n))-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 1/4.6-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.
Recurrent Neural Network Controllers Synthesis with Stability Guarantees for Partially Observed Systems
Authors: Gu Fangda , Yin He , Ghaoui Laurent   El , Arcak Murat , Seiler Peter , Jin Ming
Published: July 2022

Neural network controllers have become popular in control tasks thanks to their flexibility and expressivity. Stability is a crucial property for safety-critical dynamical systems, while stabilization of partially observed systems, in many cases, requires controllers to retain and process long-term memories of the past. We consider the important class of recurrent neural networks (RNN) as dynamic controllers for nonlinear uncertain partially-observed systems, and derive convex stability conditions based on integral quadratic constraints, S-lemma and sequential convexification. To ensure stability during the learning and control process, we propose a projected policy gradient method that iteratively enforces the stability conditions in the reparametrized space taking advantage of mild additional information on system dynamics. Numerical experiments show that our method learns stabilizing controllers with fewer samples and achieves higher final performance compared with policy gradient.
Sim2Real Object-Centric Keypoint Detection and Description
Authors: Zhong Chengliang , Yang Chao , Sun Fuchun , Qi Jinshan , Mu Xiaodong , Liu Huaping , Huang Wenbing
Published: July 2022

Keypoint detection and description play a central role in computer vision. Most existing methods are in the form of scene-level prediction, without returning the object classes of different keypoints. In this paper, we propose the object-centric formulation, which, beyond the conventional setting, requires further identifying which object each interest point belongs to. With such fine-grained information, our framework enables more downstream potentials, such as object-level matching and pose estimation in a clustered environment. To get around the difficulty of label collection in the real world, we develop a sim2real contrastive learning mechanism that can generalize the model trained in simulation to real-world applications. The novelties of our training method are three-fold: (i) we integrate the uncertainty into the learning framework to improve feature description of hard cases, e.g., less-textured or symmetric patches; (ii) we decouple the object descriptor into two independent branches, intra-object salience and inter-object distinctness, resulting in a better pixel-wise description; (iii) we enforce cross-view semantic consistency for enhanced robustness in representation learning. Comprehensive experiments on image matching and 6D pose estimation verify the encouraging generalization ability of our method. Particularly for 6D pose estimation, our method significantly outperforms typical unsupervised/sim2real methods, achieving a closer gap with the fully supervised counterpart.
Trading Complexity for Sparsity in Random Forest Explanations
Authors: Audemard Gilles , Bellart Steve , Bounia Louènas , Koriche Frédéric , Lagniez Jean-Marie , Marquis Pierre
Published: July 2022

Random forests have long been considered as powerful model ensembles in machine learning. By training multiple decision trees, whose diversity is fostered through data and feature subsampling, the resulting random forest can lead to more stable and reliable predictions than a single decision tree. This however comes at the cost of decreased interpretability: while decision trees are often easily interpretable, the predictions made by random forests are much more difficult to understand, as they involve a majority vote over multiple decision trees. In this paper, we examine different types of reasons that explain "why" an input instance is classified as positive or negative by a Boolean random forest. Notably, as an alternative to prime-implicant explanations taking the form of subset-minimal implicants of the random forest, we introduce majoritary reasons which are subset-minimal implicants of a strict majority of decision trees. For these abductive explanations, the tractability of the generation problem (finding one reason) and the optimization problem (finding one minimum-sized reason) are investigated. Unlike prime-implicant explanations, majoritary reasons may contain redundant features. However, in practice, prime-implicant explanations - for which the identification problem is DP-complete - are slightly larger than majoritary reasons that can be generated using a simple linear-time greedy algorithm. They are also significantly larger than minimum-sized majoritary reasons which can be approached using an anytime Partial MaxSAT algorithm.
Finite Entailment of Local Queries in the Z Family of Description Logics
Authors: Bednarczyk Bartosz , Kieroński Emanuel
Published: July 2022

In the last few years the field of logic-based knowledge representation took a lot of inspiration from database theory. A vital example is that the finite model semantics in description logics (DLs) is reconsidered as a desirable alternative to the classical one and that query entailment has replaced knowledge-base satisfiability (KBSat) checking as the key inference problem. However, despite the considerable effort, the overall picture concerning finite query answering in DLs is still incomplete. In this work we study the complexity of finite entailment of local queries (conjunctive queries and positive boolean combinations thereof) in the Z family of DLs, one of the most powerful KR formalisms, lying on the verge of decidability. Our main result is that the DLs ZOQ and ZOI are finitely controllable, i.e. that their finite and unrestricted entailment problems for local queries coincide. This allows us to reuse recently established upper bounds on querying these logics under the classical semantics. While we will not solve finite query entailment for the third main logic in the Z family, ZIQ, we provide a generic reduction from the finite entail- ment problem to the finite KBSat problem, working for ZIQ and some of its sublogics. Our proofs unify and solidify previously established results on finite satisfiability and finite query entailment for many known DLs.
ER: Equivariance Regularizer for Knowledge Graph Completion
Authors: Cao Zongsheng , Xu Qianqian , Yang Zhiyong , Huang Qingming
Published: July 2022

Tensor factorization and distanced based models play important roles in knowledge graph completion (KGC). However, the relational matrices in KGC methods often induce a high model complexity, bearing a high risk of overfitting. As a remedy, researchers propose a variety of different regularizers such as the tensor nuclear norm regularizer. Our motivation is based on the observation that the previous work only focuses on the “size” of the parametric space, while leaving the implicit semantic information widely untouched. To address this issue, we propose a new regularizer, namely, Equivariance Regularizer (ER), which can suppress overfitting by leveraging the implicit semantic information. Specifically, ER can enhance the generalization ability of the model by employing the semantic equivariance between the head and tail entities. Moreover, it is a generic solution for both distance based models and tensor factorization based models. Our experimental results indicate a clear and substantial improvement over the state-of-the-art relation prediction methods.
Geometry Interaction Knowledge Graph Embeddings
Authors: Cao Zongsheng , Xu Qianqian , Yang Zhiyong , Cao Xiaochun , Huang Qingming
Published: July 2022

Knowledge graph (KG) embeddings have shown great power in learning representations of entities and relations for link prediction tasks. Previous work usually embeds KGs into a single geometric space such as Euclidean space (zero curved), hyperbolic space (negatively curved) or hyperspherical space (positively curved) to maintain their specific geometric structures (e.g., chain, hierarchy and ring structures). However, the topological structure of KGs appears to be complicated, since it may contain multiple types of geometric structures simultaneously. Therefore, embedding KGs in a single space, no matter the Euclidean space, hyperbolic space or hyperspheric space, cannot capture the complex structures of KGs accurately. To overcome this challenge, we propose Geometry Interaction knowledge graph Embeddings (GIE), which learns spatial structures interactively between the Euclidean, hyperbolic and hyperspherical spaces. Theoretically, our proposed GIE can capture a richer set of relational information, model key inference patterns, and enable expressive semantic matching across entities. Experimental results on three well-established knowledge graph completion benchmarks show that our GIE achieves the state-of-the-art performance with fewer parameters.
Tractable Abstract Argumentation via Backdoor-Treewidth
Authors: Dvořák Wolfgang , Hecher Markus , König Matthias , Schidler André , Szeider Stefan , Woltran Stefan
Published: July 2022

Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to achieve manageable runtimes have been considered in the past. Among them, the backdoor-approach and the treewidth-approach turned out to yield fixed-parameter tractable fragments. However, many applications yield high parameter values for these methods, often rendering them infeasible in practice. We introduce the backdoor-treewidth approach for abstract argumentation, combining the best of both worlds with a guaranteed parameter value that does not exceed the minimum of the backdoor- and treewidth-parameter. In particular, we formally define backdoor-treewidth and establish fixed-parameter tractability for standard reasoning tasks of abstract argumentation. Moreover, we provide systems to find and exploit backdoors of small width, and conduct systematic experiments evaluating the new parameter.
BERTMap: A BERT-Based Ontology Alignment System
Authors: He Yuan , Chen Jiaoyan , Antonyrajah Denvar , Horrocks Ian
Published: July 2022

Ontology alignment (a.k.a ontology matching (OM)) plays a critical role in knowledge integration. Owing to the success of machine learning in many domains, it has been applied in OM. However, the existing methods, which often adopt ad-hoc feature engineering or non-contextual word embeddings, have not yet outperformed rule-based systems especially in an unsupervised setting. In this paper, we propose a novel OM system named BERTMap which can support both unsupervised and semi-supervised settings. It first predicts mappings using a classifier based on fine-tuning the contextual embedding model BERT on text semantics corpora extracted from ontologies, and then refines the mappings through extension and repair by utilizing the ontology structure and logic. Our evaluation with three alignment tasks on biomedical ontologies demonstrates that BERTMap can often perform better than the leading OM systems LogMap and AML.
Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula
Authors: Malhotra Sagar , Serafini Luciano
Published: July 2022

Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a given finite domain. First-Order Logic theories that admit polynomial-time WFOMC w.r.t domain cardinality are called domain liftable. We introduce the concept of lifted interpretations as a tool for formulating closed forms for WFOMC. Using lifted interpretations, we reconstruct the closed-form formula for polynomial-time FOMC in the universally quantified fragment of FO2, earlier proposed by Beame et al. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability. Finally, we show that the obtained closed-form motivates a natural definition of a family of weight functions strictly larger than symmetric weight functions.
Weakly Supervised Neural Symbolic Learning for Cognitive Tasks
Authors: Tian Jidong , Li Yitian , Chen Wenqing , Xiao Liqiang , He Hao , Jin Yaohui
Published: July 2022

Despite the recent success of end-to-end deep neural networks, there are growing concerns about their lack of logical reasoning abilities, especially on cognitive tasks with perception and reasoning processes. A solution is the neural symbolic learning (NeSyL) method that can effectively utilize pre-defined logic rules to constrain the neural architecture making it perform better on cognitive tasks. However, it is challenging to apply NeSyL to these cognitive tasks because of the lack of supervision, the non-differentiable manner of the symbolic system, and the difficulty to probabilistically constrain the neural network. In this paper, we propose WS-NeSyL, a weakly supervised neural symbolic learning model for cognitive tasks with logical reasoning. First, WS-NeSyL employs a novel back search algorithm to sample the possible reasoning process through logic rules. This sampled process can supervise the neural network as the pseudo label. Based on this algorithm, we can backpropagate gradients to the neural network of WS-NeSyL in a weakly supervised manner. Second, we introduce a probabilistic logic regularization into WS-NeSyL to help the neural network learn probabilistic logic. To evaluate WS-NeSyL, we have conducted experiments on three cognitive datasets, including temporal reasoning, handwritten formula recognition, and relational reasoning datasets. Experimental results show that WS-NeSyL not only outperforms the end-to-end neural model but also beats the state-of-the-art neural symbolic learning models.
First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics
Authors: Toman David , Weddell Grant
Published: July 2022

We consider first-order (FO) rewritability for query answering in ontology mediated querying (OMQ) in which ontologies are formulated in Horn fragments of description logics (DLs). In general, OMQ approaches for such logics rely on non-FO rewriting of the query and/or on non-FO completion of the data, called a ABox. Specifically, we consider the problem of FO rewritability in terms of Beth definability, and show how Craig interpolation can then be used to effectively construct the rewritings, when they exist, from the Clark’s completion of Datalog-like programs encoding a given DL TBox and optionally a query. We show how this approach to FO rewritability can also be used to (a) capture integrity constraints commonly available in backend relational data sources, (b) capture constraints inherent in mapping such sources to an ABox , and (c) can be used an alternative to deriving so-called perfect rewritings of queries in the case of DL-Lite ontologies.
Modeling Attrition in Recommender Systems with Departing Bandits
Authors: Ben-Porat Omer , Cohen Lee , Leqi Liu , Lipton Zachary C. , Mansour Yishay
Published: July 2022

Traditionally, when recommender systems are formalized as multi-armed bandits, the policy of the recommender system influences the rewards accrued, but not the length of interaction. However, in real-world systems, dissatisfied users may depart (and never come back). In this work, we propose a novel multi-armed bandit setup that captures such policy-dependent horizons. Our setup consists of a finite set of user types, and multiple arms with Bernoulli payoffs.
Each (user type, arm) tuple corresponds to an (unknown) reward probability. Each user's type is initially unknown
and can only be inferred through their response to recommendations. Moreover, if a user is dissatisfied with their recommendation, they might depart the system. We first address the case where all users share the same type,
demonstrating that a recent UCB-based algorithm is optimal. We then move forward to the more challenging case,
where users are divided among two types. While naive approaches cannot handle this setting,
we provide an efficient learning algorithm that achieves O(sqrt(T)ln(T)) regret, where T is the number of users.
Active Sampling for Text Classification with Subinstance Level Queries
Authors: Chakraborty Shayok , Singh Ankita
Published: July 2022

Active learning algorithms are effective in identifying the salient and exemplar samples from large amounts of unlabeled data. This tremendously reduces the human annotation effort in inducing a machine learning model as only a few samples, which are identified by the algorithm, need to be labeled manually. In problem domains like text mining and video classification, human oracles peruse the data instances incrementally to derive an opinion about their class labels (such as reading a movie review progressively to assess its sentiment). In such applications, it is not necessary for the human oracles to review an unlabeled sample end-to-end in order to provide a label; it may be more efficient to identify an optimal subinstance size (percentage of the sample from the start) for each unlabeled sample, and request the human annotator to label the sample by analyzing only the subinstance, instead of the whole data sample. In this paper, we propose a novel framework to address this challenging problem, in an effort to further reduce the labeling burden on the human oracles and utilize the available labeling budget more efficiently. We pose the sample and subinstance size selection as a constrained optimization problem and derive a linear programming relaxation to select a batch of exemplar samples, together with the optimal subinstance size of each, which can potentially augment maximal information to the underlying classification model. Our extensive empirical studies on six challenging datasets from the text mining domain corroborate the practical usefulness of our framework over competing baselines.
Clustering Interval-Censored Time-Series for Disease Phenotyping
Authors: Chen Irene Y. , Krishnan Rahul  G. , Sontag David
Published: July 2022

Unsupervised learning is often used to uncover clusters in data. However, different kinds of noise may impede the discovery of useful patterns from real-world time-series data. In this work, we focus on mitigating the interference of interval censoring in the task of clustering for disease phenotyping. We develop a deep generative, continuous-time model of time-series data that clusters time-series while correcting for censorship time. We provide conditions under which clusters and the amount of delayed entry may be identified from data under a noiseless model. On synthetic data, we demonstrate accurate, stable, and interpretable results that outperform several benchmarks. On real-world clinical datasets of heart failure and Parkinson's disease patients, we study how interval censoring can adversely affect the task of disease phenotyping. Our model corrects for this source of error and recovers known clinical subtypes.
Efficient Robust Training via Backward Smoothing
Authors: Chen Jinghui , Cheng Yu , Gan Zhe , Gu Quanquan , Liu Jingjing
Published: July 2022

Adversarial training is so far the most effective strategy in defending against adversarial examples. However, it suffers from high computational costs due to the iterative adversarial attacks in each training step. Recent studies show that it is possible to achieve fast Adversarial Training by performing a single-step attack with random initialization. However, such an approach still lags behind state-of-the-art adversarial training algorithms on both stability and model robustness. In this work, we develop a new understanding towards Fast Adversarial Training, by viewing random initialization as performing randomized smoothing for better optimization of the inner maximization problem. Following this new perspective, we also propose a new initialization strategy, backward smoothing, to further improve the stability and model robustness over single-step robust training methods.
Experiments on multiple benchmarks demonstrate that our method achieves similar model robustness as the original TRADES method while using much less training time (~3x improvement with the same training schedule).
Evidential Neighborhood Contrastive Learning for Universal Domain Adaptation
Authors: Chen Liang , Lou Yihang , He Jianzhong , Bai Tao , Deng Minghua
Published: July 2022

Universal domain adaptation (UniDA) aims to transfer the knowledge learned from a labeled source domain to an unlabeled target domain without any constraints on the label sets. However, domain shift and category shift make UniDA extremely challenging, mainly attributed to the requirement of identifying both shared “known” samples and private “unknown” samples. Previous methods barely exploit the intrinsic manifold structure relationship between two domains for feature alignment, and they rely on the softmax-based scores with class competition nature to detect underlying “unknown” samples. Therefore, in this paper, we propose a novel evidential neighborhood contrastive learning framework called TNT to address these issues. Specifically, TNT first proposes a new domain alignment principle: semantically consistent samples should be geometrically adjacent to each other, whether within or across domains. From this criterion, a cross-domain multi-sample contrastive loss based on mutual nearest neighbors is designed to achieve common category matching and private category separation. Second, toward accurate “unknown” sample detection, TNT introduces a class competition-free uncertainty score from the perspective of evidential deep learning. Instead of setting a single threshold, TNT learns a category-aware heterogeneous threshold vector to reject diverse “unknown” samples. Extensive experiments on three benchmarks demonstrate that TNT significantly outperforms previous state-of-the-art UniDA methods.
Semi-supervised Learning with Multi-Head Co-Training
Authors: Chen Mingcai , Du Yuntao , Zhang Yi , Qian Shuwei , Wang Chongjun
Published: July 2022

Co-training, extended from self-training, is one of the frameworks for semi-supervised learning. Without natural split of features, single-view co-training works at the cost of training extra classifiers, where the algorithm should be delicately designed to prevent individual classifiers from collapsing into each other. To remove these obstacles which deter the adoption of single-view co-training, we present a simple and efficient algorithm Multi-Head Co-Training. By integrating base learners into a multi-head structure, the model is in a minimal amount of extra parameters. Every classification head in the unified model interacts with its peers through a “Weak and Strong Augmentation” strategy, in which the diversity is naturally brought by the strong data augmentation. Therefore, the proposed method facilitates single-view co-training by 1). promoting diversity implicitly and 2). only requiring a small extra computational overhead. The effectiveness of Multi-Head Co-Training is demonstrated in an empirical study on standard semi-supervised learning benchmarks.
Input-Specific Robustness Certification for Randomized Smoothing
Authors: Chen Ruoxin , Li Jie , Yan Junchi , Li Ping , Sheng Bin
Published: July 2022

Although randomized smoothing has demonstrated high certified robustness and superior scalability to other certified defenses, the high computational overhead of the robustness certification bottlenecks the practical applicability, as it depends heavily on the large sample approximation for estimating the confidence interval. In existing works, the sample size for the confidence interval is universally set and agnostic to the input for prediction. This Input-Agnostic Sampling (IAS) scheme may yield a poor Average Certified Radius (ACR)-runtime trade-off which calls for improvement. In this paper, we propose Input-Specific Sampling (ISS) acceleration to achieve the cost-effectiveness for robustness certification, in an adaptive way of reducing the sampling size based on the input characteristic. Furthermore, our method universally controls the certified radius decline from the ISS sample size reduction. The empirical results on CIFAR-10 and ImageNet show that ISS can speed up the certification by more than three times at a limited cost of 0.05 certified radius. Meanwhile, ISS surpasses IAS on the average certified radius across the extensive hyperparameter settings. Specifically, ISS achieves ACR=0.958 on ImageNet in 250 minutes, compared to ACR=0.917 by IAS under the same condition. We release our code in https://github.com/roy-ch/Input-Specific-Certification.
BScNets: Block Simplicial Complex Neural Networks
Authors: Chen Yuzhou , Gel Yulia R. , Poor H. Vincent
Published: July 2022

Simplicial neural networks (SNNs) have recently emerged as a new direction in graph learning which expands the idea of convolutional architectures from node space to simplicial complexes on graphs. Instead of predominantly assessing pairwise relations among nodes as in the current practice, simplicial complexes allow us to describe higher-order interactions and multi-node graph structures. By building upon connection between the convolution operation and the new block Hodge-Laplacian, we propose the first SNN for link prediction. Our new Block Simplicial Complex Neural Networks (BScNets) model generalizes existing graph convolutional network (GCN) frameworks by systematically incorporating salient interactions among multiple higher-order graph structures of different dimensions. We discuss theoretical foundations behind BScNets and illustrate its utility for link prediction on eight real-world and synthetic datasets. Our experiments indicate that BScNets outperforms the state-of-the-art models by a significant margin while maintaining low computation costs. Finally, we show utility of BScNets as a new promising alternative for tracking spread of infectious diseases such as COVID-19 and measuring the effectiveness of the healthcare risk mitigation strategies.
Graph Neural Controlled Differential Equations for Traffic Forecasting
Authors: Choi Jeongwhan , Choi Hwangyong , Hwang Jeehyun , Park Noseong
Published: July 2022

Traffic forecasting is one of the most popular spatio-temporal tasks in the field of machine learning. A prevalent approach in the field is to combine graph convolutional networks and recurrent neural networks for the spatio-temporal processing. There has been fierce competition and many novel methods have been proposed. In this paper, we present the method of spatio-temporal graph neural controlled differential equation (STG-NCDE). Neural controlled differential equations (NCDEs) are a breakthrough concept for processing sequential data. We extend the concept and design two NCDEs: one for the temporal processing and the other for the spatial processing. After that, we combine them into a single framework. We conduct experiments with 6 benchmark datasets and 20 baselines. STG-NCDE shows the best accuracy in all cases, outperforming all those 20 baselines by non-trivial margins.