Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models

Response to # Reviewer Mddl

We sincerely thank you for the detailed evaluation and for highlighting the novelty, architectural soundness, and thorough empirical validation of our proposed framework. We have taken your comments seriously and addressed the theoretical limitations, scalability, and generalization concerns. Specifically, we have added results on new combinatorial tasks (e.g., TSP, network dismantling, network immunization), clarified the impact of MLLM selection, discussed architectural scalability strategies, as well as comparisons with hand-crafted evolutionary operators.

W1: Concern on limited theoretical analysis or formal guarantees

Response:
Thank you for this important comment. Combinatorial optimization on graphs is inherently NP-hard, especially in the context of large-scale and non-linear networks. As such, no existing method including traditional or learning-based heuristics can provide general guarantees of optimality or convergence in these settings. Our primary focus, therefore, is on designing a practical and empirically effective framework that leverages the strengths of MLLMs for structure-aware search, and demonstrates consistent performance improvements across diverse problem domains. The experimental results in our work show that the proposed approach significantly enhances optimization quality compared to both traditional and baseline methods.

We seek your kind understanding that this limitation is not specific to our framework, but reflects a broader challenge shared by all existing work operating on NP-hard problems due to inherent complexity of such kind of problem.

Regarding generalization beyond influence maximization, we have conducted additional experiments on three different tasks (network immunization, TSP, and network dismantling), as detailed in our response to W2 & Q1. These results further support the adaptability of our framework across a wide range of combinatorial problems.

W2 & Q1: Concern on unclear generalizability to other combinatorial graph tasks

Response:
Thank you for your valuable comment. We fully recognize the importance of demonstrating the generalizability of our method. We have added more experiments to show the generalizability of our method as below:

• Network Immunization: A critical problem in network science involving node removal to minimize epidemic spread [5].
• Traveling Salesman Problem (TSP): A classical permutation-based combinatorial problem.
• Network Dismantling: A sequential decision-making problem where nodes are removed to break down a network's connectivity [6].

Due to word limitations, the results for the three additional tasks have been provided in our response to #Reviewer 11CR. We kindly refer you there for full details.

These tasks differ in structure and computational nature, ranging from subset selection to permutation optimization to sequential strategies, thus providing a comprehensive validation of our structure-aware optimization framework’s generality. Moreover, our ensemble layout strategy has also been evaluated in both the network immunization and dismantling tasks, where it consistently demonstrated superior robustness and solution quality compared to single-layout baselines.

Collectively, these new experiments reinforce that our proposed MLLM-based evolutionary optimization framework is broadly applicable across a wide spectrum of combinatorial graph problems, not limited to influence maximization.

W3: Concern on computational cost and scalability of repeated MLLM calls

Response:
Thank you for raising this concern. To date, there are already many interests using LLM to do optimization. As shown in Figure 7, scalability is one of advantages of our methods in term of API call cost.

First, compared to traditional token-based LLM encodings, where input size grows linearly (or worse) with the number of nodes and edges, our visual encoding approach decouples input size from graph scale. Regardless of whether the graph contains 1,000 or 100,000 nodes, the number of tokens used during inference is determined solely by the size of the rendered image, which remains fixed. This leads to a constant token cost per inference, independent of the graph’s scale.

To ensure effective and interpretable visualizations for larger graphs, our framework incorporates a graph sparsification step that selectively retains the most structurally important components. This approach preserves the essential features needed for optimization while keeping the visual input compact and suitable for MLLM processing. As a result, our method achieves both efficient cost and scalability, even when applied to large graphs.

Q2: Question on impact of MLLM choice on search behavior and performance

Response:
Thank you for this insightful question. The choice of multimodal large language model (MLLM) indeed affects both the runtime and the quality of optimization outcomes. As shown in Table 5 in the original manuscript, we observed differences across GPT-4o, Gemini, and Qwen in terms of response latency and solution effectiveness.

• Runtime: Variability mainly stems from differences in external factors such as API server load, rate limits, or backend infrastructure. These are more about system-level variations.
• Search behavior: Each MLLM differs in its visual-textual reasoning ability, prompt understanding, and response precision. These differences fundamentally influence the evolutionary search trajectory, as MLLMs are responsible for mutation and crossover decisions. A more capable model can better interpret graph structure, leading to more effective candidate generation and faster convergence.

