Deep Graph Mating

Response to Reviewer tRzs

We appreciate the reviewer for the positive support and constructive comments.

W1. & Q1. Statistics recomputation details

"The authors miss the discussions on the Grama case where pre-trained models already contained normalization layers, which is common in the area of graph neural networks. In that case, it is unclear whether the batch statistics are also recomputed in CMC. If they are, it should be specified when the recomputation occurs: simultaneously with LFNorm or after?"

"Can you clarify if the statistics in the original normalization layer are recomputed during Grama? If so, when would they be recomputed?"

Response: We apologise for not having sufficiently highlighted the details regarding the recomputation of statistics, which might have led to them being overlooked by the reviewer. In fact, as detailed in line 313-314, we have indeed discussed the scenario where models are equipped with normalisation layers. We have explicitly explained that the running mean and variance of the original normalisation layers are recalculated for the child GNN. In our revised version, we will enhance the clarity of this detail further by also providing additional explanations in Sect. 5.3.

But admittedly, we apologise for not having specified when the recomputation of statistics occurs for the original normalisation layers in our paper. We appreciate the reviewer's insightful comments on this issue. As specified in the source code provided in the supplementary material, we clarify that the recomputation of statistics is performed concurrently with that of the LFNorm layer for the child GNN. In the revision, we will provide a detailed clarification and add the discussion on the normalisation-related procedures described above in Sect. 5.3 and Sect. 6.

---

W2. & Q2. Multi-model GRAMA results

"Because the authors have claimed multimodel reuse as a contribution of this work, I would advise the authors to include more experiments for the Grama cases with three or more pre-trained models. Otherwise, clear statements should be added to limit the scope of the study to the reuse of two pre-trained models."

"Have you experimented with using three or more pre-trained models in Grama?"

Response: We appreciate the reviewer's constructive suggestion. As suggested, we have conducted additional experiments on disjoint partitions of the ogbn-arxiv dataset using the architecture described in Tab. 10 of the main paper, specifically for the proposed GRAMA in scenarios involving the simultaneous reuse of three pre-trained models. The results, presented below, demonstrate that our proposed DuMCC approach is also effective in multi-model GRAMA contexts. These results will be incorporated into the revised version of the paper.

---

W3. & Q3. Linking experiments to the claims to validate

"The descriptions and explanations in the experimental results are not closely matched with the authors' assumptions and propositions from the previous sections. It is suggested that the authors more closely relate the texts in the experimental section to the methods section, particularly by specifying which results validate which proposition or claim. This would make the paper more readable."

"Consider improving the experimental section to more closely relate the texts to the validated claims."

Response: We would like to thank the reviewer for the constructive suggestion. In our revised version, we will strive to expand the text in Sect. 6. This will include more detailed descriptions that closely and explicitly connect the results presented in Figs. 2-3 and Tabs. 2-5 with the validated conjectures, propositions, and claims discussed in Sects. 4-5.

---

W4. Minor problem

"In the appendix, there is a minor problem where Eq 30 extends beyond the margin of the paper."

Response: Thank you for pointing out this formatting issue. We will address this issue in the revision by breaking Eq. 30 into three separate lines to ensure it fits within the margins.

W6. Comparative upper bound results of re-training

"In Tables 2 to 5, the authors overlook an important comparative result: the performance of retraining a multi-dataset model that can jointly combine the expertise of both parent models."

Response: We appreciate the reviewer's constructive suggestion. Following the reviewer's advice, we conducted additional experiments by re-training a model using combined parent datasets with ground-truth labels. The results are presented below.

As the reviewer pointed out, these results can indeed establish an upper bound for GRAMA's performance. We will incorporate these results into Sect. 6 and provide the corresponding discussion in the revision.

---

W7. Experiments with additional splitting ratios

"It is also not very clear to me why the authors chose a 20%/80% splitting ratio in the experiments, as there are too few explanations about the splitting protocol. For example, is the split random? Would other splitting, such as 10/90, work for GRAMA?"

