Graph Structure of Neural Networks

Jiaxuan You; Jure Leskovec; Kaiming He; Saining Xie

Source-linked AI summary

Graph Structure of Neural Networks

Jiaxuan You, Jure Leskovec, Kaiming He, Saining Xie

arXiv:2007.06559v2Jul 13, 2020cs.LGcs.CVcs.SIstat.ML

TL;DR

The paper studies the limited understanding of how neural-network graph structure relates to predictive performance. It introduces relational graphs, in which computation is modeled as message exchange, and finds a graph-structure sweet spot associated with improved performance across architectures and tasks.

Problem
The relationship between neural-network graph structure and predictive performance is poorly understood, despite its importance for architecture design and neural architecture search.
Method
The paper represents neural networks as relational graphs whose message-exchange rounds correspond to neural computation, then systematically varies graph structure across architectures.
Results
A relational-graph sweet spot yields significantly improved performance, with performance varying smoothly by clustering coefficient and average path length across architectures and tasks.
Takeaways & Limitations
Graph structure provides a useful basis for analyzing and designing neural architectures, connecting deep-learning design with graph methods from network science and neuroscience.
Takeaways & Limitations
The study focuses on graph structure at the layer level, leaving the more complex hierarchical structure of neurons, layers, blocks, and networks largely unexplored.

Abstract

from arXiv · show

Neural networks are often represented as graphs of connections between neurons. However, despite their wide use, there is currently little understanding of the relationship between the graph structure of the neural network and its predictive performance. Here we systematically investigate how does the graph structure of neural networks affect their predictive performance. To this end, we develop a novel graph-based representation of neural networks called relational graph, where layers of neural network computation correspond to rounds of message exchange along the graph structure. Using this representation we show that: (1) a "sweet spot" of relational graphs leads to neural networks with significantly improved predictive performance; (2) neural network's performance is approximately a smooth function of the clustering coefficient and average path length of its relational graph; (3) our findings are consistent across many different tasks and datasets; (4) the sweet spot can be identified efficiently; (5) top-performing neural networks have graph structure surprisingly similar to those of real biological neural networks. Our work opens new directions for the design of neural architectures and the understanding on neural networks in general.

1. Introduction

The paper addresses limited systematic understanding of how neural-network graph structure relates to predictive performance. It introduces relational graphs to study this relationship across architectures and tasks, finding a performance sweet spot characterized by graph measures.

Motivation: Neural-network architecture affects performance, but its relationship with underlying graph structure remains poorly understood.This gap is especially relevant to neural architecture search, which exhaustively explores connectivity patterns.
Relational graph representation: Relational graphs represent neural-network layers through message exchange between nodes rather than only directed data flow.This formulation can represent multiple layer types while avoiding several computational-graph constraints.
Experimental framework: The study explores relational graphs using clustering coefficient and average path length, then translates them into neural networks under controlled computational budgets.The framework supports MLPs, CNNs, ResNets, and other architectures.
Findings: A sweet spot of relational graphs produces significantly improved performance under controlled computational budgets.Performance is approximately a smooth function of clustering coefficient and average path length.
Findings: The findings are consistent across MLPs, CNNs, ResNets, EfficientNet, CIFAR-10, and ImageNet.The sweet spot can be identified using a few graph samples and a few training epochs.
Implications: Well-performing neural networks have graph structures surprisingly similar to those of real biological neural networks.The results are presented as relevant to neural-architecture design and the broader understanding of deep learning.

2. Neural Networks as Relational Graphs

The paper introduces relational graphs, representing neural networks through message exchanges over graph-structured neuron features. This framework unifies diverse architectures by varying node features, message and aggregation functions, and graph connectivity.

2.1. Message Exchange over Graphs: Relational graphs associate neural networks with message exchanges between graph nodes, where messages are transformed on edges and aggregated at nodes.Each exchange round updates node features from neighboring messages, with self-edges assumed and undirected graphs used for simplicity.
2.2. Fixed-width MLPs as Relational Graphs: A fixed-width MLP layer corresponds to a complete relational graph with a specialized message-exchange function.Generalizing the graph structure beyond completeness produces a broader family of models containing fixed-width MLPs as a special case.
2.3. General Neural Networks as Relational Graphs: Relational graphs generalize to variable-width networks by allowing node features and message functions to have differing dimensions across nodes and layers.An n-node graph can partition an m-dimensional layer across nodes, subject to the narrowest layer limiting the maximum graph size.
2.3. General Neural Networks as Relational Graphs: Convolutional layers are represented by replacing scalar message operations with convolutional operators, while dense convolutions remain complete graphs.The same framework also preserves specialized designs such as residual connections and alternating 3×3 and 1×1 convolutions.
2.3. General Neural Networks as Relational Graphs: With suitable node-feature and message-exchange definitions, relational graphs represent diverse architectures including MLPs, CNNs, and ResNets.The representation provides a unified language for architectures that are commonly implemented as complete relational graphs.

3. Exploring Relational Graphs

The paper explores relational-graph design using graph measures, flexible graph generation, and matched computational budgets. WS-flex is introduced to cover a broader graph-design space while keeping neural-network comparisons computationally controlled.