Q3: Question on scalability from simplified to large-scale networks

Response:
Thank you for this question. While the simplified networks we visualize may contain as few as 50 nodes and 100 edges, they are not arbitrary samples, but rather structurally representative miniatures of the original networks. This design choice is grounded in the scale-free property of real-world networks [1], where a small subset of high-degree hub nodes governs much of the network’s dynamics, and the majority of nodes contribute marginally. This allows us to sparsify the network while preserving its functional backbone, which is a key contribution of our framework.

Indeed, regardless of the original graph size, whether thousands or millions of nodes, our pipeline can scale by selectively retaining the structurally important components through graph sparsification, keeping the input size manageable for MLLMs while retaining optimization effectiveness.

In our experiments, we work with networks containing up to 36,000+ nodes, which is considered large-scale in the context of evolutionary optimization on graphs, and particularly significant for LLM/MLLM-based methods, where computational constraints are more pronounced.

If scaled further to networks with millions of nodes, the same architectural design
Graph Sparsification → Visualization → MLLM-based Optimization
remains valid. For additional scalability, our framework can be extended with divide-and-conquer techniques, where the network is partitioned into overlapping subgraphs that are optimized independently and later integrated.

Q4: Concern on comparison with traditional or learned EA operators

Response:
Thank you for this insightful question. We have compared our MLLM-driven framework with several state-of-the-art hand-crafted evolutionary optimization methods specifically designed for graph data. The results of this comparison are presented in Table 1 of the main paper and include the following baselines:

• SAEP: IEEE TSMC (2023)
• CoeCo: IEEE TEVC (2023)
• SSR: IEEE TCSS (2022)

Across multiple benchmark networks, our MLLM-based optimization consistently outperforms these hand-crafted methods in terms of solution quality. This result demonstrates the potential of leveraging multimodal large language models as a powerful and generalizable alternative to manually engineered or domain-specific evolutionary operators.

Critically, our current implementation uses a simple and generic EO pipeline, without incorporating advanced mechanisms such as self-adaptive parameter tuning, multi-task optimization, or co-evolution strategies. Thus, our framework is extremely novel in its own rights and fully compatible with these enhancements. We expect that integrating them would further improve performance.

To ensure methodological consistency across different combinatorial tasks, we carefully re-implemented our approach using a unified configuration for all experiments and have updated the results in Table 2 (and Figure 4) of the original submission accordingly, i.e.,

The revised results, obtained under this consistent framework, continue to support our main claims regarding the method’s advantages. We will reflect these updates in the final version accordingly for completeness and reproducibility.

We hope these updates and clarifications address your concerns. Please let us know if any further clarification is needed. We would be grateful if you would consider adjusting your score in light of the extended experiments and improvements.

Reference

[1] "Emergence of scaling in random networks." Science (1999).

Response to #Reviewer Etgw

We sincerely thank you for the comprehensive assessment. We are especially grateful for your recognition of the novelty, motivation alignment, and empirical rigor of our proposed framework. In response to your suggestions, we have conducted a sensitivity analysis on key hyperparameters, added a layout-sensitivity study for the reproduction phase, discussed the running time, and clarified the scalability of our framework.

W1/Q1: Concern on lack of hyperparameter sensitivity analysis in cooperative framework

Response:
Thank you for raising this important point and we appreciate the suggestion to include parameter sensitivity to further improve our work. Among these parameters, the knowledge transfer frequency, i.e., how often elite solutions are exchanged across domains, is the most critical. In our default setting, this parameter is set to every 2 generations, which reflects a balance between sufficient cross-domain communication and preserving local evolutionary stability.

In response, we have conducted a new sensitivity experiment by increasing the transfer interval to every 4 generations. The comparison results are provided in the table below. Our findings indicate that more frequent knowledge transfer (Interval = 2) leads to better optimization performance in most cases, supporting the effectiveness of our proposed cooperative optimization framework.

W2 & Q2: Concern on evaluation using subgraphs instead of full-scale networks

Response:
Thank you for this insightful comment. We would like to clarify that our method does not work on subgraphs (an independent part of the original network). Instead, we apply graph sparsification to the full network, preserving its core structural skeleton, particularly high-impact hub nodes based on the well-researched scale-free property of real-world networks. Importantly, this property ensures that even a reduced representation can retain most of the essential structural and functional characteristics of the original network.

