Nothing Special   »   [go: up one dir, main page]
Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

An Integer Programming Approach Reinforced by a Message-passing Procedure for Detecting Dense Attributed Subgraphs

DOI: http://dx.doi.org/10.15439/2022F64

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 569–576 ()

Full text

Abstract. Due to the growing reliance of various scientific and industrial problems on graphs, one of the recent challenging tasks, especially when dealing with graphs equipped with a set of nodal attributes, is discovering subgraphs consisting of highly interacting nodes with respect to the number of edges and the attributes' similarities. This paper proposes an approach based on integer programming modeling and the graph neural network message-passing manner for efficiently extracting these subgraphs. The experiments illustrate the proposed method's privilege over some alternative algorithms known so far, utilizing several well-known instances.

References

  1. L. Jiang, L. Shi, L. Liu, J. Yao, and M. A. Yousuf, “User interest community detection on social media using collaborative filtering,” Wireless Networks, pp. 1–7, 2019.
  2. A. Ferdowsi, M. Dehghan Chenary, and A. Khanteymoori, “Tscda: a dynamic two-stage community discovery approach,” Social Network Analysis and Mining, vol. 12, no. 1, pp. 1–14, 2022.
  3. Y. Atay, I. Koc, I. Babaoglu, and H. Kodaz, “Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms,” Applied Soft Computing, vol. 50, pp. 194–211, 2017.
  4. D. Krioukov, M. Kitsak, R. S. Sinkovits, D. Rideout, D. Meyer, and M. Boguñá, “Network cosmology,” Scientific reports, vol. 2, p. 793, 2012.
  5. S. Aparicio, J. Villazón-Terrazas, and G. Álvarez, “A model for scale-free networks: application to twitter,” Entropy, vol. 17, no. 8, pp. 5848–5867, 2015.
  6. N. Tremblay and P. Borgnat, “Graph wavelets for multiscale community mining,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5227–5239, 2014.
  7. O. A. Linares, G. M. Botelho, F. A. Rodrigues, and J. B. Neto, “Segmentation of large images based on super-pixels and community detection in graphs,” IET Image Processing, vol. 11, no. 12, pp. 1219–1228, 2017.
  8. L. M. Freitas and M. G. Carneiro, “Community detection to invariant pattern clustering in images,” in 2019 8th Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2019, pp. 610–615.
  9. F. D. Malliaros and M. Vazirgiannis, “Clustering and community detection in directed networks: A survey,” Physics Reports, vol. 533, no. 4, pp. 95–142, 2013.
  10. M. E. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006.
  11. S. Fortunato and M. Barthelemy, “Resolution limit in community detection,” Proceedings of the national academy of sciences, vol. 104, no. 1, pp. 36–41, 2007.
  12. T. Chakraborty, A. Dalmia, A. Mukherjee, and N. Ganguly, “Metrics for community analysis: A survey,” ACM Computing Surveys (CSUR), vol. 50, no. 4, pp. 1–37, 2017.
  13. J. Chen, O. R. Zaïane, and R. Goebel, “Detecting communities in social networks using max-min modularity,” in Proceedings of the 2009 SIAM international conference on data mining. SIAM, 2009, pp. 978–989.
  14. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, “On modularity clustering,” IEEE transactions on knowledge and data engineering, vol. 20, no. 2, pp. 172–188, 2007.
  15. A. Ferdowsi and A. Khanteymoori, “Discovering communities in networks: A linear programming approach using max-min modularity,” in 2021 16th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2021, pp. 329–335.
  16. A. R. Barghi, A. Ferdowsi, and A. Abhari, “Musical preferences prediction by classification algorithm,” in Proceedings of the Communications and Networking Symposium, 2018, pp. 1–12.
  17. H. Cai, V. W. Zheng, and K. C.-C. Chang, “A comprehensive survey of graph embedding: Problems, techniques, and applications,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 9, pp. 1616–1637, 2018.
  18. V. S. Dave, B. Zhang, P.-Y. Chen, and M. A. Hasan, “Neural-brane: Neural bayesian personalized ranking for attributed network embedding,” Data Science and Engineering, vol. 4, no. 2, pp. 119–131, 2019.
  19. S. Cavallari, V. W. Zheng, H. Cai, K. C.-C. Chang, and E. Cambria, “Learning community embedding with community detection and node embedding on graphs,” in Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017, pp. 377–386.
  20. J. J. Choong, X. Liu, and T. Murata, “Learning community structure with variational autoencoder,” in 2018 IEEE international conference on data mining (ICDM). IEEE, 2018, pp. 69–78.
  21. S. Souravlas, A. Sifaleras, M. Tsintogianni, and S. Katsavounis, “A classification of community detection methods in social networks: a survey,” International Journal of General Systems, vol. 50, no. 1, pp. 63–91, 2021.
  22. G. Agarwal and D. Kempe, “Modularity-maximizing graph communities via mathematical programming,” The European Physical Journal B, vol. 66, no. 3, pp. 409–418, 2008.
  23. D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, S. Perron, and L. Liberti, “Column generation algorithms for exact modularity maximization in networks,” Physical Review E, vol. 82, no. 4, p. 046112, 2010.
  24. T. N. Dinh and M. T. Thai, “Finding community structure with performance guarantees in complex networks,” arXiv preprint https://arxiv.org/abs/1108.4034, 2011.
  25. A. Miyauchi and Y. Miyamoto, “Computing an upper bound of modularity,” The European Physical Journal B, vol. 86, no. 7, p. 302, 2013.
  26. B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 701–710.
  27. A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855–864.
  28. X. Huang, J. Li, and X. Hu, “Accelerated attributed network embedding,” in Proceedings of the 2017 SIAM international conference on data mining. SIAM, 2017, pp. 633–641.
  29. C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Chang, “Network representation learning with rich text information,” in Twenty-fourth international joint conference on artificial intelligence, 2015.
  30. X. Su, S. Xue, F. Liu, J. Wu, J. Yang, C. Zhou, W. Hu, C. Paris, S. Nepal, D. Jin et al., “A comprehensive survey on community detection with deep learning,” IEEE Transactions on Neural Networks and Learning Systems, 2022.
  31. D. Zhang, J. Yin, X. Zhu, and C. Zhang, “User profile preserving social network embedding,” in IJCAI International Joint Conference on Artificial Intelligence, 2017.
  32. D. Jin, Z. Yu, P. Jiao, S. Pan, D. He, J. Wu, P. Yu, and W. Zhang, “A survey of community detection approaches: From statistical modeling to deep learning,” IEEE Transactions on Knowledge and Data Engineering, 2021.
  33. K. G. Dizaji, F. Zheng, N. Sadoughi, Y. Yang, C. Deng, and H. Huang, “Unsupervised deep generative adversarial hashing network,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 3664–3673.
  34. Q. Yuan and B. Liu, “Community detection via an efficient nonconvex optimization approach based on modularity,” Computational Statistics & Data Analysis, vol. 157, p. 107163, 2021.
  35. J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in International conference on machine learning. PMLR, 2017, pp. 1263–1272.
  36. T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” arXiv preprint https://arxiv.org/abs/1609.02907, 2016.
  37. O. Shchur and S. Günnemann, “Overlapping community detection with graph neural networks,” arXiv preprint https://arxiv.org/abs/1909.12201, 2019.
  38. D. D. Paepe, D. N. Avendano, and S. V. Hoecke, “Implications of z-normalization in the matrix profile,” in International Conference on Pattern Recognition Applications and Methods. Springer, 2019, pp. 95–118.
  39. M. E. Newman, “Analysis of weighted networks,” Physical review E, vol. 70, no. 5, p. 056131, 2004.
  40. C. L. Giles, K. D. Bollacker, and S. Lawrence, “Citeseer: An automatic citation indexing system,” in Proceedings of the third ACM conference on Digital libraries, 1998, pp. 89–98.
  41. J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, “Arnetminer: extraction and mining of academic social networks,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, 2008, pp. 990–998.
  42. A. L. Traud, P. J. Mucha, and M. A. Porter, “Social structure of facebook networks,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 16, pp. 4165–4180, 2012.
  43. L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, p. P09008, 2005.
  44. K. Y. Yip, D. W. Cheung, and M. K. Ng, “Harp: A practical projected clustering algorithm,” IEEE Transactions on knowledge and data engineering, vol. 16, no. 11, pp. 1387–1397, 2004.
  45. J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in Proceedings of the 24th international conference on world wide web, 2015, pp. 1067–1077.