Author name cluster

Zhang-Hua Fu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

ECAI Conference 2025 Conference Paper

Efficient Branch-and-Bound for Submodular Function Maximization Under Knapsack Constraint

Yimin Hao
Yi Zhou 0016
Chao Xu 0002
Zhang-Hua Fu

The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeated computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods.

Details

TMLR Journal 2025 Journal Article

Efficient Training of Multi-task Neural Solver for Combinatorial Optimization

Chenguang Wang
Zhang-Hua Fu
Pinyan Lu
Tianshu Yu

Efficiently training a multi-task neural solver for various combinatorial optimization problems (COPs) has been less studied so far. Naive application of conventional multi-task learning approaches often falls short in delivering a high-quality, unified neural solver. This deficiency primarily stems from the significant computational demands and a lack of adequate consideration for the complexities inherent in COPs. In this paper, we propose a general and efficient training paradigm to deliver a unified combinarotial multi-task neural solver. To this end, we resort to the theoretical loss decomposition for multiple tasks under an encoder-decoder framework, which enables more efficient training via proper bandit task-sampling algorithms through an intra-task influence matrix. By employing theoretically grounded approximations, our method significantly enhances overall performance, regardless of whether it is within constrained training budgets, across equivalent training epochs, or in terms of generalization capabilities, when compared to conventional training schedules. On the real-world datasets of TSPLib and CVRPLib, our method also achieved the best results compared to single task learning and multi-task learning approaches. Additionally, the influence matrix provides empirical evidence supporting common practices in the field of learning to optimize, further substantiating the effectiveness of our approach. Our code is open-sourced and available at \url{https://github.com/LOGO-CUHKSZ/MTL-COP}.

PDF Details

IJCAI Conference 2021 Conference Paper

A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

Hua Jiang
Dongming Zhu
Zhichao Xie
Shaowen Yao
Zhang-Hua Fu

Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing exact algorithms usually implement a branch-and-bound approach that requires a tight upper bound to reduce the search space. In this paper, we propose a new upper bound for MKP, which is a partitioning of the candidate vertex set with respect to the constructing solution. We implement a new branch-and-bound algorithm that employs the upper bound to reduce the number of branches. Experimental results show that the upper bound is very effective in reducing the search space. The new algorithm outperforms the state-of-the-art algorithms significantly on real-world massive graphs, DIMACS graphs and random graphs.

PDF Details DOI

ICRA Conference 2021 Conference Paper

An Efficient Parallel Self-assembly Planning Algorithm for Modular Robots in Environments with Obstacles

Lianxin Zhang
Zhang-Hua Fu
Hengli Liu
Qingquan Liu
Xiaoqiang Ji 0001
Huihuan Qian

Self-assembly has attracted growing interests in modular robotics during past decades. Recent work accelerates the assembly process by parallelizing the docking actions among robots. However, these methods can only apply to ideal environments without obstacles. Otherwise, robots will get trapped during the assembly process, due to the complex scenes with obstacles. This paper presents an efficient parallel assembly planning algorithm for modular robots by taking the surrounding obstacles into consideration. By this algorithm, the docking actions are able to avoid immovable obstacles, and therefore parallel self-assembly of robots can adapt to complex environments. To validate the efficacy and generality, the authors have implemented this algorithm in a grid-world simulation environment with 25 distinct maps. The simulation results show a much higher success rate (more than 80%) of our proposed algorithm compared with the existing parallel self-assembly planning algorithms. Finally, the feasibility of the algorithm is affirmed by a self-assembly experiment on the automated guided vehicles (AGVs).

Details

AAAI Conference 2021 Conference Paper

Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

Zhang-Hua Fu
Kai-Bin Qiu
Hongyuan Zha

For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10, 000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.

PDF Details

AAAI Conference 2021 Conference Paper

Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding

Yi Zhou
Shan Hu
Mingyu Xiao
Zhang-Hua Fu

In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex.

PDF Details

AAAI Conference 2021 Conference Paper

Knowledge Refinery: Learning from Decoupled Label

Qianggang Ding
Sifan Wu
Tao Dai
Hao Sun
Jiadong Guo
Zhang-Hua Fu
Shutao Xia

Recently, a variety of regularization techniques have been widely applied in deep neural networks, which mainly focus on the regularization of weight parameters to encourage generalization effectively. Label regularization techniques are also proposed with the motivation of softening the labels while neglecting the relation of classes. Among them, the technique of knowledge distillation proposes to distill the soft label, which contains the knowledge of class relations. However, this technique needs to pre-train an extra cumbersome teacher model. In this paper, we propose a method called Knowledge Refinery (KR), which enables the neural network to learn the relation of classes on-the-fly without the teacher-student training strategy. We propose the definition of decoupled labels, which consist of the original hard label and the residual label. To exhibit the generalization of KR, we evaluate our method in both fields of computer vision and natural language processing. Our empirical results show consistent performance gains under all experimental settings.

PDF Details

IJCAI Conference 2020 Conference Paper

Communicative Representation Learning on Attributed Molecular Graphs

Ying Song
Shuangjia Zheng
Zhangming Niu
Zhang-Hua Fu
Yutong Lu
Yuedong Yang

Constructing proper representations of molecules lies at the core of numerous tasks such as molecular property prediction and drug design. Graph neural networks, especially message passing neural network (MPNN) and its variants, have recently made remarkable achievements in molecular graph modeling. Albeit powerful, the one-sided focuses on atom (node) or bond (edge) information of existing MPNN methods lead to the insufficient representations of the attributed molecular graphs. Herein, we propose a Communicative Message Passing Neural Network (CMPNN) to improve the molecular embedding by strengthening the message interactions between nodes and edges through a communicative kernel. In addition, the message generation process is enriched by introducing a new message booster module. Extensive experiments demonstrated that the proposed model obtained superior performances against state-of-the-art baselines on six chemical property datasets. Further visualization also showed better representation capacity of our model.

PDF Details DOI

EAAI Journal 2015 Journal Article

A three-phase search approach for the quadratic minimum spanning tree problem

Zhang-Hua Fu
Jin-Kao Hao

Given an undirected graph with costs associated with each edge as well as each pair of edges, the quadratic minimum spanning tree problem (QMSTP) consists of determining a spanning tree of minimum cost. QMSTP is useful to model many real-life network design applications. We propose a three-phase search approach named TPS for solving QMSTP, which organizes the search process into three distinctive phases which are iterated: (1) a descent neighborhood search phase using two move operators to reach a local optimum from a given starting solution, (2) a local optima exploring phase to discover nearby local optima within a given regional area, and (3) a perturbation-based diversification phase to jump out of the current regional search area. TPS also introduces a pre-estimation criterion to significantly improve the efficiency of neighborhood evaluation, and develops a new swap-vertex neighborhood (as well as a swap-vertex based perturbation operator) which prove to be quite powerful for solving a series of special instances with particular structures. Computational experiments based on 7 sets of 659 popular benchmarks show that TPS produces highly competitive results compared to the best performing approaches in the literature. TPS discovers improved best known results (new upper bounds) for 33 open instances and matches the best known results for all the remaining instances. Critical elements and parameters of the TPS algorithm are analyzed to understand its behavior.

Details DOI