Chapter 10: Graph feature engineering: Manual and semiautomated approaches

Introduction

This introduction explains why graph machine learning needs numerical features and compares manual, semiautomated, and learned ways to create them.

• Graph elements as numerical vectors: Explain why graph elements must be represented as numerical vectors for machine learning, and how graph features differ from measurements in a traditional dataset.
  Why it matters: The features determine what information from a graph a model can use.
• Feature creation tradeoffs: Distinguish manual feature engineering, semiautomated extraction, and representation learning in terms of human effort, interpretability, and the kinds of patterns they can capture.
  Why it matters: The tradeoff helps explain why no single way of creating graph features is best for every task.
• Continuing value of manual features: Justify why manual graph features remain useful even when representations can be learned automatically, including their value for human validation and LLM reasoning.
  Why it matters: Manual features can remain valuable for explanation and reasoning even when automated methods are available.

Key terms: vectorization, featurization, graph-based features, feature engineering, semiautomated features, representation learning, interpretability, manually extracted features, interpretable features, autonomous reasoning about graphs

10.1 Manual node features

The section frames fraud detection as supervised node classification and explains why each person in the network needs a feature representation drawn from local or global graph structure.

• Fraud detection classification task: Describe the example network and the supervised classification task: use labeled people to train a model that predicts whether another person is a fraudster.
  Why it matters: This task explains what the graph features are being built to predict.
• Numerical node feature representation: Explain why each node must be represented by a set of graph-derived features before using the described classification algorithms.
  Why it matters: Feature representation connects graph structure to the inputs a classifier can use.
• Local and global features: Distinguish features drawn from a node's neighborhood from features that measure its role across the wider network.
  Why it matters: The distinction shows how node features can capture both nearby connections and wider network roles.

Key terms: nodes, undirected edges, supervised algorithms, features, label, node features, featurization, metrics, numerical feature vectors, local features

10.1.1 Degree

This section defines node degree and shows how separating fraudulent from legitimate neighbors makes degree more useful for describing a fraud network.

• Global and category-specific degrees: Explain that a node’s global degree counts all direct neighbors, while its fraud degree and legit degree count fraudulent and legitimate direct neighbors separately. Describe why the split gives a more informative picture of a node’s connections.
  Why it matters: Two nodes with the same number of neighbors may have very different fraud-related connections.

Key terms: degree, global degree, fraud degree, legit degree, direct neighbors

10.1.2 Triangles

Defines graph triangles and explains what they indicate about a node’s neighborhood, including how the example classifies triangles by the fraud status of two alters.

• Three-node triangle structure: Explain that a triangle consists of three nodes with a relationship between every pair.
  Why it matters: This definition lets you recognize which groups of nodes count as triangles.
• Egonet triangles and fraud labels: Describe what triangles in a node’s egonet suggest about its neighbors, and distinguish fraudulent, legitimate, and semifraudulent triangles in the example.
  Why it matters: Triangle counts can describe both how tightly connected a neighborhood is and the kinds of groups around a node.

Key terms: triangle, subgraph, egonet, alters, fraudulent, legitimate, semifraudulent

10.1.3 Density

This section defines graph density as the share of possible edges that exist and shows how to calculate it for a node’s egonet.

• Observed versus possible edges: Explain that density measures the portion of possible connections that appear in a graph. For N nodes, compare the observed edge count M with the N(N − 1)/2 edges possible when every pair is connected.
  Why it matters: The possible-edge count gives the observed connections a meaningful scale.
• Egonet density calculation: Apply the density calculation to a node’s egonet: node A’s seven-node egonet has 21 possible edges and seven observed edges, giving a density of about 0.33. Distinguish this structural measure from a fraud-specific or legitimate-specific measure.
  Why it matters: An egonet density describes local connectivity without treating fraud or legitimate labels as part of the calculation.

Key terms: density, possible edges, observed edges, egonet, egonet density, fraud density, legit density

10.1.4 Geodesic (or shortest) path

This subsection turns shortest-path distances and nearby-fraudster path counts into features for a fraud detection network, then explains why they are computed automatically.

• Fraud-oriented path features: Explain how geodesic distance and counts of short paths to fraudulent nodes can serve as graph features. Describe why shorter and more numerous paths may indicate greater potential for fraudulent behavior to affect a target node.
  Why it matters: These features capture both how close a node is to known fraud and how many short connections it has to fraudsters.
• Practical shortest-path computation: Explain why the section moves from manually counting paths to automated computation, and describe the Dijkstra-based implementation's scope.
  Why it matters: Automation makes the proposed path features practical beyond the small network used for illustration.

