{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T03:38:28Z","timestamp":1771299508523,"version":"3.50.1"},"reference-count":60,"publisher":"IEEE","license":[{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,9,27]]},"DOI":"10.1109\/allerton49937.2022.9929363","type":"proceedings-article","created":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T21:34:30Z","timestamp":1667597670000},"page":"1-8","source":"Crossref","is-referenced-by-count":9,"title":["Oversquashing in GNNs through the lens of information contraction and graph expansion"],"prefix":"10.1109","author":[{"given":"Pradeep Kr.","family":"Banerjee","sequence":"first","affiliation":[{"name":"MPI MiS"}]},{"given":"Kedar","family":"Karhadkar","sequence":"additional","affiliation":[{"name":"UCLA"}]},{"given":"Yu Guang","family":"Wang","sequence":"additional","affiliation":[{"name":"SJTU"}]},{"given":"Uri","family":"Alon","sequence":"additional","affiliation":[{"name":"CMU"}]},{"given":"Guido","family":"Montufar","sequence":"additional","affiliation":[{"name":"UCLA"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.818405"},{"key":"ref38","article-title":"Expander graphs - applications and combinatorial constructions","author":"wigderson","year":"2010","journal-title":"A 3-hour tutorial Pseudorandomness in Mathematical Structures Workshop"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2008.11.001"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-003-0270-6"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095674"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/1101006"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.41"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/050\/1067764"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478259"},{"key":"ref34","author":"cohen","year":"1998","journal-title":"Comparisons of Stochastic Matrices With Applications in Information Theory Statistics Economics and Population Sciences"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1088\/2632-072X\/ac730d"},{"key":"ref28","article-title":"On maximal correlation, hypercontractivity, and the data processing inequality studied by Erkip and Cover","author":"anantharam","year":"2013","journal-title":"ArXiv Preprint"},{"key":"ref27","article-title":"Understanding over-squashing and bottlenecks on graphs via curvature","author":"topping","year":"2022","journal-title":"International Conference on Learning Representations"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176995937"},{"key":"ref2","article-title":"Semi-supervised classification with graph convolutional networks","author":"kipf","year":"2017","journal-title":"International Conference on Learning Representations (ICLR)"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"ref20","first-page":"1","article-title":"On the complexity of a concentrator","volume":"318","author":"pinsker","year":"1973","journal-title":"7th International Telegraffic Conference"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.conb.2013.10.006"},{"key":"ref21","first-page":"259","article-title":"On the realization of nets in three-dimensional space","volume":"8","author":"kolmogorov","year":"1967","journal-title":"Problems in Cybernetics"},{"key":"ref24","article-title":"Relational inductive biases, deep learning, and graph networks","author":"battaglia","year":"2018","journal-title":"ArXiv Preprint"},{"key":"ref23","article-title":"Diffusion improves graph learning","volume":"33","author":"klicpera","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref26","article-title":"DropGNN: Random dropouts increase the expressiveness of graph neural networks","volume":"35","author":"papp","year":"2021","journal-title":"Advances in neural information processing systems"},{"key":"ref25","article-title":"Dropedge: Towards deep graph convolutional networks on node classification","author":"rong","year":"0","journal-title":"International Conference on Learning Representations"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.06.019"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520022"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9558-1"},{"key":"ref58","first-page":"1501","article-title":"Triangle-aware spectral sparsi-fiers and community detection","author":"sotiropoulos","year":"2021","journal-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"ref57","first-page":"1","article-title":"Edge sampling using local network information","volume":"22","author":"le","year":"2021","journal-title":"Journal of Machine Learning Research"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"ref53","volume":"42","author":"lyons","year":"2017","journal-title":"Probability on Trees and Networks"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.5948\/UPO9781614440222"},{"key":"ref10","article-title":"Long range graph benchmark","author":"dwivedi","year":"2022","journal-title":"ArXiv Preprint"},{"key":"ref40","article-title":"The spectrum of the infinite tree","author":"trevisan","year":"2014","journal-title":"tree\/"},{"key":"ref11","first-page":"5453","article-title":"Representation learning on graphs with jumping knowledge networks","author":"xu","year":"2018","journal-title":"Proc of the International Conference on Machine Learning (ICML)"},{"key":"ref12","first-page":"3419","article-title":"Generalization and representational limits of graph neural networks","author":"garg","year":"2020","journal-title":"Proc of the International Conference on Machine Learning (ICML)"},{"key":"ref13","article-title":"Lecture notes on information theory","author":"polyanskiy","year":"0","journal-title":"Lecture Notes for ECE563 (UIUC) and 6 441 (MIT) 2012–2017 2017"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/18.796377"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2549542"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-7005-6_7"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-003"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"ref19","first-page":"762","article-title":"What is an expander?","volume":"51","author":"sarnak","year":"2004","journal-title":"Notices of the American Mathe-matical Society"},{"key":"ref4","first-page":"1263","article-title":"Neural message passing for quantum chemistry","author":"gilmer","year":"2017","journal-title":"Proc of the International Conference on Machine Learning (ICML)"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"ref6","article-title":"Graph attention networks","author":"veli?kovi?","year":"2018","journal-title":"International Conference on Learning Representations (ICLR)"},{"key":"ref5","first-page":"2702","article-title":"Discriminative embeddings of latent variable models for structured data","author":"dai","year":"2016","journal-title":"Proc of the International Conference on Machine Learning (ICML)"},{"key":"ref8","article-title":"How powerful are graph neural networks?","author":"xu","year":"2019","journal-title":"International Conference on Learning Representations (ICLR)"},{"key":"ref7","first-page":"1024","article-title":"Inductive representation learning on large graphs","volume":"30","author":"hamilton","year":"2017","journal-title":"Advances in neural information processing systems"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch19"},{"key":"ref9","article-title":"On the bottleneck of graph neural networks and its practical implications","author":"alon","year":"0","journal-title":"International Conference on Learning Representations"},{"key":"ref46","first-page":"320","article-title":"Eigenvalues, expanders and superconcentra-tors","author":"alon","year":"1984","journal-title":"25th Annual Symposium on Foundations of Computer Science (FOCS)"},{"key":"ref45","first-page":"110","article-title":"A lower bound for the smallest eigenvalue of the Laplacian","volume":"625","author":"cheeger","year":"1970","journal-title":"Problems in Analysis"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.5"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073992"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21709"},{"key":"ref41","author":"friedman","year":"2008","journal-title":"A Proof of Alon's Second Eigenvalue Conjecture and Related Problems"},{"key":"ref44","article-title":"Mixing time and expansion of non-negatively curved Markov chains","author":"m\u00fcnch","year":"2022","journal-title":"ArXiv Preprint"},{"key":"ref43","article-title":"Sparse expanders have negative curvature","author":"salez","year":"2021","journal-title":"ArXiv Preprint"}],"event":{"name":"2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)","location":"Monticello, IL, USA","start":{"date-parts":[[2022,9,27]]},"end":{"date-parts":[[2022,9,30]]}},"container-title":["2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/9929313\/9929314\/09929363.pdf?arnumber=9929363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T20:25:53Z","timestamp":1669667153000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9929363\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,27]]},"references-count":60,"URL":"https:\/\/doi.org\/10.1109\/allerton49937.2022.9929363","relation":{},"subject":[],"published":{"date-parts":[[2022,9,27]]}}}