Finding Maximum Independent Sets in Dynamic Graphs using Unsupervised Learning

• URL: http://arxiv.org/abs/2505.13754v1
• Date: Mon, 19 May 2025 21:58:22 GMT
• Title: Finding Maximum Independent Sets in Dynamic Graphs using Unsupervised Learning
• Authors: Devendra Parkar, Anya Chaturvedi, Andréa W. Richa, Joshua J. Daymude,
• Abstract summary: We present the first unsupervised learning model for finding Maximum Independent Sets (MaxIS) in dynamic graphs.<n>Our method combines structural learning from graph neural networks (GNNs) with a learned distributed update mechanism.<n>Our model generalizes well on graphs 100x larger than the ones used for training, achieving performance at par with both a greedy technique and a commercial mixed integer programming solver.
• Score: 2.5749046466046903
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first unsupervised learning model for finding Maximum Independent Sets (MaxIS) in dynamic graphs where edges change over time. Our method combines structural learning from graph neural networks (GNNs) with a learned distributed update mechanism that, given an edge addition or deletion event, modifies nodes' internal memories and infers their MaxIS membership in a single, parallel step. We parameterize our model by the update mechanism's radius and investigate the resulting performance-runtime tradeoffs for various dynamic graph topologies. We evaluate our model against state-of-the-art MaxIS methods for static graphs, including a mixed integer programming solver, deterministic rule-based algorithms, and a heuristic learning framework based on dynamic programming and GNNs. Across synthetic and real-world dynamic graphs of 100-10,000 nodes, our model achieves competitive approximation ratios with excellent scalability; on large graphs, it significantly outperforms the state-of-the-art heuristic learning framework in solution quality, runtime, and memory usage. Our model generalizes well on graphs 100x larger than the ones used for training, achieving performance at par with both a greedy technique and a commercial mixed integer programming solver while running 1.5-23x faster than greedy.

Related papers

• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• LLM-Based Multi-Agent Systems are Scalable Graph Generative Models [73.28294528654885]
  GraphAgent-Generator (GAG) is a novel simulation-based framework for dynamic, text-attributed social graph generation.<n>GAG simulates the temporal node and edge generation processes for zero-shot social graph generation.<n>The resulting graphs exhibit adherence to seven key macroscopic network properties, achieving an 11% improvement in microscopic graph structure metrics.
  arXiv  Detail & Related papers  (2024-10-13T12:57:08Z)
• Efficient and Effective Implicit Dynamic Graph Neural Network [42.49148111696576]
  We present Implicit Dynamic Graph Neural Network (IDGNN) a novel implicit neural network for dynamic graphs. A key characteristic of IDGNN is that it demonstrably is well-posed, i.e., it is theoretically guaranteed to have a fixed-point representation.
  arXiv  Detail & Related papers  (2024-06-25T19:07:21Z)
• GraphFM: A Comprehensive Benchmark for Graph Foundation Model [33.157367455390144]
  Foundation Models (FMs) serve as a general class for the development of artificial intelligence systems. Despite extensive research into self-supervised learning as the cornerstone of FMs, several outstanding issues persist. The extent of generalization capability on downstream tasks remains unclear. It is unknown how effectively these models can scale to large datasets.
  arXiv  Detail & Related papers  (2024-06-12T15:10:44Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP) We propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursion call. Annotating comparisons of different graphs concerning their MIS size leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa.
  arXiv  Detail & Related papers  (2023-10-28T10:58:25Z)
• Instant Graph Neural Networks for Dynamic Graphs [18.916632816065935]
  We propose Instant Graph Neural Network (InstantGNN), an incremental approach for the graph representation matrix of dynamic graphs. Our method avoids time-consuming, repetitive computations and allows instant updates on the representation and instant predictions. Our model achieves state-of-the-art accuracy while having orders-of-magnitude higher efficiency than existing methods.
  arXiv  Detail & Related papers  (2022-06-03T03:27:42Z)
• EXPERT: Public Benchmarks for Dynamic Heterogeneous Academic Graphs [5.4744970832051445]
  We present a variety of large scale, dynamic heterogeneous academic graphs to test the effectiveness of models developed for graph forecasting tasks. Our novel datasets cover both context and content information extracted from scientific publications across two communities: Artificial Intelligence (AI) and Nuclear Nonproliferation (NN)
  arXiv  Detail & Related papers  (2022-04-14T19:43:34Z)
• Dynamic Graph Learning-Neural Network for Multivariate Time Series Modeling [2.3022070933226217]
  We propose a novel framework, namely static- and dynamic-graph learning-neural network (GL) The model acquires static and dynamic graph matrices from data to model long-term and short-term patterns respectively. It achieves state-of-the-art performance on almost all datasets.
  arXiv  Detail & Related papers  (2021-12-06T08:19:15Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  We propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT) GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-29T19:55:12Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.