Minghao Yin

AAAI Conference 2026 Conference Paper

Dimension-Aware Active Annotation for Aesthetic Perception via Multi-Agent Human–AI Collaboration

• Ye Zhang
• Jinlong He
• Dongjie Wang
• Yupeng Zhou
• Minghao Yin

To cultivate students' aesthetic development, teachers must objectively interpret and evaluate the artistic qualities and emotional resonance within their paintings—a process known as aesthetic perception. This evaluation process is labor-intensive and susceptible to biases due to variations among individual teachers. Advances in artificial intelligence (AI) motivate the use of AI-driven models to automate and enhance this aesthetic perception task. However, building effective AI-driven aesthetic perception models requires extensive datasets, which are typically labor-intensive and costly to gather. To address this, we propose a novel framework that selectively identifies the most challenging dimensions of aesthetic perception for expert annotation, using AI-generated pseudo-annotations to reduce cost and improve model performance. Our framework integrates a multi-agent active learning strategy to systematically annotate scores across multiple dimensions of aesthetic perception. Initially, we train an aesthetic perception model using a small, manually annotated dataset, establishing primary annotation capabilities. Then, this trained model generates pseudo-annotations for unlabeled data across various aesthetic dimensions (e.g., humor, happiness). To ensure annotation quality and relevance, a multi-agent system evaluates these pseudo-annotations, identifying dimensions requiring expert human input based on metrics such as model estimation confidence. Human experts provide targeted annotations selectively, refining the dataset and guiding an iterative improvement cycle. Through repeated refinement, the model progressively enhances both its predictive accuracy and its automated annotation proficiency. Our optimization approach dynamically balances accuracy, annotation relevance, and human effort. Extensive experiments conducted on two real-world datasets demonstrate the effectiveness of our framework.

JBHI Journal 2026 Journal Article

Graph Clustering-Guided Multi-View Neighborhood-Enhanced Graph Contrastive Learning for Drug-Target Interaction Prediction

• Yaomiao Zhao
• Shaohang Qiao
• Qiao Ning
• Minghao Yin

Drug-target interaction (DTI) identification is of great significance in drug development in various areas, such as drug repositioning and potential drug side effects. Although a great variety of computational methods have been proposed for DTI prediction, it is still a challenge in the face of sparsely correlated drugs or targets. To address the impact of data sparsity on the model, we propose a multi-view neighborhood-enhanced graph contrastive learning approach (MneGCL), which is based on graph clustering according to the adjacency relationship in various similarity networks between drugs or targets, to fully exploit the information of drugs and targets with few corrections. MneGCL first performs semantic clustering of drugs and targets by identifying strongly correlated nodes in the semantic similarity network to construct semantic contrastive prototypes, while simultaneously establishing phenotypic prototypes based on the Gaussian interaction profile kernel similarity. These complementary views are then combined through neighborhood-enhanced contrastive learning to effectively capture latent homogeneous features and enhance representation learning for sparse nodes in heterogeneous graphs, with final predictions generated through a graph autoencoders framework. Comparative experimental results demonstrate that MneGCL achieves superior performance across three benchmark datasets, with particularly notable improvements on the highly sparse DrugBank dataset, showing an average $2. 5 \%$ increase to baseline models. Additional experiments further validate the effectiveness of MneGCL in enriching feature representations for sparsely connected nodes.

TIST Journal 2026 Journal Article

Hierarchical Reinforcement Learning for Energy-Efficient Urban Planning

• Yanan Xiao
• Lu Jiang
• Steven Jige Quan
• Pengfei Wang
• Minghao Yin
• Pengyang Wang

Urban planning plays a pivotal role in fostering sustainable, energy-efficient communities amidst the escalating challenges of climate change and energy crises. However, traditional methods often overlook the hierarchical interdependencies inherent in urban structures, land use configurations, and building design, leading to suboptimal outcomes. Here, we introduce a Hierarchical Energy-Efficient Urban Planning (HEEUP) framework, leveraging hierarchical reinforcement learning (HRL) to integrate decision-making across three tiers: urban structure, land use configuration, and building design. Our approach facilitates collaboration between cascading agents, enabling energy-conscious planning decisions that align with functional and contextual urban demands. Evaluations across real-world datasets from Miami and Albuquerque demonstrate a 7.3% improvement in energy efficiency compared to baseline methods. Furthermore, HEEUP achieves an average 24.52% reduction in computational training time compared to traditional optimization algorithms and generative machine learning models. These findings underscore the potential of HEEUP to significantly advance energy-efficient urban planning, providing a scalable, adaptable paradigm for addressing contemporary sustainability challenges.

AAAI Conference 2026 Conference Paper

Improving Exact Algorithm for Pseudo Boolean Optimization with Two New Phase Selection Heuristics

• Yujiao Zhao
• Yizhan Xiang
• Jiangnan Li
• Yiyuan Wang
• Minghao Yin

Pseudo-Boolean optimization (PBO) problem involves optimizing a linear objective function under linear inequality constraints defined over Boolean variables. PBO is widely used for modeling many combinational optimization problems, particularly in some real-world scenarios. In core-guided CDCL-based exact solvers, the way branching variables are assigned, known as phase selection, significantly affects the solving efficiency. This paper introduces two strategies to enhance solver performance by improving phase selection. Firstly, we design a new phase selection strategy that actively guides variables in the objective function toward assignments closer to the optimal solution. Secondly, to prevent the solver from becoming trapped in local solutions, we propose a reinforcement learning-based rephase mechanism that dynamically updates and resets variable phases. We integrate two phase selection strategies into two state-of-the-art PBO solvers and compare them against top-performing solvers from the PB competitions, using benchmarks from these competitions for assessment. The experimental results show that our solvers outperform the winning solver from the competitions.

