PaperlayerView exact revision on arXiv

Source-linked AI summary

Complex Network Classification with Convolutional Neural Network

Ruyue Xin, Jiang Zhang, Yitong Shao

arXiv:1802.00539v2cs.CV

TL;DR

Research has paid limited attention to classifying complex networks as whole objects, including product networks where manual labeling is subjective. CNC embeds networks into images for CNN classification; experiments report strong classification performance, including a 0.1% average test error for BA and WS networks.

  • Problem

    Most complex-network studies examine individual network properties rather than classification, clustering, or comparison across networks, while product labeling by attributes can be subjective.

    Source: §1 · p. 1

  • Method

    CNC uses DeepWalk embeddings, reduces and rasterizes them into images, then applies a CNN for network classification.

    Source: §1 · p. 2, §3.1 · p. 3

  • Results

    CNC performs well on synthetic and empirical classification tasks; BA and WS classification yields a 0.1% average test error on the test set.

    Source: §4.1.1 · p. 4, §5 · p. 6

  • Takeaways & Limitations

    Visualized CNN filters capture differences between BA and WS networks.

    Source: §5 · p. 6

    Potential future work includes methods for high-dimensional network features and extending CNC to more graph-structured data.

    Source: §5 · p. 6

Abstract

from arXiv · show

Classifying large scale networks into several categories and distinguishing them according to their fine structures is of great importance with several applications in real life. However, most studies of complex networks focus on properties of a single network but seldom on classification, clustering, and comparison between different networks, in which the network is treated as a whole. Due to the non-Euclidean properties of the data, conventional methods can hardly be applied on networks directly. In this paper, we propose a novel framework of complex network classifier (CNC) by integrating network embedding and convolutional neural network to tackle the problem of network classification. By training the classifiers on synthetic complex network data and real international trade network data, we show CNC can not only classify networks in a high accuracy and robustness, it can also extract the features of the networks automatically.

1 INTRODUCTION

The paper addresses a gap in research that has focused on individual networks rather than classification and comparison across networks. It proposes CNC, which combines network embedding and a CNN to classify networks and extract their features.

1 INTRODUCTION

  • Research has seldom addressed comparing, clustering, and classifying complex networks as whole objects, despite the importance of these tasks.Most studies instead focus on properties of a single network.Source: §1 · p. 1
  • For international trade, network-based product classification could avoid subjective manual labeling and help countries better count trade volumes.The passage says products have different international trade network structures and a classifier could classify new products by structure.Source: §1 · p. 1
  • Existing network representation methods such as DeepWalk and node2Vec support node-level tasks, but not classification of whole networks.Graph kernels also face high computational complexity on large-scale, complex networks.Source: §1 · pp. 1–2
  • CNC embeds a network with DeepWalk, converts it into a 2D image, and uses a CNN to classify it and extract features automatically.The authors also describe the framework as small, computationally light, and scalable across network sizes.Source: §1 · p. 2
  • Unlike Antoine et al., CNC uses a simpler classic embedding approach without multi-channels and is designed to handle directed and weighted networks.The paper focuses on classifying complex network models to learn their features.Source: §1 · p. 2

2 RELATED WORK

The related work describes complex-network models and classification methods, then reviews deep learning and network representation learning. It identifies graph-structure dependence in spectral approaches and motivates combining embeddings with deep learning for whole-network classification.

2.1 Complex network

  • Classic complex-network models include regular, random, small-world, and scale-free networks, while research has focused more on reconstruction and synchronization than classification.The passage attributes small-world and scale-free models to Watts [5] and Barabási [1], respectively.Source: §2.1 · p. 2

2.2 Network classification

  • Graph classification kernels compare networks using measures such as random walks [11], shortest paths [2], graphlets [21], and Weisfeiler-Lehman features [20], but their computational cost limits large-scale use.Source: §2.2 · p. 2

2.3 Deep learning on graph-structure data

  • Deep-learning methods for graphs include spectral convolution approaches, but their Laplacian-eigenbasis filters depend on graph structure and cannot directly transfer across different structures.The paper says this dependence makes direct GCN use unsuitable when classification samples each have a specific network structure.Source: §2.3 · p. 2

2.4 Network representation learning

  • Network representation learning maps nodes into a high-dimensional vector space based on graph structure; these vectors support classification and clustering, and shallow models include DeepWalk, LINE, and Node2Vec [7].The authors choose DeepWalk as a classic, simple model efficient on large-scale networks; its random-walk mechanism can be changed for directed, weighted networks.Source: §2.4 · pp. 2–3

