Recently, many machine learning-based approaches that effectively solve graph optimization problems have been proposed. The graph optimization problem is the problem that aims to optimize (maximize or minimize) a quantity that is associated with a graph, such as the Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS) problems. These approaches are usually trained on graphs randomly generated with graph generators or sampled from existing datasets. However, we observe that such training graphs lead to poor testing performance if the testing graphs are not generated analogously, i.e., the generalizability of the models trained on thoserandomly generatedtraining graphs is very limited. To address this critical issue, in this paper, we propose a new framework, namedLearning with Iterative Graph Diversification (LIGD), and formulate a new research problem, namedDiverse Graph Modification Problem (DGMP), that iteratively generate diversified training graphs and train the models that solve graph optimization problems to improve their performance significantly. We propose three approaches to solve DGMP by considering both the performance of the machine learning approaches and the structural properties of the training graphs. In addition, we study a practical case of DGMP, namedDiverse Graph Modification Problem with XOR Diversity (DGMP-XDiv), which considers an XOR-based diversity function. We propose a polynomial-time algorithm namedStructure Diversifying Modification on Edge Score (DMES)to obtain the optimal solution. We also proposeDMES with Efficiency-Boosting Strategies (DMES-EB)to enhance the efficiency of DMES significantly. Experimental results on well-known problems show that our proposed approaches significantly boost the performance of both supervised and reinforcement learning approaches. They produce near-optimal results and significantly outperform the baseline approaches, such as graph augmentation and diffusion-based approaches.

Recently, many machine learning-based approaches that effectively solve graph optimization problems have been proposed. These approaches are usually trained on graphs randomly generated with graph generators or sampled from existing datasets. However, we observe that such training graphs lead to poor testing performance if the testing graphs are not generated analogously, i.e., the generalibility of the models trained on those randomly generated training graphs are very limited. To address this critical issue, in this paper, we propose a new framework, named Learning with Iterative Graph Diversification (LIGD), and formulate a new research problem, named Diverse Graph Modification Problem (DGMP), that iteratively generate diversified training graphs and train the models that solve graph optimization problems to significantly improve their performance. We propose three approaches to solve DGMP by considering both the performance of the machine-learning approaches and the structural properties of the training graphs. Experimental results on well-known problems show that our proposed approaches significantly boost the performance of both supervised and reinforcement learning approaches and produce near-optimal results, significantly outperforming the baseline approaches, such as graph augmentation and deep learning-based graph generation approaches.

With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and efficient ways. Although there are many works for SIoT, they focus on designing the architectures and protocols for SIoT under the specific schemes. How to efficiently utilize the collaboration capability of SIoT to complete complex tasks remains unexplored. Therefore, we propose a new problem family, namely,Task-Optimized SIoT Selection (TOSS), to find the best group of IoT objects for a given set of tasks in the task pool. TOSS aims to select the target SIoT group such that the target SIoT group is able to easily communicate with each other while maximizing the accuracy of performing the given tasks. We propose two problem formulations, namedBounded Communication-loss TOSS (BC-TOSS)andRobustness Guaranteed TOSS (RG-TOSS), for different scenarios and prove that they are both NP-hard and inapproximable. We propose a polynomial-time algorithm with a performance guarantee for BC-TOSS, and an efficient polynomial-time algorithm to obtain good solutions for RG-TOSS. Moreover, as RG-TOSS is NP-hard and inapproximable within any factor, we further proposeStructure-Aware Reinforcement Learning (SARL)to leverage the Graph Convolutional Networks (GCN) and Deep Reinforcement Learning (DRL) to effectively solve RG-TOSS. Further, since we use graph models to simulate the problem instance for DRL, which is different from the real ones, we proposeStructure-Aware Meta Reinforcement Learning (SAMRL)for fast adapting to new domains. Experimental results on multiple real datasets indicate that our proposed algorithms outperform the other deterministic and learning-based baseline approaches.

Deep neural networks have achieved great success on a wide spectrum of applications. However, neural network (NN) mod- els often include a massive number of weights and consume much memory. To reduce the NN model size, we observe that the struc- ture of the weight matrix can be further re-organized for a better compression, i.e., converting the weight matrix to the block diag- onal structure. Therefore, in this paper, we formulate a new re- search problem to consider the structural factor of the weight ma- trix, named Compression with Difference-Minimized Block Diagonal Structure (COMIS), and propose a new algorithm, Memory-Efficient and Structure-Aware Compression (MESA), which effectively prunes the weights into a block diagonal structure to significantly boost the compression rate. Extensive experiments on different models show that MESA achieves 135× to 392× compression rates for different models, which are 1.8 to 3.03 times the compression rates of the state-of-the-art approaches. In addition, our approach provides an in- ference speed-up from 2.6× to 5.1×, a speed-up up to 44% to the state-of-the-art approaches.

Many novel and exhilarating applications emerged in the past decade, thanks to the ubiquity and the volume of data in this big data era. However, large-scale data collection is often expensive and time-consuming, especially in the physical world. To address this issue, in this paper, we study a new research problem, named k-Collector Problem (k- CP), which considers to minimize the data collection time for a set of k data collectors in the road network. We propose a constant- ratio approximation algorithm, called Collective Search Walk Planning (CSP). Moreover, we also discuss different strategies to boost the efficiency of CSP. Experimental results on 3 real datasets show that our proposed CSP algorithm outperforms other baselines in both solution quality and efficiency.