Graph Classification

The core challenge is to learn a fixed-size vector representation (an embedding) for an entire graph of variable size and structure. This is achieved through graph pooling or readout functions that aggregate node-level features learned by a Graph Neural Network (GNN). Common techniques include:

• Global mean/max/sum pooling: Simple aggregation of all node embeddings.
• Hierarchical pooling: Learns to coarsen the graph iteratively, preserving hierarchical structure.
• SortPooling: Sorts node features to create a fixed-length sequence for a 1D convolutional layer. The resulting graph-level embedding is then fed into a standard classifier (e.g., a multilayer perceptron).

Effective classification relies on capturing the graph's topological properties, which go beyond simple node attributes. Key structural features include:

• Global graph statistics: Diameter, average path length, density, and assortativity.
• Subgraph patterns: Counts of specific motifs (e.g., triangles, stars) or graphlets.
• Spectral features: Derived from the eigenvalues and eigenvectors of the graph's Laplacian matrix, capturing connectivity properties.
• Centrality distributions: The distribution of node importance scores (e.g., betweenness, eigenvector centrality) across the graph. These features can be used directly in traditional classifiers (e.g., Random Forests) or as complementary signals to GNNs.

A fundamental requirement for a graph classification model is permutation invariance. The predicted label must not change if the nodes of the input graph are re-ordered (i.e., the graph is isomorphic). This is a non-trivial constraint for neural networks. Solutions include:

• Using symmetric pooling functions: Sum, mean, and max are inherently permutation-invariant aggregation operations.
• Designing GNN layers with shared parameters: Message-passing GNNs apply the same transformation to each node, making them inherently equivariant to node ordering.
• Graph kernels: Kernel methods like the Weisfeiler-Lehman (WL) subtree kernel explicitly compare graphs in an isomorphism-invariant manner by iteratively hashing neighborhood structures.

Important patterns for classification often exist at multiple scales within a graph. Modern architectures capture this through hierarchical processing:

• Stacked GNN layers: Each layer aggregates information from a larger neighborhood (K-hop). Deeper layers capture more global structure.
• Differentiable pooling (DiffPool): Learns to assign nodes to clusters in a soft, hierarchical manner, creating a coarsened graph at each layer.
• Jumping Knowledge Networks: Combine representations from all GNN layers, allowing the final classifier to access both local and global features. This multi-scale approach is critical for distinguishing graphs where the defining characteristic is a specific subgraph (local) versus the overall connectivity pattern (global).

Real-world business graphs often contain multiple node and edge types (e.g., in a knowledge graph: Customer, Product, Transaction). Heterogeneous Graph Neural Networks (HGNNs) extend GNNs for this complex data:

• Type-specific transformations: Use different weight matrices for messages passed along different relation types.
• Meta-paths: Predefined sequences of node/edge types (e.g., User -buys-> Product -bought_by-> User) are used to guide attention and aggregation.
• Heterogeneous graph transformers: Apply transformer-style attention mechanisms across nodes and edges of different types. This allows classification of complex enterprise networks, such as categorizing a supply chain graph by its risk profile or a social network by its community structure type.

Graph classification translates structural business data into actionable categories. Key enterprise use cases include:

• Financial Fraud Detection: Classifying transaction networks as fraudulent or legitimate based on the connectivity patterns between accounts and entities.
• Molecular Property Prediction: In drug discovery, classifying molecular graphs (atoms=nodes, bonds=edges) by their toxicity or bioactivity.
• Document Categorization: Representing a corpus as a graph of terms (nodes) and their co-occurrence (edges) to classify document topics.
• Supply Chain Risk Assessment: Classifying a supplier network graph as high, medium, or low risk based on its centrality, redundancy, and geographic dispersion.
• Social Network Analysis: Categorizing online community graphs by their primary function (e.g., support, interest-based, professional).

A Graph Neural Network (GNN) is a class of deep learning architectures specifically designed to operate on graph-structured data. For graph classification, GNNs are the primary model family. They work by an iterative process of message passing, where each node aggregates feature information from its neighbors. After several layers of propagation, a readout function (like global mean pooling) aggregates all node representations into a single vector that represents the entire graph, which is then passed to a classifier.

• Key Architectures: Graph Convolutional Networks (GCNs), Graph Attention Networks (GATs), and Graph Isomorphism Networks (GINs) are commonly used.
• Role in Classification: They enable end-to-end learning of discriminative graph-level features directly from node attributes and topology.

Graph embedding is a technique that maps nodes, edges, or entire graphs to low-dimensional vector representations (embeddings) in a continuous vector space. For graph classification, whole-graph embeddings are critical. Traditional, non-neural methods like graph kernels (e.g., Weisfeiler-Lehman subtree kernel) compute a similarity score between graphs that can be used with kernelized classifiers like SVMs. Neural methods often use GNNs to generate these embeddings.

• Purpose: The embedding preserves the structural properties and relational information of the graph, transforming it into a fixed-size numerical format suitable for standard machine learning classifiers.

The Weisfeiler-Lehman (WL) test is a classical, efficient algorithm for graph isomorphism testing. It forms the theoretical foundation for many modern graph kernels and GNNs. The algorithm iteratively refines node labels by aggregating the multiset of labels from a node's neighbors, creating a histogram of labels for the entire graph at each iteration.

• Connection to GNNs: The expressive power of many GNNs is upper-bounded by the WL test; they are as powerful as the WL test at distinguishing non-isomorphic graphs.
• Use in Kernels: The WL subtree kernel uses the label sequences from the test to compute a similarity measure between graphs, serving as a powerful feature extractor for kernel-based classification.

Graph pooling (or coarsening) is an operation that reduces the number of nodes in a graph while preserving its overall structure, analogous to pooling layers in convolutional neural networks for images. In hierarchical GNNs for classification, pooling is essential for learning at multiple scales and creating a graph-level representation.

• Types: Topology-based pooling (e.g., Graclus, edge contraction) and feature-based pooling (e.g., DiffPool, SAGPool) which uses node features to learn a soft assignment matrix.
• Goal: To progressively summarize subgraph information, ultimately producing a single, rich representation vector for the entire input graph to feed into the final classification layer.

A graph kernel is a kernel function that computes an inner product (a measure of similarity) between pairs of graphs in a high-dimensional feature space without explicitly computing the feature vectors. They enable the application of kernel methods like Support Vector Machines (SVMs) to graph classification tasks.

• Common Kernels: Weisfeiler-Lehman subtree kernel, random walk kernel, and shortest-path kernel.
• Mechanism: They decompose graphs into substructures (e.g., walks, subtrees, small subgraphs) and count their occurrences. The kernel value is high if two graphs share many common substructures.

This distinction is crucial in graph learning settings:

• Inductive Learning: The model learns a general mapping from graph features to labels. It can make predictions on completely unseen graphs that were not present in the training set. Most graph classification tasks are inductive.
• Transductive Learning: The model has access to the entire graph (including test nodes) during training but labels are missing for some nodes. It learns to embed this specific graph and predict missing labels for nodes within it. This is typical for node classification tasks.

For enterprise applications, inductive learning is essential, as models must generalize to new, previously unseen data graphs (e.g., classifying a new molecule or a new transaction network).