Our sparsified networks are thus not disconnected subgraphs, but rather purposefully constructed simplifications that retain high-fidelity approximations of influence, connectivity, and topology, enabling effective optimization while remaining computationally tractable for MLLMs. This design is fundamental to addressing the scalability challenge posed by large networks when visualized in their entirety. Rendering an entire network with tens of thousands of nodes on a single canvas results in severe visual clutter and degraded MLLM performance, something we explicitly seek to avoid.

To support our scalability claim, we include a comparative experiment where candidate solutions are randomly initialized on the full, unsparsified network, and the sparsified network (as used in our framework). Using the same optimization framework in both cases, we observe that the sparsified version consistently yields better initial solution quality, reinforcing that sparsification not only improves scalability but also enhances optimization performance.

Furthermore, our utilised networks are up to 36,000+ nodes, which are larger than those used in existing LLM/MLLM-based optimization works typically operating on small to medium-sized graphs.

Our method’s scalability stems from its design: a modular pipeline of
Graph Sparsification → Visualization → MLLM-based Optimization,
which we believe is a practical and effective approach for handling large real-world graphs.

W3 & Q3: Concern on missing layout-sensitivity analysis for crossover and mutation

Response:
Thank you for raising this important point. We acknowledge that our original layout-sensitivity analysis focused on the initialization phase, which is a one-time operation and more straightforward to evaluate statistically.

In contrast, crossover and mutation are iterative operations that occur across multiple generations, and their effects are inherently accumulative and interdependent. This makes it challenging to isolate and assess the sensitivity of each reproduction step to layout choice using standard statistical methods. For example, the fitness outcome of a solution after the 1st generation may differ substantially from that after the 10th generation even under the same layout due to the influence of prior evolutionary history. As a result, comparing layouts at the same generation across independent runs does not guarantee a fair or controlled assessment.

As a solution, we have conducted a statistical comparison between single-layout and ensemble approaches across the full optimization process, as shown in Table 2. These results demonstrate that layout differences significantly impact final optimization performance.

W4 & Q4: Concern on missing runtime comparison with traditional EO

Response:
Thank you for raising this important question regarding runtime overhead. As shown in Table 5 of the appendix, the runtime per MLLM-based operation (crossover and mutation) depends on factors such as the model architecture (e.g., GPT-4o) and server load at inference time. These operations are inherently slower than traditional, code-based EOs, which can be executed in milliseconds due to their lightweight nature.

However, it is important to note that traditional EO approaches are not structure-aware unless supplemented with manual, task-specific heuristics or engineered operators. In contrast, our MLLM-based method leverages multimodal perception to guide the search more intelligently, resulting in significantly improved optimization performance, as shown across multiple tasks and datasets.

While we acknowledge the higher computational cost, we seek your kind understanding that this is not just a limitation of our framework, but a general challenge shared by all LLM-based optimization approaches. As multimodal models continue to improve in efficiency, we expect this gap to diminish over time.

We hope these additions and clarifications have addressed your concerns. Please let us know if any further clarification is needed. We kindly request you to consider a score adjustment based on these improvements.

Thank you for your response. I’m especially pleased to see that additional experiments have been included to address the first two concerns regarding hyperparameter sensitivity analysis and scalability. I also appreciate the clarifications provided for the last two concerns. Please incorporate the response into your manuscript.

Response to # Reviewer 11CR

We sincerely thank you for the encouraging comments and for recognizing the novelty and clarity of our framework. In response, we have conducted additional experiments on new varied combinatorial tasks (e.g., TSP, network immunization, dismantling) and addressed your suggestions regarding comparison with other methods.

W1/Q3: Concern on lack of diverse combinatorial task evaluation

Response:
We highly appreciate your suggestion to demonstrate the broader applicability of our framework beyond influence maximization. Please be assured that we have now taken concrete steps to address it by conducting additional experiments on three diverse combinatorial optimization tasks.

Network Immunization
A critical problem in network science involving node removal to minimize epidemic spread [5]. We compared the optimization process across different evolutionary methods with Dolphins and Lesmis (The data can be found in “Network data” collected by Mark Newman). The optimization goal is to maximize the number of immune edges. The results further test our framework’s ability to handle structural node selection problems.