Response: We would like to thank the reviewer for the constructive comments. In fact, we have indeed addressed the choice of our dataset partition strategy in lines 299-302 of the main paper, following the well-established methodology of "Git Re-basin" by Ainsworth et al. [1], which involves random partitioning of the dataset.

Following the reviewer's suggestion, we conducted further experiments with an additional 90%/10% random split on the relatively large-scale ModelNet40 dataset, used for 3D object recognition tasks. The results, presented below, further substantiate the effectiveness of our proposed method.

---

W8. Constrained limitation discussions

"The current discussion of limitations in this paper appears somewhat constrained. The authors should consider expanding this section, either in the main body of the paper or in the appendix. An additional limitation to consider would be the scenario where two pre-trained models address tasks at different levels, such as node and graph-level tasks."

Response: The reviewer's point is well taken. Indeed, our current DuMCC framework does not accommodate scenarios where the parent models tackle tasks at different levels, a challenge that falls within the scope of heterogeneous GRAMA as outlined in W3. To address this, we will enhance our discussion on limitations by introducing a new Sect. G titled "Limitation Discussion" in the appendix. This section will offer a detailed analysis of this limitation and provide the corresponding potential solutions for such cases, as exemplified in W4.

---

W9. Typos

"Line 26: 'reduing' - 'reducing'; Line 106: 'presents' - 'present'; Line 193: 'are' - 'is'."

Response: We appreciate the reviewer's thorough examination of our paper. We will address these typographical errors in our revisions by correcting "reduing" to "reducing" in line 26, removing the extraneous "s" from "presents" in line 106, and adjusting "are" to "is" in line 193 to ensure grammatical correctness.

Response to Reviewer Uv5e (Part 1/2)

We truly appreciate the reviewer's insightful comments, and would like to address them as follows. Due to character limitations, we have to split our response into two parts. The second part will be provided as a comment following our initial response.

W1. Imbalanced organisation

"The current organization of the paper only allocates less than two pages to the experiment section, leaving many experimental details to the appendix."

Response: We appreciate the reviewer for the suggestion. Given the novelty of the studied GRAMA task and the sophisticated rationale behind the proposed DuMCC, our organisational approach was intended to provide detailed explanations, thus facilitating easier comprehension for the readers. These include:

• Sect. 3: Motivation, definition, and applications of the GRAMA task;
• Sect. 4.1: Vanilla solutions for the GRAMA task described in Sect. 3;
• Sect. 4.2: Challenges associated with the vanilla solutions from Sect. 4.1, leading to the motivations for our proposed DuMCC in Sect. 5;
• Sect. 5.1: An overview of our proposed DuMCC, motivated by the challenges outlined in Sect. 4.2;
• Sect. 5.2: The first component of DuMCC, PMC, including an analysis of its shortcomings, which subsequently motivates the introduction of CMC;
• Sect. 5.3: The second component of DuMCC, CMC, motivated by the findings in Sect. 5.2.

The sophisticated logic detailed above may require some pages to clarify potential confusion arising from our novel task and method. Admittedly, our preference for clarity, on the other hand, made us have to relocate some details to the appendix to adhere to page limits, exactly as the reviewer suggested.

In the revision, we will strive to achieve a better balance by incorporating as many details as possible within the scope of the additional content page allowed. Our detailed plan is as follows:

• Relocating portions of Sect. B and Sect. C to Sect. 6;
• Reorganising the architectural details in Sect. D into narrative texts and transferring the associated experimental details from Sect. D to Sect. 6.

---

W2. Limited connection between the main paper and the appendix

"The authors vaguely direct readers to Section D for further details, without specifying specific tables or paragraphs, which makes it hard to locate relevant information."

Response: We apologise for any inconvenience caused by the insufficient linkage between the main paper and the appendix, which may have extended the time required for reviewing our paper. Following the transfer of experimental details from the appendix to the main paper in W1, we will endeavour to enhance the connectivity of the remaining implementation details within the appendix to the main paper in our revision.

---

W3. Vague heterogeneous GRAMA descriptions

"The explanation regarding the heterogeneous GRAMA in Line 123 actually makes me confused. The statement is too vague. What exactly are the key differences between the homogeneous and heterogeneous cases of GRAMA?"