KR Conference 2025 System Paper

An Embarrassingly Parallel Model Counter

• Zhenghang Xu
• Minghao Yin
• Jean Marie Lagniez

Model counting (also known as #SAT) is a fundamental problem in knowledge representation and reasoning, with applications ranging from probabilistic inference to formal verification. However, state-of-the-art model counters are limited by computational resources on a single machine. In this paper, we propose a novel distributed framework for model counting, exploiting the embarrassingly parallel nature of the problem. By decomposing the search space into independent subproblems and distributing them across different computation nodes, our approach achieves near-linear scalability on practical instances. Extensive experiments on standard benchmarks demonstrate both the effectiveness and efficiency of our framework.

AAAI Conference 2025 Conference Paper

Beyond Prompt Engineering: A Reinforced Token-Level Input Refinement for Large Language Models

• Guang Huang
• Yanan Xiao
• Lu Jiang
• Minghao Yin
• Pengyang Wang

In the rapidly developing field of automatic text generation and understanding, the quality of input data has been shown to be a key factor affecting the efficiency and accuracy of large language model (LLM) output. With the advent of advanced tools such as ChatGPT, input refinement work has mainly focused on prompt engineering. However, existing methods are often too dependent on specific contexts and are easily affected by individual expert experience and potential biases, limiting their wide applicability in diverse real-world applications. To address this problem, this study develops an Reinforced Token-Level Input Refinement, called RTLIR. We choose to optimize the input data at the fine-grained level of tokens, cleverly preserving the original text structure. Operationally, each state is defined by the token set of the current text, and each action is a binary decision process to decide whether to retain a specific token information. The agent automatically calculates and determines the selection probability of each token based on the current state, thereby optimizing the entire decision process. Through continuous exploration and learning, the agent can autonomously learn to identify the key inputs that have the greatest impact on the generation results and achieve refinement of the input data. In addition, RTLIR is a plug-and-play, LLM-agnostic module that can be used for a wide range of tasks and models. Experimental results show that RTLIR improves the performance of LLM in various input scenarios and tasks, with an average accuracy increase of 6%.

JBHI Journal 2025 Journal Article

CBKG-DTI: Multi-Level Knowledge Distillation and Biomedical Knowledge Graph for Drug-Target Interaction Prediction

• Xiaosa Zhao
• Qixian Wang
• Ye Zhang
• Chenglong He
• Minghao Yin
• Xiaowei Zhao

The prediction of drug-target interactions (DTIs) has emerged as a vital step in drug discovery. Recently, biomedical knowledge graph enables the utilization of multi-omics resources for modelling complex biological systems and further improves overall performance of specific predictive task. However, due to the scale and generalization of biomedical knowledge graph, it is necessary to capture task-specific knowledge from biomedical knowledge graph for DTI prediction. Moreover, although biomedical knowledge graph has rich interactions between biological entities, there still needs to contain unignorable structural information of drugs or targets in the multi-modal fusion manner. To this end, we develop a novel DTI identification framework, CBKG-DTI, which aims to distill task-specific knowledge from the complex knowledge graph to the lightweight DTI prediction model. Specifically, CBKG-DTI first introduces a hierarchy-aware knowledge graph embedding as teacher model to capture semantic hierarchy information of biomedical knowledge graph. Then, to further improve model performance, CBKG-DTI integrates information from multiple aspects such as relational information and structural information by constructing a heterogeneous network and then employs a heterogeneous graph attention network framework as the lightweight student model. Moreover, we design a multi-level distillation mechanism to improve the representation and prediction ability of the lightweight student model via capturing the representation and logit distribution of the teacher model. Finally, we conduct the extensive comparison experiments and can reach the AUC of 0. 9751 and the AUPR of 0. 6310 under 5-fold cross validation. This not only demonstrates the superiority of CBKG-DTI in DTI prediction, but also, more importantly, validate the effectiveness of the framework capturing task-specific knowledge from biomedical knowledge graph.

AAAI Conference 2025 Conference Paper

DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem

• Jiaxin Liang
• Junping Zhou
• Minghao Yin

For many real-world problems, users are often interested not only in finding a single solution but in obtaining a sufficiently diverse collection of solutions. In this work, we consider the Diverse SAT problem, aiming to find a set of diverse satisfying assignments for a given propositional formula. We propose a novel and effective local search algorithm, DiverSAT, to solve the problem. To cope with diversity, we introduce three heuristics and a perturbation strategy based on some relevant information. We conduct extensive experiments on a large number of public benchmarks, collected from semiformal hardware verification, logistics planning, and other domains. The results show that DiverSAT outperforms the existing algorithms on most of these benchmarks.

AIIM Journal 2025 Journal Article

DMHGNN: Double multi-view heterogeneous graph neural network framework for drug-target interaction prediction

• Qiao Ning
• Yue Wang
• Yaomiao Zhao
• Jiahao Sun
• Lu Jiang
• Kaidi Wang
• Minghao Yin

JAIR Journal 2025 Journal Article

Improving Local Search Algorithm for Pseudo Boolean Optimization

• Yujiao Zhao
• Yiyuan Wang
• Yi Chu
• Wenbo Zhou
• Shaowei Cai
• Minghao Yin

Pseudo-Boolean optimization (PBO) is usually used to model combinatorial optimization problems, especially for some real-world applications. Despite its significant importance in both theory and applications, the performance of current PBO solvers is still limited. This paper develops a novel local search algorithm for PBO, which has four main ideas. First, we design a new primary scoring function and a two-level selection strategy to evaluate all candidate variables. Second, we introduce a new weighting scheme to accurately guide the search process toward more promising directions. Third, we propose a novel deep optimization strategy to disturb some search processes. Fourth, an efficient solution space exploration mechanism is applied to help the algorithm jump out of local optimum. We conduct experiments on a broad range of public benchmarks, including three large-scale practical application benchmarks, two benchmarks from PB competitions, an integer linear programming optimization benchmark, a crafted combinatorial benchmark, and a combinatorial optimization knapsack benchmark to compare our proposed algorithm against twelve state-of-the-art competitors, including seven recently-proposed pure stochastic local search PBO solvers, a non-traditional stochastic local search combined with complete oracle, two complete PB solvers, and two mixed integer programming (MIP) solvers. Our proposed algorithm has been shown to perform best on these three real-world benchmarks. On the other five benchmarks, our algorithm shows competitive performance compared to state-of-the-art competitors, and it significantly outperforms all other local search algorithms, indicating that our algorithm greatly advances the state of the art in local search for solving PBO.

AAAI Conference 2025 Conference Paper

Multi-type MOOCs Recommendation: Leveraging Deep Multi-Relational Representation and Hierarchical Reasoning

• Ye Zhang
• Yanqi Gao
• Dongjie Wang
• Yupeng Zhou
• Jinlong He
• Zhaoyang Sun
• Minghao Yin

Massive open online courses (MOOCs) recommendation provides online courses tailored to learners' individual preferences. Existing literature is limited by: 1) Ignoring the interrelations among courses, knowledge concepts, and videos, which leads to suboptimal recommendation performance; 2) Neglecting the hierarchical interactions between learners and components like courses, knowledge concepts, and videos, which makes it difficult to capture learners' intentions accurately. To address them, we propose a novel multi-type MOOCs recommendation framework, which enables multi-type educational content recommendations. This framework includes two important components: multi-relational representation and hierarchical reasoning. Regarding multi-relational representation, we first create two static course-relational and knowledge concept-relational graphs based on domain knowledge and construct a dynamic video-relational graph using learners' browsing historical sequences. Then, we capture the interactions among different components by learning the corresponding embeddings via graph neural networks. Regarding hierarchical reasoning, we implement a hierarchical beam search strategy to narrow down the candidate courses, knowledge concepts, and videos by calculating joint probability. Finally, we introduce an optional layer to increase the diversity and reasonableness of video recommendations by estimating learners' intentions. Extensive experiments are conducted to show the effectiveness, robustness, and interpretability of our method.

AAAI Conference 2025 Conference Paper

Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems

• Jitao Xu
• Yaling Wu
• Hongbo Li
• Minghao Yin

Variable ordering heuristics (VOH) play a central role in solving Constraint Satisfaction Problems (CSP). The performance of different VOHs may vary greatly when solving the same CSP instance, so identifying an efficient candidate VOH for a given CSP has been a key issue in the community. In this study, we propose a prediction-based approach to adaptively select efficient VOHs for different CSPs from a set of candidates. Our work demonstrates that efficient candidate VOHs can be identified by learning from the topology of search trees. Specifically, we propose to represent the topology of a binary search tree by the sequence of the Numbers of Positive Decisions (NPD) made before each failure occurs. Based on the representation, we predict the total failure number of a search tree from its beginning part. When solving a CSP, we run a probing procedure to obtain the NPD sequences generated by candidate VOHs and select an efficient one for the resolution according to the prediction results. Our experiments show that the Long Short Term Memory model and Gradient Boosting Decision Tree models trained with the search trees sampled from easy instances are effective in identifying efficient VOHs for hard instances. The models capture some common structure properties hidden in the search trees of different problems. Our approach outperforms the state-of-the-art adaptive VOHs in terms of the number of solved instances and the PAR2 score of runtime.

SAT Conference 2025 Conference Paper

Scalable Precise Computation of Shannon Entropy

• Yong Lai 0001
• Haolong Tong
• Zhenghang Xu
• Minghao Yin

Quantitative information flow analyses (QIF) are a class of techniques for measuring the amount of confidential information leaked by a program to its public outputs. Shannon entropy is an important method to quantify the amount of leakage in QIF. This paper focuses on the programs modeled in Boolean constraints and optimizes the two stages of the Shannon entropy computation to implement a scalable precise tool PSE. In the first stage, we design a knowledge compilation language called ADD[∧] that combines Algebraic Decision Diagrams and conjunctive decomposition. ADD[∧] avoids enumerating possible outputs of a program and supports tractable entropy computation. In the second stage, we optimize the model counting queries that are used to compute the probabilities of outputs. We compare PSE with the state-of-the-art probabilistic approximately correct tool EntropyEstimation, which was shown to significantly outperform the previous precise tools. The experimental results demonstrate that PSE solved 56 more benchmarks compared to EntropyEstimation in a total of 459. For 98% of the benchmarks that both PSE and EntropyEstimation solved, PSE is at least 10× as efficient as EntropyEstimation.

NeurIPS Conference 2025 Conference Paper

Wukong's 72 Transformations: High-fidelity Textured 3D Morphing via Flow Models

• Minghao Yin
• Yukang Cao
• Kai Han

We present WUKONG, a novel training-free framework for high-fidelity textured 3D morphing that takes a pair of source and target prompts (text or images) as input. Unlike conventional methods -- which rely on manual correspondence matching and deformation trajectory estimation (limiting generalization and requiring costly preprocessing) -- WUKONG leverages the generative prior of flow-based transformers to produce high-fidelity 3D transitions with rich texture details. To ensure smooth shape transitions, we exploit the inherent continuity of flow-based generative processes and formulate morphing as an optimal transport barycenter problem. We further introduce a sequential initialization strategy to prevent abrupt geometric distortions and preserve identity coherence. For faithful texture preservation, we propose a similarity-guided semantic consistency mechanism that selectively retains high-frequency details and enables precise control over blending dynamics. This empowers WUKONG to support both global texture transitions and identity-preserving texture morphing, catering to diverse generation needs. Through extensive quantitative and qualitative evaluations, we demonstrate that WUKONG significantly outperforms state-of-the-art methods, achieving superior results across diverse geometry and texture variations.

EAAI Journal 2024 Journal Article

A local search algorithm with movement gap and adaptive configuration checking for the maximum weighted s-plex problem

• Ruizhi Li
• Ruiqi Xu
• Fangzhou Wang
• Shuli Hu
• Yiyuan Wang
• Minghao Yin
• Hui Li

AAAI Conference 2024 Short Paper

Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract)

