Mining Large Independent Sets on Massive Graphs

The Maximum Independent Set problem is fundamental for extracting conflict-free structure from large graphs, with applications in scheduling, recommendation, and network analysis. However, existing heuristics can stagnate when search schedules are fixed and information from past solutions is underused, leading to wasted effort in low-quality regions of the search space. We present ARCIS, an efficient algorithm for mining large independent sets on massive graphs. ARCIS couples two main components. The first is an adaptive restart policy that refreshes exploration when progress slows. The second is Consensus-Guided Vertex Fixing, which restricts the search to the non-consensus region of the graph by fixing vertices consistently observed within a round. The consensus is maintained as a running intersection within each round, and because it is recomputed at every restart, the fixing is reversible. Vertices that later lose support are automatically unfixed and their neighborhoods re-enter the working graph, which corrects occasional mistakes while preserving progress. Experiments on 222 graphs from four benchmark suites show that ARCIS attains the best or tied-best solution quality in most instances while delivering competitive runtime and low variability. Ablation studies isolate the impact of each component, indicating that ARCIS is a practical and robust method for large-scale graph mining.