Graph Convolutional Network Aided Inverse Graph Partitioning for Resource Allocation

Optimizing resource allocation is critical to achieving energy-efficient industrial Internet-of-Things (IIoT). Many tasks that require grouping IIoT devices with rich connectivity can be modeled as the well-known graph partitioning problem. However, little attention has been paid to those tasks where nodes with few connections are expected to be clustered together, which is the inverse graph partitioning (IGP) problem. Here, we focus on the IGP problem abstracted from real IIoT applications, such as spectrum allocation. First, we build a unified mathematical model for the IGP problem and analyze its characteristics in detail. Then, a novel optimization approach is proposed to provide compelling solutions, which incorporates a node clustering model based on a graph convolutional network (GCN) and a node swap procedure for local optimization. We compare the proposed approach with various baselines on substantial synthetic and real-world networks. Empirical results show that the proposed approach achieves excellent performance, especially in large networks.