PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Convolutional Networks with EigenPooling

Yao Ma, Suhang Wang, Charu C. Aggarwal, Jiliang Tang

arXiv:1904.13107v2cs.LGstat.ML

TL;DR

Graph-level representations from graph neural networks can overlook global and local structural information during pooling. The paper introduces EigenPooling, combines it with GCN layers in EigenGCN, and reports effective graph classification performance across six benchmarks.

  • Problem

    Graph neural networks need graph-level representations for graph classification, but global pooling and recent hierarchical methods neglect graph or local subgraph structure.

  • Method

    EigenPooling uses graph Fourier transform through subgraph eigenvectors, and EigenGCN combines the resulting pooling layers with GCN convolutional layers for hierarchical graph representation learning.

  • Results

    EigenGCN achieves effective graph classification performance on 6 commonly used benchmarks.

  • Takeaways & Limitations

    The framework provides hierarchical graph representations that use node features and local subgraph structure during pooling.

  • Takeaways & Limitations

    The local analysis assumes a single-dimensional graph signal without loss of generality, and retaining most information with few coefficients relies on natural graph signals concentrating in early spectral components.

Abstract

from arXiv · show

Graph neural networks, which generalize deep neural network models to graph structured data, have attracted increasing attention in recent years. They usually learn node representations by transforming, propagating and aggregating node features and have been proven to improve the performance of many graph related tasks such as node classification and link prediction. To apply graph neural networks for the graph classification task, approaches to generate the \textit{graph representation} from node representations are demanded. A common way is to globally combine the node representations. However, rich structural information is overlooked. Thus a hierarchical pooling procedure is desired to preserve the graph structure during the graph representation learning. There are some recent works on hierarchically learning graph representation analogous to the pooling step in conventional convolutional neural (CNN) networks. However, the local structural information is still largely neglected during the pooling process. In this paper, we introduce a pooling operator $\pooling$ based on graph Fourier transform, which can utilize the node features and local structures during the pooling process. We then design pooling layers based on the pooling operator, which are further combined with traditional GCN convolutional layers to form a graph neural network framework $\m$ for graph classification. Theoretical analysis is provided to understand $\pooling$ from both local and global perspectives. Experimental results of the graph classification task on $6$ commonly used benchmarks demonstrate the effectiveness of the proposed framework.

1 INTRODUCTION

Graph classification requires graph-level representations that retain structural information, but global and existing hierarchical pooling methods neglect important graph or local subgraph structure. The paper introduces EigenPooling and EigenGCN to address this gap.

  • Graph classification predicts a graph label from its features and structure, requiring a graph-level representation.
  • Global summarization treats nodes equivalently and overlooks the graph structure when generating graph representations.
  • Existing hierarchical pooling methods coarsen graphs into supernodes but commonly use average or max pooling that neglects local subgraph structures.
  • Variable subgraph sizes and differing structures make it challenging to design a general fixed-size pooling operator using local structure.
  • EigenPooling uses subgraph eigenvectors to summarize node features while capturing local structures, and EigenGCN combines these pooling layers with graph neural network layers.
  • The paper provides local and global theoretical analysis and evaluates EigenGCN on numerous real-world graph classification benchmarks.

2 THE PROPOSED FRAMEWORK – EigenGCN

EigenGCN alternates graph convolution with spectral-clustering-based coarsening and EigenPooling to hierarchically transform node features and graph structure into graph representations. EigenPooling uses graph Fourier information from subgraphs, while retaining most information when only the first H coefficients are used.

  • 2 THE PROPOSED FRAMEWORK – EigenGCN: EigenGCN stacks graph convolution, graph coarsening, and EigenPooling layers to hierarchically learn graph-level representations for classification.
  • 2.1 An Overview of EigenGCN: GCN layers transform input node features into final node representations, but their output remains a matrix rather than a graph-level vector.
  • 2.1 An Overview of EigenGCN: Global pooling can produce a graph representation by averaging node representations, but it overlooks key information and graph structure.
  • 2.1 An Overview of EigenGCN: Each EigenGCN pooling layer coarsens a graph into fewer nodes and pools the graph signal onto that coarsened graph.
  • 2.2 Graph Coarsening: Spectral clustering partitions the graph into non-overlapping subgraphs, which become supernodes and determine the pooling ratio.
  • 2.3 Eigenvector-Based Pooling – EigenPooling: EigenPooling transforms node features into coarsened-node features using subgraph structure and node features, with graph Fourier analysis based on Laplacian smoothness.
  • 2.3.2 The Design of Pooling Operators.: Using only the first H pooling operators can preserve most information while reducing computational cost when H ≪ Nmax.

3 THEORETICAL ANALYSIS OF EigenPooling