3 METHODS OF NETWORK CLASSIFICATION

CNC embeds each network, reduces and rasterizes the representation into an image, and classifies that image with a CNN. The experiments use synthetic BA and WS networks and directed, weighted international trade networks.

3.1 the model

  • DeepWalk node sequences are converted into Euclidean representations, reduced by PCA to 2D, rasterized as a 48 × 48 grayscale image, and fed to a CNN classifier.The described architecture uses convolutional and pooling layers, a fully connected layer, and an output layer; Figure 1 depicts the pipeline.Source: §3.1 · p. 3, §3.2 · p. 3, Figure 1 · p. 3

3.2 Experiment data

  • The study uses both synthetic networks and empirical networks to train and test CNC.Source: §3.2 · p. 3

3.2.1 Synthetic data.

  • Synthetic data comprise BA networks generated with m = 4 until n = 1000 and WS networks with n = 1000, k = 8, and rewiring probability p = 0.1.The generated networks have an average degree of about 8; the sets are divided into 8000 training, 2000 validation, and 1200 test networks.Source: §3.2.1 · p. 3

3.2.2 Empirical data.

  • Empirical data are product-specific international trade networks covering more than 800 products from 1962 to 2000, encoded by SITC4 digits.The networks are directed and weighted, and CNC is trained to distinguish food products from chemicals products.Source: §3.2.2 · pp. 3–4

4 EXPERIMENTS AND RESULTS

The experiments test CNC on synthetic BA and WS networks, WS networks with different rewiring probabilities, and international trade networks, then examine robustness to network size. The results include low classification error and learned filters that respond to different local network structures.

4.1.1 BA and WS classification experiments.

  • 0.1% average test error rate for distinguishing BA from WS networks.The experiment used networks with n = 1000 and randomly split 11,200 networks into training, validation, and test sets.Source: §4.1.1 · p. 4, Figure 6 · p. 5
  • First-layer filters respond to local clusters with medium-density, sparse, or dense nodes and connections.Sparse clusters appear near the representation’s periphery for WS networks but in the center for BA networks; the authors say these activation patterns help distinguish the models.Source: §4.1.1 · p. 4, Figure 3 · p. 4

4.1.2 Small world networks classification.

  • WS networks with p values below 0.3 and at or above 0.4 were easier to distinguish; pairs with both p values above 0.4 were not distinguishable.The authors suggest the change may relate to a link-percolation phase transition; WS networks with p > 0.5 may be treated as random networks.Source: §4.1.2 · p. 5, Figure 4 · p. 5

4.2 Classification on trade flow networks

  • 5% classification error rate on food-versus-chemicals international trade networks.The dataset contains 10,705 food networks and 10,016 chemicals networks; the networks encode directed, weighted trade flows.Source: §4.2 · p. 5, Figure 6 · p. 5

4.3 Robustness on sizes of the network

  • Error rates were nearly independent of small node-count fluctuations but increased with larger test-versus-training size differences.The test networks varied in node and edge counts relative to the training networks.Source: Figure 7 · p. 5, §4.3 · p. 6
  • Edge-count changes produced sudden error-rate shifts, while training with BA parameter m = 8 yielded low error rates as test edge counts increased.The authors link the sudden shift to a multi-center embedding representation and conclude that classifiers trained on dense networks are more robust to edge-density variation.Source: Figure 7 · p. 5, §4.3 · p. 6

5 CONLUSION AND DISCUSSION

The proposed network classifier combines DeepWalk and CNN, and the authors report good classification performance on synthetic and empirical data. They also describe future extensions to high-dimensional network features and additional graph-structure data.

5 CONLUSION AND DISCUSSION

  • The DeepWalk-and-CNN model performs well on synthetic and empirical network classification tasks.The authors also report robustness across network sizes and the ability to handle networks with different structures and sizes.Source: §5 · p. 6
  • CNN filters capture differences between Watts–Strogatz and Barabási–Albert networks.Source: §5 · p. 6
  • The model has a small architecture and low computational complexity.Source: §5 · p. 6
  • Future work includes developing methods for high-dimensional network features and extending the model to more graph-structure data.The authors expect broader graph data to support a larger variety of problems.Source: §5 · p. 6

Related papers

Loading 1802.00539v2…