Convolutional Neural Network Dynamics: A Graph Perspective
Authors: Fatemeh Vahedian
Ruiyu Li
Puja Trivedi
Di Jin
Danai Koutra
Venue: ICLR 2022 Submitted (2022)
Keywords: neural network dynamics
time-evolving graphs
interpretation of neural networks
performance prediction

Abstract: The success of neural networks (NNs) in a wide range of applications has led to increased interest in understanding the underlying learning dynamics of these models. In this paper, we go beyond mere descriptions of the learning dynamics by taking a graph perspective and investigating the relationship between the graph structure of NNs and their performance. 
Specifically, we propose (1) representing the neural network learning process as a time-evolving graph (i.e., a series of static graph snapshots over epochs), (2) capturing the structural changes of the NN during the training phase in a simple temporal summary, and (3) leveraging the structural summary to predict the accuracy of the underlying NN in a classification or regression task. For the dynamic graph representation of NNs, we explore structural representations for fully-connected and convolutional layers, which are key components of powerful NN models. Our analysis shows that a simple summary of graph statistics, such as weighted degree and eigenvector centrality, over just a few epochs, can be used to accurately predict the performance of NNs. For example, a weighted degree-based summary of the time-evolving graph that is constructed based on 5 training epochs of the LeNet architecture achieves classification accuracy of over 93\%. Our findings are consistent for different NN architectures, including LeNet, VGG, AlexNet, and ResNet.

Under review as a conference paper at ICLR 2022
CONVOLUTIONAL NEURAL NETWORK DYNAMICS: A GRAPH PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
The success of neural networks (NNs) in a wide range of applications has led to increased interest in understanding the underlying learning dynamics of these models. In this paper, we go beyond mere descriptions of the learning dynamics by taking graph perspective and investigating the relationship between the graph structure NNs and their performance. Specifically, we propose (1) representing the neural network learning process static graph snapshots over epochs), (2) capturing the structural changes the NN during the training phase in simple temporal summary, and (3) leveraging the structural summary to predict the accuracy of the underlying NN in a classification regression task. For the dynamic graph representation of NNs, we explore structural representations for fully-connected and convolutional layers, which are key components of powerful NN models. Our analysis shows that simple summary of graph statistics, such as weighted degree and eigenvector centrality, over just few epochs can be used to accurately predict the performance of NNs. For example, a weighted degree-basee based summary of the time-evolving graph that is constructed based on 5 training epochs of the LeNet architecture achieves classification accuracy of over 93%. Our findings are consistent for different NN architectures, including LeNet, VGG, AlexNet, and ResNet.
time-evolving graph (i.e., series of
INTRODUCTION
Neural networks (NNs) have driven advancements in many domains, including computer vision and image processing (Hu et al.) 20188), natural language processing (Sutskever et al. [014]] Bahdanau al. 2015). and bioinformatics (Cao et al., 2020 et al.) 2019). As task complexity increases, networks grow deeper and larger, consequently requiring more computational resources and training data, as well as sacrificing interpretability for improved task performance. Some works have focused on understanding and interpreting deep NNs (Raghu et al. 20117: Chakraborty & et al. 2017 loffe & Szegedy 2015: He et al.) 2016). One approach towards this goal involves representing the NN as its underlying graph structure, and studying selected graph properties, such as clustering coefficient, path length You et al. 2020). modularity (Filan et al.) 202I). persistence (Rieck et al.. 2019). For example, You et al. (2020) represent NNs as relational graphs capturing the message passing process, and investigate the correlation between the predictive performance of NNs and architectural changes. However, the studies of NN structures as graphs are limited, and the structural changes of the underlying graph during the training process have been largely overlooked in the literature.
To fill this gap. in this work, we take the graph perspective and aim to predict the performance of an NN by capturing early NN dynamics during the training phase. Successful performance prediction based on only a few epochs could be used for early stopping (Yu & Zhu (020), and thus, more efficient NN training. To solve the performance prediction problem, we propose multi-step framework, depicted in Fig. [ Specifically, we propose to represent the underlying graph structure of an NN as a time-evol viol k-partite graph, where each part corresponds to different NN layer, and each graph snapshot in the evolving graph maps to an NN instance at specific epoch. We build on existing graph representations of fully-connected and convolutional layers, both of which are key components of popular NN architectures, and introduce a new, compact, efficient-to- sileiient-to-oompue ("rolled"") graph representation for convolutional layers. Then, we extract well-known node features (weighted degree and eigenvector centrality) from the time-evolving graph and construct temporal signatures by computing summary statistics on the node feature distributions. Finally, we cast NN

---

Under review as a conference paper at ICLR 2022
Training
Output:
Epoch
Epoch 2
Epoch
E. 100
Cat
Dog
① Graph Generation
Convolution
Telpowe
:eroph
FC
@ Feature extraction
Cuipar
High Low
0.8
Loss
NN architecture
Trained
Trained
@ Signature construction
Classifior...
Regressor.
prediction
Our proposed framework for predicting NN performance downstream image classification task, shown for one test instance. The input our framework is an NN trained few epochs (3, this example). Steps: (S1) the input NN is converted to three static graphs, each representing one training epoch; (S2) node features (e.g.. degree) are extracted from each graph snapshot (i.e., one epoch); (S3) in order to summarize the time, a signature vector constructed by aggregating the node features per
Figure I:
changes in the graph structure graph snapshot and concatenating the individual snapshot signatures; (S4) pre-trained classifier and regressor predict the performance of the input NN given the signature vector from (S3).
performance prediction as a classification task and regression task, each of which operates on the temporal structural signatures of the NN. Our main contributions are:
New graph-based NN representation: We introduce a new graph representation for convolutional layers that is more compact and efficient-to-compute than the existing unrolled representation (Rieck) lt al. 2019), while not sacrificing accuracy in the NN performance prediction task.
Framework for NN performance prediction: We propose a simple, multi-step graph- framework to solve the NN performance prediction problem by capturing the early NN dynamics during the training phase.
Extensive empirical analysis: Using well-known image classification datasets (ImageNet and CIFAR- 10), and variety of NN architectures (AlexNet, VGG, LeNet, and ResNet), we show that our framework can effectively predict the performance of NNs by observing only a few epochs of training, well before their corresponding early stopping epochs. For instance, using our framework to capture the changes in the graph structure in only 5 training epochs of the ResNet architecture results classification accuracy of over 90%.
2 PRELIMINARIES
We first present the key concepts that our work builds upon. Table gives the major symbols and their descriptions.
An NN model is a collection of connected units (neurons) that are organized in layers, and is defined by set of parameters that adjust during the training process. We refer to the training process of single architecture along with its respective hyperparameters as 'instance'. We focus on two types of layers that are the key components of many powerful NN models such as LeNettLecun et al., 1998), VGG (Simonyan & Zisserman 2015) and ResNet(He et al. 2016): fully connected layers (fc) and convolutional (conv) layers.
2.1 GRAPHS: TERMINOLOGY AND NOTATION
Let G (V,E) be an undirected, weighted graph with node set V. edge set E, and weighted adjacency matrix W RMMX) The neighbors of node are defined as No(w) {u (u, v) E E); i.e. the set of all nodes that connect directly to v. Graph G is k-partite if its nodeset 1/ can be partitioned into & independent sets: V U V, and V, n,V 0, á + j. A time-evolving graph is series of static graph snapshots over time: = ( G ...., GT) The graphs in the series may have different nodesets and edgesets.
Here we focus two of the most commonly used node features in graph mining and network science, degree and eigenvector centrality, which capture different types of node importance or influence. We discuss the interpretation of these features the context of neural network dynamics in 3.2
2

