{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:54:59Z","timestamp":1760057699381,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T00:00:00Z","timestamp":1739750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Combinatorial optimization on temporal graphs is critical for summarizing dynamic networks in various fields, including transportation, social networks, and biology. Among these problems, the Minimum Timeline Cover (MinTCover) problem, aimed at identifying minimal activity intervals for representing temporal interactions, remains underexplored in the context of advanced machine learning techniques. Existing heuristic and approximate methods, while effective in certain scenarios, struggle with capturing complex temporal dependencies and scalability in dense, large-scale networks. Addressing this gap, this paper introduces DLMinTC+, a novel deep learning-based algorithm for solving the MinTCover problem. The proposed method integrates Graph Neural Networks for structural embedding, Transformer-based temporal encoding, and Pointer Networks for activity interval selection, coupled with an iterative adjustment algorithm to ensure valid solutions. Key contributions include (i) demonstrating the efficacy of deep learning for temporal combinatorial optimization, achieving superior accuracy and efficiency over state-of-the-art heuristics, and (ii) advancing the analysis of temporal knowledge graphs by incorporating robust, time-sensitive embeddings. Extensive evaluations on synthetic and real-world datasets highlight DLMinTC+\u2019s ability to achieve significant coverage size reduction while maintaining generalization, offering a scalable and precise solution for complex temporal networks.<\/jats:p>","DOI":"10.3390\/a18020113","type":"journal-article","created":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T10:26:12Z","timestamp":1739787972000},"page":"113","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["DLMinTC+: A Deep Learning Based Algorithm for Minimum Timeline Cover on Temporal Graphs"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0326-8742","authenticated-orcid":false,"given":"Giorgio","family":"Lazzarinetti","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica Sistemistica e Comunicazione, Universit\u00e0 degli Studi Milano-Bicocca, 20126 Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6124-2965","authenticated-orcid":false,"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[{"name":"Dipartimento di Lettere, Filosofia e Comunicazione, Universit\u00e0 degli Studi di Bergamo, 24129 Bergamo, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6406-536X","authenticated-orcid":false,"given":"Sara","family":"Manzoni","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica Sistemistica e Comunicazione, Universit\u00e0 degli Studi Milano-Bicocca, 20126 Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7312-7123","authenticated-orcid":false,"given":"Italo","family":"Zoppis","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica Sistemistica e Comunicazione, Universit\u00e0 degli Studi Milano-Bicocca, 20126 Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,17]]},"reference":[{"key":"ref_1","unstructured":"Holme, P., and Saram\u00e4ki, J. (2011). Temporal Networks. arXiv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","article-title":"An Introduction to Temporal Graphs: An Algorithmic Perspective","volume":"12","author":"Michail","year":"2016","journal-title":"Internet Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s41019-021-00155-3","article-title":"Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art","volume":"6","author":"Peng","year":"2021","journal-title":"Data Sci. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Hosseinzadeh, M.M., Cannataro, M., Guzzi, P.H., and Dondi, R. (2023). Temporal networks in biology and medicine: A survey on models, algorithms, and tools. Netw. Model. Anal. Health Inform. Bioinform., 12.","DOI":"10.1007\/s13721-022-00406-x"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Patnaik, S., Kountchev, R., Tai, Y., and Kountcheva, R. (2023). A Review of Temporal Network Analysis and Applications. 3D Imaging\u2014Multidimensional Signal Processing and Deep Learning, Springer.","DOI":"10.1007\/978-981-99-1145-5"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s10618-020-00717-5","article-title":"The network-untangling problem: From interactions to activity timelines","volume":"35","author":"Rozenshtein","year":"2021","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Froese, V., Kunz, P., and Zschoche, P. (2022). Disentangling the Computational Complexity of Network Untangling. arXiv.","DOI":"10.24963\/ijcai.2022\/283"},{"key":"ref_8","first-page":"12:1","article-title":"An FPT Algorithm for Temporal Graph Untangling","volume":"Volume 285","author":"Misra","year":"2023","journal-title":"Proceedings of the 18th International Symposium on Parameterized and Exact Computation, IPEC 2023"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"114040","DOI":"10.1016\/j.tcs.2023.114040","article-title":"Untangling temporal graphs of bounded degree","volume":"969","author":"Dondi","year":"2023","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Dondi, R., and Popa, A. (2024). Exact and approximation algorithms for covering timeline in temporal graphs. Annals of Operations Research, Springer.","DOI":"10.1007\/s10479-024-05993-8"},{"key":"ref_11","first-page":"20:1","article-title":"FastMinTC+: A Fast and Effective Heuristic for Minimum Timeline Cover on Temporal Networks","volume":"Volume 318","author":"Sala","year":"2024","journal-title":"Proceedings of the 31st International Symposium on Temporal Representation and Reasoning, TIME 2024"},{"key":"ref_12","first-page":"62:1","article-title":"Graph Summarization Methods and Applications: A Survey","volume":"51","author":"Liu","year":"2018","journal-title":"ACM Comput. Surv."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Paranjape, A., Benson, A.R., and Leskovec, J. (2016, January 6\u201310). Motifs in Temporal Networks. Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, Cambridge, UK.","DOI":"10.1145\/3018661.3018731"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hulovatyy, Y., Chen, H., and Milenkovic, T. (2016). Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics, 32.","DOI":"10.1093\/bioinformatics\/btw310"},{"key":"ref_15","unstructured":"Cao, L., Zhang, C., Joachims, T., Webb, G.I., Margineantu, D.D., and Williams, G. (2015, January 10\u201313). TimeCrunch: Interpretable Dynamic Graph Summarization. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia."},{"key":"ref_16","unstructured":"Brefeld, U., Getoor, L., and Macskassy, S.A. (2010, January 24\u201325). Frequent subgraph discovery in dynamic networks. Proceedings of the Eighth Workshop on Mining and Learning with Graphs, MLG\u201910, Washington, DC, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Pietil\u00e4nen, A.K., and Diot, C. (2012, January 11\u201314). Dissemination in opportunistic social networks: The role of temporal communities. Proceedings of the Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc\u201912, Hilton Head, SC, USA.","DOI":"10.1145\/2248371.2248396"},{"key":"ref_18","first-page":"173","article-title":"Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms","volume":"Volume 13889","author":"Hsieh","year":"2023","journal-title":"Proceedings of the Combinatorial Algorithms\u201434th International Workshop, IWOCA 2023"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"41:1","DOI":"10.1145\/1597036.1597045","article-title":"A better approximation ratio for the vertex cover problem","volume":"5","author":"Karakostas","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","article-title":"Approximation Algorithms for the Set Covering and Vertex Cover Problems","volume":"11","author":"Hochbaum","year":"1982","journal-title":"SIAM J. Comput."},{"key":"ref_21","first-page":"12:1","article-title":"Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks","volume":"Volume 233","author":"Schulz","year":"2022","journal-title":"Proceedings of the 20th International Symposium on Experimental Algorithms, SEA 2022"},{"key":"ref_22","unstructured":"Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., and Garnett, R. (2017, January 4\u20139). Learning Combinatorial Optimization Algorithms over Graphs. Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, Long Beach, CA, USA."},{"key":"ref_23","unstructured":"Bello, I., Pham, H., Le, Q.V., Norouzi, M., and Bengio, S. (2017, January 24\u201326). Neural Combinatorial Optimization with Reinforcement Learning. Proceedings of the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"120388","DOI":"10.1109\/ACCESS.2020.3004964","article-title":"Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking","volume":"8","author":"Vesselinova","year":"2020","journal-title":"IEEE Access"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Gunarathna, U., Borovica-Gajic, R., Karunasekera, S., and Tanin, E. (2022). Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning. arXiv.","DOI":"10.1145\/3557915.3560956"},{"key":"ref_26","unstructured":"Trivedi, R., Farajtabar, M., Biswal, P., and Zha, H. (2019, January 6\u20139). Dyrep: Learning representations over dynamic graphs. Proceedings of the International Conference on Learning Representations, New Orleans, LA, USA."},{"key":"ref_27","unstructured":"Xu, D., Ruan, C., Korpeoglu, E., Kumar, S., and Achan, K. (2020, January 30). Inductive representation learning on temporal graphs. Proceedings of the International Conference on Learning Representations, Addis Ababa, Ethiopia."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., Leiserson, C.E., and Bader, D.A. (2020, January 7\u201312). EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, New York, NY, USA.","DOI":"10.1609\/aaai.v34i04.5984"},{"key":"ref_29","unstructured":"Li, Y., Yu, R., Shahabi, C., and Liu, Y. (May, January 30). Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. Proceedings of the International Conference on Learning Representations, Vancouver, BC, Canada."},{"key":"ref_30","unstructured":"Chen, Y., Zhang, J., and Qin, Z. (2019, January 3\u20137). TREND: Temporal regularization for dynamic networks. Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, China."},{"key":"ref_31","unstructured":"Rossi, E., Chamberlain, B.P., Eynard, D., Rowbottom, J., and Bronstein, M. (2020, January 13\u201318). Temporal Graph Networks for Deep Learning on Dynamic Graphs. Proceedings of the International Conference on Machine Learning, Online."},{"key":"ref_32","unstructured":"Zhang, S., Zhang, X., Nie, F., and Zhang, J. (2020, January 7\u20139). TMac: A Multi-Aspect Collaborative Neural Network for Dynamic Graph Learning. Proceedings of the 2020 SIAM International Conference on Data Mining, Cincinnati, OH, USA."},{"key":"ref_33","unstructured":"Wang, C., Yao, H., Zhao, S., Wang, Z., Wu, F., Li, Z., Wang, C., and Jiang, X. (May, January 29). Temporal Graph Collaborative Transformer for Dynamic Graph Learning. Proceedings of the 2021 SIAM International Conference on Data Mining, Virtual."},{"key":"ref_34","unstructured":"Hamilton, W., Ying, Z., and Leskovec, J. (2017, January 4\u20139). Inductive representation learning on large graphs. Proceedings of the Advances in Neural Information Processing Systems, Long Beach, CA, USA."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Kumar, S., Zhang, X., and Leskovec, J. (2019, January 4\u20138). Predicting dynamic embeddings for link prediction in evolving networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330895"},{"key":"ref_36","unstructured":"Sankar, A., Wu, Y., Gouda, Z.H., Qi, Y., and Jure, L. (2020, January 6\u201310). DySAT: Dynamic Self-Attention Network for Temporal Graphs. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual."},{"key":"ref_37","unstructured":"Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., and Garnett, R. (2015, January 7\u201312). Pointer Networks. Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, Montreal, QC, Canada."},{"key":"ref_38","unstructured":"Bonet, B., and Koenig, S. (2015, January 25\u201330). The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, TX, USA."},{"key":"ref_39","unstructured":"Bengio, Y., and LeCun, Y. (2015, January 7\u20139). Adam: A Method for Stochastic Optimization. Proceedings of the 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA. Conference Track Proceedings."},{"key":"ref_40","unstructured":"Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep Learning, MIT Press. Available online: http:\/\/www.deeplearningbook.org."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Hamilton, W.L. (2020). Graph Representation Learning, Morgan & Claypool Publishers. Synthesis Lectures on Artificial Intelligence and Machine Learning.","DOI":"10.1007\/978-3-031-01588-5"},{"key":"ref_42","unstructured":"Bengio, Y., and LeCun, Y. (2015, January 7\u20139). Neural Machine Translation by Jointly Learning to Align and Translate. Proceedings of the 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA. Conference Track Proceedings."},{"key":"ref_43","unstructured":"Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., and Garnett, R. (2017, January 4\u20139). Attention is All you Need. Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, Long Beach, CA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/2\/113\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:36:25Z","timestamp":1760027785000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/2\/113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,17]]},"references-count":43,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["a18020113"],"URL":"https:\/\/doi.org\/10.3390\/a18020113","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,2,17]]}}}