DeepGraph: Graph Structure Predicts Network Growth

Cheng Li, Xiaoxiao Guo, Qiaozhu Mei

Introduction

Predicting the evolution of complex networks—ranging from social circles to citation graphs—is a central task in network science. Traditional approaches often rely on manually engineered features or raw adjacency matrices, both of which suffer from significant drawbacks. Hand-crafted features often miss subtle global structural patterns, while adjacency matrices lack permutation invariance, making them sensitive to node ordering.

DeepGraph addresses these challenges by introducing an end-to-end deep learning framework that learns topological "fingerprints" of network growth. By leveraging spectral graph theory and a specialized convolutional architecture, DeepGraph provides a representation that is universal, invariant, and highly informative.

Methodology: The DeepGraph Framework

The DeepGraph architecture consists of two primary components designed to capture structural information across multiple scales.

Heat Kernel Signature (HKS) Descriptor

To achieve permutation invariance, DeepGraph utilizes the Heat Kernel Signature (HKS). This spectral method simulates heat diffusion across the network. Short-term diffusion captures local neighborhood structures, while long-term diffusion reveals global properties like community clusters. These signatures are then transformed into a fixed-size histogram-based descriptor, ensuring the model can handle graphs of varying sizes.

Multi-column, Multi-resolution CNN

The resulting descriptor is processed by a specialized Convolutional Neural Network (CNN). The model employs two parallel columns to extract distinct features:

  1. Column 1 (Bins): Convolves over histogram bins to capture statistical density dynamics.
  2. Column 2 (Time): Convolves over diffusion time to identify static patterns at different granularities.
DeepGraph architecture overview, showing the transformation from graph structure to HKS descriptors and the multi-column CNN processing.

Experimental Evaluation

The authors evaluated DeepGraph across five diverse real-world datasets: Facebook, YouTube, ACL Anthology (AAN), IMDB, and Weibo. These datasets represent various growth phenomena, such as social link formation, h-index increases, and information cascades.

Performance and Results

DeepGraph consistently outperformed traditional baselines and competing graph-CNN architectures. As detailed in the results table, DeepGraph achieved the lowest Mean Squared Error (MSE) across all tested domains, proving its robustness across different network types and growth dynamics.

Comparison of Mean Squared Error (MSE) across different models and datasets. DeepGraph consistently achieves the best performance (lowest error).

Beyond raw performance, internal visualizations revealed that DeepGraph automatically "re-discovers" fundamental social science concepts, such as triadic closures and structural holes, without explicit human guidance. This suggests the model is learning meaningful structural properties rather than just fitting noise.

Conclusion and Future Work

DeepGraph demonstrates that the "shape" of a network is a powerful predictor of its future growth. By combining spectral descriptors with multi-resolution convolutions, the framework offers a scalable and efficient alternative to computationally expensive graph kernels. Future research will explore incorporating node attributes (e.g., text or demographics) and extending the framework to directed graphs to further enhance predictive accuracy.

Summary updated

Abstract

The topological (or graph) structures of real-world networks are known to be predictive of multiple dynamic properties of the networks. Conventionally, a graph structure is represented using an adjacency matrix or a set of hand-crafted structural features. These representations either fail to highlight local and global properties of the graph or suffer from a severe loss of structural information. There lacks an effective graph representation, which hinges the realization of the predictive power of network structures. In this study, we propose to learn the represention of a graph, or the topological structure of a network, through a deep learning model. This end-to-end prediction model, named DeepGraph, takes the input of the raw adjacency matrix of a real-world network and outputs a prediction of the growth of the network. The adjacency matrix is first represented using a graph descriptor based on the heat kernel signature, which is then passed through a multi-column, multi-resolution convolutional neural network. Extensive experiments on five large collections of real-world networks demonstrate that the proposed prediction model significantly improves the effectiveness of existing methods, including linear or nonlinear regressors that use hand-crafted features, graph kernels, and competing deep learning methods.
BibTeX
@misc{li2016deepgraph,
  author = {Cheng Li and Xiaoxiao Guo and Qiaozhu Mei},
  title = {{DeepGraph: Graph Structure Predicts Network Growth}},
  year = {2016},
  eprint = {1610.06251},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.06251},
}
Figure