---

Under review as a conference paper at ICLR 2022
Degree is the simplest and most efficient to compute node feature, and captures the connectivity of a node. The weighted degree of node is defined as the sum of weights of the edges that are incident to i: d = E, W iz-- Tracking changes in the degree of a node over time is the most direct way of capturing its structural evolution.
Degree:
Eigenvector centrality: This centrality is sophisticated extension of degree centrality, related to Google's PageRank, which indicates the influence of a node in G (Bonacich) 1972). If node is connected to several nodes with high eigenvector centrality, then that node will have high centrality. The eigenvector centrality of node is defined as the 7t element in the principal eigenvector v of W (i.e., the eigenvector that corresponds to the largest eigenvalue A): Wv Amaz V.
2.2 FULLY-CONNECTED LAYERS: GRAPH REPRESENTATION
Let E P:. be the imput vector, W E P: the learnable weight matrix, b E Dout the bias vector and z non-linear activation functions. Then, the output of this layer is given as xx b)) where Dan and Dout correspond to the dimension of input and output layers. Fully-connected layers are straightforward to represent with a weighted, undirected graph (Filan et al. (2021). Each neuron, including those the input and output layers, cor- responds to node. Two neurons are connected via an edge if they appear in consecutive layers. More formally, let nodeset V. be the set of all neurons layer i, and nodeset Vj the set of all neurons at layer j (which follows layer i). The edges that connect all nodes across the two nodesets are defined by the learnable weight matrix W E IR [V
Table I: Major symbols and definitions
Symbol
Definition
G (V,E)
a graph with its nodeset and edgesel G²} a time-evolving graph, ie., scries of graph snapshots
g = G .....
d. d
and weighted degrce of node leamuble weight mutrix un NN, and the weighted adj matrix of G convolutional kernel
W
K
Dinjout
dimension the input/output vectors number of channels and filters height and width of an inpur image height and width of a kemel input lensor of conv layer
c.
h. w
hjers Miker
2.3 CONVOLUTIONAL LAYERS: UNROLLED GRAPH REPRESENTATION
Let X E Bexhxw be the input and K. E IB/xexhenrxxen the convolutional ker- nel, where e is the number of channels, and hker, Wher are the height and width of the ker- nel respectively. After performing the convo- lution, we have y E RF Xhout Woue, where hout = h hiker + 1 and Wont -Wker + 1. Typical multilayer CNNs consist of convolu- tional layers followed by fully-connected lay- ers. The representation fully connected layers is straightforward but cannot be used to model convolutional layers. Rieck et al. (2019) proposed to "unroll" the convolution to convert conv layers into graphs. In Sec. 3 we introduce new, compact, rolled representation that is both efficient to compute and effective at predicting the NN performance, as we show empirically in Sec.
14
19 Filters
V5
01
04
05
06
Inpur Imagee
Owipwl
(a) Example convolutional
(b) Unrolled graph representation of red box Figure 2: Unrolled graph representation example. The two typed nodes the resultant bipartite graph map to the filtration operation and the output. For the stride in this example, the output node on (in dark blue) is the output of 4 operation-typed nodes (in light blue).
operation
For convolutional layer, we first unroll the convolutional operation and then represent the graph as in the case of a fully-connected layer. In this representation, the nodes and edges of the graph are defined through the convolutional operation as matrix multiplication (Gebhart al., 2019). Specifically, for an input image X' and kernel K, E RAx x,, xh, xw; each node in layer is defined to be the output of the mapped feature of that input for each filter f.. Edges connect each of these nodes to the corresponding nodes of the output neuron in the next layer. These edges are weighted by the activation value of that neuron (i.e., the input image for a specific stride is multiplied by the filter value at that location in the image). For an input image filter size (c: x h; x w.) that results in reapure-map (output) of size 1 x on X Ow, the number of nodes of output layer of the graph representation is a function of o₁ Ow, while the number of nodes in the conv operation layer of graph is function of e x h4 x wi-
As an example, Fig. 2 depicts the unrolled graph representation of toy convolutional layer. It shows one conv operation on a small 2-dimensional input image (4 x 4) and filter (2 x 2). The nodes and edges of the represented graph are shown based on one stride (of size 2) of convolution operation.
3

---

Under review as a conference paper at ICLR 2022
3 NEURAL NETWORK PERFORMANCE PREDICTION: A TEMPORAL GRAPH-BASED APPROACH
In this section, we first formally introduce the problem that we seek to solve. Then, we present new, compact, and efficient-to- co-copp graph representation for convolutional layers ($ ($(.. and describe our proposed temporal graph-based framework that captures the NN dynamics during training ($ 3.2).
Problem 1 (NN Performance Prediction) Let N (Nar Nerg....,, Ntr.. } be training set of n. NNs trained for T epochs and {on, ;'2 their corresponding downstream task accuracies (c (e.g.. for image classification). We seek predict the accuracy aust of new instance Nest trained for very small number of t < T epochs by using epochs for the trained NNs in N.
Our proposed solution takes the graph perspective, and its first step is to represent each NN as temporal graph. In addition to the graph representations that we presented in Sec. 2 we introduce a new, efficient representation for convolutional layers, which we describe next.
3.1 ROLLED GRAPH REPRESENTATION FOR CONVOLUTIONAL LAYERS
Conv1
Conv2
FC: Graph Reprosentation
We call our proposed graph representation for conv layers "rolled," since it avoids unrolling the convolu- tional operations introduced in (Rieck et al. 2019).
Conv1
Conv2
Normichannal 2)
Overview & Motivation. To preserve the seman- tic meaning of conv layers, we represent each filter as a node, and link filters in consecutive layers via weighted edges (we define the weights below), as shown in Fig. 3 The motivation behind this approach is that for larger networks, there is an explosion of nodes by unrolling the convolutions (unrolled rep- resentation explained in $ $2.3), and the integrity of unit (a single filter kernel) becomes untenable. Also, by mapping the nodes to specific entities of NNs, our proposed graph model more interpretable than the unrolled model, and thus it is easier to inter- pret the outputs of downstream graph analysis on our graph representation (e.g., computing node features, tracking the evolution of the graph).
16
18
Normichannel
Figure 3: Rolled graph representation example. The resultant graph a tri-partite graph with three node types (Conv 1, Conv2, FC) corresponding to two convolutional layers and one FC layer. Gray and light blue nodes represent filters in the cony layers and dark blue nodes represent neurons in the FC layer. The red edge between nodes 6 (gray) and 16 (light blue) is weighted by the Norm(6" channel of filter 16). Due to dropout, the maximum number of edges is 6 x 16 between the conv layers, and 16 120 hetween the Conv2 and FC layers.
Detailed Description. Formally, let tensor IC; be a kernel in layer i with f; filters, each with c; channels and dimensions h; x wi. We use bracket notation to index into the kernel: for example, KC [t;
:;::] indexes the 1hh filter of kernel K, We create fa nodes representing each filter (v 212 1...%% with features defined as the corresponding biases in that layer. Let K, be the next convolutional layer defined analogously. While edge weights between neurons FC layers are defined the standard way, we define the edge weights between conv layers the norm over each kernel's 's channels. The edge between node 2s representing the h filter in layer (i.e., KC [k: :.::.) and node/filter of()) in layer (i.e. :,, has weight w.6
(5) (0)
.t. norm(XC,1,, :.) which is the norm of the
tthh channel of the ('filter in the 7th layer. Though the proposed representations enable alternative edge weight configurations, we focus on the norm of filters as other studies, including those on pruning NNs (Li et al. 2016), have demonstrated that this metric has strong correlation with filter importance. In the case of two conv layers, the resultant graph is an attributed bipartite graph with f + fg nodes and fa f edges, where node attributes include flattened weight vectors filter maps. Other information such as average gradients or the bias vector can also be used for node features.
3.2 PROPOSED TEMPORAL GRAPHI-BSSED FRAMEWORK
A key objective of our work is test whether the introduced graph representation of NNs is informative for predicting the performance NNs. Next, we describe the steps of our proposed framework for solving Problem I namely performance prediction from the NN training dynamics.
4

---

Under review as a conference paper at ICLR 2022
As shown in Fig. our method consists of four steps: (S1) generation of temporal graph for the training phase of each NN: (S2) extraction of node features; (S3) construction of a feature- based graph signature that captures the NN dynamics; (S4) prediction of NN performance by training classifier or regressor on the constructed signatures. We describe these steps in more detail next.
(S1) Graph generation. The first step involves converting the training process of each input NN into a time-evolving graph. Each NN Nir, E .N, is represented as a series of checkpoints saved for & training epochs. Based on these checkpoints and the graph representation approaches for fo and conv layers presented in 2.2 3.1 and 2.3 we first convert the 7th NN checkpoint into weighted
graph G timestamp/epoch We note that although our proposed graph representation involves node features, our framework does not leverage them, and thus we consider the generated graphs unattributed. Therefore, each NN Nr.; is mapped to a time-evolving graph Gtr: {G G ...,, G The output of this step is a set of n time-evolving graphs (etri:trgn Str, corresponding to the original n NNs in N.
(S2) Feature extraction. Next, the goal is to capture the structural dynamics of the NN training process. We aim to select graph measures that can capture changes during the training process, take into account the edge weight of graphs and can be calculated efficiently. In order to do that in an interpretable way, we extract two well-known node centralities from each snapshot of each generated time-evolving graph G;: weighted degree centrality and eigenvector centrality ($ 2.1). The weighted degree is a simple function of the learnable weight matrix W during the training phase of NN, therefore it gives us insights into the training dynamics at the node/neuron/filter level. The cigenvector centrality is an extension of the degree centrality, which captures the highly influential nodes, and has been successfully used in neuroscience to capture the dynamic changes of real neural networks (or connectomes) (Lohmann et al., 2010). Figenvector centrality can be used to capture importance and connectivity of filters/neurons (i.e., the nodes in our graph representation). Also, eigenvector centrality has been used for detecting communities (Newman) 2006) or clusters (Wu ct al. 2013), and thus provides structural information about the clusterability of the NN, which is complementary to that provided by the simpler and more efficient-to-coompue degree centrality.
Our choice of features is also guided by the inherent k-partite structure of our proposed graph representation, which cannot be represented well by several other commonly-used graph features. For example, clustering- basse features (e.g.. number of triangles, transitivity, clustering coefficient) and cycle-based metrics which account for closed paths in a graph are always equal to 0 for k-partite graphs. Moreover, connected component-relates features (i.e., strong/weak connectivity) do not capture the learned edge weights, which are important for modeling the training dynamics of NNs. Other features (e.g., betweenness centrality) tend to be computationally expensive, and would add significant overhead compared to early stopping methods.
(S3) Graph signature construction. In order to be able to compare NN-based graphs (with different number of nodes and edges). we summarize the structural changes in the generated time-evolving graphs at the graph level (rather than the node level, as in (S2)), and construct a statistical summary of the extracted node centralities (signature) per time-evolving graph G; For each snapshot G(+)) of G. we create signature vector using five node feature aggregators, which were introduced in (Berlingerio et al. 2012) for graph similarity: median, mean, standard deviation, skewness, and kurtosis, where all but the median are moments of the corresponding distribution. Thus, G(?)) mapped to a (static) signature vector s(²) E R2, representing the statistical summary of its node features (i.e., degree or eigenvector centrality) at time т. To put more emphasis on the most recent timestamp, we can redefine the signature at time 7 the linear weighted average of the signatures up to that point, s(*) Σラ (e2(
Σ) or exponential function of the previous signatures, s(*) as(") + (1 (0)-aass--- (-)("- To obtain the temporal signature of the evolving graph G. we aggregate the (static) signatures up to timestamp/epoch t: s = s) @ of + ... e si. where @ denotes concatenation. We note that global features such as algebraic connectivity, modularity, and average shortest paths may be seen as alternative ways for constructing global graph signatures while circumventing the local feature extraction step (S2); however, these features fail to capture the structural changes in our proposed over time) and lead to poor performance.
graph representations (they remain
(S4) Performance prediction. For the last step of performance prediction, we consider two tasks:
5

---

Under review as a conference paper at ICLR 2022
Table 2: Information for the generated NNs: range for early stopping epoch, range for accuracy, and accuracy threshold used for defining the class labels for classification task (predicting the accuracy level of NNs).
CIFAR-10
ImageNet
LeNet
AlexNet
VGG ResNet-32 ResNet-44
LeNet
AlexNet
ResNet-50
Early stopping
11~ 50
30 ~ 50
45 ~ 50
16 ~ 120
16 ~ 120
16 ~ 50
16 m 50
16 ~ 120
Acc. range
9.4> 73.8
5.5
82.4
8.8
87.6
~ 90.0
9.9 89.8
0.6 14.4
0.6 ~ 20.1 0.86 41.66
Acc. thres.
40
40
40
10
Classification: We train a classifier (e.g., SVM, MLP) using the training graphs ..., Gir,,) ( represented by their temporal signatures {s sing S and their cor- responding accuracies A = {ar, ..,,..,, On mapped to labels L [4, 2......... (a (e.g., high/low accuracy) based on some threshold. Any test NN instance is then classified using the trained classifier.
Linear regression: We perform linear regression to estimate the actual accuracy value araa of a new test instance Ne based on its signature obtained through steps (S1)-(S3).
4 EMPIRICAL ANALYSIS
In this section, we empirically evaluate the effectiveness and efficiency of our framework in the classification and regression tasks for different graph representations (rolled and unrolled graphs for conv layers) and different feature-based signatures (degree- vs. eigenvector centrality-basedl
Data. We investigate NN dynamics using our framework on two well-known image classification datasets, CIFAR-10 (Krihevskyy 2009) and ImageNet (Russakovsky et al. (015). CIFAR-10 consists of 50K training images and IOK test images. For ImageNet, we use a sample that has 50K training images and 5K validation images used as the test set. The sample is obtained by randomly selecting 100 classes from Tiny ImageNet (tin) and downsizing the images to 32x32 colored images.
Configuration. The configuration of training different NN models, and the early stopping method are described in App. A For the unrolled graph representation, which is signed, we consider different graph types (e.g.. positive, negative), which we describe in App. A.2
4.1 CLASSIFICATION PREDICTING NN ACCURACY RANGE FROM NN TRAINING DYNAMICS
Task setup. We cast the NN performance prediction as classification task. Specifically, the generated time-evolving graphs are labeled as high and low accuracy based on the performance of their corresponding NNs; Table lists the threshold value chosen for low and high accuracy labels based on the final accuracy range of trained NNs, as well the early stopping epochs for each architecture. Five-fold cross validation used to predict the label of the test graphs a binary classification task using SVM and MLP, where the input is the set of temporal signatures }. We report the classification accuracy. Since the sample of NNs A.p..A.I. is randomly selected with balanced high/low accuracy instances, the accuracy of random classifier as the baseline is 50% (omitted from the charts to avoid clutter). Additionally, to show that our proposed graph representation and signatures are general and can be useful across different NN architectures, we consider the following setup: we train the classifier on a small set of NN models (i.e., different architectures-succe LeNet, AlexNet, and VGG-and hyperparameters), and predict the performance on unseen architectures (e.g., ResNet). We describe these experiments in App. A.4
Results. Figure jillustrates the performance of SVM and MLP classifiers operating on weighted degree-based signatures of the rolled and unrolled graph representations of the LeNet and AlexNet architectures, trained on the CIFAR-10 dataset. We omit the results on VGG and ResNet, as well as image classification on ImageNet, because the unrolled graph generation process is prohibitively expensive, both in terms of time and space. Overall, the rolled and unrolled graph representations show similar trends in classifying NNs by effectively capturing their early training dynamics: the structural changes in the training NN architectures during the first 6-15 iterations are sufficient to classify the performance of NN instances with over 90% accuracy. However, our proposed rolled representation is significantly more efficient than the unrolled representation. and can generalize deeper and larger NNs. We provide more details for these experiments in App. A.2
discuss in $ 4..3

---

Under review as a conference paper at ICLR 2022
100
3:00
6.5
093
1193
640
0.5
5025
wg
000
0.0
083
6m0
040
(a) LeNet: rolled, deg
(b) AlexNet: rolled, deg
(c) LeNet: unrolled, deg
(d) AlexNet: unrolled, deg
099
690
04:
640
030
ax
1.00
g 0000
2300
0.99
069
0.00
0.0
6:50
650
0.5
220
2.00
(e) VGG: rolled, deg
(I) VGG: rolled, evec
(g) ResNet: rolled, deg
(h) ResNet: rolled, evec
Figure 4: CIFAR-I0: NN performance classification for different NN architectures, graph representations, and
features for the temporal signatures. Shorthands: 'deg' for degree-based and 'evec' for eigenvector centrality- based temporal signature. (a)-(d): Accuracy based weighted degree-based signature vectors for both the rolled and unrolled graph representations. Our rolled graph representation as effective the unrolled representation in predicting the image classification performance of NNs, while being significantly more efficient. For the unrolled representation ((c) and (d)), the negative subgraph (solid lines) results in the most accurate performance prediction among the three subgraphs. (c)-(h): Accuracy based on the weighted degree- and eigenvector centrality-based signature vectors of the rolled graph representations of VGG and ResNet-44. For both architectures, SVM performs best when leveraging the degree-based signatures (90% accuracy after training epochs), while MLP outperforms SVM when operating on the eigenvector centrality- based signatures.
OBSERVATION Both the rolled and unrolled time-evolving graph representations of NNs are effective in capturing the changes in the NN dynamics during the training phase, and can be used to predict the accuracy of an NN instance after observing only a few training epochs. Our proposed rolled representation is also space- and time-efficient, unlike the unrolled representation.
In the remainder of this analysis, we focus on the rolled representation, which is more efficient for larger NN models and datasets. We present the classification results for both types of signatures for the temporal graphs corresponding to the training dynamics of VGG and ResNet-44 (CIFAR-10 dataset) in Fig. 4 h and LeNet, AlexNet and ResNet-50 (ImageNet datatset) in Fig. In addition to the results discussed above for LeNet and AlexNet, we provide the NN classification accuracy for the eigenvector based signatures in Fig. 11 in the appendíx. In all the cases, classification accuracy of 80-95% is achieved in less than 10 training epochs. For degree- based signatures, SVM tends to outperform MLP, while the trend is reversed for eigenvector-base
signatures. For example, for both VGG and AlexNet for the CIFAR-10 image classification task, MLP can predict the performance with accuracy ~95% using the eigenvector same trend is observed on ImageNet for the LeNet and AlexNet architectures. For ResNet on the ImageNet classification task, SVM tends to perform well for both degree and eigenvector centrality signature vectors; while MI. tends to perform poorly in this case, the MI. variant operating on the exponential average of signature vectors outperforms the original MI.P and all SVM variants. In all the cases, both classifiers reach performance over 80%-90% significantly before the early stopping point for all the architectures. In general, for ImageNet, we observe that the signatures based on eigenvector centrality are more effective in the NN performance prediction task compared to the weighted degree- based signatures irrespective of NN architecture.
signatures from the first 6 training epochs; the
For the CIFAR- 10 image classification task, the rolled graph representation for all NN architectures and both signature types achieve uccuracy of > 90%. For ImageNet, the eigenvector centrality- signatures tend to yield higher performance compared to the weighted degree-bused signatures, though both achieve accuracy of 80-90%.
OBSERVATION 2
4.2 REGRESSION ANALYSIS: PREDICTING NN ACCURACY FROM NN TRAINING DYNAMICS
In this section, discuss the results and key findings of predicting the actual performance (accuracy) of an NN using a linear regression model, instead of treating this task as a classification problem as in the previous section.
7

---

Under review as a conference paper at ICLR 2022
Table 4: Regression Analysis CIFAR-10: Accuracy prediction based on the rolled graph representation and the begree-based signature.
LeNet
AlexNet
VGG
ResNet
Time
MAE
H²²
R²a
MAE
MAE
R²a
0-2
14.95
0.16
18.712
0.62
17.72
0.62
19.84
1-3
14.67
0.3
18.57
0.66
11.98
0.81
19.41
0.62
3-5
17.09
0.67
18.4
0.59
11.91
0.81
17.63
0.67
5-7
0.75
16.74
0.66
18.28
Task setup. Following the same experimental methodology in the classification task, use the degree-basee based signatures of the gener- ated time-evolving graph as the predictor and the overall accuracy of the corresponding NN as the dependent variable. We use 20% of our ob- servations as a test set, and the rest as a training set. We report the testing mean absolute error (MAE) and coefficient of determination (R?).
1.0
1.00
2/M
20.0
2775
0070
2,670
(a) LeNet: degree
(b) LeNet: evec centr.
088
J the results for regression predic- tion on ImageNet dataset, the prediction model show similar trend as CIFAR-10 on this datat-
1.000
0.25
8070
065
000
650
set. The MAE values are smaller for this dataset since the accuracy range of both architectures much narrower than the CIFAR-10 10 dataset (See Table 2 for accuracy ranges of different architectures and datasets.)
(c) AlexNet: degree
(d) AlexNet: evec centr.
20.0
Results. Table summarizes the regression re-
2070
0.25
3
0.75
sults for four architectures where the indepen-
0.3
0.55
dent variable is degree features of rolled graph representation. For each step of this experiment, we use a concatenation of two consecutive fea- ture vectors as independent variable of regres- sion model. For LeNet, at timestamp 5-7 the regression model error (MAE for test set) is 5.74, while the accuracy range of LeNet for this dataset is wide (0.9-73.8), and based on R2 = 0.91, we interpret that 91% of variant in accuracy of NN can be explained by the de- gree changes of the rolled graph between timestamp 5-7. A similar trend is observed for AlexNet, VGG and ResNet, where after observing a few epochs, the prediction model shows a very low MAE with high R²
052
(e) ResNet-50: degree
(f) ReesNet-50: evec centr.
Figure 5: ImageNet: NN classification using the weighted degree-based and eigenvector centrality-basee signature vectors for LeNet, AlexNet and ResNet. Figen- vector centrality-based signatures (b), (d), (f) yield higher performance compared to the weighted degree- based signatures (a), (e), (e).
OBSERVATION In sum, the weighted degree-based signature vector of time-evolving graphs generated based on the rolled graph representation is a strong predictor of the actual accuracy value of NNs. For both CIFAR-I0 10 and ImageNet, we show that, by observing only a subset of early training epochs, we can effectively predict the accuracy value of NNs with small M AE and a high coefficient of determination R2² > 0.5.
Table 3: Regression Analysis ImageNet: Accu- racy prediction based the rolled graph representa- tion and the saggre-bbssed signature.
4.3 DISCUSSION
Time efficiency and early stopping. Figure rep- resents the total average runtime of NN training for early stopping of each architecture (green bars) with comparison of average run-time of graph generation, degree calculation and eigenvector centrality calcu- lation for the number of epochs that were needed for that architecture to achieve the highest accuracy in classification task. For all the 3 architectures
AlexNet
LeNet
ResNet
R²
MAE
R²
R
0.3
4.04
0.30
7.99
0.57
4.10
3.94
8.36
5-7
3.96
0.70
3.58
0.46
8.02
0.62
2.70
3.24
7.49
0.67
8

---

Under review as a conference paper at ICLR 2022
10
100
oryme
contaaty
Grain
Quatrality
10
Phyt.
renraaity
gram
Gugren
Cormutity
101
centraity
gram
ba grep
centriiity
(a) LeNet
(b) AlexNet
(c) VGG
(d) ResNet
Figure 6: Average total runtime for the NN training. and the rolled/unrolled graph generation (SI) and feature extraction (S2) on CIFAR- 10 dataset (()), ResNet architecture on both CIFAR-I 10 (ResNet-44) 44) and ImageNet (ResNet-50)d)), Rolled graph representation is more efficient/faster than early stopping to generate graph and calculate signature vector for all the architectures.
rolled graph representation can achieve a high accuracy prediction much faster than the early stopping of NN training. But for unrolled representation, this only true for LeNet architecture. As the size of NN increases, the unrolled graph generation gets slower and training with early stopping method is faster than our prediction framework.
Size analysis. Table 5 shows the number of nodes and edges of the rolled graph representations compared with the unrolled representation, our proposed rolled representation of NN reduces the complexity of NN architectures in terms of #nodes and #edges in the graph while retaining comparable performance on the prediction tasks. Our proposed rolled graph representation has big advantage in terms of size over the unrolled graph representation, especially for deeper networks.
Limitations, The unrolled representation is not scalable therefore cannot be applicable for larger networks and datasets. The main advantage of this representation is that there is no loss of information during the training phase of NNs, and we can interpret the learning process easier than the rolled method. For example, we showed that the negative subgraph alone would be stronger predictor of the accuracy of NNs, which can lead us to another direction of signed graph analysis in further study of the learning process of NNs.
Complexity analysis of the rolled graph representation. For an NN with ny total number of filters in all the conv layers and n, total number of neurons in the fully connected layers, modeling the nodes takes a constant time O(V)), where V is the set of generated nodes in the graph and |V nf + nin (due to dropout some nodes are removed). The computation of the edge weights O [V [V[44)), where [/ are the nodes at layer l.
RELATED WORK
We cover the most relevant work here, and dynamic graph mining in App. A.5 Some recent research efforts are devoted to modeling the NN architectures as graphs due to their topological identity and study their graph properties Rieck al. (2019): Filan al. (2020): You al. (2020). For example, You et al. You et al. 2020) propose a relational graph representation to model message exchange between layers, and empirically show the common properties shared by NNs with significantly improved predictive performance in terms of graph clustering coefficients and average path lengths. Rieck et al. Rieck et al. (2019) propose a complexity measure related to NN performance- persistence-basee on topological data analysis weighted stratified graph. Filan et al. Filan et al. (2020) present an exploratory study of the NN modularity. Gebbart et al. (2019) proposes to compute persistent homology over the activation graph of an NN. The output is a graded set of subgraphs, which are shown to be related to the task-specific semantic that are captured by original NN.
6 CONCLUSION
In this work, we investigated the early training dynamics of NNs from time-evolving graph perspective. We proposed a new graph representation to efficiently convert convolutional layers into compact and intuitive graph structures. Then, we showed that simple, temporal graph signature based on summary statistics of the degree or eigenvector centrality distributions over only a few epochs can be used as a strong predictor variable to estimate the accuracy of NNs in downstream tasks (c.g., image classification). Exploring the role of our efficient proposed framework for early stopping is a promising future direction.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
For reprodueibility, we provide the references to the datasets and existing (rolled) graph representation of convolutional layers in $ In App. A.T we provide the detailed hyperparameter settings for NN training. We will also make our code publicly available upon acceptance.
REFERENCES
Tiny imagenet.
Charu Aggarwal and Karthik Subbian. Evolutionary network analysis: survey. ACM CSUR, 47(1):1-36, 2014.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. ICLR, 2015.
Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos. Netsimile: A scalable approach to size-independent network similarity. arXiv preprint arXiv: /209. 2012.
Phillip Bonacich. Factoring and weighting approaches to status scores and clique identification. / math soc, 2 (1):113 120, 1972.
Yue Cao, Thomas Andrew Geddes, Jcan Yee Hwa Yang, and Pengyi Yang. Ensemble deep learning in bioinformatics. Nat Mach Intell, 209):500-508, 2020.
Supriyo Chakraborty and et al. Interpretability of deep learning models: A survey of results. In Smart SmardWorld, pp- 1-6, 2017. doi: L.L109/UCCAATC.221..88990
Daniel Filan, Shlomi Hod, Cody Wild, Andrew Critch, and Stuart Russell, Neural networks are surprisingly modular. arXiv preprint 2003,0000 2020.
Daniel Filan, Stephen Casper, Shlomi Hod, Cody Wild, Andrew Critch, and Stuart Russell. Clusterability neural networks. arXiv preprint arXiv:2103.03380 2021.
Thomas Gebhart, Paul Schrater, and Alan Hylton. Characterizing the shape of activation space in deep neural networks. In IEEE ICMLA, pp. 1537-1542, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jie Hu, Li Shen, and Gang Sun. Squecze-and-excitation networks. In CVPR, pp. 7132-7141, 2018. doi: 10.1109/VVP..201..0002
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, pp. 448 456. PMLR, 2015.
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time- dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 201 2011(1))PP1105 2011.
Alex Krizhevsky, Learning multiple layers of features from tiny images. pp. 32 33, 2009. URL https 7/ //www, cs. ctt.cssstoooo....... htt.stoee...ccceeeeee/eeeeeeeeee
features- 2009 pdf
Alex Krizhevsky, Ilya Sutskever, Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NeurlPS, 2012.
Lecun, L. Bottou, Bengio, and Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11) 01:2278-23222 1998. doi: 10.1 10111109/777999
Hao Li, Asim Kadav, Igor Durdanovie, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv:1608.087/ 087100 2016.
Yu Li, Chao Huang, Lizhong Ding, Zhongxiao Li, Yijie Pan, and Xin Gao. Deep learning in bioinformatics: Introduction, application, and perspective the big data era. Methods, 166:4 21, 2019.
Gabriele Lohmann, Daniel S Margulies. Annette Horstmann. Burkhard Pleger, Joeran Lepsien, Dirk Goldhahn, Haiko Schloegl. Michael Stumvoll, Arno Villringer, and Robert Tumner. Eigenvector centrality mapping for analyzing connectivity patterns fmri data of the human brain. PloS one, 5(4)e10232, 2010.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006.
10

---

Under review as a conference paper at ICLR 2022
Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. In WSDM, pp. 601-610. 2017.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl. and Charles Leiserson. Evolvegen: Evolving graph convolutional networks dynamic graphs. AAAI, volume 34, pp. 5363-5370, 2020.
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In NeurlPS, 2017.
Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn. Thomas Gumbsch, Karsten Borgwardt, Neural persistence; complexity measure for deep neural networks using algebraic topology. In ICLR, 2019. URL ht htRLhhtss:///peeeee httpp///////eeeeeee.ee net forum? 1 Biddiiddiiiiiieeeeee CCPPQ
Matteo Riondato, David Garcfa-Soriano, and Francesco Bonchi. Graph summarization with quality guarantees. DMKD, 34 349, 2017.
Olga Russakovsky, Jia Deng, and et al. ImageNet Large Scale Visual Recognition Challenge. ICV,, 115(3): 211-252, 2015. doi: 10. 1261-1166--200 01112266-1---11111 015-0816yy.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning dynamic graphs via self-attention networks. In WSDM, pp. 519-527, 2020.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, May 2015.
Uriel Singer, Ido Guy, and Kira Radinsky. Node embedding over temporal graphs. In IJCAI, pp. 4605-4612, 2019.
Ilya Sutskever, Oriol Vinyals, and Quoe Le. Sequence to sequence learning with neural networks. NeurIPS, 27:3104-3113 3112 2014.
Qin Wu, Xingqin Qi, Eddie Fuller, and Cun-Quan Zhang. "follow the leader": A centrality guided clustering and its application to social network analysis. The Scientific World Journal, 2013, 2013.
Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. In ICML, pp- 10881 10881-10891, 2020.
Tong Yu and Hong Zhu. Hyper-parameter optimization: A review of algorithms and applications. arXiv preprint 25530:2003305689 2020.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 EXPERIMENTAL SETUP: CONFIGURATION
We first train five different NN architectures, LeNet-5 Lecun et al.) 1998). VGG13 (Simonyan & Zisserman 2015), AlexNet (Krizhevsky et al. 2012), ResNet-32 and ResNet-44 44 (He et al. 2016), on
CIFAR-IO dataset and three architectures, LeNet-5, AlexNet and ResNet-50, on ImageNet. During training, the NN parameters are updated using stochastic gradient descent. On each dataset, we train NNs by combining 48 learning rates {1, 1.5, ................................ ,455 x {10-6, 10-1), and 10 dropout rates {0, 0.1..... 0.9}. All the models are trained for 50 epochs with batch size 128 and an early stopping method by which the training stops when the testing accuracy does not increase for 10 consecutive epochs. Consequently, performance. Information for the generated NNs is summarized in Table [ the range of epochs at which the training stops early, the range of final testing accuracy for the trained NNs, and the accuracy threshold used to map actual NN performance to 'lowhigh accuracy" labels for the classification task. We trained the NNs on an Nvidia 1080Ti GPU with 1 1IG memory, and we conducted all the other experiments on 2.60GHz Intel Xeon E5-2697 v3 platform with 1024G memory.
obtain 480 NNs per architecture and dataset, with diverse
For computational efficiency and avoid having largely imbalanced dataset, out of the 480 NNs. we randomly sampled 250 NNs with an even split of high- and low-accuracy networks. For this sample, the first I epochs of training for each configuration were saved as checkpoints to be converted to time-evolving graphs (step (S1)).
A.2 UNROLLED GRAPH REPRESENTATION
In these experiments, we split the represented graph into two subgraphs with positive and negative edge weight Then we used the two graphs Gos and Gneg to calculate the degree and eigenvector centrality feature vector summary for both of them, and concatenate those feature vectors to represent the whole graph Gpos-neg- According to Figure 4 weighted degree signature vector of Gneg is good descriptive variable to predict performance of NNs. For LeNet, we achieve an accuracy of 90% with only 3-5 epochs. For AlexNet, since the graph generation process was slow, we constructed the time-evolving graph based on few sub-samples of training epochs where T = 1, 5, 10, 15. The results show that even with a fewer sequence of observations the classifier can achieve high value of accuracy. For instance, at timestamp 10, in which the feature vector is the concatenation of degree features at epochs 1, 5, and 10, the accuracy of the classifier more than 85%
Based on results in Figure Ta signature vector calculated based on eigenvector centrality of Gneg also very good descriptive variable to predict performance of NNs and can achieve accuracy of 90% with only 3-5 epochs for LeNet.
For all the experiments on unrolled representation, the feature vector only based on Gneg achieves very high accuracy similar to higher than that of Gpos-neg- while feature vectors only based on Goos result in the poorest accuracy among them.
A.3 FEATURE ANALYSIS
Classification feature analysis. Figure 7a shows the weight of each statistical aggregator for graph degree of VGG architecture for CIFAR- 10. The top three highly weighted features are mean, standard deviation and median of degree. Figures 7b 7c and repressetnnt the change in value of those features respectively over time for high and low accuracy instances. We observe that the statistical aggregator of degree for high accuracy graphs tends to increase over time while for most of low accuracy one these values do not change over time or the change is very small. Figure&& LeNet architecture, while the values degree mean and standard deviation for low accuracy cases tend to have very big spike in the first 3 epochs of training but after that they follow a flat line trend and tend to not change. Figure 9 Iillustrates similar trend for ResNet-44 architecture and CIFAR-10 10 dataset. The mode degree of graphs based on high accuracy cases tends to change drastically over time while the low accuracy cases do not change and show a flat line pattern.
similar trend for the
In the rolled graph representation there is no negative weighted edge since the weight of each edge is calculated as norm of each channel
12

---

Under review as a conference paper at ICLR 2022
High ACCLENCY
High Accurats Law Accumny
High RECuERES
lartools
Arnuney
meedan
30
0.5
50
0.0
-10
0
10 12 16
8 12
10
10 34
(Reesamp
(a) SVM: feature importance
(b) Avg node degree time for different graphs.
(c) Stdev of node degrees over time for different graphs
(d) Median of node degrees time for different graphs.
Figure 7: VGG on CIFAR-10: (a) The top three most important features in SVM classification are the mean, stdev, and median of the node degrees. (b) The change of the average node degree time shows that, in graphs corresponding to high-accuracy NNs (blue lines), the average degree exhibits an increasing pattern, while has a flat pattern for low-accuracy cases (red lines).
cases low-accuracy NNs with increasing trend may be miss-classified in the classification task. (c) (d) The changes of the standard deviation and median of node degrees follow similar pattern to mean for both low- and high-accuracy cases.
Mean
Showiess
17.5
Law Accuracy
High Accurasy
11 Law Accurary
15.0
7.5
3.0
25
Timestarpp
Timeskamp
Timestamp
Timestmp
(a) SVM: feature importance
(b) Avg node degrec over time for different graphs.
(c) Stdev of node degrees over time for different graphs.
(d) Zoomed-in plot (b).
Figure 8: LeNet CIFAR-10 10: (a) The top three most important features in SVM classification are the mean, standard deviation and median of the node degrees. (b)(d) The change average node degree time shows that graphs corresponding to high-accuracy NNs (blue lines) the average degree tends change over time with a smooth pattern, while it tends to follow a flat line pattern (after an early extreme spike) for low-accuracy cases (red lines).
Maan DEy
Weight:
10
0.3
-3.0
5
(d) Median of node degrecs over time for different graphs. Figure 9: ReNet-44 on CIFAR-10: (a) The top three most important features in SVM classification are the mean, standard deviation and median of the node degrees. (b) The change average node degree over time shows that in graphs corresponding to high-accuracy NNs (blue lines) the average degree tends change over time drastically, while it tends to follow a flat line pattern for lcc-accyrycy cases (red lines).
(a) SVM: feature importance
(b) Avg node degree over time for different graphs.
(c) Stdev of node degrees over time for different
graphs.
A.4 GENERALIZING TO UNSERN ARCHITECTURES
In this section, we broaden the scope of our empirical setup to show that proposed graph representation and signatures are general and can be useful for performance prediction across different NN architectures. In this setup, fully train just small set of different NN architectures (i.e., different architectures and hyperparameters), and predict the performance on unseen NN architectures. We consider sets of experiments:
13

---

Under review as a conference paper at ICLR 2022
1.0
10
1.0
1.0
0.8
0.9
09
0.8
0.8
ACCUROO
08
0.2
0.:
0.5
11
03
20
Timestmpp
Trrcstampp
Tinestamp
Timestamp
(a) CIFAR-10, ResNet-44 (b) ImageNet, ResNet-50 (c) CIFAR-10, ResNet-32 (d) CIFAR-IO, ResNet-44
Figure 10: NN classification based on degree signatures for the empirical setup that tests generalization to unseen architectures. (a) Train on ResNet-32, test on ResNet-44, (b) Train on ResNet-34, test on ResNet-50. (c)-(d) Train on LeNet, AlexNet and VGG, test on ReNet-32 and ResNet-44, respectively. Our proposed framework is able accurately predict the performance level on previously unseen architectures hased on the NN structural dynamics a small number of epochs (<10).
1. We train our classifier the smaller ResNet architectures (ResNet-32 for CIFAR-IO, and ResNet- 34 for ImageNet), and test the performance the larger ResNet architectures (ResNet-44 for CIFAR-10 10, and ResNet-50 for ImageNet). In Figs. 10a 10a TOb framework is able to accurately predict the performance level of the previously unseen, large ResNet architectures. Our results show that the proposed temporal signatures be used in generalized scenario to predict the accuracy level of the same architecture with different numbers of layers (on the same dataset). This generalization from small bigger architectures is important since it is faster to train the smaller architectures.
observe that proposed
In Figs. 10c and 10d we see that our proposed method also successfully predicts the perfor- architecture (i.e. ResNet) when the training set is combination of older
mance level of architectures (LeNet, VGG, AlexNet).
For both of the experiments, we set universal threshold value label graphs in the train and test set. For the training set of classifiers, we randomly choose subset of the NNs with balanced high/low accuracy labels. The size of the training set the first experiment 250 and in the second experiment is 400. The experiments were repeated times and the average accuracy of classification is reported.
A.5 ADDITIONAL RELATED WORK
Dynamic Graph Mining, Dynamic graphs are mostly modeled as sequence of edge additions and/or edge deletions. To mine the dynamic graphs, traditional approaches leverage graph properties such as node centralities or motifs Riondato et al. (2017); Paranjape et al. (2017); Kovanen et al. (20TT). Despite their simplicity, these approaches show effectiveness temporal tasks such event detection Paranjape et al. (2017) and structural prediction Aggarwal & Subbian (2014). Recent mubeddiigg-bssed approaches tend to model dynamic graphs as sequence of discrete-time snapshots and simultancously represent the graph structure of each snapshot well as the temporal evolution using deep neural networks such as GRU/LSTM [Sankar et al.] (2020); Singer et al. (2019); Pareja
al. (2020). DySAT Sankar al. (2020) leverages self-attention to compute node representations by jointly modeling graph structural property and temporal dynamics. EvolveGCN Pareja et al.) (2020) uses GCN generate node embeddings for the past snapshots, and learns parameters of the hidden layer for the next snapshot using GRU/LSTM. Unlike these methods, we propose two different approaches represent the underlying graph structure of NN, and very simple and efficient dynamic graph signature feature vector to predict the accuracy of corresponding NNs.
14

---

Under review as a conference paper at ICLR 2022
A.6 ADDITIONAL FIGURES AND TABLES
LeNet-Cenzaalit
LeNet
0.55
0.90
0.20
2.880
2.50
0.55
9.
0.75
0.75
2
0.5%
SLP pmo
HLPwwkag
M.Poriii peo noy
0.55
0.55
0.30
SWM6
Timestamp
Timestamp
Timestamp
(a) LeNet, unrolled graph repre- LeNet, rolled graph represen- (c) AlexNet, rolled graph repre- scntation
tation
sentation
Figure 11: CIFAR-10: NN classification based on cigenvector centrality signatures. The eigenvector centrality is strong predictor of NN performance after observing few epochs of training. The MI.P classifier (red lines) outperforms SVM the architectures.
1.00
1.00
0.95
0.95
0.90
0.35
0.80
0.75
0.75
0.70
0.70
0.55
0.63
0.50
SVW
HLP
0.50
SVN
0.35
expAvg
expAvg
0.30
10 0.50
10
estamp
lirestamp
(a) ResNet, degree
(b) ResNet, eigenvector centrality
Figure 12: CIFAR-IO, ResNet-32: NN classification based on degree and cigenvector centrality -bssed signatures. The both degree and eigenvector centrality are strong predictor of NN performance after observing few epochs of training.
Table 5: Size of generated graph snapshot based the rolled and unrolled conv layer representation.
CIFAR-10
ImageNet
LeNet
AlexNet
VGG
ResNet32
ResNet44
LeNet
AlexNet
ResNet50
[2] rolled
2925
1613
144
1597
713
3015
22
[t] rolled
12954
460
304 576
51 888
73392
115 362
206 560
10821 824
unrolled
11 166
54986
205 066
640
53016
uncolled
658024
45 99.997600 696
114.499
843.36
0437777
15


Reviews:
[{"review_id": "vzwDzawyGhD", "reviewer": "Reviewer_zP52", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Technically the paper is sound and I enjoyed reading it. However, I have some concerns regarding the presentation and motivation of the problem considered. \n- The motivation for the problem is not clear to me. Sure, with this technique one could decide within a few epochs of starting training of a model, whether to continue or terminate training. However, to train such a predictor requires several rounds of training for the original task (under different hyperparameters) to already have been done. Why does one need to retrain for the original task is unclear to me. \n- One of the key claimed contributions of the paper is the rolled graph representation. However, it is not clear what is the difference between a rolled representation and an unrolled representation (i.e., section 3.1). E.g., the edge between v^i_k and v^j_l has weight norm(K(l,h_j,w_i,k)) but it’s unclear what the latter notation means. It would greatly help if the authors could explain (and justify) the differences better. \n- It seems bias parameters are not involved while summarizing the neural network state. Why is this the case. \n- Problem 1 in Section 3 needs clarification. The paper seeks to predict the accuracy of a new instance N_tst, but the accuracy of N_tst after how many rounds of training is not specified.  \n", "summary_of_the_paper": "The paper considers the problem of predicting test performance of a neural network model by using statistics about the parameter weights in relation to the network structure during the first few epochs of training. The authors propose two approaches, using degree centrality and eigenvector centrality, to compute a “signature” that summarizes the neural network’s state during a training epoch. They also propose a rolled-graph representation that uses fewer nodes to represent a convolutional neural network, thereby making the training and prediction process more efficient. Experimental evaluation shows proposed method \thaving similar predictive performance as unrolled representation, while being computationally faster. ", "summary_of_the_review": "Technically sounds paper, but lacking in motivation and presentation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ds-HjgNKHrV", "reviewer": "Reviewer_Txru", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The graph analysis perspective for understanding neural networks is definitely timely and promising. The proposed method seems (experimentally) efficient in terms of the number of epochs and prediction performance. Moreover, in comparison to state of the art methods such as Rieck et al.'19, the methods is computationally more efficient. \n\nThere are however different points that should be clarified in the text. \n\n1) The whole framework should be better explained. While Fig. 1 is very useful, the paper is missing a connection between Fig. 1 and the graph construction (Figs. 3,4). In particular, it would be useful to have a picture that shows the graph structure for a 'simple' deep neural network, with only a few filters and layers, as well as the number of edges corresponding to each step. Fig. 3 is good, but it does not give the complete picture to the reader. \n\n2) The authors should explain a bit more the intuition behind these graph signatures. What type of dynamics do they capture? What do they reveal about the architecture? What is the advantage in comparison to other graph features (local or global)?\n\n3) The authors claim that the method can be used in interpretability-related tasks. Can you elaborate on that or give some examples?\n\n4) How do you define the training set for a specific architecture? For one architecture, and one dataset, you have a single time-varying graphs, no? \n\n4) The paper needs some work in terms of presentation. There are different typos or expressions that should be clarified. Some of them are listed below: \n   - pg.3 \"results feature-map\" --> \"results in feature-map\"\n   - pg.3 \"number of nodes\" --> \"the number of nodes\"\n   - pg.3 \"layer of graph\" --> \"layer of the graph\" (the entire sentence needs to be rewritten)\n   - pg.4 Fig.3: K layers means K node types? Does the type of the node play a role in defining the features?\n   - pg.4: section 3.2: \"the introduced time-evolving graph representations\" . However, from my understanding, no time-varying graph representation has been introduced till that point. \n   - pg.6: Please clarify what is the binary classification in Table 2\n   - pg.7: \"Imagent\" --> \"ImageNet\"\n   - Please explain the green colour in Fig. 6.\n   - pg.8: \"changes of rolled graph graph\" --> \"changes of the rolled graph\"\n   - pg.8: \"a few epochs prediction model shows\" --> \"a few epochs, the prediction model shows\"\n   - pg.8: \"that needed for\" --> \"that were needed for\"\n   - pg.9: Limitations: please check different typos in that paragraph\n   - Please make references consistent; some of them are even missing the venue (e.g., Krizhevsky et al.) or page numbers. \n   - pg.12: 'results the poorest accuracy\" --> \"result the poorest accuracy\"", "summary_of_the_paper": "This paper tries to model the learning dynamics of a (deep) neural network using graphs. In particular, the authors propose to represent the learning process as a time-varying graph, which is then used to capture the structural changes through some simple graph statistics (such as weighted degree and eigenvector centrality), and eventually to predict the accuracy of the neural network (through some simple ML models such as SVMs or MLP).  ", "summary_of_the_review": "The paper still needs some work to merit a publication. However, I would be willing the accept the paper if the authors do a careful revision and address all the comments raised by the reviewers. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WnMUHTF5Ygm", "reviewer": "Reviewer_cuEB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Strenghts\n- The paper is rather well written, clear and coherent (I could only spot a typo “ changes of rolled graph graph between”,  with the repeated “graph” word)\n- The empirical analysis is rather extensive and the results seem to support the claims\n* Weaknesses\n- Lack of theoretical insights makes the contribution slightly less relevant and appealing\n- Lack of asymptotic computational (time and space) complexity analysis would definitely add some more value to the paper, especially when comparing the behavior wrt early stopping and the literature alternatives.\n", "summary_of_the_paper": "The paper proposes a graph-based approach to assess the performance of deep neural networks in vision tasks. The approach is essentially based on representing the first few epochs of SGD-based training of the neural architecture seen as a graph (where nodes stand for neurons and edges stand for connections among neurons), followed by feature extraction, signature construction and finally a classifier (to predict the high or low level of final accuracy) or a regress or (to predict the exact finally accuracy score) layer.\nThe approach is assessed on several experimental settings, though limited to the case of static networks (e.g., without recurrent/recursive connections). The results seem encouraging and interesting", "summary_of_the_review": "The paper is overall convincing, even though lack of theoretical insights and of computational complexity analysis reduce a bit my final evaluation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3afiHwTtQcV", "reviewer": "Reviewer_DNSD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: It appears as though the rolling graph representation is promising. The subject is novel and deserves more investigation. \n\nWeakness:\n - It's unclear why only degree and Eigen centrality are taken into account. There are other alternative measures of importance or centrality. \n- The proposed method is intuitive and lacks solid theoretical support.\n- The overview of node characteristics does not adequately reflect the structural evolution of large-scale NNs in the modern era (ResNet). \n- The neural networks empirically evaluated, including LeNet, AlexNet, and VGG, are somewhat out of date. It would be advantageous to consider some more recent NNs, such as ResNet. \n- To facilitate interpretation, node centralities are used to indicate the graph characteristic. Reintroducing them into SVM may not improve their interpretability in some way. \n- To make the results more understandable, the centralities can also be put into a more interpretable classification model, such as logistic regression or classification tree. \n- Baselines are omitted from the experiment.", "summary_of_the_paper": "The purpose of this research is to attempt to forecast a neural network's performance from early NN dynamics. The dynamics of the neural network are stored in a time-evolving graph. The summary of two node properties, the weighted degree, and the eigenvector centrality is extracted and utilized to train classification and regression algorithms. This methodology, when combined with the paper's suggested rolled graph representation for convolutional layers, results in faster prediction than the classic early stopping method. \nThe paper's primary contribution is that the suggested rolled graph model for convolutional layers improves time and space efficiency in comparison to the existing unrolled representation.", "summary_of_the_review": "I recommend rejecting this article. Although predicting NN performance from the network structure and dynamics is an intriguing topic, it is not one that this research proposes. The method, as well as the experiment, are more about preliminary and experimental exploration. Apart from the rolled graph representation of the convolutional layers, there is only a little theoretical enhancement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to represent a deep neural network as a graph and analyze its learning dynamics as a time series of weighted graphs corresponding to the neural network. As the graph representations, the authors propose to use a rolled representation in addition to a unrolled representation. Then, they proposed to utilize the graph features of the representations for predicting its predictive accuracy. 

This paper presents an interesting idea which could be used for predicting the test accuracy from the first few epochs training. However, there are also several weaknesses as pointed out by the reviewers. First, the justification of using the graph structure to predict the accuracy is weak (indeed, the graph structure can be used for prediction, but its necessity is not well supported), and there is no theory to support the proposed method. Second, the problem setting is a bit wired. The training data is generated by using the same architecture and data set. Although the authors gave additional experiments on the architecture generalization, it is still difficult to see how convincing the method is for more general settings. Third, baseline methods are not shown in their experiments.  
In addition to that, the thresholds for the classification tasks seem to be too small (like 40% in CIFAR10) which would make the problem too easy. Therefore, the practicality of the method is rather unclear. 

This paper is quite on the borderline, but for the reasons listed above, it is a bit below the acceptance threshold.
Decision: Reject