Fetching the paper…
Reading the bibliography…
The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works.
W. S. McCulloch and W. Pitts, “A logical calculus of the ideas immanent in nervous activity,” The Bulletin of Mathematical Biophysics , vol. 5, no. 4, pp. 115–133, 1943
1943
Earlier work this paper cites.
J. von Neumann, “Probabilistic logics and the synthesis of reliable organisms from unreliable components,” Automata studies , vol. 34, no. 34, pp. 43–98, 1956
1956
Earlier work this paper cites.
R. L. Dobrushin, “Central limit theorem for nonstationary Markov chains. I,” Theory of Probability & Its Applications , vol. 1, no. 1, pp. 65–80, 1956
1956
Earlier work this paper cites.
A. N. Kolmogorov and Y. M. Barzdin, “On the realization of nets in three-dimensional space,” Problems in Cybernetics , vol. 8, no. 261-268, pp. 259–260, 1967
1967
Earlier work this paper cites.
J. Cheeger, “A lower bound for the smallest eigenvalue of the Laplacian,” Problems in Analysis , vol. 625, no. 195-199, p. 110, 1970
1970
Earlier work this paper cites.
M. S. Pinsker, “On the complexity of a concentrator,” in 7th International Telegraffic Conference , vol. 318, 1973, pp. 1–4
1973
Earlier work this paper cites.
R. Ahlswede and P. Gács, “Spreading of sets in product spaces and hypercontraction of the Markov operator,” The Annals of Probability , pp. 925–939, 1976
1976
Earlier work this paper cites.
N. Alon and V. D. Milman, “Eigenvalues, expanders and superconcentrators,” in 25th Annual Symposium on Foundations of Computer Science (FOCS) , 1984, pp. 320–322
1984
Earlier work this paper cites.
P. G. Doyle and J. L. Snell, Random walks and electric networks . American Mathematical Society, 1984, vol. 22
1984
Earlier work this paper cites.
——, “On networks of noisy gates,” in 26th Annual Symposium on Foundations of Computer Science (FOCS) , 1985, pp. 30–38
1985
Earlier work this paper cites.
N. Pippenger, “Developments in “The synthesis of reliable organisms from unreliable components”,” in The legacy of John von Neumann . American Mathematical Society, 1990, vol. 50, pp. 311–324
1990
Earlier work this paper cites.
——, “Perturbation methods of the theory of Gibbsian fields,” in Lectures on Probability Theory and Statistics . Springer, 1996, pp. 1–66
1996
Earlier work this paper cites.
A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, “The electrical resistance of a graph captures its commute and cover times,” Computational Complexity , vol. 6, no. 4, pp. 312–340, 1996
1996
Earlier work this paper cites.
J. Cohen, J. Kemperman, and G. Zbăganu, Comparisons of Stochastic Matrices with applications in information theory, statistics, economics, and population sciences . Birkhäuser, 1998
1998
Earlier work this paper cites.
W. S. Evans and L. J. Schulman, “Signal propagation and noisy circuits,” IEEE Transactions on Information Theory , vol. 45, no. 7, pp. 2367–2373, 1999
1999
Earlier work this paper cites.
P. Del Moral, M. Ledoux, and L. Miclo, “On contraction properties of Markov kernels,” Probability Theory and Related Fields , vol. 126, no. 3, pp. 395–420, 2003
2003
Earlier work this paper cites.
W. S. Evans and L. J. Schulman, “On the maximum tolerable noise of k k -input gates for reliable computation by formulas,” IEEE Transactions on Information Theory , vol. 49, no. 11, pp. 3094–3098, 2003
2003
Earlier work this paper cites.
P. C. Sarnak, “What is an expander?” Notices of the American Mathematical Society , vol. 51, no. 7, pp. 762–763, 2004
2004
Earlier work this paper cites.
P. Mahlmann and C. Schindelhauer, “Peer-to-peer networks based on random transformations of connected regular undirected graphs,” in Proc. 17th Annual ACM symposium on Parallelism in Algorithms and Architectures , 2005, pp. 155–164
2005
Earlier work this paper cites.
S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications,” Bulletin of the American Mathematical Society , vol. 43, no. 4, pp. 439–561, 2006
2006
Earlier work this paper cites.
T. Feder, A. Guetz, M. Mihail, and A. Saberi, “A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks,” in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 2006, pp. 69–76
2006
Cited alongside, same era.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Transactions on Neural Networks , vol. 20, no. 1, pp. 61–80, 2008
2008
Cited alongside, same era.
J. Friedman, A proof of Alon’s second eigenvalue conjecture and related problems . Memoirs of the American Mathematical Society, 2008
2008
Cited alongside, same era.
Y. Ollivier, “Ricci curvature of Markov chains on metric spaces,” Journal of Functional Analysis , vol. 256, no. 3, pp. 810–864, 2009
2009
Cited alongside, same era.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” in International Conference on Learning Representations (ICLR) , 2018
2018
Later among the works it cites.
K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” in Proc. 35th International Conference on Machine Learning (ICML) , 2018, pp. 5453–5462
2018
Later among the works it cites.
2018
Later among the works it cites.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in International Conference on Learning Representations (ICLR) , 2019
2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Wigderson, “Expander graphs - applications and combinatorial constructions.” A 3-hour tutorial, Pseudorandomness in Mathematical Structures Workshop, IAS, Princeton, NJ, 2010. [Online]. Available: http://www.math.ias.edu/~avi/TALKS/expander_tutorial_June2010.ppt
2010
Cited alongside, same era.
D. A. Spielman and N. Srivastava, “Graph sparsification by effective resistances,” SIAM Journal on Computing , vol. 40, no. 6, pp. 1913–1926, 2011
2011
Cited alongside, same era.
2013
Cited alongside, same era.
L. G. Valiant, “What must a global theory of cortex explain?” Current opinion in Neurobiology , vol. 25, pp. 15–19, 2014
2014
Cited alongside, same era.
L. Trevisan, “The spectrum of the infinite tree,” https://lucatrevisan.wordpress.com/2014/08/20/the-spectrum-of-the-infinite-tree/ , 2014
2014
Cited alongside, same era.
J. Jost and S. Liu, “Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs,” Discrete & Computational Geometry , vol. 51, no. 2, pp. 300–322, 2014
2014
Cited alongside, same era.
H. Dai, B. Dai, and L. Song, “Discriminative embeddings of latent variable models for structured data,” in Proc. 33rd International Conference on Machine Learning (ICML) , 2016, pp. 2702–2711
2016
Cited alongside, same era.
M. Raginsky, “Strong data processing inequalities and ϕ \phi -Sobolev inequalities for discrete channels,” IEEE Transactions on Information Theory , vol. 62, no. 6, pp. 3355–3389, 2016
2016
Cited alongside, same era.
J. Klicpera, S. Weißenberger, and S. Günnemann, “Diffusion improves graph learning,” Advances in Neural Information processing Systems , vol. 33, 2019
2019
Later among the works it cites.
C. Cooper, M. Dyer, C. Greenhill, and A. Handley, “The flip Markov chain for connected regular graphs,” Discrete Applied Mathematics , vol. 254, pp. 56–79, 2019
2019
Later among the works it cites.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems , vol. 32, no. 1, pp. 4–24, 2020
2020
Later among the works it cites.
V. Garg, S. Jegelka, and T. Jaakkola, “Generalization and representational limits of graph neural networks,” in Proc. 37th International Conference on Machine Learning (ICML) , 2020, pp. 3419–3430
2020
Later among the works it cites.
Y. Rong, W. Huang, T. Xu, and J. Huang, “Dropedge: Towards deep graph convolutional networks on node classification,” in International Conference on Learning Representations , 2020
2020
Later among the works it cites.
U. Alon and E. Yahav, “On the bottleneck of graph neural networks and its practical implications,” in International Conference on Learning Representations , 2021
2021
Later among the works it cites.
P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer, “DropGNN: Random dropouts increase the expressiveness of graph neural networks,” Advances in Neural Information Processing Systems , vol. 35, 2021
2021
Later among the works it cites.
J. Salez, “Sparse expanders have negative curvature,” arXiv preprint arXiv:2101.08242 , 2021
2021
Later among the works it cites.
C. M. Le, “Edge sampling using local network information,” Journal of Machine Learning Research , vol. 22, no. 88, pp. 1–29, 2021
2021
Later among the works it cites.
K. Sotiropoulos and C. E. Tsourakakis, “Triangle-aware spectral sparsifiers and community detection,” in Proc. 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining , 2021, pp. 1501–1509
2021
Later among the works it cites.
2022
Closest in time.
J. Topping, F. D. Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein, “Understanding over-squashing and bottlenecks on graphs via curvature,” in International Conference on Learning Representations , 2022
2022
Closest in time.
2022
Closest in time.
G. Giakkoupis, “Expanders via local edge flips in quasilinear time,” in Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , 2022, pp. 1074–1087
2022
Closest in time.
K. Devriendt and R. Lambiotte, “Discrete curvature on graphs from the effective resistance,” Journal of Physics: Complexity , vol. 3, 2022
2022
Closest in time.