Key terms: geodesic path, shortest path, geodesic distance, hops, fraudulent nodes, Dijkstra’s algorithm, networkx, single source, predefined distance

10.1.5 Closeness

This section explains how closeness centrality uses shortest-path distances to measure a node’s position in a network, including when some nodes are unreachable.

• Farness and closeness centrality: Explain how farness averages a node’s shortest-path distances to all other nodes, and how closeness centrality reverses that measure so more central nodes receive higher values.
  Why it matters: It lets you interpret a node’s centrality in terms of its distances to the rest of the network.
• Closeness in disconnected networks: Describe how the closeness calculation handles nodes that cannot be reached and why it does so.
  Why it matters: Real networks may be disconnected, so unreachable nodes affect which distances can be used meaningfully.

Key terms: closeness centrality, farness, geodesic, shortest path, reachable nodes, disconnected components

10.1.6 Betweenness

This section explains betweenness centrality as a measure of how often a node bridges shortest paths and shows how its scores can identify important nodes in a fraud network.

• Shortest-path bridge measure: Explain how betweenness centrality measures a node’s role on shortest paths between other nodes, and distinguish it from closeness centrality.
  Why it matters: It gives you a way to describe a node’s bridging role, not just its reachability.
• Bridge score interpretation: Describe what high and zero betweenness scores suggest about bridges and potential information-flow bottlenecks in the fraud network.
  Why it matters: Interpreting these scores can help identify network bottlenecks or nodes worth monitoring in fraud detection.

Key terms: betweenness centrality, closeness centrality, shortest paths, σst, σst(v), betweenness values, normalized, bottlenecks, fraud detection

10.1.7 PageRank

This section explains how PageRank measures node importance and how comparing ordinary and fraud-weighted scores can flag nodes for investigation.

• Incoming connection quality: Explain why PageRank reflects more than the number of connections a node has: incoming connections from highly ranked nodes raise its score.
  Why it matters: This distinction explains why counting connections alone can miss an important node.
• Fraud-weighted score comparison: Distinguish base PageRank, which treats connections equally, from fraud-weighted PageRank, which gives more weight to connections from known fraudulent nodes. Explain why a node whose fraud-weighted score rises relative to its base score might warrant investigation.
  Why it matters: The comparison can highlight fraud-related connections that a node's general network importance does not reveal.

Key terms: PageRank, incoming connections, node importance, base PageRank, fraud-weighted PageRank, known fraudulent nodes

10.1.8 Prediction

This subsection uses manually extracted node features to train a fraud classifier and explains how to prepare, interpret, and judge the resulting predictions.

• Iterative node feature prediction: Trace how extracted node features become inputs to a logistic-regression fraud classifier, and explain why feature design may be repeated until prediction quality is sufficient.
  Why it matters: The graph metrics become useful for fraud prediction only when they are assembled and evaluated as classifier inputs.
• Balanced and scaled model inputs: Explain why the section uses a stratified training–testing split and StandardScaler, and what feature-importance analysis is intended to show.
  Why it matters: These steps make the classifier evaluation more representative and its influential graph metrics easier to identify.
• Manual feature tradeoffs: Justify when this manual feature approach is useful and explain why the subsection does not interpret its sample-graph results.
  Why it matters: It distinguishes the method’s interpretability advantage from claims the small demonstration cannot support.

Key terms: node features, logistic regression, feature vector, training, validation, stratified split, StandardScaler, feature importance, fraudulent nodes, legitimate nodes

10.2 Manual relationship features

The section frames link prediction as a node-pair classification task and introduces two ways to represent potential relationships as features.

• Relationship prediction as classification: Explain that relationship prediction takes a pair of nodes and predicts whether a link exists or what type of link it might be, using features that represent the potential connection rather than just an individual node.
  Why it matters: It clarifies what the model must represent when the prediction concerns a connection rather than a node.
• Two relationship feature approaches: Distinguish node-based combinations, which combine the source and target nodes’ feature vectors, from path-based features, which describe connection patterns between the nodes. State the section’s broad contrast: node-based combinations work well with node embeddings, while path-based features capture complex network patterns.
  Why it matters: The distinction gives you two different sources of features for describing a possible link.

Key terms: relationship prediction, link prediction, node pair, binary classification, multiclass classification, node-based combination, feature vectors, node embeddings, path-based features, two-hop paths

10.2.1 Node-based representation

This section explains how to turn two node feature vectors into a representation of a possible link and how to choose a combination method.

• Node-pair link representation: Explain how combining the feature representations of two nodes creates a representation for a possible link, including when the nodes are not currently connected.
  Why it matters: Link prediction needs a way to describe candidate connections as well as existing ones.
