Mining Large Independent Sets on Massive Graphs

• URL: http://arxiv.org/abs/2208.07777v4
• Date: Tue, 28 Oct 2025 11:42:26 GMT
• Title: Mining Large Independent Sets on Massive Graphs
• Authors: Yu Zhang, Witold Pedrycz, Chanjuan Liu, Enqiang Zhu,
• Abstract summary: ARCIS is an efficient algorithm for mining large independent sets on massive graphs.<n>We show that ARCIS attains the best or tied-best solution quality in most instances.
• Score: 47.21699378695116
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Dynamic Deep Graph Learning for Incomplete Multi-View Clustering with Masked Graph Reconstruction Loss [26.31060859315329]
  We propose a novel textbfDynamic Deep textbfGraph Learning for textbfIncomplete textbfMulti-textbfView textbfView textbfClustering with textbfMasked Graph Reconstruction Loss (DGIMVCM)<n>A graph convolutional embedding layer is then designed to extract primary features and refined dynamic view-specific graph structures, leveraging the global graph for imputation of missing views.
  arXiv  Detail & Related papers  (2025-11-14T11:26:38Z)
• On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU [14.338954144116759]
  Graph-based Approximate Nearest Neighbor Search (ANNS) has become the dominant paradigm for modern AI applications.<n>We present the first systematic investigation of graph reordering effects for graph-based ANNS on a GPU.
  arXiv  Detail & Related papers  (2025-08-21T10:50:49Z)
• A Reduction-Driven Local Search for the Generalized Independent Set Problem [29.094247069747073]
  We present a reduction-driven local search (RLS) algorithm that integrates these reduction rules into the pre-processing, the initial solution generation, and the local search components.<n>The RLS is empirically evaluated on 278 graphs arising from different application scenarios.<n>It achieves significantly superior solutions compared to other known solvers, and it effectively provides solutions for graphs exceeding 260 million edges.
  arXiv  Detail & Related papers  (2025-05-27T11:39:05Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Learning-guided iterated local search for the minmax multiple traveling salesman problem [13.924692115320553]
  We propose a leaning-driven iterated local search approach to the minmax multiple traveling salesman problem. We show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances.
  arXiv  Detail & Related papers  (2024-03-19T02:57:10Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems. An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  Quality-Diversity (QD) algorithms aim to find a set of high-performing, yet diverse solutions. This paper tries to shed some light on the optimization ability of QD algorithms via rigorous running time analysis.
  arXiv  Detail & Related papers  (2024-01-19T07:40:24Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  Constraint Problems Optimization (COP) pose intricate challenges in problems usually addressed through Branch and Bound (B&B) methods. We propose a novel neural network algorithm based on a depth-first search algorithm for solving COP. Our method identifies feasible solutions with a gap of less than 17.63% within the initial 5 feasible solutions.
  arXiv  Detail & Related papers  (2023-12-26T03:09:08Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
  Best subset selection is considered the gold standard' for many learning problems. In this paper, we investigate the dual forms of a family of $ell$-regularized problems. An efficient primal-dual method has been developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2022-07-05T14:07:52Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Graph Denoising with Framelet Regularizer [25.542429117462547]
  This paper tailors regularizers for graph data in terms of both feature and structure noises. Our model achieves significantly better performance compared with popular graph convolutions even when the graph is heavily contaminated.
  arXiv  Detail & Related papers  (2021-11-05T05:17:23Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one. Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
  arXiv  Detail & Related papers  (2021-03-19T11:18:03Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  Real-world applications typically require finding good solutions early in the search to enable fast decision-making. We propose the first data-driven framework for schedulings in an exact MIP solver. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
  arXiv  Detail & Related papers  (2021-03-18T14:49:52Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.