pith. sign in

arxiv: 2505.13754 · v3 · submitted 2025-05-19 · 💻 cs.LG · cs.SI

Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs

Devendra Parkar , Anya Chaturvedi , Joshua J. Daymude This is my paper

Pith reviewed 2026-05-22 13:39 UTC · model grok-4.3

classification 💻 cs.LG cs.SI
keywords maximum independent setdynamic graphsunsupervised learninggraph neural networkscombinatorial optimizationlocal updatesapproximation algorithms
0
0 comments X

The pith

Unsupervised learning of local parallel updates enables competitive maximum independent set solutions in dynamic graphs without full re-optimization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an unsupervised learning method for the maximum independent set problem on graphs whose edges are added or deleted over time. It trains a graph neural network to perform a single learned update step that adjusts each node's memory and decides its membership in the set after every change. This single-step mechanism replaces the need to re-solve the full problem from scratch. The results show competitive solution quality on graphs of a few hundred nodes, several times faster runtimes than re-applying static models, and better scaling than other unsupervised methods when tested on graphs one hundred times larger than the training data. Readers may care because many practical networks evolve continuously and repeated full recomputation becomes expensive.

Core claim

The central claim is that a single learned parallel update step, triggered by an edge addition or deletion, can correctly modify node memories and infer updated MaxIS membership without requiring full re-optimization or size-specific retraining, providing a viable alternative to the naive reapplication of static-graph models to dynamic settings by leveraging temporal information.

What carries the argument

A learned distributed update mechanism integrated with graph neural networks that, given an edge addition or deletion event, modifies nodes' internal memories and infers their MaxIS membership in a single, parallel step.

Load-bearing premise

The approach assumes that a single learned parallel update step after each edge change is sufficient to maintain an accurate independent set without restarting the full computation.

What would settle it

Apply the trained model to a sequence of random edge deletions on a 500-node graph and compare the sizes of the produced independent sets against those from an exact MIP solver run after every change; consistently smaller sets by more than 15 percent would indicate the update rule fails to preserve quality.

Figures

Figures reproduced from arXiv: 2505.13754 by Anya Chaturvedi, Devendra Parkar, Joshua J. Daymude.