• Joining and averaging vectors: Describe concatenation and element-wise averaging as ways to combine two node vectors, including their effects on the output dimension.
  Why it matters: These methods produce link features with different sizes and different ways of retaining the node information.
• Difference and product features: Distinguish L1, L2, and Hadamard combinations by what each computes at corresponding vector positions.
  Why it matters: The choice of operation changes what the resulting link features express about the two nodes.
• Composition method selection: Explain why link-prediction quality depends on both the node representations and their combination method, and why benchmarking helps select a method.
  Why it matters: Testing combinations helps identify what works for a particular link-prediction problem rather than assuming one method is always best.

Key terms: node-based representation, feature representations, link prediction, Catenate, Average, element-wise average, L1, Manhattan distance, L2, Euclidean distance

10.2.2 Path-based features

This section shows how to represent compound–disease pairs with metapath-based features, make path counts less sensitive to highly connected nodes, and limit the work needed to extract useful features.

• Metapath Features for Node Pairs: Explain how paths through a biomedical graph become features for a compound–disease pair, even when the pair has no direct connection.
  Why it matters: This turns network connectivity into inputs a treatment-prediction model can use.
• Degree-Weighted Path Counts: Explain why raw path counts can mislead and how degree-weighted path count changes the contribution of paths through highly connected nodes.
  Why it matters: Damping hub-heavy paths helps the feature reflect more specific biological connections rather than sheer connectivity.
• Metapath and Pair Selection: Describe the two reductions used to make metapath-based feature extraction more manageable and relevant.
  Why it matters: Selecting both paths and pairs reduces computation while focusing the model on more relevant evidence.
• LLM Assistance with Feature Queries: Describe how an LLM can help turn specified metapaths into feature-extraction queries and what context the example prompt supplies.
  Why it matters: A well-specified prompt can help produce the queries needed to extract path-based relationship features.

Key terms: metapath, compound–disease pair, relationship features, Hetionet, path count, degree-weighted path count, DWPC, intermediate nodes, damping factor, metapath reduction

10.3 Semiautomated feature extraction

This section explains how ReFeX extracts interpretable structural graph features with less manual work, while retaining a role for domain experts.

• ReFeX as a hybrid approach: Explain why ReFeX offers a middle ground between manual feature engineering and neural approaches, including why domain experts still review its features.
  Why it matters: It explains how automation can reduce manual effort without giving up understandable features.
• Structural and transferable features: Describe what information ReFeX uses and why its resulting node features can be useful across graphs or over time.
  Why it matters: Structural features can support predictions and meaningful comparisons even when graphs change.
• Three feature extraction stages: Trace ReFeX’s local, egonet, and recursive feature extraction stages using the examples given in the section.
  Why it matters: The three stages show how simple connectivity measures become descriptions of broader graph structure.
• Recursive feature pruning: Explain why ReFeX prunes generated features and identify the pruning approaches described here.
  Why it matters: Pruning keeps recursive feature generation from producing an unmanageable set of similar features.

Key terms: ReFeX, Recursive Feature eXtraction, interpretability, human oversight, structural, regional features, feature matrix F, transferable across graphs, local feature extraction, degree

10.3.1 Performing ReFeX manually

The section works through ReFeX on a small undirected graph, from degree and egonet features to recursive aggregation of neighboring features.

• Degree and egonet features: Describe how the example establishes node degree and counts the nodes, internal edges, and edges leaving a node’s egonet.
  Why it matters: These local counts provide the starting features for the recursive part of ReFeX.
• Recursive neighbor feature aggregation: Explain how ReFeX repeatedly aggregates neighboring feature values to capture broader structural context, using node A’s mean calculations as an example.
  Why it matters: Repeating aggregation lets node features reflect more than their immediate local counts.

Key terms: degree, egonet, internal edges, in/out egonet edges, recursive feature aggregation, SUM operator, MEAN operator, iteration

10.3.2 Performing ReFeX automatically with code

This section positions ReFeX between manual feature engineering and autonomous representation learning, explaining its practical strengths and limitations.

• ReFeX structural feature extraction: Explain that ReFeX automates feature extraction from graph structure and can capture meaningful characteristics of nodes and their neighborhoods without fully autonomous representation learning.
  Why it matters: This explains what ReFeX contributes without treating it as a fully autonomous approach.
• ReFeX practical trade-offs: Describe why ReFeX can be useful when features must be traceable, reproducible, or updated as a graph changes, and state its limits concerning node attributes, edge types, and feature selection.
  Why it matters: These trade-offs help determine when ReFeX is a suitable feature-engineering choice.

Key terms: ReFeX, automated feature extraction, graph structure, structural patterns, interpretability, deterministic, selective recomputation, node attributes, edge types, pruning

10.4 Summary