Model transferability estimation is a task-adaptive pre-trained model selection problem, aiming to determine the optimal model for target dataset from a model hub pre-trained on source dataset without fine-tuning. Although existing model transferability evaluation methods have made some progress, they mainly focus on image or text data in CV and NLP. In contrast, the graph structural data with GNNs models is still underexplored, due to the complexity of the graph structure and the limitations of the generalization ability of GNN models under distribution shift. To fill this blank, we first propose a Graph Neural Network Model Transferability Estimation method via decomposition-augmented discriminant analysis, named GNNMTE, to evaluate the transferability of GNN models on target graph dataset without fine-tuning. It only calculates the GNNMTE score to determine whether it can be effectively transferred to target graph dataset and better select the optimal model for the target graph dataset. Specifically, our proposed \method contains three core components: (1) Dual-block SVD fusion for obtaining the corresponding principal component information; (2) Adaptive weighting by singular value ratio for guiding the extraction of important principal component information on graph data; (3) Graph discriminant analysis for finding the optimal projection direction that separates the classes of graph data. Extensive experimental results on cross-domain graph datasets achieve excellent results, demonstrating powerful superiority.

The minimum vertex cover (MVC) problem is a classic NP-hard combinatorial optimization problem with extensive real-world applications. In this paper, we propose an efficient local search algorithm, InfVC, to solve the MVC in massive graphs, which comprises three ideas. First, we introduce an inference-driven optimization strategy that explores better feasible solutions through inference rules. Second, we develop a structural-determined perturbation strategy that is motivated by the structure features of high-quality solutions, prioritizing high-degree vertices into the candidate solution to guide the search process to some potential high-quality search area. Third, we design a self-adaptive local search framework that dynamically balances exploration and exploitation through a perturbation management mechanism. Extensive experiments demonstrate that InfVC outperforms all the state-of-the-art algorithms on almost massive instances.

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.

The Clique Partitioning Problem (CPP) is essential in graph theory with a number of important applications. Due to its NP-hardness, efficient algorithms for solving this problem are very crucial for practical purposes, and simulated annealing is proved to be effective in state-of-the-art CPP algorithms. However, to make simulated annealing more efficient to solve large-scale CPPs, in this paper, we propose a new iterated simulated annealing algorithm. Several methods are proposed in our algorithm to improve simulated annealing. First, a new configuration checking strategy based on timestamp is presented and incorporated into simulated annealing to avoid search cycles. Afterwards, to enhance the local search ability of simulated annealing and speed up convergence, we combine our simulated annealing with a descent search method to solve the CPP. This method further improves solutions found by simulated annealing, and thus compensates for the local search effect. To further accelerate the convergence speed, we introduce a shrinking factor to decline initial temperature and then propose an iterated local search algorithm based on simulated annealing. Additionally, a restart strategy is adopted when the search procedure converges. Extensive experiments on benchmark instances of the CPP were carried out, and the results suggest that the proposed simulated annealing algorithm outperforms all the existing heuristic algorithms, including five state-of-the-art algorithms. Thus the best-known solutions for 34 instances out of 94 are updated. We also conduct comparative analyses of the proposed strategies and show their effectiveness.

Constraints propagation and backtracking are two basic techniques for solving constraint satisfaction problems (CSPs). During the search for a solution, the variable and value pairs that do not belong to any solution can be discarded by constraint propagation to ensure generalized arc consistency so as to avoid the fruitless search. However, constraint propagation is frequently invoked often with little effect on many CSPs. Much effort has been devoted to predicting when to invoke constraint propagation for solving a CSP; however, no effective approach has been developed for the alldifferent constraint. Here we present a novel theorem for identifying the edges in a value graph of alldifferent constraint whose removal can significantly reduce useless constraint propagation. We prove that if an alternating cycle exists for a prospectively removable edge that represents a variable-value assignment, the edge (and the assignment) can be discarded without constraint propagation. Based on this theorem, we developed a novel optimizing technique for early detection of useless constraint propagation which can be incorporated in any existing algorithm for alldifferent constraint. Our implementation of the new method achieved speedup by a factor of 1-5 over the state-of-art approaches on 93 benchmark problem instances in 8 domains. Furthermore, the new algorithm is scalable well and runs increasingly faster than the existing methods on larger problems.

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.

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.

Crowdsourcing carried out by cyber citizens instead of hired consultants and professionals has become increasingly an appealing solution to test the feature rich and interactive web. Despite having various online crowdsourcing testing services, the benefits of exposure to a wider audience and harnessing the collective efforts of individuals remain uncertain, especially when the quality control is problematic in an open environment. The objective of this paper is to propose a real-time collaborative testing approach (RCTA) to create a productive crowdsourced testing on a dynamic Internet. We implemented a prototype crowdsourcing system XTurk, and carried out a case study, to understand the crowdsourced testers behavior, the trustworthiness, the execution time of test cases and accuracy of feedback. Several experiments are carried out and experimental results validate the quality, efficiency and reliability of the present approach and the positive testing feedback is are shown to outperform the previous methods.

Automated software debugging can have a signifi-cant impact on the cost and quality of software development and maintenance. In recent years, researchers have invested a considerable amount of effort in developing automated techniques, and have demonstrated their effectiveness in helping developers in certain debugging tasks by pinpointing faulty statements. But there is still a gap between examining a faulty statement and understanding root causes of the cor-responding bug. As a step in this direction, we believe good developers have defensive programming in minds and software debugging is a process in search of arguments about why a statement is faulty. Therefore, a fault localization problem is rephrased as a dispute game between statements involved in successful runs and failing runs. A statement is OK if it can always provide arguments against other's blames, whereas a less defensive statement is thought to be faulty. In doing so, we propose a probabilistic dispute graph which is built upon dynamic dependencies between statements and statistics of program runs. Using such a graph, we put executed statements in dispute, compute acceptable statements, and thus figure out faulty statements if they have not strong arguments about their correctness. For empirical purpose, we carry out experiments on the well-known Siemens benchmark, and conclude that our approach not only casts new light on the causes of bugs in various cases, but also is statistically more effective in fault localization than competitors like Tarantula, SOBER, CT and PPDG.

In this paper, we investigate the hybrid tractability of binary Quantified Constraint Satisfaction Problems (QCSPs). First, a basic tractable class of binary QCSPs is identified by using the broken-triangle property. In this class, the variable ordering for the broken-triangle property must be same as that in the prefix of the QCSP. Second, we break this restriction to allow that existentially quantified variables can be shifted within or out of their blocks, and thus identify some novel tractable classes by introducing the broken-angle property. Finally, we identify a more generalized tractable class, i.e., the min-of-max extendable class for QCSPs.