• Jiaxin Liang
• Junping Zhou
• Minghao Yin

The Diversified Top-k MaxSAT (DTKMS) problem is an extension of MaxSAT. The objective of DTKMS is to find k feasible assignments of a given formula, such that each assignment satisfies all hard clauses and the k assignments together satisfy the maximum number of soft clauses. This paper presents a local search algorithm, DTKMS-DIA, which incorporates a new approach to generating initial assignments. Experimental results indicate that DTKMS-DIA can achieve attractive performance on 826 instances compared with state-of-the-art solvers.

IJCAI Conference 2024 Conference Paper

Hierarchical Reinforcement Learning for Point of Interest Recommendation

• Yanan Xiao
• Lu Jiang
• Kunpeng Liu
• Yuanbo Xu
• Pengyang Wang
• Minghao Yin

With the increasing popularity of location-based services, accurately recommending points of interest (POIs) has become a critical task. Although existing technologies are proficient in processing time-series data, they fall short when it comes to accommodating the diversity and dynamism in users' POI selections, particularly in extracting key signals from complex historical behaviors. To address this challenge, we introduced the Hierarchical Reinforcement Learning Preprocessing Framework (HRL-PRP), a framework that can be integrated into existing recommendation models to effectively optimize user profiles. The HRL-PRP framework employs a two-tiered decision-making process, where the high-level process determines the necessity of modifying profiles, and the low-level process focuses on selecting POIs within the profiles. Through evaluations on multiple real-world datasets, we have demonstrated that HRL-PRP surpasses existing state-of-the-art methods in various recommendation performance metrics.

IJCAI Conference 2024 Conference Paper

Hierarchical Reinforcement Learning on Multi-Channel Hypergraph Neural Network for Course Recommendation

• Lu Jiang
• Yanan Xiao
• Xinxin Zhao
• Yuanbo Xu
• Shuli Hu
• Pengyang Wang
• Minghao Yin

With the widespread popularity of massive open online courses, personalized course recommendation has become increasingly important due to enhancing users' learning efficiency. While achieving promising performances, current works suffering from the vary across the users and other MOOC entities. To address this problem, we propose hierarchical reinforcement learning with a multi-channel hypergraphs neural network for course recommendation(called HHCoR). Specifically, we first construct an online course hypergraph as the environment to capture the complex relationships and historical information by considering all entities. Then, we design a multi-channel propagation mechanism to aggregate embeddings in the online course hypergraph and extract user interest through an attention layer. Besides, we employ two-level decision-making: the low-level focuses on the rating courses, while the high-level integrates these considerations to finalize the decision. Furthermore, in co-optimization, we design a joint reward function to improve the policy of two-layer agents. Finally, we conducted extensive experiments on two real-world datasets and the quantitative results have demonstrated the effectiveness of the proposed method.

AAAI Conference 2024 Short Paper

MRMLREC: A Two-Stage Approach for Addressing Data Sparsity in MOOC Video Recommendation (Student Abstract)

• Ye Zhang
• Yanqi Gao
• Yupeng Zhou
• Jianan Wang
• Minghao Yin

With the abundance of learning resources available on massive open online courses (MOOCs) platforms, the issue of interactive data sparsity has emerged as a significant challenge.This paper introduces MRMLREC, an efficient MOOC video recommendation which consists of two main stages: multi-relational representation and multi-level recommendation, aiming to solve the problem of data sparsity. In the multi-relational representation stage, MRMLREC adopts a tripartite approach, constructing relational graphs based on temporal sequences, courses-videos relation, and knowledge concepts-video relation. These graphs are processed by a Graph Convolution Network (GCN) and two variant Graph Attention Networks (GAT) to derive representations. A variant of the Long Short-Term Memory Network (LSTM) then integrates these multi-dimensional data to enhance the overall representation. The multi-level recommendation stage introduces three prediction tasks at varying levels—courses, knowledge concepts, and videos—to mitigate data sparsity and improve the interpretability of video recommendations. Beam search (BS) is employed to identify top-β items at each level, refining the subsequent level's search space and enhancing recommendation efficiency. Additionally, an optional layer offers both personalization and diversification modes, ensuring variety in recommended videos and maintaining learner engagement. Comprehensive experiments demonstrate the effectiveness of MRMLREC on two real-world instances from Xuetang X.

IJCAI Conference 2024 Conference Paper

Nukplex: An Efficient Local Search Algorithm for Maximum K-Plex Problem

• Rui Sun
• Yiyuan Wang
• Shimao Wang
• Hui Li
• Ximing Li
• Minghao Yin

The maximum k-plex problem (MKPP) is an significant relaxation version of the maximum clique problem with extensive applications. Recently, lots of researchers have proposed many heuristic algorithms based on various methods to solve the MKPP. In this work, to further improve the performance of solving the MKPP, we propose an efficient local search algorithm based on three main ideas. First, we propose a relaxed bounded configuration checking strategy that considers two kinds of historical searching information to relax the restricted strength of configuration checking and the forbidden condition of candidate vertices for the operation Add, respectively. Second, we present a novel solution information-based vertex selection strategy based on two kinds of solution information to select high-quality candidate vertices. Third, we define the solution core and then introduce a core-based perturbation strategy to help the algorithm jump out of local optima. The experimental results show that the proposed algorithm significantly outperforms the state-of-the-art MKPP algorithms in almost all the instances.

AAAI Conference 2024 Conference Paper

Spatial-Temporal Interplay in Human Mobility: A Hierarchical Reinforcement Learning Approach with Hypergraph Representation

• Zhaofan Zhang
• Yanan Xiao
• Lu Jiang
• Dingqi Yang
• Minghao Yin
• Pengyang Wang

In the realm of human mobility, the decision-making process for selecting the next-visit location is intricately influenced by a trade-off between spatial and temporal constraints, which are reflective of individual needs and preferences. This trade-off, however, varies across individuals, making the modeling of these spatial-temporal dynamics a formidable challenge. To address the problem, in this work, we introduce the "Spatial-temporal Induced Hierarchical Reinforcement Learning" (STI-HRL) framework, for capturing the interplay between spatial and temporal factors in human mobility decision-making. Specifically, STI-HRL employs a two-tiered decision-making process: the low-level focuses on disentangling spatial and temporal preferences using dedicated agents, while the high-level integrates these considerations to finalize the decision. To complement the hierarchical decision setting, we construct a hypergraph to organize historical data, encapsulating the multi-aspect semantics of human mobility. We propose a cross-channel hypergraph embedding module to learn the representations as the states to facilitate the decision-making cycle. Our extensive experiments on two real-world datasets validate the superiority of STI-HRL over state-of-the-art methods in predicting users' next visits across various performance metrics.

AIJ Journal 2023 Journal Article

Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism

• Jiejiang Chen
• Shaowei Cai
• Yiyuan Wang
• Wenhao Xu
• Jia Ji
• Minghao Yin

SAT Conference 2023 Conference Paper

LS-DTKMS: A Local Search Algorithm for Diversified Top-k MaxSAT Problem

• Junping Zhou
• Jiaxin Liang
• Minghao Yin
• Bo He

The Maximum Satisfiability (MaxSAT), an important optimization problem, has a range of applications, including network routing, planning and scheduling, and combinatorial auctions. Among these applications, one usually benefits from having not just one single solution, but k diverse solutions. Motivated by this, we study an extension of MaxSAT, named Diversified Top-k MaxSAT (DTKMS) problem, which is to find k feasible assignments of a given formula such that each assignment satisfies all hard clauses and all of them together satisfy the maximum number of soft clauses. This paper presents a local search algorithm, LS-DTKMS, for DTKMS problem, which exploits novel scoring functions to select variables and assignments. Experiments demonstrate that LS-DTKMS outperforms the top-k MaxSAT based DTKMS solvers and state-of-the-art solvers for diversified top-k clique problem.

AAAI Conference 2023 Conference Paper

Multi-View MOOC Quality Evaluation via Information-Aware Graph Representation Learning

• Lu Jiang
• Yibin Wang
• Jianan Wang
• Pengyang Wang
• Minghao Yin

In this paper, we study the problem of MOOC quality evaluation that is essential for improving the course materials, promoting students' learning efficiency, and benefiting user services. While achieving promising performances, current works still suffer from the complicated interactions and relationships of entities in MOOC platforms. To tackle the challenges, we formulate the problem as a course representation learning task based, and develop an Information-aware Graph Representation Learning(IaGRL) for multi-view MOOC quality evaluation. Specifically, We first build a MOOC Heterogeneous Network (HIN) to represent the interactions and relationships among entities in MOOC platforms. And then we decompose the MOOC HIN into multiple single-relation graphs based on meta-paths to depict multi-view semantics of courses. The course representation learning can be further converted to a multi-view graph representation task. Different from traditional graph representation learning, the learned course representations are expected to match the following three types of validity: (1) the agreement on expressiveness between the raw course portfolio and the learned course representations; (2) the consistency between the representations in each view and the unified representations; (3) the alignment between the course and MOOC platform representations. Therefore, we propose to exploit mutual information for preserving the validity of course representations. We conduct extensive experiments over real-world MOOC datasets to demonstrate the effectiveness of our proposed method.

TIST Journal 2023 Journal Article

Reinforced Explainable Knowledge Concept Recommendation in MOOCs

• Lu Jiang
• Kunpeng Liu
• Yibin Wang
• Dongjie Wang
• Pengyang Wang
• Yanjie Fu
• Minghao Yin

In this article, we study knowledge concept recommendation in Massive Open Online Courses (MOOCs) in an explainable manner. Knowledge concepts, composing course units (e.g., videos) in MOOCs, refer to topics and skills that students are expected to master. Compared to traditional course recommendation in MOOCs, knowledge concepts recommendation has drawn more attention because students’ interests over knowledge concepts can better revealstudents’ real intention in a more refined granularity. However, there are three unique challenges in knowledge concept recommendation: (1) How to design an appropriate data structure to capture complex relationships between knowledge concepts, course units, and other participants (e.g., students, teachers)? (2) How to model interactions between students and knowledge concepts? (3) How to make explainable recommendation results to students? To tackle these challenges, we formulate the knowledge concept recommendation as a reinforcement learning task integrated with MOOC knowledge graph (KG). Specifically, we first construct MOOC KG as the environment to capture all the relationships and behavioral histories by considering all the entities (e.g., students, teachers, videos, courses, and knowledge concepts) on the MOOC provider. Then, to model the interactions between students and knowledge concepts, we train an agent to mimic students’ learning behavioral patterns facing the complex environment. Moreover, to provide explainable recommendation results, we generate recommended knowledge concepts in the format of a path from MOOC KG to indicate semantic reasons. Finally, we conduct extensive experiments on a real-world MOOC dataset to demonstrate the effectiveness of our proposed method.

AAAI Conference 2022 Conference Paper

A Fast Local Search Algorithm for the Latin Square Completion Problem

• Shiwei Pan
• Yiyuan Wang
• Minghao Yin

The Latin square completion (LSC) problem is an important NP-complete problem with numerous applications. Given its theoretical and practical importance, several algorithms are designed for solving the LSC problem. In this work, to further improve the performance, a fast local search algorithm is developed based on three main ideas. Firstly, a reduction reasoning technique is used to reduce the scale of search space. Secondly, we propose a novel conflict value selection heuristic, which considers the history conflicting information of vertices as a selection criterion when more than one vertex have equal values on the primary scoring function. Thirdly, during the search phase, we record previous history search information and then make use of these information to restart the candidate solution. Experimental results show that our proposed algorithm significantly outperforms the stateof-the-art heuristic algorithms on almost all instances in terms of success rate and run time.

AAAI Conference 2022 Short Paper

A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)

• Jun Wu
• Minghao Yin

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique search problem, which extends the DTKC search problem by taking into account the weight of vertices. This problem involves finding at most k maximal weighted cliques that cover maximum weight of vertices with low overlapping in a given graph. In this study, a mixed integer linear program constraint formulation is proposed to model DTKWC search problem and an efficient hybrid evolutionary algorithm (HEA-D) based on some heuristic strategies is proposed to tackle it. Experiments on two sets of 110 graphs show that HEA-D outperforms the state-of-art methods.

IJCAI Conference 2022 Conference Paper

AllSATCC: Boosting AllSAT Solving with Efficient Component Analysis

• Jiaxin Liang
• Feifei Ma
• Junping Zhou
• Minghao Yin

All Solution SAT (AllSAT) is a variant of Propositional Satisfiability, which aims to find all satisfying assignments for a given formula. AllSAT has significant applications in different domains, such as software testing, data mining, and network verification. In this paper, observing that the lack of component analysis may result in more work for algorithms with non-chronological backtracking, we propose a DPLL-based algorithm for solving AllSAT problem, named AllSATCC, which takes advantage of component analysis to reduce work repetition caused by non-chronological backtracking. The experimental results show that our algorithm outperforms the state-of-the-art algorithms on most instances.

AAAI Conference 2022 Conference Paper

An Exact Algorithm with New Upper Bounds for the Maximum k-Defective Clique Problem in Massive Sparse Graphs

• Jian Gao
• Zhenghang Xu
• Ruizhi Li
• Minghao Yin

The Maximum k-Defective Clique Problem (MDCP), as a clique relaxation model, has been used to solve various problems. Because it is a hard computational task, previous works can hardly solve the MDCP for massive sparse graphs derived from real-world applications. In this work, we propose a novel branch-and-bound algorithm to solve the MDCP based on several new techniques. First, we propose two new upper bounds of the MDCP as well as corresponding reduction rules to remove redundant vertices and edges. The proposed reduction rules are particularly useful for massive graphs. Second, we present another new upper bound by counting missing edges between fixed vertices and an unfixed vertex for cutting branches. We perform extensive computational experiments to evaluate our algorithm. Experimental results show that our reduction rules are very effective for removing redundant vertices and edges so that graphs are reduced greatly. Also, our algorithm can solve benchmark instances efficiently, and it has significantly better performance than state-of-the-art algorithms.

IJCAI Conference 2022 Conference Paper

HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem

• Jun Wu
• Chu-Min Li
• Yupeng Zhou
• Minghao Yin
• Xin Xu
• Dangdang Niu

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with extensive applications, which extends the DTKC search problem by taking into account the weight of vertices. In this paper, we formulate DTKWC search problem using mixed integer linear program constraints and propose an efficient hybrid evolutionary algorithm (HEA-D) that combines a clique-based crossover operator and an effective simulated annealing-based local optimization procedure to find high-quality local optima. The experimental results show that HEA-D performs much better than the existing methods on two representative real-world benchmarks.

AAAI Conference 2022 Conference Paper

NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem

• Jiejiang Chen
• Yiyuan Wang
• Shaowei Cai
• Minghao Yin
• Yupeng Zhou
• Jieyu Wu

The maximum k-club problem (MkCP) is an important clique relaxation problem with wide applications. Previous MkCP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named NukCP for the MkCP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking strategy is designed by giving different priorities for the neighborhood in the different levels. Experiments on a broad range of different scale instances show that NukCP significantly outperforms the state-of-the-art MkCP algorithms on most instances in terms of solution quality.

AAAI Conference 2021 Short Paper

Local Search for Diversified Top-k s-plex Search Problem (Student Abstract)

• Jun Wu
• Minghao Yin

The diversified top-k s-plex (DTKSP) search problem aims to find k maximal s-plexes that cover the maximum number of vertices with lower overlapping in a given graph. In this paper, we first formalize the diversified top-k s-plex search problem and prove the NP-hardness of it. Second, we proposed a local search algorithm for solving the diversified topk s-plex search problem based on some novel ideas. Experiments on real-world massive graphs show the effectiveness of our algorithm.

AAAI Conference 2021 Conference Paper

NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem

• Jiejiang Chen
• Shaowei Cai
• Shiwei Pan
• Yiyuan Wang
• Qingwei Lin
• Mengyu Zhao
• Minghao Yin

The maximum quasi-clique problem (MQCP) is an important extension of maximum clique problem with wide applications. Recent heuristic MQCP algorithms can hardly solve large and hard graphs effectively. This paper develops an efficient local search algorithm named NuQClq for the MQCP, which has two main ideas. First, we propose a novel vertex selection strategy, which utilizes cumulative saturation information to be a selection criterion when the candidate vertices have equal values on the primary scoring function. Second, a variant of configuration checking named BoundedCC is designed by setting an upper bound for the threshold of forbidding strength. When the threshold value of vertex exceeds the upper bound, we reset its threshold value to increase the diversity of search process. Experiments on a broad range of classic benchmarks and sparse instances show that NuQ- Clq significantly outperforms the state-of-the-art MQCP algorithms for most instances.

ICAPS Conference 2020 Conference Paper

Contention-Aware Mapping and Scheduling Optimization for NoC-Based MPSoCs

• Rongjie Yan
• Yupeng Zhou
• Anyu Cai
• Changwen Li
• Yige Yan
• Minghao Yin

Network-on-Chip (NoC) has emerged as an alternative interconnecting paradigm in the state-of-the-art multi-core architectures. Its capability of parallel data transfer over various paths increases the possibility of resource contention and causes network congestion. How to avoid contention, as well as to optimize performance and energy consumption becomes a great challenge for system designers. In this paper, we consider spatial and temporal aspects of communication to avoid contention. In spatial aspect, we propose to utilize overlapped communication paths to estimate the degree of contention, such that they can be minimized in mapping stage. In temporal aspect, we sequentialize data transfer with potential contention by introducing additional latency. To optimize the design concerns with the corresponding constraint model, we further provide an efficient algorithm to search for better solutions for the problem, which integrates a local search process into a genetic algorithm and applies various heuristics in initialization and evolution process. Experimentations from random and real-case benchmarks demonstrate the efficiency of our method in multi-objective optimization and the effectiveness of our techniques in avoiding network contention, while keeping performance and energy consumption optimized.

AAAI Conference 2020 Short Paper

Contention-Aware Mapping and Scheduling Optimization for NoC-Based MPSoCs (Student Abstract)

• Yupeng Zhou
• Rongjie Yan
• Anyu Cai
• Yige Yan
• Minghao Yin

We consider spacial and temporal aspects of communication to avoid contention in Network-on-Chip (NoC) architectures. A constraint model is constructed such that the design concerns can be evaluated, and an efficient evolutionary algorithm with various heuristics is proposed to search for better solutions. Experimentations from random benchmarks demonstrate the efficiency of our method in multi-objective optimization and the effectiveness of our techniques in avoiding network contention.

AAAI Conference 2020 Conference Paper

Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining

• Hongbo Li
• Jimmy Lee
• He Mi
• Minghao Yin

Making good decisions at the top of a search tree is important for finding good solutions early in constraint optimization. In this paper, we propose a method employing frequent pattern mining (FPM), a classic datamining technique, to find good subtrees for solving constraint optimization problems. We demonstrate that applying FPM in a small number of random high-quality feasible solutions enables us to identify subtrees containing optimal solutions in more than 55% of problem instances for four real world benchmark problems. The method works as a plugin that can be combined with any search strategy for branch-and-bound search. Exploring the identified subtrees first, the method brings substantial improvements for four efficient search strategies in both total runtime and runtime of finding optimal solutions.

AIJ Journal 2020 Journal Article

SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem

• Yiyuan Wang
• Shaowei Cai
• Jiejiang Chen
• Minghao Yin

IJCAI Conference 2018 Conference Paper

A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs

• Yiyuan Wang
• Shaowei Cai
• Jiejiang Chen
• Minghao Yin

The minimum weight dominating set (MWDS) problem is NP-hard and also important in many applications. Recent heuristic MWDS algorithms can hardly solve massive real world graphs effectively. In this paper, we design a fast local search algorithm called FastMWDS for the MWDS problem, which aims to obtain a good solution on massive graphs within a short time. In this novel local search framework, we propose two ideas to make it effective. Firstly, we design a new fast construction procedure with four reduction rules to cut down the size of massive graphs. Secondly, we propose the three-valued two-level configuration checking strategy to improve local search, which is interestingly a variant of configuration checking (CC) with two levels and multiple values. Experiment results on a broad range of massive real world graphs show that FastMWDS finds much better solutions than state of the art MWDS algorithms.

IJCAI Conference 2018 Conference Paper

An Exact Algorithm for Maximum k-Plexes in Massive Graphs

• Jian Gao
• Jiejiang Chen
• Minghao Yin
• Rong Chen
• Yiyuan Wang

The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.

AAAI Conference 2018 Short Paper

NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem

• Ruizhi Li
• Shaowei Cai
• Shuli Hu
• Minghao Yin
• Jian Gao

The minimum weighted vertex cover (MWVC) problem is a well known combinatorial optimization problem with important applications. This paper introduces a novel local search algorithm called NuMWVC for MWVC based on three ideas. First, four reduction rules are introduced during the initial construction phase. Second, the configuration checking with aspiration is proposed to reduce cycling problem. Moreover, a self-adaptive vertex removing strategy is proposed to save time.

JAIR Journal 2017 Journal Article

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function

• Yiyuan Wang
• Shaowei Cai
• Minghao Yin

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.

IJCAI Conference 2017 Conference Paper

Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function (Extended Abstract)

• Yiyuan Wang
• Shaowei Cai
• Minghao Yin

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.

JAIR Journal 2017 Journal Article

New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition

• Yong Lai
• Dayou Liu
• Minghao Yin

We identify two families of canonical knowledge compilation languages. Both families augment ROBDD with conjunctive decomposition bounded by an integer i ranging from 0 to &infin;. In the former, the decomposition is finest and the decision respects a chain C of variables, while both the decomposition and decision of the latter respect a tree T of variables. In particular, these two families cover the three existing languages ROBDD, ROBDD with as many implied literals as possible, and AND/OR BDD. We demonstrate that each language in the first family is complete, while each one in the second family is incomplete with expressivity that does not decrease with incremental i. We also demonstrate that the succinctness does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i+1)-th language in the first family. For the operating efficiency, on the one hand, we show that the two families of languages support a rich class of tractable logical operations, and particularly the tractability of each language in the second family is not less than that of ROBDD; and on the other hand, we introduce a new time efficiency criterion called rapidity which reflects the idea that exponential operations may be preferable if the language can be exponentially more succinct, and we demonstrate that the rapidity of each operation does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i+1)-th language in the first family. Furthermore, we develop a compiler for the last language in the first family (i = &infin;). Empirical results show that the compiler significantly advances the compiling efficiency of canonical representations. In fact, its compiling efficiency is comparable with that of the state-of-the-art compilers of non-canonical representations. We also provide a compiler for the i-th language in the first family by translating the last language in the first family into the i-th language (i < &infin;). Empirical results show that we can sometimes use the i-th language instead of the last language without any obvious loss of space efficiency.

IJCAI Conference 2017 Conference Paper

New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition (Extended Abstract)

• Yong Lai
• Dayou Liu
• Minghao Yin

We identify two families of canonical representations called ROBDD[/\i^]_C and ROBDD[/\T^, i]_T by augmenting ROBDD with two types of conjunctive decompositions. These representations cover the three existing languages ROBDD, ROBDD with as many implied literals as possible (ROBDD-L_&infin), and AND/OR BDD. We introduce a new time efficiency criterion called rapidity which reflects the idea that exponential operations may be preferable if the language can be exponentially more succinct. Then we demonstrate that the expressivity, succinctness and operation rapidity do not decrease from ROBDD[/\T^, i]_T to ROBDD[/\i^]_C, and then to ROBDD[/\i+1^]_C. We also demonstrate that ROBDD[/\i^]_C (i > 1) and ROBDD[/\T^, i]_T are not less tractable than ROBDD-L_&infin and ROBDD, respectively. Finally, we develop a compiler for ROBDD[/\&infin^]_C which significantly advances the compiling efficiency of canonical representations.

TCS Journal 2017 Journal Article

Two approximate algorithms for model counting

• Jinyan Wang
• Minghao Yin
• Jingli Wu

AAAI Conference 2016 Conference Paper

Two Efficient Local Search Algorithms for Maximum Weight Clique Problem

• Yiyuan Wang
• Shaowei Cai
• Minghao Yin

The Maximum Weight Clique problem (MWCP) is an important generalization of the Maximum Clique problem with wide applications. This paper introduces two heuristics and develops two local search algorithms for MWCP. Firstly, we propose a heuristic called strong configuration checking (SCC), which is a new variant of a recent powerful strategy called configuration checking (CC) for reducing cycling in local search. Based on the SCC strategy, we develop a local search algorithm named LSCC. Moreover, to improve the performance on massive graphs, we apply a low-complexity heuristic called Best from Multiple Selection (BMS) to select the swapping vertex pair quickly and effectively. The BMS heuristic is used to improve LSCC, resulting in the LSCC+BMS algorithm. Experiments show that the proposed algorithms outperform the state-of-the-art local search algorithm MN/TS and its improved version MN/TS+BMS on the standard benchmarks namely DIMACS and BHOSLIB, as well as a wide range of real world massive graphs.

AAAI Conference 2011 Conference Paper

Exact Phase Transitions and Approximate Algorithm of #CSP

• Ping Huang
• Minghao Yin
• Ke Xu

AAAI Conference 2011 Conference Paper

Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems

• Jian Gao
• Minghao Yin
• Junping Zhou

AAAI Conference 2011 Conference Paper

On the Discovery and Utility of Precedence Constraints in Temporal Planning

• Yanmei Hu
• Minghao Yin
• Dunbo Cai

SAT Conference 2011 Conference Paper

Phase Transitions in Knowledge Compilation: An Experimental Study

• Jian Gao 0007
• Minghao Yin
• Ke Xu 0001

Abstract Phase transitions, as a kind of well-known phenomena in artificial intelligence, have attracted a great amount of attention in recent years [1, 2]. Many NP-complete problems, such as random SAT and random Constraint Satisfaction Problems (CSPs), have a critical point that separates overconstrained and underconstrained regions, and soluble-to-insoluble phase transition occurs at this critical point, which is always accompanied with the transitions of CPU runtimes. Both systematic search algorithms and local search algorithms suffer an easy-hard-easy pattern when solving those problems.

AAAI Conference 2010 Conference Paper

New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter

• Junping Zhou
• Minghao Yin
• Chunguang Zhou

The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i. e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1. 1892m ) for #2-SAT and O(1. 4142m ) for #3-SAT, where m is the number of clauses.