Learning to mine approximate network motifs
Authors: Carlos Oliver
Dexiong Chen
Vincent Mallet
Pericles Philippopoulos
Karsten Borgwardt
Venue: Submitted to ICLR 2023 (2023)
Keywords: motif mining
combinatorics
unsupervised learning

Abstract: Frequent and structurally related subgraphs, also known as network motifs, are valuable features of many datasets. However, strong combinatorial bottlenecks have made it difficult to extract motifs and use them in learning tasks without strong constraints on the motif properties. In this work we propose a representation learning method based on learnable graph coarsening, MotiFiesta which is the first to be able to extract large and approximate motifs in a fully differentiable manner. We build benchmark datasets and evaluation metrics which test the ability our proposed and future models to capture different aspects of motif discovery where ground truth motifs are not known. Finally, explore the notion of exploiting learned motifs as an inductive bias in real-world datasets by showing competitive performance on motif-based featuresets with established real-world benchmark datasets against concurrent architectures.

Under review as a conference paper at ICLR 2023
LEARNING TO MINE APPROXIMATE NETWORK MOTIFS
Anonymous authors Paper under double-blind review
ABSTRACT
Frequent and structurally related subgraphs, also known network motifs, are valuable features of many datasets. However, strong combinatorial bottlenecks have made it difficult to extract motifs and use them in learning tasks without strong constraints on the motif properties. In this work we propose a repre- sentation learning method based learnable graph coarsening, MotiFiest which is the first to be able to extract large and approximate motifss in a fully differentiable manner. We build benchmark datasets and evaluation metrics which test the ability our proposed and future models to capture different aspects motif discovery where ground truth motifs not known. Finally, explore the notion of exploiting learned motifs as an inductive bias in real-world datasets by showing competitive performance on motif-based featuresets with established real-world benchmark datasets against concurrent architectures.
INTRODUCTION
In many application domains, observing over-represented substructure in dataset is as evidence for its importance in network function. For example, early studies on network motif's enumerated all possible over-represented small subgraphs across various datasets and uncovered structures which explain the behaviour of real- real-world systems have been discovered such as the feed- forward loop in gene regulatory networks, and the bi-parallel motif ecological food chains (Milo) et al., 2002). More recently, motif libraries have shown strong utility in many machine learning contexts such as (Jin et al. 2020), classification (Zhang al., 2020 Meistza et al. 2012 Thiede et al. 2021 Besta et al. (202). representation learning Bevilacqua et al. (202) Cotta et al. 2022 Rossi et al. (2020) and explainability (Perotti et al. 2022). Although exhaustively mining motils is known to be NP-hard (Yu et al., 2020), motif utility has made the discovery task a key
challenge in data mining for the past 30 years. The aim of this work is to formally expose the task
of motif mining to machine learning models in effort to enhance both the discovery of motifs and the representation power of learned models.
Any motif mining algorithm has solve computationally intensive steps: subgraph search and graph matching. The process of discovering a new occurrence of the motif involves a search over the set of subgraphs of given dataset which yields search space that grows exponentially with the number of nodes in the dataset as well as in the motif. Next, for a candidate motif and subgraph, graph matching procedure is needed determine whether the candidate can be included in the set of instances of the motif. Despite these barriers, many motif mining tools have been proposed Nijssen & Kok (2004); Yan Han (202)); Wernicke (2066), all of which rely on simplifications of the task or priori assumptions about the desired motifs. These simplifications include bounding motif size Alon et al. 2008). , topology constraints Reinharz al. (218)) and simplified subgraph matching criteria such strict isomorphism, among others.
Besides those, an important limitation that often overlooked is the variability inherent to many motif sets particularly in biological networks. Network datasets often represent dynamic or noisy processes and algorithms which limit their matching procedure to exact isomorphism will overlook large set of possible motif candidates. Some tools have addressed this challenge, again with strong limitations such as REAFUM (Li & Wang 2015) which allows for errors in node labelling, and RAM (Zhang & Yang. 2008 which tolerates fixed number of edge deletions within given

---

Under review as a conference paper at ICLR 2023
motif. All of these constraints limit the set of observable motifs and can lead to us missing important features of datasets. For this reason, we emphasize that our proposed methodology is built to support the discovery of approximate motifs.
Recent success of graph representation learning, particularly in an unsupervised context, presents an opportunity for cireumventing some of these bottlenecks (Karalias & Loukas 2020). Namely, by allowing graph embedding models to leverage the statistical properties of a dataset, we can cast the search and matching problems to efficient operations such as real-valued vector distances. Of course, as is common with neural methods we sacrifice convergence and exactness guarantees in exchange for flexibility and speed. In this regard, there has been extensive work on problems related motif
mining using neural architecture such as subgraph counting Teixeira et al. (2022): [Chen et al.
2020 Liu et al. (020)) and graph matching [Li et al. 2019 Fey et al. (2020). To our knowledge neural motif mining problems for approximate subgraphs have yet to be proposed. Although related work has shown promise in similar motif mining tasks, by (Oliver et al. 2022 in domain-specinf
and partially differentiable applications, and applied to the related problems of frequent subgraph mining, (Ying et al. 2020), and discriminative subgraph mining (Zhang et al, 2020). Finally, the composability of differentiable models allows motif mining to act as pre-training module orienting classifiers towards a robust and rich feature sets. For these reasons, we believe there is a need formally introduce the motif mining problem the ML community by providing appropriate benchmarking settings and proposing relevant methodology.
1.1 CONTRIBUTIONS
In this work, we (1) formalize the notion of motif mining as a machine learning task and provide appropriate evaluation metrics well as benchmarking datasets, (2) propose Mot F esta, fully differentiable model as a first solution to learnable motif mining which discovers new motif in seconds for large datasets, and (3) we show that motif mining could also serve as an effective unsu- pervised pre-training routine and interpretable feature selector in real-world datasets.
2
TASK
2.1
NETWORK MOTIF DEFINITION
We start from the classical definition of motif which is a subgraph with larger frequency than expected (Milo al. 2002). More formally, let (V,,,) be a connected subgraph drawn from a graph dataset where V is a set of nodes, C x set of edges, and X glVixd is feature matrix.
The frequency of subgraph g given by:
f(g. = 1(:
c hCHH
(I)
where we count the number of subgraphs isomorphic to g. The raw frequency of a motif leads to the task of frequent subgraph mining @iang et al.) (203)) where
interested in finding the set of subgraphs g with maximal frequency. However to obtain significant motifs, the frequency must be normalized by the frequency of the subgraph in null model that preserves the generic properties of the original network while ablating significantly enriched subgraphs (Milo et al.) 2002). The null graphs give us baseline expectation of subgraph occurrence and therefore points us toward significantly enriched subgraphs.
Given a randomized (aka null) dataset J. is considered a motif of G if
[ 9)1
>
(2)
f(g.9)
is sufficiently large for some threshold [o, 1].
An approximate motif follows the same definition but we simply replace the isomorphism condition
with a graph similarity function such graph kernel (Vishwanathan al. 2010 Kriege et al.
2

---

Under review as a conference paper at ICLR 2023
2020) edit distance (Riesen & Bunke 2009), to allow non-isomorphic but similar subgraphs contribute to f(g g).
Evaluating exactly is exponential in the size of the search space and of the motifs and thus in- tractable for many real-world settings. Here, machine learning methods offer the advantage of cap- turing statistical properties of datasets and allowing us to cast the problem in terms of efficient vector distances and similarities. Translating the task of identifying motif occurrences to a machine learning context, we view the process as node labeling.
3 MOTIFIESTA: MOTIF MINING MODEL
Here, describe the proposed approximate motif mining algorithm, MotiFiesta. We saw in Section[2.] that a motif is a subgraph that occurs with a sufficiently large normalized concentration. The challenge of motif mining is to search for the set all such subgraphs and their occurrences in large dataset of graphs. We propose to tackle the structural similarity and concentration problems by training two neural layers: a subgraph embedder ó and subgraph density estimator f. Mcan- while, the search for subgraphs that fit the motif definition borrows the intuition that motifs can be composed of smaller adjacent motifs and therefore one can limit the search space by looking around a current set of motifs for larger ones (Schreiber & Schwöbbermeyer 2010 Oliver et al. 2022 Kashtan et al. 2004b). We bring this search strategy to differentiable setting by adapting the Edge- Pool graph coarsening layer (Diehl 2019). Our customized EdgePool layer is trained to coarsen subgraphs that fit the motif definition into a single node that the neighbours of coarsened node become candidates for larger motifs and further coarsening. To decide which subgraphs to coarsen, rely graph similarity function K that enables defining similar subgraphs. We learn model e that maps similar subgraphs to close points in a vector space see section 3.2 Finally, we rely on vector density estimation model f to compare the frequency of subgraphs in our dataset to the ones in decoy datasets see Section 3.3 Our model then learns group together subgraphs more fre- quent in our dataset. The fully end-to-end nature of the proposed method is chosen to take advantage of the scalability benefits of neural representation methods along with the ability to connect motif mining directly with supervised learning models. The execution of Mot Fiesta is illustrated in Figure
3.1 SUBGRAPH SEARCH THROUGH LEARNABLE GRAPH COARSENING
The main intuition behind Mot MotiFiestar motif search strategy is to take advantage of the com- posability motifs in a differentiable manner by adapting EdgePool (Diehl 2019). For an input graph, the EdgePool layer collapses pairs of nodes connected by edge into single node to obtain a coarsened graph. The layer collapses edges based on a learned probability and computes a new embedding that combines embeddings of collapsed nodes into single node in the coarsened graph. As edge pooling layers are stacked, each node of upper layers contains information from larger and larger subgraphs in the original graph. Moreover, because all pooling events are carried out over edges, we guarantee that the subgraph being represented by each node is always connected which inherently satisfies the first criteria of motifs. The twist that we introduce is cast the decision to collapse an edge when the corresponding subgraphs fit the motif definition.
As we need ensure that embeddings assigned to each correspond to structural similarity, we need to keep track of the subgraph being encoded by each coarsened node. We define the spotlight of node SI.(u), as the subgraph in the original graph whose nodes have been coarsened into u. As initialization, we define spotlights for the original input graph as Vu E V.SI.(u) = {u]. Then for each coarsening event, pair of adjacent nodes is collapsed into a new node w so we have SL(w) SL(u) U SL()). At any point in the coarsening, the spotlight maps newly created node to unique connected subgraph in the input. Figure illustrates the notion spotlight.
3.2 SUBSTRUCTURE REPRESENTATION LOSS
The first loss term of model ensures that similarities in node embeddings encode structural similarities of the subgraphs (spotlights) they represent. This step is necessary for ensuring that subsequent density estimates in the embedding space point regions of high structural similarity,
3

---

Under review as a conference paper at ICLR 2023
EMBED A
SCORE
POOL
(i..)
(i.5)
Representation Loss
Concentration Loss
Randommied Grapãa
Expus Gpople
((t)
STG))
((t-0) SL()
Arlon 2.8)
(2is k3) ~ (SL,) SL(F)
(i.j) ~ Ay 2,
Figure I: Execution flow MotiFiesta through the view of one edge coarsening step t. Node embeddings computed and trained to match similarity function the subgraphs of the original graph they encode. For each edge, neural network assigns a coarsening probability ai.jj each edge according. The probability is trained assign large values to embeddings with large density in the data relative to a randomized graph dataset. Finally, we sweep through the edges of the graph while coarsening each with probability (i, create the graph step t ++1
and allows us to casily accommodate approximate motif instances. Given any graph similarity
function, simg (gt, 93) + [0, 1]. and a graph embedding function g Rd define the representation loss for a pair nodes (u, v) as:
Cuep(u, u, Φ) [(((u)), o(v)) sime (SL,
(3)
To avoid quadratic scaling factor with batch size n, we can randomly sample a fixed number of reference subgraphs B to compute only B subgraph comparisons. The choice of similarity function will dictate the implicit rule determining motif belonging and thus application specific considerations can be encoded at this step (Oliver et al. [2022). Additionally, functions with explicit feature maps or proper kernels and can use the inductive nature of á to avoid evaluating similarity across all possible pairs of nodes. For these experiments we the Wasserstein Weisfeiler Lehman graph kernel (Togminalli et al.) (2019) which jointly models structural similarity and node feature agreement on general undirected graphs.
restricted to
3.3 CONCENTRATION LOSS
The embedding model é gives node embeddings which represent connected subgraphs of the original graph. Next, we need to identify which of these subgraphs fits the concentration criterion of motifs. Let the embedding of node ddu) be 2n. remembering that the embedding is trained to represent the subgraph SL(w). To assign score to each edge at given coarsening step we pre-compute coarsened embeddings zwe over all edges (u, v) E g(0), and train scoring function Zue [0, 1]. The score is designed assign large probability to high density subgraphs. We implement with simple MLP and train it using an efficient vector density estimator so that the second loss term is given by
Z
Lconcentration (o, Z,2:8.A) - - (4 Eo(z)).
(2)))
4

---

Under review as a conference paper at ICLR 2023
f2() ) is the difference in density estimates of under batch of embeddings computed for the imput graphs and randomized (rewired) graphs Z, is the regulariza- tion strength which shrinks the scores to zero, and 3 controls the growth of a for more concentrated motifs. To generate Z we apply the standard technique described in (Schreiber & Schwäbbermeyer, 2010) which iteratively swaps pairs of edges with each other such that local connectivity patterns are disrupted but the global graph statistics such size and degree distribution are maintained.
where Ay(2; = f2(2))
Embeddings with high density under the input graphs and low concentration under the randomized distribution will result in a large negative contribution to the loss. In this case (2;) = will best minimize the loss. Non-concentrated subgraphs, or those with high concentration in both distributions will have their pushed to zero by the regularization term. As we expect motifs to occur less frequently than other embeddings, we apply an exponential to the delta function so that non-motif embeddings do not overwhelm the contribution of concentrated subgraphs.
There several choices for the density estimate f but here choose the k-NN density estimator (Mack & Rosenblatt 1979) for its efficiency. This estimator is based on the intuition that a point dense region will average have a small distance its k-th nearest neighbor which can be efficiently computed using K-D trees. We therefore let fx,A (z) N
R= where R& Rx(x) is
the distance between r and its k--th nearest neighbor, and Vd is the volume of unit d-dimensional sphere used for normalization.
A wrap up of these three components outlined in Algorithm and model architecture details are in Appendix 6.3
Algorithm MotiFieste learnable edge contraction. We train model to coarsen adjacent nodes if the subgraph they induce qualifies motif.
1: Input: batch of graphs G. graph similarity function simg, density estimator f
2: Output: embedding model ø and scoring model s
3: SL(u) + {u} for each tracks subgraph of coarsened nodes
4: I - rewire(g)
5: g()) eg
6: 0, + initialize edge score and node embedding models
7: // Repeat this loop for Ç
8: for 1- 1,...,' do
9:
G(I) +0
for (u, (t) do
11:
+ 6(u, v) Joint embedding (zur) Uniform(O,) 1) then
Add new node w g( with feature vector zuv Add edges from w to Nei(u) and Nei(u).
14:
15:
Update spotlights SL(w) + SL(w) U (Lr) end if
16:
17:
end for
18:
Add remaining unpooled nodes and edges from (t--1) to g(t)
19:
Backprop ( Zu, zv) +- [1 2n) - sima (SL(u). (L)()) for all nodes.
20:
Backprop Leone (a,, Zuv) <- -o (Z ) exp (-fz (zwv) f2 [z()))) for all edges.
21:
end for
3.4 DECODING
The output required to evaluate M-Jaccard coefficient is an assignment of nodes to fixed number of discrete categories (motifs). However, the model does not assign embeddings to any categories, instead it only models the motif-likeness through the pooling score o. To collapse this score to K motifs we apply a locality sensitive hash (Dasuupta al. 2011) to all the embeddings in the dataset. Each embedding (spotlight) is assigned to a bucket by a locality sensitive hashing function such that similar embeddings are assigned to the same bucket, leveraging the approximate motif properties enforced by representation loss.
continuous property of all subgraphs in the dataset
5

