Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations

Authors: H. Çağrı Bilgi, Lydia Y. Chen, Kubilay Atasu
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, multigraph, message passing, financial fraud detection

Abstract:
Graph Neural Networks (GNNs) have seen significant advances in recent years, yet their application to multigraphs, where parallel edges exist between the same pair of nodes, remains under-explored. Standard GNNs, designed for simple graphs, compute node representations by combining all connected edges at once, without distinguishing between edges from different neighbors. There are some GNN architectures proposed specifically for multigraph tasks, yet these architectures perform only node-level aggregation in their message-passing layers, which limits their expressive power. Furthermore, these approaches either lack permutation equivariance when a strict total edge ordering is absent, or fail to preserve the topological structure of the multigraph. To address all these shortcomings, we propose MEGA-GNN, a unified framework for message passing on multigraphs that can effectively perform diverse graph learning tasks. Our approach introduces a two-stage aggregation process in the message passing layers: first, parallel edges are aggregated, followed by a node-level aggregation that operates on aggregated messages from distinct neighbors. We show that MEGA-GNN supports permutation equivariance and invariance properties. We also show that MEGA-GNN is universal given a strict total order on the edges. Experiments on synthetic and real-world financial transaction datasets demonstrate that MEGA-GNN either significantly outperforms or is on par with the accuracy of state-of-the-art solutions.

Decision: reject
Reviewer scores: 3, 6, 6, 3

Reviews and discussion:
<thread>
creation date:
1730213625626

thread_type:
official_review

<thread_object>
creator: reviewer_euww

<content>
summary:
This paper proposes a novel message-passing procedure on multigraphs. By first aggregating all edge states between two nodes, and using those as messages for MPNNs, a permutation equivariant method is constructed. The effectiveness of the proposed method is shown on several edge classification and one node classification task.

strengths:
I like the proposed method. It is intuitive, simple and effective. The paper is nicely written and mostly easily to follow and sufficiently detailed described.

weaknesses:
W1 Theorem 3.1: All MPNNs are permutation equivariant, as they do not use indices directly. I do not understand the need to specifically point this out. 

W2 Corollary 3.1: This statement is false the way it is stated. First, you need f, g_v, and g_e to be injective as well. Lemma 5 of Xu et al. also only holds for functions over countable multisets, which is ignored in this statement. In fact, if you follow Lemma 5 of Xu et al., there needs to be an additional function that is applied before EdgeAgg for possible injectivity.

W3 Theorem 3.2: It should be clearly defined what the authors mean with universality. If a consistent ordering of the edges is given, permutation equivariance is lost. I find the claim that "our method is universal and capable of detecting any directed subgraph pattern in multigraphs" to be strongly misleading. How to construct a consistent ordering is not discussed and from my understanding not used for the experiments. Therefore, the point of this theoretical statement is unclear to me.

W4: Eq. 4 computes h^(l) but Eqs. 5,6 use h^(l-1). Is this intended?

W5: The introduced artificial nodes are not used in the proposed method. States are only computed for edges and nodes, but not for the artificial ones. Discarding the artificial nodes would make the framework much cleaner. 

W6 Experiments: 
* The baseline results seem to be reused from previous methods. It is unclear whether the same dataset splits were used, the same number of parameters, and the same hyperparameter search space.
* There are no ablation studies. For example, to better understand this method it would be nice to see how results would change if there was a single edge state between two nodes instead of having multiple edge states.

questions:
* l. 376: What does GIN aggregation mean? GIN uses sum aggregation + an MLP.
* MEGA-GNN seems to require a single vector of edge features, independently of the number of edges between two nodes. From my understanding all edge between two nodes would be equal if there are no initial edge features for each edge. This seems to a large constraint and it is not discussed in the experiments. Are these given for all datasets? Are baseline methods utilizing those as well?
* see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730589621752

thread_type:
official_review

