A hyperbolic approach for learning communities on graphs. (English) Zbl 1521.68118
Summary: Detecting communities on graphs has received significant interest in recent literature. Current state-of-the-art approaches tackle this problem by coupling Euclidean graph embedding with community detection. Considering the success of hyperbolic representations of graph-structured data in the last years, an ongoing challenge is to set up a hyperbolic approach to the community detection problem. The present paper meets this challenge by introducing a Riemannian geometry based framework for learning communities on graphs. The proposed methodology combines graph embedding on hyperbolic spaces with Riemannian K-means or Riemannian mixture models to perform community detection. The usefulness of this framework is illustrated through several experiments on generated community graphs and real-world social networks as well as comparisons with the most powerful baselines. The code implementing hyperbolic community embedding is available online https://www.github.com/tgeral68/HyperbolicGraphAndGMM.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
manifolds; representation learning; graph-structured data; hyperbolic space; community embeddingReferences:
| [1] | Afsari, B., Riemannian \(L^p\) center of mass: existence, uniqueness and convexity, Proc Am Math Soc, 139, 2, 655-6673 (2011) · Zbl 1220.53040 · doi:10.1090/S0002-9939-2010-10541-5 |
| [2] | Alekseevskij D, Vinberg EB, Solodovnikov A (1993) Geometry of spaces of constant curvature. In: Geometry II. Springer, pp 1-138 · Zbl 0787.53001 |
| [3] | Annamalai N, Mahinthan C, Rajasekar V, Lihui C, Yang L, Shantanu J (2017) graph2vec: learning distributed representations of graphs. In: Proceedings of the 13th international workshop on mining and learning with graphs (MLG) |
| [4] | Arnaudon, M.; Barbaresco, F.; Yang, L., Riemannian medians and means with applications to radar signal processing, J Sel Top Signal Process, 7, 4, 595-604 (2013) · doi:10.1109/JSTSP.2013.2261798 |
| [5] | Arnaudon, M.; Dombry, C.; Phan, A.; Yang, L., Stochastic algorithms for computing means of probability measures, Stoch Process Appl, 58, 9, 1455-1473 (2012) · Zbl 1262.60073 |
| [6] | Arnaudon, M.; Miclo, L., Means in complete manifolds: uniqueness and approximation, ESAIM Probab Stat, 18, 185-206 (2014) · Zbl 1352.60012 · doi:10.1051/ps/2013033 |
| [7] | Arnaudon M, Yang L, Barbaresco F (2011) Stochastic algorithms for computing p-means of probability measures, geometry of Radar Toeplitz covariance matrices and applications to HR Doppler processing. In: International radar symposium (IRS), pp 651-656 |
| [8] | Barachant, A.; Bonnet, S.; Congedo, M.; Jutten, C., Multiclass brain-computer interface classification by Riemannian geometry, IEEE Trans Biomed Eng, 59, 4, 920-928 (2012) · doi:10.1109/TBME.2011.2172210 |
| [9] | Becigneul G, Ganea O-E (2019) Riemannian adaptive optimization methods. In: International conference on learning representations (ICLR) |
| [10] | Boguná, M.; Papadopoulos, F.; Krioukov, D., Sustaining the internet with hyperbolic mapping, Nat Commun, 1, 1, 1-8 (2010) · doi:10.1038/ncomms1063 |
| [11] | Bonnabel, S., Stochastic gradient descent on Riemannian manifolds, IEEE Trans Autom Control, 122, 4, 2217-2229 (2013) · Zbl 1369.90110 · doi:10.1109/TAC.2013.2254619 |
| [12] | Cavallari, S.; Cambria, E.; Cai, H.; Chang, KC; Zheng, VW, Embedding both finite and infinite communities on graphs [application notes], IEEE Comput Intell Mag, 14, 3, 39-50 (2019) · doi:10.1109/MCI.2019.2919396 |
| [13] | Cavallari S, Zheng VW, Cai H, Chang KC-C, Cambria E (2017) Learning community embedding with community detection and node embedding on graphs. In: Proceedings of the 2017 ACM on conference on information and knowledge management (CIKM). ACM, pp 377-386 |
| [14] | Chamberlain B, Deisenroth M, Clough J (2017) Neural embeddings of graphs in hyperbolic space. In: Proceedings of the 13th international workshop on mining and learning with graphs (MLG) |
| [15] | Chami I, Ying Z, Ré C, Leskovec J (2019) Hyperbolic graph convolutional neural networks. In: Wallach H, Larochelle H, Beygelzimer A, Alché-Buc FD, Fox E, Garnett R (eds) Advances in neural information processing systems, vol 32. Curran Associates Inc, pp 4868-4879 |
| [16] | Cho H, DeMeo B, Peng J, Berger B (2019) Large-margin classification in hyperbolic space. volume 89 of Proceedings of Machine Learning Research. PMLR, pp 1832-1840, 16-18 |
| [17] | Cui, P.; Wang, X.; Pei, J.; Zhu, W., A survey on network embedding, IEEE Trans Knowl Data Eng, 31, 5, 833-852 (2019) · doi:10.1109/TKDE.2018.2849727 |
| [18] | Ganea O, Becigneul G, Hofmann T (2018) Hyperbolic neural networks. In: Advances in neural information processing systems 31 (NIPS). Curran Associates, Inc., pp 5345-5355 |
| [19] | Gromov M (1987) Hyperbolic Groups. Springer, New York, pp 75-263 · Zbl 0634.20015 |
| [20] | Grover A, Leskovec J (2016) Node2vec: scalable feature learning for networks. In: Proceedings of the 22th ACM international conference on knowledge discovery & data mining (SIGKDD), pp 855-864 |
| [21] | Helgason S (2001) Differential geometry, Lie groups, and symmetric spaces. American Mathematical Society · Zbl 0993.53002 |
| [22] | Heuveline S, Said S, Mostajeran C (2021) Gaussian distributions on riemannian symmetric spaces, random matrices, and planar feynman diagrams. Preprint arXiv:2106.08953 |
| [23] | Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguñá, M., Hyperbolic geometry of complex networks, Phys Rev E, 82, 036106 (2010) · doi:10.1103/PhysRevE.82.036106 |
| [24] | Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Phys Rev E, 78, 4, 046110 (2008) · doi:10.1103/PhysRevE.78.046110 |
| [25] | Lin F, Cohen WW (2010) Power iteration clustering. In: Proceedings of the 27th international conference on machine learning (ICML) |
| [26] | Liu Q, Nickel M, Kiela D (2019) Hyperbolic graph neural networks. In: Wallach H, Larochelle H, Beygelzimer A, Alché-Buc FD, Fox E, Garnett R (eds) Advances in neural information processing systems, vol 32. Curran Associates Inc, pp 8230-8241 |
| [27] | Mathieu E, Le Lan C, Maddison CJ, Tomioka R, Teh YW (2019) Continuous hierarchical representations with poincaré variational auto-encoders. In: Wallach H, Larochelle H, Beygelzimer A, Alché-Buc FD, Fox E, Garnett R (eds) Advances in neural information processing systems, vol 32. Curran Associates Inc, pp 12565-12576 |
| [28] | Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. In: Advances in neural information processing systems 26 (NIPS). Curran Associates, Inc., pp 3111-3119 |
| [29] | Miller, GA, Wordnet: a lexical database for english, Commun ACM, 38, 11, 39-41 (1995) · doi:10.1145/219717.219748 |
| [30] | Nickel M, Kiela D (2017) Poincaré embeddings for learning hierarchical representations. In: Advances in neural information processing systems 30 (NIPS). Curran Associates, Inc., pp 6338-6347 |
| [31] | Ovinnikov I (2018) Poincaré Wasserstein autoencoder. In: Bayesian deep learning workshop of advances in neural information processing systems (NIPS) |
| [32] | Pennec, X., Intrinsic statistics on Riemannian manifolds: basic tools for geometric measurements, J Math Imaging Vis, 25, 1, 127 (2006) · Zbl 1478.94072 · doi:10.1007/s10851-006-6228-4 |
| [33] | Pennington J, Socher R, Manning CD (2014) Glove: global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP) |
| [34] | Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM international conference on knowledge discovery and data mining (SIGKDD), KDD ’14, pp 701-710 |
| [35] | Said, S.; Bombrun, L.; Berthoumieu, Y.; Manton, JH, Riemannian Gaussian distributions on the space of symmetric positive definite matrices, IEEE Trans Inf Theory, 63, 4, 2153-2170 (2017) · Zbl 1366.15029 · doi:10.1109/TIT.2017.2653803 |
| [36] | Said, S.; Hajri, H.; Bombrun, L.; Vemuri, BC, Gaussian distributions on Riemannian symmetric spaces: statistical learning with structured covariance matrices, IEEE Trans Inf Theory, 64, 2, 752-772 (2018) · Zbl 1464.62300 · doi:10.1109/TIT.2017.2713829 |
| [37] | Sala F, Sa CD, Gu A, Ré C (2018) Representation tradeoffs for hyperbolic embeddings. In: Proceedings of the 35th international conference on machine learning (ICML), pp 4457-4466 |
| [38] | Skovgaard LT (1984) A riemannian geometry of the multivariate normal model. Scand J Stat:211-223 · Zbl 0579.62033 |
| [39] | Spielmat DA (1996) Spectral partitioning works: planar graphs and finite element meshes. In: Proceedings of the 37th annual symposium on foundations of computer science, FOCS ’96. IEEE Computer Society, p 96 |
| [40] | Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) Line: large-scale information network embedding. In: Proceedings of the 24th international conference on world wide web, pp 1067-1077 |
| [41] | Tu, C.; Zeng, X.; Wang, H.; Zhang, Z.; Liu, Z.; Sun, M.; Zhang, B.; Lin, L., A unified framework for community detection and network representation learning, IEEE Trans Knowl Data Eng, 31, 6, 1051-1065 (2019) · doi:10.1109/TKDE.2018.2852958 |
| [42] | Ungar, AA, A gyrovector space approach to hyperbolic geometry, Synth Lect Math Stat, 1, 1, 1-194 (2008) |
| [43] | Vulić, I.; Gerz, D.; Kiela, D.; Hill, F.; Korhonen, A., HyperLex: a large-scale evaluation of graded lexical entailment, Comput Linguist, 43, 4, 781-835 (2017) · doi:10.1162/COLI_a_00301 |
| [44] | Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of the 22Nd ACM international conference on knowledge discovery and data mining (SIGKDD ). ACM, pp 1225-1234 |
| [45] | Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp 1225-1234 |
| [46] | Zhu X, Ghahramani Z (2002) Learning from labeled and unlabeled data with label propagation. Technical report |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
