Clustering Networks with Node and Edge Attributes using Bregman Divergence
Resumo
Network clustering tackles the problem of identifying sets of nodes (clusters or communities) that have similar connection patterns. However, in many modern scenarios, nodes also have attributes that are correlated with the network structure. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this thesis establishes an information-theoretic criterion for the exact recovery of community labels and characterizes a phase transition determined by the Chernoff-Hellinger divergence of the model. The criterion shows how network and attribute information can be exchanged in order to yield exact recovery (e.g., more reliable network information requires less reliable attribute information). This thesis also presents two iterative clustering algorithms that greedily maximizes the joint likelihood of the model under the assumption that the probability distribution of network edges and node attributes belong to exponential families. Extensive analysis of the two algorithms on both synthetic datasets and real benchmarks highlights their accuracy and performance with respect to other state-of-the-art approaches.
Referências
Abbe, E., Fan, J., and Wang, K. (2022). An ℓp theory of pca and spectral clustering. The Annals of Statistics, 50(4):2359–2385.
Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In IEEE FOCS.
Banerjee, A., Merugu, S., Dhillon, I. S., Ghosh, J., and Lafferty, J. (2005). Clustering with bregman divergences. Journal of machine learning research, 6(10).
Braun, G., Tyagi, H., and Biernacki, C. (2022). An iterative clustering algorithm for the contextual stochastic block model with optimality guarantees. In ICML.
Combe, D., Largeron, C., Géry, M., and Egyed-Zsigmond, E. (2015). I-louvain: An attributed graph clustering method. In Intl. Symp. on Intelligent Data Analysis.
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. (2018). Contextual stochastic block models. In Advances in Neural Information Processing Systems (NeurIPS).
Dreveton, M., Fernandes, F. S., and Figueiredo, D. R. (2023). Exact recovery and bregman hard clustering of node-attributed stochastic block model. In NeurIPS.
Fernandes, F. S. (2023). Clustering networks with node attributes using bregman divergences. Master’s thesis, Federal University of Rio de Janeiro (UFRJ).
Fortunato, S. and Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659:1–44.
Long, B., Zhang, Z. M., and Yu, P. S. (2007). A probabilistic framework for relational clustering. In ACM SIGKDD, pages 470–479.
Mariadassou, M., Robin, S., and Vacher, C. (2010). Uncovering latent structure in valued graphs: A variational approach. The Annals of Applied Statistics, 4(2):715 – 742.
Newman, M. E. and Clauset, A. (2016). Structure and inference in annotated networks. Nature communications, 7(1):11863.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. (2008). Collective classification in network data. AI magazine, 29(3):93–93.
Stanley, N., Bonacci, T., Kwitt, R., Niethammer, M., and Mucha, P. J. (2019). Stochastic block models with multiple continuous attributes. Applied Network Science, 4(1):1–22.
Van Erven, T. and Harremos, P. (2014). Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):3797–3820.