Response: We apologise for not having made our heterogeneous GRAMA clearer, which may have confused the reviewer. We would like to clarify that the heterogeneous case of GRAMA serves as a complementary extension to the proposed homogeneous GRAMA framework in our paper, where pre-trained parent models share similar architectures and purposes. We will explicitly highlight and detail this distinction in Sect. 3 of our revised version.

---

W4. Potential solutions for heterogeneous GRAMA

"The authors should at least provide some insights or potential solutions for solving heterogeneous GRAMA, or perhaps consider removing this statement of heterogeneous GRAMA since this is not the contribution of this paper."

Response: We appreciate the advice from the reviewer. A potential solution could involve Partial GRAMA, which entails first identifying shared features between two parent models that have different architectures or handle varied tasks. Subsequently, this possible method would yield a multi-head child GNN that selectively integrates elements of the pre-trained parent GNNs. Although this method would increase the model size compared to full GRAMA, which combines the entire models, it would be expected to offer a more favourable balance and trade-off between model size and performance. We will incorporate this discussion in the revised paper.

---

W5. Applying GRAMA to variants of GNNs

"I think it is at least worth a try to apply GRAMA to two different GNN variants, such as GCN and GraphSage, since the key learnable parameters in these GNNs are all MLPs."

Response: The reviewer's point is very well taken. Our immediate-next goal is, exactly as the reviewer suggested, to adapt our proposed method for cross-architecture model reuse scenarios, including the combination of GCN and GraphSAGE as outlined in lines 348-349 of our paper.

Here, to echo the reviewer's concern, we conducted a pilot study by performing additional experiments on GRAMA using both a GCN and a GraphSAGE model on non-overlapping partitions of the ogbn-arxiv dataset. These two parent models share a similar overall architecture but differ in their respective GCN and GraphSAGE layers. For the GraphSAGE model, we employed the official SAGEConv implementation from the Deep Graph Library (DGL), setting the 'aggregator_type' to 'gcn' for this preliminary study. This adjustment is due to the design of our homogeneous GRAMA, which requires alignment of parameters with the same shape and number. The results, as shown below, highlight the promising potential and feasibility of cross-architecture GRAMA applications.

Response to Reviewer 856w

We would like to thank the reviewer for the very helpful feedback. We will address each of the reviewer's comments in detail as follows.

W1. Inadequate literature review

"Discussions on existing model fusion approaches for CNNs are not adequate. The presentation will benefit from a more comprehensive literature review."

Response: We appreciate the reviewer for the advice. We will elaborate on the Model Merging section in Sect. 2 of the main paper's related work, and add a new section in Sect. E (extended related work) of the appendix to offer a more comprehensive discussion on existing model fusion techniques for CNNs and transformers. Specifically, we plan to broaden the discussions on model fusion for CNNs and transformers in the revision, covering, but not limited to, the following:

• Singh and Jaggi [r1] frame the task of one-shot neural network merging based purely on model weights as model fusion. They propose an Optimal Transport Fusion (OTFusion) method that uses the Wasserstein distance to align weight matrices prior to performing parameter fusion, eliminating the need for re-training;
• The subsequent work [r2] extends the application of OTFusion to Transformer-based architectures, aiming to enhance efficiency and performance through fusion;
• Liu et al. [r3] approach the challenging task of model fusion as a graph matching problem, incorporating second-order parameter similarities to improve the effectiveness of model fusion;
• Addressing the fusion of pre-trained models trained on disparate tasks, Stoica et al. [r4] develop ZipIt!, a novel method that utilises a "zip" operation for layer-wise fusion based on feature redundancy, creating a versatile multi-task model without additional training;
• More recently, Xu et al. [r5] present the Merging under Dual-Space Constraints (MuDSC) framework. This approach optimises permutation matrices by mitigating inconsistencies in unit matching across both weight and activation spaces, targeting effective model fusion in multi-task scenarios.

[r1] Singh and Jaggi. Model fusion via optimal transport. In NeurIPS, 2020.

