Learning-Driven Extended Variable Neighborhood Search for Signed Graph Partitioning

0
0
0

Learning-Driven Extended Variable Neighborhood Search for Signed Graph Partitioning

Introduction

The signed graph partitioning problem (SGPP) is a fundamental combinatorial optimization problem with significant applications in various domains such as computer vision, social network analysis, and bioinformatics. Given an undirected signed graph, SGPP aims to partition the node set into K (K ≥ 2) pairwise disjoint non-empty subsets, minimizing the sum of negative edge weights within the same subset and positive edge weights across different subsets. This optimization objective ensures that the resulting partition aligns with the principles of structural balance theory, where positive edges represent friendly relationships and negative edges denote adversarial ones.

SGPP is proven to be NP-hard, making exact methods computationally infeasible for large-scale networks. Traditional approaches, including branch-and-bound and integer linear programming, struggle with scalability. Consequently, heuristic algorithms have emerged as practical alternatives, offering a balance between solution quality and computational efficiency. Among these, variable neighborhood search (VNS) has demonstrated promising performance by systematically exploring diverse neighborhood structures to escape local optima. However, existing methods still face challenges in efficiently handling large-scale networks while maintaining high solution quality.

This paper introduces a novel learning-driven extended variable neighborhood search (LDEVNS) algorithm to address these challenges. LDEVNS integrates a fast incremental update strategy, an extended VNS framework, and a reinforcement learning mechanism to guide the search direction. The algorithm is designed to efficiently explore promising regions of the solution space, achieving superior performance in both solution quality and computational time.

Problem Definition

A signed graph G = (V, E, w) consists of a node set V, an edge set E (comprising positive and negative edges, E⁺ and E⁻), and edge weights w. The goal of SGPP is to partition V into K non-overlapping subsets such that the total inconsistency—measured by the sum of intra-subset negative edges and inter-subset positive edges—is minimized.

For example, consider a social network where nodes represent individuals, and edges denote relationships. Positive edges indicate friendships, while negative edges represent conflicts. An optimal partition groups individuals into communities where friendships are maximized within groups and conflicts are minimized between groups. The challenge lies in efficiently computing such partitions for large networks.

Algorithm Design

Initial Solution Construction

LDEVNS begins by generating an initial solution using a relocation heuristic (RH). Starting from a random partition, RH iteratively relocates nodes to improve the objective function. Each node is reassigned to the subset that yields the greatest reduction in inconsistency. This process continues until no further improvements are possible, providing a high-quality starting point for subsequent optimization.

Extended Variable Neighborhood Search (EVNS)

The core of LDEVNS is the extended variable neighborhood search (EVNS), which enhances traditional VNS with advanced strategies:

  1. Neighborhood Operators: The primary operator is the Relocate operation, which moves a node from its current subset to another. This operator generates neighboring solutions by exploring different node reassignments.

  2. Fast Incremental Update Strategy: To avoid recalculating the objective function from scratch after each move, LDEVNS employs a fast incremental update mechanism. Two matrices, Pos edge to part (PtP) and Neg edge to part (NtP), store the sums of positive and negative edge weights between nodes and subsets. When a node is relocated, these matrices are incrementally updated in constant time, significantly improving efficiency.

  3. Perturbation Mechanism: To escape local optima, LDEVNS uses a frequency-based perturbation strategy. Nodes that are rarely moved during the search are randomly reassigned to diversify the search. This approach ensures exploration of distant regions in the solution space.

Reinforcement Learning Mechanism

A key innovation in LDEVNS is the integration of reinforcement learning (RL) to guide the search process:

  1. Group Selection Strategy: A probability matrix PR tracks the likelihood of each node belonging to each subset. During the search, nodes are reassigned either greedily (selecting the subset with the highest probability) or randomly (to maintain exploration).

  2. Probability Update: The RL mechanism rewards nodes that remain in their current subsets and penalizes those that are frequently relocated. This dynamic adjustment helps the algorithm focus on promising regions of the solution space.

  3. Probability Smoothing: To prevent outdated decisions from hindering the search, LDEVNS periodically smooths the probability matrix, reducing the influence of historical data and emphasizing recent trends.

Experimental Evaluation

Benchmark Instances

The performance of LDEVNS was evaluated on 15 large-scale social networks sourced from public datasets such as SNAP and KONECT. These networks range from 3,783 to 138,592 nodes and include diverse structures, ensuring a comprehensive assessment of the algorithm’s capabilities.

Comparative Analysis

LDEVNS was compared against state-of-the-art algorithms: RH, tabu search (TS), and VNS. The evaluation metrics included the best, average, and worst objective values, as well as computational time.

  1. Solution Quality: For small K values (e.g., K = 2), LDEVNS performed comparably to VNS. However, as K increased (K ≥ 8), LDEVNS consistently outperformed all competitors, achieving lower inconsistency values. This superiority became more pronounced with larger K, demonstrating the algorithm’s scalability.

  2. Computational Efficiency: LDEVNS significantly reduced runtime compared to RH, TS, and VNS. For instance, at K = 8, LDEVNS reached its best solution in 1,173.5 seconds, while VNS required 2,312.2 seconds. This efficiency is attributed to the fast incremental updates and RL-guided search.

Effectiveness of Reinforcement Learning

To validate the impact of RL, LDEVNS was compared to a variant without RL (REVNS). The results showed that RL-enhanced LDEVNS achieved better solutions, particularly for larger K values. This confirms that RL effectively guides the search toward high-quality regions, improving both solution quality and convergence speed.

Conclusion

The proposed LDEVNS algorithm represents a significant advancement in solving the signed graph partitioning problem. By combining an extended VNS framework with a fast incremental update strategy and reinforcement learning, LDEVNS achieves superior performance in both solution quality and computational efficiency. Experimental results on large-scale social networks demonstrate its robustness and scalability, particularly for larger partition counts.

Future research could explore further enhancements, such as parallelizing the algorithm for even larger networks or applying LDEVNS to real-world applications like community detection in dynamic social networks. The success of LDEVNS also opens avenues for integrating machine learning techniques into other combinatorial optimization problems.

doi.org/10.19734/j.issn.1001-3695.2024.07.0309

Was this helpful?

0 / 0