Graph Classification via Deep Learning with Virtual Nodes

Trang Pham, Truyen Tran, Khanh Hoa Dam, Svetha VenkatesharXiv 2017 · OpenReview

TL;DR

This paper introduces the Virtual Column Network (VCN), a novel deep learning approach for graph classification. VCN augments graphs with a "virtual node" that captures latent graph-level information, enabling more effective representation learning. This method achieves competitive results on tasks like predicting chemical compound bio-activity and identifying software vulnerabilities.

What Problem Does This Paper Address?

Deep learning has excelled in domains with grid-like or sequential data (e.g., images, text). However, many real-world problems are naturally represented as graphs with irregular structures (e.g., chemical compounds, social networks, protein interactions). Classifying these graphs requires transforming them into fixed-size representations that can be processed by standard machine learning models. Traditional methods like graph kernels or manual feature engineering can be computationally expensive or labor-intensive. Existing graph neural networks often focus on node-level representations, and aggregating these into a graph-level representation can be a bottleneck. This paper aims to develop an end-to-end deep learning method for graph classification that directly learns a graph representation by incorporating latent, global graph properties.

Methods

The core innovation of VCN is the introduction of a virtual node. This virtual node is added to the original graph and is bidirectionally connected to all existing "real" nodes. The virtual node is designed to capture latent aspects of the graph that are not explicitly present in node attributes or local connectivity.

The augmented graph (original graph + virtual node) is then fed into a Column Network (CLN), a recurrent neural architecture previously developed by the authors for node classification. CLN processes information iteratively, allowing nodes to communicate with their neighbors. In VCN, the virtual node's column acts as a central hub, integrating information from all real node columns and distributing a consensus graph-level representation back to the real nodes.

The key idea is that the final state of the virtual node's column serves as the representation for the entire graph. This allows for end-to-end learning of graph representations, directly optimizing for the classification task. The authors use a differentiable classifier (like a feedforward network) on top of the VCN to achieve this end-to-end training.

Datasets

The paper evaluates VCN on two main types of tasks:

  • BioAssay Activity Prediction: Three large NCI BioAssay datasets were used: Lung Cancer, Leukemia, and Yeast Anticancer. These datasets represent chemical compounds as graphs, where nodes are atoms and edges are bonds. The task is to predict whether a compound is "active" or "inactive" against a specific test. The datasets were balanced by undersampling "inactive" compounds.
  • Code Classification: A dataset of 18 Java projects was used, where each source file (Java class) is represented as a graph. Graph-level features represent attribute declarations, nodes represent methods, and edges represent method calls. The task is to predict if a source file is vulnerable. The dataset consists of 2836 samples after preprocessing.

Key Insights and Ideas

  • The Power of a Virtual Node: Augmenting a graph with a single virtual node that connects to all other nodes is a surprisingly simple yet effective way to capture global, latent graph properties. This node acts as a global aggregator and distributor of information.
  • End-to-End Learning for Graphs: By making the virtual node's representation the graph's representation and using a differentiable classifier, VCN enables true end-to-end learning for graph classification, eliminating the need for separate feature extraction or pooling steps.
  • Bridging Node and Graph Representations: VCN elegantly bridges the gap between node-level processing (handled by the underlying Column Network) and graph-level classification by using the virtual node's state as the final graph embedding.
  • Versatility of Column Networks: The paper demonstrates that Column Networks, initially designed for node classification, can be adapted for graph classification by incorporating the virtual node concept.

Key Results

  • BioAssay Activity Prediction: VCN achieved competitive results on the NCI datasets, outperforming traditional methods like SVM, Random Forest, and Gradient Boosting Machine with circular fingerprints, as well as the Neural Fingerprint baseline. For example, on average, VCN achieved an AUC of 83.6%, slightly outperforming NeuralFP (83.2%). The F1-scores also showed VCN outperforming baselines on average.
  • Code Classification: VCN significantly outperformed all baseline methods (SVM, RF, GBM) in both AUC and F1-score on the code classification task.

Limitations and Future Work

  • Single Virtual Node: The current VCN uses only one virtual node. The authors suggest that using multiple virtual nodes could lead to richer graph embeddings, potentially allowing for multitask learning or targeting specific subgraphs.
  • Alternative Architectures: While VCN uses Column Networks, the authors note that other node representation architectures (like Gated Graph Sequence Neural Networks, Graph Neural Networks, and diffusion-CNNs) could also be used with the virtual node concept.
  • Iterative Estimation: The VCN can be viewed as an instance of learning as iterative estimation, and further exploration of this perspective could be beneficial.

Summary updated

Abstract

Learning representation for graph classification turns a variable-size graph into a fixed-size vector (or matrix). Such a representation works nicely with algebraic manipulations. Here we introduce a simple method to augment an attributed graph with a virtual node that is bidirectionally connected to all existing nodes. The virtual node represents the latent aspects of the graph, which are not immediately available from the attributes and local connectivity structures. The expanded graph is then put through any node representation method. The representation of the virtual node is then the representation of the entire graph. In this paper, we use the recently introduced Column Network for the expanded graph, resulting in a new end-to-end graph classification model dubbed Virtual Column Network (VCN). The model is validated on two tasks: (i) predicting bio-activity of chemical compounds, and (ii) finding software vulnerability from source code. Results demonstrate that VCN is competitive against well-established rivals.
BibTeX
@misc{pham2017graph,
  author = {Trang Pham and Truyen Tran and Khanh Hoa Dam and Svetha Venkatesh},
  title = {{Graph Classification via Deep Learning with Virtual Nodes}},
  year = {2017},
  eprint = {1708.04357},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.04357},
}
Figure