Source-linked AI summary
Learning Convolutional Neural Networks for Graphs
Mathias Niepert, Mohamed Ahmed, Konstantin Kutzkov
TL;DR
Graph learning lacks a general way to apply CNNs when graph nodes are unordered, unaligned, and structurally diverse. PATCHY-SAN selects nodes, extracts and normalizes fixed-size neighborhoods as receptive fields, and combines them with CNN components. On benchmark datasets, the learned representations are competitive with state-of-the-art graph kernels, while receptive-field generation is efficient enough to saturate a downstream CNN.
Problem
The paper addresses graph classification, regression, and property inference when node order is missing and vertices across input graphs are not aligned.
Method
PATCHY-SAN selects an ordered fixed-length node sequence, assembles exactly k-node neighborhoods, normalizes them into fixed linear orders, and learns their representations with CNN layers.
Results
The learned representations are competitive with state-of-the-art graph kernels, while PATCHY-SAN is 2 to 8 times more efficient than the most efficient graph kernel, WL.
Takeaways & Limitations
The framework provides efficient CNN-based graph representations for directed or undirected graphs with discrete or continuous node and edge attributes.
Takeaways & Limitations
Optimal graph normalization is NP-hard, and future work includes alternative architectures, multiple receptive-field sizes, and pretraining methods.
Abstract
from arXiv · showhide
Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs. These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes. Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs. Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.
1. Introduction
The paper brings CNNs to graph learning by selecting and normalizing locally connected graph neighborhoods as receptive fields. PATCHY-SAN supports arbitrary graph structures and learns representations competitive with state-of-the-art graph kernels.
- Motivation: The paper targets classification and regression on unseen graphs whose nodes are not necessarily in correspondence.It also considers learning representations from a large graph to infer unseen properties such as node types and missing edges.
- Scope: The framework handles directed and undirected graphs with multiple discrete or continuous node and edge attributes.It constructs locally connected neighborhoods analogous to image CNN receptive fields.
- Method: PATCHY-SAN addresses missing node order and graph-to-vector mapping through node selection, fixed-size neighborhood extraction, and normalization.Each normalized neighborhood is uniquely mapped to a fixed linear order and used as a CNN receptive field.
- Method: PATCHY-SAN combines normalized neighborhood graphs with convolutional and dense layers to learn application-dependent graph features.The approach avoids crafting another graph kernel and does not require feature engineering.
- Results: Benchmark experiments show that learned graph CNN representations are competitive with state-of-the-art graph kernels.The architecture is also described as efficient, naively parallelizable, and applicable to large graphs.
2. Related Work
Prior graph-learning methods include graph kernels, recurrent graph neural networks, and CNN extensions for non-grid topologies. Their assumptions and computational characteristics motivate PATCHY-SAN’s graph-based receptive-field construction.
- Graph Kernels: Graph kernels enable kernel methods such as SVMs to operate directly on graphs by comparing graph structures or fixed-sized subgraphs.Representative families include skew spectrum, graphlet, Weisfeiler-Lehman, deep graph, and graph invariant kernels.
- PATCHY-SAN: PATCHY-SAN instead constructs normalized local neighborhoods for graph inputs, allowing existing CNN components to operate without aligned vertices across examples.Its architecture is illustrated as selecting node sequences, assembling neighborhoods, and combining them with CNN components.
- Graph Kernels: Weisfeiler-Lehman kernels support only discrete features and use memory linear in the number of training examples at test time.PATCHY-SAN can use Weisfeiler-Lehman as one graph-labeling procedure for computing receptive fields.
- Graph Neural Networks: Graph neural networks propagate node representations recurrently along graph walks until reaching a fixed point, then use the representations for prediction.The described GNNs support only discrete labels and perform backpropagation operations for graph edges and nodes per learning iteration.
- CNN Extensions: Several CNN extensions address non-grid topologies, but they assume one global graph structure with corresponding vertices across input examples.Another approach develops convolution-like operations for graphs through a differentiable variant of one graph feature.
3. Background
The background defines CNNs as local pattern extractors and formalizes graphs, node orderings, labelings, partitions, and canonicalization. These concepts provide the basis for constructing ordered graph neighborhoods.
- Convolutional Neural Networks: CNNs convolve learned filters over local image regions, producing tensor outputs whose depth equals the number of filters.Typical CNNs combine convolutional and dense layers.
- Graphs: A graph G consists of vertices V and edges E, with an adjacency matrix encoding whether directed vertex pairs are connected.Node and edge attributes provide feature values, while walks, paths, distances, and neighborhoods describe graph structure.
- Labeling and Node Partitions: A graph labeling maps vertices to an ordered set and induces a ranking that determines their relative order.If the labeling is injective, it determines a total vertex order and a unique adjacency matrix ordering.
- Labeling and Node Partitions: Every graph labeling partitions vertices into groups whose members share the same labeling value.This partitioning captures equivalence under the labeling rather than necessarily imposing a unique order.
- Labeling and Node Partitions: Node degree, centrality measures, and Weisfeiler-Lehman color refinement are examples of graph-labeling procedures.Betweenness centrality measures the fraction of shortest paths passing through a vertex.
- Isomorphism and Canonicalization: A graph canonicalization is an isomorphic graph with a fixed vertex order representing the entire isomorphism class.The graph-isomorphism problem is in NP but is not known to be in P or NP-hard.
4. Learning CNNs for Arbitrary Graphs
PATCHY-SAN adapts CNN-style receptive fields to arbitrary graphs by selecting node sequences, assembling local neighborhoods, and normalizing them into fixed vector representations. The normalization aligns structurally similar nodes, while theoretical results connect the method to CNNs and characterize its optimization limits.
- 4.1. Node Sequence Selection: PATCHY-SAN selects a fixed-length sequence of graph nodes and creates one receptive field for each selected node.Nodes are sorted by a graph labeling, traversed with stride s, and padded with all-zero receptive fields when necessary.
- 4.2. Neighborhood Assembly: Each receptive field is assembled as a local neighborhood by breadth-first exploration from its root node.The neighborhood procedure expands through vertices at increasing distance until the receptive-field size k is reached.
- 4.3. Graph Normalization: Graph normalization imposes an order on neighborhood nodes, mapping unordered graph structures into vector spaces while preserving similar structural roles.The procedure ranks nodes using a graph labeling, crops neighborhoods larger than k, pads smaller ones with dummy nodes, and canonicalizes the resulting subgraph.
- 4.3. Graph Normalization: The optimal graph normalization problem minimizes the expected discrepancy between graph-space distances and adjacency-matrix distances induced by a labeling.This problem generalizes graph canonicalization, but its exact optimization is NP-hard.
- 4.3. Graph Normalization: PATCHY-SAN does not solve the optimal normalization problem and instead compares labeling methods to select one performing best for a graph collection.Under dA ≥ dG, the labeling with the smallest estimator ˆθ is selected because it corresponds to the smallest expected absolute difference.
- 4.4. Relation to CNNs: For image grids, PATCHY-SAN with specified receptive-field size, stride, no padding, and 1-WL normalization is identical to a CNN’s first layer up to a fixed permutation.The equivalence holds for receptive field size (2m −1)^2 in PATCHY-SAN and 2m −1 in the corresponding image CNN.
5. Complexity and Implementation
PATCHY-SAN generates graph receptive fields independently, with worst-case complexity linear in the number of graphs and quasi-linear in graph size under 1-WL labeling. Its receptive-field construction is therefore computationally efficient.
- Implementation: Independent receptive-field generation makes PATCHY-SAN highly efficient and naively parallelizable.The fields for separate graph inputs are generated independently.
- Complexity: O(Nw(f(n, m) + n log(n) + exp(k))) is PATCHY-SAN’s worst-case complexity for computing receptive fields for N graphs.Here, k is receptive-field size, w is width, and f(n, m) is the complexity of the graph-labeling procedure.
- Implementation: NAUTY contributes exp(k) to the worst-case bound through graph canonicalization on k-node neighborhoods.The neighborhood size can exceed k, while the canonicalization step operates on a k-node graph.
- Complexity: For 1-WL labeling with w ≪ n and k ≪ n, complexity is linear in N and quasi-linear in m and n.The 1-WL labeling procedure has complexity O((n + m) log(n)).
6. Experiments
Experiments evaluate runtime, learned-feature visualization, and graph classification against established graph kernels. PATCHY-SAN produces receptive fields fast enough to saturate a downstream CNN and achieves competitive or superior classification results across benchmark and social graphs.
- Runtime Analysis: PATCHY-SAN creates more than 1000 receptive fields per second for k = 5 and k = 10 on most tested graphs.Rates fall to 600/s and 320/s for email-enron, respectively; for k = 50, rates remain at least 100/s.
- Runtime Analysis: 200-400 training examples per second is the downstream CNN rate, so receptive-field generation is sufficient to saturate learning.The comparison uses a CNN with two convolutional and two dense layers on the same machine.
- Feature Visualization: PATCHY-SAN features are learned with RBMs from 1-WL-normalized receptive fields, enabling qualitative visualization of graph motifs and structure.The visualization uses receptive fields of size 9 and shows feature weights alongside graphs sampled from corresponding RBM hidden units.
- Graph Classification: Six standard benchmark data sets are used to compare PATCHY-SAN with shortest-path, random-walk, graphlet-count, and Weisfeiler-Lehman kernels.The benchmark collection includes MUTAG, PTC, NCI1, NCI109, PROTEINS, and D&D.
- Graph Classification: A one-fits-all CNN architecture yields accuracy highly competitive with existing graph kernels, with receptive-field size k = 10 usually performing best.The study uses a shared architecture across experiments and omits NCI109 because its results are almost identical to NCI1.
- Graph Classification: 2 to 8 times greater efficiency than the Weisfeiler-Lehman kernel is reported, while logistic regression performs worse than CNN-based learning on the receptive fields.The authors attribute the CNN advantage to nonlinear feature combinations and shared weights across receptive fields.
- Social Graphs: PATCHY-SAN significantly outperforms two other kernels on four of six social graph data sets and ties them on the remainder.Larger social graph collections contain up to 12000 graphs with an average of 400 nodes, and normalized node degree is used as a continuous attribute.
7. Conclusion and Future Work
The framework combines node-sequence selection with locally normalized neighborhood representations to support CNN-based graph learning and achieves competitiveness with state-of-the-art graph kernels. Future work includes extending the approach with alternative architectures, receptive-field combinations, pretraining, and statistical relational models.
- The framework combines node-sequence selection covering large graph regions with locally normalized neighborhood representations for CNNs.
- Experiments show that the approach is competitive with state-of-the-art graph kernels.
- Future work includes alternative neural architectures, multiple receptive-field sizes, pretraining with RBMs and autoencoders, and statistical relational models.