Dolphins:

Lesmis:

Traveling Salesman Problem (TSP)
A classical permutation-based combinatorial problem. Note that in TSP, the layout is fixed by coordinates, rendering the multi-layout ensemble inapplicable. Therefore, we compare the optimization process of normal evolutionary optimization and MLLM-based structure-aware evolutionary optimization to demonstrate that MLLM-guided evolutionary operators can significantly improve search effectiveness. The optimization goal is to minimize the route distance.

Network Dismantling
A sequential decision-making problem where nodes are removed to break down a network's connectivity [6]. Here we use this problem to examine the influence of single-layout and multi-layout to demonstrate the advantage of our ensemble framework. The presented results show the AUC of the largest network component, with the removal process terminating after 25% of the nodes were removed.

These tasks differ greatly in structure and computational nature, ranging from subset selection to permutation optimization to sequential strategies, thus providing a comprehensive validation of our structure-aware optimization framework’s generality and flexibility.

Moreover, our ensemble layout strategy has also been evaluated in both the network immunization and dismantling tasks, where it consistently demonstrated superior robustness and solution quality compared to single-layout baselines. Collectively, these new experiments reinforce that our proposed MLLM-based evolutionary optimization framework is broadly applicable across a wide spectrum of combinatorial graph problems, not limited to influence maximization.

