Graphlet Count Estimation via Convolutional Neural Networks

Xutong Liu, Yu-Zhen Janice Chen, John C. S. Lui, Konstantin Avrachenkov

Introduction

In network science, understanding the structural properties of complex systems—ranging from biological protein-protein interactions to massive social networks—often hinges on identifying small, recurring patterns known as "graphlets." These small, connected induced subgraphs (such as triangles, paths, or cliques) serve as structural fingerprints for a network. However, determining the frequency of these patterns, or the graphlet count, presents a significant computational challenge.

As the size of the network or the complexity of the graphlet increases, the number of potential combinations to evaluate grows exponentially. Traditional approaches generally fall into two categories: exact enumeration, which is prohibitively slow for large datasets, or statistical sampling, which is faster but requires repetitive, resource-intensive counting for every new graph encountered. This paper proposes a shift from "counting from scratch" to "estimating through learning," utilizing a Convolutional Neural Network (CNN) framework to predict graphlet counts for unseen graphs based on historical data.

Methodology

The core innovation of this research is treating a graph's adjacency matrix as a 2D image, allowing the application of standard computer vision techniques to structural graph data.

CNN Architecture

The proposed model utilizes a streamlined architecture consisting of two convolutional layers with ReLU activation. These layers are designed to capture local structural patterns within the adjacency matrix that correspond to specific graphlets. The output is then flattened and passed through a fully connected layer to produce a final estimated count.

Data Preprocessing and Augmentation

To bridge the gap between graph theory and deep learning, the authors introduced two critical preprocessing techniques:

  1. Adjacency Matrix Zero Padding: To handle varying graph sizes within a dataset, smaller adjacency matrices are padded with zeros to match the dimensions of the largest graph ($N \times N$), ensuring a consistent input size for the CNN.
  2. Swapping Augmentation: Because a graph's structure is independent of its node ordering (isomorphism), the authors generated additional training samples by randomly swapping rows and columns of the adjacency matrices. This technique is functionally similar to image rotation or flipping in computer vision, forcing the network to learn invariant structural features rather than specific node positions.

Experimental Results

The framework was rigorously tested on synthetic datasets (Random Geometric and Erdos-Renyi models) and real-world biochemistry datasets (MUTAG, NCI1, and NCI109). The results demonstrate that the CNN approach offers a compelling balance of accuracy and computational efficiency.

Performance comparison of CNN against traditional sampling methods (GRAFT, CC2, GUISE) in terms of operations and relative error for 4-clique and tailed-triangle counts.

Accuracy and Efficiency

As shown in the performance analysis, the CNN achieved high precision, with relative errors often falling below 5-6% for complex patterns like 4-cliques and 4-paths. More importantly, the CNN approach is significantly more efficient than traditional sampling methods such as GRAFT, CC2, or GUISE. By measuring the number of arithmetic operations required, the authors demonstrated that once a CNN is trained, it can produce estimates almost instantaneously with a fraction of the computational cost required by iterative sampling algorithms.

Discussion and Future Work

While the CNN framework represents a significant step forward in efficient graph mining, several challenges remain. The current reliance on zero-padding requires a predefined maximum graph size, which may limit flexibility when encountering unexpectedly large networks. Additionally, the model is currently trained to estimate one specific graphlet type at a time. Future research could explore multi-task learning architectures to estimate multiple $k$-node graphlets simultaneously.

Finally, scaling this approach to massive social networks with millions of nodes remains a hurdle, as the adjacency matrix for such graphs would be too large for standard CNN processing. Nevertheless, for medium-scale graphs in domains like chemistry and biology, this learning-based estimation provides a powerful alternative to traditional counting methods.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{liu2018graphlet,
  author = {Xutong Liu and Yu-Zhen Janice Chen and John C. S. Lui and Konstantin Avrachenkov},
  title = {{Graphlet Count Estimation via Convolutional Neural Networks}},
  booktitle = {SPIRE},
  year = {2018},
}
Figure