[r2] Imfeld, et al. Transformer fusion with optimal transport. In ICLR, 2024.

[r3] Liu, et al. Deep neural network fusion via graph matching with applications to model ensemble and federated learning. In ICML, 2022.

[r4] Stoica, et al. Zipit! merging models from different tasks without training. In ICLR, 2024.

[r5] Xu, et al. Training-free pretrained model merging. In CVPR, 2024.

---

W2. Sensitivity analysis on $\alpha$

"Lack of sensitivity analysis on the interpolation coefficient alpha."

Response: We appreciate the reviewer's comments. In fact, the results of sensitivity analysis and the corresponding detailed discussions have already been reported in Sect. C of the appendix. We have also referenced these results of sensitivity analysis in line 292-293 of the main paper. We will further highlight these results in the revision.

---

W3. Experiments with more network architectures

"It seems that each task uses only one network architecture and dataset partition. More experiments are needed with more network architectures."

Response: We appreciate the constructive feedback from the reviewer. Following the suggestions provided, we conducted additional experiments with various network architectures and dataset splits on the large-scale ModelNet40 dataset. The results, along with detailed descriptions of the architectures used, are shown below. We will incorporate these results into the revised version of the paper.

---

W4. Additional applications

"It will be great to showcase more applications of the proposed approach besides training-free model reuse."

Response: We would like to thank the reviewer for the constructive comments. Here, we demonstrate an additional application of the proposed DuMCC beyond its primary role in training-free model reuse, specifically as a pre-processing step that facilitates more effective graph-based knowledge amalgamation (KA). In the table below, "KA" refers to re-training a student model from random initialisations by amalgamating knowledge from two teachers pre-trained on distinct partitions of the ModelNet40 dataset. "KA + GRAMA" denotes the process of performing KA by fine-tuning from the child model obtained via the proposed DuMCC method. The results indicate that "KA + GRAMA" leads to improved knowledge amalgamation performance. Additionally, since GRAMA provides a superior initialisation compared to random initialisation, "KA + GRAMA" empirically achieves faster convergence speed.

Response to Reviewer rPnJ (Part 1/2)

We appreciate the reviewer's constructive comments and thoughtful suggestions, and we sincerely apologise for any confusion or ambiguity caused by our use of notations.

We are committed to addressing each of the reviewer's concerns as outlined below. Due to character constraints, we have to divide our responses into two parts. The second part will be presented as a comment appended to our initial rebuttal.

Additionally, we warmly welcome any further questions or comments the reviewer may wish to share.

W1. Clarity on $\mathbf{P}$*

"After Eq 1: 'where $\mathbf{P}^*$ represents the permutation matrices' -- what does that mean? The expression $\mathbf{P}^*$ is not used in the Equation. I think it can imply one of two things. Option 1: $\mathbf{P}^* = \left[\mathbf{P}^{(\ell)}\right]_{\ell \in [L]}$ or Option 2: $\mathbf{P}^*$ refers to the space of permutation matrices (e.g., a reshuffle of the identity matrix or its continuous relaxation which is probably any basis?)

Response: We apologise for not having clearly defined the symbol $\mathbf{P}^*$, which may have led to confusion and inadvertently extended the review process. We appreciate the reviewer's patience and constructive comments. We would like to clarify that $\mathbf{P}^*$ denotes the set of all permutation matrices corresponding to each layer $\ell$ of the graph neural network (GNN), which is exactly Option 1 suggested by the reviewer.

We would like to further clarify that while $\mathbf{P}^*$ does not appear in Eq. 1, it is utilised in line 158, Eq. 3, Conjecture 4.1, and lines 208, 210, and 222. We intended to use this notation to simplify the discussions related to the collection of permutation matrices across different layers.

Admittedly, we sincerely apologise for the oversight in not explicitly linking Eq. 1 with $\mathbf{P}^*$ and for not adequately defining and elaborating on this symbol, which resulted in ambiguity. To address this issue, we will revise Eq. 1 in line with the reviewer's constructive suggestion and enhance the description of $\mathbf{P}^*$ in our revision by incorporating the following:

"$$ W^{(\ell)} = \alpha W_{a}^{(\ell)} + (1 - \alpha) P^{(\ell)} W_{b}^{(\ell)} (P^{(\ell-1)})^{T}, \quad P^{(\ell)} \in \mathbf{P}^*, \tag{1}

where $\mathbf{P}^* = \left[{P}^{(\ell)}\right]_{\ell \in [L]}$ represents the set of all permutation matrices $P^{(\ell)}$ for each layer $\ell$ of the graph neural network (GNN). Here, $[L]$ refers to the set of indices corresponding to all layers in the GNN." --- `W2.` **Issues on Eq. 3** `W2.1. & W2.2.` *Clarity on $i$ and "Agg"* >"Where does $i$ come from? do you mean to add $\sum_i$ between the $\arg \min$ and the Frobenius norm?" >"The aggregation function 'Agg' is not introduced. While the exact definition is unnecessary, however, the domain and range should be clearly specified. Does it take many vectors and output one vector? If yes, then $P \cdot \text{Agg}$ should be a vector and therefore you should be minimizing the L2 norm (not Frobenius norm). If it acts on the whole graph (i.e., Agg outputs a matrix with shape NumNodes $\times$ FeatureDim), then you are multiplying the permutation matrix from the wrong side." `Response:` We sincerely appreciate the reviewer's constructive feedback and apologise once again for the lack of clarity in our notations and the rigor of our equations. Since the issues concerning $i$ and $\text{Agg}$ are interrelated, we are combining our responses to W2.1 and W2.2 to address these two issues collectively. Originally, our intention was to use the symbol $i$ to universally represent the set of all nodes, rather than a single node. Consequently, $\text{Agg}$ was meant to act on the entire graph, outputting a matrix. Here, we would like to clarify that this output matrix was shaped as FeatureDim $\times$ NumNodes. This configuration was deliberately chosen to align with the conventions used in model merging within the Euclidean domain (e.g., Eq. 1 in [r1] and Eq. 13 in [r2], where the corresponding matrices are denoted as Dim $\times$ Num). This alignment was intended to facilitate a unified formulation and simplify conceptually intuitive comparisons across different domains. As a result, in our original Eq. 3, we multiplied the permutation matrix from the left side to match this dimension. This choice also explains our use of the Frobenius norm, as the operation is performed on the matrix. Admittedly, exactly as the reviewer kindly suggested, the definition and use of the symbol $i$ in this context lacks mathematical rigor, correctness, and explicitness, which subsequently led to confusion concerning $\text{Agg}$ and the Frobenius norm. We sincerely appreciate the reviewer's thorough advice on this issue. In our revision, we will address this issue by exactly following the reviewer's suggestion: defining $i$ as a single node identifier and introducing $\sum_i$ after $\arg \min$ to explicitly iterate over all nodes. This adjustment will result in the output of $\text{Agg}$ being a vector. Accordingly, we will replace the original Frobenius norm with the L2 norm to ensure consistency with these changes. We sincerely thank the reviewer once again for the insightful comments. We will revise Eq. 3 as described above, along with including the corresponding detailed descriptions for rigorous and explicit formulation and symbol definitions. Additionally, we will also update Eq. 3 in Alg. 1 accordingly. [r1] Ainsworth, et al. Git re-basin: Merging models modulo permutation symmetries. In ICLR, 2023. [r2] Li, et al. Deep model fusion: A survey. 2023.

W2.3(a) Clarity on $\mathbf{X}$s

"In general, where do the $\mathbf{X}$s come from? I was expecting data-independent scheme."

Response: The reviewer's point is very well taken. In our paper, we initially introduced a fully data-independent approach for GRAMA, referred to as the vanilla VAPI method, described in lines 158-161: "One possible data-independent solution is to minimise the L2 distance between the weight vectors of the pre-trained models by solving a sum of bilinear assignments problem, similar to weight matching techniques described in [1]."

