Unsupervised Federated Graph Matching with Graphlet Feature Extraction and Separate Trust Region

We thank this reviewer for the great suggestion!

Weakness 1: Despite the promising result, I have some questions regarding the fundamental assumption of this paper. The assumption is that, nodes across networks with similar graphlet degree vectors are likely to be the same nodes. However, as graph structures are different in different networks, it may well happen that a node's structure changes a lot, e.g. an author who changes his main research focus. Thus, I would like to know how accurate the assumption is. Maybe the authors can provide some numbers to show.

Answer: Thanks for the constructive comments. A graphlet is a small graph of size up to $k$ nodes of a larger graph, such as triangle, wedge, or $k$-clique, which describes the local topology of a larger graph. A node's local topology can be measured by a graphlet feature vector, where each component denotes the frequency of one type of graphlets. Thus, a graphlet feature vector is one of node structure representation (Shervashidze et al., 2009; Kondor et al., 2009; Soufiani & Airoldi, 2012; Jin et al., 2018; Tu et al., 2019). Based on structure, attribute, or embedding features, existing graph matching efforts often choose the node pairs with the smallest distances or largest similarities across the graphs are selected as the matching results (Man et al., 2016; Zhou et al., 2018a; Yasar & Catalyurek, 2018; Li et al., 2019b;a; Chu et al., 2019; Fey et al., 2020). This submission just follows this mainstream strategy for structure-based graph matching to conduct graph matching based on the graphlet features. This work explores a general solution of federated graph matching for addressing the most common graph matching question: structure-based graph matching without considering other types of features.

For the case of the graphs with quite different structures, a popular method is to combine other types of features to alleviate the structure inconsistency issue, say attribute-based graph matching. When other types of features are similar with only dissimilar structure, it is still possible that two copies of the same nodes in different graphs are still most similar to each other and can be identified as the matching results, as long as more other features are integrated or by reducing the weight of structure features.

Weakness 2 / Question 2: I wonder whether a split-learning technique can achieve the goal of the separate trust region algorithm. From my understanding, the separate trust region algorithm is designed so that the pseudo matchings are kept at servers and not exposed to clients. This may well be achieved with some kind of split learning, where clients maintain their graph feature encoders, and a matching unit is trained at the server with the pseudo labels. In this case, there would be even no requirement of the Hessian matrices. Can the authors justify the necessity of using the separate trust region algorithm and the Hessian?

How necessary is the Hessian matrix? What if we use some sort of split learning?

Answer: Thanks for the kind suggestion. The time complexity of multiple graph matching typically increases exponentially with the number of graphs to be matched. If we choose to conduct both evaluation and optimization of the graph matching model at the server, then the computational capability of each client are idle. This will dramatically degrade the algorithm efficiency, especially large-scale graph matching is often time-consuming.

Thus, we separate model optimization from model evaluation in the trust region algorithm: (1) the server aggregates the local model parameter on each client into a global model parameter, runs and evaluates the global parameter, and computes the individual loss and the first-order gradient for each client; (2) each client computes the second-order Hessian and optimizes the local model. The reason of using the second-order Hessian in the trust region algorithm is that the second-order Hessian can provide fast convergence in terms of number of training steps. The second-order Hessian computation and the local model optimization are most compute-intensive over large graphs. Thus, we move these two operations to the clients for making full use of the computational capability of each client to improve the efficiency, while maintaining the privacy constraints.

I have read the author response and find that they provide necessary information for me to answer my questions.

I find that most of my questions are well answered. I am willing to recommend a weak accept at this point.

I am still not fully convinced that split learning cannot do the job. As the authors say, the proposed method can utilize client side computation resources, but in the meantime, extra computation of Hessian is involved. Thus I still think that a well-designed split learning can achieve the goal without needing to compute Hessian. Yet this is just a minor question about the design choice, rather than the method itself.

We thank this reviewer for the encouraging comments. We are delighted to hear your positive comments on our contribution to the valuable research problem with significant real-world applications, such as financial crime detection, and the technical novelties in the FGM. The core requirement of FL is the privacy protection. The paper proposed model graphlet feature extraction and separate trust region optimization and combine two techniques into a unified UFGM model. The proposed method capture nodes' graphlet features to generate pseudo matched node pairs on different graphs across clients as the pseudo training data for leveraging the strength of supervised graph matching for improving the algorithm effectiveness. On the other hand, the combination of the unsupervised FGM and the encryption of local raw graph data is able to provide strong privacy protection for sensitive local data. In addition, the separate trust region for pseudo supervised FGM is helpful to enhance the efficiency while maintaining the privacy constraints.

Weakness 1: The scale of the experiment is a bit small. What will the performance look like on large-scale dataset?

Answer: Thanks for your great comments. In the appendix, in order to validate the scalability of our UFGM method for the problem of unsupervised federated graph matching on large-scale datasets, we selected and split the original DBLP dataset into 20 graphs by publication year, ranging from 2002-2022, such that each graph has around 100,000 and 200,000 authors as nodes and coauthor relationships as edges respectively. We have reported the $Hits@K$ scores in Table 5. The experiment results exhibit that our UFGM method scales well on different datasets . This demonstrates that our UFGM method is scalable for addressing the problem of unsupervised federated graph matching, while maintaining the privacy requirement of FL.

Weakness 2: Another concern is the benchmark comparison. Authors claim it is the first algorithm for federate graph matching, so it is better to emphasize how innovative compared with peer works.

Answer: Graph matching (i.e., network alignment) is one of the most important research topics in the graph domain, which aims to match the same entities (i.e., nodes) across two or more graphs. There is still a paucity of techniques of effective federated graph matching (FGM), which is much more difficult to study and has many real applications, such as user account linking in different social networks and financial crime detection. However, directly sharing and inferring matched node pairs on different graphs across clients and local graphs over multiple clients gives rise to a serious privacy leakage concern, which is the motivation of this work, compared with centralized graph matching methods.

To our best knowledge, this work is the first to offer an unsupervised federated graph matching solution for inferring matched node pairs on different graphs across clients while maintaining the privacy requirement of FL, by leveraging the graphlet theory and trust region optimization. Our UFGM method exhibits three compelling advantages: (1) The combination of the unsupervised FGM and the encryption of local raw graph data is able to provide strong privacy protection for sensitive local data; (2) The graphlet feature extraction can leverage the strength of supervised graph matching with the pseudo training data for improving the matching quality; and (3) The separate trust region for pseudo supervised FGM is helpful to enhance the efficiency while maintaining the privacy constraints.

We thank this reviewer for the constructive comments.

Weakness 1: The challenges and applications of applying federated training on unsupervised graph matching are not clear.

Answer: Thanks for the thoughtful comment. Since FedAvg was proposed by Google in 2017 [1], federated learning (FL) has been a hot research topic in the field of machine learning. With the increasing regulation restrictions, user concerns, and commercial competition, the government agencies limit data collection and the users are not willing to share the data. The original intention of FL proposed by Google is to reduce privacy and security risks by limiting the attack surface to only the device, rather than the device and the cloud [1]. Federated graph learning (FGL) has led to state-of-the-art innovations in various applications, such as node classification, graph classification, network embedding, and link prediction. There is still a paucity of techniques of effective federated graph matching (FGM), which is much more difficult to study.

A good real-world application of FGM is that financial crime detection on transaction networks with millions to billions of bank customers and transactions [2-4]. Data exchange among clients and server about sensitive bank customer and transfer data should be limited for privacy risks. Especially, US and UK governments launched a privacy-enhancing technology (PET) challenge about federated learning for financial crime detection in July 2022 [5,6]. The dataset contains SWIFT transfer data between bank accounts and individual bank account transaction data. Frequent interbank transactions between the same or affiliated entities may be potential money laundering activities. Another real application is user account linking in different networks, since the user information contain many sensitive information. Directly collecting and uploading the raw user data to the server for centralized graph matching (CGM) gives rise to a serious privacy concern.

[1] Communication-Efficient Learning of Deep Networks from Decentralized Data. AISTATS 2017.

[2] Towards federated graph learning for collaborative financial crimes detection. CoRR, abs/1909.12946, 2019.

[3] A semi-supervised graph attentive network for financial fraud detection. ICDM 2019.

[4] Federated graph learning - A position paper. CoRR, abs/2105.11099, 2021.

[5] https://research.ibm.com/blog/privacy-preserving-federated-learning-finance

[6] https://www.drivendata.org/competitions/group/nist-federated-learning/

The unsupervised graph matching fails to employ the strength of training data and thus often leads to sub-optimal solutions, compared with supervised graph matching. However, the latter using the pre-matched node pairs as the training data is improper for the FGM scenarios due to privacy risks of direct cross-graph information exchange.

Thus, we propose to capture nodes' graphlet features to generate pseudo matched node pairs on different graphs across clients as the pseudo training data for leveraging the strength of supervised graph matching and improving the quality of unsupervised graph matching. However, graphlet enumeration one by one on large graphs is impossible due to expensive cost. We propose to leverage Monte Carlo Markov Chain (MCMC) technique for sampling a small number of graphlets.

Stochastic gradient descent (SGD) optimization widely used in deep learning fails to work on the clients in the FGM, since each client can access only its own local graph data and thus cannot update local loss based on the pseudo matched node pairs. We propose a separate trust region algorithm for pseudo supervised FGM while maintaining the privacy constraints. We separate model optimization from model evaluation in the trust region algorithm: (1) the server aggregates the local model parameter on each client into a global model parameter, runs and evaluates the global parameter, and computes the individual loss and the first-order gradient for each client; (2) each client computes the second-order Hessian and optimizes the local model.

Thanks for the consideration of our comments!

In previous versions of the submission, we use federated graph learning baselines to describe FedGraphNN, FKGE, SpreadGNN, SFL, FederatedScope-GNN, and FedStar, instead of term federated graph matching. Since these federated graph learning baselines are originally designed to address other graph learning tasks, such as node classification, graph classification, and network embedding., our UFGM achieves better performance than these federated graph learning baselines.

In the current version of the submission, we have re-drawn Figures 1-8, updated Tables 1-3, and 6, and modified the corresponding descriptions to remove all experiment results of these federated graph learning baselines and all the statements about them. In order to satisfy the ICLR requirement that reflects new changes to the revision against the original submission, we currently use strikethroughs to represent the contents to be removed. We will physically remove the contents with the strikethrough representation in this version into the next revision.

Thanks again for taking the time to review our submission!

I highly appreciate the point-by-point response!

1. The example “user account linking in different networks, since the user information contains many sensitive information” is reasonable for the motivation of federated graph matching.
2. The MCMC for graphlet feature extraction and separate trust regions can definitely solve such a problem.

However, my concern about experiments is not resolved.

1. Could the authors elaborate more on why UFGM can be better than (semi)-supervised federated graph matching? Semi-supervised federated graph matching (eg. FL+NextAlign) should have the same accuracy as the centralized semi-supervised training by a few tricks (e.g. encrypts the node pairs). Could the authors elaborate more on how they run FedGraphNN, FKGE, SpreadGNN, SFL, FederatedScope-GNN, and FedStar?
2. Minor thing about the ablation study: Is graphlet feature extraction+separate trust regions (UFGM) better than graphlet feature extraction+fedavg?

I increase my rating from 3 to 4 since the theory is definitely complete.

We thank this reviewer for the helpful comments. We are delighted to hear your positive comments on our contribution to the unsupervised federated graph matching with privacy preservation and good performance. Following your precise assessment, we believe that our work makes a solid step to offer an unsupervised federated graph matching solution for inferring matched node pairs on different graphs across clients while maintaining the privacy requirement of federated learning. We also want to remark that the utilization of the pseudo supervised FGM is able to significantly improve the performance of FGM models.

Weaknesses 1: It seems the scope of the proposed method is specific as it seems to only be designed for federated graph matching. I wonder how hard it will be to generalize the proposed method to general federated learning.

Answer: Thanks for your helpful comments. Different from the FL for computer vision and other graph learning tasks, such as image classification and graph classification, where the data on a client are often independent of the data on another client and stochastic gradient descent (SGD) optimization can be used to evaluate and optimize the local FL models without the need of accessing the data on other clients. However, graph matching aims to match the same entities (i.e., nodes) across two or more graphs. Thus, the FGM needs to infer matched node pairs on different graphs across clients. Directly accessing and sharing local graphs over multiple clients gives rise to a serious privacy leakage concern. Therefore, the SGD optimization widely used in deep learning and FL fails to work on the clients in the FGM, since each client can access only its own local graph data and thus cannot update local loss based on the pseudo matched node pairs. We propose a separate trust region algorithm to separate local model optimization from model evaluation in the trust region algorithm for pseudo supervised FGM while maintaining the privacy constraints.

Weaknesses 2: I can understand the limitations on the experimental side, however, it would be great to hear from authors regarding how the performance of the centralized variant of the proposed federated graph matching approach (i.e., no federated learning)? Does this approach have much better performance?

Answer: Thanks for the kind suggestion. In the appendix, we evaluate two versions of UFGM to show the strength of our UFGM method for federated graph matching. UFGM is the federated version with graph data encryption, graphlet feature extraction, model evaluation on the server, model optimization with the trust region on the clients, and Hessian approximation. UFGM-C is the centralized version with raw graph data uploaded to the server, graphlet feature extraction, model evaluation and model optimization with the standard stochastic gradient descent on the server. The experiment results in Table 4 exhibit that the performance of the centralized version, UFGM-C, is close to our federated version, UFGM, over all three datasets. This further validates that our UFGM algorithm can achieve superior performance for the federated graph matching. In addition, the performance of our UFGM-C method is close to (NextAlign, NetTrans, and SeedGNN) or better than (CPUGA, ASAR-GM, and SIGMA) among six centralized graph matching methods. Notice that NextAlign, NetTrans, and SeedGNN are semi-supervised or supervised methods with 20% training data.