EigenPooling is analyzed locally as graph Fourier transformation within subgraphs and globally as a filterbank that can preserve graph-signal information. The resulting EigenGCN framework is also shown to be permutation invariant.

  • 3.1 A Local View of EigenPooling: Locally, EigenPooling summarizes each subgraph into a supernode using Fourier coefficients that reflect both node features and subgraph structure.Each coefficient corresponds to an eigenvector with a distinct smoothness, so pooling captures different structural properties of the graph signal.
  • 3.1 A Local View of EigenPooling: Using the first H Fourier coefficients emphasizes smoother signal components while reducing computational cost and preserving most information for natural graph signals.The paper motivates this approximation by the concentration of natural graph signals in their first few spectral coefficients.
  • 3.2 A Global View of EigenPooling: Globally, the pooling operators form a filterbank whose filtered signals are defined on the coarsened graph and can preserve the original signal information.Graph coarsening together with eigenvector pooling also enlarges the receptive field for learning graph representations.
  • 3.2 A Global View of EigenPooling: With Nmax filters, EigenPooling can perfectly reconstruct the input graph signal from its filtered signals.This property follows from the paper’s reconstruction result for the complete set of pooling operators.
  • 3.2 A Global View of EigenPooling: The ℓ2 norm of the input graph signal equals the summed ℓ2 norms of the pooled signals when all Nmax filters are used.With only H ≪ Nmax filters, the method is described as approximately energy/information preserving.
  • 3.3 Permutation Invariance of EigenGCN: EigenGCN is permutation invariant: permuting the adjacency matrix and node features changes neither the learned graph representation nor the relevant subgraph structures.The argument covers GCN, spectral-clustering graph coarsening, EigenPooling, and the final graph representation.

4 EXPERIMENT

The experiments evaluate EigenGCN on six graph-classification benchmarks against representative baselines and examine how the number of EigenPooling filters affects performance and information preservation.

  • 4.1 Data sets: EigenGCN is evaluated on six benchmarks spanning protein, mutagen, and cancer-cell-line graph datasets.The datasets are ENZYMES, PROTEINS, D&D, Mutagenicity, NCI1, and NCI109.
  • 4.2 Baselines and Experimental Settings: Each dataset is randomly split into 80% training, 10% validation, and 10% testing sets, with ten repeated splits.Average performance across the ten splits is reported.
  • 4.3 Performance on Graph Classification: Diff-pool and EigenGCN outperform methods without hierarchical pooling in most cases, indicating that hierarchical aggregation can improve graph representations.EigenGCN outperforms GCN, GraphSage, and SET2SET in most datasets despite sharing their convolutional layer.
  • 4.4 Understanding Graph Signals: For most datasets, using more eigenvectors improves performance, although additional eigenvectors can preserve noise and fail to improve or worsen results.The analysis evaluates how much signal information is retained by the first H Fourier coefficients.
  • 4.3 Performance on Graph Classification: EigenGCN achieves state-of-the-art or at least comparable performance on all datasets.The paper attributes this result to the effectiveness of EigenPooling within the EigenGCN framework.
  • 4.4 Understanding Graph Signals: Most datasets concentrate graph-signal magnitude in their first few Fourier coefficients, supporting H ≪ Nmax filters and lower computational cost.The first H coefficients preserve the majority of information for natural graph signals.

5 RELATED WORK

Related work includes message-passing and graph-Fourier approaches to graph neural networks, while graph classification requires methods that summarize node representations into graph representations.

  • Message-passing methods: Message-passing graph neural networks transform, propagate, and aggregate node features across graph edges.This family includes methods for node- and graph-level representation learning.
  • Spectral methods: Graph-Fourier graph neural networks transform features into the spectral domain, apply learnable filters, and transform them back.The paper discusses connections between spectral and message-passing approaches.
  • Graph-level representation: Pure graph neural network layers are flat because they output node representations for all graph nodes.Graph classification therefore requires an additional procedure to summarize node representations into a graph representation.

6 CONCLUSION

The paper introduces EigenPooling and EigenGCN to hierarchically learn graph-level representations using local graph Fourier information, and reports strong performance on graph-classification benchmarks.

  • 6 CONCLUSION: EigenPooling extracts subgraph information using both node features and subgraph structure.It is based on the local graph Fourier transform.
  • 6 CONCLUSION: EigenPooling-based layers can be incorporated into graph neural networks to hierarchically learn graph-level representations.EigenGCN combines these pooling layers with GCN convolutional layers.
  • 6 CONCLUSION: Experiments on six commonly used graph-classification benchmarks show state-of-the-art performance on most datasets.The conclusion presents this result as evidence of the proposed framework’s effectiveness.
Loading 1904.13107v2…