United States

The concept of Strong Backdoor Sets (SBS) for Constraint Satisfaction Problems is well known as one of the attempts to exploit structural peculiarities in hard instances. However, in practice, finding an SBS for a particular instance is often harder than solving it. Recently, a probabilistic weakened variant of the SBS was introduced: in the SBS, all subproblems must be polynomially solvable, whereas in the probabilistic SBS only a large fraction ρ of them should have this property.
This new variant of backdoors called ρ-backdoors makes it possible to use the Monte Carlo method and metaheuristic optimization to find ρ-backdoors with ρ very close to 1, and relatively fast. Despite the fact that in a ρ-backdoor-based decomposition a portion of hard subproblems remain, in practice the narrowing of the search space often allows solving the problem faster than without it. In this paper, we significantly improve on the concept of ρ-backdoors by extending this concept to backdoor trees, introduce ρ-backdoor trees, show the interconnections between SBS, ρ-backdoors, and the corresponding backdoor trees, and establish some new theoretical properties of backdoor trees. In the experimental part of the paper, we show that moving from the metaheuristic search for ρ-backdoors to that of ρ-backdoor trees allows drastically reducing the time required to construct the required decompositions without compromising their quality.

AAAI 2023

Probabilistic Generalization of Backdoor Trees with Application to SAT

backdoor trees

backdoors

**Welcome to ACL-IJCNLP 2021!**

The great event is jointly organized by the Association for Computational Linguistics (ACL) and Asian Federation of Natural Language Processing (AFNLP). 

As in previous years, the program of the conference includes a poster session, tutorials, workshops and demonstrations in addition to the main conference.


We were able to keep the registration fees similar to those charged for the virtual ACL 2020. The one fee allows attendance at the main conference and any/all tutorials and workshops. These fees would be $125 Regular Early and $175 Regular Late; $50 Student Early and $75 Student Late. Early registration closes at midnight July 11, 2021 (Eastern Daylight Time).

**Reminder:** It is ACL’s policy that at least one author of each accepted paper (including ACL Finding papers) must register for the conference.

**Reminder2:** Underline site will open closer to the event. If you already registered you will receive access detail

Registration is now open

ACL-IJCNLP 2021

The great event is jointly organized by the Association for Computational Linguistics (ACL) and Asian Federation of Natural Language Processing (AFNLP).

poster

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

Recent development of deep neural networks (DNNs) for tabular learning has largely benefited from the capability of DNNs for automatic feature interaction. However, the heterogeneity nature of tabular features makes such features relatively independent, and developing effective methods to promote tabular feature interaction still remains an open problem. In this paper, we propose a novel Graph Estimator, which automatically estimates the relations among tabular features and builds graphs by assigning edges between related features. Such relation graphs organize independent tabular features into a kind of graph data such that interaction of nodes (tabular features) can be conducted in an orderly fashion. Based on our proposed Graph Estimator, we present a bespoke Transformer network tailored for tabular learning, called T2G-Former, which processes tabular data by performing tabular feature interaction guided by the relation graphs. A specific Cross-level Readout collects salient features predicted by the layers in T2G-Former across different levels, and attains global semantics for final prediction. Comprehensive experiments show that our T2G-Former achieves superior performance among DNNs and is competitive with non-deep Gradient Boosted Decision Tree models.

T2G-Former: Organizing Tabular Features into Relation Graphs Promotes Heterogeneous Feature Interaction

Existing lifting networks for regressing 3D human poses from 2D single-view poses are typically constructed with linear layers based on graph-structured representation learning. In sharp contrast to them, this paper presents Grid Convolution (GridConv), mimicking the wisdom of regular convolution operations in image space. GridConv is based on a novel Semantic Grid Transformation (SGT) which leverages a binary assignment matrix to map the irregular graph-structured human pose onto a regular weave-like grid pose representation joint by joint, enabling layer-wise feature learning with GridConv operations. We provide two ways to implement SGT, including handcrafted and learnable designs. Surprisingly, both designs turn out to achieve promising results and the learnable one is better, demonstrating the great potential of this new lifting representation learning formulation. To improve the ability of GridConv to encode contextual cues, we introduce an attention module over the convolutional kernel, making grid convolution operations input-dependent, spatial-aware and grid-specific. We show that our fully convolutional grid lifting network outperforms state-of-the-art methods with noticeable margins under (1) conventional evaluation on Human3.6M and (2) cross-evaluation on MPI-INF-3DHP. Code is available at https://github.com/OSVAI/GridConv.

3D Human Pose Lifting with Grid Convolution

Molecular representation learning is a fundamental problem in the field of drug discovery and molecular science. Whereas incorporating molecular 3D information in the representations of molecule seems beneficial, which is related to computational chemistry with the basic task of predicting stable 3D structures (conformations) of molecules. Existing machine learning methods either rely on 1D and 2D molecular properties or simulate molecular force field to use additional 3D structure information via Hamiltonian network. The former has the disadvantage of ignoring important 3D structure features, while the latter has the disadvantage that existing Hamiltonian neural network must satisfy the “canonial” constraint, which is difficult to be obeyed in many cases. In this paper, we propose a novel plug-and-play architecture LagNet by simulating molecular force field only with parameterized position coordinates, which implements Lagrangian mechanics to learn molecular representation by preserving 3D conformation without obeying any additional restrictions. LagNet is designed to generate known conformations and generalize for unknown ones from molecular SMILES. Implicit positions in LagNet are learned iteratively using discrete-time Lagrangian equations. Experimental results show that LagNet can well learn 3D molecular structure features, and outperforms previous state-of-the-art baselines related molecular representation by a significant margin.

LagNet: Deep Lagrangian Mechanics for Plug-and-Play Molecular Representation Learning

Hashing has been widely researched to solve the large-scale approximate nearest neighbor search problem owing to its time and storage superiority. In recent years, a number of online hashing methods have emerged, which can update the hash functions to adapt to the new stream data and realize dynamic  retrieval. However, existing online hashing methods are required to update the whole database with the latest hash functions when a query arrives, which leads to low retrieval efficiency with the continuous increase of the stream data. On the other hand, these methods ignore the supervision relationship among the examples, especially in the multi-label case. In this paper, we propose a novel Fast Online Hashing (FOH) method which only updates the binary codes of a small part of the database. To be specific, we first build a query pool in which the nearest neighbors of each central point are recorded. When a new query arrives, only the binary codes of the corresponding potential neighbors are updated. In addition, we create a similarity matrix which takes the multi-label supervision information into account and bring in the multi-label projection loss to further preserve the similarity among the multi-label data. The experimental results on two common benchmarks show that the proposed FOH can achieve dramatic superiority on query time up to 6.28 seconds less than state-of-the-art baselines with competitive retrieval accuracy.

Fast Online Hashing with Multi-Label Projection

A Fisher market is an economic model of buyer and seller interactions in which each buyer's utility depends only on the bundle of goods she obtains. Many people's interests, however, are affected by their social interactions with others. In this paper, we introduce a generalization of Fisher markets, namely influence Fisher markets, which captures the impact of social influence on buyers' utilities. We model influence Fisher markets as pseudo-games. Using this framework, we first define and prove the existence of competitive equilibrium in all influence Fisher markets with continuous and concave utility functions. We then construct a second similar pseudo-game, which is monotone and whose solution, a variational equilibrium, and dual together characterize competitive equilibria in influence Fisher markets with continuous, concave, homogeneous (CCH) utility functions. This observation immediately implies that competitive equilibria in these markets can be computed in polynomial time. The dual of this pseudo-game enables us to interpret the competitive equilibria of CCH influence Fisher markets as the Stackelberg equilibria of a single-leader multiple-follower Stackelberg game. Finally, we derive a novel first-order method that solves this Stackelberg game in polynomial time, prove that it is equivalent to computing competitive equilibrium prices via t\^{a}tonnement, and run experiments that confirm our theoretical results.

Fisher Markets with Social Influence

There is a significant need for principled uncertainty reasoning in machine learning systems as they are increasingly deployed in safety-critical domains.
A new approach with uncertainty-aware regression-based neural networks (NNs), based on learning evidential distributions for aleatoric and epistemic uncertainties, shows promise over traditional deterministic methods and typical Bayesian NNs, notably with the capabilities to disentangle aleatoric and epistemic uncertainties.
Despite some empirical success of Deep Evidential Regression (DER), there are important gaps in the mathematical foundation that raise the question of why the proposed technique seemingly works.
We detail the theoretical shortcomings and analyze the performance on synthetic and real-world data sets, showing that Deep Evidential Regression is a heuristic rather than an exact uncertainty quantification.
We go on to discuss corrections and redefinitions of how aleatoric and epistemic uncertainties should be extracted from NNs.

