An Experimental Study of Variable Neighborhood Search for General-Purpose Subgraph Optimization in Parallel Systems
Resumo
Many network analysis tasks over large graphs involve finding subgraphs that optimize a given scoring function. Scoring functions are defined according to the analysis objective and thus, they can be very diverse (e.g. high density, high reachability, high entropy). In this context we study the Connected Subgraph Optimization Problem (CSOP) in which the goal is to find a subgraph that optimizes a given scoring function within a graph. Such tasks are computationally intensive since (i) they require handling an exponential search space over large graphs and (ii) they involve very skewed and sparse real graphs, which is why algorithm scalability and efficiency are central for feasibility. In this work we provide an experimental characterization of the potential of Variable Neighborhood Search metaheuristic (VNS) in providing a competitive and efficient parallel framework for the CSOP problem. Our results show that VNS offers competitive, near-ideal scalability for accelerating CSOP, but its effectiveness can be limited by expensive scoring functions, branch mispredictions, and both backend and frontend CPU bottlenecks.
Referências
Boob, D., Gao, Y., Peng, R., Sawlani, S., Tsourakakis, C., Wang, D., and Wang, J. (2020). Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020, WWW ’20, page 573–583, New York, NY, USA. Association for Computing Machinery.
Chagas, G. O., Lorena, L. A., dos Santos, R. D., Renaud, J., and Coelho, L. C. (2024). A parallel variable neighborhood search for α-neighbor facility location problems. Computers & Operations Research, 165:106589.
Chen, H., Liu, M., Zhao, Y., Yan, X., Yan, D., and Cheng, J. (2018). G-miner: An efficient task-oriented graph mining system. In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18.
Cheng, X., Dale, C., and Liu, J. (2008). Dataset for “statistics and social network of youtube videos”. [link].
Crainic, T. (2018). Parallel metaheuristics and cooperative search. In Handbook of metaheuristics, pages 419–451. Springer.
Dias, V., Teixeira, C. H. C., Guedes, D., Meira Jr., W., and Parthasarathy, S. (2019). Fractal: A general-purpose graph pattern mining system. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD).
Elfarouk, H., Kent, Q., and Chandra, C. (2022). Faster and scalable algorithms for densest subgraph and decomposition. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA. Curran Associates Inc.
Elseidy, M., Abdelhamid, E., Skiadopoulos, S., and Kalnis, P. (2014). Grami: Frequent subgraph and pattern mining in a single large graph. Proc. VLDB Endow., 7(7):517–528.
Galhotra, S., Bagchi, A., Bedathur, S., Ramanath, M., and Jain, V. (2015). Tracking the conductance of rapidly evolving topic-subgraphs. Proc. VLDB Endow., 8(13):2170–2181.
Hall, B. H., Jaffe, A. B., and Trajtenberg, M. (2001). The nber patent citation data file: Lessons, insights and methodological tools. Working Paper 8498, National Bureau of Economic Research.
Hooi, B., Shin, K., Lamba, H., and Faloutsos, C. (2020). Telltail: Fast scoring and detection of dense subgraphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):4150–4157.
Jamshidi, K., Mahadasa, R., and Vora, K. (2020). Peregrine: A pattern-aware graph mining system. In Proceedings of the Fifteenth European Conference on Computer Systems, EuroSys ’20, New York, NY, USA. Association for Computing Machinery.
Jiang, J., Yao, S., Li, Y., Wang, Q., He, B., and Chen, M. (2025). Dupin: A parallel framework for densest subgraph discovery in fraud detection on massive graphs. Proc. ACM Manag. Data, 3(3).
Letsios, M., Balalau, O. D., Danisch, M., Orsini, E., and Sozio, M. (2016). Finding heaviest k-subgraphs and events in social media. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pages 113–120.
Ma, H., Guan, S., Toomey, C., and Wu, Y. (2022). Diversified subgraph query generation with group fairness. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM ’22, page 686–694, New York, NY, USA. Association for Computing Machinery.
Mawhirter, D. and Wu, B. (2019). Automine: Harmonizing high-level abstraction and high performance for graph mining. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, pages 509–523, New York, NY, USA. ACM.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100.
Oettershagen, L., Wang, H., and Gionis, A. (2024). Finding densest subgraphs with edgecolor constraints. In Proceedings of the ACM Web Conference 2024, WWW ’24, page 936–947, New York, NY, USA. Association for Computing Machinery.
Song, A. and Wu, G. (2025). Rems: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems. arXiv preprint arXiv:2505.17108.
Sze, J. F., Salhi, S., and Wassan, N. (2024). An adaptive variable neighbourhood search approach for the dynamic vehicle routing problem. Computers & Operations Research, 164:106531.
Teixeira, C. H. C., Fonseca, A. J., Serafini, M., Siganos, G., Zaki, M. J., and Aboulnaga, A. (2015). Arabesque: a system for distributed graph mining. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP ’15. ACM.
Tsourakakis, C. E. (2014). A novel approach to finding near-cliques: The triangle-densest subgraph problem. CoRR, abs/1405.1477.
Wickrama Arachchi, C., Kumpulainen, I., and Tatti, N. (2024). Dense subgraph discovery meets strong triadic closure. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 3334–3344, New York, NY, USA. Association for Computing Machinery.
Xavier, E. (2019). Uma interface de programação de aplicações para o brkga na plataforma cuda. In Anais do XX Simpósio em Sistemas Computacionais de Alto Desempenho, pages 13–24, Porto Alegre, RS, Brasil. SBC.
Xu, Y., Ma, C., Fang, Y., and Bao, Z. (2023). Efficient and effective algorithms for generalized densest subgraph discovery. Proc. ACM Manag. Data, 1(2).
Yang, J. and Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, New York, NY, USA. Association for Computing Machinery.
Yasin, A. (2014). A top-down method for performance analysis and counters architecture. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 35–44.
Ye, X., Li, R.-H., Liang, L., Liu, Z., Lin, L., and Wang, G. (2024). Efficient and effective anchored densest subgraph search: A convex-programming based approach. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 3907–3918, New York, NY, USA. Association for Computing Machinery.
Zhao, J. and Hifi, M. (2025). Reinforcement learning-enhanced variable neighborhood search strategies for the k-clustering minimum biclique completion problem. Computers & Operations Research, 178:107008.
Chagas, G. O., Lorena, L. A., dos Santos, R. D., Renaud, J., and Coelho, L. C. (2024). A parallel variable neighborhood search for α-neighbor facility location problems. Computers & Operations Research, 165:106589.
Chen, H., Liu, M., Zhao, Y., Yan, X., Yan, D., and Cheng, J. (2018). G-miner: An efficient task-oriented graph mining system. In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18.
Cheng, X., Dale, C., and Liu, J. (2008). Dataset for “statistics and social network of youtube videos”. [link].
Crainic, T. (2018). Parallel metaheuristics and cooperative search. In Handbook of metaheuristics, pages 419–451. Springer.
Dias, V., Teixeira, C. H. C., Guedes, D., Meira Jr., W., and Parthasarathy, S. (2019). Fractal: A general-purpose graph pattern mining system. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD).
Elfarouk, H., Kent, Q., and Chandra, C. (2022). Faster and scalable algorithms for densest subgraph and decomposition. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA. Curran Associates Inc.
Elseidy, M., Abdelhamid, E., Skiadopoulos, S., and Kalnis, P. (2014). Grami: Frequent subgraph and pattern mining in a single large graph. Proc. VLDB Endow., 7(7):517–528.
Galhotra, S., Bagchi, A., Bedathur, S., Ramanath, M., and Jain, V. (2015). Tracking the conductance of rapidly evolving topic-subgraphs. Proc. VLDB Endow., 8(13):2170–2181.
Hall, B. H., Jaffe, A. B., and Trajtenberg, M. (2001). The nber patent citation data file: Lessons, insights and methodological tools. Working Paper 8498, National Bureau of Economic Research.
Hooi, B., Shin, K., Lamba, H., and Faloutsos, C. (2020). Telltail: Fast scoring and detection of dense subgraphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):4150–4157.
Jamshidi, K., Mahadasa, R., and Vora, K. (2020). Peregrine: A pattern-aware graph mining system. In Proceedings of the Fifteenth European Conference on Computer Systems, EuroSys ’20, New York, NY, USA. Association for Computing Machinery.
Jiang, J., Yao, S., Li, Y., Wang, Q., He, B., and Chen, M. (2025). Dupin: A parallel framework for densest subgraph discovery in fraud detection on massive graphs. Proc. ACM Manag. Data, 3(3).
Letsios, M., Balalau, O. D., Danisch, M., Orsini, E., and Sozio, M. (2016). Finding heaviest k-subgraphs and events in social media. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pages 113–120.
Ma, H., Guan, S., Toomey, C., and Wu, Y. (2022). Diversified subgraph query generation with group fairness. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM ’22, page 686–694, New York, NY, USA. Association for Computing Machinery.
Mawhirter, D. and Wu, B. (2019). Automine: Harmonizing high-level abstraction and high performance for graph mining. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, pages 509–523, New York, NY, USA. ACM.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100.
Oettershagen, L., Wang, H., and Gionis, A. (2024). Finding densest subgraphs with edgecolor constraints. In Proceedings of the ACM Web Conference 2024, WWW ’24, page 936–947, New York, NY, USA. Association for Computing Machinery.
Song, A. and Wu, G. (2025). Rems: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems. arXiv preprint arXiv:2505.17108.
Sze, J. F., Salhi, S., and Wassan, N. (2024). An adaptive variable neighbourhood search approach for the dynamic vehicle routing problem. Computers & Operations Research, 164:106531.
Teixeira, C. H. C., Fonseca, A. J., Serafini, M., Siganos, G., Zaki, M. J., and Aboulnaga, A. (2015). Arabesque: a system for distributed graph mining. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP ’15. ACM.
Tsourakakis, C. E. (2014). A novel approach to finding near-cliques: The triangle-densest subgraph problem. CoRR, abs/1405.1477.
Wickrama Arachchi, C., Kumpulainen, I., and Tatti, N. (2024). Dense subgraph discovery meets strong triadic closure. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 3334–3344, New York, NY, USA. Association for Computing Machinery.
Xavier, E. (2019). Uma interface de programação de aplicações para o brkga na plataforma cuda. In Anais do XX Simpósio em Sistemas Computacionais de Alto Desempenho, pages 13–24, Porto Alegre, RS, Brasil. SBC.
Xu, Y., Ma, C., Fang, Y., and Bao, Z. (2023). Efficient and effective algorithms for generalized densest subgraph discovery. Proc. ACM Manag. Data, 1(2).
Yang, J. and Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, New York, NY, USA. Association for Computing Machinery.
Yasin, A. (2014). A top-down method for performance analysis and counters architecture. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 35–44.
Ye, X., Li, R.-H., Liang, L., Liu, Z., Lin, L., and Wang, G. (2024). Efficient and effective anchored densest subgraph search: A convex-programming based approach. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 3907–3918, New York, NY, USA. Association for Computing Machinery.
Zhao, J. and Hifi, M. (2025). Reinforcement learning-enhanced variable neighborhood search strategies for the k-clustering minimum biclique completion problem. Computers & Operations Research, 178:107008.
Publicado
28/10/2025
Como Citar
CARVALHO, Diogo; MOREIRA, Mayron; DIAS, Vinícius.
An Experimental Study of Variable Neighborhood Search for General-Purpose Subgraph Optimization in Parallel Systems. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 26. , 2025, Bonito/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 85-96.
DOI: https://doi.org/10.5753/sscad.2025.15847.
