Partitioning Message Passing for Graph Fraud Detection

Q3: An analysis about the labeled neighborhoods’ label distributions of central nodes in the training dataset is necessary. This is crucial as the proposed method relies heavily on the labels of neighboring nodes. Furthermore, it is important to emphasize the ratio of normal nodes to anomaly nodes in the training data.

A3: Your suggestion is indeed crucial. Therefore, we present the label distributions of the labeled neighborhoods of the training nodes in the Appendix D.2 of the revised paper. Here, we present these distributions in it in tabular form. More details and distribution diagram can be found in the Appendix D.2.

To analyze the label distributions of the labeled neighborhoods of training nodes, we use $\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|}$ to represent the number of fraud neighbors relative to benign neighbors for a central node. $\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|} <1$ indicates that the number of labeled fraud neighbors is fewer than benign neighbors. Specifically, if $\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|} <0.5$, it indicates that the central node has far fewer fraud neighbors compared to benign ones, denoting a highly imbalanced neighborhood. Consequently, the smaller the value of $\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|}$, the more imbalanced the label distribution of neighbors of a given central node is. We use $|V_{\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|} < 1}|$ to represent the number of training center nodes with $\frac{|\mathcal{N}\_{fr}|}{|\mathcal{N}\_{be}|} < 1$, allowing us to assess the label distribution relative to this ratio.

Our results show that commonly used datasets such as Yelp, Amazon, and T-Finance suffer from significant label imbalance in the neighborhoods, which could lead to the general vanishing of the general GNN model with respect to the minority class neighbors, as we state in Section 2.2. Thus, since the model trained under the condition of imbalanced neighborhood label distribution, the ideal model needs to enhance the influence from the minority class neighbors on the center nodes. As demonstrated in Section 5.3, our PMP method effectively achieves this, enhancing the influence from minority class neighbors more efficiently than traditional GNN approaches.

Regarding your query about the ratio of normal to anomaly nodes in the training data, this ratio in the training set is the same as the ratio in the whole graph. Specifically, in the following table, we show the ratio of fraud nodes in the whole graph. For example, 14.53% of nodes in the Yelp are fraud nodes, so in the training set, the fraud nodes also occupy 14.53% of the training set.

Q4: Concerns have been raised about the correctness of equation (7).

A4: Based on your concerns, we re-examined the derivation process of Theorem 1 and equation (7). The proof of equation (7) is similar to the spectral analysis flow of traditional GCN, and the detailed proof can be found in Appendix B. We're sure it's correct.

We thank the reviewer for providing insightful and constructive comments. We address the reviewer's comments/concerns as follows.

Q1.1: The issues of label imbalance and homophily-heterophily have been effectively addressed in the past. Notably, Tang et al. [1] offered a theoretical explanation for these concerns using spectral graph analysis.

A1.1: In our opinion, BWGNN proposed by Tang et al. [1] aims to preserve or emphasize information from certain frequencies based on the PDF of Beta distribution, so BWGNN acts as a band-pass spectral graph filter, which has been proved effective for graph with heterophily. However, BWGNN does not specifically cater to the label imbalance challenge. There are two key reasons for this. Firstly, BWGNN use Beta wavelets as propagation matrix, which is predefined and only related to the graph Laplacian, thus the propagation matrix of BWGNN is label-agnostic. Secondly, the feature transformation matrices of BWGNN is uniformly shared across all nodes, so it is also label-agnostic. These two factors indicate that the training process of BWGNN does not explicitly account for the label imbalance inherent in certain graphs. The empirical evidence presented in Table 4 of Section 5.3 illustrates that our approach more effectively mitigates problems arising from label imbalance compared to BWGNN. This is achieved by investigating the influence distribution from neighbors on minority class nodes and tailoring the message passing process accordingly.

Q1.2：Building upon the findings of [1], this paper makes incremental enhancements in the field of fraud detection while questioning the complexity of earlier algorithms. Nonetheless, This paper does not provide comprehensive comparison of time and space complexities with previous works.

A1.2: We first show a detailed comparison of the time and space complexities in the following table (PC-GNN is built upon Care-GNN, and GHRN is an extension of BWGNN. They share similar complexity profiles with their respective base models), where $|E| \ll N^2$ is the number of edges, $d$ is the feature dimension and $C$ is the number of spectral filter in BWGNN. Usually, $N > |E|$, thus our model demonstrates optimal time and space complexities compared to these baselines. We have updated it in the Appendix A of the revised manuscript.

Besides, we would like to explain that our PMP is not built upon the findings of BWGNN. PMP and BWGNN have different motivation, methodology, and theoretical insights. So we think BWGNN cannot hide our contributions. The main differences between PMP and BWGNN are summarized as follows:

[Motivation] PMP is motivated by investigating the influence propagation during message passing (Section 2.2 in the updated version), which leads us to propose a fundamental principle for the successful application of GNNs in GFD: distinguishing between neighbors with different labels during the message passing. However, BWGNN is motivated by the 'right-shift' phenomenon of the spectral energy distribution, which inspires the BWGNN to define a band-pass graph filter based on beta wavelet.

[Methodology] （1）Label Utilization: PMP is spatial and label-aware, using distinct weight matrices for different labels. BWGNN, a spectral model, has shared, label-agnostic parameters.(2). Weight Matrix Design: PMP's weight matrices are root-specific (See Section 3), tailored for each node. BWGNN uses randomly initialized weights. (3) Unlabeled Nodes Handling: PMP treats unlabeled nodes as a mix of benign and fraud labels (See Section 3), while BWGNN treats all nodes uniformly, regardless of their labeled or unlabeled status.

Q2: The approach of treating fraud detection as a binary classification problem has inherent limitations. Real-world scenarios often involve anomalies that cannot be neatly classified into a single class and that do not adhere to clustering assumptions. Given the multitude of existing papers that have already presented effective solutions to address the challenges of imbalance and homophily-heterophily by binary classification algorithms, it raises questions about the need for publishing similar articles at the cutting-edge conference ICLR.

A2: We acknowledge that the binary classification framework has its limitations in capturing the full spectrum of real-world frauds. However, in real-world application, due to the large scale and strong heterogeneity of the network, we usually need to extract all potential fraud nodes first, and then do a more detailed classification and analysis of the extracted fraud nodes. Thus, modeling GFD problem as a binary classification is usually the first step. Besides, to our best knowledge, all the datasets publicly available and commonly used in research, including those we have utilized, are modeled for binary classification. This modeling choice reflects the practical realities of many real-world applications, where a binary approach remains a fundamental and highly effective method for initial fraud detection. We still greatly appreciate your valuable suggestion. Considering the current limitation of most works focusing on binary classification, we plan to explore the issue of multi-classification in our subsequent work.

Given the practical importance of graph fraud detection task, we agree that this problem has been studied in many past work. However, we do not think research in this area have converged because this problem is highly relevant to industrial applications. This requires that the model can capture the essence of the problem and be simple enough to make it easy to deploy in industrial environment. In our paper, we try to explore the key to solving this problem, rather than blindly designing complicated algorithms. Based on the motivation study, we propose that the key to successfully applying GNNs for GFD is to distinguish neighbors with different labels during message passing, instead of excluding heterophilic neighbors used in most prior work. Our proposed PMP is built upon this finding, and maintains simplicity to facilitate ease of deployment in industrial applications. To verify this point, in Appendix E.2 of our paper, we present experiments conducted on datasets provided by our industrial collaborators. These experiments demonstrate the applicability and effectiveness of our method in real-world industrial scenarios, affirming its practical relevance. Thus, we believe our paper offers valuable insights for future research in this domain.

We thank you for your time and effort in reviewing our paper. Below, we respond to address your concerns.

Q1: The primary innovation in the PMP method lies in the use of different weighting matrices for aggregating nodes of various classes. While effective, this focus may be perceived as lacking in breadth in terms of overall innovativeness.

A1: We understand that our embarrassingly simple model may give rise to concerns about its innovativeness. We respectfully argue that our work is novel, and we highlight our technical novelty as follows:

1. [High-level insight] We propose that the key to successfully applying GNNs for GFD relies not on excluding which used in most prior work, but on distinctly recognizing and processing neighbors with different labels during message passing. Thus, our approach is a fundamental departure from existing methodologies.

2. [Strong practical implications in applying GNN to GFD Applications] Graph fraud detection is a practical problem, especially in the industrial application. Thus, it is crucial to capture the essence of the problem, and design a simple and easy-to-deploy model. Our PMP method is designed with these requirements in mind. Through the motivation study, theoretical analysis and strong empirical results, we demonstrate PMP's effectiveness. The simplicity of our model does not diminish its impact; rather, it enhances its practical utility, making it a valuable tool in real-world applications.

While PMP's design is straightforward in form, it represents a meaningful step forward in the field, offering both a novel perspective and a practical solution. We believe that PMP has a certain guiding role in future work.

Q2: The article would benefit from a more meticulous attention to the use of symbols and language. Ensuring consistent and clear terminology and notation would contribute to the paper's readability and accessibility.

A2: Thanks for your valuable feedback. We have undertaken a thorough review of our manuscript with a focus on standardizing the terminology and symbols used throughout the paper. The modifications have been highlighted in blue in the resvised manuscript.

Q3: On Page 2, in the penultimate line of "where each node v_i is assigned a binary label $y_i\in Y$", please confirm whether it is "Y" or "fi"?

A3: In our paper, $\mathcal{Y} = \{y_1, y_2, \cdots, y_N\}$ represents the set of node labels, where $y_i \in \mathcal{Y}$ means the label of node $v_i$. $y_i$ has two possible values, i.e., $y_i = 1$ denotes $v_i$ is a fraud node $0$ denotes benign node.

Q4: In the description of Eq.(4) on page 4, it is mentioned that "In other words, a small $\alpha_i^{(l)}$ means that the model treats unlabeled neighbors more similarly to fraud nodes". In conjunction with Eq.(4), shouldn't it be the case that a smaller $\alpha_i^{(l)}$ makes unlabeled neighbors more biased to benign nodes?

A4: Thanks for pointing this out. Upon re-examination, we agree that there was an error in our description of how $\alpha^{(l)}\_{i}$ influences the treatment of unlabeled neighbors in our model. As you correctly noted, a small $\alpha^{(l)}\_{i}$ should indeed indicate that the model treats unlabeled neighbors more similarly to benign nodes due to the larger weight placed on $\mathbf{W}\_{\text{be}}^{(l)}$. We have corrected the text in the manuscript to accurately reflect this relationship.

Q5: Throughout the paper, sections 2, 3, and 7 are more similar to one part of the content, related work, could they be synthesized into one section?

A5: We agree your suggestion that enhances the readability. We have merged Sections 2, 3, and 7 into a single cohesive section titled "Background and Motivation" in new Section 2.

Q6: When introducing PMP, the article mentions the use of one layer of MLP in the generation of $\alpha^{(l)}_{i}$. Still, it does not note how many layers of MLP are used in the subsequent "Root-specific weight matrices generation".

A6: To maintain simplicity in the model design, we also apply the single-layer MLP in the "Root-specific weight matrices generation" to define the weight generators $\Psi_{\text{fr}}$ and $\Psi_{\text{be}}$. We have clarified this point in the revised manuscript. Moreover, we show influence of the number of MLP layers on the final results (AUC). We can find that the number of MLP layers does not drastically affect the performance of the model.

Q7: In the experimental results for the T-Social dataset, the AUC value is much higher than that of the comparative algorithm, close to 100%, is it possible to analyze the reason for this excellent result?

A7: Referring to Table 2, our PMP model shows substantial improvements compared to other baselines. Specifically, it surpasses the current state-of-the-art by 4.9% in AUC and achieves an 11.21% relative increase in Macro-F1 score.

We analyze the characteristics of the T-Social dataset. From the global perspective, as shown in Table 4, T-Social is an exceptionally large-scale dataset, having over 5 million nodes.This size is roughly 100 times greater than other datasets used in our study, presenting a unique scalability challenge for GNNs. Some baselines (Care-GNN, PC-GNN, H2-FDetector, GHRN) focus on augmenting graph structure by resampling neighbors, reweighting or pruning edges for each node to balance the message passing. However, given the immense size of T-Social, coupled with its diverse local patterns (where node degrees range from 1 to 3217), it becomes challenging to learn or define a general and shared strategy for local structure augmentation applicable to all nodes. Consequently, these models are less effective on large scale graphs. Differently, PMP and BWGNN do not make any assumptions about the local structure at the node level. They learn directly from the original graph without implementing any node-level augmentations. These approaches effectively alleviates the scalability challenges posed by the size and complexity of T-Social.

Then we would like to analyze the reason why PMP is better than BWGNN from the perspective of label imbalance. As shown in Table 4, T-Social exhibits a higher imbalance level, with only 3% of its nodes labeled as fraud. This leads to benign nodes overwhelmingly dominate the dataset, both in number and proportion. For BWGNN, the propagation matrix is predefined by Beta wavelet matrix, which is label-agnostic, and the feature transformation matrix is shared across all nodes, it leads to label imbalance knowledge can not be encoded into the model parameters during message passing. For our PMP, our model encode label information into the trainable parameter by utilizing distinct transformation matrices for different classes during the aggregation process, By processing nodes of different classes independently, the overfitting of the model to the class is alleviated. We believe that this is the key factor contributing to the excellent results achieved by our PMP.

Q8: In the last sentence of Section 5.4, "wherein each of these designs brings more than a 1% improvement across most metrics", does that mean that each approach delivers at least a 1% improvement over GraphSAGE, or does it mean that it provides a 1% improvement over the previous pivotal components? Please be as precise as possible.

A8: Thanks for pointing out our imprecise description. The "+partition" serves as the foundational element and is responsible for the major improvements observed, because it yields more than 3% improvement compared to GraphSAGE on most metrics. The subsequent components, "++adaptive combination" and "+++root-specific weights", are developed upon the "+partition" base. 1% improvement here means "++adaptive combination" and "+++root-specific weights" bring a cumulative improvement of more than 1% to "+partition". Both components provide useful contributions, but the amount of contribution provided by the two components differs depending on the datasets. For example, "++adaptive combination" bring a small improvement while "+++root-specific weights" provide more, such as in T-Finance dataset, while in Amazon dataset, "++adaptive combination" brings more improvement. We recognize that our initial expression in the paper might have been imprecise, and we have now amended as:

The "++adaptive combination", building upon the "+partition", brings incremental improvements across all datasets. The "+++root-specific weights", further extending the preceding component, enhances performance on most metrics in most datasets. Combined, these two components contribute to a cumulative improvement of more than 1% over the "+partition" baseline.

The modification has been marked as blue in Section 5.4 in the revised manuscript.

Dear Reviewer XqA8,

We appreciate your valuable feedback on our paper. With the discussion period nearing its end, we've compiled a succinct summary of our responses to your comments for ease of reference in your final evaluation:

Part 1: We highlight our contribution from the perspectives of high-level insight and practical value.

Part 2: The manuscript have been revised to ensure consistency and enhance its readability and accessibility.

Part 3: We have corrected an inaccurate description of $\alpha$.

Part 4: The sections of the paper have been reorganized based on your suggestions.

Part 5: We have added detailed hyperparameter settings.

Part 6: We analyzed the experimental results on T-Social datasets, and modified imprecise descriptions in the experiment analysis.

Warm regards,

The Authors of Submission 9114.

Q2: The strategy of partitioning message passing is very similar to GNNs with adaptive channel mixing used in [1] although [1] is from the spectral perspective. It will be interesting to discuss the differences and relationships between your proposed method and [1].

A2: Thanks for your suggestions, which inspire us to rethink our Partitioning Message Passing (PMP) and Adaptive Channel Mixing (ACM) [1]. We agree that our work does indeed share similarities with ACM. However, the motivation, methodology, theoretical insights still differ. We provide a detailed comparison from these perspectives as follows:

[Motivation] In our paper, we contend that the key to successfully applying GNNs for GFD task lies not in the exclusion of neighbors but in the ability to distinguish between them based on their labels during the neighborhood aggregation. This core belief is operationalized in our proposed PMP framework, which integrates this motivation into the traditional message passing paradigm. By partitioning neighbors during the aggregation phase using distinct transformation matrices, PMP effectively discriminates between different classes of neighbors, ensuring that the message passing mechanism is both simple and highly effective in addressing the unique challenges of GFD.

Contrastingly, ACM is motivated by the concept of "Diversification Distinguishability", which primarily involves attributing negative weights to heterophilic neighbors through a spectral synthesis of low-pass and high-pass filters. This technique fundamentally differs from our PMP. It is because the use of negative weights in ACM is indicative of removing (or subtracting) the heterophilc components from the homophilic neighbors. This can be interpreted as a form of information 'forgetting' where heterophilic features are de-emphasized in favor of homophilic features. It is different from PMP which preserves and utilizes all available information.

[Methodology] ACM is rooted in spectral graph theory, while PMP is spatially oriented. This difference is not just theoretical but has practical implications. The spectral nature of ACM inherently influences its scalability, particularly in the context of large graphs. Typically, spectral-based models, including ACM, require the entire graph as input, which can pose challenges for mini-batch training and thereby limit scalability. In contrast, our PMP model, with its spatial-based framework, inherently supports mini-batch training and is thus more adaptable to large-scale graphs. Furthermore, considering the application of ACM in GFD tasks, its formulation, with removed nonlinearity for simplicity's sake, can be expressed as $H_{**ACM**}^{(l+1)} = \alpha F_{L}\begin{bmatrix}H^{(l)}\_{fr} \\\ H^{(l)}\_{be} \\\ H^{(l)}\_{un}\end{bmatrix} W_{1}^{(l)} + \beta F_{H}\begin{bmatrix}H^{(l)}\_{fr} \\\ H^{(l)}\_{be} \\\ H^{(l)}\_{un}\end{bmatrix} W_{2}^{(l)}$ where $F_L$ and $F_H$ are distinct spectral filters. We can observation that the trainable weight matrix $W_{L}^{(l)}$ and $W_{H}^{(l)}$ are both shared across all nodes. In contrast, our PMP model, when represented in matrix form, can be rewritten as $H_{**PMP**}^{(l+1)} = F \begin{bmatrix}H^{(l)}\_{fr} W_1\\\ H^{(l)}\_{be} W_2 \\\ H^{(l)}\_{un} (\alpha W_1 + (1-\alpha)W_2)\end{bmatrix}$ where $F$ is the normalized adjacency matrix. Unlike ACM, trainable weight matrices in PMP, $W_1$ and $W_2$ , are specifically applied to nodes with different labels, where $W_1$ and $W_2$ captures the information of fraud nodes and benign nodes respectively, reflecting a more label-aware and adaptive approach to message passing in the context of GFD.

[Theoretical Insights] The theoretical insights of PMP and ACM reveal a significant divergence in their spectral capabilities, highlighting a fundamental difference in how they process graph signals. Specifically, ACM predominantly operates as a combination of low-pass and high-pass filters, which (de)emphasizing high or low frequency signal components can not control the information from other spectrum, i.e., ACM does not equate to the functionality of a band-pass filter. Differently, our theoretical analysis and visualization in Section.4 proves that our PMP operates as an adaptive graph filter which cover all frequencies in the spectral domain.

We also think such comparisons are very meaningful for a deeper understanding of our work, thus we include them in Appendix C of the revised manuscript.

Q3: A minor issue: repeated references 2nd and 3rd articles.

A3: Thank you for pointing out the repeated references. We have carefully reviewed the manuscript and rectified the referencing. This correction has been reflected in the revised manuscript.

We thank you for your time and effort in reviewing our paper. Below, we respond to address your concerns.

Q1: The relationships between heterophily and imbalance (which is specific in fraud detection) are not clear. This is important to understand the problem.

A1: In the context of network fraud detection, attackers strategically inject fraud nodes sparsely within benign communities to camouflage fraudulent activities and spread their influence to normal nodes. As a result, these fraud nodes frequently establish connections with benign nodes, leading to a network characterized by heterophily -- where connections are predominantly between nodes with dissimilar labels (i.e., fraud nodes connecting with benign nodes). In the Table 5 of Appendix D.1, we show the heterophily level with measure $\hat{\eta}$ of real-world datasets , which clearly demonstrate the heterophilic nature of such networks.

Furthermore, the injection of fraud nodes into the network is deliberately kept to a minimum to conceal their fraudulent activities. This results in a significantly smaller population of fraud nodes compared to benign ones, thus engendering a label imbalance in the fraud graph. As evidenced in Table 5 of Appendix D.1, less than 10% of nodes in commonly used datasets are labeled as fraud nodes. Here we show the statistical data of the benchmark datasets as follows:

Overall, such a sparse distribution of fraud nodes not only confirms the label imbalance but also contributes to the network's heterophilic characteristics. Such interplay of heterophily and label imbalance in fraud graphs provides a unique challenge for GNNs.

Dear Reviewer 8onS,

Thank you again for your thoughtful feedback on our submission. As the discussion period draws to a close, we have prepared a brief summary below that encapsulates our responses to your points for your convenience in the final review:

Part 1: We have explained the relationship between homophily and label imbalance under the fraud detection task.

Part 2: We have provided a detailed comparison between PMP and ACM from the perspectives of motivation, methodology, theoretical insights.

Part 3: We have corrected the repeated references.

Warm regards,

The Authors of Submission 9114.

We appreciate your detailed suggestions for our work. We provide the response to your concerns point by point as follows:

Q1: It would be easier for a reader to follow if the same notation would not be used for different purposes. $h$ (page 15) - class homophily metric $h_{i}^{(l)}$ (page 3) - $l$-th layer hidden representation of $v_i$.

A1: Thank you for pointing out the confusion caused by the overlapping use of the notation $h$. To address this, we have revised the notation to eliminate any ambiguity. The class homophily metric previously denoted by $h$ on page 15 will now be denoted by $\eta$ throughout the paper. We have marked these changes in blue in the revised manuscript.

Q2: On page 4, equation 4: Shouldn't a small $\alpha^{(l)}\_{i}$ indicate that the model should treat unlabeled neighbors more similarly to benign nodes (instead of fraud nodes as written in the paper)?

A2: Thank you for pointing out the inconsistency regarding the interpretation of the parameter $\alpha^{(l)}\_{i}$ in equation 4 on page 4. Upon re-examination, we agree that there was an error in our description of how $\alpha^{(l)}\_{i}$ influences the treatment of unlabeled neighbors in our model.

As you correctly noted, a small $\alpha^{(l)}\_{i}$ should indeed indicate that the model treats unlabeled neighbors more similarly to benign nodes due to the larger weight placed on $\mathbf{W}\_{\text{be}}^{(l)}$. We have corrected the text in the manuscript to accurately reflect this relationship.

Q3: On Figure 4 (page 8): Influence distribution: why GCN (and not R-GCN) was chosen as one of the methods for comparison? My understanding is that GCN cannot distinguish between diffenent relations and both Yelp and Amazon datasets include multiple relationship types. May be that is why GCN did better at T-Finance (with only one relation type)

A3: Thanks for your deep insights. Our aim is to provide a comprehensive comparison across a spectrum of GNNs, ranging from the most basic GCN to the more advanced and fraud-specific model, BWGNN. These methods are selected as the most representative baselines for different classes of GNNs. We agree that the Yelp and Amazon datasets contain multiple relationship types and that GCN’s inability to differentiate between these may impact its performance. In the single-relational dataset T-Finance, the disadvantages of GCN are reduced because other methods no longer have the advantage of handling multiple relations, which is a logical result.

We appreciate the suggestion that including R-GCN, which is designed to handle multiple types of relationships, could provide a more direct comparison for datasets with such complexity. To address this, we have conducted additional experiments with R-GCN, which we have included in the Appendix E.3 of the revised manuscript. From the extended experiments with R-GCN in Appendix E.3, we include R-GCN due to its ability to handle multiple types of relationships within a graph. R-GCN extends the GCN model to account for different types of relations in the graph. Results illustrate the influence distributions for the multi-relational Yelp and Amazon datasets. It is evident that accounting for multiple relationships results in a rightward (positive) shift in the influence distributions.

Dear Reviewer 69ev,

Thank you once again for your insightful feedback on our submission. We would like to remind you that the discussion period is concluding. To facilitate your review, we have provided a concise summary below, outlining our responses to each of your concerns:

Part 1: We have carefully checked the manuscript to ensure that all notations are now distinct and consistently applied throughout the paper.

Part 2: We have corrected an inaccurate description of $\alpha$.

Part 3: We compare our model with R-GCN and analyze their relationships.

Warm regards,

The Authors of Submission 9114.