Harnessing spectral representations for subgraph alignment
Authors: Marco Pegoraro
Riccardo Marin
Arianna Rampini
Simone Melzi
Luca Cosmo
Emanuele Rodolà
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph alignment
Spectral theory

Abstract: With the rise and advent of graph learning techniques, graph data has become ubiquitous in the machine learning field. However, while several efforts have been devoted to the design of new convolutional architectures, pooling or positional encoding schemes, relatively little focus has been spent on modeling pairwise problems such as signal transfer, graph isomorphism and subgraph correspondence tasks. With this paper, we anticipate the need for a convenient framework to deal with problems that revolve around the notion of a map among graphs, and focus in particular on the challenging subgraph alignment scenario. We claim that, first and foremost, the representation of a map plays a central role in how these problems should be modeled -- be it a map inference problem or a simpler signal transport task. Taking the hint from recent work in geometry processing, we propose the adoption of a spectral representation for maps that is compact, easy to compute, permutation-equivariant, easy to plug into learning pipelines, and especially effective for a wide range of situations, most notably when dealing with subgraph alignment problems. We further report for the first time a surprising phenomenon where the partiality arising in subgraph alignment is manifested in the structure of the map coefficients, even in the absence of exact isomorphism, and which is consistently observed over different families of graphs.

Under review as a conference paper at ICLR 2023
HARNESSING SPECTRAL REPRESENTATIONS FOR SUBGRAPH ALIGNMENT
Anonymous authors
Paper under double-blind review
ABSTRACT
With the rise and advent of graph learning techniques, graph data has become ubiquitous. However, while several efforts are being devoted to the design of new convolutional architectures, pooling positional encoding schemes, less effort is being spent on problems involving maps between (possibly very large) graphs, such as signal transfer, graph isomorphism and subgraph correspondence. With this paper, we anticipate the need for a convenient framework to deal with such problems, and focus in particular the challenging subgraph aligmment scenario. We claim that, first and foremost, the representation how these problems should be modeled. Taking the hint from recent work in geometry processing, we propose the adoption of a spectral representation for maps that is compact, easy to compute, robust topological changes, easy to plug into existing pipelines, and is especially effective for subgraph alignment prob- lems. We report for the first time a surprising phenomenon where the partiality associated to the subgraph is manifested as a special structure of the map coeffi- cients, even the absence of exact subgraph isomorphism, and which consis- tently observed over different families of graphs up to several thousand nodes.
map plays a central role
INTRODUCTION
The ability to align data is the heart of many successful techniques machine learning and related areas. In its most abstract form, the problem has a straightforward formulation: Given two generic domains Dj and D2, find a transformation T such that TD, R D2 according to some approximation metric that depends the task. Examples of such problems are found in numerous applications, including molecular docking (Gainza et al. 2020), image- based rendering (Fachada et al. (02T). 3D reconstruction (Zhao al., 2022), generative models (Dai & Hang 2021 and style transfer (Zhang ett al.) 2022). in addition to countless others. Recent remarkable examples include CLIP Meila & Zhang (202T), where images are associated to corresponding captions by aligning their learned embeddings, or MaSIF (Gainza et al.) 2020), where the interaction site between protein structures (i.e., the surface patches where the proteins geometrically align) is predicted by geometric deep learning pipeline.
Perhaps the most challenging setting for alignment problems arises whenever the two domains only correspond partially, for example due to the lack of observations or noise in the data. In this case, one is not only interested in aligning the two domains, but also in discovering which portions of the domains actually align. The problem is particularly hard if an exact alignment does not even exist, requiring additional robustness to local perturbations the data.
In this paper, we focus on the general problem of subgraph alignment, as it is representative of broad spectrum of applications including those mentioned above. We assume to given two graphs G1 and G2. where G2 appears within G1, possibly up topological changes. A special case appears when G2 is isomorphic to a subgraph of G1 which is referred to as subgraph isomorphism (see (ii) in Figure D. This case is included in treatment, but also consider noisier settings where subgraph isomorphism does not exist (see (iii) in Figure I yet a semantic correspondence can still be defined.
Contribution, In this paper, we focus in particular on the choice of a representation for the corre- spondence. That is, instead of introducing new matching pipeline solve subgraph alignment,

---

Under review as a conference paper at ICLR 2023
fall i ssomoophic
isomoorpii phic subgragh
nou-isomophic
subgraph
Figure 1: Functional maps of size 50 x 50 between full graph (depicted on the left) and three different graphs, respectively: an isomorphic graph (i), an isomorphic subgraph containing 80% of the original nodes (ii), and non-isomorphic subgraph obtained by randomly rewiring the former (iii). The green edges are novel and randomly added (10% of the total), the red edges are randomly removed (10% of the total). The map representation still maintains visible structure despite the significant changes of connectivity that span several hops.
show an alternative way of representing maps between graph and its subgraphs. In cases where the map is unknown and must be sought for, the new representation makes the inference problem easier solve; while if the map is given, the new representation more compact, has regularizing ef- fect, and bears natural structure that is missing from classical representations such as node-to-node binary correspondence matrices.
From technical perspective, the map representation is defined with respect to a spectral basis; namely, the eigenvectors of the graph Laplacian. This idea, introduced a decade ago the geometry processing area (Ovsjanikov al. 2012), brought significant progress to several tasks in graphics and vision yet, its application to graphs has been largely overlooked.
We claim that part of the reason is common misconception. The lack of smooth metric (i.e., smooth manifold underlying the graph) leads to the assumption that key properties of the spectral representation of the maps, such as those observed in Ovsjanikov et al. (2012); Rodola et al.) (017)) only exist for surface domains. With this work, we challenge this view by showing extensive empir- ical evidence that only these spectral maps applicable to general subgraphs, but also that they exhibit robustness properties that go beyond what was shown on surfaces. Therefore, we propose to embrace the spectral representation of maps compact, efficient, interpretable, robust, and easy to manipulate objects that can be naturally integrated into several pipelines, including but not limited to graph learning models.
We summarize our main contributions as follows:
We propose the adoption of spectral representations for maps between graphs and sub- graphs. For the first time, we show that such maps exhibit special structure in their coefficients, capturing the similarity between the Laplacian eigenspaces the two graphs.
We further show robustness of the representation to topological modifications of the sub- graph, due for example to graph rewiring. This leads to well-defined maps even in the absence of exact isomorphism.
We include extensive experiments showing practical applications, such signal transfer and subgraph matching, on graphs spanning a few dozen to tens of thousands of nodes, and demonstrate key benefits terms of robustness to noise, interpretability, and computational complexity.
All the code and generated data will be publicly released upon acceptance.
RELATED WORK
Graph alignment problems are ubiquitous in applications from social network analysis (Liu et al. 2016) to bioinformatics (Singh et al. 2008). Given its relevance, a rich body of literature devoted to this problem. A comparative study on several network alignment techniques can found in Trung et al. 2020). Though not exhaustive, discuss the most relevant works in the following.
2

---

Under review as a conference paper at ICLR 2023
Node-to-node correspondence. IsoRank (Singh et al. 2008 is widely considered the baseline for protein-to- pootein-to-protee to-protein interaction (PPI) aligmment. It constructs an eigenvalue problem for every pair of input networks and extracts global alignment across a set of networks by a k-partite matching. Subsequently, it inspired other works, such as Liao et al. ; Nassar et al.] (2018); Feizi et al. (2019), that still attribute and topological information (Zhang & Tong 2016) or propagated the ground-truth matches over the input graphs (Yartseva& & Grossglauser] [0133] Kazemi et al. 2015). Another thriving line of works first computes node embeddings and then aligns the nodes using the similarity between these features. The embeddings can be computed from the Laplacian eigenvectors (Knossow et al., 2009), the connectivity structure and node attributes (Heimann et al.] 2018) or directly use representation learning methods (Liu et al. 2016, Man et al. 2016 Zhou et al.] 2018), thus requiring manually corresponding matches during the training phase.
spectral approach. Other works leveraged
optimization process based on
All these methods directly look for node-wise correspondence between input graphs, soon becom- ing infeasible when the size of the graphs reaches thousands of nodes. We investigate different approach, where we adopt a functional (as opposed to node-wise) representation to define a cor- respondence between graphs. Furthermore, previous works mostly focus single application, either global PPI network alignment (Singh et al.] 2008: Liao et al.] 22009), synthetic datasets with structural noise (where small portion of edges are randomly removed) (Hermanns al., [02T]] Trung et al., (020), or social networks (Liu et al., 2016 Man et al., 2016]] Zhou et al.] 2018)_ In our analysis. we address the general task of subgraph alignment, where a large portion of the graph is missing. without focusing on any specific domain. This is also different from the problem of subgraph isomorphism, which concerns the decision problem as whether small query graphs exist
within larger graphs (Duong et al. ).21).
Functional correspondence. The functional maps framework (Ovsjanikov et al. 2012) was first in- troduced in the shape analysis field to find correspondences between deformable 3D shapes. Thanks to its flexibility, many extensions of this framework were later proposed, improving the correspon- dence accuracy by means of dedicated regularizers (Ovsjanikov et al. 2017|Nogneng & Ovsjanikov] 2017 Ezuz& & Ben-Chen] 2017 Mclzi et al. 2019; Ren et al./ 2020a). To allow matching non- isometric shapes, Kovnatsky et al. (2013) apply the framework approximate eigenbases obtained with a joint diagonalization algorithm. The same approach was later adapted to partial shape match- ing in Rodolà et al. (2017); Litany et al. (2017); Cosmo et al. (2016c), where the goal is to map part of a deformed 3D shape to a possibly incomplete model.
In the context of graphs, first attempt to represent similarity between graphs in functional space was proposed in WWan et al. (2019). However, there the functional representation is on the edge domain, and its application limited to the case of Euclidean graphs. More related to our work is the recent GRASP (Hermanns et al., [022]). which detects an alignment among graphs by em- ploying a functional correspondence among pre-aligned Laplacian eigenvectors. Different our work, GRASP considers only the setting of noisy complete graphs, i.e., full network is perturbed by randomly deleting edges with a probability p up to 0.25. Instead, we study the correspondence problem much broader class of graphs, undergoing strong partiality transformations in addition to strong perturbation of the connectivity, and consider larger scales reaching up to several thousand nodes.
3 PRELIMINARIES
Graphs and Laplacian eigenvectors. We consider undirected, unweighted graphs G = =V, (V,E) with nodes V and edges E C V x V. We denote as A E {0, 1| the adjacency matrix of G. which is a binary matrix where A(i otherwise.
if an edge connects node i to node j. and A(i,j)
The symmetric normalized Laplacian for G is defined as the square matrix L =1- - AD 1, where D is a diagonal matrix of node degrees, with entries (i,, = ΣM A(I.j). This linear operator is symmetric and positive semi-definite; it admits an eigendecomposition L TAΦT where A is a diagonal matrix that contains the eigenvalues, and is a matrix having as columns the corresponding eigenvectors. Throughout this paper, we assume the eigenvalues (and corresponding
3

---

Under review as a conference paper at ICLR 2023
eigenvectors) to be sorted in non-descending order 0 X1 I A2 ... 2; this assumption is important for interpreting the functional maps that we define in the sequel.
Each cigenvector for / = ...... V has length [V,, and can be interpreted fined on the nodes of the graph; for this reason, we will occasionally refer to them as cigenfunctions for added clarity. The eigenfunctions form orthonormal basis for the space of functions defined on the graph nodes. Usually, one may consider a subset of eigenfunctions, namely those associated with the k smallest eigenvalues, approximate the graph signals in a compact way.
scalar function de-
F Functional maps. Ours is direct adaptation of the functional map representation introduced Ovsjamikov al. (2012) for pairs of quasi-isometric surfaces. We present the original framework for surfaces here, and discuss its application to graphs and subgraphs in Sections 4 and Appendix
Consider two smooth manifolds M and N, and let T - M be a point-to-pon toottotottttooooo map between them. Given scalar function f MM + R, the map T induces functional mapping via the composition g = foT, which can be seen linear map Tr + g from the space of functions on M to the space of functions on M. As linear map, the functional Tr admits matrix representation after choosing a basis for the two function spaces.
To this end, consider a discretization of M and N, with vetices Vi and V2 respectively, and the corresponding disretized version of their Laplace-Beltrami operators (LBOs) (the counterpart of the graph Laplacian smooth manifolds). The first k eigenfunctions of the two LBOs can be concatenated side by side columns to form the matrices & E RlVl| and V E R. Va|x Further, assume the pointwise map T is available and encoded y E V/2 corresponds to x E V1, and O otherwise. By choosing & and V as bases, the functional map TF can be encoded in a small & x k matrix C' via the change of basis formula:
binary matrix S, such that Syy, =
C= --$$$
(1)
where is the Moore-Penrose pseudoinverse. The size of C' does not depend on the number of points in M and N,, but only on the number it of basis functions. In other words, C represents the linear transformation that maps the coefficients of any given function : M - expressed in the eigenbasis t to coefficients of corresponding function g :N + IR expressed in the eigenbasis V.
When the pointwise similarity S is unknown, one can directly compute the matrix C as the solution of a regularized least-squares problem with 122 unknowns, given some input features on the two surfaces (e.g., landmark matches or local descriptors). For further details we refer to Ovsjanikov et al. 2012 2017).
4 FUNCTIONAL MAPS FOR SUBGRAPHS
In this work, we consider the setting where we are given a graph G and a possibly noisy subgraph G2 = E2) of G1, such that 1/2 S V12 and Eg C E1. When moving from surfaces to graphs, Equation I takes simpler expression as we show in Appendix A.I
4.1 MOTIVATION
Classically, maps are represented as binary matrices whose dimensions scale quadratically with the number of nodes in the graphs. One can directly adopt Equation 4 to shift to spectral repre- sentation C of the map; however, recall that we consider the setting where G2 is a subgraph G1. This simple fact leads to the following important observation, that is central to our contribution:
In many practical cases, the eigenspaces of the normalized graph Laplacian well preserved under non-isomorphic transformations of the graph, including strong partiality, topological per- turbations, and edge rewiring.
Put simply, the values of the Laplacian eigenfunctions stay approximately the same (up sign, in case of simple spectrum) at the nodes that are not directly involved the perturbation which is to say that the eigenvectors of the partial graph G2, encoded in 42 correlate strongly with the those of G encoded in Φ,. This observation is not trivial and has not been reported before, to the best of our knowledge.
4

---

Under review as a conference paper at ICLR 2023
M
G1
N
G2
G3
G4
Figure 3: Left: Functional map matrix between smooth surface M and deformed part W; the slanted-diagonal structure suggests that the cigenspaces of M are mostly preserved N. Right: Functional map matrices between graph G1 and different subgraphs; G2 is obtained by removing 40% of the nodes of G1, while G3, G4 are obtained by removing 55% and 80% of the edges from G2 respectively. The slanted-diagons structure can still be observed, and gets dispersed only at very high partiality. In the graphs above, corresponding nodes have the same color.
In the sequel we show extensive empirical evidence of this surprising behavior, and describe its practical consequences.
4.2 EIGENVECTORS CORRELATION
10
To get a better understanding of this phenomenon, in the inset we show an example where the Laplacian eigenfunctions Minnesota subgraph strongly correlate with the eigenfunctions of the complete graph, i.e., the Laplacian eigenfunctions have similar values at corresponding nodes, up to sign. Above each image, we also report the index of the plotted eigenfunction, leading to the following remark:
Remark (eigenvector indexing): The cigenfunctions the complete graph and those of the subgraph do not necessarily correlate at the same index (see pair 5-4) and the correlation may not be exact (see pair 10-8); the extent to which the eigen- functions correlate is captured precisely by the structure of C.
Figure 2: Corresponding eigen- functions of Minnesota (top row) and its subgraph (bottom row).
In 3D geometry processing, similar behavior erator under partiality transformations (Rodolà et al.) [017]] Postolache et al., (200);; however, their theoretical analysis assumes the data be Riemannian surfaces with smooth metric an assump- tion that does not hold in the case of general graphs. We refer to Appendix A.2 for further details.
observed for the discrete -eltace- op-
4.3 MAP STRUCTURE
The most direct consequence of this preservation of eigenspaces is reflected the structure of the functional map C. According Equation (4) each coefficient cjj of C' corresponds dot product between of and SØ);; this measures the correlation corresponding nodes between Laplacian eigenvector oe of Gg, and Laplacian eigenvector of of G1- Each eigenvector of is expressed linear combination of eigenvectors So). and combination coefficients are stored in row C.
In Figure we show several examples of matrix C. for different subgraphs. In the left side, the slanted-diagonal structure of the map hetween A and is explained by an application of Weyl's law to 2-dimensional Riemannian manifolds, However, there is no theoretical counterpart to explain the map structure between G₁ and its sub- graphs, due the complete absence of metric information about the underlying surface: the eigen- functions are computed purely from the graph connectivity. Yet. the diagonal structure is preserved under rather dense removal of edges, suggesting deeper algebraic implications.
(Rodolà et al.) 2017 Eq. 9) and Appendix A.2
One might legitimately ask whether the presence structure in the maps of Figure B due to the specific choice of the data, where the subgraphs derive from 3D mesh (although the normalized
5

---

Under review as a conference paper at ICLR 2023
graph Laplacian dismisses any edge length information) and where the type of partiality resembles a neat 'cut' (although we also perform random edge removals). However, the same behavior is also observed with abstract graphs, we show with CORA (McCallum al.] 2000) in Figure 4 and with the datasets PPIO (Hamilton et al. ),17), Amazon Photo (McAuley et al. 2015) and Amazon Computer (McAuley
2015) Figure of the Appendix.
To explain with an example how the structure of C' relates to the graph eigenspaces, consider the example of the Minnesota graph in Fig- I Suppose we map the full graph to its per- muted version (i). In this case, the two graphs have the same eigenspaces due to the permu- tation equivariance of Laplacian eigenvectors. Thus, matrix is diagonal with +1 along the diagonal, because Gij 0 for + (due to orthogonality of the eigenvectors), while Cy = +1 (due to the sign ambiguity of the eigenvectors). In the of repeated eigenvalues, one may ob- serve small blocks of coefficients along the diagonal due to the non-uniqueness of the choice of the eigenvectors spanning high-dimensional eigenspaces. When (ii), the two graphs have partially similar eigenspaces, meaning that the inner products hetween of and SØ) tend to be close zero and close =1, but not exactly equal. The matrix has sparse structure but is not necessarily diagonal. This is because the cigenvectors on the subgraph corre- late with those of the full graph at different indices + j unlike the full-to-full case, where the correspondence happens at
CONT
CORT
cluss removal
raniom cut
Figure 4: Functional maps between CORA and two different subgraphs.
map the full graph its subgraph
Remark (map structure): The functional map matrices are not necessarily diagonal, but may present a different sparsity structure which depends on the particular graph and subgraph.
As we will show in Section [ the presence of sparse structure in the functional map matrix C works as regularizer, in all those cases where the map is not given but must be estimated from the graph data.
4.4 NON-ISOMORPHIC SUBGRAPHS
In many practical settings, there are cases where the subgraph G2 is contained in the bigger graph Gi only up some topological alterations; for example, in the graph learning literature, topolog- ical perturbations frequently occur due to noise in the data, or are explicitly obtained by rewiring operations (Chamberlain et al. (02TT) or adversarial attacks (Jin et al. 2021 among others.
In Figure ! we show the functional map between Minnesota and a subgraph after rewiring (iii). We still observe correspondence between the cigenvectors of the full graph and those of the subgraph. The functional map has a sparse pattern, but it loosens up as the topological modifications increase. In Section 5.1 we further investigate this property and show the robustness of the functional repre- sentation to local topological changes.
Remark (topological changes):
The harder case, where there is partiality in conjunction with topo- logical changes, still manifests sparse structure in the coefficient matrix.
All the remarks far directly depend graph connectivity, and is hard to find analogies for smooth surfaces. We conjecture that local topological transformations of a graph, while they can certainly induce strong transformations of some of its Laplacian eigenspaces (similar to single-point perturbations on planar manifolds, see Filoche & Mayboroda (2012), are less likely to distort all the eigenspaces at once. This way, the functional map matrix tends to maintain its global structure intact, and exhibits local perturbations.
EMPIRICAL RESULTS AND ANALYSIS
In this section we validate the claims made in the previous sections with additional qualitative and numerical results. More experiments and details of the used datasets be found in Appendix B

---

Under review as a conference paper at ICLR 2023
Sabgraph
Naise
3%
30%
Cot
-00 mine 53392 10050
CORA
Conntation
rowiring
Figure 5:
Robustness of the map the simultaneous action of partiality and rewiring of the sub-
graph. We compare the addition of gaussian noise (μ 0z 0.2) with the impact of increasing rewiring (from 3% to 30% of the total number of edges) on the functional map C of size 50 50. On the left, we plot three graphs with their functional map: no rewiring (Subgraph), the addition of gaussian noise (Noise), 3% of edges rewired (3%), and 30% of edges rewired (30%). On the right, plot the variation of C' at different percentages of rewiring (solid lines) and with the addition of noise (dashed lines) for each graph.
5.1 ROBUSTNESS TO REWIRING
we claimed that the functional representation is robust to changes in graph connec- tivity. For this to be true, we expect that small changes in graph connectivity lead to small changes the matrix coefficients. See Appendix B.2 for the formal definition.
In section 4.4
In Figure [ we evaluate the changes of the functional map at increasing percentages of rewiring of a subgraph. We consider six graphs and compute subgraph from each one. Then, we apply small incremental changes to the topology of the subgraphs, with increments of 3% of the total number of edges; the changes are performed by removing and adding random edges, obtaining new subgraphs G. The plot the right shows how much the functional map representation is affected by the increasing topological changes compared to adding Gaussian noise. all the cases, the rewiring produces less variation in the functional map than adding Gaussian noise. In particular, the functional representation is more robust on larger graphs, such as cat (10000 nodes) or citeseer (2120 nodes), while smaller graphs such as QM9 (29 nodes) and Karate (34 nodes), removing or adding an edge has a more significant impact. This observation demonstrates the effectiveness of the spectral representation, especially on larger graphs. Appendix [B22] we show the complete qualitative analysis; while in Appendix C.2
we push this experiment to stronger rewiring.
5.2 SIGNAL TRANSFER
Within a graph, nodes may often come with numerical or vector-valued attributes, for instance, encoding molecular properties in PPIs, user identities in social networks, or positional encodings to better distinguish and characterize nodes. We can model such data as a collection of functions f: V1 + R that map each node of G1 to real value. Recent works (abriel-a et al. 2022) have demonstrated that transferring the positional encoding from a graph to its rewired version can improve GNN performance. The functional map C allows to transfer these functions from graph G to a subgraph G2 without requiring the explicit computation of a node-to-node correspondence. For each function f. it is sufficient the linear transformation C' to the obtained coefficients, and finally reconstruct the signal on the target graph G2 as linear combination of its Laplacian eigenfunctions. The described procedure is implemented by the simple formula:
project f onto the Laplacian eigenfunctions of GI, apply
9 -
where the function 9 V/2 + R is the transfer f to G2. Motivated by the results from Brüel- Gabrielsson et al.) (202)), we leverage this property of the spectral representation to transfer the positional encoding computed on graph to subgraphs. In Figure 6 we analyze the functional map transfer performance while increasing the number of eigenfunctions used for the map repre- sentation. We consider pairs composed of the original graph and series of subgraphs extracted according semantic criterion, e.g., nodes belonging the same class nodes connected by the
7

---

Under review as a conference paper at ICLR 2023
Original graph
Sub graph
0.9
PPIO
CiteSeer
PP113
0.7
AmazonPhoto
FraudAmazon
RMSE
0.5
AmazonComputer
%
10%
75%
1385 10%
1006
Percentage of eigenfunctions
Figure 6: RMSE obtained by transferring positional encodings (PE) using the functional map with an increasing amount of eigenfunctions. On the left, we show a qualitative example of signal transfer on PPIO. The first shows the full graph and the partial graph, with the PE plotted top. The bottom row shows the results of signal transfer with different percentage of cigenfunctions. On the right, we plot the RMSE at increasing percentages of eigenfunctions.
same edge type. We transfer the Random Walk Positional Encoding (Dwivedi et al. 2022) com- puted the full graphs the subgraphs. We normalize each dimension of the node features of the original graph to exhibit zero mean and unitary standard deviation throughout all the nodes, and then transfer this signal through Equation 2 In Figure 6 we can see how the Root Mean Squared Error between the functional map and the ground truth transfer (we refer to Appendix B.3 3.3 for more details on the evaluation) decreases as the number of eigenfunctions increases. In particular, the er- ror rapidly decreases at 10%-30% of eigenvectors. This behavior demonstrates that using a compact representation with few eigenvectors can approximate the signal well. The qualitative examples on the left of Figure O portray the transferred signal on PPIO. Already at 1 % of the eigenfunctions the transfer reaches a good approximation, while at 75% it is almost identical. In Appendix A.3] we show more experiments with different number of eigenfunctions.
Suppose the graph and subgraphs are equipped with features independent of topological changes (like in Citeseer). In that case, can compute the functional map C' from these features with- out needing ground truth correspondence a priori. To show the effectiveness of this alternative, in Appendix B.3 we show the results of signal transfer via estimated C.
5.3 NODE-TO-NODE CORRESPONDENCE
Table I: Comparison of the Mean Average Precision of different graph matching methods. We use k 50 eigenfunctions for the functional map representation. We also report the percentage of eigenfunctions used w.r.t. the number of nodes of the full graph (A%).
Partiality
FINAL
PALE
GRASP
FMw
FMy +ZM
GT
Cat
0.5 0.1
0.0
0.0
93
1.9
6.8
0.4
11 + 0.0
68 14
69 + 14
92 4 3.9
Minnesota
patch
1.9
0.2
0.1
1.:00
87
3.3
13 0.4
18 1:2
88 1
89 3.7
94 1.6
Cora
0.5 1: 0.0
0.6 0.0
54
3.5
22 2.9
6.8 1: 1.8
33 1 9.4
34 9.5
65 3.1
Cora
class
0.4 1 0.0
0.4
0.4.0...0
55
3.4
1712
51 1. 22
60 1
85 6.5
online
0.7
3.1
One of the advantages of the spectral representation is to reduce the NP-hard problem of finding node-to-node correspondences (usually formulated as quadratic assignment problem (Loiola al. 2007 to the more tractable (polynomial) problem of finding the linear transformation between the reduced eigenbases of the graphs (at least under the reasonable assumption of smoothness of the sought correspondence, i.e., nearby nodes on the input graph are located nearby also on the target subgraph). Assuming list corresponding functions staked column-wise in matrices
F = | (f(")) } and F2 = 1 |... ((m)) respectively defined on the node sets V and Vg, the general functional map matching algorithm corresponds to the following minimization problem:
arg min |C& T F1 2.J F2ll 1 reg(C')
(3)
8

---

Under review as a conference paper at ICLR 2023
where reg(C) is regularization imposing desired properties on C' (e.g. sparsity, diagonal structure). The corresponding functions can be any consistent function between the two graphs, such as input features coming with the data.
In this experiment, we apply two functional map-based matching algorithms. We adopt the off- the-shelf partial functional map algorithm (F (FMw) (Rodolà et al.) (017) and then the ZuomOut refinement (Melzi et al. 2019) (FMw + ZM). We compare the spectral representation with the network alignment methods proposed in the benchmark (Trung et al. 2020); IsoRank (Singh al.) 2008), FINAL (Zhang & Tong 2016), REGAL (Heimann et al. 201 8) and PALE (Man et al. 2016)) For all the methods, we use as input 50 landmark matches. For the two functional map methods we truncate the basis to the first 50 eigenvectors and use smooth indicator functions computed on the given landmarks as corresponding functions. We refer to the appendix B.4 for further details.
To investigate the degradation of the correspondence induced by the truncated eigenbasis, excluding errors generated by the matching algorithm, we also compute the correspondence starting from the ground-truth functional map (GT in the table).
We report Table the Mean Average Precision (MAP) defined as _ EE=1 ro; where ra, the n rank (position) of positive matching node in the sequence of sorted candidates. For our evalua- tion we consider different graphs and subgraphs. We extract 10 partial graphs by considering k-hops subgraphs starting from random points. As we can see from the GT column, the functional represen- tation seems to preserve well the correspondence on these graphs, reaching the highest performance in almost all cases, Even the functional map based methods leverage a more compact represen- tation, their performance is satisfactory, being the best performing method in Minnesota and the second best in the other two datasets. Moreover, Appendix [3.]] demonstrates that the functional map representation remains the fastest method in every graph. We note that for social graphs like CORA, characterized by few nodes with high degrees, the performance improves when the subgraph is semantically meaningful, obtained by removing all the nodes belonging specific class (fourth row). REGAL performs better since it is an ad-hoc algorithm for node-to-node correspondences on graphs, while our method a more general solution that leverages a simple linear system. We find it remarkable that using functional map as a representation without any fine-tuning works better in most cases, and are positive that this could lead follow-up work for subgraph matching.
Finally, we test the functional representation on Douban (Wu et al.) 2016), real-world dataset com- posed of an online and offline version of the same social network. In this case, both the nodes and connectivity are very different between the two graphs, resulting in incompatible eigenbases mak- ing this scenario particularly challenging for functional representation, as can also been observed by the low accuracy achieved using the GT functional map. In Appendix C and [A.3] we further investigate the performance of the functional representation at increasing partiality and number of eigenfunctions.
CONCLUSIONS
The spectral representation of functional maps for encoding graph and subgraph correspondences lends itself well several applications, and we anticipate that will be a useful addition the graph learning toolset. Among the promising directions that we aim to explore are the definition of novel positional encodings for graphs robust to partiality transformations and to graph rewiring, and the application of functional mapping to more abstract structures such as learned graph embeddings.
Further, while this paper we showed extensive evidence that the spectral map representation bears a special structure depending on the type of partiality, currently we have not taken full advantage of this structure. When the task at hand requires seeking for the subgraph alignment, i.e. whenever the map is unknown, it may be possible to design stronger regularizers induce sparsity in the matrix representation of the map. This is quite different from the better known setting of 3D surfaces, where this sparse structure is typically just diagonal
-iigona...
In the light of the increasing interest of the graph learning community toward spectral techniques, adopting spectral representation for maps between graphs is natural next step; it is simple to adopt, easy to manipulate, and memorr-efficiemn and has the potential to become a fundamental ingredient in spectral graph leamnngg pipelines in the near future.
9

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
All the code and generated data will be publicly released upon acceptance. In the supplementary ma- terial, have provided anonymous sample of the MATLAB code for reproducibility. In Section 5) we have specified the parameters used in the experiments, such as the number of eigenvectors, the error formulation the probe functions. In particular, Appendix [ focuses on clarifying our experiments' details and presenting the dataset used throughout our work.
REFERENCES
Yonathan Aflalo, Haim Brezis, and Ron Kimmel. On the optimality of shape and data representation in the spectral domain. SIAM Journal on Imaging Sciences, 8(2):14411110) 2015.
Mikhail Belkin and Partha Niyogi. Convergence of laplacian eigenmaps. In Proc. NIPS, pp. 129- 136, 2006.
P. J. Besl and N. D. McKay. A method for registration of 3-d shapes. TEEEsaaanttiinss Pattern Analysis and Machine Intelligence, 14(2):239-25 226,, Feb 1992.
Nicolas Boumal, Bamdev Mishra, Pierre-Antoine Absil, and Rodolphe Sepulchre. Manopt, a matlab toolbox for optimization manifolds. CoRR, abs//3308.522 2013.
Rickard Gabrielabri,,sonn, Mikhail Yurochkin, and Justin Solomon. Rewiring with positional en- codings for graph neural networks. 2022.
Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion graphs. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1594-1609. Curran Associates, Inc., 2021.
L. Cosmo, E. Rodolà, M. M. Bronstein, A. Torsello, D. Cremers, and Y. Sahillioglu. Partial Match- ing of Deformable Shapes. In A. Ferreira, A. Giachetti, and D. Giorgi (eds.), Eurographics Workshop on 3D Object Retrieval. The Eurographics Association, 2016a.
Luca Cosmo, Emanuele Rodolà, Michael M Bronstein, Andrea Torsello, Daniel Cremers, and Y Sahillioglu. Shrec' 16: Partial matching of deformable shapes. Proc. 3DOR, 2(9): 2016h.
Luca Cosmo, Emanuele Rodolà, Jonathan Masci, Andrea Torsello, and Michael M Bronstein. Matching deformable objects in clutter. In International Conference on 3D Vision (3DV), pp- 1-10. IEEE, 2016c.
Mengyu Dai and Haibin Hang. Manifold matching via deep metrie learning for generative modeling. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6587-6597, 2021.
Chi Thang Duong, Trung Dung Hoang, Hongzhi Yin, Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer. Efficient streaming subgraph isomorphism with graph neural networks. Pro- ceedings of the VLDB Endowment, 14(5):730-742, 2021.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022. URL/https:/ppeeeeeiieee forrmmmm?
in=wTT
Danielle Ezuz and Mirela Ben-Chen. Deblurring and denoising of maps between shapes. Computer Graphics Forum, 3655)41 2017.
Sarah Fachada, Daniele Bonatto, Mehrdad Teratani, and Gauthier Lafruit. Light field rendering for non-lambertian objects. Electronic Imaging, 2021(2):54-1, 2021.
Soheil Feizi, Gerald Quon, Mariana Recamonde-Mendoza, Muriel Medard, Manolis Kellis, and Ali Jadbabaie. Spectral alignment of graphs. IEEE Transactions on Network Science and Engineer- ing, 7(3): 182-1197, 2019.
10

---

Under review as a conference paper at ICLR 2023
Marcel Filoche and Svitlana Mayboroda. Universal mechanism for anderson and weak localization. Proceedings of the National Academy of Sciences, 109(37):14611-1476. 2012.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodolå, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geo- metric deep learning. Nature Methods, 17(2): 172))184-192, 2020.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. Association for Computing Machinery, 1998.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.002166 2017.
Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning- based graph alignment. In Proceedings of the 27th ACM international conference on information and knowledge management, pp. 117-126, 2018.
Judith Hermanns, Anton Tsitsulin, Marina Munkhoeva, Alex Bronstein, Davide Mottin, and Pana- giotis Karras. Grasp: Graph alignment through spectral signatures. In Asia-Pacific Web (APWeh) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data, pp. 44-52. Springer, 2021.
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adver- sarial attacks and defenses graphs. SIGKDD Explor. Newsl., 22(2):19-34, jan 2021. ISSN 1931-0145. doi: 10.1145/8445556.344755
Ehsan Kazemi, S Hamed Hassani, and Matthias Grossglauser Growing graph matching from handful of seeds. Proceedings of the VLDB Endowment, 1100)10100-121,, 2015.
Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molec- ular graphs. CoRR, abs/2003.03125 2020.
David Knossow, Avinash Sharma, Diana Mateus, and Radu Horaud. Inexact matching of large and sparse graphs using laplacian eigenvectors. In International workshop on graph-based represen- tations pattern recognition, pp. 144-153. Springer, 2009.
Artiom Kovnatsky, Michael M Bronstein, Alexander M Bronstein, Klaus Glashoff, and Ron Kim- mel. Coupled quasi-harmonic bases. Computer Graphics Forum, 32(2pt4):439-448 2013.
Chung-Shou Liao, Kanghao Lu, Michael Baym, Rohit Singh, and Bonnie Berger. Isorankn: spectral methods for global alignment of multiple protein networks. Bioinformatics, 25(12):i55-i2558, 2009.
O. Litany, Rodolà, A. M. Bronstein, and M. M. Bronstein. Fully spectral partial shape matching. Computer Graphics Forum, 36(2):247-25 258, 2017.
Li Liu, William K Cheung, Xin Li, and Lejian Liao. Aligning users across social networks using network embedding. In Ijcai, pp. 1774-1780, 2016.
Eliane Maria Loiola, Nair Maria Maia Abreu, Paulo Oswaldo Boaventura Netto, Peter Hahn, and Tania Maia Querido. A survey for the quadratic assignment problem. Eur J. Oper. Res., 176(2): 657-690, 2007.
doi: 10. 00.1016/.ejor.20055.oo
Tong Man, Huawei Shen, Shenghua Liu, Xiaolong Jin, and Xueqi Cheng. Predict anchor links across social networks via an embedding approach. In Ijcai, volume 16, pp. 1823-1829, 2016.
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. CoRR, abs/1500.04457, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2))127-163, 2000.
11

---

Under review as a conference paper at ICLR 2023
Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International Conference on Machine Learning, JCML 2021. 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, 2021. PMLR.
Simone Melzi, Jing Ren, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovsjanikov. Zoomout: Spectral upsampling for efficient shape correspondence. ACM Transactions on Graph- ics (TOG), 38(6):155, 2019.
Huda Nassar, Nate Veldt, Shahin Mohammadi, Ananth Grama, and David F Gleich. Low rank spectral network alignment. In Proceedings of the 2018 World Wide Web Conference, pp. 619- 628, 2018.
Dorian Nogneng and Maks Ovsjanikov. Informative descriptor preservation via commutativity for shape matching. Computer Graphics Forum, 36(2):259-267 2017.
Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. Func- tional maps: flexible representation of maps between shapes. ACM Transactions on Graphics (TOG), 3144::0::1330 2012.
Maks Ovsjanikov, Etienne Corman, Michael Bronstein, Emanuele Rodolå, Mirela Ben-Chen, Leonidas Guibas, Frederic Chazal, and Alex Bronstein. Computing and processing correspon- dences with functional maps. In SIGGRAPH 2017 Courses. 2017.
E. Postolache, M. Fumero, L. Cosmo, and Rodolà. A parametric analysis of discrete hamiltonian functional maps. Computer Graphics Forum, 3935):003-118, 2020. doi: https://doi.org/100 1111/ 140.2
Jing Ren, Simone Melzi, Maks Ovsjanikov, and Peter Wonka. Maptree: Recovering multiple solu- tions in the space of maps. ACM Trans. Graph., 39(6), November 2020a.
Jing Ren, Mikhail Panine, Peter Wonka, and Maks Ovsjanikov. Structured regularization of func- tional map computations. CoRR, abx/2009.14624, 2020b.
Emanuele Rodolà, Luca Cosmo, Michael M Bronstein, Andrea Torsello, and Daniel Cremers. Partial functional correspondence. Computer Graphics Forum, 36( 11:222-2336 2017.
Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction net- works with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105635): 12768, 2008
Huynh Thanh Trung, Nguyen Thanh Toan, Tong Van Vinh, Hoang Thanh Dat, Duong Chi Thang, Nguyen Quoe Viet Hung, and Abdul Sattar. A comparative study network alignment tech- niques. Expert Systems with Applications, 140: 12883, 2020.
Fu-Dong Wang, Nan Xue, Yipeng Zhang, Gui-Song Xia, and Marcello Pelillo. A functional repre- sentation for graph matching. IEEE transactions pattern analysis and machine intelligence, 2019.
H. Weyl. Ueber die asymptotische verteilung der eigenwerte. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematish--Phyilae Physikalische Klasse, 1911:110-117, 1911. URI.
httt:://eudl..oo/ wotg//o///5/3
Yu Wu, Wei Wu, Ming Zhou, and Zhoujun Li. Sequential match network: A new architecture for multi-turn response selection in retrieval- based chatbots. CoRR, abs/1612. 2016.
Lyudmila Yartseva and Matthias Grossglauser. On the performance of percolation graph matching. In Proceedings of the first ACM conference on Online social networks, pp. 119-130, 2013.
Wayne W. Zachary. An information flow model for conflict and fission in small groups Journal of Anthropological Research, 33(4):552-473 1977. ISSN 00917710. URL. http::// www.. stor wtt.:orgg/aaaaeeeeeeeeeeee
Shijie Zhang, Hongzhi Yin, Tong Chen, Quoe Viet Hung Nguyen, Zi Huang, and Lizhen Cui. Gen- based user representation learning for unifying robust recommendation and fraudster detection. CoRR, abs/2005. 10150, 2020.
12

---

Under review as a conference paper at ICLR 2023
Si Zhang and Hanghang Tong. Final: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1345- 1354, 2016.
Yabin Zhang, Minghan Li, Ruihuang Li, Kui Jia, and Lei Zhang. Exact feature distribution matching for arbitrary style transfer and domain generalization. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 8035-8045, 2022.
Li Zhao, Yongmei Liu, Chaoguang Men, and Yubo Men. Double propagation stereo matching for urban 3-d reconstruction from satellite imagery. IEEE Transactions on Geoscience and Remote Sensing, 60:1-17, 2022.
Fan Zhou, Lei Liu, Kunpeng Zhang, Goce Trajcevski, Jin Wu, and Ting Zhong. Deeplink: A deep learning approach for user identity linkage. In IEEE INFOCOM 2018-IEÉE conference on computer communications, pp. 1313-1321. IEEE, 2018.
A INTERPRETATION OF THE FUNCTIONAL MAP MATRIX
A.1 MATRIX REPRESENTATION
In the case of graphs, the functional map matrix is simply written as:
C Φ S
(4)
where 4, E X &2 E I Vall contain the first eigenvectors of the symmetrically normalized graph Laplacians of G₁ and G2 respectively, and S E RR Vi x/Val a matrix encoding the node-to- node correspondence. Note that differently from the case of surface meshes, in Equation 4 write & instead of using the pseudo-inverse $ this is due to the fact that the graph Laplacian eigenvectors are orthogonal with respect to the standard dot product, i.e., + Φ and $ Φ1 T. This makes the matrix C' easy to compute by simple matrix multiplication.
A.2 COMPARISON WITH SMOOTH SURFACES
In the case of smooth surfaces, it has been shown (Rodolà et al. 2017) that the sparsity pattern of matrix C' can be well approximated by a simple formula. Given a surface M and an isometric part N, the matrix C is approximately diagonal, with diagonal angle a proportional to the ratio of surface areas:
Arca(A)
(5)
Area(M)
As special case, full-to-full isometric shape matching yields diagonal matrix C, since Arca(N) Arca(M). This result comes directly from an application of Weyl's asymptotic law for Laplacian eigenvalues of smooth manifolds (Weyl 1911), which relates the eigenvalue growth to the surface area of the manifold via the relation:
(2T)²
A Area(M)2zd 22/d
where d is the dimension of the manifold (d = 2 for surfaces). We refer to (Rodolà et al. 2017 Eq. 9) for additional details pertaining surfaces.
However, Weyl's law (Equation 6) does not hold for graphs, since there is not well-defined notion of "area" graph. In fact, when we work with graphs and subgraphs, we observe that matrix C does not necessarily follow diagonal pattern. More general sparse structures are observed in the coefficients of C, but an explanation rooted in differential geometry is not readily available.
In Figure 7 report additional examples with large abstract graphs undergoing partiality transfor- mations, showing that clear patterns appear rather consistently across different datasets.
Based on these observations, we believe there is intriguing theoretical gap between what has been observed in the case of smooth manifolds, and what we report for graphs in this paper. In the former case, geometric explanation has been proposed in the literature. In the latter case, empirical evidence yields similar results, yet seems to be a purely algebraic phenomenon that remains to be addressed.
13

---

Under review as a conference paper at ICLR 2023
CORA
PP10
full graph: 2485 nodes; subgraph: 1491 nodes
full graph: 1546 nodes; subgraph: 1422 nodes
100
500
16
Amuzon Phoso
Amazan Computer
full graph: 7487 nodes; subgraph: 609 nodes
full graph: 13381 nodes; sulgraplh: 800 modes
100
800
Figure 7: Functional maps computed over abstract graphs from 4 different datasets (CORA McCal-
lum et al. 2000). PPIO (Hamilton et al. 2017). Amazon Photo McAuley et al.) 2015) and Amazon Computer McAuley et al. 2015)), showing clear pattern in all cases. For each dataset, compute the functional map matrix C between the complete graph and a subgraph; the subgraph is obtained
according to semantic criterion depending
the dataset, e.g., for Amazon Photo, by considering the subgraph of nodes belonging to the same product category. For each functional map matrix C, we also show a zoom-in (framed in red). All the matrices are sparse, and have clean structure that in some cases approximates slanted diagonal. The wide matrix on the bottom is computed on Amazon Photo (using a different subgraph than the one used in the example above it), and shows that the sparse behavior is maintained throughout the entire spectrum.
A.3 NUMBER OF EIGENVECTORS
Given two graphs G2 and G2 with and nodes respectively, the node-to-node map S has size n X m, thus scaling quadratically with the number of nodes.
By contrast, matrix C as defined in Equation 4 has dimensions that only depend the number of Laplacian eigenvectors encoded in the matrices 11, D2. If one chooses the first k < m Laplacian eigenvectors for G1 and the first la n. Laplacian eigenvectors for G2, the size of C is k2 kn- Observe that C' is rectangular in general, but can be made square by choosing k = k2 if so desired.
The experiments in Figure 6 and show that the number of eigenvectors increases, the perfor- mance also increases. In particular, Figure S Eemonstrates that, in most of the cases, a low percentage of eigenvectors (about 5%) suffices to retrieve a good node-to-node correspondence; while 50% of the eigenvectors on all graphs the error is above 90%. As general guideline, in this paper we typi- cally use 20 50 for graph with 1000 nodes, leading to an especially compact representation C.
A.4 REGULARIZING BEHAVIOR
Using & & n eigenvectors in the construction of C' has a regularizing effect on the map, akin to a low-pass filtering of the correspondence.
14

---

Under review as a conference paper at ICLR 2023
MAP(S))
Eigenvectors percentage
Figure 8: MAP(%) the correspondence on different datasets increasing number of eigenvectors (expressed as percentages, growing from 1% to 75%). The correspondences obtained from ground-truth functional maps.
particular, when we use all the eigenvectors Φ and 42 to construct C, Equation 4 corresponds to orthogonal change of basis; therefore, the representations S and C' are equivalent and have the same dimensions. Truncating the bases to the first 1 and ky eigenvectors, as described in the
Appendix A.3 yields low-rank approximation C ze S. In signal processing terms, matrix C as a band-limited representation of the node-to-node correspondence S.
The regularizing effect is desirable in many cases, but is traded off for loss in accuracy if precise node-to-node correspondence desired. On the one hand, if the map C' is used to transfer smooth signal (e.g. node-wise features like spectral positional encodings or carrying semantic information depending on the data), then the loss in accuracy is negligible, since Laplacian eigenvectors are optimal for representing smooth signals (Ailalo et al., 2015); on the other hand, transferring non- smooth signals via a small C' has the effect of filtering out the high frequencies. If high frequencies are desired, it is often sufficient to just increase the values of kj 12, leading to bigger matrix C.
D=D- A
1/2 AD 1/2
A.5 CHOICE OF LAPLACE OPERATOR
A functional map be computed from the eigenbasis of any linear operator. In this paper we use the symmet- rically normalized graph Laplacian L = I- DD valid alternative is the standard Laplacian -= D A. which shows similar behavior to the normalized counter- part. At practical level, we observed that the Lapla- cian L suffers from more problems of high multiplicity at lower frequencies, see Figure 9
Figure 9:
Functional map computed with two different Laplacians between the CORA graph and its subgraph.
In the special case where the graph is constructed top of a point cloud sampled from a (possibly high-dimensional) manifold M, it has been shown that the eigenvectors of the normalized graph Laplacian converge to the eigenfunctions of the Laplace- Beltrami operator on M (Belkin & Niyogi 2006). However, as discussed in Appendix A.2 our case is more general. We consider generic abstract graphs without explicit underlying manifold, iee. we do not construct our graphs from input point clouds. Further, in Belkin Niyogi (2006) is assumed that M is compact infinitely differentiable Riemannian submanifold of 12 without boundary, meaning that partiality transformations, which are the main focus of this paper, are not considered.
B DATASET AND IMPLEMENTATION DETAILS
In this section report additional details about the experimental setup used in the main manuscript.
15

---

Under review as a conference paper at ICLR 2023
B. DATASETS
In 2 we sum up the main statistics across all the datasets and benchmarks used in our experi- ments. In addition number of nodes, number of edges, graph diameter and average node degree, in the table we also report the application domain of each dataset, the task where they are used, the type and number of node-wise features (where used). Since PPI and QM9 are collections of graphs, we used only subset. In particular, from the PPI dataset we used the first and fourteenth graphs (specified with 0 and in the experiments). The Cat graph derived from the corresponding mesh of the SHREC' 16 Partial Deformable Shapes benchmark (Cosmo et al. 2016b).
Table 2: Summary of statistics about the datasets used in experiments.
Thiasse
Nodes
Edges
Diameter
Averuee degree
Domain
Task
Featues
of Festures
Number
QM9 Kliepera at al.
2020
29
47
3.24
Chemisny
Graph regression
Kamae
Zachary
197
Social
Node classification
PP1
Familion
2017
1546
17699
21,90
Chemistry
Graph regression
Glene autiibute
50
Chosee Ghies nl.
199
2120
3731
28
3,50
Ciation networks
Node classification
Bog-of- Words
3703
Com
McCallum
2485
5069
Ciation networks
clavsification
Minnesota
2035
1298
Roadmap
PP1 13 (lamilooo et al.
2017
3450
56857
31,68
Chemistry
Graph regression
Gene aumbutes
50
Douhan
WWaer 2016
5906
8164
Social networks
Network alignment
McAplex
Co-purchaase
Node classification
Bug Words
745
Cat Cosma
10000
19940
5.99
Genmetry prncessing:
Shage matching
HandAmazon Zhang al
X00
11944
4417576
739.71
Product reviews
Frand detection
Bag of Words
25
Compuier (cAAley
13381
purchasse
Node classification
Bag
B.2 ROBUSTNESS TO REWIRING
In this Section, we formally define the connectivity changes and functional map robustness used in Section 5.1 Given two graphs G EV, and G' = (V", EE).. we measure the amount of change from G to G' as the (minimum) number of edits needed to transform E to E", divided by |B]] [1E- + El),, In our experiments, we consider small changes in the graph connectivity as [F|
a perturbation of 3% of the edges. The rewiring operation that we applied to the graphs consists of the deletion addition of the same amount of edges.
We define the difference between the functional map C and as ||C - C Note that there is ambiguity in the sign of the eigenfunctions of C"; to factor it out from the error computation, use the sign that minimizes the error.
In Figure 10 show the functional maps generated from the experiment in Figure 5 Figure 10a
shows the functional map between the full and partial graphs from 0% to 30% of rewiring: Fig- ure TOb shows the variation in the functional representation between the non-rewired case and the different percentages of rewiring.
B.3 SIGNAL TRANSFER
We evaluate the fidelity of the transferred signal with the Root Mean Squared Error between the transferred signal and the ground truth signal g (obtained via the ground truth node-to-node corre- spondence):
RMSE
(0()) o(1))2,
where n is the number of nodes in the subgraph.
Table 3: RMSE of the signal transfer com- puted with two functional maps obtained with different methods.
As anticipated in the main manuscript, the func- tional map C can also be computed from features independent of topological changes with Equation g On Citeseer, the node features are Bag-of-Vo Words that identify each node, therefore they should not change under perturbations of the graph topology. We use probe functions the features defined each node and compute a map C' using 50 eigen- functions without any regularizer refinement to
Subgraph
Cgt
1
0.68
0.85
2
0.96
0.97
3
0.60
0.63
4
0.81
0.83
5
0.72
0.77
Mean
0.75
0.81
16

---

Under review as a conference paper at ICLR 2023
0%
3%%
6%
9%
12%
15%
18%
21%
24%
27%
30%
Minnesota
396
6%
9%
12%
15%
18%
24%
27%
0%
396
6%
99%
12%
15%
18%
21 9
24%
27%
30%
0%
33%
61%
9%
12%
15%
18%
96
24%
27%
30%
QM9
01%
35%
61%
9/%
12%
15%
18%
21%
24%
27%
30%
Karnte
(a) The plotted matrices represent the functional map between the full and partial graphs from 0% to 30% of rewiring, showing the effect of rewiring on functional map structure.
3%
6%
9%
12%
15%
18%
21%
24%
27%
30%
6%
9%
12%
15%
21%
24%
27%
30%
Minnesoto
3%
6%
9%
12%
15%
18%
21%
24%
27%
30%
6%%
9%
12%
15%
27%
QMP
35%
6%
9%
12%
15%
18%
21%
24%
27%
30%
Kanale
(b) The plotted matrices encode the element error of the functional map after the topological perturba- tions. Error encoded color, growing from white to red.
Figure 10: Robustness of the map to the simultaneous action of partiality and rewiring of the subgraph. The rewiring operations are increasingly stronger, with increments of 3% of the total number of edges (starting from 3% and reaching 30%). The second column shows one representative example (per dataset) of such topological modifications, depicting the added edges in green, and the removed edges in red. The plotted matrices represent the functional map after the topological perturbations, showing the effect of rewiring on the functional map structure.
17

---

Under review as a conference paper at ICLR 2023
highlight the contribution of the features. We compare the results of this functional map C' with the ones map Cgr obtained from the ground truth correspondences (Equation 4). Each row of Table repprssetts the RMSE of different subgraph, while the bottom row reports the mean. The results show that even we do not have a ground truth correspondence between two graphs, the functional map C' can transfer signals with good approximation.
B.4 NODE-TO-NODE MAP INFERENCE
As stated in the main manuscript, to test the effectiveness of the spectral representation when seeking mode-to-node correspondence matrix, we adopt the off thf-lf partial functional maps algorithm (FMw (Rodolà et al. 2017) and then refine the correspondence with ZuomOut (Melzi et al., 2019) (FMw + ZM). These algorithms are not specifically designed for graph matching, but can work with generic spectral representations, which is one of their main benefits.
We implemented the F FM optimization MATLAB through the manopt package (Boumal al, 2013). We considered minimization problem with the form:
C arg Main||CCa Bl12,1 + R(C), CEREX
(8)
where A and B are the coefficients in the Laplacian basis for set of corresponding probe functions, while RC)) some additional regularizer. As probe functions we computed smooth functions for the given set of landmark matches. For all the methods that accepted nodes features (FINAL, REGAL, GRASP) as input, we used the same functions as nodes features. R(C)) fosters additional structure C and is defined as:
R(C)= = M1 O WIE u12
CIC js E((CT Clee- E4h
where each term has its weight fl, #2 and μ3- W is mask matrix that acts through element- wise multiplication and encodes the relation between the eigenvalues of the two shapes, which approximates the daited-diagonal structure of C induced by the partiality. In particular, we com- puted W with the complex resolvent method proposed in Ren et al. (2020b). The term weighted by /42 promotes orthogonality of the map by penalizing the off-diagonal entries of C C. Finally de {0, 1} VÊ; the entries equal to represent which singular values of C are expected to be non- zero. A refinement, similar to the iterative closest point algorithm (Besl & McKay 1992) in the space of the coefficients, is then applied to the matrix C. As final step, the spectral refinement ap- proach of ZoomOut (Melzi et al. 2019) is applied to the computed C. Given a map of size 50 x 50 input, apply ZoomOut to its 37 37 sub-matrix and get back refined matrix Czm of size 50 x 50.
The ground-truth functional map (GT) is obtained through Equation 4 where S is the ground-truth correspondence matrix.
All the methods compared to in Section 5.3 of the main paper were taken from the public bench- mark (Trung et al. 2020). To run the experiments, we used the standard parameters suggested in their code. As node features, we used the same probe functions defined from the landmarks in F FMw. PALE was trained on the ground-truth correspondences given by the 50 landmarks.
B.5 COMPUTATIONAL TIME
In Table we report the optimization time needed to compute the correspondences of Table from the main paper. For functional map-based matching algorithms (FMw. FMw + Z.M we did not consider the computation of the eigenvectors since is an offline cost as eigenvectors can be pre- computed once and re- re-used. For FMw + ZM, only report the computational time of ZoomOut refinement starting from an input functional map. All the experiments were performed on a Intel(R) Core(TM) 17-9700K CPU @ 3.60GHz.
18

---

Under review as a conference paper at ICLR 2023
Table Comparison of the computational time (in seconds) needed by different methods compute mode-to-node correspondence, across several datasets. Spectral based methods (last two columns) the most efficient.
Partialtt
IsoRank
FINAL
REGAL
PALE
GRASP
FMw
FMw
+2M
Cal
270.44 + 9.84
156.49 = 2:73
36.78 = 0.86 3586.4 4 109.5 1057.7
100.59
20.73
1.67
5.45
0.28
Minnesota
pulch
32.18
3.94
10:21
0.15
7:08
145.72
G48.43
267.5
2.83
0.38
31.34
4 3.1
0.35
7.33
0.15
211.99
148.3
2.89
Cora
class
14.92
4 2.4
01.61 + 10.2
10.92 # 0.9
434.13 + 35.8
118.61 + 72
1.96 0.1
0.38 + 0.02
Doubun
unline- offine
11.34
27.07
10.41
337.56
16.32
4.43
0.03
MAP(50)
Subgraph Patch
Subgraph (b) Holes
Figure 11: MAP(%) of the correspondence on different datasets at decreasing size of the subgraph (expressed as percentages, decreasing from 90% to 50%) with two types of partiality: patch (left)
and holes (right). The correspondences are obtained from ground trutth functional maps.
C ADDITIONAL EXPERIMENTS
C.I PARTIALITY PERCENTAGE
The aim of this experiment is to study how much the performance of the functional representation for correspondence task degrades with different levels and types of partiality.
In Figure II we perform an experiment similar to the one in Section 5.3 of the main paper and test how the MAP of the correspondence changes when we consider subgraphs of different dimen- sions. In particular, we test 2 partialities: patch and holes. The former is obtained by expanding a neighborhood from a given random node until certain number of nodes is reached. The latter obtained by removing random nodes with their immediate neighborhood. The main difference is in the sparsity of the two partialities. The first keeps a cluster of nodes without changing the inner connectivity of the graph; the latter is sparser in the sense that it removes paths between nodes of the graph, changing the whole connectivity the graph. In Figure [2] we plot the functional maps different percentages of partiality of type patch (left) and holes (right).
C.2 REWIRING
In the main paper and in Figure I0 we highlight how the functional map degrades when we apply sequence local rewiring operations. Here we consider much stronger variation, namely, a global rewiring where we do not limit the topological perturbation to local neighborhood. The results are reported in Figure 13
we show the functional maps under the action of pure rewiring pertur- bations, without any partiality involved.
Finally, in Figures and 15
19

---

Under review as a conference paper at ICLR 2023
Minnesoto 90%
80%
70%
60%
60%
Minnesota
90%
80%
70%
00%
50%
CORA
CORA
Citescer
Citeseer
(a) Patch
(b) Holes
Figure 12: Robustness of the map to the action of two partialities: patch and holes. The partialities are increasingly wider, from a subgraph with 90% of the nodes a subgraph with 50% of the nodes. As partiality increases, the functional map structure becomes less defined.
Cal
100%
Minnesota
10%
30%
50%
100%
CORA
10%
30%
50%
100%
Robustness of the map the simultaneous action of partiality and rewiring of the subgraph. The rewiring operations are increasingly wider, involving nodes and edges farther apart. The left column shows the full graph, while the pairs composed by graph and matrix show the rewiring operation and the resulting functional map, starting with rewiring involving just nodes within 1% of the graph diameter (left) up the full graph diameter (right).
Figure 13:
Minsesota
72%
80%
CORA
16%
24%
32%
40%
48%
56%
64%
72%
80%
Karate
24%
32%
40%
64%
72%
80%
Robustness of the map to rewiring of the subgraph. The rewiring operations are increas- ingly stronger, with increments of 8% of the total number edges (starting from 8% and reaching 80%). The plotted matrices represent the functional map after the topological perturbations, show- ing the effect of rewiring on the functional map structure.
Figure 14:
20

---

Under review as a conference paper at ICLR 2023
1%
5%
10%
30%
50%
100%
Minnesath
1%
5%%
10.
30%
50%
100%
CORA
1%
5%
10%
30%
50%
100%
Figure 15: Robustness of the map to rewiring the subgraph. The rewiring operations are increas- ingly wider. involving nodes and edges farther apart. The left column shows the full graph, while the others columns show the resulting functional map, starting with a rewiring involving just nodes within 1% of the graph diameter (left) up the full graph diameter (right)
21


Reviews:
[{"review_id": "cBmdpUUko92", "reviewer": "Reviewer_BSxT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The article discusses the adaptation of manifold alignement (as studied, e.g., 10 years ago in Osjanikov et al, 2012) to the setting of graphs. One relevant and nice idea is not to consider not only full graph alignment, but also subgraph alignments even in the non-isomorphic case. The authors show that the notion of functional map correspondance can be translated to graphs as looking at mixed eigenmaps connecting eigenvectors of the two considered domains (graphs). Then some empirical results follow. ", "summary_of_the_review": "For all the reasons above, my initial recommendation is to reject the paper, yet I would be happy to revise lmy judgement if the authors revise significantly the manner to present the work, so as to improve clarity and better put forward the methodological novelties that are now hidden in lengthy appendices and absent from the main text. ", "strength_and_weaknesses": "Strength:\n\n1- as mentioned above, the idea of using map correspondence is nice, and some insghts gained on the alignment between a graph and subgraphs (even non-isomorphic ones) are interesting. This does not appear to have be commented much.\n\n2- the conceptual simplicity of the proposed method is interesting, meaning that the writing of eq. (4) appears almost like a method in itself.\n\nWeaknesses :\n\n1- The writing of the article is wrong for me : i) All the discussions in sections 1 and 2 are, for me, off for a scientific article. Some constatations in 1 are forced without actual any fact to support that (e.g. \"has been largely overlooked\" ; \"common misconception\" ? it could be mere lack of interest due to more relevant things to do) ; Section 2 is way too long to discusse node-to-node correspondence and functional correspondence while there is only scarce comparisons to these state-of-the-art methods in the text (only in Table 1, which is not that conclusive, see underneath)\n\n2- On the other side: the interesting parts of the paper are mostlty in the Appendices.: A.1, A.3, A.4, most of B. This is disturbing to read comments in the main text that are not always useful (details in Section 2), founded (in 1), or with enough details to understand (all of Section 4 where there is no equation describing the proposed method). In the current state of presentation, I don't think this article is suited to the audience of the conference (interested in understading the proposed method and not only in looking at results and discussions).      \n\n3- the mentioned insight about alignment between a graph and subgraphs is not that surprising for people working witgh Graph Laplacians. Hence, the presentation of the results related to that should be dowtoned a bit.\n\n4- the results in 5.3, about node-to-node correspondence, are somehow disappointing (especially w.r.t. the high hopes and stakes puty forward by the authors in Sec 1 to 4): on the task, REGAL performs way better; the proposed method is significantly further away from Ground Truth. \n\n5- I didn't find any point of  comparisons for results in 5.1 and 5.2. No SOTA to compare to ?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZfadUHKmnG", "reviewer": "Reviewer_iFfS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes that a robust spectral alignment map may exist between graphs and partial graphs (which could be subgraphs in the original graph). The claims are driven by empirical observations on various real-world datasets. ", "summary_of_the_review": "Subgraph alignment is an interesting observation. However, the paper lacks in comparisons with existing literature. The experiments are not rigorous enough for a reader to draw meaningful insights that could be generalized beyond the datasets presented in this paper. ", "strength_and_weaknesses": "Strengths:\n\nAlignment between graphs and their sub-graphs is an interesting problem. The paper provides convincing empirical evidence that a correspondence between the functional maps (defined by the eigenvectors) may exist between graphs and their sub-graphs even when the sub-graphs are localized. \n\nWeaknesses:\n\n1. **Related Work** : The comparison with existing works in the literature is critically lacking. There exists a rich literature on domain adaptation and meta learning where the contributions involve learning linear mapping to align data from two domains. \n\n      *a. Sun, Baochen, Jiashi Feng, and Kate Saenko. \"Return of frustratingly easy domain adaptation.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.*\n\n      *b. Yang, Yi, et al. \"Data-Efficient Brain Connectome Analysis via Multi-Task Meta-Learning.\" arXiv preprint arXiv:2206.04486 (2022).*\n\n     *c. Pilanci, Mehmet, and Elif Vural. \"Domain adaptation on graphs by learning aligned graph bases.\" IEEE Transactions on Knowledge and Data Engineering (2020).*\n \n    Moreover, inference over graph limit objects, such as graphons, relates to the setting of a subgraph constructed by eliminating nodes randomly all over the graph (such as in Fig. 3). \n\n2. While the observation that the eigenvectors of a partial graph and the complete graph may correlate is not trivial, the experiments provide no concrete insight into how and why such correlation may exist. For instance, can you meaningfully quantify the similarity between the subgraph and graph sufficient for the correlation pattern in Fig. 2 to emerge? Are the datasets used in Fig. 6  and Fig. 8 low rank? \n\n3. The paper focuses on learning only linear mappings whereas there seem to be no technical challenges to learn non-linear mappings between the functional maps. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HSVUR-9np8g", "reviewer": "Reviewer_rw4F", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper talk in detail about the subgraph alignment problem. Which they assume the graph laplacian of the graph is well preserved by the subgraphs. There are some good merit of the paper in turns of experiments. But overall, I find the paper quit confusing. And the basis of the paper is too empirical and not justiable. ", "summary_of_the_review": "This paper try to tackle subgraph matching based on the empirical visualization. But without valid proof, the visualization is not very intuitive thus make it hard to evaluate the paper. ", "strength_and_weaknesses": "The paper try to address the subgraph matching with eigen decomposition. And the whole paper based on a very strong assumption that the eigen information in subgraph is preserved compared with original graph. \n\nThis observation is quite empirical and without solid proof in this paper. Though the author conducted the extensive experiment but that does not exactly prove the same thing. \n\nFrankly, I do agree in some cases, the subgraph would definitely preserve the information of original graph like in figure 2 of the paper. But for most of the cases, subgraph would be very different than the original graph. Thus it is very hard to do the matching/alignment. And make it difficult to evaluate this paper. Overall, I do not think this result is valid given the empirical observation. Thus I intend to give this paper a boarderline assessment. \n\nI do think investing on some cornor case, where the eigen information did not preserve the information would help improve this paper.  \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject