PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Capsule Convolutional Neural Networks

Saurabh Verma, Zhi-Li Zhang

arXiv:1805.08090v4stat.MLcs.CVcs.LG

TL;DR

Standard GCNNs face limitations in retaining local information and producing permutation-invariant graph representations for graph classification. The paper proposes GCAPS-CNN, combining capsule representations with covariance-based invariance and global features, and reports stronger results than existing deep-learning methods and graph kernels on many benchmark datasets.

  • Problem

    Standard GCNNs aggregate local node values and are permutation equivariant, leaving information-loss concerns and requiring an additional invariant layer for graph classification.

    Source: §1 · pp. 1–2

  • Method

    GCAPS-CNN uses capsule vectors for richer local representations, a covariance-based permutation-invariant layer, and FGSD global features when node features are missing.

    Source: §4.2 · p. 6, §7 · p. 10

  • Results

    GCAPS-CNN showed superior performance on many bioinformatics and social-network datasets versus existing deep-learning methods and graph kernels; social datasets gained at least 4% −9% accuracy against graph kernels.

    Source: §7 · p. 10, §6 · p. 10

  • Takeaways & Limitations

    The paper reports covariance as a fast permutation-invariant alternative that performs better than aggregation or max-sort pooling for graph classification.

    Source: §7 · p. 10

    Polynomial-coefficient capsule functions are costly to compute at each node and can be numerically unstable, so the authors leave this direction for future work.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Graph Convolutional Neural Networks (GCNNs) are the most recent exciting advancement in deep learning field and their applications are quickly spreading in multi-cross-domains including bioinformatics, chemoinformatics, social networks, natural language processing and computer vision. In this paper, we expose and tackle some of the basic weaknesses of a GCNN model with a capsule idea presented in \cite{hinton2011transforming} and propose our Graph Capsule Network (GCAPS-CNN) model. In addition, we design our GCAPS-CNN model to solve especially graph classification problem which current GCNN models find challenging. Through extensive experiments, we show that our proposed Graph Capsule Network can significantly outperforms both the existing state-of-art deep learning methods and graph kernels on graph classification benchmark datasets.

1. Introduction

The introduction identifies limitations of standard GCNNs, especially for graph classification, and presents GCAPS-CNN as a capsule-based model to address them. Its proposed components include richer local node representations, a covariance-based permutation-invariant layer, and explicit global graph features.

1. Introduction

  • The paper positions GCAPS-CNN as a graph-classification-focused model while noting that its capsule idea can also be used in GCNNs for semi-supervised learning or graph sequence learning.The latter includes Graph Convolution Recurrent Neural Network models.Source: §1 · p. 1
  • Graph capsules replace scalar convolution outputs with small vectors containing higher-order neighborhood statistics to address information loss in local aggregation.The neighborhood is defined as in standard GCNNs.Source: §1 · pp. 1–2
  • Standard GCNN outputs are permutation equivariant, so graph classification needs an additional differentiable permutation-invariant layer to give isomorphic graphs consistent outputs.For node permutation matrix P, the GCNN output transforms as f(PX, PLP^T) = Pf(X, L).Source: §1 · p. 2
  • A covariance-based layer is proposed to produce permutation-invariant graph representations, with the authors reporting it as better than aggregation or max pooling and efficient to compute.The layer requires a single dense-matrix multiplication.Source: §1 · p. 2
  • GCNN filters provide local aggregate views, and node-degree features are not very helpful when node labels are absent; the paper proposes graph spectral distances as global features.The proposed model is designed to include global graph features at each node.Source: §1 · p. 2

2. Related Work

Related work covers graph kernels, explicit graph features, and graph convolutional approaches to graph classification. It also describes message passing and permutation-invariant strategies used with GCNNs.

2. Related Work

  • Graph kernels compare graphs through inner products of vectors that count substructure frequencies, with methods differing in which substructures they use.Examples include graphlets, random-walk, shortest-path, and Weisfeiler-Lehman subtree kernels.Source: §2 · p. 3
  • Explicit graph-feature methods include FGSD, based on graph spectral distances, while graphlet and skew spectra are noted to have O(N^3) computational complexity.The passage says FGSD comes with certain theoretical guarantees.Source: §2 · p. 3
  • Graph convolution approaches learn filters associated with the graph Laplacian, with later models using propagation rules, localized spectral filters, pooling, or sequences of local nodes.The graph-convolution idea is traced to graph signal processing; localized spectral filters are described by Defferrard et al. (2016), and local-node sequences by Niepert et al. (2016).Source: §2 · p. 3
  • Message passing updates node states using neighbor messages and shared recurrent-network weights; cited graph-classification approaches use aggregation, max-sort pooling, or group theory for permutation invariance.The passage relates the number of message-passing iterations to GCNN depth.Source: §2 · p. 3

3. Graph Capsule CNN Model

Standard graph convolutions reduce each node’s neighborhood to scalar feature values, potentially losing information. GCAPS-CNN instead builds vector-valued capsules from neighborhood statistics and uses them within a graph convolutional model.

3. Graph Capsule CNN Model

  • Standard graph convolution can lose neighborhood information by reducing each feature’s local neighborhood to a single scalar.The proposed capsule approach is intended to remedy this information loss.Source: §3 · p. 4

3.1. Graph Capsule Networks

  • GCAPS-CNN replaces scalar neighborhood functions with vector-valued capsule functions that capture higher-order statistical information.The capsule outputs are instantiation parameters intended to encode local neighborhood values.Source: §3.1 · pp. 4–5
  • Higher-order statistical moments provide permutation-invariant instantiation parameters that can be computed efficiently using matrix multiplication.The capsule output has dimensions N × h × p, where p is the number of instantiation parameters.Source: §3.1 · p. 5
  • Capsule functions should preserve neighborhood information, remain permutation invariant to input-node order, and be efficient to compute.The paper describes bijectivity as the desired property for encoding and decoding neighborhood values.Source: §3.1 · pp. 4–5
  • Polynomial coefficients can recover neighborhood values up to permutation, but computing them costs O(k^2) without FFT and raises numerical-instability concerns.The authors leave further work on addressing these issues for future work.Source: §3.1 · p. 5

4. Designing Graph Permutation Invariant Layer

The section examines permutation-invariant graph features for classification, including a failure mode of Max-Sort Pooling. It proposes covariance features, which are permutation invariant and pass the paper’s sub-graph isomorphism feature test.

4.1. Problems with Max-Sort Pooling Layer

  • Max-Sort Pooling fails the sub-graph isomorphism feature test because node ordering can make corresponding feature entries incomparable.Adding a node absent from the smaller graph can disrupt the comparison order.Source: §4.1 · p. 6

4.2. Covariance as Permutation Invariant Layer

  • Covariance is differentiable, independent of node order, and computed with a single matrix multiplication.The method flattens the last two dimensions of the GCAPS-CNN layer output before computing covariance.Source: §4.2 · p. 6
  • Flattening the symmetric covariance matrix yields a graph feature vector whose dimension is independent of the number of nodes and can be adjusted for computational constraints.The covariance also includes information about shapes, norms, and angles between node hidden features.Source: §4.2 · p. 6
  • The covariance layer produces permutation-invariant features and passes the sub-graph isomorphism feature test by comparing corresponding feature dimensions.The covariance output compares norms and angles between corresponding pairs of feature-dimension vectors.Source: §4.2 · pp. 6–7

5. Designing GCAP-CNN with Global Features

GCNN layers capture only bounded local neighborhoods, while graph classification can depend on global structure. The section proposes adding FGSD features and concatenating intermediate outputs to address this gap while preserving isomorphism invariance.

5. Designing GCAP-CNN with Global Features

  • With polynomial filters of degree k, an ℓ-layer GCNN node output depends only on input values within kℓ hops.The theorem bounds the local receptive field of the model.Source: §5 · p. 7
  • Aggregation captures only average variation over kℓ-hop neighborhoods; increasing filter order or depth raises complexity and sample needs, so the authors prefer depth.Increasing filter order also broadens the GCNN layer.Source: §5 · p. 7
  • Global features use the full graph structure, which matters because graph labels depend on global information and node degree alone is insufficient when node features are missing.A very deep GCNN could capture more global information but requires higher sample complexity.Source: §5 · p. 7
  • FGSD features are per-node histograms of harmonic distances to all nodes; the model adds them when node features are missing, including in the social-network experiments.The authors also say FGSD can be concatenated with original node features.Source: §5 · p. 7
  • Concatenated outputs from intermediate layers feed the covariance and fully connected layers, and the end-to-end model is guaranteed to give identical outputs for isomorphic graphs.The covariance and fully connected layers receive outputs concatenated across intermediate layers.Source: §5 · p. 7

6. Experiment and Results

Across bioinformatics and social-network graph-classification benchmarks, GCAPS-CNN generally outperforms the compared deep-learning methods and graph kernels, with some dataset-specific exceptions and gains. The experiments use 10-fold cross-validation and compare against both method families.

6. Experiment and Results

  • The GCAPS-CNN configuration uses graph-capsule layers, concatenated intermediate outputs, mean-and-covariance pooling, fully connected layers, and softmax classification.Layer count and hidden dimensions vary with dataset size; capsule instantiation parameters are restricted to 1–4 for computational reasons.Source: §6 · p. 8
  • The evaluation covers six bioinformatics and five social-network graph-classification datasets, using 10-fold cross-validation to report average classification accuracy.The bioinformatics datasets include PTC, PROTEINS, NCI1, NCI109, D&D, and ENZYMES.Source: §6 · p. 8
  • The comparisons include four graph-convolutional neural-network baselines and six graph-kernel baselines, with prior-work results used for some methods.Kernel performance is evaluated using LIBSVM and independently tuned training-fold parameters.Source: §6 · p. 8
  • 1%–6% classification-accuracy gains over most deep-learning methods on bioinformatics datasets (except D&D), alongside up to 4% on COLLAB and around 1% elsewhere socially.The reported social-network gain reaches 4% on COLLAB; other datasets show around 1% gain against deep-learning approaches.Source: §6 · pp. 8, 10, Table 1 · p. 9, Table 2 · p. 9
  • 1%–3% accuracy gains over strong graph kernels on many bioinformatics datasets and at least 4%–9% on social-network datasets are reported.The highest reported gains are on PTC and REDDIT-MULTI, respectively.Source: Table 1 · p. 9, Table 2 · p. 9, §6 · p. 10

7. Conclusion & Future Work

GCAPS-CNN combines capsule-based local representations with covariance-based permutation invariance and explicit global features, and the authors report strong benchmark performance. They leave more information-preserving capsule functions and other design choices for future work.

7. Conclusion & Future Work

  • The model uses capsule functions that preserve statistical moments for faster computation and capture richer local structure information.The authors describe capsules as providing richer representations of graph nodes or the whole graph.Source: §7 · p. 10
  • GCAPS-CNN is reported to achieve state-of-the-art performance on bioinformatics and social-network datasets against deep-learning methods and graph kernels.The authors also characterize it as capturing richer representations of individual nodes or the whole graph.Source: §7 · p. 10
  • Future work includes more sophisticated information-preserving capsule functions, kernel density estimation, and alternative ways to manage capsule-vector dimensions.Polynomial coefficients are one proposed instantiation-parameter choice with theoretical guarantees.Source: §7 · p. 10

Related papers

Loading 1805.08090v4…