3.1. Graph Measures: The study characterizes relational graphs using average path length and clustering coefficient, capturing global and local structural properties.Both measures are established in network science and neuroscience.
3.2. Design of Graph Generators: Classic graph generators cover limited regions of graph-measure space despite extensive sampling across ER, WS, BA, Harary, ring, and complete graphs.The study generated hundreds of thousands of graphs from some generator families while still observing limited coverage.
3.2. Design of Graph Generators: WS-flex relaxes the equal-degree constraint of Watts-Strogatz graphs to generate a wider coverage of graph measures.Its parameters are node count n, average degree k, and rewiring probability p, with edge count e = ⌊n ∗k/2⌋.
3.3. Controlling Computational Budget: Neural networks translated from different relational graphs are compared at approximately matched complexity using FLOPS as the computational-budget metric.Widths can be adjusted without changing graph structure, matching baseline FLOPS within 0.5%.

4. Experimental Setup

The experiments evaluate relational graphs across CIFAR-10 and ImageNet using multiple neural architectures, while controlling computational complexity and varying the sampled graph space.

Datasets and architectures: The study examines MLPs on CIFAR-10 and ResNet-family, EfficientNet-B0, and CNN architectures on ImageNet.CIFAR-10 uses 3942 sampled 64-node graphs, while ImageNet uses a smaller graph sample because of computational cost.
CIFAR-10 setup: The CIFAR-10 baseline is a 5-layer MLP with 512 hidden units, trained for 200 epochs with five random seeds.Each layer uses ReLU and BatchNorm, with cosine learning-rate scheduling.
ImageNet setup: ImageNet models are trained for 100 epochs with cosine learning-rate schedules and three random seeds.Batch sizes are 256 for ResNet-family models and 512 for EfficientNet-B0.
Evaluation controls: All visualized results use rigorously controlled computational budgets and average at least three random seeds.The complete graph with C = 1 and L = 1 serves as the baseline.
Graph instantiation: Sampled relational graphs replace dense and convolutional layers while input, output, down-sampling, and skip-connection designs remain unchanged.The models are matched to reference computational complexity.

5. Results

Across tasks and architectures, relational graphs with particular clustering coefficients and average path lengths outperform complete-graph baselines, with performance varying smoothly across graph measures. The promising region can be identified from relatively few graph samples and early training results, and top-performing artificial graphs resemble biological neural networks.

5.1. A Sweet Spot for Top Neural Networks: Best relational graphs improve top-1 error over complete-graph baselines by 1.4% on CIFAR-10 and 0.5%–1.2% on ImageNet.The comparison is made under controlled computational budgets.
5.1. A Sweet Spot for Top Neural Networks: Top-performing graphs cluster in a sweet spot defined by their clustering coefficient C and average path length L.The sweet spot is identified by aggregating graphs into bins and retaining bins not significantly worse than the best-performing bin.
5.2. Graph Measures and Performance: Performance is approximately a smooth function of clustering coefficient and average path length.The study visualizes the trends with second-degree polynomial regression while fixing one measure within a small range.
5.3. Consistency across Architectures: The consistent sweet spot across architectures is C ∈[0.43, 0.50] and L ∈[1.82, 2.28].The reported U-shaped trends are also visually consistent across architectures.
5.4. Quickly Identifying a Sweet Spot: Only 52 graph samples achieve a 0.90 Pearson correlation with bin values computed from all 3942 samples.This indicates that a similar sweet-spot analysis can use substantially fewer graphs.
5.4. Quickly Identifying a Sweet Spot: After 3 training epochs, validation top-1 error reaches a 0.93 correlation with results after 100 epochs across 52 relational graphs.This shows that early training results can identify graphs that perform well after full training.
5.5. Network Science and Neuroscience Connections: Top-performing relational graphs have graph measures highly similar to biological neural networks.Translating biological neural networks into 5-layer MLPs also produced models that outperformed complete-graph baselines, although the authors describe the finding as preliminary.

6. Related Work

The related work situates the study among approaches that design neural-network connectivity at macro and micro scales and among neural architecture search methods that learn connectivity patterns.

Neural network connectivity: Prior neural-network connectivity research considers macro structures across layers and micro structures within layers.The cited work spans connectivity patterns at different granularities.
Neural architecture search: Neural architecture search studies learn connectivity patterns at micro or macro levels while developing improved learning and search algorithms.NAS-Bench-101 defines a constrained graph search space by enumerating DAGs with at most seven nodes.

7. Discussions

The discussion examines graph structure as a prior, its relationship to learned structure, and the framework’s broader connection to GNNs. It also identifies hierarchical exploration and implementation speed as important limitations.

