Chapter 9: Machine learning on knowledge graphs: A primer approach

Introduction

The introduction explains why machine learning on knowledge graphs matters for intelligent advisory systems: it can use integrated graph knowledge to provide insights beyond ordinary querying and navigation.

• Integrated knowledge for analysis: Explain how a knowledge graph brings knowledge from diverse sources into a form that supports exploration, navigation, and more advanced analytics.
  Why it matters: This explains why the graph can serve as a foundation for more advanced analysis.
• Machine learning for advisory insights: Explain why intelligent advisory systems may use machine learning algorithms with graph knowledge as input, rather than relying only on querying, navigation, and basic statistics.
  Why it matters: It distinguishes an advisory insight from simply retrieving or inspecting information already in the graph.

Key terms: knowledge graphs, holistic knowledge, advanced analytics, intelligent advisory systems, advising, machine learning, knowledge in the graphs

9.1 Machine learning on graphs: Why?

The section explains why graph-based machine learning can be a good fit for connected data and graph-shaped problems, and how GNNs and LLMs can complement each other.

• Graphs as a common representation: Explain why graphs can be useful when applications produce many different forms of data.
  Why it matters: A common graph representation lets you consider graph-based methods for data that did not start out as a graph.
• Problems as graph tasks: Describe how different application problems can be framed as a small set of graph tasks, using the section’s examples.
  Why it matters: Framing the business problem as a graph task helps you choose an appropriate ML approach.
• Connected data and independence: Explain why graph-based ML can be preferable when data items depend on one another.
  Why it matters: When relationships matter to the answer, discarding them can undermine the result.
• Complementary GNN and LLM roles: Distinguish what GNNs and LLMs contribute when used together in the section’s personalized-medicine example.
  Why it matters: The combination can make graph-derived patterns understandable and actionable for end users.

Key terms: graphs, data representation, problem modeling, node classification, relationship prediction, data item dependency, independent and identically distributed, relationships, GNNs, LLMs

9.2 Machine learning on graphs: What?

This section explains why graph ML tasks are grouped by whether each data point is a node or relationship in one graph, or an entire graph, rather than only by whether labels are available.

• Node versus graph task units: Distinguish node-focused from graph-focused ML tasks by describing what counts as a data point in each.
  Why it matters: The distinction tells you what the model is working on: parts of one graph or whole graphs.
• Label based task categories: Explain supervised and unsupervised learning in terms of labels, and why those categories are not necessarily the most useful way to divide graph ML tasks.
  Why it matters: Label availability describes how a task learns, but does not capture the distinction this section uses to organize graph tasks.

Key terms: node-focused tasks, graph-focused tasks, data points, supervised, unsupervised, labels

9.2.1 Node classification

This section defines node classification, explains why graph relationships matter when predicting node labels, and clarifies its semisupervised and multilabel forms.

• Node Classification Task: Describe node classification as predicting labels for unlabeled graph nodes from a small set of labeled nodes, as in identifying bots in a social network.
  Why it matters: This defines what the model is trying to predict before considering how graph structure helps.
• Relational Nature of Nodes: Explain why graph nodes violate the usual independent-and-identically-distributed assumption and why classification should consider both node attributes and relationships.
  Why it matters: The connections between nodes can be as informative as the attributes of the nodes themselves.
• Semisupervised Classification Nuance: Explain why node classification is often called semisupervised and why that label does not fit classical semisupervised learning perfectly.
  Why it matters: It explains both the useful semisupervised label and the limit of that familiar category.
• Multiple Labels per Node: Describe how node classification can assign multiple labels to one node, using Flickr users’ interest groups as an example.
  Why it matters: Some graph entities belong to several categories, so prediction need not be limited to one label per node.

Key terms: node classification, unlabeled node, training set of nodes, label, i.i.d. assumption, node attributes, network relationships, homophily, structural equivalence, heterophily

9.2.2 Link prediction (a.k.a. relationship prediction)

This section explains what link prediction seeks to infer, why graph edges may be missing, and how existing connections and node information can support predictions.

• Link prediction task: Explain that link prediction forecasts connections between nodes, using the co-authorship example to show how it predicts possible future collaborations between authors who have not worked together.
  Why it matters: It identifies the prediction target before considering how a graph model might learn it.
• Reasons for missing edges: Describe the two reasons edges may be absent: an existing connection was not observed, recorded, or disclosed, or the graph is evolving and a new connection may form.
  Why it matters: The reason an edge is absent helps explain why predicting it can be useful.
• Link and relationship terminology: Distinguish prediction of a connection’s existence from prediction of its relationship type, while noting that this book uses link prediction and relationship prediction interchangeably.
  Why it matters: The distinction clarifies what is being predicted even when the book uses both names for the task.
• Semisupervised prediction inputs: Explain that link prediction typically uses existing connections, graph patterns, and node-level information to infer likely missing or future connections.
  Why it matters: It connects the prediction target to the information available for making a prediction.

Key terms: link prediction, co-authorship graph, nodes, edges, missing edges, evolving graphs, relationship prediction, graph completion, relational inference, semisupervised learning

9.2.3 Clustering and community detection