<thread_object>
creator: reviewer_xlvr

<content>
summary:
The authors introduce MEGA-GNN, a message-passing framework for multigraphs—graphs where multiple parallel edges can exist between the same pair of nodes. Traditional GNNs are not well-suited for multigraphs due to their single-stage node-level aggregation. 

MEGA-GNN addresses this limitation by implementing a two-stage aggregation process: first, it aggregates parallel edges between the same nodes, and then it performs node-level aggregation on the aggregated messages from distinct neighbors. The authors give theoretical proofs that MEGA-GNN supports permutation equivariance, injectivity, and universality under specifi conditions. 

Experimental results on synthetic and financial transaction datasets demonstrate that MEGA-GNN either outperforms or matches the accuracy of state-of-the-art models.

strengths:
1. MEGA-GNN gives a solution to a gap of GNNs' effecitveness, by focusing on multigraphs rather than simple graphs, where multiple edges between nodes could be useful for many applications, such as financial fraud detection (as benchmarked in the paper).

2. The authors theoretically validate MEGA-GNN’s permutation equivariance, injectivity, and universality properties.

3. MEGA-GNN achieves state-of-the-art or comparable performance across various (synthetic and real-world0 datasets, particularly in edge and node classification tasks.

weaknesses:
1. The proof for the universality property assumes that there is an ordering over the edges of the multigraph. This is not always the case for real-world setups, giving a small question-mark on what happens when the edge ordering is not consistent.

2. Although I find the utilization of financial transaction datasets quite interesting, I think it's not very diverse. I'd be very interested in seeing whether such a multigraph approach can be useful in other domains (e.g. knowledge graphs could potentially be of relevance due to the variety and number of different relations that can occur between identical pairs of nodes. For example, biomedical knwoeldge graphs could a potential use). 

3. The method requires the addition of artificial nodes, and the two-stage aggregation. This hints a computational overhead that is not discussed in the paper, and how it'd affect message passing in large/dense graphs.

questions:
1. How does MEGA-GNN scale with larger, more complex multigraphs, and what are the computational costs with the two-stage aggregation process?

2. Is it possible to relax the assumption of consistent edge ordering, and if so, how would that impact the theoretic properties of MEGA-GNN?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709156434

thread_type:
official_review

<thread_object>
creator: reviewer_74yn

<content>
summary:
The paper introduces MEGA-GNN, a novel message-passing framework tailored for multigraphs—graphs that include multiple parallel edges between node pairs. Unlike standard GNNs that aggregate all edges at once, MEGA-GNN introduces a two-stage aggregation strategy: Parallel Edge Aggregation and Node-Level Aggregation. The authors demonstrate the permutation equivariance and invariance of the proposed model and show that it is universal when the edges are consistently ordered.

strengths:
- The paper is clearly written and easy to follow with various figures demonstrating the ideas in the paper.
- Novel Aggregation Mechanism: The two-stage approach addresses the limitation of traditional GNNs, enhancing expressivity by first aggregating parallel edges and then aggregating at the node level.
- The paper provides proofs for permutation equivariance, injectivity, and universality.
- Experimental Evaluation: The proposed method shows promising improvements in the included datasets.
- The code is included in the supplementary material.

weaknesses:
1- Scalability: Although multigraphs are well-suited to some applications, real-world graphs can be vast in scale. The two-stage aggregation with artificial nodes might pose computational challenges and memory overhead for large, densely connected multigraphs. Some discussion on scalability in practical settings or optimizations for large-scale data would be appreciated.

2- The paper shows that under a consistent ordering of edges the model is universal. However, for many real work scenarios, this is not always feasible, especially in dynamic setting. Have authors considered dynamically evolving multigraph setting?

3- The experiments are limited to financial datasets and lack diversity in application areas, which might constrain the broader applicability of MEGA-GNN. I am not familiar with the multi-graph learning literature but are there other domains you can explore?

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731094879529

thread_type:
official_review

<thread_object>
creator: reviewer_q2cp

<content>
summary:
This paper studies neural architecture for learning on multigraphs. Existing methods either reduce to simple graphs or break properties such as permutation equivariance. A two-stage message-passing framework is proposed by introducing artificial nodes for parallel edges that preserves several desirable properties. The proposed MEGA-GNN is evaluated on synthetic and real-world financial transaction datasets and shows better or comparable performance compared to SoTA methods.

strengths:
- The use of two-stage aggregation and artificial nodes can effectively address the limitations of existing GNN models to capture information across parallel edges while preserving certain properties.

- The MEGA-GNN framework shows good flexibility and performance in applications on financial transaction datasets.

- The authors offer in-depth analysis and jusfiication for the proposed framework regarding properties of permutation equivariance, injectivity and universality.

weaknesses:
- The techniques used in MEGA-GNN such as bi-directional message passing and multi-stage aggregation are already well established, and the technical challenges for multi-graph have also been largely addressed by hypergraph learning research, which limits the overall novelty.

- The model is only evaluated on financial datasets, which raise questions about wheter multi-graph learning is applicabile for broad scenarios. 

- Some choices, such as specific aggregation functions and the role of artificial nodes, lack detailed justification.

Feng, Yifan, et al. "Hypergraph neural networks." AAAI’19  
Gao, Yue, et al. "Hypergraph learning: Methods and practices." TPAMI’2020.

questions:
- Q1 In practice, is permutation equivariance indeed needed for multi-graph applications? Based on results from Tables 2 amd 3, Multi-GNN without this property is a very strong baseline, especially for the node classification task.

- Q2 What aggregation functions (EdgeAgg in Eqs 4, 8, AGG in Eqs 5,9) are used for the results reported in Tables 2 and 3?

- Q3 Could the authors include ablation studies to highlight the contribution of Ego-IDs? Comparsion with other baselines without node labelling seems unfair.

You, Jiaxuan, et al. "Identity-aware graph neural networks." AAAI'21
</content>
</thread_object>

</thread>
<thread>
creation date:
1732750495712

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Revisions

comment:
Dear reviewers,

Thank you for your feedback and suggestions. We have significantly revised our submission based on your comments. We have made the following important changes in our revised submission:

**Section 3.2**
- We have improved our notation to fully explain the way multigraph edge features are used both by standard GNNs and our multigraph GNNs.
- We have included formal definitions of universality, permutation equivariance, and strict total order.

**Sections 3.3 and 3.4**
- We have updated these sections to use the new notation in addition to simplifying their description.

**Section 3.5**
- We have significantly re-written this section to better explain our motivation for such a theoretical analysis and the most important insights we have derived:
- Both MEGA-GNN and Multi-GNN are permutation equivariant and universal when there is a strict total ordering of the edges.
- When such an ordering is not available, 1) MEGA-GNN is permutation equivariant but non-universal, and 2) Multi-GNN is universal but not permutation equivariant.

**Section 4.3**
- This is a new section that includes ablation studies of MEGA-GNN as well as inference throughput comparisons with the state-of-the-art baseline (Multi-GNN)
- The ablation studies show that the single most important factor contributing to MEGA-GNN’s high accuracy is the two-stage edge-aggregation mechanism taking place in MEGA-GNN’s message passing layers. Bi-directional message passing enables more moderate accuracy gains, and EGO-IDs do not lead to any consistent accuracy improvements.
- Even the most basic MEGA-GNN variant is significantly more accurate than ADAMM, proving the importance of performing multi-edge aggregations within the message passing layers rather than applying only a single multi-edge aggregation in a pre-embedding layer.
- Our throughput analysis shows that MEGA-GNN is only slightly slower than Multi-GNN. Furthermore, MEGA-GNN becomes significantly faster when bi-directional message passing is disabled.

**Section 5**
- We have included a new paragraph at the end of this section to discuss the relationships and differences between our work, hypergraph GNNs, and relational GNNs.

**Appendix D**
- We have added a brand new Appendix D Section that covers the computational and memory overheads of supporting multi-edge aggregations as well as some performance optimisation opportunities.

**Appendix E**
- We have added Appendix E, which includes additional experiments conducted on the baseline method, Multi-GNN. Specifically, we investigate the impact of edge permutations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733227360724

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final remarks

comment:
Dear reviewers,

Thank you again for all your constructive comments.

In your final evaluations, we would be glad if you could take into account our revisions as well as our following significant results:
- On IBM's extremely imbalanced Anti-Money Laundering datasets, our MEGA-GNNs outperform the state-of-the-art multi-graph neural network solution (Multi-GNN) by up to 13% in terms of the minority class F1 score. 
- On a real-world phishing classification dataset, our MEGA-GNNs outperform the only other permutation-invariant multi-graph GNN model (ADAMM) by 30%.
- Our MEGA-GNNs are not only permutation invariant, but also universal when the graph edges are contextually (e.g., temporally) ordered.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**(a) Scientific Claims and Findings:**
The paper introduces MEGA-GNN, a novel framework designed to enhance Graph Neural Networks (GNNs) for multigraphs—graphs that permit multiple parallel edges between node pairs. Traditional GNNs often aggregate messages from all connected edges simultaneously, potentially overlooking the distinct contributions of parallel edges. MEGA-GNN addresses this by implementing a two-stage aggregation process: initially aggregating messages from parallel edges, followed by node-level aggregation from distinct neighbors. This design ensures permutation equivariance and invariance, maintaining the multigraph's topological structure. The authors demonstrate that MEGA-GNN achieves universality given a strict total order on edges. Empirical evaluations on synthetic and real-world financial transaction datasets indicate that MEGA-GNN either outperforms or matches the accuracy of current state-of-the-art models.

**(b) Strengths:**
* Innovative Aggregation Mechanism: MEGA-GNN's two-stage aggregation process effectively distinguishes between parallel edges and distinct neighbors, enhancing the expressive power of GNNs in multigraph contexts.
* Theoretical Guarantees: The framework upholds permutation equivariance and invariance properties, ensuring consistent performance across varying multigraph structures.
* Empirical Performance: The model demonstrates superior or comparable accuracy to existing solutions on both synthetic and real-world datasets, particularly in financial fraud detection scenarios.

**(c) Weaknesses:**
* Scalability Concerns: The paper lacks a comprehensive analysis of MEGA-GNN's scalability, especially when applied to large-scale multigraphs prevalent in practical applications.
* Computational Complexity: The introduction of a bi-directional multi-edge aggregation mechanism may increase computational demands, potentially limiting the model's efficiency in large datasets.
* Generality of Applicability: While the model excels in financial transaction datasets, its performance across diverse domains remains unexplored, raising questions about its generalizability.

**(d) Reasons for Rejection:**
After careful consideration, the decision to reject the paper is based on the following factors:
1. Insufficient Scalability Analysis: While a new appendix section (D) has been added during the rebuttal to provide a theoretical analysis of the algorithms complexity, no run-time tables were provided. This leaves uncertainty regarding MEGA-GNN's applicability to large-scale multigraphs.
2. Potential Computational Overhead: The increased complexity introduced by the bi-directional multi-edge aggregation mechanism may hinder the model's efficiency, especially in extensive datasets, without sufficient justification or optimization strategies.
3. Limited Domain Evaluation: The model's evaluation is primarily confined to financial transaction datasets, lacking evidence of its effectiveness across a broader range of applications, which limits the assessment of its generalizability.
Addressing these concerns through comprehensive scalability analyses, optimization of computational efficiency, and validation across diverse domains would significantly strengthen the paper's contributions and its potential for acceptance in future submissions.