The Unreasonable Effectiveness of Deep Evidential Regression

Sophisticated data augmentations  can greatly boost the efficiency of Graph Contrastive Learning (GCL). However, there are works investigating the feature augmentation for unsupervised contrastive learning, although (class-conditional) feature augmentation has been proven useful in supervised learning. Thus, we present a novel/efficient spectral feature argumentation for contrastive learning on graphs (and images). To this end, from two data views, respectively, we estimate a low-rank approximation per feature map and  subtract that approximation from the map to obtain its complement. This is achieved by the proposed herein  so-called incomplete power iteration, a non-standard power iteration regime which enjoys two valuable byproducts (under the low number of iterations only): (i) relieve the unbalancing spectrum of the feature map, and (ii) injecting the noise into the singular values of the feature map. For two views, we align these complement feature maps as the spectrum-balanced alignment step focuses on less dominant singular values of spectra of both views, whereas the spectral augmentation of singular values does not affect the spectral angle alignment (singular vectors are left intact). We derive the analytical form for the incomplete power iteration to capture its spectrum-balancing effect and the variance of singular values implicitly augmented by the noise. We also show that this augmentation leads to a lower generalization bound. Experiments on graph and image datasets demonstrate the proposed spectral feature augmentation  outperforms baselines, and is complementary with other graph augmentation approaches and compatible with various contrastive losses. 

Spectral Feature Augmentation for Graph Contrastive Learning and Beyond

Cooperative multi-agent reinforcement learning (c-MARL) is widely applied in safety-critical scenarios, thus the analysis of robustness for c-MARL models is profoundly important. However, robustness certification for c-MARLs has not yet been explored in the community. In this paper, we propose a novel certification method, which is the first work to leverage a scalable approach for c-MARLs to determine actions with guaranteed certified bounds. c-MARL certification poses two key challenges compared with single-agent systems: (i) the accumulated uncertainty as the number of agents increases; (ii) the potential lack of impact when changing the action of a single agent into a global team reward. These challenges prevent us from directly using existing algorithms. Hence, we employ the false discovery rate (FDR) controlling procedure considering the importance of each agent to certify per-state robustness and propose a tree-search-based algorithm to find a lower bound of the global reward under the minimal certified perturbation. As our method is general, it can also be applied in single-agent environments. We empirically show that our certification bounds are much tighter than those of the state-of-the-art RL certification solutions. We also run experiments on two popular c-MARL algorithms: QMIX and VDN, in two different environments, with two and four agents. The experimental results show that our method produces a meaningful guaranteed robustness for all models and environments. Our tool CertifyCMARL is available at https://github.com/TrustAI/CertifyCMARL.

Certified Policy Smoothing for Cooperative Multi-Agent Reinforcement Learning

The concept of walkable urban development has gained increased
attention due to its public health, economic, and environmental
sustainability benefits. Unfortunately, land zoning
and historic under-investment have resulted in spatial inequality
in walkability and social inequality among residents.
We tackle the problem of Walkability Optimization through
the lens of combinatorial optimization. The task is to select
locations in which additional amenities (e.g., grocery stores,
schools, restaurants) can be allocated to improve resident access
via walking while taking into account existing amenities
and providing multiple options (e.g., for restaurants).
To this end, we derive Mixed-Integer Linear Programming
(MILP) and Constraint Programming (CP) models. Moreover,
we show that the problem’s objective function is submodular
in special cases, which motivates an efficient greedy
heuristic. We conduct a case study on 31 underserved neighborhoods
in the City of Toronto, Canada. MILP finds the
best solutions in most scenarios but does not scale well with
network size. The greedy algorithm scales well and finds
near-optimal solutions. Our empirical evaluation shows that
neighbourhoods with low walkability have a great potential
for transformation into pedestrian-friendly neighbourhoods
by strategically placing new amenities. Allocating 3 additional
grocery stores, schools, and restaurants can improve the
“WalkScore” by more than 50 points (on a scale of 100) for 4
neighbourhoods and reduce the walking distances to amenities
for 75% of all residential locations to 10 minutes for all
amenity types. Our code and paper appendix are available at
https://github.com/khalil-research/walkability.

Downloads

Next from AAAI 2023

T2G-Former: Organizing Tabular Features into Relation Graphs Promotes Heterogeneous Feature Interaction

Similar lecture

Backdoors in Neural Models of Source Code