Spectral Subgraph Localization
Authors: Judith Hermanns
Amit Boyarski
Petros Petsinis
Alex M. Bronstein
Davide Mottin
Panagiotis Karras
Venue: Submitted to ICLR 2023 (2023)
Keywords: subgraph isomorphism
subgraph localization

Abstract: Several graph mining problems are based on some variant of the subgraph isomorphism problem: Given two graphs, G and Q, does G contain a subgraph isomorphic to Q? As this problem is NP-hard, many methods avoid addressing it explicitly. In this paper, we propose a method that solves the problem by localizing, i.e., finding the position of, Q in G, by means of an alignment among graph spectra. Finding a node correspondence from Q to G thereafter is relegated to a separate task, as an instance of the graph alignment problem. We demonstrate that our spectral approach outperforms a baseline based on the state-of-the-art method for graph alignment in terms of accuracy on real graphs and scales to hundreds of nodes as no other method does.

SPECTRAL SUBGRAPH LOCALIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Several graph mining problems are based on some variant of the subgraph iso- morphism problem: Given two graphs. and Q, does contain subgraph iso- morphic to Q? As this problem is compleee many methods avoid addressing it explicitly. In this paper, we propose method that solves the problem by local- izing, i.e., finding the position of, Q in G. by means of an alignment among graph spectra. Finding a node correspondence from Q to thereafter is relegated to a separate task, an instance of the graph alignment problem. We demonstrate that our spectral approach outperforms a bascline based on the state-of off-the-rrt method for graph alignment in terms of accuracy real graphs and scales hundreds of nodes as no other method does.
INTRODUCTION
Graph analysis tasks frequently require localizing smaller target graph Q within larger source graph G, i... finding a subgraph of G that is best aligned with Q. This type of problem may ap- pear as subgraph discovery (Kuramochi & Karypis 2001 Bianchini et 2018), where we need to find any target graph in G, in subgraph querying (Katsarou et al. 2015 Sun & Luo 2019), where we find out whether target subgraph match exists within a collection of source graphs, or graph matching (Zhang & Tong 2016), where we have to align corresponding nodes across two graphs, potentially of different sizes. Such subgraph localization is interest in practical applications such as localizing smaller electronic circuit within a large circuit (Fyrbiak et al.) 2019), detecting sub- molecules in bigger molecules (Najmanovich et al. 2008), and localizing parts of shapes com- putational geometry (Rampini al. (2019). For instance, the task of subcircuit detection (Fyrbiak et al., 2019) involves sampling multiple subgraphs and comparing the spectra of their adjacency matrices that of the query subgraph. Despite the prevalence of the problem, current research has avoided tackling it directly, due to its NP-hardness.
In this paper, tion to the problem of subgraph localization, built around the notion of identifying the spectrum Ao of graph Q within that of another graph G. Figure visualizes an instance of the subgraph localization problem by formulation; aim to find func- tion that indicates which nodes in G correspond to Q. Our solution effectively recovers both the nodes belonging to the part and the edges that con- nect the part to the rest of the graph. This problem is an instance of inverse eigenvalues problems (Chu & Golub) 2005), the class of problems which aim to reconstruct matrix from its spectrum.
propose novel spectral solu-
8
2
0
3
0
4
8 0
G
Figure 1: An instance of subgraph localiza- tion (left) and its solution (right).
Our experimental study demonstrates that our approach tackles the subgraph localization problem more effectively than state-of-the-art neural competitors and showcases its applicability to the real world problem of subgraph aligument.
In summary, our contributions are as follows:
We propose spectral formulation for the subgraph localization problem (Sec.
We show that our solution achieves the optimum value under mild conditions (Sec. 3
We experimentally validate the effectiveness of our solution real and synthetic graphs (Sec.

---

2 RELATED WORK
We review related work on five problems related to subgraph localization, namely subgraph isomor- phism, subgraph discovery, subgraph querying, subgraph matching, and subgraph localization.
The subgraph isomorphism problem is to decide whether a source graph contains a target subgraph and return that exact subgraph in the souree. In graph analyties, this problem is mainly solved for very small target subgraphs (< 10 nodes) and aims at exact matches. Several methods speed up this process by exploiting query specifics, such as patterns in multiple subgraph queries (Duong al., 2021]. By contrast, our method aims at bigger target subgraphs.
In subgraph discovery, target subgraph is not given input, yet the problem is to identify in- teresting components of a source graph according to some criteria, as, c.g., those that appear fre- quently (Kuramochi & Karypis 2001 2004). achieve a density threshold (Lee et al. 2010 Qin al. 2015). or form cliques (Bianchini et al. 2018).
In subgraph querying, the goal is to identify all souree graphs among a collection that contain a query target subgraph, without necessarily indicating the position of that subgraph within the returned graphs (Katsarou et al., 2015| Sun Luo 2019 Sun et al. 2020). A closely related topic is subgraph retrieval, where the goal is to retrieve the most relevant graphs from graph database, with relevance being measured by some score. In Roy et al. (2022) node embeddings are learned in order to produce a subgraph matching for the computation of the relevance score. In Li et al. (2019), nodes are matched in order to produce a graph similarity score without producing node embeddings as intermediate step. In both cases, the queries are significantly smaller than ours.
The goal of subgraph matching is to match the nodes of a smaller graph to those a subgraph in bigger graph via minimizing some eπror criteria, possibly in the presence of available attribute information. Many methods for graph matching effectively solve a subgraph isomorphism problem, even though they are not specifically designed for this purpose (Zhang & Tong 2016). Recent work (Lou et al., 2020; Li et al., (2019) employs deep neural models to learn node embeddings that are subsequently used for matching.
The problem of subgraph localization calls to detect a good fit, by some measure (kktsss et al., 2023) of a target subgraph within a bigger source graph, without aiming for full isomorphism. This problem has been scarcely studied. A recent application in computer vision (Xu et al. (0200) uses subgraph localization to detect temporal actions, where a graph models actions and the temporal relations between them. However, this model uses edges for temporal aspects and inter-scene rela- tions, and hence does not generalize to arbitrary graphs. An existing spectral solution (Candogan & Chandrasekaran 2018) is limited to special families of graphs, such as cliques.
3 SUBGRAPH LOCALIZATION
All aforementioned problems have in common the search for one graph within another. We study the most generic form of this problem, which corresponds the problem named Subgraph localization in our previous discussion. That is, we aim to identify a subset of the nodes of a graph G corre- sponding an input graph Q; do not aim at an exact 1-to-1 correspondence among all graph elements, but to simply detect set of best matches.
Problem 1. The subgraph localization problem for a graph G = =V, EV,E), where is set of n nodes and E C V x V is a set of edges, and query graph Q = (Vq, Fo) with no [Voll no < n, calls to find set of nodes Vs C V, inducing a set of edges E.s C F., such that [Vsl [Vo] and there exists bijective function f : Vs + VQ between the nodes in Vs and those in VQ such that for each (i,j) E És there exists (f()), f()) E Eq and vice versa.
In many applications, solving subgraph localization, do not need to explicitly materialize the correspondence function f. Such one-to-one correspondence is not explicitly sought for. Thus, we eschew recovering an exact and instead aim at finding indicator function ö V - 1) such that 5(v) = 1, if u E Vq. and 5(v) = otherwise.
At first glance, finding such indicator function seems easier than recovering bijective func- tion f. However, even in this identity-functtin formulation, the problem corresponds to the decision version of the subgraph isomorphism problem, which asks whether graph G contains a subgraph
2

---

isomorphic to another graph Q. Thus, the problem is still NP-complete. Even so, further relax our requirements, allowing the function be a binary version of a continuous real-value func- tion v V - IR on values below a threshold T:
8(0) = f 0o
if v <T
(I)
otherwise
This relaxed problem calls to find real function, or, equivalently, a real vector E R", with [V], for known permutation of nodes in the graph. To overcome the requirement for a known node permutation, consider permutation cermutation-ivvariann spectral alignment approach reminiscent of the Hamiltonian operator used in shape analysis (Choukroun et al. 2018: Rampini et al. 2019). Before delving into the approach, introduce the necessary notation.
Background. The adjacency matrix of graph G with n nodes a x n matrix A E {0, ]]nx where Aij if (i, E E, otherwise. The degree matrix D is an diagonal matrix where each entry dis ンjt Aij holds the degree of node i. The graph Laplacian matrix is defined as:
L A.
The Laplacian matrix of undirected graphs is positive semi-definite symmetric matrix, hence its eigenvalues .1..... : An: are real and non-negative. The specirum X(M) of matrix M is the ordered sequence À S I An of its eigenvalues. Correspondingly, graph's spectrum is the spectrum of its Laplacian matrix.
SPECTRAL SUBGRAPH LOCALIZATION
We examine how the presence of subgraph within a graph affects the graph's spectrum. Spec- tral theory establishes that the spectrum of subgraph interlaces with the spectrum of the graph. However, the problem is also non-trivially affected by nodes beside the subgraph. Still, if we could compensate for the effect of nodes other than the subgraph's nodes, the two spectra would be indis- tinguishable. Following this reasoning, we devise novel objective for subgraph localization. To that end, first propose original connection between subgraph localization and inverse eigen- value problems with structural constraints (Chu & Golub 2005).
Inverse Eigenvalue Problem. The general additive inverse eigenvalue problem (AIEP) is defined as follows:
Problem 2 (ATEP, Problem 3.6 in Chu & Golub of matrices N. and set of scalars (t
2005) )) Given an matrix A, special class
X E N such that {>(A + X); = M
vast literature on this problem (see Chu & Golub 2005) and references therein) explores questions regarding the existence of solutions and numerical approximation algorithms for various special classes of matrices N. A common variant of Problem | expresses the problem as a least squares problem between the spectra:
min |A(A+ - - XEN
In what follows, we establish a connection between the subgraph localization problem (Problem I and the additive inverse eigenvalue problem (Problem ( Under the above formulation, aim to find a v that, added to the diagonal of the Laplacian of G, renders its first no eigenvalues equal to those the query graph. In addition to finding v, we aim to remove from G the edges that connect the identified part to the remaining nodes. To the best of our knowledge, this is the first time such connection has been established, and the first time an AIEP with structural Laplacian constraints is considered.
To devise our solution for subgraph localization, commence with intuitive scenario. We assume that G has a number of clearly separated communities, one of which corresponds to the query graph Q. A community is defined by cut, nodes within the same community more well connected than nodes across communities. Without loss of generality, assume the graph com- prises distinet communities. In this case, G's Laplacian is block matrix with two diagonal
3

---

blocks L ER and (on and few entries in the blocks R
and L21 nn)xnn representing edges across the two communities. The spectra A(L) of G and X(L)) of differ on the nodes in L22 and the edges in L12 and L21.
We aim to transform into Hamiltonian Choukroun et al. 2018), defined hereby, to cancel out this difference. A Hamiltonian is operator H. L + diag( v) where v V R is scalar real- valued function and L the Laplacian. The Hamiltonian reduces to the Laplacian the potential O. According (Rampini et al., 2019 Lemma 1), if we add to the diagonal of vector having non-zero values, v(v) > limited to nodes in L22, i.e., outside V2. then eigenvectors corresponding to eigenvalues X; < r of the resulting spectrum A(L + diag(v) will have non-zero values limited to the positions corresponding to nodes in Vo. in effect rendering A(L + diag(v)) similar X (L)). Still, the non-zero entries between communities L L21 affect the spectrum. To cancel that effect, we introduce Laplacian editing matrix that removes the contribution of such edges to the Laplacian of the graph G:
E diag(L122) L21
L12 (Lagg(L11)
where Lig1 (resp. L21 corrects the degree of the nodes after removing the edges in L12 (resp. L21). In effect, the corrected Laplacian L E is equivalent to the Laplacian of a graph with two connected components, one of which isomorphic the query graph Q. Thus, the solution v renders the VVol smallest eigenvalues of the corrected Laplacian indistinguishable from the spectrum of Q, Ag i.e., A(L E + diag(v) (v)) = Xq. where, with a slight abuse of notation, A(L diag(v) refers to the |Vol smallest eigenvalues of L E + diag(v).
Since both v and are unknown, we optimize the objective:
min v.E
| + diag(v)) Aqli l
(4)
s.t.
E1 O, oL E) S O, ||v| cc
This objective is not convex, yet it only depends on the spectrum, for which there exists efficient approximations (Cohen-Steinet
al. 2018); it leads to solution even if the initial value of v is a noisy version the ground truth. As constraints, we postulate that E should be: (i) symmetric, E = E T, (ii) row- (and, by symmetry, also column-) centered, E1 O, with every row summing to 0; and (iii) yielding only non-positive off-diagonal entries off (L (L-E) < 0. In addition, we enforce that v be point on the surface of a sphere of radius c, via the constraint ||v/l = c. Proposition 4.1 provides a sufficient condition on for the optimality of Equation 44), considering the noiseless case where exactly contains the subgraph Q.
Proposition 4.1. When c > vn- - max (xQ), the global optimum of Equation is obtained at
iu E VQ otherwise
(5)
with
V min(v)
max(v) - -min(v) Sij = 10, B
E = (Saa -
(6)
E is the Laplacian of a graph composed of two disjoint components, one of which is exactly the component indicated by Equation 5 i.e., the query subgraph Q. Then there is permutation II such that IILII is block diagonal matrix with the Laplacian each component on the diagonal. Without loss generality, we assume that the Hamiltonian operator attains this block diagonal form:
Proof. Let be constructed from Equations 5
LQ
L E + diag(v) (v)
Vu-na
When satisfies the stated condition, the spectrum of the bottom-right block contains only eigenval- ues larger than max(Ac) follows that the first ng eigenvalues of L E + diag(v) are exactly those of Lg, rendering the objective of Equation 3 Mequal to
4

---

In effect, by Proposition 4.1
recover the optimal solution v is appropriately normalized and è is no less than a certain value. We exploit this result in Section 4.2 to design our algorithm by numerical optimization. We first introduce regularization term.
Regularization. The objective in Equation 1 does not prevent from taking arbitrary values. How- ever, since L E has two connected components. v plays role similar to that of Fiedler's vector in the minimization of the normalized cut (Shi Malik 2000). This observation leads us to the spectral regularization v (L Ejv that exhorts v to take values in the null-space of L E. In other words, the spectral regularizer drives to a stepwise function. We combine spectral regularization with our objective as follows:
min A V.E
E + ding(v)) - AQll3 +aV (L E)y
Data term
Spectral regularizer
s.t.
= 0, of (IL-E)= 0, | =
where μ 2 is regularization coefficient.
Corollary. Proposition applies also with the spectral regularization term in Equation
Proof. Let E be constructed from Equations 5 6). L E is the Laplacian of graph composed of two disjoint components, one of which is exactly indicated by Equation (5). i... the query sub- graph Q. Then in Equation (5) belongs to the null-space of L E, rendering the regularization term 0, hence Equation (5) also provides the global minimum of Equation (8)
4.1 LOCALIZING DISCONNECTED SUBGRAPHS
special case of subgraph localization is that of a graph with a number of connected components, one of which corresponds to the query graph Q. In this case the editing matrix E 0, leading to the simpler objective:
min ALL diag(v)) AQll2 uv Lv s.t. |
(9)
4.2 NUMERICAL OPTIMIZATION
We exploit Proposition 4.1 to craft numerical procedure that minimizes the objective in Equa-
tion collaterally optimizing for E and v. the first iteration q O, we initialize E, 0. In iteration @ + we minimize f(v, E.y A( - E, + diag(v)) ÀQll + pv T (L Eg) v for given E,:
V4+1 arg min f(v, Eg), v:|lv||=e via projected gradient descent, until convergence; an iteration h + 1 of projected gradient descent performs the step:
(10)
X++1 = X641 oV Vvv
Xk
(1I)
Vk+1
where regulates the learning rate. The gradient V. for Equation II requires differentiable eigendecooposition, which achievable by extant methods (Wang et al. 2019
We subsequently update E according to:
V min(vg)
(12)
max V min(v Vv,)'
S, 10: lAi.
(13)
E = (S1a S.
(14)
We obtain threshold of the indicator function 5(v) in Equation 1 for the nodes comprising the subgraph by splitting the elements of v into two clusters minimizing sum-of-squares error from the mean (i.e., optimizing the k-means objective in one dimension) and compute the matrix E from this
thresholded v by Equations 12
5

---

Eigenvalue X
2
2
2
0 0
0 0
4
8
10
2
4
8
10
2
8
10
(a) Iteration
(b) Iteration 6
(c) Iteration 18
Figure 2: Alignment of the spectrum 2o of Q and the part of the spectrum A(L - + diag(v) v))
of G corresponding Q at 1, 6, and 18 iterations. As two spectra progressively converge. especially in smaller eigenvalues, Q is correctly localized in G.
The SSL algorithm. We eventually present our Spectral Sub- graph Localization (SSL) algorithm (Algorithm I in the sup- plementary material) for Problem [ SSL takes as input the adjacency matrix A of the full graph G and the spectrum of query subgraph, and returns the vector v and the threshold r of the indicator function 8; it additionally requires some hyperpa- rameters, such as the number of outer iterations maxiterout. the number of inner iterations maxiter: ter the learning rate a, and the regularization coefficient μ.. We empirically found that the number of iterations and the learning rate do not sig- nificantly affect results across datasets if chosen within some range; we report those ranges and recommended values in Ta- ble [ in the supplementary material. On the other hand, the regularization coefficient j in Equation S requires tuning for each dataset. We thus first normalize the value of μu by c² to remove the dependency on v's magnitude and then perform grid search on range of values for p select an appropriate value.
Figure 3: Example SSL result: ground-truth subgraph in blue; remaining nodes of G in red.
The optimization process alternates the projected gradient optimization in Equation 11 and the update of E using Equations [4 until it converges or reaches the maximum number of itera- tions maxiterout. Figure 2 illustrates the solution's progressive convergence through iterations, while Figure 3 shows an example result.
4.3 COMPLEXITY ANALYSIS
We derive the worst-case time complexity of the algorithm in the number of nodes in the graph G. The eigendecomposition in Equation takes (n)²) per iteration; the computation Equation 14 takes (n²2) for the matrix-vector multiplicatio;; 1-D k-means in Line takes O(n) with the best algorithm (Grønlund et al. 2017). In effect, the total time is O(maxi ter (maxiter,, * n + n² + n)), where the (n))) term dominates. However, as -- diag(v) (v) a graph's Laplacian, its spectrum can be efficiently approximated through sampling (Cohen-Steine Steiner et al. 2018)
5 EXPERIMENTS
Here we empirically evaluate our method, SSI., on a number of datasets and against several hy- potheses. Our evaluation aims answer the following questions:
(Q1) Do the regularization term and the constraint ||v|| = in Equation
g help the localization?
(Q2) How does the conductance of the part corresponding to affect the quality of localization and how does SSL fare against state-of-the-art methods for graph alignment?
(Q3) What kind of graphs challenging for SSL and why?

---

5.1 EXPERIMENT DESIGN
The code and data are available at wthttps://anonoo http://wwwooo..oo.oooooo.eeer//a
Hyperparameters. Unless stated otherwise, choose maxiterout 3, maxiter 500, atol 10 and = 0.02. Regarding the regularization coefficient, we select = 0.2 through grid search. This choice achieves good accuracy across datasets and conductance levels.
Datasets. We evaluate SSL on the three real-world graphs from Rossi & Ahmed (0013) and two synthetic graphs generated by the Erdös-Renyi (ER) and Barabasi- Albert (BA) models. The data characteristics are described in the supplementary material. Additionally, we generate graphs with community structure using the stochastic block model (SBM) (Holland et al. 1983).
Choosing Q. Given number k, we generate query workload of size Vq k from real-world graph G to evaluate our subgraph localization method as follows.
1. Randomly select a node u, add it to Vo and place all its neighbors into a set N.
2. Randomly select node v' from N, add it to Vo, place in N all its neighbors not in Vo.
3. Repeat the previous step until [Vol = k.
4. Set Q as the subgraph induced by Vo in G.
For graphs generated by the stochastic block model, we set Q as the smallest community.
Quality measure. To evaluate performance in a manner independent subgraph size, we use Balanced Accuracy (BA) (Brodersen et al. 2010); given the query graph Vi and the subgraph Vs returned by a localization algorithm, balanced accuracy BA(v) = _ VonVal arithmetic mean of sensitivity (or recall) and specificity.
[Vol + [-Von-Va] is the
Vool
data term
data term sp. reg.
SSL obj.
term
data term sp. reg-
15
15
15
SSL objective
10
10
10
s
Bal. accuracy
0
0.8
0
20
40
0
20
40
0
20
40
0.6
0.4
0.2
0.3
0.4
[Val/V1l
(a) Balanced Accuracy
(b) values in ascending order and corresponding graph nodes.
Figure 4: Variants of the objective function; SSL's objective achieves the highest accuracy.
5.2 ABLATION STUDY
We commence our study by examining how the terms in SSL's objective function (Equation g) affect the result. Recall that the objective function consists of: (1) the data term, that drives the alignment between the spectrum of the part and that of the query, (2) spectral regularization term that exhorts v to be in the null space of norm the potential To study the contribution of each term the results, compare SSL against two variants thercof:
and (3) the sphere constraint that enforces a constant
1. A method only optimizing the data term |X(L - E + diag(v)) - Xa 1
2. A method optimizing a linear combination of the data term || E + diag(v)) A and the spectral regularization v (L E) v, without sphere constraint.

---

We experiment graphs with [V| = 200 nodes sampled form the stochastic block model, letting the size of the query subgraph increase from 20% of the graph to 45%. Figure 4a reports on the results of this ablation study in terms of average balanced accuracy over 5 sampled graphs for each subgraph size. Unsurprisingly. the optimization of the data term yields the worst results, although the method performs well small subgraphs. Still, the addition of the spectral regularizer and sphere constraint enhances the results up to 20% accuracy. For small subgraphs the sphere constraint brings only marginal gains compared to the spectral regularization. On the other hand, on large query subgraphs, the sphere constraint boosts the accuracy by an additional 8%.
To further corroborate these results, Figure Abishows an example of how the terms impact the po- tential v, on 40-node graph sampled from the SBM with two communities with 20 nodes each; the query graph is one of the two communities. Ideally, we would like to obtain a v clearly separating values between the part corresponding to the query graph and the rest. In that case, we say that forms a step function. The optimization of the data term (left chart) alone leads to no clear sepa- ration between the two parts. Introducing the spectral regularization (middle chart) yields result closer to a step function, though some nodes are incorrectly assigned to the part. Finally, the full objective in Equation 8 produces to clearly separated potential vector Visualizing the mapping of this potential to the graph G, we clearly recognize the part Gg as the light-colored nodes.
5.3 COMPETING METHOOS
Here assess our method against previous work. To the best of our knowledge, no extant unsu- pervised method is capable to answer localization queries in graphs with more than 15 nodes (Roy) al. 2022 Therefore, we compare SSL to the nearest feasible competitor, namely the state-of- the-art method for unsupervised graph alignment, CONE (Chen et al. 2020). To set up CONE so that it detects subgraphs, we inject in the query nodes with degree 0, so that the size of the query Q corresponds to that of the graph G, i..., IV/- = Vl. We extract the ensuing localization vector as the matches of query nodes in G with the default syper-paramettr settings.
Figure and Figure 2 present the average BA of 10 randomly generated connected subgraphs as Lievo.eevo Auj
i.e., the ratio between the function of conductance, T (VQ)) min (Eevg A Azj)
size of the cut among query Q and graph G and the minimum number of edges among the two resulting partitions. A graph's minimum conductance is associated (Cheeger (0155) to its algebraic connectivity, i.e., second smallest eigenvalue 22 (Fiedler) 1973). A larger conductance denotes more edges between the query subgraph and the rest of the graph. thus harder subgraph localization instance. We use query subgraphs corresponding to 10%, 20% and 30% of the full graph size.
The results in Figure that SSL effectively localizes the query in real graphs. Accuracy grad- ually increases as the conductance approaches & (V₂) = O, finally settling at 100% accuracy on all datasets, when the query is disconnected. In the Malaria dataset, we note more abrupt increase. The performance of SSL is always comparable to, and most often exceeds, that of CONE. While performance drops as conductance grows, in real applications we would aim at detecting interest- ing subgraphs that exhibit distinguishable structures, such as social communities. Such subgraphs deviate substantially from both random and complete subgraphs. We model these nontrivial con- nectivity patterns by a lower conductance. As conductance increases, the subgraph progressively becomes merged into other nodes, hence SSL cannot discriminate it.
The results in Figure o show that SSL. consistently outperforms CONE on synthetic graphs. As with real graphs, we observe gradual accuracy increase the graph becomes progressively dis- connected. Notably, on ER graphs, SSL succeeds even at high conductance values (> 0.6).
Impact of the graph's 's spectrum. To better understand the performance of SSL on different graphs. look it under the lens of the graph's is spectrum. 7 the spectra of the real (Figure
and synthetic graphs (Figure 6) in our experiments, normalized in the range 00 Au= First, we observe that the spectrum of synthetic graphs exhibits a gradual increase and a small difference between X and the maximum eigenvalue Xn. By the Generalized Cheeger's inequality (Lee et al.) 2010) the hthh -order conductance, miny, Vo....V max(((V.)) th eigenvalue. We conclude that, under gradual eigenvalue growth. the presence or absence of one edge does not affect the spectrum significantly, hence the projected gradient descent in SSL
= 1,2, is related to the
8

---

gracefully retrieves good solution. On the other hand, the spectra of real graphs in experiments exhibit an abrupt divergence between A2 and higher eigenvalues, indicating that a single edge may significantly affect the spectrum, rendering the task of projected gradient descent more challenging. In effect, SSL performs better as the gap between 22 and the rest the eigenvalues decreases.
Vol 0.1
[Vl TV
0.2
Vol 0.3
Bal. accuracy
1
1
Football
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
0.2
0.4
0.6
0.2
0.4
0
0.2
0.4
Highschool Bal. accuracy
1
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0
0.2
0.4
0.6
0.2
0.4
0.6
0
0.2
0.4
Malaria Bal. accuracy
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
SS1.
CONE
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.2
0.4
+ (V2)
(Vo)
<(V2)
Figure 5: Accuracy vs. conductance between query subgraph Q and graph G, real graphs.
IVl
M = 0.1
VVl M
0.2
IV
0.3
[V
Erdos- Renyi Bal. accuracy
Football Highschoul
0.8
Malaria
Erdos-Renyi
0.6
Barabasi
0.4
0.2
Norm. Eigenvalues
0.8
0.2
0.4
0.6
0.8
0.2 0.4 0.6
0
0.4
0.6
Barabasi Bal. accuracy
0.6
0.8
0.6
0.4
0.4
0.2
0.2
SSL
CONE
0
0.2
0.4
0.6
0.8 0
0.2 0.4 0.6
0
0.2 0.4
0.6
A2
Xn/2
An
(V22)
((V2)
((V2)
Spectrum
Figure 6: Accuracy conductance, ER and BA graphs.
Figure 7: Graph spectra.
CONCLUSION
We studied the challenging problem of subgraph localization, which calls find set of nodes in a larger graph that best corresponds to given subgraph. We devised novel spectral solution that identifies the query match by adding a penalty to the Laplacian matrix so as to obtain a spectrum similar to that of the query graph. This novel approach requires solving non-convex, non-smooth problem for which we devised a numerical method. Our results demonstrate that our spectral method localizes query subgraphs more effectively than baseline based the state-of-the-as method for graph alignment. To our knowledge, this is the first endeavor in effective subgraph localization that can handle graphs of any size in the order of magnitude of hundreds of nodes.

---

REFERENCES
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286 (5439):509-512, 1999.
Monica Bianchini. Giovanna Maria Dimitri, Marco Maggini, and Franco Scarselli. Deep neural networks for structured data. In Computational Intelligence for Pattern Recognition, pp. 29-51. Springer, 2018.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim Buhmann. The balanced accuracy and its posterior distribution. In International Conference Pattern Recogni- tion, pp. 3121-3124, 2010.
Utkan Onur Candogan and Venkat Chandrasekaran. Finding planted subgraphs with few eigenvalues using the schur-horn relaxation. SIAM Journal on Optimization, 28(1):735-759, 2018.
Jeff Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian, pp. 195-200. Princeton University Press, Princeton, 2015.
Xiyuan Chen, Mark Heimann, Fatemeh Vahedian, and Danai Koutra. Cone-align: Consistent net- work aligmment with proximity-presenve node embedding. Proceedings of the 29th ACM International Conference Information & Knowledge Management, pp. 1985-1988, 2020.
Yoni Choukroun, Alon Shtern, Alex Bronstein, and Ron Kimmel. Hamiltonian operator for spectral shape analysis. IEEE TVCG, 26(2): 12311331, 2018
Moody Chu and Gene Golub. Inverse eigenvalue problems: theory, algorithms, and applications. OUP Oxford, 2005.
David Cohen-Steiner, Weihao Kong, Christian Sohler, and Gregory Valiant. Approximating the Paul D) Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
spectrum of graph. In KDD, pp. 1263-1271, 2018.
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.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ, Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2): 298-305, 1973.
Julie Fournet and Alain Barrat. Contact patterns among high school students. PloS one, 2014.
Mare Fyrbiak, Sebastian Wallat, Sascha Reinhard, Nicolai Bissantz, and Christof Paar. Graph simi- larity and its applications to hardware security. IEEE Transactions on Computers, 694))505--51, 2019.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821-7826, 2002.
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schnei- der, and Mingzhou Song. Fast exact k-means, k- &-medians and Bregman divergence clustering in 1d. arXiv preprint 1rXiv:1701.07204 2017.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109-13,, 1983.
Foteini Katsarou, Nikos Ntarmos, and Peter Triantafiloou. Performance and scalability of indexed subgraph query processing methods. Proc. VLDB Endow., (11)))1566-157,,00
Jérôme Kunegis. Konect: the Koblenz network collection. In wWW. pp. 1343-1350. ACM, 2013.
10

---

Michihiro Kuramochi and George Karypis. Frequent subgraph discovery. In ICDM, pp- 313-320. IEEE, 2001.
Michihiro Kuramochi and George Karypis. Grew-a scalable frequent subgraph discovery algorithm. In ICDM, pp. 439-442. IEEE, 2004.
Daniel B Larremore, Aaron Clauset, and Caroline O Buckee. network approach analyzing 2013.
highly recombinant malaria parasite genes. PLoS computational biology.
Victor E Lee. Ning Ruan, Ruoming Jin, and Charu Aggarwal. A survey of algorithms for dense
subgraph discovery. In Managing and Mining Graph Data, pp. 303-336. Springer, 2010.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net-
works for learning the similarity of graph structured objects. In ICML, pp. 3835-3845. PMLR, 2019.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural sub- graph matching. arXiv preprint rrXiv:2007.03092 2020.
Rafael Najmanovich, Natalja Kurbatova, and Janet Thornton. Detection of 3d atomic similarities and their in the discrimination of small molecule protein-binding sites. Bioinformatics, 24 (16):1005-4) i115i 2008.
Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. Locally densest subgraph discovery. In KDD, pp. 965-974, 2015.
Arianna Rampini, Irene Tallini, Maks Ovsjanikov, Alex M Bronstein, and Emanuele Rodolà. Correspondence-fieee free region localization for partial shape similarity via hamiltonian spectrum alignment. In 3DV, pp. 37-46. IEEE, 2019.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL
i tory. com
Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. In AAAI, 2022.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):8888-9)) 2000.
Konstantinos Skitsas, Karol Orlowski, Judith Hermanns, Davide Mottin, and Panagiotis Karras. Comprehensive evaluation of algorithms for unrestricted graph alignment. In EDBT, pp. 260- 272, 2023.
Shixuan Sun and Qiong Luo. Scaling up subgraph query processing with efficient subgraph match- ing. In ICDE, pp. 220-231. IEEE, 2019.
Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, and Bingsheng He. Rapidmatch: a holistic approach to subgraph query processing. Proc. VLDB Endow:, 14(2):176-188, 2020.
Wei Wang, Zheng Dang. Yinlin Hu, Pascal Fua, and Mathieu Salzmann. Backpropaggaiion-frinndd) cigendecomposition. NeurIPS, 32, 2019.
Mengmeng Xu, Chen Zhao, David S Rojas. Ali Thabet, and Bemard Ghanem. G-tad: Sub-graph localization for temporal action detection. In IEEE/CVF CVPR, pp. 10156-10165, 2020.
Si Zhang and Hanghang Tong. Final: Fast attributed network alignment. KDD, pp. 1345-1354, 2016.
11

---

A SUPPLEMENTARY MATERIAL
We implemented SSL in Python 3.6 and ran experiments on an 8-core Intel Core 17-8565U machine with 16GB RAM. Code and data available https: battps://anonymouue 4open. /cien//e/////
SSL F39A
A.1 HYPERPARAMETER SETTING
We calibrated SSL using grid search the hyperparameters maxiterin. maxiterous atol, and a. The range the tested hyperparameters is depicted in [able[] We observe no significant difference in the hyperparameters in different datasets, vindicating the robustness of method. Surprisingly, we observe the same robustness for the regularization parameter μ..
Parameter
Value/range
Description
maxiter;n
500-1000
number of inner iterations
maxiterout
3-5
number of outer iterations
atol
10 5
loss tolerance
0.02
gradient step size
Table 1: SSL hyperparameters and default values.
A.2 DATASET DESCRIPTION
Table 2 and Table presents the characteristics of the datasets used in the experimental evaluations in the number of nodes V, edges E, network type, and parameters.
Dataset
Source
[V]
F.
Network type
Football
Girvan Newman 2002
115
613
Contact
Malaria
Larremore et al. (2013)
306
9042
Biological
HighSchool
Fournet & Barrat (2014)
327
5 818
Proximity
Table 2: Real graphs used in evaluation: number of nodes type.
|V], number of vertices |E], and graph
Dataset
Source
[
E
Parameters
Barabási-Albert
Barabási & Albert (1999)
200
5907
Mhew 50
Rényi
Erdös et al. 1960)
200
8185
Pnew 0.5
Table 3: Synthetic graphs used in evaluation: number of nodes [V), number of vertices |E],
number edges to attach from a new node to existing nodes Mnews edge creation probability Pnew-
A.3 CHALLENGING CASES
In this section, we investigate some examples of challenging cases for SSL, illustrated in Figures and In the results of Figure g we observe that the spectrum of the query graph and that of the detected subgraph are well aligned. However, the ground truth. Similarly, in the results of Figure 9 while SSL does not perfectly align the two spectra, yields a correlated spectrum. Nevertheless, SSL detects subgraph comprising nodes that are only connected by one edge. In both cases, the challenge arises from the sensitivity of the spectrum at weakly connected parts the graph. Changing the Laplacian in such parts by adding v has larger impact on the spectrum than changing the Laplacian in coll-connected neighborhood. These types of graphs force the optimization process into a local optimum, as the optimizer has large incentive separate these weakly connected parts of the graph.
localized subgraph deviates substantially from
12

---

2
Eigenvalue X;
1.5
0.5
0
10
20
30
i
(a) Alignment of spectra
(b) Ground truth
(c) Localization
Figure 8: Alignment of the spectrum Xo of Q and the corresponding part of the spectrum A(L E --aaiag(v) of G after convergence, ground truth Vs (blue) and V\Vs (white), and corresponding localization by SSL, while the spectra are perfectly aligned, the detected subgraph is not the ground truth. The depicted graph is Doig 2003).
interaction network from the D&D dataset Dobson &
10
Eigenvalue X
8
6
2
10000
0
10
20
30
(b) Ground truth
(c) Localization
i
(a) Alignment of spectra
Figure 9: Alignment of the spectrum Xo of Q and the corresponding part of the spectrum X(L E+ diag v)) of after convergence, ground truth Vs (blue) and V'Vs (white), and corresponding localization by SSL; while the spectra well aligned, the detected subgraph is not the ground truth; the detected subgraph coincides with nodes that have degree 0 or 1. The depicted graph is arenas Kunegis 2013).
A.4 SSL PSEUDOCODE
Algorithm| shows the psedocode SSL presented in Section 3 The algorithm easy to implement in few lines of code.
13

---

Algorithm SSL
Input: A adjacency matrix the full graph; Xo spectrum of the query subgraph.
Params: regularization coefficient; atol loss tolerance; gradient step size; maxiter maxi- mum number inner iterations; maxiterous maximum number of outer iterations
Output: Vector v, threshold
1: L
2: loss
3: c + 2/n- n4 (ax
4: vo -1
5: Eg +
6: while q S maxiter and loss 2 Qcol do
// Compute Vy41 by iterating
maxiter
7: Va+1 f- arg ( f(v. E
// Update Egt1 via
8:
Eg+1 f.from.v(v
// Update the threshold
9:
+ mm
10:
loss + f(v,, E,)
q a+ +-9+1
12: return T
14


Reviews:
[{"review_id": "qm38SWRn2xp", "reviewer": "Reviewer_rJzq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 addresses the problem of subgraph localization (SGL). The goal is to identify a good fit of a target subgraph within a larger source graph. This problem is related to the subgraph isomorphism problem and is NP-hard. The authors establish a connection between the SGL problem and the additive inverse eigen value problem. This connection leads to a spectral based algorithm called SSL for solving the SGL problem. This algorithm identifies the nodes and edges in the source graph corresponding to the target subgraph. Experimental results are encouraging.", "summary_of_the_review": "This paper addresses the problem of subgraph localization (SGL). The authors establish a connection between the SGL problem and the additive inverse eigen value problem. This connection leads to a spectral based algorithm called SSL for solving the SGL problem. This algorithm identifies the nodes and edges in the source graph corresponding to the target subgraph. Experimental results are encouraging. The authors could focus on improving the balanced accuracy especially when |V_Q| is large.", "strength_and_weaknesses": "A major strength of the paper is in the discovery of the connection between the SGL problem and the additive inverse eigen value problem. A major weakness lies in the accuracy obtained. For example, when |V_Q|/|V| is 0.5, the balanced accuracy drops to around 0.65.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pZ9tfSKPuBJ", "reviewer": "Reviewer_aKY2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper under review studies the problem of graph localization. This can be thought of as a problem belonging to the venerable family of problems falling under the subgraph isomorphism problem and its variants. The paper under review defines the subgraph localization problem as the following: You are given a query graph Q along with its spectra. You are also given a host graph G. The challenge is to find a subset of vertices in G which induces a copy of Q. As stated this is a NP-Hard problem. The results of the paper suggest that the spectral subgraph localization approach (the one developed in the paper) can find a copy of Q in G if G admits a community-like structure and Q is one of the communities in G.\n\nTheoretically, Spectral Subgraph Localization (SSL) solves an inverse eigenvalue problem (which is non-convex). This inverse problem is formulated as an optimization problem where you try to minimize the l_2^2 difference between the eigenvalues of Q and eigenvalues of an \"edited\" Laplacian. You minimize this difference over all the edits and the minimizer is deemed to reveal the set Q. \n\nThe authors have supporting experiments in the paper. These experiments suggest that the SSL approach recovers 80% fraction of the vertices when G comes from the Stochastic Block Model.", "summary_of_the_review": "Overall, the experimental results in this work are fairly intriguing. While there are not enough theoretical results to accompany the experimental findings, I think the paper can spur some theoretical investigation in the analysis of SSL (or its variants). For this reason alone, I recommend an accept verdict.\n\n========================================\n\n(EDIT: added later)\n\nAfter a detailed discussion with my fellow reviewers and a bit of pouring over the experiments section a little more carefully, I have to say that I must eat my words from before.\n\nIn particular, now I vote to reject the paper. As is evident, the paper does not have any ammunition on the theory side. What was gunning for the paper in my mind earlier was the experimental side. Let me make a few remarks about that now.\n\nIt is clear from Section 5.2 that this set of plots is used to back the SSL objective as the winning horse among some of its minor variants. To me, this is not much of a value add to the technical prowess of the paper. After my fellow reviewers pointed out to me, I agree the SSL algorithm only works for well-separable graphs. \n\nGiven these concerns, I now change my vote to reject the paper.\n", "strength_and_weaknesses": "The major strength of the paper comes from the experimental evaluation of SSL.No unsupervised method is able to handle query graphs Q on more than 15 vertices to the best of what authors know. Thus, I find it particularly impressive that SSL can handle graphs up to 200 nodes (thanks to their choice of a different spectral formulation). \n\nOn the other hand, the obvious weakness is the lack of theoretical results to go alongside. While I do not insist on theoretical results being present in this same submission, there is another weakness that the authors themselves bring up (but do not address). This weakness has to do with trying to understand what kind of query graphs Q are hard for SSL and why? The current version does not offer any insight on this problem and this is something I would have really liked to see.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BtaAUGh2_E", "reviewer": "Reviewer_oSHA", "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 paper studies the subgraph localization problem -- given a target graph and a source graph, compute the alignment of the target graph in the source graph. The problem of alignment is closely related to that of detecting isomorphic subgraph in a source graph. The goal here is to compute an indicator function that identifies a subset of nodes in the source graph that can be isomorphically mapped to the target subgraph. \n\n\nKey contributions:\n\n1.\tPropose a new spectral approach for the alignment problem.\n2.\tUnder “mild” assumptions, specifically on the separability of the source graph, prove that their approach yields optimum value under a certain loss function. \n3.\tExperimental validation of their approach.\n", "summary_of_the_review": "I think the paper has some promise but needs to be significantly rewritten to make it cleaner. The idea of decomposing X into E and diag(v), subject to some relevant constraints on E, is where I see the claimed novelty. But as discussed, I not completely convinced of the effectiveness of the approach (both from a theoretical side and practice). \n\n==== update after the rebuttal ======\n\nI would like to thank the authors for their feedback. Post reading other reviews + feedback + discussions with reviewers, I think while the problem is somewhat interesting, there are some keys issues that need to be addressed:\n\n1. The theory is simply non-existent. So there are no guarantees on the quality of the algorithm. While, the suggested simple approach may indeed be \"bad\"  as the authors, it is not clear why (perhaps that can be a point of exploration, simplification of the algorithm or proof that you cannot simplify)\n2. More importantly, the experimental results are not convincing enough. Indeed, the graph constructed seem to be tailored to ensure well separability and therefore the algorithm has a definite advantage over state of the art. From the results, in fact, it is easy to deduce that as the graphs become close to real, the algorithm looses any advantage over SOTA ..\n\nFor the above reasons, I am inclined to reject the current paper. ", "strength_and_weaknesses": "The key difference between the subgraph isomorphism problem and the alignment problem is that one doesn’t focus on computing the isomorphism function explicitly but instead only determine the indicator function.\n\nThe paper proposes to “relax” this problem further to a continuous version where the goal is to compute, instead of the indicator function, a real-valued function on the node set such that the indicator function can be retrieved by applying a thresholding on the real-valued function. \n\nQ: Given the real-valued function, there are a linear number of threshold function possible. So how exactly is this real-valued version a relaxation of the indicator version of the problem. \n\n\nThe central idea behind their approach is to connect subgraph localization to another well-studied problem known as inverse eigenvalue problem. Essentially, in this problem, we are given base matrix and a set of target eigenvalues, and the goal is to compute a matrix (from a family of matrices) that can be added to the base matrix such that the resulting matrix has eigenvalues equal to the target values. One of the several approaches to solve is problem is formulating it as a least squares problem. \n\nThe key idea of the work is to characterize the addendum matrix (to the base matrix) as the difference of another matrix E and a diagonal matrix whose diagonal values correspond to the real-valued indicator function. The matrix E is constrained as a symmetric matrix satisfying some additional properties. \n\nThe loss function is then minimized by using projected gradient descent. There is no convergence shown but assumed that a max-iters parameter can be specified in practice to limit the runtime. \n\nQ: Why can’t we first compute the matrix X that can be added to the based matrix A and then decompose X to compute matrices E and delta matrix? It appears that the first problem is solved by state-of-the-art approaches and the latter is a much simpler problem. Perhaps the benefit of this could be easier convergence proof?\n\n \nPros:\n\n1.\tThe characterization of the problem is indeed interesting, and the paper does present some good theoretical and experimental results.\n\nCons:\n1.\tPresentation is extremely confusing. For example, it is not clear right now, if there is any difference between computing the delta indicator function vs the real-valued function. It is indeed easier to compute the real-valued function, but the indicator function can easily be retrieved from it by thresholding – then why is relaxation not simple an aspect of the solution (instead of defining it as a new problem variant). \n2.\tThere are no guarantees whatsoever on the quality. The well-separability assumption is not mild as claimed and I think even the experimental results seem to show that clearly (as the conductance increases the loss of the approach in fact is worse than the baseline, in figure 5).\n3.\tThere is no guarantee on the convergence. The paper claims that in the experiment they see quick convergence, then I think it should be possible to show some convergence on the theoretical side. Otherwise, just characterizing the loss function and applying project gradient descent is just too weak from a theoretical point of view. \n4.\tFinally, I am not convinced of the applicability of the approach itself to that of subgraph detection. The measure of quality is that of balanced accuracy but I am not sure if it would mean anything in reality. For instance, if I obtain a subgraph with 0.9 accuracy, it could be a completely wrong subgraph. A better measure might be – how many times were you able completely identify the correct subgraph (upto isomorphism). Otherwise, I am sure how one can use this. \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": {}}]

Author rebuttal:

Decision: Reject