Universal Local Attractors on Graphs
Source abstract
Abstract
Being able to express broad families of equivariant or invariant attributed graph functions is a popular measuring stick of whether graph neural networks should be employed in practical applications. However, it is equally important to find deep local minima of losses (i.e., produce outputs with much smaller loss values compared to other minima), even when architectures cannot express global minima. In this work we introduce the architectural property of attracting optimization trajectories to local minima as a means of achieving smaller loss values. We take first steps in satisfying this property for losses defined over attributed undirected unweighted graphs with an architecture called universal local attractor (ULA). This refines each dimension of end-to-end-trained node feature embeddings based on graph structure to track the optimization trajectories of losses satisfying some mild conditions. The refined dimensions are then linearly pooled to create predictions. We experiment on 11 tasks, from node classification to clique detection, on which ULA is comparable with or outperforms popular alternatives of similar or greater theoretical expressive power.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Graph Neural Networks · Ferroelectric and Negative Capacitance Devices · Machine Learning in Materials Science
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Information Technologies Institute @ CERTH, 6th km Charilaou-Thermi, 57001 Thessaloniki, Greece
Funding
European Commission · European Union · UKRI
References (39)
Show source-provided references
1. Loukas, A. (2019). What graph neural networks cannot learn: Depth vs width. arXiv.
2. Nguyen, Q., Mukkamala, M.C., and Hein, M. (2018). On the loss landscape of a class of deep neural networks with no bad local valleys. arXiv.
3. Optimization for deep learning: An overview10.1007/s40305-020-00309-6 ↗
4. Bae, K., Ryu, H., and Shin, H. (2019). Does Adam optimizer keep close to the optimal point?. arXiv.
5. Graph signal processing: Overview, challenges, and applications10.1109/JPROC.2018.2820126 ↗
6. Page, L., Brin, S., Motwani, R., and Winograd, T. (2024, April 01). The Pagerank Citation Ranking: Bringing Order to the Web. Available online: https://www.semanticscholar.org/paper/The-PageRank-Citation-Ranking-%3A-Bringing-Order-to-Page-Brin/eb82d3035849cd23578096462ba419b53198a556.
7. The heat kernel as the pagerank of a graph10.1073/pnas.0708838104 ↗
8. Gasteiger, J., Bojchevski, A., and Günnemann, S. (2018). Predict then propagate: Graph neural networks meet personalized pagerank. arXiv.
9. Agarap, A.F. (2018). Deep learning using rectified linear units (relu). arXiv.
10. Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., and Dahl, G.E. (2017, January 6–11). Neural message passing for quantum chemistry. Proceedings of the International Conference on Machine Learning, PMLR, Sydney, Australia.
11. Balcilar, M., Héroux, P., Gauzere, B., Vasseur, P., Adam, S., and Honeine, P. (2021, January 18–24). Breaking the limits of message passing graph neural networks. Proceedings of the International Conference on Machine Learning, PMLR, Virtual.
12. Kipf, T.N., and Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv.
13. Graph attention networks
14. An optimal lower bound on the number of variables for graph identification10.1007/BF01305232 ↗
15. Provably powerful graph networks
16. Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., and Grohe, M. (2019–1, January 27). Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, Honolulu, HI, USA.10.1609/aaai.v33i01.33014602 ↗
17. Deep sets
18. Universal invariant and equivariant graph neural networks
19. Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019, January 9–15). On the universality of invariant networks. Proceedings of the International Conference on Machine Learning, PMLR, Long Beach, CA, USA.
20. Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural networks?. arXiv.
21. Wang, H., Yin, H., Zhang, M., and Li, P. (2022). Equivariant and stable positional encoding for more powerful graph neural networks. arXiv.
22. What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
23. Sato, R., Yamada, M., and Kashima, H. (May, January 29). Random features strengthen graph neural networks. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), SIAM, Virtual.10.1137/1.9781611976700.38 ↗
24. Abboud, R., Ceylan, I.I., Grohe, M., and Lukasiewicz, T. (2020). The surprising power of graph neural networks with random node initialization. arXiv.10.24963/ijcai.2021/291 ↗
25. Krasanakis, E., Papadopoulos, S., and Kompatsiaris, I. (2021). Applying fairness constraints on graph node ranks under personalization bias. Complex Networks & Their Applications IX: Volume 2, Proceedings of the Ninth International Conference on Complex Networks and Their Applications Complex Networks, Madrid, Spain, 1–3 December 2020, Springer.10.1007/978-3-030-65351-4_49 ↗
26. Kidger, P., and Lyons, T. (2020, January 9–12). Universal approximation with deep narrow networks. Proceedings of the Conference on Learning Theory, PMLR, Graz, Austria.
27. Hoang, N., Maehara, T., and Murata, T. (2021, January 10–15). Revisiting graph neural networks: Graph filtering perspective. Proceedings of the 2020 25th International Conference on Pattern Recognition (ICPR), Milan, Italy.
28. Huang, Q., He, H., Singh, A., Lim, S.N., and Benson, A.R. (2020). Combining Label Propagation and Simple Models Out-performs Graph Neural Networks. arXiv.
29. Learning with local and global consistency
30. Fey, M., and Lenssen, J.E. (2019). Fast graph representation learning with PyTorch Geometric. arXiv.
31. Bojchevski, A., and Günnemann, S. (2017). Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv.
32. Collective classification in network data
33. Namata, G., London, B., Getoor, L., Huang, B., and Edu, U. (2012, January 1). Query-driven active surveying for collective classification. Proceedings of the Workshop on Mining and Learning with Graphs (MLG-2012), Edinburgh, UK.10.1007/978-1-4899-7502-7_44-1 ↗
34. Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. (2020, January 13–18). Simple and deep graph convolutional networks. Proceedings of the International Conference on Machine Learning, PMLR, Virtual.
35. Multiple comparisons among means10.1080/01621459.1961.10482090 ↗
36. Statistical comparisons of classifiers over multiple data sets
37. Hollander, M., Wolfe, D.A., and Chicken, E. (2013). Nonparametric Statistical Methods, John Wiley & Sons.
38. He, K., Zhang, X., Ren, S., and Sun, J. (2015, January 7–13). Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE International Conference on Computer Vision, Santiago, Chile.10.1109/ICCV.2015.123 ↗
39. Nunes, M., Fraga, P.M., and Pappa, G.L. (2021, January 10–14). Fitness landscape analysis of graph neural network architecture search spaces. Proceedings of the Genetic and Evolutionary Computation Conference, Lille, France.10.1145/3449639.3459318 ↗