Deep Neural Network Fusion via Graph Matching with Applications to Model Ensemble and Federated Learning

Chang Liu, Chenfei Lou, Runzhong Wang, Alan Yuhan Xi, Li Shen, Junchi YanICML 2022 · OpenReview

Fusing independently trained neural networks often fails because internal channels are randomly permuted during training. This paper formulates model fusion as a graph matching problem to align channels based on second-order weight similarities. The authors propose a highly scalable algorithm called GAMF (Graduated Assignment Model Fusion), which significantly outperforms existing linear assignment methods in both compact model ensembling and federated learning scenarios.

The Challenge of Model Fusion

Imagine having several neural networks trained independently on different subsets of data. Combining them into a single, highly accurate model without accessing the original training data is highly desirable. It enables the creation of "compact ensembles"—saving the memory and compute of running multiple models—and serves as the foundational mechanism for Federated Learning (FL).

The naive approach is to simply average the weights of the models (e.g., FedAvg). However, due to the randomness of initialization and stochastic gradient descent, the internal channels of independently trained networks are randomly permuted. For instance, Channel 5 in Model A might represent the exact same feature as Channel 12 in Model B. If you simply average them, the features destructively interfere, severely degrading the model's performance.

Recent works (like OTFusion) attempt to align the channels before averaging using Linear Assignment. However, they only look at "first-order" similarity, treating channels as isolated entities. This paper argues that neural networks are inherently graphs: we shouldn't just look at the channels (nodes), but also the weights connecting them (edges).

Methods: The GAMF Approach

The authors formulate model fusion as a Graph Matching (GM) problem, which is a Quadratic Assignment Problem. By matching nodes (channels) while preserving edge affinities (weights), they capture the "second-order" similarity between models.

Graph matching concept for neural networks

However, standard GM is NP-hard. For a modern neural network with thousands of channels, the mathematical affinity tensor requires $O(d^4)$ memory, which would instantly crash standard commercial solvers. To solve this, the authors introduce GAMF:

  1. Exploiting Intrinsic Sparsity: The authors observe that matching a channel in Layer 1 to a channel in Layer 3 is mathematically meaningless. By restricting matches to the same layer, the affinity matrix becomes incredibly sparse, dropping the complexity to a manageable level.
  2. Slice-and-Scan Algorithm: GAMF uses a memory-efficient iterative process. It starts with a relaxed, continuous assignment (using the Sinkhorn algorithm) and gradually tightens the constraints (annealing) until it converges into a strict 1-to-1 discrete matching (Hungarian algorithm).
  3. Multi-Model Cycle Consistency: When fusing more than two models, GAMF enforces "cycle consistency." If Model A aligns to B, and B to C, then A's alignment to C must mathematically agree, preventing contradictory alignments across the ensemble.

Key Insights and Results

The authors evaluated GAMF on standard image classification benchmarks (MNIST, CIFAR-10, CIFAR-100, and Tiny-Imagenet) using various architectures (ConvNet, LeNet, VGG11). Data was partitioned into homogeneous (IID) and heterogeneous (Non-IID) splits to simulate real-world federated learning conditions.

  • Second-order > First-order: Aligning channels based on how they connect to the next layer yields much smoother and more accurate alignments than looking at channels in isolation.
  • Compact Ensembles: On CIFAR-10 (VGG11, heterogeneous data), finetuning a GAMF-fused model achieves 79.40% accuracy. This significantly outperforms the previous state-of-the-art OTFusion (62.08%) and vanilla averaging (60.34%).
  • Federated Learning: On the difficult CIFAR-100 dataset (5 clients), GAMF reaches 49.80% accuracy, outperforming FedMA (47.50%). Notably, OTFusion completely fails to converge in this setup (1.00%).
Accuracy vs. communication round showing GAMF and Moon synergy
  • Synergy with Local FL Improvements: GAMF focuses entirely on the server-side aggregation step of Federated Learning. This means it can be seamlessly combined with client-side training improvements. Combining GAMF with Moon (a contrastive learning FL method) yields the best overall results, hitting 84.92% on CIFAR-10 (5 clients). This proves that better local training combined with better global alignment is a winning formula.
  • The Trade-off: Because it calculates second-order similarities, GAMF takes about 50% more compute time than OTFusion. However, this overhead is justified by the massive accuracy boost and the fact that communication, not server compute, is usually the primary bottleneck in FL.

Limitations and Future Work

While optimized, GAMF still carries a higher time complexity than simple averaging or first-order methods. Additionally, the current formulation assumes all models being fused have the exact same architecture and number of channels. Future directions include exploring the fusion of different-sized models, scaling the algorithm to handle a massive number of clients, and replacing traditional optimization-based graph matching with modern, learning-based graph matching neural networks.

Summary updated

Abstract

Model fusion without accessing training data in machine learning has attracted increasing interest due to the practical resource-saving and data privacy issues. During the training process, the neu...
BibTeX
@inproceedings{liu2022deep,
  author = {Chang Liu and Chenfei Lou and Runzhong Wang and Alan Yuhan Xi and Li Shen and Junchi Yan},
  title = {{Deep Neural Network Fusion via Graph Matching with Applications to Model Ensemble and Federated Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=FZz7TvipL4},
}
Figure