FUGAL: Feature-fortified Unrestricted Graph Alignment

Authors: aditya  bommakanti
harshith  reddy vonteri
konstantinos  skitsas
sayan  ranu
davide  mottin
panagiotis  karras
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 11:27:59

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.

Main paper: 
 introduction and related work: 
 Graph alignment seeks to match a pair of graphs to each other, i.e., 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 as 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 one 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 [5, 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 APX-hard to approximate even within an approximation factor that grows linearly with the number of nodes [30, 13] .Owing to the problem's hardness, several heuristics have been proposed. Nevertheless, state-of-the-art graph alignment 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 to 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 to solve the QAP. In the subsequent discussion, we summarize the various mediated and unmediated approaches in the literature.Mediated Approaches: GWL [44] jointly learns embeddings and alignments using the dissimilarity notion of Gromov-Wasserstein 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 [20] 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 a node pair using the score of their neighbors. GRAAL [25] is a greedy alignment method that matches nodes using a similarity score based on a 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. fGOT [32] adopts a dissimilarity metric that aligns two graphs using the probability distribution of data generated via graph filters. PARROT [46] presents a semi-supervised methodology which encodes graph topology through random walks with restart (RWR) for a position-aware transport cost and addresses a regularized Optimal Transport (OT) problem to determine node mappings. GW [35] and FGW [40] compute Gromov-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 § 5, 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 all-pairs-shortest-paths for graph alignment. We characterize these methods as unrestricted, since they also avail of help from mediated representations. As we will see in § 5, these methods are significantly inferior to FUGAL in terms of accuracy.Optimization problem formulation: We present FUGAL (Feature-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 a 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] to steer the resulting doubly stochastic solution towards a quasi-permutation 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 state-of-theart graph alignment methods in accuracy without a detrimental efficiency overhead.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: See Sections 3, 4, 5.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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem formulation: 
 Definition 2.1. Let G(V, E) denote an unlabelled, undirected graph, where V is the set of nodes each identified by a number [n] = {1, . . . , n} and E ⊆ V × V is the edge set. The adjacency matrix of G is A ∈ {0, 1} n×n such that a ij = a ji = 1 if and only if (i, j) ∈ E.We denote an all-ones vector as 1, an all-ones square matrix as J, and an all-zero square matrix as O. The dimensions of entities are inferred from the equations employing them. Definition 2.2. We denote the set of binary-valued permutation matrices as P n = {P ∈ {0, 1} n×n : P1 = 1, P ⊤ 1 = 1} and that of real-valued doubly stochastic matrices asW n = {W ∈ [0, 1] n×n : W1 = 1, W ⊤ 1 = 1}. Definition 2.3. Let A = [a ij ] i∈[n],j∈[m] ∈ R n×m .We denote the Frobenius norm as the entry-wise2-norm ∥A∥ F = n i=1 m j=1 |a ij | 2 1 /2. 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)) = 0 is a permutation matrix.Proof. From tr(A ⊤ (J -A)) = 0 follows that i j a ij • (1 -a ij ) = 0. Since A is doubly- stochastic, 0 ≤ a ij ≤ 1 for all i and j. Thus, a ij • (1 -a ij ) ≥ 0 for 1 ≤ i, j ≤ n. Therefore, a ij • (1 -a ij ) =0 for all i and j. As a consequence, a ij ∈ {0, 1} for each i and j. Given that A is doubly-stochastic and all its entries are either 0 or 1, by Definition 2.2, A is a permutation matrix.Problem 1 (Unmediated Graph Alignment). Consider two graphs G 1 := (V 1 , E 1 ) and G 2 := (V 2 , E 2 )with adjacency matrices A, B respectively. The objective of unmediated graph alignment is to identify a bijection f : V 1 → V 2 between the two graphs that minimizes the number of edge disagreements. Formally, the problem is expressed as:EQUATIONwhere P n denotes the set of permutation matrices.The appellation unmediated denotes that we seek a correspondence among nodes without using any information other than the adjacency matrix. The problem is an instance of the NP-hard quadratic assignment problem (QAP) [24] .Due to the problem's hardness, a popular approximation path utilizes intermediaries such as node embeddings. A mediated graph alignment is thus expressed as a linear assignment between embeddings rather than a quadratic assignment between adjacency matrices:EQUATION)whereE k ∈ R |V k |×F is the embedding matrix of G k and E k [i, :] is the F -dimensional vector representation of node i of G k .The optimization problem in Equation ( 2) is a linear assignment problem (LAP), which is solvable optimally in O N 3 by the Hungarian algorithm [26] , while sub-optimal solutions reduce complexity to O N 2 .Extension to graphs of unequal sizes. Consider two graphs G 1 and G 2 with node counts n 1 and n 2 , respectively (n 1 < n 2 ). To enable alignment despite the size difference, we augment G 1 with (n 2 -n 1 ) isolated dummy nodes and discard mappings involving dummy nodes from the output.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Section 5, 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
fugal: 
 To design FUGAL, we augment the core QAP of Eq. ( 1) with a LAP supplement that leverages simple structural graph features ( § 3.1) to form a unified optimization problem over the set of permutation matrices P n ( § 3.2). As this problem is NP-hard, we relax its solution space to the set of doubly stochastic matrices W n ( § 3.3), a superset of the set of permutation matrices. We refine the solution to obtain a quasi-permutation matrix, i.e., almost a permutation matrix, which we adjust to a 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.Here, we formalize the Linear Assignment Problem (LAP), which is auxiliary to our framework. We construct a node feature vector using four structural features proposed in NETSIMILE [2] . This includes (1) d i , the degree of node v i , (2) c i , the clustering coefficient of v i , (3) dNi , the mean degree of v i 's neighbors, (4) and cNi , the mean clustering coefficient of v i 's neighbours. Other features, such as betweenness centrality, PageRank, may also be 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, we construct a feature matrixF k ∈ R |V k |×4for each graph G k and, by the rationale that the structural features of corresponding nodes are similar, we formulate a Linear Assignment Problem for G 1 and G 2 as:EQUATION)By the Frobenius norm definition, Eq. ( 3) is equivalent to:EQUATION)Utilizing the property of permutation matrices that each row contains only one 1, we reformulate Eq. ( 4) to: minEQUATION)where D is a distance matrix with D ij denoting the squared Euclidean distance between F 1 [i, :] and F 2 [j, :]. Since each row P[i, :] contributes exactly one term to this sum, being the element of D corresponding to the single 1 entry in P[i, :], the result is equal to the trace of the matrix product:EQUATIONOur problem formulation augments the QAP of Eq. ( 1) with a LAP regularizing term as in Eq. ( 6):EQUATIONwhere A and B denote the adjacency matrices of G 1 and G 2 , respectively, D follows Eq. ( 6), and µ regulates the LAP's significance; since PP ⊤ = I, this is expanded to:EQUATIONequivalently, ignoring constant terms and reversing the sign,EQUATIONIn the case of µ = 0, the first term alone corresponds to the maxQAP problem [30] , which is APX-hard 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 we relax combinatorial constraints.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 n , as considered in FAQ [42] : EQUATION1: Q ← 1 • 1 ⊤ /n 2: for λ = 0 to T -1 do 3: for it = 1 to 10 do 4: grad ← ∇f (Q) + λ • ∇g(Q) 5:qit ← arg min q∈W n ⟨grad, q⟩ \\ Sinkhorn-Knoppα ← 2 2+it 7:Q ← Q + α • (qit -Q)8: end for 9: end for 10: return Q Since the problem in Eq. ( 10) calls to minimize a function subject to linear constraints implied by P ∈ W n , the solution can be efficiently found [3] by algorithms such as Adam [23] and Frank-Wolfe [16] . The FAQ algorithm [42] follows such an approach to solve the relaxed optimization with the Frank-Wolfe algorithm and project the solution back onto P n , yet addresses exclusively the first, QAP term in Eq. (10) . To further augment quality, as we elaborate later in Section 5, we include the LAP term in Eq. ( 10) and also add a regularizing term that guides the solution towards a quasi-permutation matrix. By Theorem 2.5, which establishes that a doubly-stochastic matrix P with tr(P ⊤ (J -P)) = 0 is a permutation matrix, we rewrite the problem in Eq. ( 9) as:min P∈W n -tr(APB ⊤ P ⊤ ) + µ • tr(P ⊤ D)Constraints: tr(P ⊤ (J -P)) = 0 (11) and turn the constraint to a regularizer with parameter λ:EQUATIONEquivalently, by reformulating the constraints:min P -tr(APB ⊤ P ⊤ ) + µ • tr(P ⊤ D) + λ • (tr(P ⊤ (J -P)))EQUATIONWe solve the problem in eq. ( 13) for λ = 0 by the Frank-Wolfe (FW) algorithm [16] with updates guided by an objective computed via the Sinkhorn-Knopp algorithm [7] , due to the computational efficiency they confer. We use the solution to this optimization problem as a warm start, and refine it by gradually increasing λ over T iterations, each initiating with the solution obtained in the preceding one and solving the problem in Eq. ( 13) by FW. Alg. 1 outlines the process.Rounding Algorithm: Alg. 1 yields a quasi-permutation matrix Q. Next, to obtain an one-to-one mapping between nodes of G 1 and G2, we need to adjust Q to a permutation matrix by rounding. We pose this problem as an assignment problem, maximizing the sum of Q ij entries selected for rounding up to 1, while rounding the rest down to 0, and solve it optimally by the Hungarian algorithm [26] . Alg. 2 in the appendix presents the complete FUGAL pseudocode.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [Yes] Justification: See Section 5, Appendix 5.7.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
customized optimization strategy for node alignment: 
 In this section, we elucidate the intricacies of Algorithm 1, which derives a quasi-permutation matrix, focusing on two pivotal steps: (i) initialization of the quasi-permutation matrix; (ii) finding the local solution for a given λ.Initialization: Any doubly stochastic matrix is a viable option for initialization. However, we opt for an uninformative flat matrix, 1 • 1 ⊤ /n. Our empirical observations indicated that this initialization consistently performs well across diverse datasets, contrary to informative initializations like the identity matrix, which exhibit inconsistency in performance, as we further elaborate in Section A.8.Local Solution for a given λ: Given a specific λ, our objective is to 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 a 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 functionf (P) = -tr(APB ⊤ P ⊤ ) + µ • tr(P ⊤ D) with respect to P, evaluated at Q, is ∇f (Q) = -AQB ⊤ -A ⊤ QB + µ • D. Additionally,the gradient of the constraint function g(P) = tr(P ⊤ (J -P)) with respect to P, evaluated at Q, is ∇g (Q) = J -2Q.Updating Q: A critical step involves determining the doubly-stochastic matrix q it that minimizes the inner product ⟨grad, q⟩, where grad is the current gradient. Prior work [42] applies the Hungarian algorithm to obtain a permutation matrix to that end, which, however, may not yield the optimal answer and incurs O(n 3 ) cost. Contrarily, we obtain a proper doubly stochastic matrix to that end. Definition 4.1 (Optimal Transport Distance Between r and c). Given a n × n cost matrix M, the cost of mapping an n-dimensional probability vector r to c, using a transportation matrix (or joint probability) P is quantified as ⟨P, M⟩. The following problem: minEQUATIONis an optimal transport problem between r and c given cost M, whereEQUATIONTo render this optimal transport objective strictly convex and thus efficiently solvable by the matrix scaling Sinkhorn-Knopp fixed-point iteration algorithm [38] via matrix-vector products, we regularize it with an entropic penalty h(P) that yields the Sinkhorn distance objective [7] :EQUATIONwhereh(P) = - n i,j=1 P ij log P ij , κ ∈ (0, ∞],which becomes equivalent to the transport distance for suitably large κ [7] . The method exhibits excellent performance in practice with O(n 2 ) empirical time complexity.Setting r and c to 1 (the all-ones vector) in Eq. ( 15), U (r, 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 q it that minimizes ⟨grad, q⟩ by the Sinkhorn-Knopp algorithm and update Q asQ ← Q + α • (q it -Q), with the step size α following the conventional choice α = 2/(2 + it).Complexity Analysis: The complexity of FUGAL is O(n 3 ), 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. A.1.The O(n 3 ) complexity stems from the need to perform matrix multiplications, a core operation in FUGAL as well as the baselines. A thorough evaluation of empirical running times ( § 5.5) also demonstrates the practical scalability of FUGAL. 
experiments: 
 In this section, we present a comprehensive evaluation of FUGAL vs. state-of-the-art graph alignment baselines on real and synthetic data sets with varying noise levels.Real Graphs. Table 1 summarizes the real-world datasets used to benchmark FUGAL.The last three data sets in the table are evolving graphs mandating challenging ground-truth alignments. 1 174 1 417 infrastructure bio-celegans [9] 453 2 025 biological ca-netscience [33] 379 914 collaboration ACM [48] 9 872 39 561 citation DBLP [48] 9 916 44 808 citation MultiMagna [41] 1 004 8 323 biological HighSchool [15] 327 5 818 proximity Voles [8] 712 2 391 proximity Synthetic Graphs. We employ Newmann-Watts (NW) [21] graphs, characterized by small-world properties and a high clustering coefficient. We generate NW graphs with 1000 nodes, number of neighbors per node k = 7, and a rewiring probability of p = 0.1. For each graph, we generate 5 noisy variants, perform alignments on each, and report average results. Given the obtained alignment set P and the ground truth set of alignments P real , we calculate accuracy as|P∩P real | |P| • 100.Noise Types. As in prior work [4, 20, 43] , we introduce perturbations to the adjacency matrix by either removing or adding edges. We employ two noise types: one-way noise removes edges from the target graph, while bimodal noise removes and restores the same number of edges. We ran all experiments on a 40-core Intel Xeon E5-2687W CPU machine @3.10GHz with Python implementations of FUGAL 1 and competitors;2 the latter include CONE [4] , IsoRank [37] , S-GWL [43] , GRAMPA [13] , GRASP-B [19] , FAQ [42] , 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 it 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 to their inferior performance [39, 29] . As we focus on non-attributed graphs, we exclude FINAL [47] , which is equivalent to IsoRank on graphs without attributes. For the prerequisite similarity score in IsoRank, we devise a customized weight scheme as sim(u, v) = 1 -|du-dv| max{du,dv} , where d u = |N (u)| denotes the degree of node u. With all baselines, we use author-recommended 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.Graphs with real Noise: We evaluate all algorithms on accuracy with three real-world networks: MultiMagna, Voles, and High School. MultiMagna represents a yeast protein-protein interaction (PPI) network and noisy variants incorporating an additional q% 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 1 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 a 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% of FUGAL. On the High School network, FUGAL, FAQ and PARROT align graphs perfectly, while S-GWL attains near-perfect alignment. IsoRank, GRAMPA, GRASP-B fGOT, GW and FGW fall short of FUGAL'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 Bimodal noise 0 1 3 5One-way noise0 1 3 5Bimodal noise 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. Real Graphs with Injected Noise: Figure 2 illustrates 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 a robust graph alignment solution. Appendix A.3 zooms in on the performance of FUGAL vs. baselines 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-Watts graphs of 1000 nodes with node degree k = 7 and rewiring probability p = 0.1 subject to synthetic noise. Under one-way noise, all methods except CONE and FAQ achieve perfect alignment at 0% noise. With noise of 5% and 10%, FUGAL attains a 60% and 14% gain, respectively, over the 2nd-best method, S-GWL. Beyond these noise levels, all methods experience failures. Bimodal noise at 0% results in perfect alignment for most methods. However, alignment failures occur as noise grows. Figure 3 further zooms in noise levels in the range of 0% to 5%. FUGAL significantly outperforms all baselines under one-way noise, achieving a margin of 60% at 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 in handling diverse graph structures.Here, we examine performance under varying graph density. In Newmann-Watts graphs, the rewiring probability parameter p affects the edge density of sampled graphs for a fixed number of nodes n, while the parameter k, 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 p = 0.25, outperforming S-GWL, which achieves only 54%. Sparse graphs pose a challenge for alignment, as they provide less discriminating evidence in 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. Here we compare the computational efficiency of FUGAL to that of S-GWL, which ranks as the second-best performer across most benchmark datasets. Figure 5 plots running times in logarithmic axes. FUGAL achieves lower running times on MultiMagna, Voles, euroroad, arenas, and Newmann-Watts networks with an up to 3x speed up, highlighting its capacity to handle large networks. Conversely, S-GWL marginally outperforms FUGAL on smaller networks. S-GWL did not scale for ACM-DBLP, failing to terminate even after 5 hours. This discrepancy 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 as an efficient and effective solution. Appendix A.2 presents running times for all baselines. Given the results of Section 5.5, we delve into the scalability of FUGAL and S-GWL with Newmann-Watts graphs of increasing nodes. Figure 6 plots our findings. At 512 nodes, FUGAL and S-GWL have comparable running times. Still, as nodes grow, FUGAL outpaces S-GWL. Table 3 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 µ controls the sway of node features in the optimization. Sparser graphs, characterized by lower connectivity and less information in adjacency matrices, benefit from higher reliance on node features, hence we recommend a higher µ. Sparser datasets such as inf-euroroad, ca-netscience, and NW (k = 7, p = 0.1) benefit from higher values of µ (1-2), denser graphs from smaller values (0.1-0.5). 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 i th structural feature while excluding others. FUGAL-0 abstains from all structural features. Figure 7 juxtaposes the accuracy of these variants to that of FUGAL on two networks. Each variant employing structural features attains higher accuracy than FUGAL-0, 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 investigate a variant setting λ = 0, denoted as FUGAL-DS (for doubly stochastic), instead of iteratively increasing it. As Figure 8 shows, FUGAL-DS attains worse accuracy. 
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, we established that FUGAL surpasses state-of-the-art 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 to improved solutions in graph alignment, 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 bioinformatics, 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See Section 5, Appendix 5.7.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 are 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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: See Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] .Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: See Section 5.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Algorithm 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 permutation matrix. Let us consider source and target graphs G 1 , G 2 with n nodes. Among NETSIMILE structural features, the clustering coefficient incurs a high computational cost of O(nM 2 ), where M 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 O(nM ϵ ), with 0 < ϵ < 1 [18] , while finding pairwise Euclidean distances between node features takes O(n 2 ). The quasi-permutation matrix derivation involves determining the gradient of the optimization problem, which requires O(n 3 ) due to matrix multiplications. The Sinkhorn-Knopp algorithm finds the doubly-stochastic matrix q minimizing ⟨grad, q⟩, is nearly O(n 2 ) [7] , while the update to Q takes O(n 2 ) time. Thus, the time complexity for finding a quasi-permutation matrix is O(T • n 3 ), where T is the number of iterations. We round the quasi-permutation matrix to a permutation matrix by the Hungarian algorithm, incurring a time complexity of O(n 3 ). Therefore, the time complexity of FUGAL is O(T • n 3 ). Empirically, T typically ranges from 10 to 20, resulting in a cost of O(n 3 ) since T ≪ n. We provide computational costs of baselines in Appendix A.6. Table 4 compares FUGAL's computational cost to that of baselines.Figure 9 presents the running times of various baselines on 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 §. 5, renders a comparison skewed in favor of FUGAL.In § 5, we have already demonstrated the superior performance of FUGAL in the presence of noise levels ranging from 0% to 25%. In this section, we extend the comparison to assess the performance 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. In 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 a 6% improvement over the next-best method, S-GWL. The consistent and superior performance of FUGAL across all benchmark datasets underscores its robustness.To compare the performance of non-scalable methods like GOT, fGOT, PATH and DSPP with FUGAL, we employed small Erdős-Rényi random graphs [12] . The limited scalability of these methods for larger graphs is empirically demonstrated in Section 5 (failing to terminate within 5 hours) as well as evidenced by the maximum graph size evaluated by the authors, which was 100. Following the methodology of fGOT [32] , we varied the node count n from 20 to 100, with edges generated using a 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 11 . While FUGAL, S-GWL, and PARROT achieved perfect alignment 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 Figure 11 . 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.We assess FUGAL against S-GWL and CONE in terms of Matched Neighborhood Consistency (MNC) [4] 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. The computational costs incurred by the baseline methods and FUGAL are presented in Table 4 . It 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 3 ). 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, as 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.5 and 5.6 revealed slower running times compared to expectations. Moreover, S-GWL fails to scale for larger graphs such as ACM-DBLP (failing to terminate within 5 hours), whereas FUGAL achieves superior accuracy within 40 minutes. The limited scalability of S-GWL 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. S-GWL employs a recursive graph partition mechanism to accelerate graph alignment computations. An important question is how the performance of SGWL is affected by this recursive mechanism with respect to FUGAL. We have identified that the hyper-parameters cluster_num (C), partition_level (P), and node_prior (N) significantly influence the recursive partitioning process. Three variants of S-GWL were proposed by the authors [43] based on different combinations of C and P: (C = 2, P = 3), (C = 4, P = 2), and (C = 8, P = 1). Additionally, we vary the node_prior parameter within the set {10, 100, 1000}. These combinations result in nine distinct variants of S-GWL, denoted as CxPyNz where x, y, z represent the values of C, P, and N respectively. We conduct a comparative evaluation of FUGAL against these nine variants with respect to both accuracy and running times jointly. Figure 13 depict the outcomes on the inf-euroroad 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 in 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. Lastly, we empirically examine our decision to employ a non-informative flat doubly stochastic matrix, denoted as 1 • 1 T /n, as the initial quasi-permutation matrix in Algorithm 1, in contrast to alternatives. We try out a 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 on the HighSchool network, indicating its instability. These findings substantiate our selection of the flat doubly stochastic matrix as a robust choice for initialization. EQUATIONWe illustrate the functionality of FUGAL through an example in Figure 15 . We create a source graph G1 of 6 nodes and randomly permute it to a target graph G2. We show three stages of FUGAL's operation: (1) the doubly stochastic matrix Q, generated after the first iteration of Algorithm 1 (λ = 0); (2) the quasi-permutation matrix Q to which Algorithm 1 (Section 3) steers the doubly stochastic matrix; (3) the permutation matrix P into which Algorithm 2 refines this quasi-permutation matrix using the Hungarian algorithm. FUGAL aligns G1 and G2 perfectly.NeurIPS Paper ChecklistCode and data at https://github.com/idea-iitd/Fugal.Source code from https://github.com/constantinosskitsas/Framework_GraphAlignment. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: There are several weaknesses of the paper:

1. 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.  
https://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.


2. One of the big advantage 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.
questions: questions: See above.
limitations: limitations: I stated the key limitations in the weakenesses.
paper_summary: paper_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.
FUGAL 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.
strength_weakness: strength_weakness: The authors do not clearly define the limitations of their method, and there is no clear sensitivity analysis or ablation study of certain aspects. 
Besides, there is a complete lack of statistical significance analysis.
questions: questions: Here are some suggestions and comments:

- 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.

- 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.

- In Figure 1, using the variants of MultiMagna instead of $q$ may confuse the reader slightly.

- 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.

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.

- 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: limitations: Including some sentences that clearly stree the method's limitations would improve the paper.
paper_summary: paper_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.

--- 
score raised after rebuttal.
strength_weakness: strength_weakness: This is not a totally novel approaches but it is understandable given the nature of the combinatorial optimization problem.  

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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: One huge weakness is the absolute lack of references to related work.
In 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. 
Here 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].

[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] 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.

[3] Zhou, F., & De la Torre, F. (2015). Factorized graph matching. IEEE transactions on pattern analysis and machine intelligence, 38(9), 1774-1789.

[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.

[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. 

[6] Nadav Dym, Haggai Maron, Yaron Lipman. (2017) Ds++: A flexible, scalable and provably tight relaxation for matching problems


This makes the experimental section kind of weak also, since at least I would have compared with [1] and eventually [6].

Besides 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.

Another 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?
I 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.

Another 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. 
A more suitable measure could be $||AP-PB||_F^2$
questions: questions: In Algorithm 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?

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 in this case? (also, not a good idea to use the same name for different parameters)

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 for example.
Also, why use the Hungarian algorithm and not the Sinkhorn formulation here? It is the same problem.

Minor comment:
In line 33, there's a word missing (method?) "In this work, we propose an unrestricted graph alignment m that avoids restricting ..."
limitations: limitations: There's no explicit mention of any limitation of the algorithm.

Comments: title: Further evidence on QAP efficacy for network alignment.
Response
Keenly awaiting feedback from Reviewer ts95
Eagerly awaiting feedback on our rebuttal
Eagerly awaiting feedback from Reviewer ts95
Please address author responses
comment: Dear Reviewer T3ao,

We wish to further highlight that the paper (2) you refer to in your last comment, that is the quoted line below, is the FAQ paper. FAQ is one of the primary baselines we compare to and show that it is significantly inferior to FUGAL (Figs. 1-4, Table 2). 

> A key application of QAP is network alignment. See for example: (1) https://arxiv.org/abs/1908.00265 (2) https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0121002

This serves as further evidence of:

1. Why the stated claim of generic solvers being effective on network alignment **stands on unsubstantiated grounds.**
2. The impact and novelty of the regularizers, features and optimization strategies we design for the network alignment problem that enables us to **outperform FAQ and 12 other baselines** in a comprehensive benchmarking exercise.

Our extensive benchmarking exercise provides compelling evidence of the inefficacy of generic QAP solvers for network alignment, thereby underscoring the significance and contributions of our work.

We hope this clarification helps to highlight the merits of our approach in the context of existing solutions for network alignment.

Thank you for your consideration.

Best regards,

The Authors
I want to thank the authors for the detailed response.

Some of my concerns were taken, as well as suggestions. I'll raise my score accordingly.

I still think that the heuristic optimization needs a more precise framework, and a stronger theoretical study.
Dear Reviewer T3ao,

**QAP Vs. Network Alignment:** QAP solvers approximate the optimal solution. This approximation is of low quality unless aided with regularizers and features specific to network alignment, which we do. We have compared with generic QAP solvers and outperform them comprehensively. Our novelty lies in designing the regularizer and optimization strategies that work in the context of network alignment. Herein lies our core novelty. Furthermore, **we have outperformed well-established state-of-the-art network alignment algorithms such as S-GWL, both in accuracy and efficiency.** This further substantiates the impact of our work.

**Supervised Network Alignment:** The referred papers for supervised learning are **inaccurate.** As we mentioned in our rebuttal, we would appreciate examples of peer-reviewed works that perform network alignment on unseen networks without retraining. In this context, we point out why the referred papers do not serve this role.

1. ERIC is tailored for computing graph edit distance and can't scale for large graphs. The average size of the graphs ERIC aligned is less than 30 whereas we are aligning graphs with more than 1000 nodes. Moreover, ERIC needs to be trained on every dataset separately as GNN is a function of number of features and these vary across datasets. 

2. Same is the case with Deep graph matching consensus as it needs to be trained for every network separately.

3. SGWL, GWL are unsupervised and need to learn embeddings for every graph pair separately. We have already compared with these methods and comprehensively outperform them.

**Efficiency of S-GWL:** Our empirical study includes comprehensive efficiency comparison with S-GWL and reveals its inability to scale to large datasets, which is consistent with several other works in the literature [1,2,3,4]. One contributing factor to this limitation is that S-GWL performs recursive -partitioning, a process that is not conducive to parallelization on modern CPUs with high levels of hyper-threading [4]. 

[1] Zeng, Z., Zhang, S., Xia, Y., and Tong, H. Parrot: Position-aware regularized optimal transport for network alignment. WWW ’23, pp. 372–382.

[2] Hermanns, J., Skitsas, K., Tsitsulin, A., Munkhoeva, M., Kyster, A., Nielsen, S., Bronstein, A. M., Mottin, D., and Karras, P. Grasp: Scalable graph alignment by spectral corresponding functions. ACM Trans. Knowl. Discov. Data, 17(4), Feb 2023.

[3] Skitsas, K., Orlowski, K., Hermanns, J., Mottin, D., and Karras, P. Comprehensive evaluation of algorithms for unrestricted graph alignment. In EDBT 2023, Ioannina, Greece, March 28-31, 2023, pp. 260–272.

[4] Li, J., Tang, J., Kong, L., Liu, H., Li, J., So, A. M.-C., and Blanchet, J. A convergent single-loop algorithm for relaxation of gromov-wasserstein in graph data. In ICLR, 2023.
Thanks to the authors for the rebuttal. My responses are as follows:

> 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.

A key application of QAP is network alignment. 
See for example: 
(1) https://arxiv.org/abs/1908.00265 
(2) https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0121002

I do not understand why a generic QAP solver will not work on the current problem. 
QAP is often given in the form of:

$$ \max _{P} \text{trace}(MPQPR) $$ where $M,Q,R$ are known matrix and $P$ is a permutation matrix. Conceptually, the above problem can be easily cast into the above term (plus the linear term Tr(P^T D)).  Except the linear term, there is no difference from any general QAP problem. In fact, the current algorithm is not treating A, B etc., beyond ordinary matrices--- so there is nothing specific in the context of graphs in the underlying solution.

In fact, the formulation is also almost same here: Eugene: explainable unsupervised approximation of graph edit distance https://arxiv.org/abs/2402.05885

The novelty factor of this paper is too limited. In my view, the work is a QAP problem (with network alignment application), solved using a numerical optimization method (no learning involved) with some modification of very known algorithm (Sinkhorn/knopp, already used in GWL paper).




>  To our knowledge, no embedding-based method has demonstrated competitive performance in network alignment. 

There are many papers, other than GWL or S-GWL. For example:

ERIC: https://openreview.net/forum?id=lblv6NGI7un

Deep Graph Matching Consensus: https://arxiv.org/abs/2001.09621

Also, the complexity of S-GWL is O((V+E)K) and the current paper is O(V^3), right? In this light, I could not parse the results in Appendix A.7

In a nutshell, I think this is an interesting work, but it does not add too much value to the literature--- as it is, it is a numerical optimization to QAP, which is quite rich in literature. As presented in this paper, the contribution with respect to such broad literature is quite limited. In fact, I think it may be of interest to data mining community e.g., SDM or ICDM, with significant modifications. But, I don't think this has crossed the bar of Neurips *as of now*.
Dear Reviewer ts95,

We are less than a day away from the closure of the author-reviewer discussion phase. We are keenly awaiting your feedback on our detailed rebuttal. We thank you for your constructive feedback and hope all your concerns have now been addressed.

regards,

Authors
Dear Reviewer T3ao,

We are less than a day away from the closure of the discussion phase. We would greatly appreciate you feedback on the clarifications offered in our rebuttal. We are also happy to inform that two reviewers have already rated our work as "Accept (7)".

regards,

Authors
I appreciate your detailed rebuttal. It has helped clarify several points.
Thank you for your constructive feedback, which has helped us improve our work. We appreciate your support and the Accept rating.

Sincerely,

The Authors
I appreciate the rebuttal. I can see that the paper's contribution is pretty solid. I raise my score to reflect my current assessment of the paper.
Dear Reveiwer ts95,

First of all, thank you for taking your time out in reviewing our work and providing constructive feedback. Based on your suggestions, we have incorporated new baselines, ablation studies, metrics. We are eagerly awaiting your feedback on the rebuttal. We humbly appeal to you to please review the revisions made since the discussion phase closes in less than 2 days from now.

regards,

Authors.
Dear Reviewers, 

The paper has received a wide range of reviews.

Please take a look at the other reviewer comments as well as the author feedback, and provide a response: at a minimum, acknowledging that you have looked at the responses; and adjusting your review and/or rating if you feel it is appropriate.  

Please do this ASAP.

Thank you, 

SAC