SeedGNN: Graph Neural Network for Supervised Seeded Graph Matching
Authors: Liren Yu
Jiaming Xu
Xiaojun Lin
Venue: Submitted to ICLR 2023 (2023)
Keywords: seeded graph matching
Graph Neural Network (GNN)
percolation
multi-hop witnesses

Abstract: There have been significant interests in designing Graph Neural Networks (GNNs) for seeded graph matching, which aims to match two (unlabeled) graphs using only topological information and a small set of seeds. However, most previous GNNs for seeded graph matching employ a semi-supervised approach, which requires a large number of seeds and can not learn knowledge transferable to unseen graphs. In contrast, this paper proposes a new supervised approach that can learn from a training set how to match unseen graphs with only a few seeds. At the core of our SeedGNN architecture are two novel modules: 1) a convolution module that can easily learn the capability of counting and using witnesses of different hops; 2) a percolation module that can use easily-matched pairs as new seeds to percolate and match other nodes. We evaluate SeedGNN on both synthetic and real graphs, and demonstrate significant performance improvement over both non-learning and learning algorithms in the existing literature. Further, our experiments confirm that the knowledge learned by SeedGNN from training graphs can be generalized to test graphs with different sizes and categories. 

Under review as a conference paper at ICLR 2023
SEEDGNN: GRAPH NEURAL NETWORK FOR SUPER- VISED SEEDED GRAPH MATCHING
Anonymous authors Paper under double-blind review
ABSTRACT
There have been significant interests in designing Graph Neural Networks (GNNs) for seeded graph matching, which aims to match two (unlabeled) graphs using only topological information and a small set of seeds. However, most previous GNNs for seeded graph matching employ semi-supervised approach, which re- quires a large number of seeds and can not learn knowledge transferable to unseen graphs. In contrast, this paper proposes new supervised approach that can learn from a training set how to match unseen graphs with only a few seeds. At the core of our SeedGNN architecture are two novel modules: 1) a convolution module that can easily learn the capability of counting and using witnesses of different hops; 2) a percolation module that can use easily-matched pairs new seeds to percolate and match other nodes. We evaluate SeedGNN on both synthetic and real graphs, and demonstrate significant performance improvement over both non-learning and learning algorithms in the existing literature. Further, our exper- iments confirm that the knowledge learned by SeedGNN from training graphs can be generalized to test graphs with different sizes and categories.
INTRODUCTION
Graph matching, also known as network alignment, aims to find the node correspondence between two graphs that maximally aligns their edge sets. As ubiquitous but challenging problem, graph matching has numerous applications, including social network analysis (Narayanan et al., 2008
2009
Zafarani al. 2015| Zhang et al., 20.5bb011bb al Chiasserini et al., 2016). computer vision (Conte
iet al. 2004; Schellewald et al. 2005; Vento et al. 2013)). natural language processing (Haghighi 2005), and computational biology (Snghh et 2008 Kazemi et al., 2016 Kriege et al.) 2019).
let al.]
This paper focuses on seeded graph matching, where a small portion of the node correspondence
between the two graphs is revealed as seeds, and we seek to complete the correspondence by growing from the few seeded node pairs. Seeded graph matching is motivated by the fact that, in many real applications, the correspondence between small portion of the two node sets is naturally available. For example, in social network de ce-anonymization, some users who explicitly link their accounts across different social networks could become sceds (Narayanan et al.) [2008] 2009). Knowledge of even a few seeds has been shown significantly improve the matching results for many real-world graphs (Kazemi et al. 2015 Fishkind et al., 2019).
Recently, the Graph Neural Network (GNN) approach for graph matching has attracted much search attention. Although such a machine-learning-baass able theoretical guarantees, it has the potential learn valuable features from a large set of train- ing data. Unfortunately, to date GNN has not been successfully applied to seeded graph matching. Most previous GNNs for seeded graph matching are limited wesssemmsppe superviee learning paradigm, which only operates on a single pair of graphs (Zhang et al., 2019 Li et al.) 2019a b Zhou et al.) 2019 Chen al. 2020 Derr et al.] 2021) and treats the seed set as the labelled training data, The goal is to learn the useful features from the seed set, and then to generalize the knowledge to the rest of the unseeded nodes. This semi-supervised learning, however, suffers from two major limitations. First, in order to obtain high matching accuracy, the set of seeds needs to be sufficiently large, which is often unrealistic in practice. Second, as this semi-supervised setting only learns within a given pair of graphs, there is no effort in transferring knowledge from one pair of graphs to other pairs of unseen graphs, which severely limits GNNs' potential in distilling the common knowledge from a large set of training graphs. A natural but fundamental question is
approach usually does not possess prov-

---

Under review as a conference paper at ICLR 2023
Can we learn to match two graphs from only a few seeds while generalizing to unseen graphs?
This paper provides an affirmative answer to this question. Specifically, we design a novel GNN architecture through supervised approach, namely SeedGNN, that can learn from many examples of matched graph pairs, distill the knowledge into the trained model automatically, and then apply such knowledge to match unseen graph pairs with only few seeds. In contrast prior GNN approach for seeded graph matching that apply GNNs separately to each graph and learn a node- embedding for each node (by aggregating neighborhood information within each individual graph), a key departure of our SeedGNN architecture is to apply the GNN jointly over two graphs and to learn a pair-wise similarity for each pair of nodes directly. As we will discuss further below, this pair-wise GNN architecture is crucial for learning both useful features (from seeds) and the best way to synthesize them in different types of graphs. (We note that this type of pair-wise GNNs have been used in supervised learning approach for seedless graph matching in Rolínek et al. (2020); Wang et al. (202T). However, they have not been used for seeded graph matching. See Section 2 for further discussions.) Numerical experiments on both synthetic and real-world graphs show that our SeedGNN significantly outperforms the state-of-the-ar algorithms, including both non-learning and learning- baase ones, in terms of seed size requirement and matching accuracy. Moreover, our SeedGNN can generalize to match unseen graphs of sizes and types different from the training set.
At the core of our SeedGNN are two innovative designs. One is the convolution module that learn to count "witnesses" at different hops - a notion that plays a pivotal role in seeded graph match- ing (Mossel et al.. 2019). Here, the ê-hop witnesses of a node-pair are seeded pairs that lie in the neighborhood at é hops. Naturally, true pair is expected to have more witnesses than a fake pair. As we will further discuss in Section 4.1 and Section 4.2 our pair-wise SeedGNN architecture is much more effective than existing node-based GNNs in learning how to count witnesses, in a man- ner that can be easily generalized to unseen graphs. The second innovation is the percolation module that matches high-confidence node-pairs at one layer and propagates the matched node-painy as new seeds to the subsequent layers, triggering a percolation process that matches large number of node pairs. However, we emphasize that it remains highly non-trivial how to best utilize either the witness or the percolation idea for achieving high matching accuracy. Indeed, when graphs are very sparse, even true node-pairs may not have enough witnesses if the number of hops E is small; when graphs are very dense, a fake pair may also have many witnesses if é is large. Similarly, a fake pair may be incorrectly propagated
new seed, which can lead to many cascading errors. The pair-wise archi- tecture of SeedGNN is also crucial to facilitate learning how to best synthesize these two modules. As result, our SeedGNN can potentially figure out which hops of witnesses are more reliable and what "cleaner" new seeds should be used to trigger the percolation process.
2 FURTHER RELATED WORK
Theoretical Algorithms Various seeded matching algorithms have been proposed based on hand- designed similarity metrics computed from local topological structures (Pedarsani et al., 2011 Yart- seva al. 2013] Korula et al.) 2014; Chiasserini et al.) 2016 (Shirnni et al.] [201]] 7 Mossel et al.] 2019 Yu et al. 2021b). The theoretical analysis on these algorithms explains why a particular set of features (e.g.. witnesses (Korula et al.) 2014) and percolation (Yartseva et al., 2013) are valuable for graph matching. However, these theoretical algorithms may not synthesize different features most effectively. See detailed discussion in Appendix A In contrast, our SeedGNN can potentially figure out what combinations of features are most useful, and therefore it can potentially outperform known theoretical algorithms (see our experiments in Section and Appendix C..)
GNN for Seedless Graph Matching As we discussed earlier, most existing GNNs for seeded graph matching take a remi-supervised learning approach. In contrast, our SeedGNN falls into a supervised learning approach, which aims to transfer knowledge from training graphs to unseen graphs. In the literature, such a supervised learning approach has been applied to seedless versions
of the graph matching problems in ŞZanfir et al. 2018 Wang et al. 2019 2021 2020a 2021 Jiang eet al. 2022: Wang et al. 2020b Fey et al. 2020 Rolinek et al.) 2020 Gao et al.) 202 Yu et al.) 2021c). For such seedless matching problems, non topologgll node features are often assumed to be available. Thus, a mode-based GNN is effective in learning how to extract useful node representa- tions from high-quality non- topoologll node features. Unfortunately, from our own experience, we found that it is not easy to design node-based GNN that effectively utilizes seed information (see
2

---

Under review as a conference paper at ICLR 2023
In contrast, our pair-wise SeedGNN architecture is much more effective in learning how to use seed information and synthesize various features. The design of our pair-wise architecture is also related to the work in Rolinek et al. 2020 Wang et al. (2021) How- ever, [Rolinek et al. 2020) still corresponds to node-based GNN method and relies on high-quality
detailed discussions in Section 4.1
node features. The NGM architecture of Wang al. (202T is most similar
However, NGM was not designed for seeded graph matching and has not been evaluated for this purpose either. See
detailed discussion Appendix A..] and our experiments in Section 5.2 where we find that, when
extended to seeded graph matching, the NGM algorithm in Wang et al. (2021) does not generalize well when the test graph is with much larger size and node-degree than the training graph.
Inductive Semi-supervised Learning on Graphs Our goal of using supervised learning for
seeded graph matching shares some similarity with [Wen et al. (202T. which also aims to both
perform inductive learning (i.e., learn transferable knowledge from training graphs) and use a small amount of labeled data on the test graph. However, [Wen et al. 2021 focuses on node classification, which is quite different from seeded graph matching. See detailed discussion in Appendix A
More discussion on additional related work is deferred to Appendix
3 PROBLEM DEFINITION
We represent a graph of n nodes by G = (V, AV, where V [1, n) denotes the node set, and A {0, 1|m=x denotes the symmetric adjacent matrix, such that A(i,) = 1 if and only if nodes i and] j are connected. For seeded graph matching, we are given two graphs Gi (V1, Ai) of nodes and G2 = (V2, A2) of n2 nodes. Without loss of generality, we assume n2 S n2.. There is an unknown injective mapping π. V1 - V/ between G1 and G2. When x1) j. we say that i E Vi corresponds to j E V/2. Throughout the paper, we denote a node-pair by (i,j), where E Vi and j E V22 For each node-pair (i, j). if j x (i), then (i, is a true pair; if o (i), then (i is fake pair. Then, an initial seed set S containing fraction of true pairs is given. The goal of seeded graph matching
recover the ground-trui mapping π based on the observation of G1, G2 and S.
In this work, we consider the problem of seeded graph matching in the supervised setting. The train- ing set consists of several pairs of graphs, their initial seeds, and ground-truth mappings. Specif- ically, we use T = ((P(L), क ( (P(2), ,T(2)), (P(N), , (} to denote the training set, where p()) = (g g. )()) denotes the i-th training example and π (3) is the ground-trum mapping for the i-th training example. For different training examples, the sizes of graphs and seed sets could be different. Our goal is to design a GNN architecture that can learn from training examples to predict the ground-truth mappings for unseen test graphs.
4 THE PROPOSED METHOD
In this section, we present detail our proposed SeedGNN for seeded graph matching- See Figure for high-level illustration. In Section 4.1 we briefly illustrate the limitations of node-based GNNs for seeded graph matching, which motivate us to design pair-wise GNNs. We then describe the convolution module in Section 4.2] and the percolation module in Section The supervised
training procedure is presented in Section
4.4
The I-th layer
Percolation Module
Convolution Module
Softmax 6
Hungurian
furnec
unveci
Aggregatton
(2 vecl MLP
MLP
S
Masking
vecf.)
Concal
S1-1
Figure 1: An overview of the I-th layer of our SeedGNN architecture. There are layers in total and each layer consists of two main modules. With the node-pair representations st as input, the convolution module is local processing step that aggregates the neighborhood information of each node-pair and updates the representation of its similarity through neural network. The percolation module is global processing step that compares the updated similarities of all node-pain pairs and finds the highhhoofideece ones. Then, we combine the local and global information from the two modules and propagate the new representations 8141 to the next layer.
3

---

Under review as a conference paper at ICLR 2023
Notation vec(-) to denote the vectorization that converts a 11 f2 x d matrix to matrix of Ring x d, where the (i.j,))-th -thh entry of the input matrix is the ((i - 1mm + j.:)-th entry of the output matrix. Then, the unvectorization unvec(-) is the inverse operation of the vectorization.
4.1 FROM NODE- BASED GNNS TO PAIRWISE GNNS
Since most existing approaches for graph matching use node-based GNNs (Zhang et al. 2019 Chen et al. 2020; Wang et al. 2019 2020a Fey et al., 2020, Rolinek et al. 2020), we also started with node- based GNNs when we first researched the supervised approach to seeded-graph matching. However, from our experience, we found that node- base- GNNs have significant difficulty effec- tively utilizing seed information. Note that node-based GNNs are adequate for the semi-supervised setting because the seed information is only used in the training objectives. However, as we discuss earlier in the introduction, this semi-suuerrvied approach does not lead to transferable knowledge to unseen graphs. In contrast, to apply the node-based GNNs in the supervised setting, the first diffi- culty is to figure out a way to encode seed information as input. One natural attempt is to convert seeds node features input. For example, one could apply one-hot encoding, which represents the i-th seeds as a binary vector with the i-th element being 1 and 0 otherwise, However, this method needs to pre-specify the maximum number of seeds, and thus can not generalize to new graphs with even more seeds. Another possible method is random encoding, which uses a random vector to represent each seed. However, the vector dimension must also chosen to be sufficiently large; otherwise two vectors corresponding to different seeds may have too similar encodings, which may confuse the GNN. This dependency on the vector dimension will again lead to generalization issue when the test graphs have much more seeds than the training graphs
To avoid the generalization difficulty, an alternative approach is to use auxiliary "'cross-likks" across the two graphs to represent the seeds (see Figure 2). With these "cross-links", we can then com- bine the two graphs together and apply the node-based GNN on this union graph. This method is easier for generalization because the same GNN can be applied to graphs with arbitrary size and num- ber of seeds. However, the topological structure of this union graph only informs the GNN that there is seed at particular location in the neighborhood, but not the seed identity. For example. in Figure 2 even though node I and node 4' have different seeds in their neighborhoods, their local neighborhood typologies (and the seed positions) look exactly the same. Thus, it would be difficult for a node-based GNN to produce node representations that can distinguish the two nodes.
G
92
Figure 2: Let i' = (i). The red node-pairs are seeds. The red edges are cross-links.
To circumvent the aforementioned issues of existing sade-based GNNs, we instead apply GNNs on node-pairs instead of nodes. Intuitively, when we apply such a pair-wise GNN to the node-pairs (1, 1') and (1,4") in Figure 2 it can easily tell that (1, 1') has common seed, while (1,4") does not. As a result, this pair-wise GNN architecture will be able to learn generalizable knowledge from cross-links. We discuss the difference between our design and the previous pair-wise GNN architectures for seedless graph matching (Wang et al. 202T in Appendix A.I Below, we provide details of our proposed SeedGNN based this idea.
4.2 CONVOLUTION MODULE
Generalizable Encoding Method for Seeds. We follow the cross-link idea to encode the seed information as inputs for our SeedGNN, which is easier for generalization to unseen graphs as discussed earlier. Specifically, let S1 {0, 1 x be the indicator matrix for seeds among n2n2 node-pairs. If the node-pair (i,j) is a seed, we let (i,j)) be 1, and 0 otherwise. Then, we input 81 = vec(Si) E (0. 1 R miRii into our SeedGNN.
With the input of seed information, we design the convolution module for SeedGNN that can count and utilize witnesses. We first introduce the definition of I-hop witnesses (Mossel et al. 2019). Given any graph G and two nodes u, e in G. we denote the length of the shortest path from to in G by distg (u. v). Then, for each node pair (u, v) with u in 91 and v in G2. the seed (w, (w)) becomes t-hop witness for (u, a) if distg, (u, w)
take the mode-pair representations as input, our design is to apply SeedGNN to each node-pair pair across the two graphs. In this way, the pair-wise SeedGNN can directly infer from the neighboring topological
and distg, (v. rw)) = I. Since
4

---

Under review as a conference paper at ICLR 2023
structure whether there is witness. Specifically, taking the seed encoding vector $1 input, the counting of I-hop witnesses can be written as
h1 (A1 @ A2)51:
where @ denotes the Kronecker product. Likewise, we may further compute the l-hop witness- like information the 1-th layer our SeedGNN as
h4 (A1 A2)s1,
where st E R xd specified later in Section 4.3 which contains the witness- like information
within (1 - 1) >-hops. Note that this expression ① can be expanded as, for node-pair (i,j),
hul(i - 1)mg + j.:l =
Σ
s:[(u - 1)ng + v,
(u,v): 1 A2(r.)=1
which is similar the aggregation step of the standard GNN in (Hamilton et al. 2017). The only difference that we aggregate over a mode-pair's neighborhoods. A direct implementation of (T) takes (n) computation, but can reduce the complexity by letting Hi unvec(hi) and
S = un)e and rewriting [ as
Hi(:,,, t] = unvec (AA A2)st(;, t]) A,Si(;, i t 1,2, di.
Assume that the mean of the node degrees of Gi and Go is dmnan Then, by sparse matrix multiplica- tion, the complexity of the right-hand-side of is reduced to O (lgdmmaa)
As we will see later in Section 4.3 in SeedGNN st will also contain outputs from the perco- lation layer. order to learn how to best synthesize these two features (see further discussions in Section 4.3) apply neural network on hy after (I)
my (11)))
where the update function Φr implemented as a K-layer neural network (we use in our experiment). Let of (hx) = hy. The k-th layer of oi can be formulated as
o (hr) (0) (h:) W k- +bbk-1) blit-1).
(4)
where Wik-1] and b are learnable weights, initialized as Gaussian random variables; a is an activation function (we use ReLU). The updated representations my [R=mmx((=1)) will be sent to the next layer of SeedGNN.
4.3 PERCOLATION MODULE
The percolation module designed to match high-confidence nodes one layer and propagate the matched nodes new seeds to the subsequent layers. Formally, we first obtain similarity matrix in the 1-th layer by mapping the node-pair representations my I-dimension vectors, which is used to assess the similarity of each node-pair:
It = (m(m))
(5)
We implement Pt as multi-layer neural networks that is defined similarly as di in (4). The output æt is in R21*2 Then, we transform zj to Xi = unvec(ay) R"1 and apply row-wise softmax to normalize X₁:
Y (softmax(X) (X,) + softmax(x7))7) /2,
(6)
where for each row (ui,.., ..., vn) R of input matrix, the softmax function is defined
exp(v,) for i = 1,,
softmax(v); Ej= exp(e,))
The similarity matrix Yi needs "cleaning" because contains lot of "noisy" information. For ample, many fake pairs possess comparable similarity with true pairs (see Figure3((a) for example). Further, there are far more fake pairs than true pairs. As result, directly utilizing such misleading
5

---

Under review as a conference paper at ICLR 2023
information would lead to even more matching errors. Since the percolation idea from theoretical algorithms passes only new seeds with high confidence to the next stage (Yrrtseva et al.] 2013), leverage approach called "masking" to remove the noisy information and retain the cleaner information in Y, More precisely, we utilize the Hungarian matching algorithm (Edmonds & Karp 1972] to solve linear assignment problem on Yi to find injective mapping between 91 and G2, such that the total similarity of the matched node-pairs is maximized (see Figure
example). The matching result is denoted by Ri E {0, 11th X where ji = if the node-pair (i.j) is matched by the Hungarian algorithm and Ri j) = 0 otherwise. Then, we filter out the noisy information in Y by "masking":
21 = vec(Y) o Rı),
where o denotes element wise multiplication (see Figure 3(c) for example). The matching informa- tion 2) is sent to the next layer. As a result, many potentially noisy node-pairs are discarded. We note that both the idea of using similarity matrix to refine higher-laye matching and the idea of masking
have appeared in seedless matching (Wang et al. 2019 Fey al. 2020 Yu et al. 2019). However, there are crucial differences in the way that these ideas are utilized. Further, unlike previous perco-
lation algorithms (Yartseva et al.) 2013), our design of the percolation module correct matching errors from earlier layers. We discuss these differences further in Appendix A
Y
0.99
0.06
0.1
0:05
0:22
-2
0.1
0.00
222
6:0
0/36
6166
0.16
(a) Similarity matrix.
(h) Hungarian algorithm.
(c) Masking.
Figure 3: An illustration of our percolation process.
The combination of the two features With the convolution module and the percolation module, our SeedGNN can identify witnesses different hops and generate new seeds for percolation. How- ever, these capabilities alone are insufficient. For example, when graphs are very sparse, even true node-pairs may not have enough witnesses if the number of hops is small. When graphs are very dense, a fake pair may also have many witnesses if is large. Thus, SeedGNN needs to learn how to adaptively utilize various types of witnesses in different types of graphs. Similarly, even with the above "cleaning" procedure, the output of the percolation module may still have low-confident seeds. Directly using them for percolation could lead to cascading errors. Thus, SeedGNN also needs to learn how to use new seeds with different levels of confidence.
The neural module in (3) is precisely designed to enable such learning. Specifically, instead of directly using the output zι from the percolation module as new seeds, we concatenate it with the output of the convolution module, i.c., $1+1 = [m,, 2]] E Rn Xdi+1, as the input to the next layer. Then, after passing 81-1 through I we apply the neural module (3). The joint effect of this design is that SeedGNN can utilize the confidence of z decide how much it should rely on various types of witnesses. Intuitively, higher layer > 2, after passing s; by (T) and (3). my may contain I-hop witness information from the initial seeds $1, (1- 1)-hop witness information from new seeds 21, ... and I-hop witnesses information from new seeds 21-1 (see Figure However, unlike the initial seeds 81 that are either O or 1, the new seeds 21, 22, .... 21-1 also come with confidence levels. Thus, thanks to the non- linearity in di at each layer, the strength of the various types of witness information (from either the initial seeds or the new seeds) will vary depending on the confidence levels of the new seeds, which then potentially allows SeedGNN to learn how to best utilize them adaptively. For example, for sparse graphs, the confidence levels of the new seeds in the first several layers are low. As result, SeedGNN can utilize witnesses based on the initial seeds but at a larger number of hops. In contrast, for dense graphs, if the confidence levels of the new seeds in the first several layers
Layer
Layer 2
Layer
my hop
Gnitial spads
hop
2 hop
now seeds by
I-hop
1)-hog
new soeds 15
-hop
Convelution
Jmg Py
New seeds
Percolation
Styl
(112) 2n]
Figure 4: The witness information and new seeds computed by each layer.

---

Under review as a conference paper at ICLR 2023
already high, SeedGNN can then utilize the new witnesses computed from those seeds. This capability is experimentally validated in Appendix C.3 by studying the layer-wise matching process of SeedGNN for different types of graphs. Further, SeedGNN can even combine different types of witness information together and potentially extract unknown but more valuable features.
4.4 Loss FUNCTION
Finally, we utilize the ground-truth node-to-node correspondence as the supervised training infor- mation for end-to-end training. More precisely, for any training example (P,,T) T, we adopt the cross-entropy loss to measure the difference between our prediction and the ground-truth mapping и. Then, we add up the cross-entropy loss of every layer:
Cp(0)= - E
Σ
log (Yi(i.J) + +c) +
E
log (1 (1 (i(,)) + +c)
(F.5): j=m(()
(6.), (t)
where Yi is given in (6). denotes all the learnable weights in the networks Φi and pt. and is 10-9 to avoid a logarithm of zero. The total loss function is [(0) = -PPT (0). We find that the use of the losses from all layers in training helps to speed up the training process. This is somewhat inspired by hierarchical learning methods in (Bengio, 2009 (Schmidhuber 1992, Simonyan & Zisserman 2015). It allows the lower layers to be trained first, making it easier to train the next layers. Then, testing, we will apply the trained SeedGNN model on the test graphs and only use the matching result of the final layer, R2, as the predicted mapping since the final layer already synthesizes all the features learned the lower layers.
small positive value (e.g.
The total time complexity of SeedGNN is (()nn)), and the space complexity is O(n122). The detailed discussion on the complexity and scalability of our SeedGNN is deferred Appendix
5
EXPERIMENTS
In this section, we conduct numerical experiments to demonstrate the advantages of SeedGNN.
5.1 EXPERIMENTAL SET-UP
The number of ScedGNN layers is empirically fixed to 6 throughout our experiments. We implement the operators Φi and O as two-layer neural networks with d; = 16. For all experiments, optimization is done via ADAM (Kingma et al. 2015) with a fixed learning rate of 10-2 Our code is implemented using Py Torch (Paszke et al.) 2019) and trained on an Intel Core i7-8750H CPU. The performance is evaluated using the matching accuracy rate, i.e., the fraction of nodes that are correctly matched.
Datasets. We use the correlated Erdös-Rényi graph model (Pedarsani et al., (01T), SHREC' 16 dataset in (Lähner et al. 2016) and Facebook networks provided in (Traud et al.] 2012) in our experiments. 1) The correlated Erdös-Rényí graph model. We first generate the parent graph Go from the Erdōs-Rénn Rényi model G(n, i.e., start with empty graph pair of two nodes independently with probability p. Then, we obtain a subgraph G1 by sampling each edge of Go into G1 independently with probability s. Repeat the same sub-sampling process independently and relabel the nodes according to a uniformly random permutation permutation и to construct another subgraph G2. Then, each true pair is independently added into the seed set S with probability 0. 2) Facebook networks. The dataset in (Traud et al.) 2012) provides 100 Facebook networks from different institutions. We randomly choose 10 for training and 90 for testing. The sizes of the Facebook networks range from 962 to 32361. To lower the training cost, we down- sample the sizes of the training graphs. Specifically, for each Facebook network for training, we first down-sample nodes with probability 0.25 to get the parent graph Go- However, for testing, we do not perform this down-sampling and use the original graphs directly as the parent graph Go. For both training and testing, we generate Gi and G2 from Go by independently sub-sampling each edge of Gu twice with probability = 0.8 and sub-sampling each node of Go twice with probability 0.9. random permutation
nodes and connect any
The nodes of G2 are then relabeled according independently added into the seed set S with probability 8. 3) The 1 dataset. Matching 3D deformable shapes is central problem in computer vision, and has been extensively studied
Then, each true pair is
7

---

Under review as a conference paper at ICLR 2023
for decades (see Van Kaick et al. 2011 and (Sahillioglu 2020) for surveys). The SHREC' 16
dataset in (Lähner et al. 2016) provides 25 deformable 3D shapes (15 for training and 10 for testing) undergoing different topologiall changes. Each shape is represented by triangulated mesh graph consisting of around 8K-1 IK nodes (with 3D coordinates).
Training set. We construct the training set T in the following way. First, generate 100 random pairs of correlated Erdós-Rénn Rényi graphs with n = 100. p E {0.1, 0.3, 8 E {0.6, 0.8, 1), and 0 -.11 Second, we add 10 pairs of Facebook networks as discussed above with 0 = 0.1 into the training set. Third, we do not include any SHREC" 16 dataset in the training set, because our SeedGNN trained on the above two datasets already performs well for the SHREC'16 dataset (see Section 5.2). which verifies the generalization power of our SeedGNN.
Baselines. We compare the performance of our proposed SeedGNN with several state-of-the-arr algorithms: 1) D-hop (Mossel et al., 2019) finds the node mapping between the two graphs that maximizes the total number of D-hop witnesses for given D. For a fair comparison with other algorithms, we iteratively apply the D-hop algorithm T times (with DT 6 because SeedGNN is fixed to have 6 layers). In each iteration, we use the matching result of the previous iteration as new seeds and apply the D-hop algorithm again. 2) PGM (Kazemi et al. 2015) iteratively matches
node-pairs with at least r witnesses. We choose r = 2, which is the same as the simulation setting in (Kazemi et al. 2015). 3) PLD (Yu et al.) 20211) is the state-of-the art seeded graph matching algorithm designed for graphs with power-lave law degree distributions (which is a common feature of real-world social networks (Barabási 2016). 4) SGM (Fishkind et al., 2019) uses Frank-Wolfe method to approximately solves a quadratic assignment problem that maximizes the number of matched edges between two graphs, while being consistent with the given seeds. 5) MGCN (Chen) et al. (2200) is a representative semi-supervised learning-based GNN approach, whose performance comparable with other semi-supern supervised learning approaches. The parameters are set in the same way as those in (Chen et al.] 2020). 6) NGM (Wang et al. (021] is a supervised GNN method for seedless graph matching, but it also uses a pair-wise GNN that utilizes an affinity matrix as input. We transfer this approach to seeded graph matching by modifying the affinity matrix to also encode
seed information. We then train the weights of NGM with the same training set as our SeedGNN.
5.2 RESULTS
Performance Comparison on Correlated Erdös-Rényí Model. In Figure 5 we show the per- formance of the algorithms on the correlated Erdös-Rényi graph model. For test graphs, we vary 0 while fixing n = 500, p E {0.01, 0.2). s = 0.8. The different graph sizes between the training set (n 100) and the test set (n 500) aim to demonstrate the generalization power of our SeedGNN. We can observe that, among the -frth--rt methods, the iterative 2-hop algorithm has the best performance for sparse graphs (p- 0.01). and the SGM algorithm performs the best for dense graphs (u = 0.2). However, our SeedGNN has overall the best performance among all algorithms. From theoretical graph matching results (Mossel et al. 2019), we have learned that we need to use witnesses at different numbers of hops for matching sparse graphs (p 0.01) and dense graphs (p = 0.2). Thus, these results suggest that our SeedGNN chooses the appropriate features to match different types of graphs. Further, from the fact that our SeedGNN outperforms existing algorithms even in the settings that they work well, it indicates that our SeedGNN is able to utilize the features more effectively than the state-of-the-art methods. When comparing the performance of SeedGNN with NGM (which also uses a pair-wise GNN architecture), we can observe from Figure that, al- though NGM performs close to our SeedGNN in larger sparse graphs (p 0.01), it performs quite poorly in larger dense graphs (p = 0.2). We discuss the possible reason in Appendix A.
1.0
1.0
Accuracy Rake
0.8
Accuracy Rate
0.8
SeeeGMN L-5
SGM
0.6
0.6
1/hop Tw6
2-hop Tw3
0.4
0.4
3-hop Tw2
0.2
0.2
PGM
MGCN
0.0
0.0
NGN
0.0
0.04
0.08
0.12
0.16
0.05
Fraction S
Fraction Seeds
(a)
0.01
(b) p = 0.2
Figure 5: Performance comparison on correlated Erdös-Rényi graphs. Fix n 500 and = 0.8.
8

---

Under review as a conference paper at ICLR 2023
Performance Comparison on Facebook Networks. We compare the SeedGNN with the state-of- the algorithms on the 90 Facebook networks for testing, when we vary from 0 to 0.05. We show the performance of these algorithms in Figure 6 We can observe that our SeedGNN is comparable with SGM and significantly outperforms other algorithms. Note that the matching accuracy is satu- rated at around 80%, because there are about 15% nodes that do not have any common neighbour in G1 and G2 and thus can not be correctly matched.
Performance Comparison on S1REC'16 Dataset. To validate that our SeedGNN can adapt to different graphs, we evaluate ScedGNN for deformable shape matching using the SHREC' 16 dataset. Note that the sizes and types of graphs in this dataset are quite different from the Erdōs- Rényi and Facebook graphs in the training set. We can see in Figure that our SeedGNN still outperforms all baselines. This improvement demonstrates that SeedGNN trained with the other two datasets can generalize to real-world graphs with different sizes and types. We note that MGCN (a GNN based on semi-supervised training) utilizes both topological structures and non-topological node features. However, in this application the non-topologica node features correspond to 3D coordinates, which do not provide much useful information for correlating two 3D shapes with different poses. As a result, MGCN algorithm using 3D coordinates as node features almost fails completely. To confirm that the non-topological node features in the SHREC' 16 dataset are not very helpful, we also run supervised learning methods for seedless graph matching that only rely on the 3D coordinates. As we shown in Table they all suffer poor performance. Due to this reason, MGCN does not perform well either. To further validate that our SeedGNN use seed information more effectively than other supervised learning methods, we use the random encoding mentioned in Section 4. to represent seed information. and provide them as input for supervised GNNs (except NGM, for which we directly modify the affinity matrix using seed information). We fix the fraction of seeds 0 at 0.01 and the encoding vector dimension at 16. In Table [ we can observe that both our ScedGNN and NGM outperform the supervised methods using node-based GNNs, even when the latter are augmented with seed information. This suggests that our method is more effective in using seed information than the mode-based supervised GNN methods. Moreover, we discuss why NGM has similar performance with our SeedGNN on the SHREC'16 dataset in Appendix [ In Table I we also show the average run time of supervised learning algorithms to match a pair of graphs. We can observe that our SeedGNN is comparable with these algorithms on large graphs. Additional numerical studies to compare SeedGNN with more state-of-the-art GNN approaches on another real graph datasets with different sizes and types are deferred Appendix D
Accuracy Rate
0.8
SoodChN
Accuracy Rate
0.8
SeecChiN
0.6
Loup
0.6
SGM
2nop Two
1-t0p
0.4
3.nop Tw2
0.4
2-100
PGM
0.2
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.00
0.02
0.04
0.06
0.08
0.10
Fraction of Seeds
Fraction of Seeds
Figure 6:
Performance comparison on the
Figure 7: Performance comparison on the
Facebook networks with different 0.
SHREC' 16 dataset with different 0.
Table I: Comparison of GNN methods on SHREC' 16 dataset. The best results are marked bold.
Semi-Supervised
Supervised
Method
Despl ink, Ziwe
Cras
MGCN
DGMC
BB-GM
DGM
NGM
SeedGNN
201
Chastal 2019
Chene
2001
Solrak a. 200
Que
2021
Warg
2021
ours
Accuracy
secded
3.3
0.8
4.2
3.8
23.2 6.8
21.1
4.4
19.31
10.6
37.9
5.7
43.1 + 8.5
(%)
seedless
0.1
0.0
0.1
0.1
1 0.0
run time (8)
80.2
130.1
211.3
$79.2
141.5
Additional experiments. We conduct additional experiments to further investigate the inner work- ing of our SeedGNN (please refer to Appendix for details). First, to verify the effectiveness of our design choices for SeedGNN, we compare the performance of different architectural designs. Then, we investigate which sets of samples need to be included in our training set to obtain an effective study the matching process of SeedGNN for different types of graphs. The results suggest that SeedGNN chooses the appropriate features for different graphs based on the confidence level of new seeds.
trained model. Finally,

---

Under review as a conference paper at ICLR 2023
REFERENCES
David Avis. A survey of heuristics for the weighted matching problem. Networks, 13(4):475 1983.
Albert-László Barabási. Network Science. Cambridge University Press, Cambridge, 2016.
Yoshua Bengio. Learning deep architectures for Al. Now Publishers Inc, 2009.
Hongxu Chen, Hongzhi Yin, Xiangguo Sun, Tong Chen, Bogdan Gabrys, and Katarzyna Musial. Multi-level graph convolutional networks for cross-platforn anchor link prediction. Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Min- ing. pp. 1503-1511, 2020.
Carla-Fabiana Chiasserini, Michele Garetto, and Emilio Leonardi. Social network de de-anonymization under scale-free user relations. JEEE/ACM Transactions on Networking, (466)3375--3766 2016.
Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. In 2013 IEEE International Conference Computer Vision, pp. 25-32, 2013, doi: 10. 1011100C..222133.11111
Xiaokai Chu, Xinxin Fan, Di Yao, Zhihua Zhu, Jianhui Huang, and Jingping Bi. Cross-network embedding for multi-network alignment. In The world wide web conference, pp- 273 273-284, 2019.
Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18 (03):265 298, 2004.
David F Crouse. On implementing 2d rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52(4): 2016.
Tyler Derr, Hamid Karimi, Xiaorui Liu, Jiejun Xu, and Jiliang Tang. Deep adversarial network align- ment. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 352-361,200 2021.
Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248-264, 1972.
Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2020.
Donniell E Fishkind, Sancar Adali, Heather G Patsolic, Lingyao Meng, Digvijay Singh, Vince Lyzinski, and Carey E Priebe. Seeded graph matching. Pattern recognition, 87:203-215. 2019.
Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Deep graph matching under quadratic constraint. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5069-5078, 2021.
Aria D Haghighi, Andrew Y Ng, and Christopher D Manning. Robust textual inference via graph matching. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pp. 387-394, Association for Computational Linguis- tics, 2005.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Bo Jiang, Pengfei Sun, and Bin Luo. Glmnet: Graph learning-matching convolutional networks for feature matching. Pattern Recogn. 12I(C), jan 2022. ISSN 0031-3203. doi: 1..1016/j.patcop 2021.108167.
Ehsan Kazemi, S Hamed Hassani, and Matthias Grossglauser. Growing a graph matching from a handful of seeds. Proceedings of the VLDB Endowment, 1010:1000- 2015.
10

---

Under review as a conference paper at ICLR 2023
Ehsan Kazemi, Hamed Hassani, Matthias Grossglauser, and Hassan Pezeshgi Modarres. Proper: global protein interaction network alignment through percolation matching. BMC bioinformatics, 17(1):527, 2016.
Diederik Kingma, Jimmy Ba, et al. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Nitish Korula, Silvio Lattanzi, al. An efficient reconciliation algorithm for social networks. Pro- ceedings of the VLDB Endowment, 7(5):777-388, 2014.
Nils M. Kriege, Lina Humbeck, and Oliver Koch. Chemical similarity and substructure searches. In Encyclopedia of Bioinformatics and Computational Biology, pp. 640 649. Academic Press, Oxford, 2019.
Z Lähner, Emanuele Rodolà, MM Bronstein, Daniel Cremers, Oliver Burghard, Luca Cosmo, An- dreas Dieckmann, Reinhard Klein, and Sahillioglu. SHREC'16: Matching of deformable shapes with topological noise. Proc. 3DOR, 2(10.2312), 2016.
Chaozhuo Li, Senzhang Wang, Hao Wang, Yanbo Liang, Philip S Yu, Zhoujun Li, and Wei Wang. Partially shared adversarial learning for semi-supervised multi-platform user identity linkage. In Proceedings of the 28th ACM International Conference on Information and Knowledge Manage- ment, pp. 249-258, 2019a.
Chaozhuo Li, Senzhang Wang. Yukun Wang, Philip Yu, Yanbo Liang, Yun Liu, and Zhoujun Li. Adversarial learning for weakly-superrised social network alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 996-1003, 2019b.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3835-3845, PMLR, 2019c.
Vince Lyzinski, Donniell Fishkind, and Carey E. Priebe. Seeded graph matching for correlated Erdös- Rényi graphs. Journal of Machine Learning Research, 15(1):5513-3540 2014.
Tong Man, Huawei Shen, Shenghua Liu, Xiaolong Jin, and Xueqi Cheng. Predict anchor links across social networks via embedding approach. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 1823-1829, 2016.
Elchanan Mossel, Jiaming Xu, et al. Seeded graph matching via large neighborhood statistics. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1005- 1014. SIAM, 2019.
Arvind Narayanan, Vitaly Shmatikov, et al. Robust de-anonymization of large sparse datasets. In Security and Privacy, 2008. SP 2008. IEEE Symposium on, pp. 111-125. IEEE, 2008
Arvind Narayanan, Vitaly Shmatikov, et al. De-anonymizing social networks. In Security and Privacy, 2009 30th IEEE Symposium on, pp. 173-187. IEEE, 2009.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-BB Buc, E. Fox, and R. Gameet (cds.), Advances in Neural Information Processing Systems 32, pp. 8024 8024-8035. Curran Associates, Inc., 2019.
Pedram Pedarsani, Matthias Grossglauser, et al. On the privacy of anonymized networks. In Pro- ceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1235-1243. ACM, 2011.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox diffcrentiation of combinatorial solvers. 16th European Conference Computer Vision, pp. 407-424. Springer, 2020.
11

---

Under review as a conference paper at ICLR 2023
Yusuf Sahillioglu. Recent advances in shape correspondence. The Visual Computer, 36(8):1705- 1721, 2020.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta- learning with mnemory-augmenter neural networks. In International conference machine learn- ing, pp. 1842-1850. PMLR, 2016.
Christian Schellewald, Christoph Schnörr, et al. Probabilistic subgraph matching based on convex relaxation. In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 171-186. Springer, 2005.
Jürgen Schmidhuber. Learning complex, extended sequences using the principle of history com- pression. Neural Computation, 4(2):234 1992.
Farhad Shirani, Siddharth Garg, and Elza Erkip Seeded graph matching: Efficient algorithms and theoretical guarantees. In 2017 51st Asilomar Conference on Signals, Systems, and Computers, pp. IEEE, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.11 2015.
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, (05(35):12763-122) 12633-12666666 2008
Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 391(16):415-4188, Aug 2012. ISSN 0378-4371.
Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. A survey shape cor- respondence. In Computer Graphics Forum, volume 30, pp. 1681-1707. Wiley Online Library, 2011.
Mario Vento, Pasquale Foggia, al. Graph matching techniques for computer vision. In Image Processing: Concepts, Methodologies, Tools, and Applications, pp. 38 181-421. IGI Global, 2013.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3056-3065, 2019.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions Pattern Analysis and Machine Intelligence, 2020a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and multiple-graph match- ing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Tao Wang. He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling, Learning combinatorial solver for graph matching. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 7568-7577, 2020b.
Zhihao Wen, Yuan Fang, and Zemin Liu. Meta-inductive node classification across graphs In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1219-1228. 2021.
Lyudmila Yartseva, Matthias Grossglauser, al. On the performance of percolation graph matching. In Proceedings of the first ACM conference on Online social networks, pp. 119-130. ACM, 2013.
Liren Yu, Jiaming Xu, and Xiaojun Lin. Graph matching with partially-correct seeds. Journal of Machine Learming Research, 22(280): 2021a.
Liren Yu, Jiaming Xu, and Xiaojun Lin. The power of d-hops in matching power-law graphs. In Abstract Proceedings of the 2021 ACM SICMETRCCS/neerattond Conference on Measurement and Modeling of Computer Systems, pp. 77-78, 2021b.
12

---

Under review as a conference paper at ICLR 2023
Tianshu Yu, Runzhong Wang. Junchi Yan, and Baoxin Li. Learning deep graph matching with Obanmel-independent embedding and hungarian attention. In International conference on learning representations. 2019.
Tianshu Yu, Runzhong Wang. Junchi Yan, and Baoxin Li. Deep latent graph matching. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 12187-12197, PMLR, 18-24 Jul 2021c
Reza Zafarani, Lei Tang, and Huan Liu. User identification across social media. ACM Transactions on Knowledge Discovery from Data (TKDD), 10(2):1-30, 2015.
Andrei Zanfir, Cristian Sminchisescu, et al. Deep learning of graph matching. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2684-2693, 2018.
Jiawei Zhang, Yu Philip, al. Multiple anonymized social networks alignment. 2015 IEEE International Conference on Data Mining, pp. 599-608, IEEE, 2015a.
Wen Zhang, Kai Shu, Huan Liu, and Yalin Wang. Graph neural networks for user identity linkage. arXiv preprint arXiv: 000.: 2019.
Yutao Zhang, Jie Tang, Zhilin Yang. Jian Pei, and Philip S Yu. Cosnet: Connecting heterogeneous social networks with local and global consistency. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1485-1494, 2015b.
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-IEEE conference on computer communications, pp. (313-1321) IEEE, 2018.
Fan Zhou, Zijing Wen, Goce Trajcevski, Kunpeng Zhang, Ting Zhong, and Fang Liu. Disentangled network alignment with matching explainability. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pp. 1360-1368 IEEE, 2019.
13

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL RELATED WORK
Theoretical Algorithms Existing theoretical algorithms suffer from several limitations. First, graphs with different characteristies (e.g., Erdōs-Rényi graphs versus power-law graphs) may require different features and carefully tuned parameters. In contrast, by learning from the training graphs, our SeedGNN can automatically choose the effective features. Second, these theoretical algorithms may not synthesize different features most effectively. For instance, the (-hop algorithm in (Mossel et al. 2019) only utilizes the witnesses at specific hop I, but does not study how to combine witnesses at different hops.
Inductive Semi-supervised Learning on Graphs Our goal of using supervised learning for seeded graph matching shares some similarity with the work in Wenn et al. (202T). which also aims to both perform inductive learning (i.e., learn transferrable knowledge from training graphs) and utilize a small amount of labeled data on the test graph. However, Wen et al. (2021) focuses on node classification problem, which is quite different from seeded graph matching. In particular, WWen ct al. (202I) uses node-based GNNs, which (as we discussed in Section 4.1) have more difficulty in ellectively utilizing seed information than our proposed pair-wise GNN. Further, in order to transfer knowledge from the trained GNN to test graphs. Wenn et al. (2021) scales all GNN weights by common factor. It is unclear how this scaling will effectively transfer knowledge for seeded graph matching, e.g., how to best use different hops of witnesses. In contrast, our design of SeedGNN exploits the inherent structure of the seeded graph matching problem, and can be shown to general- ize well to unseen graphs of sizes and types very different from the training set. For future work, would be of interest to explore whether our SeedGNN can be further improved with a meta-lcarning component (Santoro al. 2016
Convex Relaxation Algorithms In addition to the theoretical algorithms and the GNN ap- proaches, there is another class of algorithms based on convex relaxations of the quadratic assign- ment problem, which maximizes the total number of matched edges between two graphs subject to the seed constraint (Lyzinski et al. 2014; Fishkind et al., 2019). In (Fishkind et al. 2019). the authors describe gradient ascent approach solve this relaxed problem, which called SGM. Compared to SeedGNN, SGM also has flavors of using witnesses and percolation ideas. Specifi- cally, the gradient of the SGM algorithm is similar to a matrix counting 1-hop witnesses. However, using only 1-hop witnesses is known to be ineffective in sparse graphs (as there are very few 1-hop witnesses even for true pairs). Indeed, our experiments in Section [5) find that our SeedGNN often outperforms SGM, especially in sparse graphs
Differences in Using Similarity Matrix and Masking We note that both the idea of using sim- ilarity matrix to refine higher-layer matching and the idea of masking have appeared in seedless matching. For example, some previously proposed nose- GNN architectures for seedless graph matching also compute the similarity matrix and use to refine the node embedding in each layer (Wang et al. 2019 Fey et al., 2020). However, these approaches heavily rely on high-quality non- topological node features and does not clean up the "noisy" information as we carefully did. Yuu et al. 2019) also uses the Hungarian algorithm for seedless graph matching, but they only clean up the matching result in their loss function. The results of intermediate layers are still very noisy. We use the Hungarian algorithm in each layer to filter out the misleading information, and thus the final result would be better.
Differences between Our Percolation Module and Previous Percolation Aalgorithms Unlike previous percolation algorithms (Yartseva et al., 2013), we allow SeedGNN to correct errors from ealier layers by re-matching nodes at each layer. Note that in many percolation algorithms, once a new pair of seeds is identified, it will be used as the correct matching until the end. This approach can be problematic if an incorrect pair is identified as seeds, whose impact will be lasting for many iterations down the road. In contrast, since our SeedGNN rematches nodes at each layer, even if some of the newly-identifee these errors in the next layer, long the fraction of incorrect seeds is small. In other words, our design of SeedGNN takes advantage of the power of partially-correct (i.c., noisy) seeds (as theoretically verified in Yu et al. 2021a))
seeds in the previous layer are incorrect, we can potentially correct
14

---

Under review as a conference paper at ICLR 2023
A.1 COMPARISON WITH NGM
The NGM architecture of Wang et al. 2021) shares some similarity with our SeedGNN. and also uses pair-wise GNN and uses the affinity matrix as input. However, note that Wang et al. (202T) focuses on seedless graph matching. Therefore, the NGM architecture in Wang et al. (2021) I was not designed for seeded graph matching. For example, they do not aim to exploit important features such as witness. Further, the NGM algorithm has not been evaluated for seeded graph matching either. In Section 2 we transferred the NGM approach to seeded graph matching by modifying the affinity matrix to encode seed information, and compare its performance with our SeedGNN. Through these experiments, we find that the NGM algorithm in [aang al. (202T) does not generalize well when the test graph is with much larger size and node-degree than the training graph. Below, we discuss the possible reasons.
Recall that we train both NGM and our SeedGNN on the same training set in Section 5.] and test on correlated Rrdös-Rényi graphs with n 500, 0.8, p = {0.01, 0.2). Note that this test graph size is larger than the training Erdös-Rénn graph size of n = 100. From the experimental results in Figure M in Section 5.2 we can observe that, although NGM performs close to our SeedGNN in larger sparse graphs (p = 0.01). it performs quite poorly in larger dense graphs (p = 0.2). One possible reason for this deterioration in the generalization power of NGM could be that, in the aggregation step, NGM normalizes each representation by the vertex degree of the association graph (which is roughly the square of the node degrees), but we do not. To see why this difference matters, note that according to known theoretical results seeded graph matching, there exist algorithms that only need (log r)) seeds to match all n nodes (Mossel et al. 2019). However, if the graph sparsity p is fixed, the node degree increases proportionally to n, and correspondingly the vertex degree of the association graph increases quadratically with n. As a result, when NGM divides the similarity of each node pair by the vertex degree, we expect that the resulting value (~ log 2 will n²
decrease close to zero as the graph size increases. Hence, it would be difficult for the sinkhorn step in NGM to distinguish the true pairs from the fake pairs in test graphs with larger size and node degrees than the training graphs. In contrast, since SeedGNN does not divide the similarity scores by the vertex degrees, the Hungarian algorithm step in our percolation (which can distinguish any absolute difference) will then be able to distinguish the true pairs from the fake pairs.
In contrast to Figure 5(b) for the experiment on the SHREC' 16 dataset (Table D. NGM has similar performance as our SeedGNN. This because in this experiment, we train NGM also with the SHREC 16 dataset (same as other seedless GNNs in Table D. Note that the node degrees of the graphs in the SHREC' 16 dataset are all around 6. In other words, the test graphs and training graphs are with similar node degrees. As result, the issue caused by dividing the similarity scores by the vertex degree of the associate graphs is not as critical for the SHREC' 16 dataset.
B COMPLEXITY AND SCALABILITY
B.1 TIME AND SPACE COMPLEXITY
First, we analyze the computational complexity of our SeedGNN. In each layer, counting witnesses in (2) takes (117iddmmm))) time. The neural networks 33) and 5 take O(1172) time. The Hungarian
algorithm takes ((n)nz) times (Crouse 2016). Thus, the total time complexity is O(nin))
The space complexity of our SeedGNN is O(112)) since we need to store the representations of all n2 node-pairs in each layer.
B.2 MAKING SEEDGNN MORE SCALABLE
For very large graphs, the step of the Hungarian algorithm may potentially become the compu- tational bottleneck. We can use greedy max-weight matching (GMWM) in (Avis) 1983) instead, as the time complexity of GMWM is only O(ninz logng). nzy). With this improvement, the total time- C time complexity for GNN-based algorithms is ( (Fey et al. 2020). Thus, the computational complexity of our SeedGNN is only moderately larger than the best known one. Our numerical
complexity is reduced to O log n2 R.ddeau To the best of our knowledge, the best-known
15

---

Under review as a conference paper at ICLR 2023
result shown in Table I has demonstrated that the run time of our SeedGNN is comparable to the best-known GNN-based algorithms.
C STUDYING THE INNER- WORKING OF SEEDGNN
In this section, we further investigate how the performance of SeedGNN varies as we change its inner working. First, to verify the effectiveness of our design choices for our SeedGNN method, we compare the performance of different architectural designs. Then, we investigate which sets of samples need to be included in our training set to obtain effective trained model. Finally, we study the matching process of SeedGNN for different types of graphs. The results suggest that SeedGNN could potentially choose the appropriate features for different graphs based on the confidence level of new seeds.
C.I STUDY OF THE DESIGN CHOICES
To verify the effectiveness of our design choices, consider four variants of SeedGNN, which are:
1. SeedGNN-x: SeedGNN without convolution module. This variant aims to verify the im- portance of extracting witness-like information a larger number of hops.
2. SeedGNN-w: ScedGNN without percolation module. This variant aims to verify the im- portance of the percolation module in SeedGNN.
3. SeedGNN-p: ScedGNN with percolation module but without the Hungarian matching al- gorithm (i.c., 21 = unvec(Yi) in each GNN layer). This variant aims to verify the impor- tance of the "cleaning" process in SeedGNN.
4. SeedGNN-h: ScedGNN with 2 unvec(Ri) instead of 7 in each layer. This vari- ant aims to verify that among the new seeds, it is still important to distinguish the high- confident one and low-confident one.
Finally, we use "SeedGNN" to denote the full design in Fig. We train all these variants with the same training T in Section 5.1
In Figure g we show the performance of the above variants of SeedGNN on correlated Erdós-Rényi graph model. For test graphs, we increase 0 from 0.05 while fixing n 500, p 0.04, 0.8. As illustrated Figure g our SeedGNN with full design achieves the best performance among all variants, which shows the effectiveness of our design choices for the SeedGNN architecture. Further, among the variants, SeedGNN-w almost fails completely, which highlights the significant importance of using the percolation idea SeedGNN for seeded graph matching. SeedGNNx does performs poorly, which demonstrates that it is also important to extract witness information at larger number hops instead of only I-hop. We can observe that SeedGNN and SeedGNN-h both outperform SeedGNN-p and the improvement of SeedGNN is significantly bigger. This result verifies that is not enough to only use the soft-correspondence (as in SeedGNN-p) and we need to combine both the matching result R₁ of the Hungarian algorithm and the similarity Yi as in (7) to achieve the best performance.
C.2 STUDY OF THE NECESSARY TRAINING SAMPLES FOR GENERALIZATION
Intuitively, in order to help our SeedGNN successfully learn useful knowledge that can be applied never-seen graphs, the training set needs to contain graph pairs with different varieties, e.g., graph sparsity, graph correlation, and the size of seed set. However, a larger training set also increases the training time. To show which sets of graph pairs are necessary, we compare SeedGNN trained with different training sets, whose parameters are shown in Table 2 We use T denote the training set that only includes the Erdós-Rénn Rényii graphs of the training set in Section 5.1 First, to show the necessity training graph pairs with a wide range of sparsity, we train SeedGNN with T, Tp and T22, and compare the performance of the trained models while increasing p from 0.02 to 0.2 and fixing n = 500, s = 0.8 and = 0.05. Figure (a)) shows that, if SeedGNN is only trained with p 0.1, it performs well on sparse graphs but poorly dense graphs. In contrast, if SeedGNN is only trained with p = 0.5, it performs well on dense graphs but poorly on sparse graphs. Thus, we should include both p- 0.1 and p 0.5 in the training set achieve good performance. Second, to
16

---

Under review as a conference paper at ICLR 2023
1.0
0.8
Accuracy Rate
0.6
SeedGNN
0.4
SeedGNN-h
SeedGNN-p
0.2
SeedGNN-X
SeedGNN-w
0.0
0.00
0.01
0.02
0.03
0.04
0.05
Fraction of Seeds
Figure 8: Performance comparison of SeedGNN and four other variants correlated Erdós-
Rényi graph model with different 0. Fix 500, 0.04, 0.8.
show the necessity of training graph pairs with different correlations, we compare the performance of SeedGNN trained with T, T.1, T.2 and Tax. and compare these models while increasing from 0.5 to and fixing n = 500, p = 0.08 and = 0.05. Figure showss that, SeedGNN is only trained moderately correlated graphs but poorly highly correlated
with 0.6, it performs well graphs. contrast, if SeedGNN is only trained with = 0.8 or = 1, it performs well on highly correlated graphs but poorly on moderately correlated graphs. Thus, we should include different correlations in the training set to achieve good performance. Third, we compare the performance of SeedGNN trained with T, Ta and Te2, and compare these models while increasing from 0.05 and fixing n 500, 0.04 and 0.8. Figure [eguuee((c]ssa shows that, if SeedGNN is only trained with 0.1 and E 10.1, 0.3), performs exactly the same. If SeedGNN is only trained with 0.3, it performs worse than the former two. Thus, we only need to include graph pairs with relatively small seed set the training set.
Table 2: Different Training Sets
Training Sets
p
S
7p1
{
[0.6, 0.8, 1
10.05, 0.1
Tp2
(0.5)
0.66, 0.8, 1)
0.05, 0.1
Ta1
0.51
(1)
(0.05, 0.1
Ts2
0..1,
{0.8]
(0.05, 0.1]
Ta3
0.51,
(0.6)
(0.05, 0.1
Te
(0.1,0.5)
[0.6, 0.8, 1
{0.3}
Tr2
0.1,
0.66, 0.8, 1
(0.1, 0.3
1.0
1.0
0.8
Accuracy Rate
SeedGNN SeedGNN p1
0.6
0.6
0.4
SeedGNN
0.4
SeedGNN
0.4
SeedGNN 51
SeedGNN SeedGNN
0.2
SeedCNIt
SeedGNIN s3
0.0 coa 324
0.0
0.03
Sparsity
Graph
(a) 8 = 0.8, 0.05.
(b) p = 0.08, 0.05.
(c) = 0.04, 8 = 0.8.
Figure 9: Performance comparison of SeedGNN trained with different training sets. Fix 500.
17

---

Under review as a conference paper at ICLR 2023
C.3 LAYER-WISE STUDY OF SEEDGNN
Recall from Section 4.3 that our design on the feature combination potentially enables SeedGNN to utilize various types witness information adaptively, based on the confidence levels of new seeds 21. In this section, verify this capability through numerical results. To directly visualize in the matching process, we present the similarity matrix Y/ of each layer of SeedGNN and compare it with the witness matrix of the iterative 1-hop and 2-hop algorithms at each iteration. We assume that the true mapping ı the identity permutation, i.e., (t)
First, we study the matching process in dense graphs. We fix a pair of correlated Erdös-Rény" graphs with n = 50, p 0.4, 8 = 0.8 and 0.1. Then, we index the nodes from 0 to 49 in the descending order of the node degree in the parent graph Go- In Figure TO show the similarity matrix Yı in each layer of our SeedGNN, and compare it with the witness matrix in each iteration using either the I-hop 2-hop algorithm. We can immediately see that the similarity matrices provided by SeedGNN are more similar to the witness matrices of the iterative 1-hop algorithm than that of the iterative 2-hop algorithm. Specifically, since the graphs are dense, the I-hop witness information from the initial seeds can already generate new seeds with high confidence (see Figure [O(a) and 10(g) where there are many dark points on the diagonal (i.e., consistent with the underlying true mapping), while there are few dark points off the diagonal). The iterative I t-hop algorithm is known to use new 1-hop witnesses from these new seeds (see Figure I0(h) in the next iteration. In contrast, the 2-hop witnesses from the initial seeds are much noisier (see Figure [0(m) where the darkness of the points on the diagonal cannot be differentiated from those off the diagonal). As we illustrated in Figure these types of witness information are both contained in the second layer of SeedGNN. By comparing Figure [0r) with Figure [O(h)and and Figure [0(m) we can observe that the second layer of SeedGNN produces a similarity matrix that closer to the witness matrix of the I-hop algorithm
than that of the 2-hop algorithm. Thus, we infer that, for these dense graphs in which the new seeds reliable, the SeedGNN relies more on witnesses computed from these new seeds.
(a) Layer 1.
(b) Layer 2.
(c) Layer
(d) Layer 4.
(c) Layer 5.
Layer 6.
(g) Iteration 1.
(h) Iteration 2.
(1) Iteration 3.
Iteration 4.
(k) Iteration
(l) Iteration
(m) Iteration 1.
(n) Iteration 2.
(o) Iteration 3.
Figure 10: The similarity/witness matrices of the matching process on a fixed pair of dense corre-
lated Erdös-Rényi graphs with n 50, p 0.4, 0.8 and 0 0.1. Darker points correspond
to bigher similarity (in Y) or a larger number witnesses. Figure T0(a)
Figure IO(T) are the
similarity matrix from each layer of SeedGNN. Figure 10(g) Figure 100
the witness matrix
from each iteration of the iterative 1 1-hop algorithm. Figure 10(m)
Figure 10[o] are the witness
matrix from each iteration of the iterative 2-hop algorithm.
Then, we study the matching process in sparse graphs. We fix a pair of correlated Erdós-Rényl graphs with 50, p 0.1, 0.8 and 0 0.1. Then, also index the nodes from 0 to 49 in
18

---

Under review as a conference paper at ICLR 2023
the descending order of the node degree in the parent graph Gu- In Figure 11 show the similarity matrix Yi in each layer of our SeedGNN, and compare it with the witness matrix each iteration using either the 1 1hhop or 2-hop algorithm. In contrast Figure T0 in this case, observe that the similarity matrices provided by SeedGNN are more similar to the witness matrices of the iterative 2-hop algorithm than those of the iterative 1-hop algorithm. Specifically, since the graphs are sparse, there are very few 1-hop witnesses even for true pairs. Thus, the 1-hop algorithm almost fails com- pletely (see Figure [g) Figure I1O). On the contrary, the 2-hop witnesses from the initial seeds are much more reliable (see Figure (1(m) As result, the iterative 2-hop algorithm produces much
better results (see (ig
Figure [[oo). By comparing Figure [I(b) with Figure [h and
Figure (m) we can observe that the second layer of SeedGNN produces a similarity matrix that is closer to witness matrix the 2-hop algorithm than that of the h-hop algorithm. Thus, we can infer that, for these sparse graphs in which the confidence levels of new seeds are low, SeedGNN
utilizes 2-hop witness information from the initial seeds, and avoids using 1-hop witnesses based on these new seeds.
(a) Layer 1.
(b) Layer 2.
(c) Layer
(d) Layer 4.
(e) Layer 5.
(f) Layer 6.
Iteration 1.
(h) Iteration 2.
(i) Iteration 3.
( Iteration 4.
(k) Iteration 5.
(1) Iteration
Tenmasnen
(m) Iteration
(n) Iteration
Iteration
Figure 11: The similarity/witness matrices of the matching process on fixed pair of sparse corre- lated Erdös-Reee Rényi graphs with n 50, = 0.1, s 0.8 and
0.1. Darker points correspond
to higher similarity (in Yi) or larger number of witnesses. Figure [Iaa)
Figure II( the
similarity matrix from each layer of SeedGNN, Figure [[(g) Figure are the witness matrix from each iteration of the iterative 1-hop algorithm. Figure (m
Higure
[1(0) are the witness
matrix from each iteration of the iterative 2-hop algorithm.
In summary, from these two studies, conclude that SeedGNN might be able choose the appropriate features for different types of graphs according to the confidence level of new seeds. Further, we observe that the matching accuracy of SeedGNN is even higher than that of the 1- hop and 2-hop algorithms, the latter two of which have been theoretically proven to work well for dense graphs and sparse graphs, respectively (Mossel al. 2019). Thus, this result suggests that SeedGNN may extract more valuable features, or learn more effective ways to synthesize witness information, than the theoretical algorithms.
D PERFORMANCE COMPARISON WITH GNN METHODS
In this section, we further compare the SeedGNN with several
art deep graph match-
ing networks, including supe-supe learning methods (PALE (Man et al.] 2016). DeepLink (Zhou et al.) 2018), dName (Zhou et al. 2019). CrossMNA (Chu et al. 2019), MGCN (Chen et al. 2020 and supervised learning methods (GMN (Zanfir et al. 2018 PCA-GM (Wang al. 2019
19

---

Under review as a conference paper at ICLR 2023
2021). IPCA-GM (Wang et al. 2020a CIE Yu al. 2019 GLMNet Jiang Wang et al. 2020b), DGMC (Fey et al 2020). BB-GM (Rolinek et al. 2020), 2021). DLGM (Yu al. 2021c)). We conduct experiments Willow Object dataset (Cho et al. 2013). which consists of 256 images in 5 categories. The training set contains all categories of images, with 20 images of each category. We test the trained models the rest images. Following the experimental setups in (Fey et al., 2020), we construct graphs via the De- keypoints, and the input features of keypoints are given by the concatenated output of relu4.2 2 and relu5_1 of pre-trained VGGI6 (Simonyan & Zisserman 2013). Note that the resulting graphs only have 10 nodes. For semi-supervised methods, we randomly choose true pairs as seeds. For supervised methods, they do not need seeds. For SeedGNN, we still directly use the model trained Section 5.T We generate the seeds in two ways. The first way is to apply the Hungarian algorithm on the similarities of non-topological node features. The second way is to use the matching result the GNN methods for seedless graph matching (we choose DGMC). Note that for both ways, SeedGNN does not utilize any training graph in the Willow Object dataset. For the semi-supervised algorithms, we use the publicly available implementations from their respective papers to generate the corresponding matching results. The performance values of the existing supervised algorithms are directly retrieved from their respective papers.
NGM (Wang al.
ct al. 2022), LCS
DGM (Gao et al.
launay triangulation
Since there are lack of sufficient training data for semi-supervised methods (there only seeds for each pair of graphs), it is difficult for them to learn to match the seeds effectively. As a result, observe Table 3 that SeedGNN significantly outperforms the semi-supervised methods. In contrast, the supervised methods learn from large number of graph pairs. Further, the two images similar
be matched are of the same category. Therefore, the input node feature generated and informative enough for correlating keypoints. Thus, the supervised methods have performed relatively well, and SeedGNN using seeds generated by the non-topological node features does not achieve performance gain. However, we can use SeedGNN to refine the output of seedless graph matching algorithms. We observe that SeedGNN consistently improves matching performance of DGMC and achieves the best performance.
Table 3: Comparison of matching accuracy (%) on Willow Object dataset. The best results marked as bold. The performance values of the existing supervised algorithms are directly retrieved from their respective papers.
Method
face
mbike
car
duck
wbottle
Mean
Semi- Supervised
PALE Man et al. (016)
85.4
52.9
55.1
56.4
68.1
60.1
DeepLink Zhou al.
2011
86.1 1
55.8
63.7
62.0
72.3
66.0
dName Zhou et al. 2019)
86.9
58.3
65.3
66.0
77.7
68.8
CrossMNA (Chu et 2019
85.6
60.1
61.4
65.8
74.2
68.0
MGCN (Chen et al. 2020)
87.2
63.0
67.5
67.2
78.1
72.6
GMN (Zanfir et al. 2018)
98.1
65.0
72.9
74.3
70.5
76.2
PCA-GM (Wang et |2.19
100.0
76.7
84.0
93.5
96.9
90.2
NGM (Wang et al. 2021)
99.2
82.1
84.1
77.4
93.5
87.2
Supervised
IPCA-GM (Wang et al. 2020a)
100.0
77.7
90.2
84.9
95.2
89.6
CIE (Yu et al. 2019)
100.0
90.0
82.2
81.2
97.6
90.2
GLMNet (Jiang
2022
89.7 100.0
93.6
85.4
93.4
92.4
LCS (Wang et al.
2020b
100.0
99.4
91.2
86.2
97.9
94.9
DGMC (Fey et
2020
100.0
92.1
90.3
89.0
97.1
93.7
BB-GM (Rolinek et
al.
(2020)
100.0
98.9
95.7
93.1
99.1
97.4
DGM Gao al. 2021)
100.0
98.8
98.0
92.8
99.0
97.7
DLGM Yu et al. 2021c
100.0
99.3
96.5
93.7
99.3
97.8
SeedGNN (ours)
100.0
98.9
98.0
93.1
98.7
97.7
DGMC+ SeedGNN
100.0
99.6
100.0
99.7
99.1
99.5
20


Reviews:
[{"review_id": "aWoHZbWglk", "reviewer": "Reviewer_g881", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies the seeded graph matching problem, in which the learning algorithm is given a set of ground-truth seed pairs and the task is to match the rest of the nodes. The contribution of the paper is an end-to-end learning based on GNN. The model consists of two modules, namely convolution and percolation modules. The proposed method achieve competitive performance on real and synthetic datasets.", "summary_of_the_review": "This paper proposes an end-to-end GNN model for seeded graph matching. The design of the model is interesting and achieve promising empirical results. However, the high time and space complexity of the model make it not suitable for matching large-scale graphs.", "strength_and_weaknesses": "Strength:\n1. The seeded graph matching problem is important, which has many applications.\n2. The end-to-end learning framework is novel and the design is sophisticated but clearly explained.\n3. The empirical results seems promising.\n4. Comprehensive auxiliary experiments  are also provided, which are informative.\n\nWeaknesses:\n1. The ideas behind each building block are not new, which have been used in previous graph matching algorithms.\n2. The main drawback of the framework is the high computational complexity. The complexity of the proposed model is essentially the same as a GNN model on a graph with $n_1n_2$ nodes and $m_1m_2$ edges. Thus the time and space complexity is $m_1m_2$ and $n_1n_2$  respectively for each layer. This is huge for moderate-size graphs.  I think the memory usage is the reason why the model is trained on CPU instead of on GPU.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "W9t-t9mflrH", "reviewer": "Reviewer_7PdA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "In this paper, the authors focus on the seeded graph matching problem, which is a variant of the graph matching problem with several pre-matched pairs as initial seeds. In existing works, the seeds are hardly considered especially in supervised graph matching works. They propose to apply the GNN jointly over both the two input graphs for matching and try to learn the pair-wise similarities. Specifically, their proposed SeedGNN contains two modules: the convolution part for learning the witnesses to distinguish the true pairs and the fake pairs; the percolation part for filtering the prediction of the model and generating the new seeds by matched node pairs. Experiments are conducted on multiple datasets to verify the performance of the proposed SeedGNN with the comparison of various baselines including both semi-supervised learning and supervised learning.", "summary_of_the_review": "This paper aims to solve the seeded graph matching problem which is hardly considered in the literature. However, except for this point, the other parts of this paper look not good enough to me. As I mentioned in the weakness part, the authors need to clarify the difference between several existing works to further demonstrate their contributions. Therefore, I consider this paper is not yet ready for publication in ICLR.\n", "strength_and_weaknesses": "**Strength:**\n1. This paper focuses on the seeded graph matching problem, which is hardly considered in the literature, especially for existing deep graph matching works. Indeed, initial seeds can make models better handle graphs with a large number of nodes. Therefore, I think it's necessary and interesting to consider the seeded graph matching problem.\n2. The authors propose a new architecture called SeedGNN consisting of two main components namely the convolution module and the percolation module, which can better handle the seeds and generate more new seeds.\n\n**Weakness:**\n1. The authors claim, \"In contrast to previous approaches that apply GNNs separately to each graph, a key departure of our SeedGNN architecture is to apply the GNN jointly over two graphs and to learn a pair-wise similarity for each pair of nodes directly.\" While in the field of deep graph matching, similar approaches already exist, such as the SOTA BBGM[1] and NGM[2]. These methods utilize the single affinity matrix constructed from the two input graphs as the input to their GNN. So, what is the main difference between the proposed SeedGNN and existing deep graph matching works? \n2. As for the comparison of SeedGNN and existing deep graph matching works, I agree that existing deep graph matching works hardly consider utilizing the initial seeds, but I think it is too absolutely to claim that the \"node-based GNN approach faces significant difficulty in learning how to use seed information\". For example, we can set the initial seeds as matched pairs and let the methods learn the other nodes, or we can modify node/edge affinities in the affinity matrix based on the matching seeds, or we can remove the initial seeds from the input graph to generate a smaller graph and let the methods work on the new graph. Anyway, I think there are many straightforward approaches to allow existing deep graph matching methods to use the same seed information as the SeedGNN, and it is arbitrary to make such a judgment in this paper. \n3. For the results in Table 1, I hope the authors may consider my suggestion above and make a more fair comparison. I think the current results in Table 1 look weird that the results of all supervised methods (including SOTA methods in graph matching) are zeros. Making the supervised methods use the same seed information will be better.\n4. The authors claim the proposed SeedGNN can automatically choose the effective features many times in the paper, but the proof looks not sufficient enough to me. The authors only prove it in the experiments: \"From theoretical graph matching results, we have learned that we need to use witnesses at different numbers of hops for matching sparse graphs (p = 0.01) and dense graphs (p = 0.2). Thus, these results suggest that our SeedGNN can adaptively choose the appropriate features to match different types of graphs.\" While I do not think it can demonstrate the claim. Moreover, I think this claim should be demonstrated in theory, since the good performance in the experiments may have multiple reasons instead of the reason for choosing the right features claimed by the authors.\n5. For the masking part of the proposed SeedGNN, the authors claim \"we leverage an approach called masking to remove the noisy information and retain the cleaner information.\"  However, I think this masking approach is very similar to one existing graph matching paper in ICLR 2020 (Eq 17 of [3]), which also uses Hungarian as a mask for the output. Could the authors please show the difference between their approach and the ICLR 2020 work?\n6. The proposed SeedGNN can generate new seeds by matched node pairs in the matching process, but I wonder if it will be troublesome when the newly generated seed is wrong by mistake. For example, if the generated seeds at the beginning of the matching process are wrong, would it damage the entire matching process? Maybe an error correction or regret mechanism should be considered.\n\n**References**\n\n[1] Rolínek, Michal, et al. \"Deep graph matching via blackbox differentiation of combinatorial solvers.\" European Conference on Computer Vision. Springer, Cham, 2020.\n\n[2] Wang, Runzhong, Junchi Yan, and Xiaokang Yang. \"Neural graph matching network: Learning Lawler's quadratic assignment problem with extension to hypergraph and multiple-graph matching.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).\n\n[3] Yu, Tianshu, et al. \"Learning deep graph matching with channel-independent embedding and hungarian attention.\" International conference on learning representations. 2019.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "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": "SzOV8NfgNvT", "reviewer": "Reviewer_fUFE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 a GNN for seeded graph matching. In the non-seeded version, the goal is to align/match the nodes between two graphs (eg. in social networks/ego networks, the same users appear across multiple networks.), while in the seeded version, there are a small number of pre-existing matching given. Most previous GNNs for seeded graph matching adopt a transductive semi-supervised setting, which  cannot learn transferable prior that is generalizable to unseen graphs. This paper proposes SeedGNN, which operates on a pair-level. There is first a convolution module to capture witnesses of seeds across different hops, and a percolation module to filter high-confidence pairs and use them as new seeds. SeedGNN is evaluated on both synthetic and real graphs.\n\n\n", "summary_of_the_review": "Overall, I think the weaknesses overweigh the strengths. The weaknesses should be clarified/corrected.", "strength_and_weaknesses": "Strong points:\n\nS1. The proposed method is able to learn an inductive model for seeded graph matching, instead of traditionally transudative approaches.\n\nS2. Experiments are conducted on both synthetic and real-world datasets\n\nWeaknesses:\n\nW1. Inductive semi-supervised learning has been proposed in other tasks before, e.g. node classification [1]. Despite the task differences, the model design might still be relevant and some ideas can be borrowed. At the minimum, a discussion on the model design should be included to highlight why previous inductive semi-supervised approaches cannot be adopted here.\n\n[1] Meta-Inductive Node Classification across Graphs  https://arxiv.org/abs/2105.06725\n\nW2. The idea of using easily matched pairs as new seeds in the percolation layer is quite straightforward and used in other seeded problems, where a few initial seeds can bootstrap the process and high-confidence instances can be added as new seeds later.\n\nW3. The \"witness\" is an important concept. While i get the general idea at the high level, it is not clearly defined: what exactly are witnesses? Is there a precise definition?\n\nW4. In table 1, the supervised seedless models have very low accuracy (0-0.1%). But is such comparison meaningful? After all, the supervised methods are not designed for such seeded setting with very small supervision. Some other models, eg, self-supervised/contrastive models, may better handle small labeled data.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "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