Scope and limitations: The study focuses on layer-level graph structures, although neural networks are hierarchical graphs spanning neurons, layers, blocks, and whole networks.Exploring this larger design space is described as computationally prohibitive.
Scope and limitations: The current implementation uses weight masking and has worse wall-clock performance than baseline complete graphs.Block-sparse kernels and fast sparse ConvNets are identified as possible ways to narrow the gap between theoretical FLOPS and practical gains.
Prior versus learning: The relational graph is currently used as a structural prior, with its structure hard-wired throughout training.The authors ask whether graph structure can instead emerge from training a fully connected network.
Prior versus learning: After training, inferred graphs from a fully connected CIFAR-10 MLP move toward the sweet spot but remain worse than the best graph imposed as a prior.The learned graph is inferred by grouping hidden-layer weights, symmetrizing them, using Frobenius norms as edge values, and thresholding.
Prior versus learning: Special cases occur where learning the graph structure is superior, particularly when the task is simple and network capacity is abundant.These results further support studying graph structure to understand predictive performance.
Unified view of GNNs: Under the relational graph view, GNNs are a special class of neural architectures whose graph structure is input data and whose message functions are shared across edges.This unified view is intended to connect GNN and general neural architecture design and encourage transfer of techniques between them.

8. Conclusion

The paper proposes relational graphs as a new perspective for analyzing neural networks. It suggests applying graph-based techniques from network science and neuroscience to understanding and designing deep neural networks.

Conclusion: Relational graph representation provides a new perspective for analyzing and understanding neural networks.The conclusion frames this as a transition from studying conventional computation architectures to studying neural-network graph structure.
Conclusion: Graph techniques from network science and neuroscience could contribute to understanding and designing deep neural networks.The paper presents this as a future research direction for more complex situations.

Appendix for “Graph Structure of Neural Networks”

The appendix lists four authors and their affiliation markers.

Jiaxuan You and Jure Leskovec are listed with affiliation marker 1.
Kaiming He and Saining Xie are listed with affiliation marker 2.
The author list contains four named researchers.

1. Details for Generating Relational Graphs

The appendix generates relational-graph candidates from several graph families and samples them using graph-structure measures. Most generators fix 64 nodes and constrain sparsity between 0.125 and 1.0.

Generation setup: The graph-generation appendix fixes the number of nodes at n = 64 and constrains graph sparsity to [0.125, 1.0].This setting applies across the described generators.
Graph families: WS graphs are parameterized by node count, integer initial degree, and rewiring probability; the appendix generates 486,000 instances.The search uses 54 degree settings, 300 squared probability values, and 30 random seeds.
Graph families: ER graphs are parameterized by node count and edge count, with 52,800 graphs generated using 30 random seeds.The edge-count range spans from 64 × 4 to 64 × 63/2.
Graph families: BA graphs are described by the number of nodes and the number of existing nodes to which each new node connects.The supplied passage states the parameterization but does not provide the total number generated.
Sampling strategy: The appendix subsamples one graph per occupied two-dimensional bin over average path length and clustering coefficient, yielding 3,942 WS-flex graphs.For ImageNet, a further subsample produces 52 graphs distributed roughly uniformly in graph-measure space.

2. Details for Matching the Reference FLOPS

The study matches neural networks to reference FLOPS by adjusting layer widths, while examining how width and depth affect graph–performance relationships.

Matching the Reference FLOPS: Reference FLOPS are matched by varying neural-network layer widths and selecting widths closest to the target computational budget.For uniform-width networks, widths are incremented by one and the smallest width above the reference FLOPS is selected.
Graph Measures: Figure 1 compares global and local graph measures with 5-layer, 512-dimensional MLP performance on CIFAR-10.
Width and Depth: Figure 2 measures Pearson correlations across graph-translated MLPs with different widths and depths, using the 5-layer, 512-dimensional MLP as default.

3. Details for Wall Clock Running Time

The experiments examine graph measures, network size, and task difficulty, finding broadly stable structural patterns but important depth- and task-dependent exceptions.

Graph Measures: More graph measures exhibit a U-shaped correlation with predictive performance across 3,942 relational graphs evaluated with 5-layer MLPs on CIFAR-10.The overall trend is visualized using locally weighted linear regression.
Width and Depth: Graph-structure correlations remain high across networks with different widths, but reducing MLP depth to 3 layers reverses the correlation.Increasing depth to 7 layers maintains high correlation with the 5-layer MLP; a 3-layer MLP has only one message-passing round over the relational graph.
Graph Size: Varying relational-graph size has little effect on the study’s findings across 52-, 64-, and 71-node graphs.The ablation averages results from 482, 449, and 422 relational graphs for the three graph sizes, respectively.
Task and Dataset Effects: For some CNNs on CIFAR-10, the usual sweet spot disappears and approximately fully connected graphs perform best.The reported sweet spot is C ∈[0.43, 0.50] and L ∈[1.82, 2.28]; this exception does not occur for the corresponding ImageNet setting.
Task and Dataset Effects: Reducing an 8-layer CNN from 64 to 16 dimensions on CIFAR-10 restores the advantage of sparse graph structures over the complete graph.The paper hypothesizes that structural priors matter less when a simple task has abundant representation capacity.
Task and Dataset Effects: For challenging ImageNet tasks, sparse relational graphs consistently outperform fully connected counterparts in the sweet spot regions.The reported exception is specific to some CIFAR-10 CNN settings; the figure discussion also notes that no sweet spot is identifiable for an 11-layer MLP on CIFAR-10.