The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to the vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the$\mathcal {NP}$-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to$10^{7}$vertices). This article presents an efficient hybrid heuristic algorithm for GCP, namedHyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency ofHyColorcomes from the following three aspects: 1) a local decision strategy to improve the lower bound on the chromatic number; 2) a graph-reduction strategy to reduce the working graph; and 3) a$k$-core and mixed degree-based greedy heuristic for efficiently coloring graphs.HyColoris evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate thatHyColorconsistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably,HyColorachieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore,HyColorsuccessfully determined the chromatic number and achieved optimal coloring in 128 instances.

The problem of Multi-Agent Reinforcement Learning (MARL) shows a high level of both complexity in the environment and coordination between agents. In order to scale the algorithm to large-scale agent scenarios, neural networks designed for MARL are typically implemented with parameter sharing. These characteristics result in the challenges of partial observability, credit assignment and strategy homogenization. In this paper, a Transformer-Based Multi-Agent Reinforcement Learning Method With Credit-Oriented Strategy Differentiation (TMRC) is presented to address each of these challenges. First, we design a Temporal-Spatial Encoding module and an Attention-Based Value Decomposition module based on the Transformer architecture. The former leverages both temporal and spatial observation information, compensating for the missing environmental perspectives due to partial observability. The latter is designed to identify each agent’s individual contribution in complex interactions, effectively optimizing the credit assignment process. Then, we propose a Credit-Oriented Strategy Differentiation module that differentiates the entity representations of each agent based on their current task differences, allowing agents to have distinct real-time strategies, effectively mitigating the issue of strategy homogenization. We evaluate the proposed method on the SMAC benchmark. It demonstrates better final performance, faster convergence, and greater stability compared to other comparative methods. Additionally, a series of experiments are conducted to validate the effectiveness of the proposed modules. Our code is available at https://github.com/Hkxuan/TMRC.git.

Car detection is an important task that serves as a crucial prerequisite for many automated driving functions. The large variations in lighting/weather conditions and vehicle densities of the scenes pose significant challenges to existing car detection algorithms to meet the highly accurate perception demand for safety, due to the unstable/limited color information, which impedes the extraction of meaningful/discriminative features of cars. In this work, we present a novel learning-based car detection method that leverages trichromatic linear polarization as an additional cue to disambiguate such challenging cases. A key observation is that polarization, characteristic of the light wave, can robustly describe intrinsic physical properties of the scene objects in various imaging conditions and is strongly linked to the nature of materials for cars (e.g., metal and glass) and their surrounding environment (e.g., soil and trees), thereby providing reliable and discriminative features for robust car detection in challenging scenes. To exploit polarization cues, we first construct a pixel-aligned RGB-Polarization car detection dataset, which we subsequently employ to train a novel multimodal fusion network. Our car detection network dynamically integrates RGB and polarization features in a request-and-complement manner and can explore the intrinsic material properties of cars across all learning samples. We extensively validate our method and demonstrate that it outperforms state-of-the-art detection methods. Experimental results show that polarization is a powerful cue for car detection. Our code is available at https://github.com/wind1117/AAAI24-PCDNet.

Multi-domain recommendation systems have attracted attention for their potential in utilizing data from various domains. However, existing multi-domain recommendation systems face two limitations. First, current models typically use a unified modeling approach to handle both inter-domain global information (common preferences of users across all domains) and independent intra-domain information (preferences of users within a single domain), leading to the entanglement of the two types of information, making it difficult to effectively utilize them and achieve complementary gains. Second, data sparsity and the lack of effective information transfer mechanisms further limit multi-domain interaction, weakening recommendation performance. To address these limitations, we propose a method that combines adaptive domain disentanglement and multi-domain meta-contrastive learning to disentangle inter-domain and intra-domain information, amplifying the advantages of both types of information to jointly complete the recommendation task. Meanwhile, knowledge transfer between multiple domains is employed to improve overall recommendation performance. To disentangle inter-domain and intra-domain information, we design a shared hypernetwork based on graph convolution to adaptively aggregate neighbor information and inject high-order neighbor information to capture holistic feature. We integrate the meta-learning and contrastive learning. Based on the multi-domain contrastive learning, we design a meta-knowledge encoder and a meta-weight mapping network, generating a tailored loss function that promotes the effective transfer of information between domains. Experiments on three public datasets show our model outperforms nine baseline models.

