CoChat
Sign Up
PreprintCited by 344Advanced Graph Neural NetworksNeural Networks and ApplicationsTopological and Geometric Data Analysis

Hyperbolic Graph Convolutional Neural Networks

Open access
Chami, Ines, Ying, Rex, Ré, Christopher, Leskovec, Jure·2019·arXiv
DOI 10.48550/arxiv.1910.12933arXiv 1910.12933
Open this paper in CoChat — free accountOpen PDF

Abstract

Graph convolutional neural networks (GCNs) embed nodes in a graph into Euclidean space, which has been shown to incur a large distortion when embedding real-world graphs with scale-free or hierarchical structure. Hyperbolic geometry offers an exciting alternative, as it enables embeddings with much smaller distortion. However, extending GCNs to hyperbolic geometry presents several unique challenges because it is not clear how to define neural network operations, such as feature transformation and aggregation, in hyperbolic space. Furthermore, since input features are often Euclidean, it is unclear how to transform the features into hyperbolic embeddings with the right amount of curvature. Here we propose Hyperbolic Graph Convolutional Neural Network (HGCN), the first inductive hyperbolic GCN that leverages both the expressiveness of GCNs and hyperbolic geometry to learn inductive node representations for hierarchical and scale-free graphs. We derive GCN operations in the hyperboloid model of hyperbolic space and map Euclidean input features to embeddings in hyperbolic spaces with different trainable curvature at each layer. Experiments demonstrate that HGCN learns embeddings that preserve hierarchical structure, and leads to improved performance when compared to Euclidean analogs, even with very low dimensional embeddings: compared to state-of-the-art GCNs, HGCN achieves an error reduction of up to 63.1% in ROC AUC for link prediction and of up to 47.5% in F1 score for node classification, also improving state-of-the art on the Pubmed dataset.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1910.12933

Cites

9 of 9 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Many real-world knowledge graphs contain hierarchical relations.

    “Many real-world knowledge graphs contain hierarchical relations [10, 11, 26].”

    From Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic Cones (2021) · cites this paper as [26]

    The Introduction (p. 2) describes graph datasets with varying degrees of hierarchical structure, and Related Work (p. 3) refers to real-world graphs with hierarchical structure. The paper does not specifically establish that many real-world knowledge graphs contain hierarchical relations; its statements concern graphs more generally. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 37

  1. [1][1] Aaron B Adcock, Blair D Sullivan, and Michael W Mahoney. Tree-like structure in large social and information networks. In 2013 IEEE 13th International Conference on Data Mining , pages 1-10. IEEE, 2013. -
  2. [2][2] Roy M Anderson and Robert M May. Infectious diseases of humans: dynamics and control . Oxford university press, 1992. -
  3. [3][3] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems , pages 585-591, 2002. -
  4. [5][5] Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359 , 2017. - · arXiv
  5. [6][6] Wei Chen, Wenjie Fang, Guangda Hu, and Michael W Mahoney. On the hyperbolicity of small-world and treelike random graphs. Internet Mathematics , 9(4):434-491, 2013. -
  6. [7][7] Aaron Clauset, Cristopher Moore, and Mark EJ Newman. Hierarchical structure and the prediction of missing links in networks. Nature , 453(7191):98, 2008. -
  7. [8][8] Bhuwan Dhingra, Christopher J Shallue, Mohammad Norouzi, Andrew M Dai, and George E Dahl. Embedding text in hyperbolic spaces. NAACL HLT , 2018. -
  8. [10][10] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in neural information processing systems , pages 5345-5355, 2018. -
  9. [11][11] Octavian-Eugen Ganea, Gary Becigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In International Conference on Machine Learning , pages 1632-1641, 2018. -
  10. [13][13] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representations in product spaces. In International Conference on Learning Representations , 2019. -
  11. [14][14] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, et al. Hyperbolic attention networks. In International Conference on Learning Representations , 2019. -
  12. [15][15] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems , pages 1024-1034, 2017. -
  13. [17][17] Edmond Jonckheere, Poonsuk Lohsoonthorn, and Francis Bonahon. Scaled gromov hyperbolic graphs. Journal of Graph Theory , 2008. -
  14. [18][18] Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oseledets, and Victor Lempitsky. Hyperbolic image embeddings. arXiv preprint arXiv:1904.02239 , 2019. - · arXiv
  15. [19][19] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations , 2015. -
  16. [20][20] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NeurIPS Workshop on Bayesian Deep Learning , 2016. -
  17. [21][21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017. -
  18. [22][22] Robert Kleinberg. Geographic routing using hyperbolic space. In IEEE International Conference on Computer Communications , 2007. -
  19. [23][23] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E , 2010. -
  20. [25][25] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations , 2016. -
  21. [26][26] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems , 2019. -
  22. [30][30] Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning , pages 3776-3785, 2018. -
  23. [31][31] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 701-710. ACM, 2014. -
  24. [32][32] Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. Physical review E , 2003. -
  25. [34][34] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoffs for hyperbolic embeddings. In International Conference on Machine Learning , pages 4457-4466, 2018. -
  26. [35][35] Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing , 2011. -
  27. [38][38] Yi Tay, Luu Anh Tuan, and Siu Cheung Hui. Hyperbolic representation learning for fast and efficient neural question answering. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining , pages 583-591. ACM, 2018. -
  28. [39][39] Alexandru Tifrea, Gary Becigneul, and Octavian-Eugen Ganea. Poincaré glove: Hyperbolic word embeddings. In International Conference on Learning Representations , 2019. -
  29. [42][42] Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning , pages 1058-1066, 2013. -
  30. [43][43] Richard C Wilson, Edwin R Hancock, El˙ zbieta Pekalska, and Robert PW Duin. Spherical and hyperbolic embeddings of data. IEEE transactions on pattern analysis and machine intelligence , 36(11):2255-2269, 2014. -
  31. [44][44] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning , pages 6861-6871, 2019. -
  32. [45][45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations , 2019. -
  33. [46][46] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning , pages 40-48, 2016. -
  34. [47][47] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages 974-983. ACM, 2018. -
  35. [48][48] Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds. In Advances in Neural Information Processing Systems , pages 4592-4600, 2016. -
  36. [49][49] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems , pages 5165-5175, 2018. -
  37. [50][50] Marinka Zitnik, Marcus W Feldman, Jure Leskovec, et al. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences , 116(10):4426-4433, 2019.

Cited by

Sorted by citations

Authors
Chami, I., Ying, R., Ré, C., & Leskovec, J.
Affiliations
Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1910.12933
arXiv
1910.12933
OpenAlex
W2982490267
Cited by
344
References
9
Citations by year
2026: 1 · 2025: 41 · 2024: 70 · 2023: 74 · 2022: 65 · 2021: 69 · 2020: 24
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
Keywords
hyperbolic geometry, hyperbolic embeddings, hyperboloid model, scale-free networks, hierarchical graphs, link prediction, node classification

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review