FUGAL: Feature-fortified Unrestricted Graph Alignment
Authors: Aditya Bommakanti
Harshith Reddy Vonteri
Konstantinos Skitsas
Sayan Ranu
Davide Mottin
Panagiotis Karras
Venue: NeurIPS 2024 poster (2024)
Keywords: graph alignment
Primary area: optimization
TL;DR: We find a permutation matrix that maps one graph to another by directly operating on their adjacency matrices, surpassing state-of-the-art methods in accuracy across all benchmark datasets without encumbering efficiency.

Abstract: The necessity to align two graphs, minimizing a structural distance metric, is prevalent in biology, chemistry, recommender systems, and social network analysis. Due to the problem’s NP-hardness, prevailing graph alignment methods follow a modular and mediated approach, solving the problem by restricting to the domain of intermediary graph representations or products like embeddings, spectra, and graph signals. Restricting the problem to this intermediate space may distort the original problem and are hence predisposed to miss high-quality solutions. In this paper, we propose an unrestricted method, FUGAL, which finds a permutation matrix that maps one graph to another by directly operating on their adjacency matrices with judicious constraint relaxation. Extensive experimentation demonstrates that FUGAL consistently surpasses state-of-the-art graph alignment methods in accuracy across all benchmark datasets without encumbering efficiency.

FUGAL:
Feature-fortiffed Unrestricted Graph Alignment
Adítya Bommakanti IIT Delhi
Harshith Reddy Vonteri
IIT Delhi
adi aatxyabommaaann:1000ggglall com
larghitbreedyrrooter.gg.........
Konstantinos Skitsas
Sayan Ranu
Davide Mottin Aarhus University davideScs au. dk
Aarhus University skitsas8cs. au. dk
IIT Delhi
sayanranu8cse.. iitddac......... in
Panagiotis Karras
University of Copenhagen & Aarhus University piekarras@gmail.com com
Abstract
The necessity to align two graphs, minimizing structural distance metric, is prevalent biology, chemistry, recommender systems, and social network analysis. Due to the problem's NP NP-hardness, prevailing graph alignment methods follow a modular and mediated approach, solving the problem restricted to the domain intermediary graph representations or products like embeddings, spectra, and graph signals. Restricting the problem to this intermediate space may distort the original problem and are hence predisposed miss high-quality solutions. In this paper, we propose an unrestricted method, FUGAL, which finds a permutation matrix that maps graph another by directly operating their adjacency matrices with judicious constraint relaxation. Extensive experimentation demonstrates that FUGAL consistently surpasses state-of-the-a graph alignment methods in accuracy across all benchmark datasets without encumbering efficiency.
Introduction and Related Work
Graph alignment seeks to match pair of graphs to each other, i.c., to correlate nodes of one graph to those of the other. For instance, biological systems such as protein-protein interaction networks and gene regulatory networks can be represented graphs. The alignment of such biological networks across species reveals orthologous proteins or genes (i.e., homologous genes that evolved from a common ancestor) and thereby conveys the biological function of uncharted genes in species through their better-studied counterparts in another species [37 36] The same problem also arises in other high-impact network science tasks (11), such as identifying users in social networks [22
and feature matching in computer vision 6 The problem can be formulated as an instance of
the quadratic assignment problem (QAP) 13 24 between nodes of the two graphs, which treats the
edges in one graph as units of flow and the edges in the other graph as distances between nodes. This relation renders the problem A-X-hard approximate even within an approximation factor that
grows linearly with the number of nodes [30 [3).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1
Related Works
Owing to the problem's 's hardness, several heuristics have been proposed. Nevertheless, state-of-the-art graph aligmment methods refrain from directly addressing the edge-aware QAP. Instead, they craft intermediate representations of nodes that allow for the computation of similarities and settle for solving an assignment problem over those representations. We call these methods mediated due to their restriction to intermediary graph representations. While the transformation from the original graph space an intermediate space enables computational efficiency, the transformation incurs loss of information. In this work, we propose an unrestricted graph alignment method that avoids restricting the problem to an intermediate space, while also retaining efficiency. We call our method "unrestricted" rather than "unmediated" since, while we retain the full graph information in the core QAP, we also avail of help from mediated representations solve the QAP. In the subsequent discussion, we summarize the various mediated and unmediated approaches in the literature.
Mediated Approaches: GWL jointly learns embeddings and alignments using the dissimilarity notion of W discrepancy: it estimates distance matrices using the embeddings when learning the optimal transport, and regularizes the learning of embeddings using the learned transport. S-GWL [43] addresses the scalability drawback of GWL by adopting a partitioning method on the input graphs. CONE [4] models intra-network proximity with node embeddings and uses them to match nodes across networks after aligning embedding subspaces. REGAL [17] identifies node matchings by greedily aligning their latent feature representations learnt from graph structures. GRAMPA [13] constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs. GRASP (0) uses the spectral properties of the graphs grounded on the eigenvectors of their normalized Laplacian matrices. IsoRank (37] uses neighborhood similarity to extract structural graph information and recursively updates the score of node pair using the score of their neighbors. GRAAL (25) is greedy alignment method that matches nodes using a similarity score based on dictionary of small frequent graph patterns. GOT (31] employs the probabilistic distribution of smooth graph signals defined with respect to the graph topology, and seeks alignments by minimizing the distance between these graph signal distributions. IGOT [32] adopts a dissimilarity metric that aligns two graphs using the probability distribution of data generated via graph filters.
PARROT 46) presents a -upervise methodology which encodes graph topology through random walks with restart (RWR) for position- position-aware aware transport cost and addresses a regularized Optimal Transport (OT) problem to determine node mappings. GW 335 and FGW [40] compute Gromov-Wasserstee Wasserstein discrepancy using similarity matrices of shortest path distances between nodes.
Unmediated Approaches: FAQ 42 is an unmediated algorithm that addresses the QAP by relaxing constraints to attain computational tractability. GLAG [14] proposes a problem formulation that retains the full graph information and relaxes the permutation constraints. As we will see in $ these methods of relaxing constraints lead to inferior accuracy.
Unrestricted Approaches: In addition to the full graph information, PATH 45 and FGM 49 also use feature matching, while DSPP [10] employs cil--arrr-sooteess
for graph alignment. We characterize these methods unrestricted, since they also avail of help from mediated representations. As we will see in $ S] these methods are significantly inferior to FUGAL in terms of accuracy.
1.2 Contributions
Optimization problem formulation: We present FUGAL (Feeaure-fortified Unrestricted Graph Alignment), a graph alignment method that retains full graph information by integrating the quadratic assignment problem (QAP) in the optimization objective. To augment quality, we utilize regularizer in the form of a linear assignment (LAP) supplement incorporating graph structural features.
Unrestricted solution: FUGAL relaxes the solution space to doubly stochastic matrices and uses a customized optimization strategy that guides the Frank-Wolfe algorithm [16] through a Sinkhorn distance objective 7 steer the resulting doubly stochastic solution towards a quasi-permutatiinn matrix. We call our approach unrestricted, as it does not rely solely on intermediate representations. On the other hand, it is not entirely unmediated, as the LAP regularizer using structural features is mediated. Thereby, we retain the full graph information and also enable mediating representations to efficiently guide the optimization process and thereby enable both efficacy and tractability. Experimental evaluation: Through extensive experimentation with real-world and synthetic datasets across varying graph density and noise levels, we demonstrate that FUGAL outperforms -fate-of-the- art graph alignment methods in accuracy without a detrimental efficiency overhead.

---

2 Problem Formulation
Definition 2.1. Let E) denote unlabelled, undirected graph, where V is the set of nodes each identified by a number [x] = (1..... n) and & C V x V is the edge set. The adjacency matrix of g is A E (0, 1 such that dij aji 1 if and only if (i,j) E E.
We denote an all-ones vector as an all-ones square matrix J, and an all-zero square matrix O. The dimensions of entities are inferred from the equations employing them.
Definition 2.2. We denote the set of binary-valued permulation matrices J (P E {0, 1j P1 = 1, P.PT1 = } and that of real-valued doubly stochastic matrices as W = (W E [0, 1 1
W1 = 1, W = 1}.
Definition 2.3. Let A ((G))e(())JEEm) E E
We denote the Frobenius norm as the entry-wise
2-norm | <>
-j= m
|
Definition 2.4. We denote the trace of a matrix A as tr(A).
Theorem 2.5. A doubly-stochastic matrix A with tr(A (J -A))
permutation matrix.
Proof. From ir(AT(J A)) O follows that Σ,E, Dij (1 0:g) 0. Since A is doubly- stochastic, 0 dij 1 for all and j. Thus, aij (1 d.ÿ) 2 0 for 15 i,j S n. Therefore,
az (1 - azy) 0 for all and j. As a consequence, ag E {0, for each and j. Given that A is doubly-stochastie and all its entries are either or by Definition 2.2 A is permutation matrix. 0
Problem (Unmediated Graph Alignment). Consider two graphs G1 == (V1, E1) and G2 == (V2, Eg) with adjacency matrices A, B respectively. The objective of unmediated graph alignment is to identify bijection f : V1 + V22 between the two graphs that minimizes the number of edge disagreements. Formally, the problem expressed as:
min
AP - PBB
PEDA
where In denotes the set of permutation matrices.
The appellation unmediated denotes that we seek correspondence among nodes without using any information other than the adjacency matrix. The problem an instance of the NP- quadratic assignment problem (QAP) [24]
Due the problem's 's hardness, a popular approximation path utilizes intermediaries such as node beddings. A mediated graph alignment is thus expressed as a linear assignment between embeddings rather than a quadratic assignment between adjacency matrices:
min E, PF
PEF
where Eg / is the embedding matrix of Gk and [g[i,;] :] is the F-dimensional vector representation of node of Gk- The optimization problem in Equation (2) is a linear assignment problem (LAP), which is solvable optimally in O (N*) by the Hungarian algorithm [26). while sub-optimal solutions reduce complexity to O (N2).
Extension to graphs of unequal sizes. Consider two graphs G1 and G2 with node counts nı and n2, respectively (n1 < n2). To enable alignment despite the size difference, augment Gı with (n2 n1)
isolated dummy nodes and discard mappings involving dummy nodes from the output.
3 FUGAL
To design FUGAL, we augment the core QAP of Eq. (1) with a LAP supplement that leverages simple structural graph features (S 3.1 to form a unified optimization problem over the set of permutation matrices 1a (S 3.2 As this problem is NP-hard, we relax its solution space to the set of doubly stochastic matrices solution to obtain a quasi quasi-permudii permutation matrix, i.e., almost a permutation matrix, which we adjust to permutation matrix that signifies a valid alignment by solving a simple LAP using the Hungarian algorithm 26). We dub this approach "unrestricted" as it eschews the information loss incurred by mediated solutions, which rely solely on intermediary representations, However, we still employ supplementary mediating representations to ensure tractability and efficiency.
(S (33.3) superset of the set of permutation matrices. We refine the
3

---

3.1 LAP Formulation
Here, we formalize the Linear Assignment Problem (LAP), which is auxiliary to our framework. We construct node feature vector using four structural features proposed in NETSIMILE [2]. This includes (1) d,. the degree of node v4 (2) c, the clustering coefficient of v4. (3) dx. the mean degree of 04's neighbors, (4) and čN., the mean clustering coefficient of ey's neighbours. Other features, such as betweenness centrality, PageRank, may also used. Ultimately, the decision resides on the trade-off between the utility of including these features on alignment quality and the efficiency of computing these features.
Using these features, construct feature matrix F5x R x4 for each graph G3 and, by the rationale that the structural features of corresponding nodes are similar, we formulate a Linear Assignment Problem for Ø1 and 92 as:
min PEP
F - 2F2
By the Frobenius norm definition, Eq.
equivalent to:
min
Σ
F [i. - Pispiali
(4)
Utilizing the property of permutation matrices that each row contains only one we reformulate
Eq. (4) to:
min PEP
Fal. min ΣP.D, PEF
(5)
1.
1.j
where D is a distance matrix with Dij denoting the squared Euclidean distance between F1 Fi and Fz Since each row :[ contributes exactly one term to this sum, being the element D corresponding to the single I entry in Pli, :]. the result is equal to the trace of the matrix product:
min tr(P (D(P PEF
(6)
3.2 Optimization Problem
Our problem formulation augments the QAP of Eq. ① with LAP regularizing term in Eq. 6
min PEP
|PP PB P μ D)
where and denote the adjacency matrices of 91 and G2, respectively, D follows Eq. (6. and regulates the LAP's significance; since PPT I, this is expanded to:
min tr T A) + tr B) 2tr(AA p
(8)
PEP
cquivalently, ignoring constant terms and reversing the sign,
max Lr(APB pa ()) PEP
(9)
In the case of μ O, the first term alone corresponds the maxQAP problem 330. which is A to approximate even within an approximation factor that grows linearly with the number of nodes. Given this hardness of the QAP alone and the fact that relaxing combinatorial constraints often results in a substantial deterioration of solution quality, we introduce the LAP regularization to ground the QAP solution on pragmatic features and thereby guide it, even after relax combinatorial constraints.
3.3 Approximating the Optimization Problem
The problem in Eq. 9 is NP-hard, due to the non-convex nature of the space of permutation matrices (24). A natural way to overcome this hardness is to enlarge the allowed solution space to the convex set of doubly stochastic matrices W", as considered in FAQ 42
min PEW
tr(APB T μ tr(P D)
(10)

---

Since the problem in Eq. (TO) calls to minimize function subject to linear constraints implied by P E W the solution can be efficiently found [3 by algorithms such as Adam (33 and
Algorithm
FINDQUASIPERMUTATIOO
(A, B, D, (r,
Input: Adjacency Matrices A, B, Distance matrix D. control param-
eter ja. nom iters
Frank- Wolfe [16]. The FAQ algorithm [42] follows such an approach to solve the relaxed optimization with the Frank-Woll algorithm and project the so- lution back onto P", yet addresses exclusively the first, QAP term in Eq. (T0.. To further augment
Output: Puasi-Permutation matrix
Nolation:
S(P): tx(APB + D)
((P) : tr(P P))
1: Q <- 1. 1. 1
2: for A
T
quality, as we elaborate later in Section we in- clude the LAP term in Eq. (TO) and also add reg- ularizing term that guides the solution towards a quasi-permutation matrix. By Theorem 2.5 which
for it 1
grad (S(Q) + A VQ(Q)
5:
migmin, vown (grad, Sinkhorn
6:
24
Q- 1gs Q)
establishes that a doubly-stochastie matrix P with tr(P (J P)) 0 is permutation matrix, we rewrite the problem in Eq. 9 as:
end for
for
10: return
tr(AAB P t. u
min
PEW
(1I)
Constraints:
tr(P (J P)) =
and turn the constraint a regularizer with parameter A:
min tr TiBBTPTy PJ) + + p. tr(P + A (tr(P PJ))
(12)
PEW
Equivalently, by reformulating the constraints:
min - tr(APB T P p.p.tri trptttpPP TD) + (J-)P)
(J-P)))
(13)
Constraints: P1 1,P = 1,0 P.j S
We solve the problem in eq. (3 for À = 0 by the Frank Wolfe (FW) algorithm 16 with updates guided by an objective computed via the Känkhorn-Knopp algorithm [7]. due to the computational warm start, and refine
efficiency they confer. We use the solution this optimization problem by gradually increasing À over I' iterations, each initiating with the solution obtained in the preceding one and solving the problem in Eq. (13) by FW. Alg. Noulines the process.
Rounding Algorithm: Alg. yields a gieasi-permutatiinn matrix Q. Next, to obtain an one-to-one mapping between nodes of 91 and 92, we need adjust Q to permutation matrix by rounding. We pose this problem as an assignment problem, maximizing the sum of Qú, entries selected for rounding up 1, while rounding the rest down O, and solve it optimally by the Hungarian algorithm (26 Alg. 2 in the appendix presents the complete FUGAL pseudocode.
4 Customized Optimization Strategy for Node Alignment
In this section, we elucidate the intricacies of Algorithm I, which derives quasi-permutation matrix, focusing on two pivotal steps: (i) initialization of the quasi-permutatio matrix; (ii) finding the local solution for a given X.
Initialization:
Any doubly stochastic matrix is a viable option for initialization. However, we opt for an uninformative flat matrix, 1 //n. Our empirical observations indicated that this initialization consistently performs well across diverse datasets, contrary informative initializations like the identity matrix, which exhibit inconsistency in performance, as we further elaborate in Section A.8
Local Solution for given X: Given specific X, our objective is solve the optimization problem of Eq. (13) under linear constraints. To achieve this, we employ the Frank-Wolfe algorithm (FW), a successive first-order optimization technique devised for solving convex quadratic programs [16]. While FW is a widely utilized solver as subroutine for QAP algorithms, we tailor its application to FUGAL. Specifically, each iteration commences from the local solution obtained in the previous iteration and involves the following steps:
Computing the Gradient: The gradient of the objective function f(P) tr(APP T + +
tr(P D) with respect to P, evaluated at Q, is f (Q) AQB - AA QB + D. Additionally,
5

---

the gradient of the constraint function g(P) - ir(PT(a (J- (0-P) P)) with respect to P, evaluated at Q. = (
--Q..
Updating Q: A critical step involves determining the doubly-stochastic matrix da that minimizes the inner product (grad, 4), where grad the current gradient. Prior work 442 applies the Hungarian algorithm to obtain permutation matrix to that end, which, however, may not yield the optimal answer and incurs (n²)) cost. Contrarily, we obtain proper doubly stochastic matrix to that end. Definition 4.1 (Optimal Transport Distance Between and c). Given n x cost matrix M, the cost of mapping an n-dimensional probability vector r to e, using a transportation matrix (or joint probability) P is quantified as (P, M). The following problem:
min
(P,M)
(14)
PEU(N.)
an optimal transport problem between Y and given cost M, where
C(r,c) (P e RTx" P1 = Pi=r,P 1 1-
(15)
To render this optimal transport objective strictly convex and thus efficiently solvable by the matrix scaling Sinkhomn-Knon fixed-point iteration algorithm [38] via matrix-vector products, we regularize with an entropic penalty h(P) that yields the Sinkhorn distance objective 77]
(P.M) h(P) PEU(IC)
min
(16)
K
where h(P) = = -E Piy log Pú. E (0, oo], which becomes equivalent to the transport distance
for suitably large [7]. The method exhibits excellent performance in practice with On?) empirical time complexity.
Setting r and с to 1 (the all-ones vector) in Eq. (5) (rr c) becomes the space of doubly stochastic matrices, hence Eq. (14) with M grad captures our update step objective. Thus, we find the doubly stochastic matrix Qie that minimizes (grad, q) by the Sinkhorn Sinkhorn-Knopp algorithm and update Q as Q +++++ (ga Q), with the step size a following the conventional choice
2/(2 + it).
The complexity of FUGAL is O(n²), which is in line with the majority of the baselines. A detailed derivation and comparison of FUGAL'S complexity with baselines is provided in App. The The (n²²) complexity stems from the need to perform matrix multiplications, a core operation in FUGAL as well as the baselines. thorough evaluation of empirical running times (S 5.5 also demonstrates the practical scalability of FUGAL.
Complexity Analysis:
Experiments
In this section, present comprehensive evaluation of FUGAL state-of-the-art graph alignment baselines on real and synthetic data sets with varying noise levels.
5.1 Datasets
Real Graphs. Table I summarizes the real-world datasets used to benchmark FUGAL. last three data sets in the table are evolving graphs mandating challenging ground alignments.
Synthetic Graphs. We employ Newmann- Watts (NW) [21] graphs, characterized by small-world prop- erties and a high clustering coefficient. We generate NW graphs with 1000 nodes, number of neighbors per node k = and a rewiring probability of p= 0.1. For each graph, we generate noisy variants, perform align- ments on each, and report average results. Given the ob- tained alignment set P and the ground truth of align-
Table 1:
Real- Real-graph nodes n, edges m, and network type.
Dataset
Type
Arenas
55
1133
5451
communication
inf-eureroal
1
1174
1417
infrastructure
hio-celegans
453
2025
hiological
ca-netscience
3k
379
914
collaboration
ACM 48
9872
39
561
citation
ments Preat, we calculate accuracy as
PPP
100. PP
M8
9916
citation
MultiMagna
4|
1004
8.323
hiological
Noise Types. As in prior work 4 20 we introduce perturbations to the adjacency matrix by either removing or adding edges. We employ two noise types: one-way
HighSchool
15
327
5818
proximity
Vales
712
2391
proximity
noise removes edges from the target graph. while bimodal noise removes and restores the same number of edges.

---

FUGAL
CONE PARROT
IsoRank
S-GWL
GRAMPA
GRASP-B
FAQ
fGOT
GW
FGW
MultiMagna
Voles
HighSchool
0.8
Accuracy
0.6
0.4
0.2
0
1
2
3
4
5
100
90
80
100
90
80
variant #
% of edges
% of edges
Figure 1: Accuracy, real graphs with real noise.
5.2 Experimental Setup
We ran all experiments on 40-core Intel Xeon E5-2687W CPU machine @3.10GHz with Python im-
plementations of FUGAI f and competitors F the latter include CONE [4. IsoRank [37] I. S-GWL
43
GRAMPA 13 GRASP-B 19), FAQ 421, PARROT [46), fGOT 32 GOT
31. GW
35 and
FGW 40 Due to scalability limitations, we excluded fGOT from consideration for graphs with more than 1000 nodes, on which failed to terminate within 5 hours. Moreover, due to the inability of GOT, PATH, and DSPP to scale for the smallest dataset in our analysis, we assess them separately on smaller graphs in Appendix A.4 We exclude GWL from evaluation in favor of its scalable and superior variant, S-GWL 39 We omit from the comparison algorithms such as GRAAL (25) GLAG [14] and REGAL 17 due their inferior performance [39] [2]. As we focus on attribbbb graphs, we
exclude FINAL 47 which is equivalent to IsoRank on graphs without attributes. For the prerequisite
similarity score in IsoRank, we devise customized weight scheme sim(u,
(dg-dul
max m du
where d,, = [u) denotes the degree of node u. With all baselines, we use author-recommender parameters and derive node matchings from similarity scores using the Hungarian algorithm. In Appendix A.5 we benchmark FUGAL against S-GWL and CONE in terms of Matched Neighborhood consistency (MNC) 4 and the Frobenius norm between aligned graph adjacency matrices.
5.3 Accuracy on varying noise
Graphs with real Noise: We evaluate all algorithms on accuracy with three real-world networks: MultiMagna, Voles, and High School. MultiMagna represents yeast protein-protedd interaction (PPI) network and noisy variants incorporating an additional 9% of low-confidence interactions, with q (5, 10. 15, 20, 25). High School and Voles are temporal proximity networks: we align the last graph version to versions containing 80%, 85%, 90%, and 99% of edges. Figure [ presents our results. FUGAL consistently achieves accuracy surpassing its counterparts across all datasets, with S-GWL being the closest baseline on average. On MultiMagna, FUGAL attains 4% improvement over the next best algorithm, S-GWL, on the first graph variant, and this gap steadily increases to 16% on the last variant. On Voles, CONE and S-GWL follow FUGAL's accuracy with up to 90% of edges, yet with 80% of edges, they achieve 83% and 75% accuracy, respectively, vs. 90% FUGAL. On the High School network, FUGAL, FAQ and PARROT align graphs perfectly, while S-GWL attains near near-pertee perfect alignment. IsoRank, GRAMPA, GRASP-B fGOT, GW and FGW fall short of FUGAL'S 's performance across all three datasets. Despite performing comparably to FUGAL on the HighSchool dataset, FAQ and PARROT exhibit notably poorer performance on other datasets. The consistently superior performance of FUGAL underscores its robustness.
Large Real Graphs with Partially Aligned nodes: ACM and DBLP are two co-authorship networks of the ACM Digital Library and DBLP bibliography. In these networks, nodes represent authors, and an edge exists between two authors if they have collaborated on at least one publication. Across both networks, there are 6,325 authors who appear in both. Although both networks are attributed, we did not incorporate this information in our experiments. Note that S-GWL and GRASP-B are not scalable for networks of this magnitude, hence omitted from the analysis. Furthermore. the experiment was conducted in an unsupervised manner, meaning that the methods were not provided with any prior information regarding node alignment. Our results, detailed in Table 2 showcase
I 'Code and data at httpp://giihubb.mm//beeeeeiiiiii
"Source code http:///ttta..cocoooosaaaaaaaaas

---

FUGAL
CONE
IsoRank
S-GWL
GRAMPA
GRASP-B
FAQ
PARROT
FGOT
GW
FGW
inf-euroroad
arenas
ca-Netscience
bio-celegans
0.8
Accuracy
0.6
0.4
0.2
0
5
10
15
20
25
0
5
10
15
20
25
0
5
10
15
20
25
0
10
15
20
25
Noise
Noise
Noise
Noise
inf-euroroad
arenas
ca-Netscience
bio-celegans
0.8
Accuracy
0.6
0.4
0
0
5
10
15
20
25
0 5
10
15 20
25
0 5
10
15
20
25
0
10
15
20
25
Noise
Noise
Noise
Noise
Figure 2: Accuracy, one-way (top) & bimodal (bottom) noise.
CONE
IsoRank S-GWL
GRAMPA GRASP-B
FAQ
FUGAL a- PARROT GW
FGW
One-way noise
Bimodal noise
One-way noise
Bimodal noise
0.8
Accuracy
0.6
0.4
0.2
0
5
10
15
20
25
0
5 10 15
20
25
0
3
5
0
5
Noise
Noise
Noise
Noise
Figure 3: Accuracy, Newmann- Watts graphs.
the fraction of correctly aligned nodes out of the 6,325 aligned nodes. FUGAL demonstrated a significant improvement of 30% compared to the closest baseline, CONE. This underscores the superior scalability of FUGAL without compromising accuracy.
Table 2: Accuracy in alignment across ACM-DBLP.
CONE
IsoRank GRAMPA FAQ PARROT
GW
FGW
FUGAL 0.487
Accuracy 0.183
0.042
0.011
0.025
0.000
0.028
0.012
Real Graphs with Injected Noise: Figure 2 iillssraates the results on real datasets subject to synthetic one-way and bimodal noise. Consistent with the trends observed in real noise, FUGAL exhibits superior performance across all evaluated networks and noise types. This consistent superior performance of FUGAL establishes it as robust graph alignment solution. Appendix A.3 zooms in on the performance of FUGAL vs. basclines with noise levels in the range 0% to 5 % to better highlight the performance superiority of FUGAL.
Synthetic Graphs: Figure 3 portrays accuracy results on Newmann- -owtann-Watts graphs of 1000 nodes with node degree k = and rewiring probability p = 0.1 subject to synthetic noise. Under one-way noise, all methods except CONE and FAQ achieve perfect alignment 0% noise. With noise of 5% and 10%, FUGAL attains 60% and 14% gain, respectively. over the 2nd-best method, S-GWL. Beyond these noise levels, methods experience failures. Bimodal noise at 0% results in perfect alignment for most methods. However, alignment failures occur noise grows. Figure 3 further zooms noise levels the range of 0% 5%. FUGAL significantly outperforms all baselines under one-way noise, achieving margin of 60% 3% and 5% levels. Moreover, FUGAL performs

---

superiorly in the bimodal noise within the 5% noise threshold, gaining nearly 40% at 1% and 3% noise levels. These results underscore the efficacy of FUGAL handling diverse graph structures.
5,4 Varying Density
Here, we examine performance under varying graph density. In Newmann- Watts graphs, the rewiring probability parameter affects the edge density of sampled graphs for fixed number of nodes while the parameter kt representing the number of nearest neighbors per node, affects the minimum and expected degree. Figure 4 shows our results when varying p and k in NW graphs comprising 1000 nodes. Methods other than FUGAL consistently fail to handle sparse graphs (low p). However, FUGAL attains accuracy 92% at 0.25, outperforming S-GWL, which achieves only 54%. Sparse graphs pose a challenge for alignment, as they provide less discriminating evidence terms of density differentials. When varying k, FUGAL consistently achieves near-perfect alignment, surpassing all baselines. These findings corroborate the resilience of FUGAL across graph densities and its adaptability to varying degrees of connectivity.
FUGAL
CONE
IsoRank
S-GWL
GRAMPA
GRASP-B
FAQ
PARROT
GW
FGW
k=
k=
p 0.5
0.8
Accuracy
0.6
0.4
0.2
0.05
0.15
0.25
0.2
0.6
20
60
100
p
p
k
Figure 4: Accuracy varying density and one-way noise.
5.5
Efficiency
Here compare the computational efficiency of FUGAL to that of S-GWL, which ranks as the second-ber best performer across most benchmark datasets.
Figure D plots running times in logarith- mic axes. FUGAL achieves lower running times on MultiMagna, Voles, euroroad, arenas, and Newmann- Waatann--Watssss networks with an up to 3x speed up, highlighting its capacity to handle large networks. Con- versely, S-GWL marginally outperforms FUGAL on smaller networks. S-GWL did not scale for ACM-DBLP, failing to terminate even after 5 hours. This dis- crepancy indicates S-GWL's incapacity to scale to large networks, which restricts its broader applicability. We emphasize that FUGAL achieves a substantial accuracy advantage without compromising efficiency, affirming its prowess efficient and effective solution. Appendix A.2 presents running times for all baselines.
B
FUGALEI E S-GWL
Time (see)
10
100
10-2
MultiMagnal
Voles HighSchool
euroroad
arenas
netscience celegans
NW ACM-DBLP
Dataset
Figure 5: Running time comparison, FUGAL vs S-GWL.
5.6 Scalability
FUGAl S-GWI
-104
Time (sec)
Given the results of Section 5.5 into the scalability FUGAL and S-GWL with Newmann- Watts graphs of increasing nodes. ploss our findings. At 512 nodes, FUGAL and S-GWL have compa- rable running times. Still, as nodes grow, FUGAL outpaces S-GWL.
we delve
4
2
29
200
2
212
213
Number nodes
Figure 6: Scalability on NW graphs, k = 7, p = 0.5.

---

5.7 Parameters and Ablation
FUGAL-O
FUGAL-1 -n FUGAL-2
3UGAL-3
FUGAL-4
FUGAL
Table in Appendix lists the parameters we employ in FUGAL with each dataset. We set the number of iterations T to 15 for all datasets. The parameter μe con-
inf-euroroad
ca-netscience
0.8
trols the sway of node features in the op- timization. Sparser graphs, characterized by lower connectivity and less information in adjacency matrices, benefit from higher reliance on node features, hence we recom- mend higher μ.. Sparser datasets such as inf-euroroad, ca-netscience, and NW (k 7, p 0.1) benefit from higher val- ues of μ (1-2), denser graphs from smaller values (0.1-0.5)
Accuracy
0.6
0.4
0.2
5
10
15
20
0
10
15
20
25
Noise
Noise
Figure
Accuracy of FUGAL variants, one-way noise.
FUGAL FUGAL-DS
We also conduct an extensive ablation study to assess the impact of the structural features outlined in Section 3.1 We craft five variants of FUGAL, where FUGAL-i utilizes only the ith structural feature while excluding others. FUGAL-O abstains from all structural features. Figure 7 juxtaposes the accuracy of these variants to that of FUGAL on two networks. Each variant em- ploying structural features attains higher accuracy than FUGAL-O, corroborating the usefulness of these features. Further, FU- GAL, leveraging all features, outperforms other variants. Notably, FUGAL-1 performs second-best, underscoring the significance of degree in identifying node alignments. We also inves- tigate variant setting À denoted as FUGAL-DS (for doubly stochastic), instead of iteratively increasing it. As Figure shows, FUGAL-DS attains worse accuracy.
MultiMagna
inf-euroroad
0.8
Accuracy
0.6
0.4
0.2
0
2
3
4
5
0
10
15
20
25
Variant #
Noise
Figure 8: The effect of setting X = 0 (FUGAL-DS) against the default option of iteratively increasing.
6 Conclusions
We introduced FUGAL, an unrestricted algebraic approach to graph alignment that works directly on graph adjacency matrices and identifies node correspondences by relaxing permutation matrix constraints and steering the solution to the desired form, followed by rounding. Through extensive experimentation, established that FUGAL surpasses state-of-the-e graph alignment methods in accuracy across network types, noise conditions, and graph densities, even while maintaining a scalability advantage.
Broader Impact and Ethical consequences: FUGAL opens the way improved solutions in graph aligmment, as reflected in its performance across diverse networks, noise types, and graph density. This outcome can spark further research in optimization techniques and advances in bioinformat- ics, social network analysis, and infrastructure mapping. Still, advances in graph alignment also enhance the abilities of attackers attempting to de-anonymize sensitive social network and biological data. Therefore, preventing attacks on privacy is crucial, calling for the enforcement of advanced anonymization methods (34] before publishing such data.
Acknowledgements
AB supported by Graviton Research Capital LLP. HRV was supported by the CSE Research Acceleration Fund of IIT Delhi. KS was supported by the Independent Research Fund Denmark.
10

---

References
[1] David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner, editors. Graph Partitioning and Graph Clustering. Proceedings of the 10th DIMACS Implementation Challenge Workshop., volume 588 Contemporary Mathematics. American Mathematical Society, 2013.
[2] Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos. Network similarity via multiple social theories. In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 1439-1440, 2013.
[3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[4] Xiyuan Chen, Mark Heimann, Fatemeh Vahedian, and Danai Koutra. CONE-Align: Consistent network alignment with proximity pressrriin node embedding. In 29th ACM International Conference on Information and Knowledge Management, CIKM, pages 1985-1988, 2020.
[5] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Graph matching appli- cations in pattern recognition and image processing. International Conference on Image Processing, ICIP, pages 21-24, 2003.
[6] L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367-137 2004.
[7] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurlPS, pages 2292-2300,, 2013.
[8] Stephen Davis, Babak Abbasi, Shrupa Shah, Sandra Telfer, and Mike Begon. Spatial analyses of wildlife contact networks. Journal of The Royal Society, Interface, 12(102)20014004, 2015.
[9] Jordi Duch and Alex Arenas. Community detection in complex networks using extremal optimization. Phys. Rev. E, 72:027104, 2005.
[10] Nadav Dym, Haggai Maron, and Yaron Lipman. DS++: a flexible, scalable and provably tight relaxation for matching problems. ACM Trans. Graph., 36(6):18::11184:144 2017.
[11] Frank Emmert- Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph matching. network alignment and network comparison. Inf. Sci., 346-347:180-1997, 2016.
[12] Paul Erdōs and Alfréd Rényi. On random graphs I. Publicationes Mathematicae Debrecen, 6:290, 1959.
[13] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In ICML, volume 119, pages 2985-2995, 2020.
[14] Marcelo Fiori, Pablo Sprechmann, Joshua T. Vogelstein, Pablo Musé, and Guillermo Sapiro. Robust multimodal graph matching: Sparse coding meets graph matching. In NeurlPS, pages 127-135, 2013.
[15] Julie Fournet and Alain Barrat. Contact Patterns among High School Students. PLOS ONE, (19:
[16] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)995-10, 1956.
[17] Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. REGAL: representation learning-based graph alignment. In 27th ACM International Conference on Information and Knowledge Management, CIKM, pages 117-126, 2018.
[18] Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad Rad, Hanghang Tong, and Christos Faloutsos. It's who you know: graph mining using recursive structural features. In 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
KDD, pages 663-671, 2011.
11

---

[19] Judith Hermanns, Konstantinos Skitsas, Anton Tsitsulin, Marina Munkhoeva, Alexander Kyster, Simon Nielsen, Alexander M. Bronstein, Davide Mottin, and Panagiotis Karras. Grasp: Scalable graph alignment by spectral corresponding functions. ACM Trans. Knowl. Discov. Data, 17(4),
feb 2023.
[20] Judith Hermanns, Anton Tsitsulin, Marina Munkhoeva, Alexander M. Bronstein, Davide Mottin, and Panagiotis Karras. GRASP: graph alignment through spectral signatures. In Web and Big Data 5th International Joint Conference, APWeb- WAIM 2021, pages 44-52, 2021.
[21] Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Phys. Rev. E, 65:026107, Jan 2002.
[22] Ehsan Kazemi, S. Hamed Hassani, and Matthias Grossglauser. Growing graph matching from a handful of seeds. Proc. VLDB Endow. 1000::010-1021, jun 2015.
[23] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
[24] Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25(1):53-76, 1957.
[25] Oleksii Kuchaiev, Tijana Milenkovic, Vesna Memisevic, Wayne Hayes, and Natasa Przulj. Topological network alignment uncovers biological function and phylogeny. Nature Precedings, 4, 12 2009.
[26] Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83-99) 1955.
[27] Jérôme Kunegis. KONECT: the Koblenz network collection. In 22nd International World Wide Web Conference, WWW, pages 1343-1350, 2013.
[28] Jajjin Li, Jianheng Tang, Lemin Kong. Huikang Liu, Jia Li, Anthony Man-Cho So, and Jose Blanchet. A convergent single-loop algorithm for relaxation of Gromov- Wasserstein in graph data. In ICLR, 2023.
[29] Vince Lyzinski, Donniell E. Fishkind, Marcelo Fiori, Joshua Vogelstein, Carey E. Priebe, and Guillermo Sapiro. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(1):60-73, 2016.
[30] Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic as- signment problem: Reduction from maximum label cover and Ip-hased approximation algorithm. ACM Trans. Algorithms, 10(4): 18:1188 2014.
[31] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. GOT: an optimal transport framework for graph comparison. In NeurlPS, pages 13876-13887, 2019.
[32] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. fGOT: Graph distances based on filters and optimal transport. In AAAI, pages 7710-7718, 2022.
[33] Mark F. Newman. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74:036104, 2006.
[34] Sadegh Nobari, Panagiotis Karras, HweeHwa Pang, and Stéphane Bressan. L-opacity: Linkage- aware graph anonymization. In 17th International Conference on Extending Database Technol- ogy, EDBT, pages 583-594, 2014.
[35] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Grosov-Wasserstein averaging of kernel and distance matrices. ICML, pages 2664-2672, 2016.
[36] Roded Sharan and Trey Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 24:427-33, 05 2006.
[37] Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35) 2008.
12

---

[38] Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21:343-348. 1967.
[39] Konstantinos Skitsas, Karol Orlowski, Judith Hermanns, Davide Mottin, and Panagiotis Karras. Comprehensive evaluation of algorithms for unrestricted graph alignment. In Proceedings 26th International Conference on Extending Database Technology. EDBT, pages 260-272, 2023.
[40] Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary. Optimal transport for structured data with application graphs. In ICML, pages 6275-6284, 2019.
[41] Vipin Vijayan and Tijana Milenkovié. Multiple network alignment via MultiAANN+++. IEEE/ACM Transactions on Computational Biology and Bioinformaties, 1569:1666--162,, 2018.
[42] Joshua Vogelstein, John M Conroy, Vince Lyzinski, Louis J Podrazik, Steven G Kratzer, Eric T Harley, Donniell E Fishkind, R Jacob Vogelstein, and Carey E Priehe. Fast approximate quadratic programming for graph matching. PLOS one, 10(4))0011 21002, 2015.
[43] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable Gromov- Wassev-stnnn learning for graph partitioning and matching. In NeurlPS, pages 3046-3056, 2019.
[44] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov-Wass Wasserstein learning for graph matching and node embedding. In ICML, pages 6932-6941, 2019.
[45] Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12):2227-23 2242, 2009.
[46] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. PARROT: position-aware regularized optimal transport for network alignment. ACM Web Conference, WWW, pages 372-382, 2023.
[47] Si Zhang and Hanghang Tong. FINAL: fast attributed network alignment. In 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 1345-1354, 2016.
[48] Si Zhang and Hanghang Tong. Attributed network alignment: Problem definitions and fast solutions. IEEE Transactions on Knowledge and Data Engineering, 31(9):1680-1692, 2019.
[49] Feng Zhou and Fernando De la Torre Factorized graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(9):177-1178, 2016.
13

---

A
Appendix
Algorithm 2 FUGAL (Gi, G2)
Input: Graphs G1, 92
Output: Permutation matrix
1: \. STEP 1. Extract NetSimile Features
2: F < EXTRACTFEATURES/
3: F2 < EXTRACTFEATURES (G2
4: D EUCLEDIANDISTANCEE;;
5: \\ STEP 2. Approximate Optimization
6: Q ENDQUASIPEMUTAAIONNA B, 1,,, (,
7: STEP 3. Round to Permutation
8: P HUNGARIAN(Q)
9: returnP
Table 3: Parameters used in FUGAL.
Dataset
Arenas
0.5
inf-euroroad
2
bio-celegans
0.1
ca-netscience
MultiMagna
0.5
HighSchool
0.5
Voles
0.5
Newmann- -Watts
2
ACM-DBLP
0.1
A.1 Complexity Analysis
To assess the computational complexity of FUGAL, we examine the three primary components: (i) structural feature extraction; (ii) obtaining a quasi-permutation matrix; (iii) rounding to a permu- tation matrix. Let us consider source and target graphs G1, G2 with n nodes. Among NETSIMILEE structural features, the clustering coefficient incurs high computational cost of ( where is the maximum degree among vertices in the graph. Still, for real-world graphs conforming to a power-law degree distribution, the complexity for neighborhood features extraction is expected to be OnnMs,, with 0 < features takes (n²)) The crausi-prmmtatiion matrix derivation involves determining the gradient of the optimization problem. which requires Onz²) due matrix multiplications. The Sinkhorn Sinkhorn-Knopp algorithm finds the doubly-stochastic matrix ş minimizing (grad, q), is nearly (nn²) 7. while the update Q takes (n?)) time. Thus, the time complexity for finding muasi-permutationn matrix O(T n²), where is the number iterations. We round the quasi quasi-permutation matrix to a permutation matrix by the Hungarian algorithm, incurring time complexity of (n Therefore, the time complexity of FUGAL is O(T n²)). Empirically, I' typically ranges from 10 to 20, resulting in cost of Onn*) since T n. We provide computational costs of baselines in Appendix A.6 Table compares FUGAL'S computational cost to that of baselines.
[8]. while finding pairwise Euclidean distances between node
A.2 Running times for all baselines
Figure 9 presents the rumning times of various basclines the benchmark datasets. It is noteworthy that while some of these baselines exhibit better running times than FUGAL, the substantial disparity in accuracy, as previously demonstrated in $. renders comparison skewed in favor of FUGAL.
A.3 Accuracy on Real Graphs with Synthetic Noise Low Noise Range
In we have already demonstrated the superior performance of FUGAL in the presence noise levels ranging from 0% to 25%. In this section, extend the comparison to assess the performance
14

---

Table Computational Complexity comparison with baselines. n, m denotes the number of nodes and edges respectively. T, L denote the number of loop iterations.
CONE
looRank
S-GWL
GRAMPA
GRASP-B
FAQ
PARROT
IGOT
GOT
FOGAL
GW
FGW
Time (1,)
ma iog
mnn
Ths?
FUGUAAL MI CONE IsoRannk 3 118-GWL & GRAMPA & GRASP- 1 FAQ PARROT 1GOT I GW I
FGW
Time (sec)
102
100
10
MultiMagna
Voles
HighSchool
euroroad
arenas
Time (sec)
10
10a
10-2
netscience
celegans
NW
ACM-DBLP
Dataset
Figure Running times of all baselines.
of FUGAL and other baseline methods on real datasets with synthetic noise, specifically of One-Way and Multi-Modal types, within the range of 0% to 5%. The results are presented in Figure 10 On the inf-euroroad dataset, FUGAL consistently outperforms all baselines across varying noise levels in both One-Way and Multi-Modal scenarios. For the arenas dataset, FUGAL, CONE. S-GWL, PARROT, and GW maintain accuracy levels exceeding 95% consistently across all noise levels, whereas other baselines exhibit a decline in performance with increasing noise levels, particularly evident in the Multi-Modal scenario. the case of the ca-netscience dataset, both FUGAL and S-GWL achieve similar accuracy in both One-Way and Multi-Modal scenarios. On the bio-celegans dataset, S-GWL closely matches the performance of FUGAL in the One- Way scenario; however, with Multi-Modal noise, FUGAL achieves 6% improvement over the next-best method, S-GWL. The consistent and superior performance of FUGAL across all benchmark datasets underscores its robustness.
A.4 Evaluation on Small Graphs
To compare the performance of non-scalable methods like GOT, FGOT, PATH and DSPP with FUGAL, we employed small Erdós-Rényl Rényi random graphs [12. The limited scalability of these methods for larger graphs is empirically demonstrated Section 5 (failing to terminate within hours) as well as evidenced by the maximum graph size evaluated by the authors, which was 100. Following the methodology IGOT [32), we varied the node count n from 20 to 100, with edges generated using probability of 2 log(n)) (n) We also included S-GWL and PARROT in the analysis. The accuracy of these methods across different graph sizes is depicted in Figure II While FUGAL, S-GWL, and PARROT achieved perfect aligmment across all graph sizes, other methods exhibited notably inferior performance. Following (32). the Frobenius distance between aligned graph Laplacian matrices across varying graph sizes is also reported in Fi FUGAL,, S-GWL, and PARROT maintained an L2 Distance of 0 across all graph sizes, indicating perfect alignment, whereas the performance of other methods deteriorated with increasing graph size. These distance values closely align with those reported by the original authors in [32], validating our experimental setup.
A.5 Additional Metrics
We assess FUGAL against S-GWL and CONE in terms of Matched Neighborhood Consistency (MNC) and the Frobenius distance between aligned graph adjacency matrices. The results in Figure 12 indicate that FUGAL outperforms S-GWL and CONE across noise levels and noisy variants.
15

---

FUGAL CONE
IsoRank
S-GWI.
GRAMPA GRASP-B
FAQ
PARROT
fGOT
GW
FGW
inf-euroroad
arenas
ca-Netscience
bio-celegans
0.8
Accuracy
0.4
0.2
0
0
1
3
5
0
1
3
5
0
3
5
0
3
5
Noise
Noise
Noise
Noise
inf-euroroad
arenas
ca-Netscience
bio-celegans
0.8
Accuracy
0.4
0.2
0
1
3
5
0
1
3
5
0
3
5
0
3
5
Noise
Noise
Noise
Noise
Figure 10: Accuracy comparison for real datasets with noise ranging from 0% to 5%. Top row represents One-Wee Way noise, bottom row represents Multi-Modal noise scenarios.
FUGAL u S-GWL u
PARROT
fGOT
GOT
DSPP
PATH
60
0.8
L2 Distance
Accuracy
40
0.6
0.4
20
0.2
0
20
40
60
80
100
20
40
60
80
100
Graph Size
Graph Size
Figure 11: Performance comparison on Erdös-Rény' graphs. The performance is shown in terms of Accuracy (L) and the Frobenius distance between aligned graph Laplacian matrices (R) across different graph sizes (# of nodes).
A.6 Computational Complexity Analysis Baselines
The computational costs incurred by the baseline methods and FUGAL presented in Table is notable that all algorithms utilize the Hungarian algorithm to convert the similarity matrix into a permutation matrix, incurring a computational cost of O(n²). However, the costs reported in Table 4 solely pertain to the computation of the similarity matrix, excluding this operation. Among the baselines, CONE, S-GWL, and PARROT exhibit superior time complexity compared to FUGAL. However, demonstrated in Section 5 both CONE and PARROT fall significantly short of FUGAL in terms of performance. Despite the seemingly promising computational cost of S-GWL, our empirical analysis in Sections 5.3 and [36] re6eaeee slower running times compared to expectations. Moreover, S-GWL fails to scale for larger graphs such as ACM-DBLP (failing to terminate within hours), whereas FUGAL achieves superior accuracy within 40 minutes. The limited scalability of S-GWI. has been underscored by various studies [46] 19 39 28). Consequently, FUGAL emerges as a preferable option for attaining superior accuracy without incurring detrimental overhead.
16

---

FUGAL
S-GWL
CONE
MulniMagaa
-104
MultiMagna
0.8
Distance
0.8
MNC
0.6
0.6
0.4
0.4
0.2
0.2
0
0
1
2
4
5
3
4
Variant #
Variant #
inf-curoroad
inf-euroroad
4,000
0.8
L2 Distance
3,000
MNC
0.6
2,000
0.4
1,000
0.2
0
5
10
15
20
25
0
10
15
20
25
Noise
Noise
Figure 12: Comparison of FUGAL with S-GWL and CONE on MultiMagna and inf-euroroad datasets
terms of Matched Neighborhood Consistency (MNC) (L) and the Frobenius distance between aligned graph adjacency matrices (R) across different variants and varying noise respectively.
inf-euroroad
Newmann Watts
FUGAL
C2P3N1000
0.8
C2P3N100
Accuracy
C2P3N10
0.6
C4P2N1000
C4P2N100
0.4
C4P2N10
0.2
CSPINIOOS
CSPIN100
0
CSPIN10
20
40
60
10
30
40
50
Time (sec)
Time (sec)
Figure 13: Accuracy vs. Running time, FUGAL vs S-GWL variants, one-way noise 5%.
A.7 Accuracy Running Time
S-GWL employs recursive graph partition mechanism to accelerate graph alignment computations.
An important question is how the performance of SGWL affected by this recursive mechanism with respect FUGAL. We have identified that the hyper-parameters fluster_nmm (C), partition level (P), and node_prior (N) significantly influence the recursive partitioning process. Three variants of S-GWL proposed the authors 43 based different combinations of C and P: (C= 2, P 3). (C = 4, 2),), and (C=8, P= 1). Additionally, we vary the node_prion parameter within the set {10, 100, 1000]. These combinations result in nine distinct variants of S-GWL, denoted CxPyNz where x, y, 2 represent the values of C, P, and N respectively. We conduct comparative evaluation of FUGAL against these nine variants with respect both accuracy and running times jointly. Figure [3 depict the outcomes on the nuf-eurrooad and Newmann Watts datasets. For the inf-euroroad dataset, variants achieving comparable accuracy to FUGAL exhibit significantly higher running times, while those with lower running times have accuracy less than 20%. In the Newmann Watts dataset, none of the S-GWL variants approach the accuracy of FUGAL, as previously established Section 5 Notably, variants with reasonable accuracy tend to have longer running times, whereas those with better running times demonstrate poorer accuracy. These findings underscore the practical suitability of FUGAL for graph alignment, given its favorable balance between accuracy and running times.
17

---

FUGAL
FUGAL-I
inf-euroroad
HighSchool
0.8
Accuracy
0.6
0.4
0.2
0
5
10
15
20
25
100
90
80
Noise
% of edges
Figure 14: Accuracy, FUGAL vs FUGAL-I, one-way noise.
A.8 Effect of Initialization
Lastly, empirically examine decision to employ non-informative flat doubly stochastic matrix, denoted 1 17) /n, as the initial quasi-permutatioon matrix in Algorithm [ in contrast to alternatives. We try out variant of FUGAL, FUGAL-I, which utilizes the Identity matrix as the initial quasi-permutation matrix instead. Figure 14 presents two instances of our comparative evaluation of FUGAL-I vs FUGAL. While FUGAL-I closely reaches the accuracy of FUGAL on the inf-euroroad network, it falls short of FUGAL the HighSchool network, indicating its instability. These findings substantiate our selection of the flat doubly stochastic matrix as a robust choice for initialization.
4
6
5
01011
0
0.003
0.4781
0.0188
0.0001
0.0011
0
0.0188
Algorities End loration
1
4
A
0.0755
DIOTUS
0U125
04/10
0.005
0.0051
0
DI
0-710
G1
G2
Algoritm
0
00
0
0
0
0
Algorithn
-0 -
Figure 15: Operational stages of FUGAL. Values less than le 10 are approximated to 0.
A.9 Illustrative example of FUGAL'S pipeline
We illustrate the functionality of FUGAL through an example in Figure 15 We create source graph
G1 of 6 nodes and randomly permute it to target graph g2. We show three stages of FUGAL'S operation: (1) the doubly stochastic matrix Q, generated after the first iteration of Algorithm
(A = 0); (2) the quasi-permutation matrix Q to which Algorithm (Section 3 steers the doubly stochastic matrix; (3) the permutation matrix into which
refines this quasi-permutatiin matrix using the Hungarian algorithm. FUGAL aligns Gl and G2 perfectly.
18

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Sections
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
See Sections 3 Appendix A.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Section Appendix 5.7
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer: [Yes]
Justification: See Section
S
Appendix 5.7
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
httppsscccpbbbccpppeeccccc gwtp///ieee///ee/ Cooeeeoodeesssseeeeee http///bbb////uuuuoooooo//aaaaaa casssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
See Section Appendix 5.7
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The error bars compromising the visual interpretability of the plots due to the large number of baselines compared against.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section S
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://urrp..ccpplll//hccccccaaa
Question:
Answer: [Yes]
Justification: [NA].
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Section 6
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA].
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See Section 5
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Link codebase in Section 5
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA].
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "RTSxscbLNb", "reviewer": "Reviewer_T3ao", "summary": "The current work tackles the problem of graph alignment, where the objective is to find an optimal alignment between two graphs. The current work attempts an unrestricted approach by solving a QAP and augmenting it with a LAP regularizer for tractability. This is in contrast to past work where the matching happens in an embedding space or an intermediate representation of the original graph, which incurs loss of information and consequently reduces the performance. The QAP finds a permutation matrix directly on the adjacency matrices of both the graphs and the augmented LAP uses structural features of the nodes to enhance node similarity of the matchings.", "questions": "See above.", "limitations": "I stated the key limitations in the weakenesses.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- The problem is aimed at solving an important problem of graph alignment\n- The paper is clearly written\n- I checked out the code, it is quite clean", "weaknesses": "There are several weaknesses of the paper:\n\n1. I think the QAP problem has been well studied long before since 1990. See for example: https://www.math.cmu.edu/users/af1p/Texfiles/QAP.pdf.  \nhttps://link.springer.com/chapter/10.1007/978-1-4757-3155-2_6\nhttps://link.springer.com/article/10.1007/s12652-018-0917-x\nThe authors need to perform comprehensive comparison against such approximation algorithm literature, since this paper does fall in the domain of improving the optimization of QAP. Otherwise, this paper does not add significant value.\n\n\n2. One of the big advantage of embedding based graph alignment is during *test time* one does not have to re-optimize for alignment.\nWhile yes, data driven methods will never be as strong as procedural algorithms, but on the flip side, the procedural algorithm have to re-run for unseen graphs as well.  I was expecting a comprehensive analysis to investigate the trade off. Just reporting time and accuracy won't help. One needs to see the curve between accuracy and time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1. I think the QAP problem has been well studied long before since 1990. See for example: https://www.math.cmu.edu/users/af1p/Texfiles/QAP.pdf.\nhttps://link.springer.com/chapter/10.1007/978-1-4757-3155-2_6 https://link.springer.com/article/10.1007/s12652-018-0917-x The authors need to perform comprehensive comparison against such approximation algorithm literature, since this paper does fall in the domain of improving the optimization of QAP. Otherwise, this paper does not add significant value.**\n\n*Answer:* The comments appears to step from a misunderstanding on the objective . **The objective of our work is not approximating QAP**. The objective **is network alignment**, which, among other formulations, can be formulated as an instance of QAP. Hence, we are not aiming to provide the best approximation for any given QAP, but for the specific network alignment instances. Our comprehensive empirical comparison already involves comparison with _11 state-of-the-art baselines_ for the network alignment problem, as evident from this survey [3]. On the other hand, due to the QAP formulation our study already included the FAQ baseline, that adopts the QAP approach for network alignment. Yet, FAQ fails to achieve competitive performance. To further shed light between graph alignment and QAP, we have added two more QAP-based baselines for network alignment [1, 2]. The experiments reveal the same pattern (See Fig. 1 in the pdf attached to global response), i.e., vanilla QAP formulations attain significantly worse results in graph alignment. \n\nThe *value* of our work lies designing effective regularizers, that leverage and integrate various network-based features such as degree, clustering coefficient, etc., to the vanilla QAP, and a customized optimization strategy that empowers it to **achieve state of the art performance for network alignment.** \n\nWe do not claim to have designed a state of the art QAP approximation algorithm. Rather, we assert that our method, which combines QAP with carefully selected network-based regularizers and optimization strategies, achieves state-of-the-art performance specifically for network alignment problems.\n\n[1] Zaslavskiy, M., Bach, F., & Vert, J. P. (2008). A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227-2242.\n\n[2] Nadav Dym, Haggai Maron, and Yaron Lipman. 2017. DS++: a flexible, scalable and provably tight relaxation for matching problems. ACM Trans. Graph. 36, 6, Article 184 (December 2017).\n\n[3] Konstantinos Skitsas, Karol Orlowski, Judith Hermanns, Davide Mottin, and Panagiotis Karras., Comprehensive evaluation of algorithms for unrestricted graph alignment. EDBT 2023.\n\n**W2. One of the big advantages of embedding based graph alignment is during test time one does not have to re-optimize for alignment. While yes, data driven methods will never be as strong as procedural algorithms, but on the flip side, the procedural algorithm have to re-run for unseen graphs as well. I was expecting a comprehensive analysis to investigate the trade off. Just reporting time and accuracy won't help. One needs to see the curve between accuracy and time.**\n\n*Answer:* To our knowledge, no embedding-based method has demonstrated competitive performance in network alignment. Moreover, supervised embedding approaches typically require dataset-specific training. This raises questions about the feasibility of performing inference on unseen test graphs without retraining. We would welcome information about any published, peer-reviewed algorithm that contradicts these observations. If such work exists, we would be happy to compare.\n\n**Accuracy-time trade-off:** The accuracy-time tradeoff against S-GWL, which is well established as the state-of-the-art, is already included in Fig. 11 along with a detailed discussion in Appendix A.7. At best, S-GWL achieves 20% lower accuracy when restricted to the running time of FUGAL. In addition, it never approaches the same accuracy as FUGAL.\n\n-------\n\n# Appeal to the reviewer\n\nWe hope that our clarification on the scope and objectives of our work has provided a better context for our research. In response to the comments received, we have made several significant enhancements to our manuscript:\n\n1. Added two more QAP-based baselines [1,2] \n2. Introduced new metrics to provide a more robust assessment of performance\n3. Included additional ablation studies to deepen the understanding of our method's components\n\nThese empirical enhancements further substantiate our claim of advancing the state of the art in network alignment. In light of these improvements, we kindly request you to reassess our work and consider adjusting the rating accordingly. We would be glad to engage in further discussion during the author-reviewer period if you have any additional concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XIxB3e5tl6", "reviewer": "Reviewer_b2PL", "summary": "The paper presents FUGAL, a method for aligning graphs by finding a permutation matrix. FUGAL is an unrestricted method as it (also) operates on adjacency matrices, unlike most methods that rely only on intermediary graph representations.\nFUGAL combines a Quadratic Assignment Problem (QAP) with a Linear Assignment Problem (LAP). The QAP focuses on finding the permutation matrix directly on the adjacency matrices, while the LAP works on node feature vectors built using structural features. Essentially, FUGAL augments the QAP with a LAP regularizing term. An initial algorithm is defined to find a quasi-permutation matrix  Q . Then, the authors propose refining  Q  using the Hungarian algorithm. Interestingly, FUGAL relaxes the solution space to doubly stochastic matrices.", "questions": "Here are some suggestions and comments:\n\n- Probably, a paragraph summarizing those cases in which the method works well and when it might perform poorly is missing. Maybe I missed something, but sections 5 and 6 should include the limitations as per your “NeurIPS Paper Checklist,” though they might not be well emphasized.\n\n- In Chen, X., Heimann, M., Vahedian, F., & Koutra, D. (2020, October). “Cone-align: Consistent network alignment with proximity-preserving node embedding.” In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (pp. 1985-1988) [CONE], there is an experiment on MNC and matched neighborhood consistency. Specifically, I refer to Figure 4. I suggest conducting a similar experiment, even if just to add in the appendix for further comparison.\n\n- In Figure 1, using the variants of MultiMagna instead of $q$ may confuse the reader slightly.\n\n- I wonder if the multimagna dataset you used corresponds to the PPI dataset used, for example, in [CONE] and also used in Xu, H., Luo, D., & Carin, L. (2019). “Scalable Gromov-Wasserstein learning for graph partitioning and matching.” Advances in neural information processing systems, 32.\n\nIf PPI is multimagna, in other works, such as in [CONE], I see that they used the average accuracy with standard deviation in error bars. You mentioned that “The error bars are compromising the visual interpretability of the plots due to the large number of baselines compared against,” but these values are significant, so at least in the appendix, I would suggest to visualize some by rearranging the plots.\n\n- Regarding sensitivity analysis, I refer, for example, to the structural features. It is possible that only one of these features is actually useful or very influencing. I understand that this is not the focus of your method, but it would be interesting to see the influence of these node features for completeness.", "limitations": "Including some sentences that clearly stree the method's limitations would improve the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well-written and the method is well-presented, especially in Section 3. The idea of combining QAP and LAP leads to an elegant solution, and the fact that it does not use intermediary graph representations distinguishes it significantly from other methods.", "weaknesses": "The authors do not clearly define the limitations of their method, and there is no clear sensitivity analysis or ablation study of certain aspects. \nBesides, there is a complete lack of statistical significance analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Probably, a paragraph summarizing those cases in which the method works well and when it might perform poorly is missing. Maybe I missed something, but sections 5 and 6 should include the limitations as per your “NeurIPS Paper Checklist,” though they might not be well emphasized.**\n\n*Answer:* Our discussion on the limitations of FUGAL is interspersed in the discussion in Sections 5 and 6. These include:  \n- In _line 325-326_, we point out that S-GWL is more efficient that FUGAL on small graphs. \n- In _line 566_, we complement that CONE, S-GWL, and PARROT exhibit superior time complexity compared to FUGAL. \n- In _Section 6_, we highlight the ethical aspect that advances in graph alignment also enhance the abilities of attackers attempting to de-anonymize sensitive network data. \n\nAs suggested, we will collect them into a single paragraph to emphasize them more prominently.\n\n**Q2. In Chen, X., Heimann, M., Vahedian, F., & Koutra, D. (2020, October). “Cone-align: Consistent network alignment with proximity-preserving node embedding.” In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (pp. 1985-1988) [CONE], there is an experiment on MNC and matched neighborhood consistency. Specifically, I refer to Figure 4. I suggest conducting a similar experiment, even if just to add in the appendix for further comparison.**\n\n*Answer:* As suggested, we have added *matched neighborhood consistent (MNC)* and *Frobenius Norm* as additional metrics. The results are presented in `Fig. 2 of the PDF attached to the global response`. These new metrics align with our previous findings using the accuracy metric, further vindicating FUGAL's superior performance across multiple evaluation criteria.\n\n**Q3. In Figure 1, using the variants of MultiMagna instead of $q$ may confuse the reader slightly.**\n\n*Answer:* We will change the $x$-axis to $q$ as suggested.\n \n **Q4. I wonder if the multimagna dataset you used corresponds to the PPI dataset used, for example, in [CONE] and also used in Xu, H., Luo, D., & Carin, L. (2019). “Scalable Gromov-Wasserstein learning for graph partitioning and matching.” Advances in neural information processing systems, 32.**\n \n *Answer:* Yes, these two refers to the same dataset.\n \n**Q5. If PPI is multimagna, in other works, such as in [CONE], I see that they used the average accuracy with standard deviation in error bars. You mentioned that “The error bars are compromising the visual interpretability of the plots due to the large number of baselines compared against,” but these values are significant, so at least in the appendix, I would suggest to visualize some by rearranging the plots.**\n\n*Answer:* Thanks for the suggestion. We will add standard deviation in the appendix.\n\n**Q6. Regarding sensitivity analysis, I refer, for example, to the structural features. It is possible that only one of these features is actually useful or very influencing. I understand that this is not the focus of your method, but it would be interesting to see the influence of these node features for completeness.**\n\n*Answer:*  We already include experiments on feature ablation study and the impact of setting both $\\lambda=0$ and $\\mu=0$ in Eq. 13. We have now also added the third ablation of only $\\lambda=0$. Specifically:\n\n* **Features:** We have a detailed ablation study in Appendix A.3 (referred from Section 5.2 in main manuscript), where we systematically turn on each feature and study its impact (Fig 8). The results reveal that degree is the most important feature, followed by the mean degree of neighbors. \n\n* **$\\lambda=0$ and $\\mu=0$:** This setting degenerates to the FAQ method, already present in our experimental evaluation. As evident from our experiments, the deterioration in efficacy is significant.\n\n* **$\\lambda=0$:** We have added this experiment now. `Fig. 3 in the pdf attached to the global rebuttal` presents the results. We see clear evidence that if $\\lambda$ is not iteratively increased (recall Alg. 1), the performance is compromised.\n\n------------\n\n# Appeal to the reviewer\n\nWith the inclusion of additional metrics, ablation studies and clarifications, we hope the reviewer finds our manuscript improved. If the reviewer agrees, we would appreciate support for our work by increasing the rating accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lI5nohsg8Z", "reviewer": "Reviewer_FAZB", "summary": "The paper proposes FUGAL, a method for graph alignment by using additional features of nodes to guide optimization of a relaxed problem. It combines strengths of 2 lines of methods, using full graph information and structural features enrichment.\n\n--- \nscore raised after rebuttal.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the paper blends the approach in a reasonable way to take the advantages of mediated  and unmediated approaches. The idea seems right and its formulation seems sound. It has very good performance to back up the choices in the method.", "weaknesses": "This is not a totally novel approaches but it is understandable given the nature of the combinatorial optimization problem.  \n\nThere should be a lot of room for improvement in terms of the structural features used in the paper. There might be many more to choose from. Depending on the nature of the application domain, some feature sets may make sense more than other. Some additional analysis on this part might be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments on our work. Please find below some clarifications on the queries posed.\n\n**W1. Clarification on novelty**\n\n*Answer.* The novelty of our work lies in: \n1. crafting a regularizer using network features that makes the QAP potent for network alignment. State of the art algorithms for network alignment had generally moved away from a QAP based formulation due to its non-competitive performance\n2. Devising a novel optimization strategy wherein we guide the Frank-Wolfe algorithm through a Sinkhorn distance objective, and gradually steer the resulting doubly stochastic solution towards a quasi-permutation matrix.\n\nWith these innovations, we design an algorithm that outperforms 13 different baselines in a comprehensive empirical benchmarking exercise and achieves state-of the-art-performance.\n\n**W2. There should be a lot of room for improvement in terms of the structural features used in the paper. There might be many more to choose from. Depending on the nature of the application domain, some feature sets may make sense more than other. Some additional analysis on this part might be interesting.**\n\n*Answer.* We'd like to draw your attention to Appendix A.3 (referenced in Section 5.2 of the main manuscript), where we've already included a comprehensive ablation study examining the importance of each feature (Fig. 8). Our findings indicate that degree is the most crucial feature, closely followed by the mean degree of neighbors.\n\nWe concur with your insight that identifying other beneficial structural features remains an open research question. This point is explicitly addressed in lines 128-131 of our manuscript. To further supplement this analysis with empirical data, we further expanded our feature ablation study by covering more node features spanning PageRank (PR), Eigen Centrality (EC) and Closeness Centrality (CC). \n\nThe table below compares the efficacy of using only one of these features as opposed to the 4 vanilla features used in Fugal (degree, mean degree of neighborhood, clustering coefficient, mean clustering coefficient in neighborhood). The experiment is performed on the ca-netscience dataset at various noise levels. Among individual features, we note Degree to have the maximal impact and closely followed by PageRank. This result is not surprising given that PageRank is correlated to degree. Overall, Fugal, which uses 4 features, continues to be superior to relying on any single feature. \n\n#### **Caption**: Accuracy in the ca-netscience dataset at various noise levels. Fugal represents the default version that uses the four features mentioned above (and in Section 3.1). The other columns represent the accuracy achieved when only the corresponding feature is used in the LAP regularizer.\n\nNoise\t| CS\t| Degree|\tEC|\tPR\t| Fugal \n---|---|---|---|---|--\n0|\t0.70\t|0.71|\t0.70\t|0.70\t|0.70\n5|\t0.67\t|0.70|\t0.67\t|0.69\t|0.68\n10|\t0.57\t|0.67|\t0.61\t|0.64\t|0.67\n15|\t0.52\t|0.63|\t0.51\t|0.55\t|0.61\n20|\t0.34\t|0.56|\t0.39\t|0.53\t|0.57\n25|\t0.35|\t0.48|\t0.27|\t0.46|\t0.53\n\nThe effectiveness of features can vary across datasets due to differences in network properties. Automatically selecting optimal features would require shifting to a supervised pipeline. We must also consider feature interactions, as individually informative features may not provide any marginal improvement when combined. The optimal feature set needs to account for potential signal overlap. However, this approach would demand training on each specific dataset, substantially increasing our framework's computational demands. This dataset-specific optimization, while potentially more accurate, would significantly complicate the overall process.\n\nWe will include the above discussion in our revision.\n\n-------------------\n\n# Appeal to the reviewer\n\n If the reviewer feels satisfied with the clarifications provided, we would appreciate support for our work by adjusting the rating accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wB6XMmfmdU", "reviewer": "Reviewer_ts95", "summary": "In this paper, the authors propose an algorithm for graph matching. The method is based on the classical relaxation to the set of doubly stochastic matrices, where the authors add two variants to the optimization: (1) an additional term to match node features (computed from the graph as degree, clustering coefficient, and others), and (2) an extra term to push the matrix to be closer to a permutation matrix. The paper presents some promising experimental evaluations.", "questions": "In Algorithm 1, the number of iterations T is the value for lambda??\nWhy does lambda vary in the integers? And how is the value of lambda chosen?\n\nWhen you change the problem of finding the q minimizing the inner product with grad, with the formulation in eq (16), the solution is not guaranteed to be the same.\nHow do you choose the lambda in this case? (also, not a good idea to use the same name for different parameters)\n\nIn line 179, the rounding process is the same as projecting the solution to the set of permutation matrices? Because this projection is solved exactly as an LAP with the Hungarian algorithm for example.\nAlso, why use the Hungarian algorithm and not the Sinkhorn formulation here? It is the same problem.\n\nMinor comment:\nIn line 33, there's a word missing (method?) \"In this work, we propose an unrestricted graph alignment m that avoids restricting ...\"", "limitations": "There's no explicit mention of any limitation of the algorithm.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper is well written in general. The strength of the paper is the combination of a classical formulation (the relaxation to doubly stochastic matrices, and I would add the features-term as classical as well) with a new term in the optimization, pushing the solution closer to a permutation matrix. Although the paper has no theorethical guarantees at all, it provides some experimental evaluation.", "weaknesses": "One huge weakness is the absolute lack of references to related work.\nIn the paper (line 57), the authors say that FAQ is the only algorithm addressing the graph matching (they say the QAP, actually) problem directly through the adjacency matrices. This is profoundly inaccurate. \nHere are some references, some of them with formulations extremely related to the one presented in this paper. Most of them pose the problem by relaxing to the set of doubly stochastic matrices. Some of them add a term for \"feature matching\" (like [1] and [3], equation (21) in [1] adds exactly the same term as in eq (7) in this paper). And some of them add an extra term pushing the doubly stochastic matrix closer to a permutation matrix (as presented in this paper), for instance [1] and [6].\n\n[1] Zaslavskiy, M., Bach, F., & Vert, J. P. (2008). A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227-2242.\n\n[2] Fiori, M., Sprechmann, P., Vogelstein, J., Musé, P., & Sapiro, G. (2013). Robust multimodal graph matching: Sparse coding meets graph matching. Advances in neural information processing systems, 26.\n\n[3] Zhou, F., & De la Torre, F. (2015). Factorized graph matching. IEEE transactions on pattern analysis and machine intelligence, 38(9), 1774-1789.\n\n[4] Aflalo, Y., Bronstein, A., & Kimmel, R. (2015). On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112(10), 2942-2947.\n\n[5] Fiori, M., & Sapiro, G. (2015). On spectral properties for graph matching and graph isomorphism problems. Information and Inference: A Journal of the IMA, 4(1), 63-76. \n\n[6] Nadav Dym, Haggai Maron, Yaron Lipman. (2017) Ds++: A flexible, scalable and provably tight relaxation for matching problems\n\n\nThis makes the experimental section kind of weak also, since at least I would have compared with [1] and eventually [6].\n\nBesides that, to me the experimental section lacks an experiment showing the gain from each addition to the vanilla formulation. This is, what is the difference in performance with and without the features, and lambda=0 vs other lambda.\n\nAnother weakness is the lack of theoretical results in terms of guarantees of the method, or at least a comment on which part has or has not guarantees. For instance, the formulation is guaranteed to obtain the solution for some graphs? (in the spirit of Aflalo et. al [4]). The optimization algorithm is guaranteed to obtain a local minima?\nI understand the properties of the FW method, but I'm not sure that the presented algorithm solves exactly every sub-process of the FW method.\n\nAnother comment is the way of measuring the error. The authors measure the coincidence between the obtained permutation matrix and \"the\" true isomorphism. However, there may be many solutions, if the graph has nontrivial automorphism group (hence the \"the\" in the previous sentence). This is the case for instance of the graph presented in the paper in Figure 13. \nA more suitable measure could be $||AP-PB||_F^2$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1(a). Lack of references: the authors say that FAQ is the only algorithm addressing the graph matching (they say the QAP, actually) problem directly through the adjacency matrices. This is profoundly inaccurate. [1]-[6]** \n\n**Answer:** We apologize for the lack of precision in our original statement. Our intent was to convey that FAQ is one of the few algorithms that solves QAP for network alignment **without** introducing additional regularizers, which we term the *unmediated* approach. As defined in footnote 1, when QAP is augmented with mediated features, such as in our regularizer and several other algorithms (e.g., PATH [1] using feature matching, [6] employing all pairs shortest paths, [3] with feature matching, and [4] utilizing vector attributes), they fall into *unrestricted* category.\n\nWe acknowledge that our initial claim about FAQ being the only unmediated approach was incorrect. GLAG [2] is also an unmediated approach and we will revise our statement accordingly. Besides, [7] shows that GLAG's relaxation leads to worse alignments than FAQ.\n\n[7] Lyzinski, V. et al. Graph matching: Relax at your own risk. PAMI, 2015.\n\n**W1(b) Compare with [1] and [6].**\n\n**Answer:** We have incorporated PATH[1] and DDSP[6]. `Fig. 1 in the pdf attached to the global rebuttal` presents the results. Both baselines fall short compared to FUGAL. Furthermore, as the graph sizes grow, the performance gap widens.\n\nAdditionally, both algorithms are prohibitively slow and fail to return an alignment within 5 hours even on the smallest real-world dataset in our experiments, ca-netscience. Hence, we report results on synthetic datasets. [7] (cited above) have shown FAQ to outperform Path.\n\n**W2. What is the difference in performance with and without the features, and lambda=0 vs other lambda.**\n\n**Answer:** We already include experiments on feature ablation study and the impact of setting both $\\lambda=0$ and $\\mu=0$. We have now also added the third ablation for $\\lambda=0$. \n\n* **Features:** We have a detailed ablation study in Appendix A.3 (referred from Section 5.2 in main manuscript), where we systematically turn on each feature and study its impact (Fig 8). The results reveal that degree is the most important feature, followed by the mean degree of neighbors. \n\n* **$\\lambda=0$**: `Fig. 3 in the pdf attached to the global rebuttal` presents the results. If $\\lambda$ is not iteratively increased (recall Alg. 1), the performance suffers.\n\n**W3(a). Is the formulation guaranteed to obtain the solution for some graphs? (like [4]).** \n\n**Answer:** We do not have guarantees of an optimal solution for any specific class of graphs.\n\n**W3(b). Is the optimization algorithm guaranteed to obtain a local minima?**\n\n**Answer:** The problem is not convex due to the regularizer that guides the solution towards a permutation matrix. In this scenario, we do not guarantee obtaining local minima. However, as discussed in W2, the proposed strategy of iteratively increasing $\\lambda$ yields better accuracy. \n\n**W3(c). I'm not sure that the presented algorithm solves exactly every sub-process of FW.**\n\n**Answer:** It does. Each iteration of the algorithm uses FW within which we employ optimal transport to determine the doubly-stochastic matrix $q$ that minimizes the inner product with $grad$. However, across iterations, we increment $\\lambda$ to guide the solution towards a permutation matrix.\n\n**W4. ...A more suitable measure could be $||AP-PB||_F^2$.**\n\n**Answer:** We have added *Frobenius Norm*, as well as, *matched neighborhood consistency (MNC)* as additional metrics. The results are presented in `Fig. 2 of the PDF attached to the global response`. Consistent with the accuracy results, FUGAL maintains its competitive edge. \n\n**Q1. In Alg. 1, the number of iterations T is the value for lambda?? Why does lambda vary in the integers? And how is the value of lambda chosen?**\n\n**Answer:** Yes, $\\lambda$ varies from 0 to $T-1$ in integers. We set $T$ to $15$ across all datasets. Varying $\\lambda$ in the integers is just an empirical decision; it's not a constraint. Both $T$ and the granularity of increasing $\\lambda$ are hyper-parameters. We choose $T=15$ since at this value FUGAL demonstrates robust accuracy across all datasets.\n\n**Q2. When you change the problem of finding the $q$ minimizing the inner product with grad, with the formulation in eq (16), the solution is not guaranteed to be the same. How do you choose the lambda? (also, not a good idea to use the same name for different parameters)**\n\n**Answer:** We set $\\lambda=1$ across all datasets. We will update the variable name and mention this hyperparameter setting in  App. A.3.\n\n**Q3(a). In line 179, the rounding process is the same as projecting the solution to the set of permutation matrices? Because this projection is solved exactly as an LAP with the Hungarian algorithm.** \n\n**Answer:** Our rounding algorithm employs maximum weight matching using the Hungarian method. We construct a complete bipartite graph, with nodes from graphs A and B forming the two partite sets. Edge weights correspond to the values in the quasi-permutation matrix produced by Alg. 1. The Hungarian algorithm determines the optimal one-to-one mapping between the node sets, maximizing the cumulative weight of the selected edges. \n\n**Q3(b). why use the Hungarian and not Sinkhorn here?**\n\n**Answer:** Sinkhorn projects the matrix into the space of doubly stochastic matrices. But we need a permutation matrix as output, hence the Hungarian.\n\n**Q4. In line 33, there's a word missing (method?)**\n\n**Answer.** We'll correct this.\n\n----------\n\n# Appeal to the reviewer\n\nThank you for helping us with actionable comments on our work. We have comprehensively incorporated _all_ suggestions by adding new baselines, ablation studies, metrics, and clarifications. We would be grateful if the reviewer could reassess our paper in light of these improvements and consider adjusting the rating accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewers for their insightful and constructive feedback. Below, we provide a comprehensive point-by-point response to their comments. Additionally, we attach a PDF document containing plots of several new empirical analyses as suggested by the reviewers. The key revisions and insights include:

1. **Enhanced Empirical Benchmarking:**
   * Integration of two new QAP-based baselines: Path [1] and DSPP [2]. (`Fig. 1 in PDF`)
   * Addition of Frobenius Norm and Matched Neighborhood Consistency performance measures. (`Fig. 2 in PDF`)
   * Enhanced ablation study highlighting the importance of each feature in the LAP regularizer and the impact of $\lambda$ in guiding the doubly-stochastic matrix towards a quasi-permutation matrix. (`Fig. 3 in PDF`)

2. **Expanded Related Works:**
   * We will cite and discuss various related works pointed out by Reviewer `ts95`. Two of these works [1,2] have been incorporated as new baselines. 

3. **Clarifications and Improvements:**
   * We provided will better highlight the theoretical characterization of our work on algorithm convergence and termination.
   * Better consolidation of limitations and future scope for improvement.
   * Incorporation of standard deviation and other plot enhancements as suggested by Reviewer `b2PL`.

We believe these revisions significantly strengthen our manuscript. We are open to further engagement with the reviewers for any additional queries or suggestions. In light of these improvements, we kindly request the reviewers to reassess their ratings of our work.


[1] Zaslavskiy, M., Bach, F., & Vert, J. P. (2008). A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227-2242.

[2] Nadav Dym, Haggai Maron, and Yaron Lipman. 2017. DS++: a flexible, scalable and provably tight relaxation for matching problems. ACM Trans. Graph. 36, 6, Article 184 (December 2017).

Meta-review: The paper considers the problem of graph alignment, where the objective is to find an optimal alignment between two graphs, and it attempts to solve the problem wht a QAP and augmenting it with a LAP regularizer for tractability. The QAP finds a permutation matrix directly on the adjacency matrices of both the graphs and the augmented LAP uses structural features of the nodes to enhance node similarity of the matchings.  Reviewers saw novelty in the method, and good evaluation.  One outlying reviewer seemed to ask for clarifications and improvements that were not the main focus of the paper.
Decision: Accept (poster)