Reviewing the previous work of diversity Reinforcement Learning, diversity is often obtained via an augmented loss function, which requires a balance between reward and diversity. Generally, diversity optimization algorithms use Multi-armed Bandits algorithms to select the coefficient in the pre-defined space. However, the dynamic distribution of reward signals for MABs or the conflict between quality and diversity limits the performance of these methods. We introduce the Phasic Diversity Optimization (PDO) algorithm, a Population-Based Training framework that separates reward and diversity training into distinct phases instead of optimizing a multi-objective function. In the auxiliary phase, agents with poor performance diversified via determinants will not replace the better agents in the archive. The decoupling of reward and diversity allows us to use an aggressive diversity optimization in the auxiliary phase without performance degradation. Furthermore, we construct a dogfight scenario for aerial agents to demonstrate the practicality of the PDO algorithm. We introduce two implementations of PDO archive and conduct tests in the newly proposed adversarial dogfight and MuJoCo simulations. The results show that our proposed algorithm achieves better performance than baselines.

Industrial Control Systems (ICS) are increasingly facing the threat of False Data Injection (FDI) attacks. Process-based anomaly detection is an emerging intrusion detection approach for I CS that effectively identifies anomalies induced by FDI attacks. Anomaly detection models are constructed to describe the normal patterns of industrial processes and subsequently perform real-time evaluation of process data. However, this approach suffers from low detection accuracy due to the complex nonlinear spatiotemporal correlations in industrial pro-cess data, which are difficult to explicitly describe using anomaly detection models. Additionally, noise and interference within the process data prevent these models from recognizing genuine anomalous events. This paper proposes a State Space-based Anomaly Detection (SSAD) approach. Specifically, to explicitly describe the spatiotemporal correlations in process data, we introduce a deep learning-based state estimation model that employs Convolutional Neural Networks (CNNs) for temporal modeling and utilizes a Selective State Space (SSS) for spatial modeling. To detect anomalies in the presence of noise and interference, we design a robust anomaly identification model that combines maximum deviation and threshold strategies to analyze the outputs of the state estimation model. Extensive experiments on two benchmark I CS security datasets demonstrate the effectiveness of SSAD.

Autonomous obstacle avoidance is of vital importance for an intelligent agent such as a mobile robot to navigate in its environment. Existing state-of-the-art methods train a spiking neural network (SNN) with deep reinforcement learning (DRL) to achieve energy-efficient and fast inference speed in complex/unknown scenes. These methods typically assume that the environment is static while the obstacles in real-world scenes are often dynamic. The movement of obstacles increases the complexity of the environment and poses a great challenge to the existing methods. In this work, we approach robust dynamic obstacle avoidance twofold. First, we introduce the neuromorphic vision sensor (i.e., event camera) to provide motion cues complementary to the traditional Laser depth data for handling dynamic obstacles. Second, we develop an DRL-based event-enhanced multimodal spiking actor network (EEM-SAN) that extracts information from motion events data via unsupervised representation learning and fuses Laser and event camera data with learnable thresholding. Experiments demonstrate that our EEM-SAN outperforms state-of-the-art obstacle avoidance methods by a significant margin, especially for dynamic obstacle avoidance.

Digital watermarking technology is a method of embedding specific information in digital images and videos, often used for copyright protection and identity verification. However, unscrupulous users may also use this technique to falsify and tamper with data. Therefore, a reliable watermark attack network is needed to detect and remove watermarks embedded by unscrupulous users. In this paper, we propose a watermarking attack network based on feature pyramid attention, which can effectively remove watermarks embedded in digital images and greatly guarantee the image quality of carrier images. The network consists of two main modules: the feature extraction module and the watermark attack module. In the feature extraction module, we use a convolutional neural network and a residual block to extract the features of the image. Then, in the watermarking attack module, we use the pyramid attention mechanism to focus on the important regions in the feature map and apply the attention weights to the watermarking attack operation. To validate the effectiveness of this network, we conducted experiments using a variety of standard data sets. Experimental results show that the network can effectively attack the watermark information embedded in digital images while guaranteeing the quality of the images after the attack. Overall, the watermarking attack network based on feature pyramid attention proposed in this paper is an effective attack with high imperceptibility that can be applied in the field of digital media protection and security in practical scenarios.

Most matting research resorts to advanced semantics to achieve high-quality alpha mattes, and a direct low-level features combination is usually explored to complement alpha details. However, we argue that appearance-agnostic integration can only provide biased foreground (FG) details and that alpha mattes require different-level feature aggregation for better pixel-wise opacity perception. In this article, we propose an end-to-end hierarchical and progressive attention matting network (HAttMatting++), which can better predict the opacity of the FG from single RGB images without additional input. Specifically, we utilize channel-wise attention (CA) to distill pyramidal features and employ spatial attention (SA) at different levels to filter appearance cues. This progressive attention mechanism can estimate alpha mattes from adaptive semantics and semantics-indicated boundaries. We also introduce a hybrid loss function fusing structural similarity, mean square error, adversarial loss, and sentry supervision to guide the network to further improve the overall FG structure. In addition, we construct a large-scale and challenging image matting dataset comprised of 59,000 training images and 1,000 test images (a total of 646 distinct FG alpha mattes), which can further improve the robustness of our hierarchical and progressive aggregation model. Extensive experiments demonstrate that the proposed HAttMatting++ can capture sophisticated FG structures and achieve state-of-the-art performance with single RGB images as input.

Contexts play an important role in salient object detection (SOD). High-level contexts describe the relations between different parts/objects and thus are helpful for discovering the specific locations of salient objects while low-level contexts could provide the fine detail information for delineating the boundary of the salient objects. However, the way of perceiving/leveraging rich contexts has not been fully investigated by existing SOD works. The common context extraction strategies (e.g., leveraging convolutions with large kernels or atrous convolutions with large dilation rates) do not consider the effectiveness and efficiency simultaneously and may cause sub-optimal solutions. In this paper, we devote to exploring an effective and efficient way to learn rich contexts for accurate SOD. Specifically, we first build a dense context exploration (DCE) module to capture dense multi-scale contexts and further leverage the learned contexts to enhance the features discriminability. Then, we embed multiple DCE modules in an encoder-decoder architecture to harvest dense contexts of different levels. Furthermore, we propose an attentive skip-connection to transmit useful features from the encoder part to the decoder part for better dense context exploration. Finally, extensive experiments demonstrate that the proposed method achieves more superior detection results on the six benchmark datasets than 18 state-of-the-art SOD methods.

Glass is very common in the real world. Influenced by the uncertainty about the glass region and the varying complex scenes behind the glass, the existence of glass poses severe challenges to many computer vision tasks, making glass segmentation as an important computer vision task. Glass does not have its own visual appearances but only transmit/reflect the appearances of its surroundings, making it fundamentally different from other common objects. To address such a challenging task, existing methods typically explore and combine useful cues from different levels of features in the deep network. As there exists a characteristic gap between level-different features, i.e., deep layer features embed more high-level semantics and are better at locating the target objects while shallow layer features have larger spatial sizes and keep richer and more detailed low-level information, fusing these features naively thus would lead to a sub-optimal solution. In this paper, we approach the effective features fusion towards accurate glass segmentation in two steps. First, we attempt to bridge the characteristic gap between different levels of features by developing a Discriminability Enhancement (DE) module which enables level-specific features to be a more discriminative representation, alleviating the features incompatibility for fusion. Second, we design a Focus-and-Exploration Based Fusion (FEBF) module to richly excavate useful information in the fusion process by highlighting the common and exploring the difference between level-different features. Combining these two steps, we construct a Progressive Glass Segmentation Network (PGSNet) which uses multiple DE and FEBF modules to progressively aggregate features from high-level to low-level, implementing a coarse-to-fine glass segmentation. In addition, we build the first home-scene-oriented glass segmentation dataset for advancing household robot applications and in-depth research on this topic. Extensive experiments demonstrate that our method outperforms 26 cutting-edge models on three challenging datasets under four standard metrics. The code and dataset will be made publicly available.

Camouflaged object segmentation (COS) aims to identify objects that are "perfectly" assimilate into their surroundings, which has a wide range of valuable applications. The key challenge of COS is that there exist high intrinsic similarities between the candidate objects and noise background. In this paper, we strive to embrace challenges towards effective and efficient COS. To this end, we develop a bio-inspired framework, termed Positioning and Focus Network (PFNet), which mimics the process of predation in nature. Specifically, our PFNet contains two key modules, i.e., the positioning module (PM) and the focus module (FM). The PM is designed to mimic the detection process in predation for positioning the potential target objects from a global perspective and the FM is then used to perform the identification process in predation for progressively refining the coarse prediction via focusing on the ambiguous regions. Notably, in the FM, we develop a novel distraction mining strategy for the distraction discovery and removal, to benefit the performance of estimation. Extensive experiments demonstrate that our PFNet runs in real-time (72 FPS) and significantly outperforms 18 cutting-edge models on three challenging datasets under four standard metrics.

Training a classifier based on imbalanced data set is considered a great challenge in classification tasks, as classifiers are often "biased" due to highly skewed data distribution and overlapping borderline between different classes. When the imbalanced data appears in the multi-class classification scenario, the classification difficulty increases exponentially. In this paper, we propose an integrated approach to handle imbalanced multi-class classification by combining the population-based sampling method and a multi-expert classifier. In the implementation, we choose the Ant Colony Optimization to realize the sampling process. As for the classifier, the voting mechanism is applied to intensify the weak classifiers. To test the algorithm’s performance, we choose 10 representative imbalanced multi-class data sets from the UCI Machine Learning Repository. G – mean and mAUC are chosen as the metrics. According to the experimental results, the proposed algorithm dominates in 8 data sets and gets a second place in 1 data set when evaluated by G – mean, and ranks first in 3 data sets and top-3 among the most for mAUC.

Governments of the world have invested a lot of manpower and material resources to combat COVID-19 this year. At this moment, the most efficient way that could stop the epidemic is to leverage the contact tracing system to monitor people's daily contact information and isolate the close contacts of COVID-19. However, the contact tracing data usually contains people's sensitive information that they do not want to share with the contact tracing system and government. Conversely, the contact tracing system could perform better when it obtains more detailed contact tracing data. In this article, we treat the process of collecting contact tracing data from a crowdsourcing perspective in order to motivate users to contribute more contact tracing data and propose the incentive algorithm named CovidCrowd. Different from previous works where they ask users to contribute their data voluntarily, the government offers some reward to users who upload their contact tracing data to reimburse the privacy and data processing cost. We formulate the problem as a Stackelberg game and show there exists a Nash equilibrium for any user given the fixed reward value. Then, CovidCrowd computes the optimal reward value which could maximize the utility of the system. Finally, we conduct a large-scale simulation with thousands of users and evaluation with real-world data set. Both results show that CovidCrowd outperforms the benchmarks, e.g., the user participating level is improved by at least 13.2% for all evaluation scenarios.

Following the completion of the human genome project, a large amount of high-throughput bio-data was generated. To analyze these data, massively parallel sequencing, namely next-generation sequencing, was rapidly developed. DNA barcodes are used to identify the ownership between sequences and samples when they are attached at the beginning or end of sequencing reads. Constructing DNA barcode sets provides the candidate DNA barcodes for this application. To increase the accuracy of DNA barcode sets, a particle swarm optimization (PSO) algorithm has been modified and used to construct the DNA barcode sets in this paper. Compared with the extant results, some lower bounds of DNA barcode sets are improved. The results show that the proposed algorithm is effective in constructing DNA barcode sets.