11 Graph representation learning and graph neural network

This chapter motivates graph representation learning as a scalable alternative to manual feature engineering for machine learning on graphs. It explains how embeddings transform nodes, edges, and subgraphs into dense vectors that preserve structural and semantic properties, enabling downstream tasks such as node classification, link prediction, and community detection. The narrative frames Graph Neural Networks as a key vehicle for learning such representations directly from graph structure and attributes, emphasizing a practical mindset: combine the intuition and transparency of handcrafted features with the power and adaptability of automated representation learning to build robust, real-world intelligent advisory systems.

The text surveys core design choices behind embeddings and their implications for practice. It contrasts Euclidean and non-Euclidean (notably hyperbolic) geometries, distinguishes positional (global) versus structural (local) embeddings, and outlines transductive versus inductive learning regimes. It unifies methods under an encoder–decoder view, illustrating with node2vec, and then extends shallow embeddings to multi-relational knowledge graphs through efficient training objectives (e.g., cross-entropy with negative sampling) and expressive decoders (translation-, matrix-, and semantic-matching–based such as TransE, RESCAL, DistMult, and ComplEx). Throughout, it ties these choices to concrete application needs in social, biomedical, and medical knowledge graphs.

The chapter then develops GNNs through message passing, where nodes iteratively aggregate neighbor information and update their states to capture higher-order structure and features. It generalizes aggregation with neighborhood normalization and attention (including multi-head variants and transformer-style formulations), and strengthens updates via skip connections, gated mechanisms, and jumping knowledge to balance locality, depth, stability, and expressiveness. Finally, it highlights the complementarity between GNNs and large language models, outlining three integration patterns—LLMs as predictors, encoders, and aligners—to fuse textual semantics with graph structure for stronger reasoning, prediction, and generation in knowledge-graph–centric systems.

The image depicts the node embedding problem. The goal of the task is to learn an encoding function, encode(x), which maps nodes to multi-dimensional embedding space. These embeddings are optimized so that distances in the embedding space reflect some relevant aspects of the original graph, like the relative positions of the nodes.

An illustration of Euclidean vs. non-Euclidean space [3]. Pixels in an image are all equally distant from each other and have all eight neighbors (except those on the border). In a graph, the number of neighbors can vary enormously from one node to the other.

Euclidean space grows polynomially as we increase the number of dimensions. Moving from 2D to 3D to 4D and beyond, the available space increases according to a polynomial relationship with the dimension. For example, a unit square in 2D has an area of 1, a unit cube in 3D has a volume of 1, and a unit hypercube in 4D has a hypervolume of 1. Still, the total space available along each axis increases polynomially rather than exponentially.

Overview of the encoder-decoder approach. The encoder maps the node c to a low-dimensional embedding zc. The decoder then uses zc to reconstruct c's local neighborhood information.

Example of how a single node aggregates messages from its local neighborhood in the message-passing model. Notice that the computation graph of the GNN forms a tree structure by unfolding the neighborhood around the target node.

• Graph representation learning automates feature engineering by transforming nodes and edges into dense vector representations.
• The evolution spans three generations: traditional dimensionality reduction, word2vec-inspired approaches, and modern Graph Neural Networks.
• Graph embeddings can be either positional (preserving global structure) or structural (capturing local patterns), each suited for different tasks.
• The selection of the embedding method should consider data characteristics, computational resources, and specific application requirements.
• The choice between transductive and inductive approaches depends on whether new nodes are expected to join the graph.
• Geometric spaces matter - some graph structures are better represented in non-Euclidean spaces, particularly for hierarchical data.
• The encoding-decoding process works like a translation system, converting graph data into vectors and then back to meaningful patterns.
• The encoder-decoder framework unifies different embedding approaches by separating graph encoding from property reconstruction.
• Shallow embeddings provide a simple but important baseline through their lookup-table approach to graph representation.
• Message passing in GNNs enables automatic feature discovery through iterative information aggregation from neighboring nodes.
• Multi-head attention enables GNNs to process different types of node relationships in parallel, similar to transformers.
• Neighborhood normalization and attention mechanisms help handle varying neighborhood sizes and relationship importance.
• Skip connections and gated updates improve information flow across multiple GNN layers, preventing feature loss.
• LLMs complement GNNs by providing three integration paths: as predictors, encoders, or aligners for graph tasks.

1. Y. Ma and J. Tang, "Deep Learning on Graphs." Cambridge, UK: Cambridge University Press, 2021. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.1017/9781108924184
2. W. L. Hamilton, "Graph Representation Learning." San Rafael, CA, USA: Morgan & Claypool Publishers, 2020. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.2200/S01045ED1V01Y202009AIM046
3. I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy, "Machine Learning on Graphs: A Model and Comprehensive Taxonomy," arXiv preprint arXiv:2204.06025, 2022. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/2204.06025
4. A. Grover and J. Leskovec, "node2vec: Scalable Feature Learning for Networks," in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 855-864. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.1145/2939672.2939754
5. A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, "Translating Embeddings for Modeling Multi-relational Data," in Advances in Neural Information Processing Systems 26 (NeurIPS 2013), Lake Tahoe, NV, USA, 2013, pp. 2787-2795. Accessed: May 15, 2024 [Online]. Available: https://proceedings.neurips.cc/paper/2013/hash/1cecc7a77928ca8133fa24680a88d2f9-Abstract.html
6. M. Nickel, V. Tresp, and H. P. Kriegel, "A Three-Way Model for Collective Learning on Multi-Relational Data," in Proceedings of the 28th International Conference on Machine Learning (ICML 2011), Bellevue, WA, USA, 2011, pp. 809-816. Accessed: May 15, 2024 [Online]. Available: https://icml.cc/2011/papers/438_icmlpaper.pdf
7. B. Yang, W. Yih, X. He, J. Gao, and L. Deng, "Embedding Entities and Relations for Learning and Inference in Knowledge Bases," in International Conference on Learning Representations (ICLR 2015), San Diego, CA, USA, 2015. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/1412.6575
8. T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, and G. Bouchard, "Complex Embeddings for Simple Link Prediction," in Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), New York, NY, USA, 2016, pp. 2071-2080. Accessed: May 15, 2024 [Online]. Available: https://proceedings.mlr.press/v48/trouillon16.html
9. T. N. Kipf and M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks." In International Conference on Learning Representations (ICLR), Toulon, France, 2017. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/1609.02907
10. P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, Y. Bengio, "Graph Attention Networks," in International Conference on Learning Representations, Vancouver, Canada, 2018. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/1710.10903
11. W. L. Hamilton, R. Ying, and J. Leskovec, "Inductive Representation Learning on Large Graphs," in Advances in Neural Information Processing Systems 30, Long Beach, CA, USA, 2017, pp. 1024-1034. Accessed: May 15, 2024 [Online]. Available: https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html
12. Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu, "A Comprehensive Survey on Graph Neural Networks," IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 1, pp. 4-24, 2021. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.1109/TNNLS.2020.2978386
13. B. Jin, C. Han, H. Ji, J. Han, "Large Language Models on Graphs: A Comprehensive Survey," arXiv preprint arXiv:2312.02783, 2024. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/2312.02783

FAQ