This section explains how community detection finds groups from graph relationships, why those groups help summarize a network, and how graph clustering differs from traditional clustering.

• Communities in network structure: Explain why a collaboration graph may contain communities and what community detection identifies from the graph.
  Why it matters: It establishes what information a community-detection task takes from a graph and what it produces.
• Structural summary of large graphs: Explain how identifying densely connected regions helps describe or summarize a graph.
  Why it matters: A community-level view makes complex network relationships easier to describe.
• Graph and vector clustering distinction: Distinguish graph clustering from traditional clustering of data points, including how the terms graph clustering and community detection are used here.
  Why it matters: The distinction clarifies why a graph’s edges cannot be treated as incidental to finding its groups.
• Labels in community assignment: Describe whether graph clustering needs preexisting labels and the exception noted in the section.
  Why it matters: This prevents treating the absence of labels as an absolute rule for every clustering approach.

Key terms: community detection, graph clustering, network topology, relationships, graph description, summarization, densely connected regions, traditional clustering, K-means, DBSCAN

9.2.4 Graph classification

This section explains how whole graphs can be classified or clustered, using molecules, proteins, and programs as examples.

• Whole-graph classification: Explain how graph classification uses labeled graphs to predict a label for a previously unlabeled graph, and distinguish this from labeling individual nodes.
  Why it matters: It identifies what counts as one sample—and what the prediction is about—in a graph classification task.
• Graph-level patterns and clustering: Describe why graph-level tasks need information about both a graph’s components and their connections, and distinguish graph clustering from supervised graph classification.
  Why it matters: A whole-graph prediction can miss important information if it considers only the parts or only how they connect.

Key terms: graph classification, node classification, labeled graphs, i.i.d. data point, graph clustering, internal structure, features, components

9.3 Machine learning on graphs: How?

Introduces two ways to apply machine learning to graphs: use graph-specific algorithms or convert graph structure into features for conventional ML.

• Graph machine learning approaches: Distinguish graph-specific algorithms from approaches that turn graph structure into feature vectors, and explain what each approach uses to make predictions.
  Why it matters: This distinction explains why graph feature engineering is useful even when conventional ML algorithms are available.

Key terms: collective classification, graph structure, feature vectors, feature engineering, node features, neighborhood relationships

9.3.1 Node classification and link prediction

This section walks through a karate-club node classification example to show how graph features feed a classifier and why domain-informed features can outperform simple or automatically learned representations.

• Consistent training and prediction features: Describe how graph features are used to train a prediction model and then make predictions, and explain why featurization must remain the same in both phases.
  Why it matters: A trained model can only use prediction inputs represented in the way it was trained to expect.
• Karate club classification setup: Explain what the karate club example predicts, what supplies its labels, and what information is used to make the predictions.
  Why it matters: The example makes clear which information is available for prediction and which outcome is being tested.
• Graph vectors and classifier evaluation: Describe the node representations tried, how the classifier uses them, and how its predictions are evaluated.
  Why it matters: Turning nodes into comparable numerical inputs lets a conventional classifier be trained and checked against actual outcomes.
• Homophily guided feature improvement: Explain why the initial results prompted a change in features and how the revised representation improved the example.
  Why it matters: The comparison shows why choosing features that reflect the graph’s social context can matter more than choosing a familiar classifier.

Key terms: featurization, training, prediction model, node classification, link prediction, Zachary Karate Club, ground-truth labels, friendship network structure, degree, Node2Vec

9.3.2 Graph classification

This section outlines how graph classification uses whole-graph features to train a model and classify previously unlabeled graphs.

• Graph Classification Workflow: Describe how graph classification differs from node classification in its inputs and features, and how a trained model is used to classify unclassified graphs.
  Why it matters: The unit being classified determines which features the model needs.
• Feature Quality and Model Performance: Explain why feature extraction matters to graph classification and what else affects the quality of its output.
  Why it matters: Even a suitable classification workflow depends on informative features and well-tuned parameters for good results.

Key terms: graph classification, feature engineering, prediction phase, unclassified graphs, feature extraction, accuracy, downstream algorithm parameters

9.3.3 Graph clustering

Graph clustering finds communities directly from a graph without feature extraction or a training phase, and the section illustrates the result on a karate club network.

• Direct unsupervised graph clustering: Explain how graph clustering takes an entire graph or subgraph as input and uses its nodes and relationships to produce communities without feature extraction, representation transformation, or training labels.
  Why it matters: This distinguishes graph clustering from graph ML tasks that first transform the graph into features and train a model.
• Community detection method differences: Distinguish the fixed mechanism of weakly connected components from methods such as Louvain and label propagation that optimize outcomes, and describe how label propagation assigns communities and why its output can vary.
  Why it matters: The method chosen affects both what counts as a community and whether repeated runs give the same result.
• Karate club clustering result: Describe what the Louvain example found in the karate club graph and how the section judges the resulting communities.
  Why it matters: The example makes the intended community pattern concrete while showing that an identified community need not align perfectly with existing groups.

Key terms: graph clustering, feature extraction, representation transformation, unsupervised approach, weakly connected component (WCC), Louvain, label propagation algorithm (LPA), modularity, karate club graph, communities

9.4 Summary