Research map / Graph learning / Graph algorithms and clustering
FUGAL: Feature-fortified Unrestricted Graph Alignment
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 FUGAL, an unrestricted graph alignment method that optimizes a QAP on adjacency matrices plus a NetSimile-feature LAP regularizer, solved via Frank-Wolfe with Sinkhorn steps and a gradually increasing quasi-permutation penalty, then rounded by the Hungarian algorithm.
Problem
Aligning two unlabeled graphs by minimizing edge disagreements (a quadratic assignment problem, NP-hard), where prior methods restrict to intermediate representations such as embeddings, spectra, or graph signals that lose information.
Approach
Keeps the full adjacency-based QAP objective, adds a linear assignment regularizer on NetSimile structural node features, relaxes to doubly stochastic matrices, and steers the solution toward a permutation matrix with a tr(P^T(J-P)) penalty that is gradually increased before Hungarian rounding.
Key results
- On ACM-DBLP partially aligned networks, FUGAL reaches 0.487 accuracy versus 0.183 for the next best method (CONE).
- On MultiMagna, FUGAL improves over the next best method S-GWL by 4% on the first noisy variant, with the gap growing to 16% on the last variant.
- On Newmann-Watts graphs at p=0.25 with 1000 nodes, FUGAL reaches 92% accuracy while S-GWL achieves 54%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FUGAL instead of the strongest baseline, CONE | ACM-DBLP alignment · ACM-DBLP | accuracy: 0.183 -> 0.487 | Helped |
| use FUGAL instead of CONE or S-GWL | graph alignment · Voles, 80% of edges | accuracy: 83% and 75% accuracy, respectively, vs. 90% of FUGAL | Helped |
| use FUGAL instead of S-GWL | graph alignment · Newmann-Watts, p = 0.25 | accuracy: 54% -> 92% | Helped |
| add structural features to the alignment objective (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| use degree as the only structural feature (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| use clustering coefficient as the only structural feature (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| use mean neighbor degree as the only structural feature (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| use mean neighbor clustering coefficient as the only structural feature (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| include all four structural features rather than none or a single feature (ablation) | FUGAL · inf-euroroad and ca-netscience, one-way noise | accuracy | Helped |
| iteratively increase λ rather than keeping λ = 0 (ablation) | FUGAL · MultiMagna and inf-euroroad | accuracy | Helped |
| use a flat doubly stochastic initialization instead of the identity matrix (ablation) | FUGAL · inf-euroroad and HighSchool | accuracy | Mixed |
Surprising findings
- Initializing with the identity matrix instead of a flat doubly stochastic matrix gives unstable accuracy, performing worse on HighSchool.
- Fixing lambda=0 (pure doubly stochastic optimization, FUGAL-DS) yields lower accuracy than gradually increasing lambda.
Limitations
- Does not report error bars or statistical significance for experiments.
- Requires tuning the LAP weight mu per dataset (Table 3), with sparser graphs preferring higher values.
- Cubic complexity from matrix multiplications; S-GWL is theoretically cheaper and some baselines run faster on small graphs.
Experimental setup
Datasets: Arenas inf-euroroad bio-celegans ca-netscience ACM DBLP MultiMagna HighSchool Voles Newmann-Watts synthetic graphs Erdos-Renyi graphs
Benchmarks: Arenas inf-euroroad bio-celegans ca-netscience ACM-DBLP MultiMagna HighSchool Voles Newmann-Watts synthetic graphs
Metrics: accuracy running time MNC Frobenius distance between aligned adjacency matrices
Baselines: CONE IsoRank S-GWL GRAMPA GRASP-B FAQ PARROT fGOT GW FGW
Builds on: FAQ NetSimile Sinkhorn distance Frank-Wolfe
Closest papers by meaning
- Graph Alignment via Dual-Pass Spectral Encoding and Latent Space Communication (ICML 2026 · similarity 0.86)
- Chaining 2-FWL GNNs for Combinatorial Graph Alignment (NeurIPS 2026 · similarity 0.86)
- Hypergraph Learning for Unsupervised Graph Alignment via Optimal Transport (AAAI 2025 · similarity 0.85)
- UGC: Universal Graph Coarsening (NeurIPS 2024 · similarity 0.84)
- Pairwise Alignment Improves Graph Domain Adaptation (ICML 2024 · similarity 0.83)
- Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem (NeurIPS 2024 · similarity 0.82)
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.