9 Machine learning on knowledge graphs: a primer approach
Intelligent Advisory Systems need to go beyond querying and manual exploration of knowledge graphs to uncover the rich, implicit structure they encode. This chapter motivates machine learning on knowledge graphs as the natural way to surface insights at scale across domains such as drug discovery, personalized medicine, and law enforcement. It argues that graphs provide a universal data representation, allow many problems to be cast as a small set of graph tasks, and natively capture dependencies that violate the independent-and-identically-distributed assumption of classical ML. It also highlights the growing maturity of graph ML tooling, the complementary strengths of Graph Neural Networks and Large Language Models, and the importance of keeping the discipline problem-driven.
The chapter organizes graph ML work into node-focused and graph-focused tasks. Node classification predicts labels for nodes within a single graph and is often treated as semi-supervised because models exploit the full network structure during training; its effectiveness depends on modeling homophily, heterophily, and structural equivalence rather than assuming i.i.d. data. Link (relationship) prediction addresses missing or future edges in evolving, incomplete graphs and powers use cases from recommendations to knowledge graph completion. Community detection/graph clustering is typically unsupervised, discovers latent group structure from topology alone, and supports summarization and segmentation at scale. Graph classification treats each graph as a data point (e.g., molecules) and learns mappings from whole-graph structure to labels, contrasting with node-level prediction.
Methodologically, there are two routes: use graph-native algorithms that operate directly on structure, or transform graphs into feature vectors and apply standard ML. The chapter emphasizes feature engineering as the linchpin—featurizing nodes, edges, or whole graphs, keeping train/predict pipelines consistent, and applying scaling and robust classifiers. A worked example on the Karate Club shows that naive features (degree) and even generic embeddings (Node2Vec) can be unstable, while simple, domain-aware features that reflect neighborhood composition deliver large, reliable gains. For graph classification, features summarize entire graphs; for clustering, algorithms like Louvain or Label Propagation need no featurization or training. The chapter sets up the remainder of the book to progress from manual feature design to automated representation learning with GNNs, underscoring that final performance hinges on representation quality and careful tuning.
Node-focused and graph-focused tasks are represented in terms of expected input and output during training and prediction.
Node classification typical flow. As with many supervised machine learning tasks, it has two phases. The first is the training and the second is the prediction that, in this case, translates into classifying unclassified nodes.
Link prediction typical flow. Link prediction has two phases. During the first one, the training, a graph is taken and the model is trained to recognize whether a link exists or not. During the prediction phase, the model provides an output for each pair of nodes representing the target relationship to predict. For each, it will provide an existence probability.
Community Detection flow. The input is a graph, and the output is a mapping between nodes and groups. In the image, the groups are represented as colors and different circles.
Graph classification flow. Like many supervised tasks, it has two phases. During the training, it takes different graphs with the related classes and trains a model to recognize the class of each. During the prediction, the model takes a graph and predicts its class.
A graph-based classification approach (collective) versus traditional algorithms for classification.
Training flow for node classification and link prediction. A critical step is the “featurization” of nodes and relationships. Once these steps have been done, the vectors can be passed to a classic algorithm. Both node classification and link prediction can be seen as classification tasks.
Prediction flow for node classification and link prediction. The featurization process should be the same as the training. The classifier model built previously is used in this phase for making the predictions.
Karate Club graph as produced by the code in listing 9.1, the colors of the nodes represent the club the member ultimately joined.
High-level training process for the graph classification task. The output is a classifier model that has been trained on the known classes of different graphs.
High-level prediction process for the graph classification task. The output in this case is the classes assigned to the previous unlabeled graphs.
High-level graph clustering task process. This is an example of a pure graph algorithm approach that doesn’t require an intermediate transformation in a vector representation or other formats.
The result of the community detection algorithm applied to the Karate Club network. The algorithm has identified 4 different communities. All but one contain members of the same groups. Only in one case, there is a spurious element, but it is very well connected to other people belonging to a different group.
Summary
- Machine Learning on graphs emerges as a crucial approach because it naturally handles interconnected data, provides universal data representation, and enables the modeling of complex problems through a limited set of computational tasks.
- Unlike traditional machine learning that assumes independent and identically distributed (i.i.d.) data points, graph-based approaches explicitly leverage connections and dependencies between nodes, better reflecting real-world relationships and patterns.
- Machine learning tasks on graphs fall into two main categories: node-focused (like node classification and link prediction) where tasks are performed on a single graph, and graph-focused (like graph classification) where each graph is a separate data point.
- Node classification and link prediction are typically semi-supervised tasks, utilizing both labeled and unlabeled data, along with the graph's structural information. Community detection, in contrast, is usually unsupervised and operates directly on graph structure.
- Feature engineering plays a critical role these tasks. Simple approaches (like using node degree) often underperform compared to more sophisticated features that capture domain knowledge (like homophily-based metrics) or structural patterns.
- Node embeddings can be generated through various approaches, from manual feature engineering to automated techniques like Node2Vec. However, autonomous embeddings require careful tuning to avoid generating overly homogeneous representations.
- The success of graph-based machine learning often depends on finding the right balance between automated feature learning, domain knowledge incorporation, and appropriate algorithm selection for the specific task at hand.
- A. Negro, Graph-Powered Machine Learning. Shelter Island, NY, USA: Manning Publications, 2021
- A. Mukkamala, P. Szolovits, and J. Lin, "Representation Learning: From Diagnoses to Healthcare Analytics," Data Science, vol. 4, no. 2, pp. 125-146, Sep. 2021. Accessed: May 15, 2024 [Online]. Available: https://content.iospress.com/articles/data-science/ds007
- Y. Ma and J. Tang, Deep Learning on Graphs. Cambridge, UK: Cambridge University Press, 2021
- W. L. Hamilton, Graph Representation Learning. San Rafael, CA, USA: Morgan & Claypool Publishers, 2020
- T. N. Kipf and M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks," in International Conference on Learning Representations (ICLR 2016), San Juan, Puerto Rico, 2016. Accessed: May 15, 2024 [Online]. Available: https://arxiv.org/abs/1609.02907
- M. McPherson, L. Smith-Lovin, and J. Cook, "Birds of a Feather: Homophily in Social Networks," Annual Review of Sociology, vol. 27, no. 1, pp. 415-444, 2001
- D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Scholkopf, "Learning with Local and Global Consistency," in Proceedings of the 17th International Conference on Neural Information Processing Systems (NeurIPS 2004), Vancouver, BC, Canada, 2004. Accessed: May 15, 2024 [Online]. Available: https://proceedings.neurips.cc/paper/2003/hash/87682805257e619d49b8e0dfdc14affa-Abstract.html
- C. Donnat, M. Zitnik, D. Hallac, and J. Leskovec, "Graph Wavelets for Structural Role Similarity in Complex Networks," in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2018), London, UK, 2018. Accessed: May 15, 2024 [Online]. Available: https://dl.acm.org/doi/10.1145/3219819.3220025
- Z. Yang, W. Cohen, and R. Salakhutdinov, "Revisiting Semi-Supervised Learning with Graph Embeddings," in Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), New York, NY, USA, 2016. Accessed: May 15, 2024 [Online]. Available: https://proceedings.mlr.press/v48/yanga16.html
- L. Tang and H. Liu, "Relational Learning via Latent Social Dimensions," in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2009), Paris, France, pp. 817-826, 2009. Accessed: May 15, 2024 [Online]. Available: https://dl.acm.org/doi/10.1145/1557019.1557109
- L. A. Adamic and E. Adar, "Friends and Neighbors on the Web," Social Networks, vol. 25, no. 3, pp. 211-230, 2003
- R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, "Graph Convolutional Neural Networks for Web-Scale Recommender Systems," in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2018), London, UK, pp. 974-983, 2018. Accessed: May 15, 2024 [Online]. Available: https://dl.acm.org/doi/10.1145/3219819.3219890
- M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich, "A Review of Relational Machine Learning for Knowledge Graphs," Proceedings of the IEEE, vol. 104, no. 1, pp. 11-33, 2015. Accessed: May 15, 2024 [Online]. Available: https://ieeexplore.ieee.org/document/7358050
- M. Zitnik, M. Agrawal, and J. Leskovec, "Modeling polypharmacy side effects with graph convolutional networks," Bioinformatics, vol. 34, no. 13, pp. i457–i466, 2018.
- A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, "Translating Embeddings for Modeling Multi-relational Data," in Proceedings of the 26th International Conference on Neural Information Processing Systems (NeurIPS 2013), Lake Tahoe, NV, USA, 2013. Accessed: May 15, 2024 [Online]. Available: https://papers.nips.cc/paper_files/paper/2013/hash/1cecc7a77928ca8133fa24680a88d2f9-Abstract.html
- Wang, H. Huang, C. Ding, and F. Nie, "Predicting Protein–Protein Interactions from Multimodal Biological Data Sources via Nonnegative Matrix Tri-Factorization," Journal of Computational Biology, vol. 20, no. 4, pp. 344-358, 2013. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.1089/cmb.2012.0273
- G. Berlusconi, F. Calderoni, N. Parolini, M. Verani, and C. Piccardi, "Link Prediction in Criminal Networks: A Tool for Criminal Intelligence Analysis," PLOS ONE, vol. 11, no. 4, e0154244, 2016. Accessed: May 15, 2024 [Online]. Available: https://doi.org/10.1371/journal.pone.0154244
- M. Agrawal, M. Zitnik, J. Leskovec, "Large-scale analysis of disease pathways in the human interactome," in Proc. Pacific Symposium on Biocomputing (PSB), 2018, pp. 111-122. Accessed: Nov. 18, 2024 [Online]. Available: https://pmc.ncbi.nlm.nih.gov/articles/PMC5731453/
- S. Pandit, D. Chau, S. Wang, and C. Faloutsos, "NetProbe: A fast and scalable system for fraud detection in online auction networks," in Proc. 16th International World Wide Web Conference (WWW), 2007, pp. 201-210. Accessed: Nov. 18, 2024 [Online]. Available: https://www.cs.cmu.edu/~christos/PUBLICATIONS/netprobe-www07.pdf
- U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Physical Review E, vol. 76, no. 3, 036106, 2007. Accessed: Nov. 18, 2024 [Online]. Available: https://arxiv.org/pdf/0709.2938
- J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, "Neural message passing for quantum chemistry," in Proc. 34th International Conference on Machine Learning (ICML), 2017, pp. 1263-1272. Accessed: Nov. 18, 2024 [Online]. Available: https://proceedings.mlr.press/v70/gilmer17a.html
- Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli, "Graph matching networks for learning the similarity of graph structured objects," in Proc. 36th International Conference on Machine Learning (ICML), 2019, pp. 3835-3845. Accessed: Nov. 18, 2024 [Online]. Available: https://proceedings.mlr.press/v97/li19d.html
- P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classification in network data," AI Magazine, vol. 29, no. 3, pp. 93-106, 2008. Accessed: Nov. 18, 2024 [Online]. Available: https://doi.org/10.1609/aimag.v29i3.2157
- 24. W. W. Zachary, "An information flow model for conflict and fission in small groups," Journal of Anthropological Research, vol. 33, no. 4, pp. 452-473, 1977. Accessed: Nov. 18, 2024 [Online]. Available: https://www.jstor.org/stable/3629752
- A. Grover and J. Leskovec, "node2vec: Scalable Feature Learning for Networks," in Proc. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016, pp. 855-864. Accessed: Nov. 18, 2024 [Online]. Available: https://arxiv.org/abs/1607.00653
Knowledge Graphs and LLMs in Action ebook for free