To ensure methodological consistency across different combinatorial tasks, we carefully re-implemented our approach using a unified configuration for all experiments and have updated the results in **Table 2 ** (and **Figure 4 **) of the original submission accordingly (due to the word limit, please refer to the ending section of the response to **#Reviewer Mddl **). The revised results, obtained under this consistent framework, continue to support our main claims regarding the method’s advantages. We will reflect these updates in the final version accordingly for completeness and reproducibility.

W2/Q3: Concern on missing comparison with SOTA GNN-based methods

Response:
Thank you very much for this thoughtful comment. As stated at the end of the introduction, the primary focus of this paper is not about advancing the state-of-the-art in influence maximization itself, but rather on using it (being well-known in network science) as a representative benchmark to demonstrate how MLLMs can serve as evolutionary optimization operators in a novel structure-aware optimization framework.

Our main goal is to explore the integration of MLLMs into evolutionary algorithms, a direction that is applicable to a wide range of combinatorial optimization problems. Due to time constraints and the nature of our work, we seek for your kind understanding that we chose to prioritize demonstrating the generalizability of our framework across multiple tasks as shown in the response to W1.

Moreover, comparing fairly with GNN-based approaches such as GLIE or AutoGNP is non-trivial, as their performance can vary significantly depending on implementation details and task-specific tuning. Similarly, the performance of any evolutionary algorithm including ours can be further improved by tuning hyperparameters like crossover/mutation rates, generation count, and population size. To ensure a controlled evaluation using consistent evolutionary parameters, we compared our method with other evolutionary optimization frameworks under the same settings, as shown in Table 3. The results highlight the superiority of our structure-aware evolutionary operators, in particular because we did not incorporate advanced techniques such as multi-task learning, and instead followed a standard evolutionary optimization pipeline.

Q1: Suggestion for weighted voting instead of uniform consensus

Response:
Thank you for this insightful suggestion. Indeed, incorporating a weighted voting mechanism where weights are derived from the fitness of the best solutions generated by each layout could potentially enhance decision quality in our ensemble framework. This aligns with the broader direction of developing self-adaptive strategies to dynamically balance contributions from different views.

In the current work, our primary goal was to establish the effectiveness of multi-layout ensemble optimization, and to isolate its impact, we deliberately adopted the most straightforward aggregation method, i.e., majority voting. This allowed us to clearly demonstrate that layout diversity alone can significantly improve robustness and performance.

We fully agree that introducing a more sophisticated, adaptive weighting scheme could further enhance our method. New design choices (e.g., how to normalize fitness across layouts, address fitness noise, and ensure consistency during evolution) motivates future work in which a dedicated follow-up study will be conducted. Due to time constraints during the rebuttal phase, we could not include new experimental validation, but we genuinely appreciate this suggestion and plan to explore it in future work.

Q2: Suggestion to compare with single graph-based MLLM for robustness

Response:
Thank you for this valuable question. As shown in Table 2 of the original manuscript, our ensemble method significantly outperforms any single-layout variant (e.g., KK, FR, GraphOpt) across multiple networks. To further strengthen this finding, we also applied the same single-vs-multi layout comparison to two additional tasks, i.e., network immunization and network dismantling as described in our response to W1. The results consistently demonstrate the advantage of layout diversity through ensemble voting.

We hope these updates and clarifications adequately address your comments. Please let us know if any further clarification is needed. We would be grateful if you would consider adjusting your score in light of the improvements provided.

Response to # Reviewer B64q

We sincerely thank you for your constructive feedback and we are glad to hear that you found our approach novel and the paper clearly written. We have carefully addressed all of your concerns via adding new domain experiments (e.g., TSP, network immunization, dismantling), illustrating task generalization, scalability, and dataset size.

W1: Concern on the scope within NeurIPS community

Response:
Thank you very much for this comment. Regarding the alignment with the NeurIPS community: our work builds on a growing interest in combining LLMs with combinatorial and graph reasoning (e.g., [1,2]), and also connects to active lines of research in evolutionary optimization [3] and graph combinatorial optimization [4]. Thus, we believe our contribution is timely and relevant to the NeurIPS audience.

W2 & Q1: Concern on limited task diversity/generalization

Response:
We appreciate the your comment regarding the generazibility of our work. While our primary case study is influence maximization, we would like to emphasize that this was chosen not due to any task-specific limitation, but rather because it serves as a representative task (being well-known in network science) in graph-based combinatorial optimization. We fully acknowledge the importance of demonstrating broader applicability. To address this concern, we have substantially expanded our evaluation to include three additional tasks that vary widely in structure, decision space, and domain characteristics:

• Network Immunization: A critical problem in network science involving node subset removal to minimize epidemic spread [5].

• Traveling Salesman Problem (TSP): A classical permutation-based combinatorial problem to find the shortest route.

• Network Dismantling: A sequential decision-making problem where nodes are removed to break down a network's connectivity [6].

These tasks span diverse types of combinatorial optimization (subset selection, permutation-based ordering, and sequential decision-making), demonstrating that our MLLM-based evolutionary framework is not limited to a narrow task type. Furthermore, our ensemble strategy was evaluated on the network immunization and dismantling tasks, and continues to validate the benefit of layout diversity beyond a single setting.

Due to word limitations, the results for these three additional tasks have been provided in our response to # Reviewer 11CR. We kindly refer you there for full details.

To ensure methodological consistency across different combinatorial tasks, we carefully re-implemented our approach using a unified configuration for all experiments and have updated the results in Table 2 (and Figure 4) of the original submission accordingly (due to the word limit, please refer to the last section of the response to # Reviewer Mddl). The revised results, obtained under this consistent framework, continue to support our main claims regarding the method’s advantages. We will reflect these updates in the final version accordingly for completeness and reproducibility.

W3 & Q2: Concern on limited dataset scale / scalability

Response:
We appreciate the reviewer’s concern regarding scalability. We would like to respectfully clarify that our current study focuses on networks of up to 36,000+ nodes, which is considered large-scale in the context of evolutionary optimization-based graph optimization. This is corroborated by recent literature, such as [7], where the tested networks are of comparable size. Even highly efficient heuristics, like the H-index-based method [8], also operate on networks within this scale.

As supported by Reviewer #Etgw who acknowledged the large scale of the datasets utilized in this paper, we sincerely hope that the Reviewer can re-evaluate our results, particularly when integrating models like MLLMs which introduce additional complexity. Importantly, one of the core contributions of our work is to improve scalability through graph sparsification, motivated by the scale-free nature of real-world networks [9]. This property implies that a small subset of nodes (hubs) play a disproportionately large role, allowing for intelligent reduction strategies without losing essential structural information.

Our framework exploits this through structured sparsification and cooperative optimization, enabling MLLMs to operate effectively even in the presence of high complexity. For a more detailed discussion on computational costs, please refer to our response to W4 & Q3.

W4 & Q3: Concern on MLLM inference cost / scalability

Response:
Thank you very much for this constructive comment. We fully agree that inference with MLLMs can be computationally intensive, particularly on large graphs. Scalability is a central challenge and addressing it is a key motivation behind our framework design.

1. Fixed Input Size via Visual Encoding
   Compared to traditional token-based LLM encodings (please refer to Figure 7 in the original submission), where input size grows linearly (or worse) with the number of nodes and edges, our visual encoding approach decouples input size from graph scale. Regardless of whether a graph has 1,000 or 100,000 nodes, the rendered image size remains fixed (e.g., 1200×1200 pixels, downscaled to 768×768 during GPT-4o inference). This results in constant token cost per inference, independent of network size, which offers a crucial advantage in scaling to larger graphs.

2. Reducing Visual Clutter through Sparsification
   We recognize the visual clutter problem that arises when plotting very large graphs. To address this, we incorporate graph sparsification as a core component of our pipeline. This allows us to retain essential structural features while significantly reducing the visual and computational complexity. The resulting sparsified views are more interpretable and manageable for MLLMs without sacrificing optimization quality.

3. Scalable Modular Pipeline Design
   Our framework is explicitly designed for scalability through the modular pipeline:

   Graph Sparsification → Visualization → MLLM-based Optimization
   

   This design leverages the scale-free nature of real-world networks [9], which implies that a small fraction of influential nodes often govern the network's behavior. By focusing on those structurally critical components, our method remains effective even on networks of much larger size.

4. Future Extensions with Divide-and-Conquer
   For future work, our framework can be extended with a divide-and-conquer strategy, where large networks are partitioned into overlapping subgraphs that are optimized independently and then merged. This aligns with distributed optimization principles and further enhances scalability without increasing MLLM inference cost linearly with graph size. To conclude, our work carefully considers both computational cost by using image-based representations and effectiveness and efficiency by applying graph sparsification.

We hope that our responses and the extended experiments have addressed your concerns. We kindly hope you will consider raising your score based on the revisions and additional evidence provided.

Reference

[1]"Can language models solve graph problems in natural language?" NeurIPS (2023).

[2]"Gita: Graph to visual and textual integration for vision-language graph reasoning." NeurIPS (2024).

[3]"Neuroevobench: Benchmarking evolutionary optimizers for deep learning applications." NeurIPS (2023).

[4]"Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs." NeurIPS (2020).

[5]“The hidden geometry of complex, network-driven contagion phenomena,” Science (2013).

[6] "Network dismantling." PNAS (2016).

[7] "Evolutionary Hypergraph Learning: A Multi-Objective Influence Maximization Approach Considering Seed Selection Costs." IEEE TEVC (2025).

[8] "The H-index of a network node and its relation to degree and coreness." Nature Communications (2016).

[9] "Emergence of scaling in random networks." Science (1999).

Dear Reviewer B64q,

We apologize for reaching out at this stage, as we understand you may be busy with other reviews or commitments.

In our previous rebuttal, due to word limit constraints, we used cross-referencing to present our experimental results across three different tasks in the response to Reviewer 11CR’s concerns regarding generalizability. We are glad to note that Reviewer 11CR has acknowledged our efforts.

For your convenience, we have now presented the experimental results in this new thread. Please kindly find the results below:

Network Immunization

A critical problem in network science involving node removal to minimize epidemic spread. We compared the optimization process across different evolutionary methods with Dolphins and Lesmis (The data can be found in “Network data” collected by Mark Newman). The optimization goal is to maximize the number of immune edges. The results further test our framework’s ability to handle structural node selection problems with global impact.

Dolphins:

Lesmis:

Traveling Salesman Problem (TSP)

A classical permutation-based combinatorial problem. Note that in TSP, the layout is fixed by coordinates, rendering the multi-layout ensemble inapplicable. Therefore, we compare the optimization process of normal evolutionary optimization and MLLM-based structure-aware evolutionary optimization to demonstrate that MLLM-guided evolutionary operators can significantly improve search effectiveness. The optimization goal is to minimize the route distance.

Network Dismantling

A sequential decision-making problem where nodes are removed to break down a network's connectivity. Here we use this problem to examine the influence of single-layout and multi-layout to demonstrate the advantage of our ensemble framework. The presented results show the AUC of the largest network component, with the removal process terminating after 25% of the nodes were removed.

We sincerely hope to engage with you and would greatly appreciate your feedback.

Warm regards,

The Authors of Submission 25561