Figure 1
Figure 1. Figure 1: An overview of our unsupervised learning model for MaxIS on dynamic graphs. Nodes maintain memories (node [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Models’ performance (top), runtime (middle), and [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Node estimates pt(v) of membership in the candidate solution across testing snapshots of the RB-200 dataset. After partitioning these estimates by those above (green) and below (orange) the 0.5 threshold (dashed line), it is clear from each part’s mean estimate (solid line) and standard deviation (shaded region) that all estimates are nearly-one or nearly-zero [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

We present the first unsupervised learning model for Maximum-Independent-Set (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 evaluate our model against a mixed integer programming solver and a breadth of unsupervised and supervised learning models for combinatorial optimization on static graphs. Across dynamic graphs of 200-1,000 nodes, our model achieves approximation ratios that are competitive with the state-of-the-art models while running 1.91-6.70x faster. When generalizing to graphs with 100x more nodes than those used for training, our model produces MaxIS solutions 1.00-1.18x larger than all other unsupervised models, but is outperformed by the state-of-the-art supervised model. These results demonstrate that this novel, unsupervised, update-based learning approach to dynamic combinatorial optimization is a viable alternative to the na\"ive reapplication of analogous models for static graphs, leveraging temporal information to improve neural methods for combinatorial optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the first unsupervised learning model for the Maximum Independent Set (MaxIS) problem on dynamic graphs. It combines GNN structural learning with a learned distributed update mechanism that, upon an edge addition or deletion, modifies node internal memories and infers MaxIS membership in a single parallel step. Experiments on dynamic graphs with 200-1000 nodes report competitive approximation ratios and 1.91-6.70x speedups versus MIP solvers and other static-graph models; the approach also generalizes to graphs 100x larger than the training set, outperforming other unsupervised baselines but trailing the best supervised model.

Significance. If the central claims hold, the work is significant for introducing an unsupervised, update-based paradigm for dynamic combinatorial optimization that avoids naive re-solving of static models. The single-step parallel update and demonstrated generalization to much larger instances could enable efficient real-time handling of evolving graphs in applications such as network design and resource allocation. The unsupervised training and explicit use of temporal edge events represent a clear technical advance over re-application of static solvers.

major comments (2)
  1. [Abstract and Evaluation] The central performance claims (competitive ratios, 1.91-6.70x speedups, and 1.00-1.18x larger solutions on 100x larger graphs) are reported in the abstract and evaluation sections as summarized numbers without error bars, statistical tests, details on training dynamics, or explicit data-split protocols. This absence makes it impossible to assess robustness of the reported speed/quality trade-offs, which are load-bearing for the claim that the single-update approach is a viable alternative to static re-optimization.
  2. [Method (update mechanism)] The weakest assumption—that a single learned parallel update step triggered by an edge event suffices to maintain a valid independent set and competitive approximation quality—is not accompanied by an explicit propagation or global-correction mechanism. In graphs with high-degree vertices or dense regions, an edge deletion can invalidate membership for many nodes simultaneously; without multi-step message passing or a post-update feasibility repair (as used in iterative static GNN solvers), the approximation ratios could degrade on instances where connectivity creates long-range dependencies, directly affecting both the speed claim and the 100x generalization result.
minor comments (2)
  1. Notation for node memories and the precise form of the learned update function should be defined with an equation or pseudocode block to allow readers to distinguish it from standard GNN message passing.
  2. [Evaluation] The manuscript should clarify whether the reported approximation ratios are computed with respect to the MIP optimum or a known upper bound, and whether the same MIP solver settings are used across all baselines.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address each major comment below and indicate planned revisions to improve the manuscript.

read point-by-point responses

  1. Referee: [Abstract and Evaluation] The central performance claims (competitive ratios, 1.91-6.70x speedups, and 1.00-1.18x larger solutions on 100x larger graphs) are reported in the abstract and evaluation sections as summarized numbers without error bars, statistical tests, details on training dynamics, or explicit data-split protocols. This absence makes it impossible to assess robustness of the reported speed/quality trade-offs, which are load-bearing for the claim that the single-update approach is a viable alternative to static re-optimization.

    Authors: We agree that the current presentation of aggregate metrics without error bars, statistical tests, or explicit protocols limits evaluation of robustness. In the revised manuscript we will add standard deviations and error bars computed over multiple independent training runs with different random seeds. We will include statistical significance tests (e.g., paired t-tests) for key comparisons against baselines. The experimental setup section will be expanded to detail the data generation process for dynamic edge events, the train/validation/test split protocols, and how generalization instances were constructed. Training dynamics, including loss curves and convergence behavior, will be added to the main text or supplementary material. These changes will directly strengthen the support for the reported speed/quality claims. revision: yes

  2. Referee: [Method (update mechanism)] The weakest assumption—that a single learned parallel update step triggered by an edge event suffices to maintain a valid independent set and competitive approximation quality—is not accompanied by an explicit propagation or global-correction mechanism. In graphs with high-degree vertices or dense regions, an edge deletion can invalidate membership for many nodes simultaneously; without multi-step message passing or a post-update feasibility repair (as used in iterative static GNN solvers), the approximation ratios could degrade on instances where connectivity creates long-range dependencies, directly affecting both the speed claim and the 100x generalization result.

    Authors: The model is deliberately constructed to perform a single parallel update that combines GNN-derived structural features with the edge event to adjust node memories and infer membership. This design enables the reported speed advantage over re-solving static models. Experiments on 200–1000 node dynamic graphs, including instances with varying densities, show that the learned local rules maintain valid independent sets and competitive approximation ratios. We acknowledge that in graphs with high-degree vertices or dense subgraphs, long-range effects may not be fully resolved in one step. We will add a discussion subsection analyzing the scope of the single-step mechanism, including empirical checks for independent-set validity immediately after updates and any recovery across subsequent events. An optional multi-step ablation will also be reported to quantify the trade-off. These additions will clarify limitations without altering the core contribution. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation chain is self-contained against external benchmarks

full rationale

The paper introduces an unsupervised GNN-based model with a learned single-step parallel update for dynamic MaxIS, trained on graphs of 200-1000 nodes and evaluated via approximation ratios against an external MIP solver plus other published unsupervised and supervised models on both held-out and 100x larger instances. No equation or claim reduces by construction to fitted parameters, self-citations, or ansatzes; the central claim that one update suffices is tested empirically rather than assumed tautologically, and generalization results are measured against independent baselines rather than being forced by the training objective itself.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central performance and generalization claims rest on the assumption that local memory updates suffice for dynamic edge events and on the learned neural parameters that encode both structure and update rules.

free parameters (1)
  • GNN weights and update-mechanism parameters
    Neural network parameters are fitted during unsupervised training on dynamic graph sequences.
axioms (1)
  • domain assumption Edge addition or deletion events can be processed by a single parallel local update to node memories that correctly revises MaxIS membership.
    Invoked in the description of the update mechanism that operates in one step without global re-optimization.

pith-pipeline@v0.9.0 · 5748 in / 1381 out tokens · 47188 ms · 2026-05-22T13:39:21.654299+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · 3 internal anchors

  1. [1]

    Y . Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A Biological Solution to a Fundamental Distributed Computing Problem.Science, 331(6014):183– 185, 2011. doi:10.1126/science.1193210

    work page doi:10.1126/science.1193210 2011

  2. [2]

    S. Ahn, Y . Seo, and J. Shin. Learning What to Defer for Maximum Independent Sets. InProceedings of the 37th International Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pages 134–144, Virtual Event, 2020. Proceedings of Machine Learning Research

    work page 2020

  3. [3]

    M. C. Angelini and F. Ricci-Tersenghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set.Nature Machine Intelligence, 5(1):29–31, 2022. doi:10.1038/s42256-022-00589-y

    work page doi:10.1038/s42256-022-00589-y 2022

  4. [4]

    D. L. Applegate, R. E. Bixby, V . Chvátal, and W. J. Cook. The Traveling Salesman Problem: A Computational Study, volume 17 ofPrinceton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, USA, 2007

    work page 2007

  5. [5]

    Assadi, K

    S. Assadi, K. Onak, B. Schieber, and S. Solomon. Fully Dynamic Maximal Independent Set with Sub- linear in n Update Time. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1919–1936, San Diego, CA, USA,

    work page 1919

  6. [6]

    doi:10.1137/1.9781611975482.116

    Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611975482.116

    work page doi:10.1137/1.9781611975482.116

  7. [7]

    P. W. Battaglia, J. B. Hamrick, V . Bapst, A. Sanchez- Gonzalez, V . Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V . Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y . Li, and R. Pascanu. Relational inductive b...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1806.01261 2018

  8. [8]

    Behnezhad, M

    S. Behnezhad, M. Derakhshan, M. Hajiaghayi, C. Stein, and M. Sudan. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 382–405, Baltimore, MD, USA,

    work page

  9. [9]

    doi:10.1109/FOCS.2019.00032

    IEEE. doi:10.1109/FOCS.2019.00032

    work page doi:10.1109/focs.2019.00032 2019

  10. [10]

    Bengio, A

    Y . Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021. doi:10.1016/j.ejor.2020.07.063

    work page doi:10.1016/j.ejor.2020.07.063 2021

  11. [11]

    Brusca, L

    L. Brusca, L. C. Quaedvlieg, S. Skoulakis, G. Chrysos, and V . Cevher. Maximum Independent Set: Self-Training through Dynamic Programming. InAdvances in Neural Information Processing Systems, volume 36, pages 40637– 40658, New Orleans, LA, USA, 2023. Curran Associates, Inc

    work page 2023

  12. [12]

    Bui-Xuan, A

    B.-M. Bui-Xuan, A. Ferreira, and A. Jarry. Com- puting Shortest, Fastest, and Foremost Journeys in Dynamic Networks.International Journal of Foun- dations of Computer Science, 14(02):267–285, 2003. doi:10.1142/S0129054103001728

    work page doi:10.1142/s0129054103001728 2003

  13. [13]

    Casteigts, P

    A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-Varying Graphs and Dynamic Networks.International Journal of Parallel, Emer- gent and Distributed Systems, 27(5):387–408, 2012. doi:10.1080/17445760.2012.668546

    work page doi:10.1080/17445760.2012.668546 2012

  14. [14]

    Chechik and T

    S. Chechik and T. Zhang. Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 370–381, Baltimore, MD, USA, 2019. IEEE. doi:10.1109/FOCS.2019.00031

    work page doi:10.1109/focs.2019.00031 2019

  15. [15]

    Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling

    J. Chung, C. Gulcehre, K. Cho, and Y . Bengio. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling, 2014. doi:10.48550/arxiv.1412.3555

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1412.3555 2014

  16. [16]

    N. A. Crossley, A. Mechelli, P. E. Vértes, T. T. Winton- Brown, A. X. Patel, C. E. Ginestet, P. McGuire, and E. T. Bullmore. Cognitive relevance of the community structure of the human brain functional coactivation network. Proceedings of the National Academy of Sciences, 110 (28):11583–11588, 2013. doi:10.1073/pnas.1220826110

    work page doi:10.1073/pnas.1220826110 2013

  17. [17]

    H. Dai, E. B. Khalil, Y . Zhang, B. Dilkina, and L. Song. Learning Combinatorial Optimization Algorithms over Graphs. InAdvances in Neural Information Processing Systems, volume 30, pages 1–11, Virtual Event, 2017. Curran Associates, Inc

    work page 2017

  18. [18]

    Donti, D

    P. Donti, D. Rolnick, and Z. Kolter. DC3: A learning method for optimization with hard constraints. InPro- ceedings of the 9th International Conference on Learning Representations, pages 1–17, Virtual Event, 2021

    work page 2021

  19. [19]

    F. V . Fomin and P. Kaski. Exact exponential algo- rithms.Communications of the ACM, 56(3):80–88, 2013. doi:10.1145/2428556.2428575

    work page doi:10.1145/2428556.2428575 2013

  20. [20]

    X. Gao, J. Li, and D. Miao. Dynamic Approximate Maximum Independent Set on Massive Graphs. In2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 1835–1847, Kuala Lumpur, Malaysia, 2022. IEEE. doi:10.1109/ICDE53745.2022.00183

    work page doi:10.1109/icde53745.2022.00183 2022

  21. [21]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., United States, 1979

    work page 1979

  22. [22]

    TorchGeo: Deep learning with geospatial data,

    U. Gunarathna, R. Borovica-Gajic, S. Karunasekera, and E. Tanin. Dynamic graph combinatorial optimization with multi-attention deep reinforcement learning. InProceed- ings of the 30th International Conference on Advances in Geographic Information Systems, pages 1–12, Seattle, W A, USA, 2022. ACM. doi:10.1145/3557915.3560956

    work page doi:10.1145/3557915.3560956 2022

  23. [23]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    work page 2024

  24. [24]

    Hanauer, M

    K. Hanauer, M. Henzinger, and C. Schulz. Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide.ACM Journal of Experimental Algorithmics, 27:1–45, 2022. doi:10.1145/3555806

    work page doi:10.1145/3555806 2022

  25. [25]

    J. Håstad. Clique is hard to approximate within n^(1-ε). InProceedings of 37th Conference on Foundations of Computer Science, pages 627–636, Burlington, VT, USA,

    work page

  26. [26]

    doi:10.1109/SFCS.1996.548522

    IEEE. doi:10.1109/SFCS.1996.548522

    work page doi:10.1109/sfcs.1996.548522 1996

  27. [27]

    Hidaka, Y

    R. Hidaka, Y . Hamakawa, J. Nakayama, and K. Tat- sumura. Correlation-Diversified Portfolio Construction by Finding Maximum Independent Set in Large-Scale Market Graph.IEEE Access, 11:142979–142991, 2023. doi:10.1109/ACCESS.2023.3341422

    work page doi:10.1109/access.2023.3341422 2023

  28. [28]

    Karalias and A

    N. Karalias and A. Loukas. Erd ˝os Goes Neural: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs. InAdvances in Neural Informa- tion Processing Systems, volume 33, pages 40637–40658, Virtual Event, 2020. Curran Associates, Inc

    work page 2020

  29. [29]

    S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart. Representation Learning for Dynamic Graphs: A Survey.Journal of Machine Learning Research, 21(70):1–73, 2020

    work page 2020

  30. [30]

    Kumar, X

    S. Kumar, X. Zhang, and J. Leskovec. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1269–1278, Anchorage, AK, USA, 2019. ACM. doi:10.1145/3292500.3330895

    work page doi:10.1145/3292500.3330895 2019

  31. [31]

    S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck. Finding Near-Optimal Independent Sets at Scale. In2016 Proceedings of the Eigh- teenth Workshop on Algorithm Engineering and Experi- ments (ALENEX), pages 138–150, Arlington, V A, USA,

    work page

  32. [32]

    doi:10.1137/1.9781611974317.12

    Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974317.12

    work page doi:10.1137/1.9781611974317.12

  33. [33]

    Y . Li, J. Guo, R. Wang, H. Zha, and J. Yan. Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimiza- tion. InAdvances in Neural Information Processing Sys- tems, volume 37, pages 30179–30206, Vancouver, Canada,

    work page

  34. [34]

    doi:10.52202/079017-0950

    Curran Associates, Inc. doi:10.52202/079017-0950

    work page doi:10.52202/079017-0950

  35. [35]

    Z. Li, Q. Chen, and V . Koltun. Combinatorial Optimiza- tion with Graph Convolutional Networks and Guided Tree Search. InAdvances in Neural Information Processing Systems, volume 31, pages 1–10, Montréal, Québec, Canada, 2018. Curran Associates, Inc

    work page 2018

  36. [36]

    H. Liu, Y . Zhang, T. Wang, R. Jiang, and Y . Yu. Weighted Graph Clustering via Scale Contraction and Graph Structure Learning. InProceedings of the ACM Web Conference 2026, pages 1004–1014, Dubai, United Arab Emirates, 2026. ACM. doi:10.1145/3774904.3792363

    work page doi:10.1145/3774904.3792363 2026

  37. [37]

    Longa, V

    A. Longa, V . Lachi, G. Santin, M. Bianchini, B. Lepri, P. Lio, F. Scarselli, and A. Passerini. Graph Neural Networks for Temporal Graphs: State of the Art, Open Challenges, and Opportunities.Transactions on Machine Learning Research, pages 1–24, 2023

    work page 2023

  38. [38]

    P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer. DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks. InAdvances in Neural Information Processing Systems, volume 34, pages 21997– 22009, Virtual Event, 2021. Curran Associates, Inc

    work page 2021

  39. [39]

    Pareja, G

    A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. Schardl, and C. Leiserson. EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs.Proceedings of the AAAI Confer- ence on Artificial Intelligence, 34(04):5363–5370, 2020. doi:10.1609/aaai.v34i04.5984

    work page doi:10.1609/aaai.v34i04.5984 2020

  40. [40]

    Y . Peng, B. Choi, and J. Xu. Graph Learning for Combinatorial Optimization: A Survey of State-of-the- Art.Data Science and Engineering, 6(2):119–141, 2021. doi:10.1007/s41019-021-00155-3

    work page doi:10.1007/s41019-021-00155-3 2021

  41. [41]

    J. Robson. Algorithms for maximum independent sets.Journal of Algorithms, 7(3):425–440, 1986. doi:10.1016/0196-6774(86)90032-5

    work page doi:10.1016/0196-6774(86)90032-5 1986

  42. [42]

    Temporal Graph Networks for Deep Learning on Dynamic Graphs

    E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein. Temporal Graph Net- works for Deep Learning on Dynamic Graphs, 2020. doi:10.48550/arxiv.2006.10637

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2006.10637 2020

  43. [43]

    M. J. A. Schuetz, J. K. Brubaker, and H. G. Katzgraber. Combinatorial optimization with physics-inspired graph neural networks.Nature Machine Intelligence, 4(4):367– 377, 2022. doi:10.1038/s42256-022-00468-6

    work page doi:10.1038/s42256-022-00468-6 2022

  44. [44]

    Sun and Y

    Z. Sun and Y . Yang. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. InAdvances in Neural Information Processing Systems, volume 36, pages 3706–3731, New Orleans, LA, USA, 2023. Curran Associates, Inc

    work page 2023

  45. [45]

    R. E. Tarjan and A. E. Trojanowski. Finding a Maximum Independent Set.SIAM Journal on Computing, 6(3): 537–546, 1977. doi:10.1137/0206038

    work page doi:10.1137/0206038 1977

  46. [46]

    Toth and D

    P. Toth and D. Vigo, editors.Vehicle Routing: Problems, Methods, and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2nd edition,

    work page

  47. [47]

    doi:10.1137/1.9781611973594

    work page doi:10.1137/1.9781611973594

  48. [48]

    Trivedi, M

    R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha. DyRep: Learning Representations over Dynamic Graphs. In Proceedings of the 7th International Conference on Learning Representations, pages 1–25, New Orleans, LA, USA, 2019

    work page 2019

  49. [49]

    Wang and P

    H. Wang and P. Li. Unsupervised Learning for Combina- torial Optimization Needs Meta Learning. InProceedings of the 11th International Conference on Learning Repre- sentations, pages 1–18, Kigali, Rwanda, 2023

    work page 2023

  50. [50]

    H. Wang, N. Wu, H. Yang, C. Hao, and P. Li. Unsu- pervised Learning for Combinatorial Optimization with Principled Objective Relaxation. InAdvances in Neural Information Processing Systems, volume 35, pages 31444– 31458, New Orleans, LA, USA, 2022. Curran Associates, Inc

    work page 2022

  51. [51]

    Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A Comprehensive Survey on Graph Neural Networks.IEEE Transactions on Neural Networks and Learning Systems, 32(1):4–24, 2020. doi:10.1109/TNNLS.2020.2978386

    work page doi:10.1109/tnnls.2020.2978386 2020

  52. [52]

    Xiao and H

    M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set.Information and Computation, 255(1):126–146, 2017. doi:10.1016/j.ic.2017.06.001

    work page doi:10.1016/j.ic.2017.06.001 2017

  53. [53]

    D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan. Inductive representation learning on temporal graphs. InProceedings of the 8th International Conference on Learning Representations, pages 1–19, Virtual Event, 2020

    work page 2020

  54. [54]

    M. Yau, N. Karalias, E. Lu, J. Xu, and S. Jegelka. Are Graph Neural Networks Optimal Approxima- tion Algorithms? InAdvances in Neural Informa- tion Processing Systems, volume 37, pages 73124– 73181, Vancouver, Canada, 2024. Curran Associates, Inc. doi:10.52202/079017-2328

    work page doi:10.52202/079017-2328 2024

  55. [55]

    L. Yu, L. Sun, B. Du, and W. Lv. Towards Better Dynamic Graph Learning: New Architecture and Unified Library. InAdvances in Neural Information Processing Systems, volume 36, pages 67686–67700, New Orleans, LA, USA,

    work page

  56. [56]

    Curran Associates, Inc

    work page

  57. [57]

    Zhang, H

    D. Zhang, H. Dai, N. Malkin, A. C. Courville, Y . Bengio, and L. Pan. Let the Flows Tell: Solving Graph Combina- torial Problems with GFlowNets. InAdvances in Neural Information Processing Systems, volume 36, pages 11952– 11969, New Orleans, LA, USA, 2023. Curran Associates, Inc

    work page 2023

  58. [58]

    Zhang, H

    S. Zhang, H. Tong, J. Xu, and R. Maciejewski. Graph convolutional networks: A comprehensive re- view.Computational Social Networks, 6(1):11, 2019. doi:10.1186/s40649-019-0069-y

    work page doi:10.1186/s40649-019-0069-y 2019

  59. [59]

    Zheng, C

    W. Zheng, C. Piao, H. Cheng, and J. X. Yu. Computing a Near-Maximum Independent Set in Dynamic Graphs. In2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 76–87, Macau, China, 2019. IEEE. doi:10.1109/ICDE.2019.00016. APPENDIX A. Model Pseudocode Algorithms 1–3 show pseudocode for our model’s initial MaxIS generation procedure, upda...

    work page doi:10.1109/icde.2019.00016 2019