---

Under review as a conference paper at ICLR 2023
The bucket identifier can then be taken as an integer code of the nodes in the original graph. For each bucket, we are given the mean or score and keep only the top K scoring buckets while the rest assigned to the 'no motif" label. At this point apply the M-Jaccard coefficient permutation test on datasets where have a ground truth motif labeling. We summarize the decoding execution in Algorithm
3.5 COMPLEXITY ANALYSIS
The bulk of runtime is spent on the training step which is performed once per dataset. Since we chose the Wasserstein Weisfeiler Lehman graph kernel, evaluating the representation loss for nodes requires Omn²) calls to the WWL kernel with runtime Onn log(n)) where is the number of graphs one batch. As an implementation detail, we were able to achieve good performance by computing constant number of pairwise subgraph comparisons regardless of batch size to avoid the quadratic cost. The density estimation is built on a nearest neighbor estimator which relies on quick neighbourhood searches which can be implemented phase, we execute a forward pass through the scoring and pooling which is (()). To discretize the subgraphs
K-d tree in (log(m)). In the induction
an (n) locality sensitive hashing procedure. We note that polynomial and sub-polynomial runtimes for classical enumeration methods are very rare. Typical training times on were around 2 hours for the synthetic datasets on single GPU, and the decoding step takes 10 seconds.
RESULTS
We test the proposed model and model evaluation framework in three settings. The first experiment the ability of MotiFiesta retrieve motifs in synthetic datasets when the ground truth motifs are known. Finally, we explore the potential for the motif mining task as an unsupervised pre-training step graph classification setting. Finally, to explore the relevance and interpretability of the motif mining procedure we perform ablation study important motifs.
mined motifs to search for
4.1 MINING FOR PLANTED MOTIFS
To evaluate the motif mining capacity of our trained models, we propose in (Ying 2020) build synthetic dataset where motifs are artificially injected at high concentrations at known posi- tions (see Appendix 6.1]. In this context, and in real-world datasets where ground-truit -trth motifs are known, evaluating the performance of motif miner can be done through efficient set comparisons through a small modification of the Jaccard measure.
We denote the (soft) labeling with Y [0, 1]|V which specifies the probability that node belongs to motif j for all graphs in dataset where K is the number of motifs in the dataset. In not given the model at synthetic setting, the number of motifs is known a priori assignment of nodes to motifs, training time. Note that this framing allows for soft (probabilistic) non-isomorphic motif occurrences, as well as one node belonging to multiple motifs (non-disjoint motifs).
When considering single dimension (motif), we see that Y..i partitions & into those nodes inside motif Y. + and those outside the motif Y-, + 0. At this point, we wish measure the agreement between two sets for all motifs, for which the Jaccard coefficient is widely accepted. Here, we use the generalization of the Jaccard coefficient to real-valued sets. To evaluate the model applied to a single graph, we have
min Yig. Yis) max (Yg. Y,,)
JÝ Y)
where Ý, Y.Ye [0, 1
The Jaccard coefficient ranges from 0 to and simultaneously captures precision and recall. Models which over-assign nodes to given motif penalized by the denominator which considers the

---

Under review as a conference paper at ICLR 2023
union of the prediction and the true motif, while model that misses motif nodes will have low numerator value.
Because there is no inherent ordering to motif sets, the labeling assigned by the model and the one chosen for ground-truth motifs will be arbitrary. The final performance measure for a motif labeling is therefore given by the maximum Jaccard coefficient over all permutations Sx of the columns of Y:
M-Jaccard Y, Y)
max xESM
(Y)).
(5)
We generate several synthetic datasets that capture different motif-related variables. Each dataset consists of 1000 graphs generated randomly using the Erdös-Reyni random graph generator. Next, we generate one more subgraphs that will act as the motifs. To create concentrated subgraphs we insert the motifs graphs into the each of the original graph and randomly connect nodes in the motif to the rest of the graph. In this manner know which nodes belong to motif's and can control the concentration, size, topology, and structural variability of the motifs. This comes with a caveat since it is possible that the base graphs already contain motif occurrences naturally which would not be annotated as motif instances. is possible to check the extent of this problem for simple motifs that have specified counting algorithms (e.g. cliques) which show in Appendix [ To mitigate this effect, we focus our evaluation on larger motifs (10 nodes) for most experiments.
We test three main motif mining conditions: motif topology, number of motifs in the dataset, and varying true concentration of the motif using the M-Jaccard. Results are summarized in Table [] (continued in Appendix (8) and sample of top scoring motif sets for various settings are shown in Figure 2 As a control condition, for each dataset we train model where all edge scores are fixed 0.5. Before performing the M-Jaccard, we performed simple check on the behaviour of the scores to verify that motif nodes are assigned larger scores (see Appendix 7).
(a) Star
(b) Barbell
(c) Clique
Figure 2: Random samples from most populated buckets with ground truth motif nodes in blue.
The hyperparameter set remains the same for all experiments (see Appendix 6.3 Results for all conditions tested are summarized Appendix. The decoding step uses small grid search over the flexibility parameter in the hashing step (hash size) as well as in the pooling layer to use (subgraph size), we output the max average accuracy over repetitions for each condition. Mot iF Festa is able to consistently outperform the random baseline in many conditions. Notably, it appears that when the topology the motif is well defined (as in the case of the barbell and clique) we the strongest results, indicating that the power of the graph embedding model is important factor. As external comparisons, we apply the classical Mfinder (Kashtan et al.) 2004a) and neural method SP-Miner (Ying al. 2020) on synthetic motifs. Since Mfndee limited to small isomorphic motifs we only test the different topologies and find that for all except the clique, we are able to achieve significantly higher performance (see Appendix (6.6). We find similar results when comparing to SP-Miner which is designed to mine the globally most frequent isomorphic subgraphs (see Appendix 6.7p. We note that both these algorithms, while performing similar tasks, are not directly comparable to our approximate and significant motif mining setting.
4.2 MOTIF MINING AS FEATURE EXTRACTION
Apart from applications in data mining, we explore the potential for the motif task as a pre-training phase in supervised learning. We therefore test the view that motifs statistically robust and
7

---

Under review as a conference paper at ICLR 2023
c= 0
0.01
0.02
< 0.05
barbell
0.68 0.04 0.040
0.66 1 0.05
0.69 1 0.01 (0.32
0.67 0.02 (0.34
clique
0.58 0.14 (0.35 = 0.00)
0.62 = 0.08
0.1
0.41 4 0.08 (0.34
random
0.51 0.03 (0.34 0.00)
0.49 0.02 -
0.46 0.02 00.05++000)
0.44 (0.35
star
0.43 1: 0.09 (0.43 0.03)
0.42 1 0.02 (0:40 0.04)
0.40 0.02 (0.38
0.40 1 0.03 (0.38 0.0))
nodes
0.37 0.02 (0.34 0.00)
0.36 = 0.00 (0.35 0.01)
0.36 0.01 (0.36
0.36 :: 0.00 (0.35 0.02)
10 nodes
0.48 1 0.02 (0.35 0.00)
0.46 1 0.03 (0.35 0.00)
0.43 0.01 (0.38 0.04)
0.47 1: 0.03 (0.35 0.01)
20 nodes
0.48 + 0.12 (0.34 0.01)
0.43 1 0.08 (0.35 = 0.01)
0.44 1 0.03 (0.39 0.05)
0.33 1: 0.00 (0.34 0.00)
Table I: M-Jaccard score under various synthetic motif mining conditions. Each row contains the M- Jaccard score when lesting on motif datasets with each edge of the motifs distorted with probability Unless specified otherwise, motif instances are of size 10 nodes. The values in small type and parentheses are the scores obtained by dummy model that assigns all edges a merging probability of 0.5. The largest score in each experiment is in bold when significant.
structurally complex feature sets. Taking three real world datasets in the TUDataset (Morris et al.) 2020) from various domains we train Mot ifiisti using only the representation and concentration loss again with rewired graphs as a negative distribution. Once the motif mining model is trained we compute a whole graph embedding by applying a global pooling to each merging layer and concatenate the output of each layer produce graph embedding dimensions each, we obtain a 7 x d feature vector for each graph. Once training converges, we freeze Mot estta and pass the embeddings to random forest classifier. In this manner, the embeddings are computed without any information about the classification labels. As baselines we train three graph neural network models an end to end fashion (EdgePool, GCN (Kipf & Welling 2016). GIN (Xu et al. 2018)). We report the results in Table 2
that for T pooling layers of
PROTEINS
COX2
IMDB-BINARY
MotiFiesta EdgePool Diehl (019
73.1+2.0
80.7+:2.4
72.2:13.3
73.
80.5
71,8++3.6
GCN Kipf Welling 2016)
73.5
80.9
72.8
GIN Xu et al. 2018)
72.6
79.615.1
73.4
Table 2: Classification performance of Mot iiistaa on graph classification benchmarks.
Across three different datasets, using motif-hased embeddings has similar performance state of the art graph neural network architectures. It cannot be said that this method improves the state of the art but given the unsupervised nature of MotiFiesta, this result suggests that computing embeddings solely by focusing the attention of the model towards statistically enriched subgraphs (motifs) can be a powerful and efficient way of extracting useful subgraph features. This provides support for the notion that frequent subgraphs are useful inductive bias in prediction tasks.
4.3 MOST SIGNIFICANT MOTIFS CORRELATE WITH MODEL PERFORMANCE
In real-world datasets, we lack ground-truth motifs, making definite motif mining evaluation dif- ficult. Despite this limitation, we propose study the importance of the mined motifs through ablation studies on classification tasks. If the motifs identified in real-world datasets hold important information about the functioning of the network, excluding their embeddings from the global graph embedding should have an impact on classification performance. Next, we apply the same models trained for 2 but when computing the global graph embedding, we only allow subgraphs with the top L a scores to contribute to the global graph embedding. The intuition is that the subgraphs which the model assigns the highest motif likeness should lead to the strongest classification performance. To control for the differing amount of information entering the global embedding with varying L, we also filter the embeddings by picking L spotlights at random (red line). We see in Figure 3 general upward trend in performance as L grows while the top L filtered models outperform the random model for low values of L. This indicates that in a fully unsupervised manner, the model is able to identify useful subgraphs.
8

---

Under review as a conference paper at ICLR 2023
tap
0.72
0.80
0.00
0.70
0.675
0.050
0.52
0.30
0.000
0.755
0.70
3.0
PROTEINS
(b) COX2
Figure 3: Subgraph ablation study. Using only the subgraphs with the largest score leads to the best performance compared choosing random subgraphs during classification.
One could then simply inspect motif's with large o values for potentially explanatory subgraphs and owing to the representation term in the training, all similar subgraphs are also given for free for inspection. Generally, do expect that motif-likeness will contain information about graph- level properties (e.g. classification label) for all datasets. However, the large body of motif min- ing literature contains many examples of settings where motifs do point towards network function Aacosta-Mendozi et al. [2022] Milo et al. 2002 Leontis et al. 2006). We leave further inspection of these subgraphs for future work.
5 CONCLUSION
We introduced a framing of the approximate network motif problem in manner suitable for ma- chine learning models, and propose a first model architecture to address this challenge. The model we propose for this task is able to efficiently recover motifs over baselines several synthetic data conditions with decoding times the order of seconds. When placed in classification setting show that motif mining has potential as a challenging pre-training step and that the obtained mo- tifs show potential to be naturally used as interpretable feature extractors. Although the inductive nature of our model provides a significant performance boost at inference time, the subgraph simi- larity loss computation is quadratic of polynomial time kernel which could limit the sensitivity of the model. Additionally, the decoding phase requires tuning of several parameters which has to be carefully chosen for each application. Further exploration of of efficient subgraph representa- tion functions Bevilacquu et al. (2021) and graph partitioning [Burritsas et al. (2021) models will therefore become relevant topies for motif mining. We also expect that the specific choices of the modules in MotiFis Fietta will be highly domain-specific. Certain datasets will naturally call for different notions of subgraph similarity, and certain datasets will tolerate varying degrees of distor- tion in their motif occurrences. Future work should also focus in further exploring the impact of these module choices.
AVAILABILITY
The code all experiments is made available as a tarball. will made available on GitHub after the anonymous phase.
REFERENCES
Niusvel Andrés Gago-Alonss and José E Medina-Pagola, Frequent approximate subgraphs as features for graph- image classification. Knowledge-Bord -aaelddge--Beedddd Systems, 27:381- 392, 2012.

---

Under review as a conference paper at ICLR 2023
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24(13): 1241-i249, 2008.
Maciej Besta, Raphael Grob, Cesare Miglioli, Nicola Bernold, Grzegorz Kwasniewski, Gabriel Gjini, Raghavendra Kanakagiri, Saleh Ashkboos, Lukas Gianinazzi, Nikoli Dryden, et al. Motif prediction with graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 35-45, 2022.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. arXiv preprint arXiv: 10.02910, 2021.
Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael Bronstein. Partition and code: learning how compress graphs. Advances in Neural Information Processing Systems, 34: 18603-18619, 2021.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383- 10395, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. Advances in Neural Information Processing Systems, 14:1713-1726, 2021.
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. Fast locality-sensitive hashing, In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1073-1081, 2011.
Frederik Diehl. Edge contraction pooling for graph neural networks arXiv: 10990, 2019.
arXiv preprint
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. arXiv preprint arXiv:2001.096211 2020.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
Chuntao Jiang, Frans Coenen, and Michele Zito. A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review, 28(1):75-105, 2013.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, pp. 4839-4848. PMLR, 2020.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimat- ing subgraph concentrations and detecting network motifs. Bioinformatics, 20411)1176-11588, 2004a.
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Topological generalizations of network motifs. Physical Review E, 70(3):031909 2004b.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv:1609.02900 2016.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
Neocles B Leontis, Aurelie Lescoute, and Eric Westhof. The building blocks and motifs of ma architecture. Current opinion in structural biology, 16(3):279-287, 2006.
10

---

Under review as a conference paper at ICLR 2023
Ruirui Li and Wei Wang. Reafum: Representative approximate frequent subgraph mining. In Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 757-765, SIAM, 2015.
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-383-0 3845. PMLR, 2019.
Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1959-1969, 2020.
YP Mack and Murray Rosenblatt. Multivariate k-nearest neighbor density estimates. Journal of Multivariaate Analysis, 9(1):1-15, 1979.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594):824-82) 2002.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. graphl hampheearningg...
Siegfried Nijssen and Joost Kok, quickstart in frequent structure mining can make a difference. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 647-652, 2004.
Carlos Oliver, Vincent Mallet, Pericles Philippopoulos, William L Hamilton, and Jérôme Wald- ispühl. Vernal: tool for mining fuzzy network motifs in ma. Bioinformatics, 3844)997--976 2022.
Alan Perotti, Paolo Bajardi, Francesco Bonchi, and André Panisson. Graphshap: Motif- basid- ex- planations for black-box graph classifiers. arXiv preprint wwXiv:2202.088/5. 2022.
Vladimir Reinharz, Antoine Soulé, Eric Westhof, Jérôme Waldispühl, and Alain Denise. Mining for recurrent long-range interactions in ma structures reveals embedded hierarchies in network families. Nucleic acids research, 46(8):38413385 2018.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing, 27(7):950-99) 95900999.1011 2009.
Ryan A Rossi, Nesreen Ahmed, Eunyee Koh, Sungchul Kim. Anup Rao, and Yasin Abbasi- Yadkori. A structural graph representation learning framework. In Proceedings of the 13th inter- national conference on web search and data mining, pp. 483-491, 2020.
Falk Schreiber and Henning Schwöhbermeyer. Motifs in biological networks. In Statistical and Evolutionary Analysis of Biological Networks, pp. 45-64 World Scientific, 2010.
Carlos HC Teixeira, Mayank Kakodkar, Vinícius Dias, Wagner Meira, and Bruno Ribeiro. Sequen- tial stratified regeneration: Meme for large state spaces with an application to subgraph count estimation. Data Mining and Knowledge Discovery, 36(():614444440 447, 202.
Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. Advances in Neural Information Processing Systems, 34, 2021.
Matteo Togninalli. Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels. Advances in Neural Information Processing Sys- tems, 32, 2019.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 1 11: 1011-222 2010.
Sebastian Wernicke. Efficient detection of network motifs. JEEE/ACM transactions on computa- fional biology and bioinformatics, 3(4):347-359, 2006.

---

Under review as a conference paper at ICLR 2023
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In 2002 IEEE Inter- national Conference on Data Mining, 2002. Proceedings, pp. 721-724. IEEE, 2002.
R. Ying. Wang. You, and Jure Leskovec. Frequent subgraph mining by walking in order embedding space. 2020.
Shuo Yu, Yufan Feng, Da Zhang, Hayat Dino Bedru, Bo Xu, and Feng Xia. Motif discovery in networks: a survey. Computer Science Review, 37:100267, 2020.
Shichang Zhang, Ziniu Hu, Arjun Subramonian, and Yizhou Sun. Motif-driven contrastive learning of graph representations. arXiv preprint arXiv:2012./2533 2020.
Shijie Zhang and Jiong Yang. Ram: Randomized approximate graph mining. In International Conference on Scientific and Statistical Database Management, pp. 187-203. Springer, 2008
Yun Zhang, Faisal N Abu-Khzam, Nicole E Baldwin, Elissa J Chesler, Michael A Langston, and Na- giza F Samatova. Genome-scale computational approaches to memory-intensive applications in systems biology. In SC'05: Proceedings of the 2005 ACM/IEEE Conference Supercomputing, pp. 12-12. IEEE, 2005.
12

---

Under review as a conference paper at ICLR 2023
Appendix
The appendix contains additional details regarding dataset preparation, benchmarking, and experi- ment setup.
6.1 DATASET PREPARATION
To test motif mining models on datasets with ground truth motifs we generate synthetic graphs and repeatedly insert motifs to create over-represented subgraphs known positions. The dataset con- struction process admits several choices including number and type of motifs to insert, abundance and degree of distortion across motif instances. For given motif graph m and randomly generated graph g. we randomly sample node from .V(g) to delete and replace with m. Each g is gen- crated using the Reils- random graph generator with a connection probability p = 0.1. Next, randomly sample pairs of nodes from (u, v) (g) (mm) as the set of edges that connect m to the rest of g. all experiments, the graph containing the motif chosen to be twice as large as the motif. Distorting motif according to probability is done by iterating over all node pairs u, E V and with probability c, we create an edge between u and e does not exist, and delete the edge if it does exist. Table summarizes these parameter choices.
Variable
Values
Description
Motif type
barbell, wheel, random, star, clique 3, 5, 10, 20 30%, 50%, 100%
Topology of planted motif Number of nodes planted motif Fraction of graphs where motif appears.
Motif size
Concentration
Number of motifs
1, 3, 10
Number of motifs in single dataset. Probability of distorting edge in motif.
Distortion probability (e)
001, .020 .05
Table 3: Synthetic dataset construction parameters
6.2 ADAPTING EDGEPOOT. FOR MOTIF MINING
The EdgePool layer introduced in Dichl 2019) computes a new graph G" from an input graph G (V, F,, X) by first computing
Sur MLP V(u, E. A greedy algorithm chooses edges with the highest scores first and collapses them into a new node we denote as un, and computes a new node embedding Tur Pool The Pool operation is typically sum pool but can be any differentiable operation. Contraction is stopped when no edges that connect previously pooled nodes are left. Nodes that do not belong
contracted edge are assigned to new node in G". That is, after the pooling step, every node in G is assigned to exactly one node in G' and contracted pairs of nodes are mapped to the same node in G'. Mot iostiFieste iesta we wish to allow for the possibility that some graphs do not give rise to motifs if they do not fit the concentration criteria. For this reason we replace the greedy contraction algorithm with a random sampling. Each edge assigned a probability using Sigmoid layer and the node set is computed by iterating through each edge and adding to the pooled edges with probability proportional to (u, v). As such, our version of coarsening is stochastic. Additionally, EdgePool computes joint embeddings Tae only after deciding to contract an edge. Instead we wish for the model to make the pooling decision as a function of the join! subgraph and thus in our modification, s(u, v) Sigmoid(Pool(2) x.))), for which joint embeddings are computed before the merging step.
6.3 MOTIF IESTA ARCHITECTURE
The models built for main results follow the hyperparameters choices outlined in Table Once a model is trained, the bSHeb decoding phase admits two choices. The first is the dimensionality of the hash digest which we vary from (8, 16, 32} and which controls the collision probability when assigning embeddings motif label. Larger hash digests have lower collision probabilities and
13

---

Under review as a conference paper at ICLR 2023
therefore more sensitive to variability in motif structure. The second choice in decoding is the MotiFin aetita pooling layer to use, for larger motifs we choose higher layers. This is also varied from 2 to 4 in our experiments.
Parameter
Values
Embedding model
MLP, ReLU activation
Embedding size
8
Pooling layers
Scoring model
MLP, Sigmoid activation
Table 4: Hyperparameter choices for Mot iFiesta
6.4 DECODING ALGORITHM
In Algorithm g we describe the procedure of going from MotiFiesta model to K dimen- sional labeling containing the top K motifs.
Algorithm Motif decoding process. Compute integer code for all node embeddings to assign each subgraph to a motif ID. We rank motif IDs by the mean pooling score o its constituent subgraphs keeping only the top K.
1: Input: batch of graphs G. Motiiieste model he, coarsening level T, number of motifs K
2: Output: node-to-motif assignment matrix Ý [0, (] x
3: Z. S.S + h T) collect all node embeddings after 7 layers and scores
(2) map each embedding to integer code. 5: H. < set of unique hash codes in H.
4: +- LocalitySSensitieHaar
6: Y <- OneHot( H, H)
7: Let R(H:S) return the rank of a hash code by descending mean score of all subgraphs with the
same hash.
8: for H do
9: if R()) K then
[h t
11: end if
end for
13: return
6.5 OBSERVED RUNTIME
Training time on typical synthetic runs using NVIDIA GeForce GTX 1080 varied between 4-8 hours on the synthetic datasets. We benchmark the decoding time on one of our synthetic datasets of 1000 graphs of 20 nodes each. Results for 30 runs for decoding at I to 4 pooling layers shown in Fig Decoding was performed on a personal laptop using 1.6GHz dual-core Intel Core i5 processor.
14

---

Under review as a conference paper at ICLR 2023
40
30
Time (s)
25
20
15
(1.6/2.0)
(3.4/7.11 Level (mean subgraph size / max subgraph size)
(2.4/4.0)
(4.8/12.7)
Figure 4: Decoding Runtime. Given a trained model, we decode motifs at each specified pooling layer (1-4, on x-axis) and note the resulting mean subgraph size and largest subgraph found each layer.
6.6 COMPARISON WITH EXACT METHOD
As an external comparison of motif retrieval, we compare with the popular exact motif mining algorithm, MFFiddrr Kashtan et al. (2004)). Since this method enumerates substructures the software crashed after hours on datasets containing motifs of size 5 which is the smallest motif we tested on Mot iiiista Single-motif datasets with size 4 motifs did execute successfully for each of our motif topologies, and 4 distortion levels. Resulting M-Jaccard values are summarized in Table 5 MFinder unable to retrieve the planted motif for all topologies except for cliques which are almost. perfectly recovered.
0.00
= 0.01
0.02
0.05
barbell
0.00
0.04
0.08
0.22
clique
1.00
0.94
0.88
0.73
random
0.00
0.05
0.09
0.18
star
0.00
0.10
0.18
0.33
Table 5: M-Jaccard coefficient using MFinder Kashtan et al. (2004a)
on synthetic dataset with motifs of size 4.
Because in MFinder, only isomorphic subgraphs are counted part of motif, we observe that when the motif is missed, completely missed (M-Jaccard - 0). This particularly noticeable when distortion probability is close to zero, and the opposite trend can be seen for cliques where the algorithm successfully detects the motif it catches all instances and performance decreases with distortion probability. We note that at such small motif sizes, the M-Jaccard that only counts inserted motifs the motif set can misleading as randomized graphs can include naturally occurring motif' occurrences that the score will not be aware of. Since it is costly count subgraph occurrences in
15

---

Under review as a conference paper at ICLR 2023
general we provide count of clique occurrences using clique finder algorithm (CITE). While we manually insert one clique each graph for 1000 graphs, Table shows that below cliques of size 10, there are actually many more cliques than are inserted. Cliques enumerated using the NetworkX Hagberg et al. 2008 implementation of /Zang et al. 2005).
0.00
0.01
0.02
0.05
clique size
4
210000
198339
870
743
5
252000
229164
0
6
210000
182185
0
0
8
45000
34589
0
0
10
1000
659
0
Table 6: True count of clique occurrences in synthetically generated datasets. Each column repeats the count after distorting the motif with probability c.
6.7 COMPARISON TO NEURAL METHON
As an additional external comparison take SP-Miner Ying et al. (2020), the most similar ap- proach we could find. The SP-Miner model computes the most unnormalized frequent subgraphs and is restricted to isomorphism up to WL isomorphism test. this reason the results are not included as part of the main results. Nevertheless the results highlight the importance of model- ing subgraph similarity as well as the use of significance testing for motifs. M-Jaccard scores for analogous settings to Table T are show in Table
0.00
0.01
0.02
0.05
dataset
barbell
0.008
0.008
0.010
0.011
clique
0.018
0.012
0.009
0,008
random
0.011
0.008
0.007
0.007
star
0.014
0.014
0.012
0.009
Table 7: M-Jaccard results for SP-Miner
Ying et al.
2020) neural frequent subgraph miner.
7 ANALYSIS AND VISUALIZATION OF MERGING SCORES
After training Mot iotiFiesee on dataset, we compute the M-Jaccard coefficient both the original data distribution, as well as on datasets with increasing degrees distortion applied to the motif subgraphs. Before applying the decoding step, however subgraph scoring layer. Since by construction (see Appendix 6.I we know which nodes belong to motifs and which do not, should expect that measuring the merging in motif nodes should be significantly larger than for non-motif nodes. In Figure [5b see a clear separation between the two distributions, indicating that the model is able to assign proper scores enriched subgraphs. As a visual aid, we show the pooling process on an example graph in Figure
already assess the quality of the
assigned by the model
Sa
M-JACCARD CONTINUED
In Table we include the results of experimenting on datasets with varying number of motifs (3 motifs, motifs) well as different concentrations (sparsity 0.3, 0.5, 1) where the sparsity represents the probability that given graph will contain motif instance.
16

---

Under review as a conference paper at ICLR 2023
30-
25-
10-
non-moth
(a) Illustration of edge pooling execution.
(b) Pooling score distribution.
Figure 5: (a) input graph the bottom with white nodes, and motif nodes drawn with star shape. Pooled nodes are connected to the collapsed node by a dotted line. Illustration shows stacked pooling layers. (b) distribution of edge scores assigned nodes within known motif versus those outside of the motif subgraph.
motifs motifs
0.19 0.01 (0.18 0.01)
0.29
01.5 (0.18 0.01)
0.24 + 0.06 (0.17
(..99 + 0.06 (0.19 0.01)
0.11 1:11::00 0.00
0.11
0.00 (000
0.11 +: 0.00 (0.11
0.11 4: 0.00 (0.11 0.00)
sparse-0.30
0.36 :: 0.00 (0.33 0.02)
0.36 ::: 0.01 (0.35 0.00)
0.35 1: 0.01 (0.34 0.001)
0.35 1: 0.00 (0.34 0.00
sparse-0.50
0.40 : 0.03 (0.34 0.00)
0.43 : 0.02 (0.34 0.00)
0.40 : 0.04 (U.34 0.00)
0.43 1: 0.05 (0.34 1: 0.01)
sparse-1.00
0.40 (0.34 0.00)
0.42 (0.32 0.02)
0.41 0.02 (0.34 0.00)
0.42 + 0.04 (0.34 0.00)
Table 8: Continuation of M-Jaccard score under various synthetic motif mining conditions. Each row contains the M-Jaccard score when testing motif datasets with each edge of the motif's dis- torted with probability e. Unless specified otherwise, motif instances are of size nodes. The values in small type and parentheses are the scores obtained by dummy model that assigns all edges a merging probability 0.5.
17


Reviews:
[{"review_id": "yuvAcjyVvF", "reviewer": "Reviewer_4vV6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work formalized the notion of motif mining as a node-assignment problem in machine learning. It proposed an approximate motif mining algorithm, MotiFiesta, which utilizes the composability of motifs in a differentiable manner by contracting edges. This work then empirically showed that motif mining could also serve as an effective unsupervised pre-training routine and interpretable feature selector in real-world datasets.", "summary_of_the_review": "This work formalized the notion of motif mining as a node-assignment problem in machine learning. It proposed an approximate motif mining algorithm, MotiFiesta, which utilizes the composability of motifs in a differentiable manner by contracting edges. This work also empirically showed that motif mining could also serve as an effective unsupervised pre-training routine and interpretable feature selector in real-world datasets. \n\nOverall, this work has originality in its proposed graph mining algorithm, but the quality and clarity of the work could be better improved. Therefore, I recommend borderline rejection for this paper.", "strength_and_weaknesses": "Strength:\n-\n\n[+] The proposed motif mining method has some novelty.\n\n[+] The work also empirically demonstrates that ELF Distillation performs better than a variety of strong baselines on a suite of minigrid environments.\n\nWeakness:\n-\n\n[-] The experimental section misses comparison with other existing motif mining techniques.\n\n[-] The presentation of the work could be improved. Currently, the paper is hard to understand: \n\n- It is difficult to see how different sections and their subsections are connected. It would be good to add transition paragraphs/sentences in front of each (sub)section to explain how they are connected to the earlier content.\n\n- The presentation could be better improved with better usage of terminology. For example, what is the difference between graph coarsening and motif mining? It seems that many terms are used directly without definitions.\n\n-  It would also be much clearer if the paper could provide some concrete examples justifying the choice of these parts used in its proposed graph mining algorithm: search strategy, loss function, scoring function, and so on.\n\n\n[-] The presentation of the experimental results is not self-contained, which may cause confusion to the readers. \n\n- For example, in Table 1, what does the first column represent? Also, it is hard to see the trends via numeric values (figures are recommended for better visualization of comparison).\n\n[-] The empirical improvements of using motif mining to downstream tasks look incremental in Table 2. For example, the vanilla GIN model could outperform MotiFiesta in the IMDB-Binary dataset.\n\nMinor comment:\n\n- The citation style doesn't look right.", "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": "r3XeJLhVKU5", "reviewer": "Reviewer_Vrqg", "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": "This work proposes a formulation of the network motif mining problem as a machine learning task. In this task, the authors consider evaluating the top-K approximate motifs (according to some distance function) through an end-to-end learning process. The paper then proposes MotiFiesta, an architecture that leverages EdgePool layers to learn approximate motifs under this new framework. Empirically, the authors evaluate the method when retrieving motifs from synthetic datasets and when serving as a pre-training strategy for graph classification.", "summary_of_the_review": "I believe the weaknesses and clarity sections provide a good justification for my final score. I would like to make it clear that I like the direction of the paper, I think it's quite relevant. I simply think it needs more work: baselines, citations, some theoretical justification for the marginalization in subgraphs' representations. Also, I think the paper will get substantially better as the authors' improve presentation. I encourage them to resubmit soon once these problems are addressed. ", "strength_and_weaknesses": "## Strength\n\nThe main contribution of this work is an unsupervised formulation of the network motif mining problem (although it is not how the authors call it). All previous contributions relied on supervised learning to count/mine subgraphs. Here, the authors acquire the learning signal from the similarity function. The problem approached is quite important and often overlooked in the graph learning community, thus I think it is an important direction to follow.\n\n## Weaknesses\n\na) There is a fundamental problem (not acknowledged) with motif mining as a node assignment problem: it marginalizes subgraph representations. The main thing to keep in mind here is that subgraphs function as a joint structure, e.g., removing or adding a node can impact drastically whether the others' are in the subgraph or not. Think of having nodes a,b,c,d forming a square and choosing to add a node e that is connected to all of them vs adding a node f that is connected to only one of them. The issue with this marginalization procedure is vastly discussed in [1]. This issue is carried over to MotiFiesta, where coarsening iteratively induces the same problem. I understand it is a strategy to overcome the combinatorial structure of joint representations, but i) it should be clarified and discussed and ii) there are works addressing this via sampling[1] or combinatorial representations[2].\nb) The clarity issues with this paper are not so trivial. Paragraphs are too long and math definitions are in-line, which makes it hard to understand the work (see clarity section for more details).\nc) The work overlooks a huge part of existing literature in subgraph sampling and neural networks for subgraph count methods. I understand it's not *exactly* what the authors are proposing, but it should be clear what are the differences.\nd) The authors do not provide any theory, e.g. convergence guarantees, or extensive experiments. I believe in a conference such as ICLR we should convince readers in at one of this forms.\ne) Empirical evaluation is extremely limited. Table 2 has only small datasets, no OGB or Zinc evaluations for instance, and trivial baselines. See [1] in the appendix for an example of such a comparison.  There exists a vast literature in graph pre-training by now. Just to be clear, I understand the authors are not aiming at SOTA necessarily, but it's important to compare against what's more recent out there anyway. Table 1 also contains very small graphs and almost no baseline. Please see some examples of citations and baselines in the Clarity section. Finally, erdos-renyi graphs tend to present very random structure, which facilitates the task of finding an artificially injected motif (in the authors' definition).\n\n[1] Unsupervised Joint k-node Graph Representations with Compositional Energy-Based Models, Cotta et al.\n[2] Understanding and extending subgraph gnns by rethinking their symmetries, Frasca et al.", "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": "ROFemhiHUb1", "reviewer": "Reviewer_oTWr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes MotiFiesta, a novel deep-learning model to mine (approximate) motifs. The proposed method combines graph representation learning (via GNNs) and a graph coarsening (pooling) strategy to identify approximate motifs and estimate its frequency by comparison with random graphs (through local randomization). The proposed method is evaluated against random baselines and exact mining algorithms in synthetic datasets. It is also used to build motif-based representations as features for graph classification benchmarks on real world datasets.\n", "summary_of_the_review": "The paper addresses an interesting, relevant and difficult problem (graph mining with machine learning). The proposed solution is based on existing building blocks, but their use in solving a motif mining problem is interesting and novel. The relaxation of the problem into mining approximate (but still relevant) motifs is also interesting. However, there are pieces of related work missing, some lack of clarity in parts of the paper and a somewhat weak experimental setup. As such, I don't think the paper crosses the threshold for acceptance.", "strength_and_weaknesses": "### Strengths\n\nI find the problem studied in the paper (approximate mining with machine learning) to be very interesting and relevant. By extending mining to approximate motifs, the task becomes more amenable to machine learning techniques, and the paper proposes an interesting way of solving it while still focusing on identifying relevant motifs.\n\n### Weaknesses\n\nWhile the paper indicates some of the challenges of motif mining in the introduction, it lacks a more in depth discussion of the task and relevant literature, which could better situate and inform the reader by illustrating chaallenges and solutions from the data mining perspective, as well as describing in more detail what makes a machine learning solution both useful and difficult.\n\nAs for the machine learning literature, there are relevant works that either aim at applying machine learning to the mining task, or that leverage and discuss usefulness of subgraph structure for feature representation which I'd like to see discussed. Some examples:\n\n- Besta, M., Grob, R., Miglioli, C., Bernold, N., Kwasniewski, G., Gjini, G., ... & Hoefler, T. (2022, August). Motif prediction with graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 35-45).\n- Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., ... & Maron, H. (2022). Equivariant subgraph aggregation networks. International Conference on Learning Representations.\n- Cotta, L., Morris, C., & Ribeiro, B. (2021). Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34, 1713-1726.\n- Rossi, R. A., Ahmed, N. K., Koh, E., Kim, S., Rao, A., & Abbasi-Yadkori, Y. (2020, January). A structural graph representation learning framework. In Proceedings of the 13th international conference on web search and data mining (pp. 483-491).\n\nThe presentation of the paper could also be improved. Both Figures 1 and 2 were hard to understand. I recommend improving the captions and giving a better description in the text. Also, in Figure 1, it seems as if $h(\\cdot)$  can only take value either 0 or 1, whereas the text describe the domain of $h_\\theta$ as the continuum $[0, 1]$, which is confusing.\n\nThe description of the M-Jaccard coefficient seems a bit out of place. I would recomend moving it closer to the evaluation section, putting it at end of Sec 3 or beginning of Sec 4.\n\nIn the Algorithm 1, it is not clear what line 7 means. And the function $\\sigma$ is not an argument of the loss functions. How is it updated? How is the sampling step of line 12 taken into account when computing the gradients for $\\sigma$?\n\nThe results presented in Table 1 are hard to understand. It is not clear what is the comparison being made. What is the baseline? What is being compared?\n\nFinally, there are decisions made in the method which are not well discussed or evaluated, such as the choice of the similarity function, the use if LSH or the choice of the density estimation method. What were the alternatives considered and why are these choiices the best? Was an ablation study performed?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FZv8FGmJZU0", "reviewer": "Reviewer_HL23", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes the task of identifying motif occurrences as a machine learning problem. Then, it proposes a new model called MotiFiesta. MotiFiesta is separated into two parts, a subgraph embedder, and a subgraph density estimator. Unfortunately, the results are inconclusive, given that the model is not compared against any baselines or applied to any network with known ground truth motifs (even though this is mentioned in subsection 6.6 of the appendix).  ", "summary_of_the_review": "The paper proposes a new task a novel model. So, even though the clarity could be improved, the main problem of the paper is the evaluation process, where no baselines are considered. I understand that there are no baselines (considering that this is a new problem), but other motif algorithms can be used to compare the final results.\n", "strength_and_weaknesses": "The main strength of the paper is the formulation of motif occurrences as a machine learning problem. The formulation is simple and it can open a new door for motif estimation. Another important contribution is the new proposed model. Both elements are interesting and publishable, however, the evaluation and time complexity must be improved.\n\nThere are several papers that calculate the exact number of motifs (for small networks), and other approximation algorithms that try to estimate motifs. However, none of them are considered in this paper. So, currently, we have a model that can extract large motifs and approximate motifs, but there is no ground truth telling us that it works. \n\nTo improve your paper, empirically demonstrated that you are able to extract these motifs from large datasets. Maybe, instead of applying 4 o 5 node motifs reduce it to three and use some known datasets. \n\nAnother issue is the time complexity of the model, which is O(n^3\\log(n)). This time complexity makes the model unfeasible for medium size networks. Maybe, it is better to have an approximate algorithm able to extract some medium large motifs rather than applied this model.  \n\nminor comments:\nsection 1: \"size ,\"\nsubsection 2.1: \"ponts\"", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject