Research map / Graph learning / Graph algorithms and clustering
Effective Federated Graph Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UFGM, an unsupervised federated graph matching method that generates pseudo-matched node pairs from MCMC-sampled graphlet features and optimizes a separate trust-region model with scalar quasi-Newton Hessian approximations.
Problem
Node matching (graph alignment) across graphs held by different clients in a federated setting, where supervised pre-matched pairs cannot be shared for privacy reasons and unsupervised methods underperform.
Approach
Use graphlet-frequency features estimated via MCMC subgraph sampling with Horvitz-Thompson weighting to create pseudo-matched training pairs, then train a GCN-based matcher with a separate trust-region algorithm where the server computes losses and gradients and clients use a scalar quasi-Newton Hessian approximation; data are encrypted with a shared key.
Key results
- UFGM reaches Hits@1 of 0.371 on SNS and 0.771 on PPI, outperforming all federated graph learning and federated domain adaptation baselines.
- On SNS, NextAlign (centralized) achieves Hits@1 0.430 versus UFGM 0.371, a gap the paper describes as about 15.3%.
- UFGM reports about 31.8% and 35.4% convergence improvement in rounds on SNS and PPI respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use UFGM instead of the strongest centralized baseline NextAlign | SNS graph matching · SNS | Hits@1: 0.430 -> 0.371 | Hurt |
| use UFGM instead of the strongest federated baseline FKGE | SNS graph matching · SNS | Hits@1: 0.177 -> 0.371 | Helped |
| use UFGM instead of the strongest centralized baseline NextAlign | PPI graph matching · PPI | Hits@1: 0.951 -> 0.771 | Hurt |
| use UFGM instead of the strongest federated baseline FKGE | PPI graph matching · PPI | Hits@1: 0.231 -> 0.771 | Helped |
| increase trust-region radius; moderate increases initially improve Hits@1, while too-large radii reduce it (ablation) | UFGM · SNS, PPI, DBLP | Hits@1 | Mixed |
| increase maximum subgraph size k; Hits@1 rises then stabilizes (ablation) | UFGM · SNS, PPI, DBLP | Hits@1 | Helped |
| increase training rounds (ablation) | UFGM · SNS, PPI, DBLP | Hits@1 | Helped |
| increase graphlet sample number O; gains level off at larger sample counts (ablation) | UFGM · SNS, PPI, DBLP | Hits@1 | Helped |
Surprising findings
- Centralized NextAlign still outperforms UFGM on SNS at Hits@1 (0.430 vs 0.371), and the paper's own convergence claims are not uniformly supported by Table 1 Hits@10 values.
Limitations
- Assumes each client holds one local graph; multi-graph clients are only discussed as an extension.
- Privacy relies on a shared encryption key among clients and does not provide formal privacy guarantees in the text.
- Hits@K results are not uniformly best; centralized NextAlign outperforms UFGM on SNS.
Experimental setup
Datasets: SNS PPI DBLP
Benchmarks: SNS PPI DBLP
Metrics: Hits@1 Hits@5 Hits@10 Hits@50 Loss
Baselines: NextAlign NetTrans CPUGA ASAR-GM SIGMA SeedGNN FedGraphNN FKGE SpreadGNN SFL FederatedScope-GNN FedStar
Builds on: GCN trust region method Horvitz-Thompson estimator graphlet counting
Closest papers by meaning
- Federated Graph Condensation with Information Bottleneck Principles (AAAI 2025 · similarity 0.87)
- Subgraph Federated Learning via Spectral Methods (NeurIPS 2025 · similarity 0.87)
- Progressive Distribution Matching for Federated Semi-Supervised Learning (AAAI 2025 · similarity 0.87)
- Federated Graph-Level Clustering Network (AAAI 2025 · similarity 0.86)
- Federated Graph Learning under Domain Shift with Generalizable Prototypes (AAAI 2024 · similarity 0.86)
- FedSPA: Generalizable Federated Graph Learning under Homophily Heterogeneity (CVPR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.