However, as discussed in Sect. 4.2, our subsequent analysis reveals that GNNs are particularly sensitive to mismatches in parameter alignment, which are "contingent upon the topological characteristics inherent to each graph" (Conjecture 4.1). This sensitivity renders the data-independent solution less effective. Motivated by this, we propose integrating the topological characteristics inherent to each graph. To achieve this, we have to resort to passing the graph data to the pre-trained model to capture these graph-specific topological characteristics, utilising $\mathbf{X}$.

Nevertheless, we clarify that our PMC and CMC methodologies require only a single forward pass of the unlabelled graph data to extract messages for alignment and calibration, respectively—eliminating the need for iterative training or ground-truth labels. Our immediate-next goal is, exactly as the reviewer suggested, to explore the possibility of an entirely data-independent GRAMA scheme, for example, by initially generating fake graphs as described in [r3]. We will include these discussions in the revised version.

[r3] Deng and Zhang. Graph-free knowledge distillation for graph neural networks. In IJCAI, 2021

W2.3(b) Details of aligning

" In my reading, at this point, I think paper is 'learning to align' (because you are doing gradient descent on the permutation matrix by looping over data, no?)"

Response: We apologise for any confusion caused by our previous lack of clarity and the omission of essential details. We would like to clarify that our method does not employ gradient descent for alignment. In the field of model merging within the Euclidean domain, the minimisation problem in the form of Eq. 3 is typically transformed into a maximisation problem to maximise an inner product (as derived from expanding Eq. 3), thereby fitting it within the framework of a standard linear assignment problem [r1, r2, r3, r4]. In our revision, we will include these crucial details and introduce a preliminary section on Euclidean model merging to ensure our paper is self-contained.

[r1] Ainsworth, et al. Git re-basin: Merging models modulo permutation symmetries. In ICLR, 2023.

[r2] Li, et al. Deep model fusion: A survey. 2023.

[r3] Liu, et al. Deep neural network fusion via graph matching with applications to model ensemble and federated learning. In ICML, 2022.

[r4] Stoica, et al. Zipit! merging models from different tasks without training. In ICLR, 2024.

---

Q1. Model-specific variants of Eq. 2

"Does the exact form of Equation 2 depends on the architecture of the GNN model? I would expect to see different formulas depending on the model (e.g., GraphSAGE vs GCN of Kipf vs GAT vs MixHop etc)"

Response: We appreciate the constructive comments provided by the reviewer. To maintain clarity and simplicity, Eq. 2 in our paper is based on the most basic form of GNNs. Due to the short rebuttal period, we have only been able to develop specific formulas for GraphSAGE and Kipf's GCN as suggested by the reviewer. Our model formulation presented here follows the unified mathematical framework detailed in [r5], albeit with symbols adapted to those used in our paper. In the revised version, we are committed to developing more detailed, model-specific formulas.

(We apologise for having to split each of our equations below into two lines for display purposes, as OpenReview does not support single-line presentation of long equations.)

Eq. 2 tailored for GCN of Kipf is as follows:

$$\Delta F_i \approx \sigma'\left(W \sum_{j \in \mathcal{N}(i)} \frac{X_j}{\sqrt{\deg}_i \sqrt{\deg}_j}\right)$$ $$\cdot \left(\epsilon \sum_{j \in \mathcal{N}(i)} \frac{X_j}{\sqrt{\deg}_i \sqrt{\deg}_j}\right)$$

Eq. 2 tailored for GraphSAGE is as follows:

$$\Delta F_i \approx \sigma' \left(W \ \text{Concat}\left(X_i, \text{Mean}_{j \in \mathcal{N}(i)} X_j\right)\right)$$ $$\cdot \left(\epsilon \ \text{Concat}\left(X_i, \text{Mean}_{j \in \mathcal{N}(i)} X_j\right) \right)$$

[r5] Dwivedi, et al. Benchmarking graph neural networks. In JMLR, 2023.

---

L1. Limitations

"I did not spot a Limitations section."

We apologise for not making the limitations section more explicit in our paper. In fact, we have included a section on limitations in Sect. 7, titled "Conclusions and Limitations". We will highlight this section further in the introduction.