Predicting Network Motif Fingerprints with Graph Neural Networks

Authors: Pedro C Vieira, Miguel E. P. Silva, Pedro Manuel Pinto Ribeiro
Primary area: learning on graphs and other geometries & topologies
Keywords: motifs, graph representation learning, synthetic data, significance profiles

Abstract:
Graph Neural Networks (GNNs) are a predominant method for graph representation learning. However, beyond subgraph frequency estimation, their application to network motif prediction remains underexplored, with no established benchmarks in the literature. We propose to address this problem, framing motif prediction as an extension of subgraph frequency estimation. Our approach formulates motif estimation as a multitarget regression problem, optimising for interpretability and improving stability and scalability on large graphs. We validate our method using a large synthetic dataset generated by graph generators that mimic real-world data, and further test it on real-world graphs. Our experiments reveal that 1-WL limited models trained on synthetic data struggle to predict accurately motif profiles of real-world networks. However, apart from their reasonable performance within synthetic data, they can generalise to approximate the graph generation processes of real-world networks by comparing their predicted motif profiles with the ones originating from synthetic data. This first study on GNN-based motif prediction sets a benchmark and should open pathways for further developing the connection between motif profiles and subgraph frequency from a graph representation learning perspective.

Decision: reject
Reviewer scores: 3, 3, 1, 3, 3

Reviews and discussion:
<thread>
creation date:
1730298197563

thread_type:
official_review

<thread_object>
creator: reviewer_qmx2

<content>
summary:
The paper proposes a framework to extract network motifs, i.e., subgraph patterns that have some kind of significance, with graph neural networks. They formulate the task as a multitarget regression problem, where the targets are the significance scores of the (fixed) pattern graphs. The authors also provide a dataset of synthetic graphs that contain specific types of motifs/patterns.
In a nutshell, the topic is very interesting but I believe that the contributions of this paper are too limited for ICLR.

strengths:
- the motif mining problem is a very relevant task, that has multiple applications in computational chemistry as well as social network analysis. Moreover, the approach proposed by the authors, albeit not very novel, is reasonable and seemingly effective.
- The code to generate the large and diverse dataset of synthetic graphs created by the authors could be useful for subsequent articles on motif discovery.

weaknesses:
- The idea is not particularly novel, as the model seems to be (although the description is not very clear) just a GNN trained to regress a vector of significance values for a set of patterns of interest.
- The model can only obtain the significance of a fixed and pre-determined set of patterns, which limits the applicability of the method. In particular, the authors focus on unlabeled graphs of size 3 and 4. In practice, this is not ideal, as node labels carry a lot of information (e.g., in molecules, unlabeled patterns have little meaning, while labeled patterns can identify functional groups). Since the number of labeled patterns grows very fast, one could train the model only for a small fraction of them, and most of the subgraph pattern queries would not be able to be answered by the proposed model. If the model was able to learn the interesting motifs directly, the model could be much more useful.
- The authors give an unclear discussion in Section 4.2 of the relation between the ability of GNNs to count subgraphs and their task, but the explanation of why 1-WL MPNNs are sufficient for the motif mining task is not satisfactory and vague (“MPNNs remain highly valuable and find numerous practical applications in real-world scenarios”). It would be helpful if the authors provided proof of their statements or at least some experimental evidence.
- The experimental results are not only unsatisfactory (see point below), but they are also very hard to understand (e.g., I can’t understand the results in Table 1). The definition of “correct” and “incorrect” is unclear, and should be clarified and formalized better.
- The model has performance on real-world data that is close to the one of a model guessing at random and is much worse than the results on the synthetic data. This is a severe limitation to the applicability of the model to any real word task.
- Overall, the paper feels unpolished. Many statements are too vague or unclear. See some of my questions below.

#### Minor remarks:
- line 491: you have an extra comma.
- I appreciate that the authors provide the code to generate the synthetic datasets, but it is unclear whether a precomputed version is available for download.

questions:
- line 196: “Thus, we start with a vector of Z-scores”. You mean that the vector is your ground-truth label? This is unclear
- the paragraph on “Correct predictions, line 340” is very unclear to me. Can you please elaborate on your metrics?
- line 458: “due to failing to approximate an injective function or because the bound does not work well in practical scenarios.” Which bound are you referring to? This needs further elaboration.
- which null model are you using to generate the ground truth significances? I can’t find this in the paper.
- what is the “margin of error” that you mention?
- Do you have any insights on how to obtain better performance on real world data?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730344276577

thread_type:
official_review

<thread_object>
creator: reviewer_uysj

<content>
summary:
This paper tackles the challenge of predicting network motifs using Graph Neural Networks (GNNs). Given the known expressiveness limitations of GNNs, the authors reframe motif estimation as a multitarget regression task, where curated regression targets are assigned to each input graph. This method is validated on a large, diverse synthetic dataset. The study reveals that 1-WL-limited models trained on synthetic data struggle to generalize effectively to more complex, real-world networks.

strengths:
- This paper tackles an important and challenging problem of using GNNs for network motif estimation.

weaknesses:
- The proposed workaround—framing motif prediction as a multitarget regression task instead of directly predicting network motifs—relies heavily on heuristics and lacks sufficient motivation. Neither theoretical justification nor empirical evidence is provided to explain why altering the task would enable GNNs to perform better. For example, the statement in line 275, "We might have made the problem easier (or harder) than substructure counting," adds to the ambiguity surrounding the authors’ approach.

- As a heuristic-based study, the experiments are restricted to synthetic data, limiting the findings’ relevance to practical applications in complex real-world networks.

- While acknowledging the inherent limitations of GNNs, the authors overlook recent approaches leveraging large language models for classical graph problems like subgraph counting (e.g., [1]). Such methods, despite their own limitations, have shown performance improvements over GNNs but are neither cited nor compared here.

- Limited backbone choices: Only SAGE and GIN are used as backbones, while more expressive GNN models are not included (see, e.g., [2–4]).

[1] Understanding Transformer Reasoning Capabilities via Graph Algorithms.

[2] From stars to subgraphs: Uplifting any GNN with local structure awareness.

[3] Building powerful and equivariant graph neural networks with structural message-passing.

[4] Understanding and extending subgraph gnns by rethinking their symmetries.

questions:
Aforementioned in weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730568161759

thread_type:
official_review

<thread_object>
creator: reviewer_dukg

<content>
summary:
The paper proposes a method that frames motif estimation as a multitarget regression problem, which enhances interpretability and scalability for large graphs. The findings indicate that while models trained on synthetic data perform reasonably well, they struggle with real-world networks, highlighting a gap in generalization.

strengths:
1. The paper presents a unique formulation of motif estimation as a multitarget regression problem.
2. The paper sets a benchmark for future research in the field.

weaknesses:
1. The introduction section requires significant improvement, as it contains poorly defined terms and vague sentences. For instance:
In line 40, the phrase “what is a good network model for protein-protein interactions” lacks clarity. The authors may have intended to ask which architecture is preferred for this purpose. Additionally, the term "control networks" in line 42 is not clearly defined.
The phrase “very hard computational task” in line 43 is not professionally articulated. The term "very" is ambiguous; it would be more precise to state that the task is NP-hard.
The statement in lines 46-48 lacks supporting references, making the claim questionable. Additionally, phrases such as “typically do not give very interpretable results” are vague. What exactly is meant by “very interpretable”? This concept requires clearer definition and explanation.
Lines 49-52, which aim to outline the main contributions of the paper, are overly vague. The term “interpretable scores” needs further clarification. In the context of motif discovery, what does “score” refer to? Furthermore, the phrase “ensuring the possibility of further insight into the conclusions obtained” is unclear; which conclusions are being referred to?
Line 43 states, “Additionally, our method is robust and versatile, capable of operating effectively on graphs of any size.” The term "robust" is ambiguous in this context, and since many graph neural networks (GNNs) can operate on graphs of varying sizes, this statement does not clearly highlight the uniqueness of the authors' approach.
The sentence in line 53, “Knowing how difficult it is to obtain a high volume of real-world graph datasets that have both high quality and variety,” lacks supporting references, which undermines the claim.
Finally, lines 62-63 are poorly constructed: “We make available a large diverse synthetic dataset in terms of graph topology and motif significance-profile generated with 23 synthetic generators.” This statement could benefit from clearer phrasing and more specificity regarding what is meant by “motif significance-profile.”
More vague and poorly written lines: 192-193. 
Overall, the introduction requires substantial revision for clarity, precision, and supporting evidence.


2. The motivation for the proposed method is unclear, primarily due to the lack of references supporting the claims made in the introduction (lines 46-48). Additionally, Section 3.2 outlines numerous methods for detecting substructures and motifs but fails to address their limitations or specify how the proposed method intends to resolve these issues.

3. The structure of the paper could be enhanced for better clarity and coherence. For example, dedicating an entire section (Section 2) to preliminaries that consists of only four lines seems excessive, especially since these preliminaries are only referenced in Section 4. This placement raises questions about its necessity. Additionally, the title of Section 4, “INITIAL PROBLEM DESCRIPTION,” is misleading, as the majority of the section focuses on the proposed method rather than outlining the problem. Furthermore, lines 180-188 appear to contain preliminary information; starting a section with such lines without appropriate context is unprofessional and detracts from the overall readability of the paper.

4. Ultimately, the method is limited to small graphs of sizes 3 and 4, which restricts its overall contribution. Additionally, there is a lack of explanation regarding why existing approaches fail to detect such graphs, as previously mentioned in comment 2.

5. While the authors assert that interpretability is one of the main contributions of the paper in the abstract and introduction, the topic is not addressed further, nor is there any demonstration of how the method achieves interpretability. In the context of explainable artificial intelligence (XAI), which emphasizes transparent, white-box models, it is unclear how the proposed approach qualifies as interpretable. Additionally, the paper fails to establish how their method offers enhanced interpretability compared to existing approaches.

6.The paper does not provide any comparisons to existing approaches, which is a significant oversight. Without such comparisons, it is difficult to assess the effectiveness and advantages of the proposed method in relation to established techniques. Including a comparative analysis would enhance the paper's contributions and provide clearer context for the claims made about the method's performance and interpretability

questions:
1. What is the motivation behind the proposed method? Specifically, what problems associated with existing approaches does it address, particularly in relation to the methods discussed in Section 3.2?
2.The method focuses on small graphs of sizes 3 and 4. What are the implications of this limitation for the broader applicability of your approach
3.Can you provide more insight into the limitations of existing methods for detecting small graphs? What specific challenges do they face that your method aims to address?
4.How does your method enhance interpretability compared to existing approaches? Can you provide specific examples or references to studies that illustrate the limitations of current methods in this regard?
5.I kindly request that you include a comparative analysis of your proposed method against existing approaches.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721561548

thread_type:
official_review

<thread_object>
creator: reviewer_lucz

<content>
summary:
The paper proposes a GNN model for estimating the frequency of a set of subgraphs (called motifs) in a given graph.
The described estimator predicts the standardized occurrence counts (Z-counts) $z_i$ for subgraph H_i in a target graph $\mathcal{G}$ relative to a set of reference graphs $\mathcal{G}_\mathrm{NULL}$, i.e., the model is trained to predict how many standard deviations the occurrence count of H_i in $\mathcal{G}$ is above or below that in G_NULL.

The proposed approach normalizes the Z-counts to the interval $[-1, 1]$. Additionally, the Z-count vector $z$ is normalized via the Euclidean norm to obtain a so-called *significance profile* vector $s$.
The model is trained by minimizing the MSE between the true and the predicted significance profiles of synthetically generated training graphs.

The model is evaluated by comparing the significance profile MSEs on unseen synthetic and real-world graphs. The proposed approach performs well on the synthetic validation and test data. However, on real-world graphs, the estimator performs significantly worse.

strengths:
The proposed approach is well motivated and contextualized by giving a good overview of the strength and weaknesses of prior work in the field.

The idea of predicting Z-scores instead of absolute occurrences to circumvent potential generalization  issues with directly predicting absolute counts which might grow super-exponentially is convincing. 

Additionally, the relations between absolute counts and significance profile estimation described in Section 4.2 raise interesting questions about the possibility of difficulty classes for different counting problems wrt. different NULL models.

The analysis of the reported empirical results is thorough with many details being provided in the supplement.

weaknesses:
As described by the authors, the proposed approach does not appear to produce satisfactory results on real world data. However, since "negative" results can also be of interest, I will not focus on that here.

First, while theoretically interesting, I found it difficult to assess to which degree the proposed approach might be useful for practical purposes, mainly due to the following reasons:
1. The approach is only compared to itself. As described in Section 3, there has been prior work on substructure counting with GNNs. An empirical comparison to another counting model (e.g., [1]), would have been helpful.
2. The performance of the estimator is only evaluated wrt. the MSE of the predicted significance profiles. While interesting, it is unclear to me to which extent those significance profiles are useful in downstream tasks. Why was the quality of the predicted Z-scores or possibly the absolute occurrence counts not evaluated?
3. Related to my previous point, it would have been interesting to highlight potential applications for the proposed approach in the experiments, e.g., via a case study showcasing how the estimator might be used in practice.

Second, I found the motivation for using significance profiles at all to be lacking.
In Section 4.1 the authors write that this "imposes a mathematical interconnectivity between the Z-scores"; no explanation as to why such a constraint is desirable is given.
For induced subgraphs one can argue that an increase of one subgraph of a certain size might lead to a decrease in occurrence of other subgraphs of that size, assuming that the set of motifs contains **all** subgraphs of a given size.
However, since this is a constraint on the sum of the Z-scores, L1 normalization instead of the used Euclidean norm would have been appropriate.
Can you elaborate on why you chose to use L2-normalized significance profiles and discuss the advantages (and potential disadvantages) of this choice?

Third, in Section 7.2 conjecture that the GNN models used in the estimator might not be expressive enough to properly learn occurrence counts in the evaluated setting.
Given this observation, it is unclear why the authors did not also evaluate more expressive GNN models.
In Section 4.2, they mention that more expressive models have high computational complexity; however, there are a number of higher-order GNN architectures with different performance characteristics [2,3,4], e.g., 2-FWL approximations with a tunable complexity parameter [3].
Even if all currently proposed higher-order approaches were infeasible for the intended setting, a small scale evaluation of more expressive models would have been interesting.
Could you run such an experiment, e.g., using one of the mentioned higher-order GNN approaches?

Last, I have a few minor comments regarding the presentation:
- Figure 1 is difficult to parse by itself; more specifically, repeating the x-labels on all six subplots and adding a meaningful y-axis label would be helpful.
- In Table 1, the distinction between SAGE and GIN using underline and italics is unnecessarily hard to parse; adding an explicit heading to the already existing columns for both would be better.
- On page 2, line 54, I found the choice of the word "myriad" to be vague and misleading, when the number of used generators is "just" 23.
- On page 6, line 304: Grammar. "being those" should read "those being".

---
[1] Chen, Z., Chen, L., Villar, S., Bruna, J.: Can graph neural networks count substructures? In: Proceedings of the 34th International Conference on Neural Information Processing Systems. pp. 10383–10395. Curran Associates Inc., Red Hook, NY, USA (2020).

[2] Maron, H. et al.: Provably Powerful Graph Networks. arXiv. (2019).

[3] Damke, C. et al.: A Novel Higher-order Weisfeiler-Lehman Graph Convolution. In: Proceedings of The 12th Asian Conference on Machine Learning. pp. 49–64 PMLR (2020).

[4] Tahmasebi, B. et al.: Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results, [http://arxiv.org/abs/2012.03174](http://arxiv.org/abs/2012.03174), (2021). [https://doi.org/10.48550/arXiv.2012.03174](https://doi.org/10.48550/arXiv.2012.03174).

questions:
A few questions were already raised in the weaknesses, namely:
- Why were no other occurrence estimations approaches used for comparison in the evaluation?
- Which downstream applications do you envision for your proposed approach?
- Why the focus on significance profiles instead of Z-scores?
- Why are the significance profiles normalized using L2 instead of L1?

Additionally, out of curiosity, I would like to ask why the set of significance values specified in Section 5 (line 305) is as described. The explanation for why $\frac{1}{\sqrt{2}}$ appears is understandable, but why are 0 and 1 also part of the set and why is -1 not in it?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730835905376

thread_type:
official_review

<thread_object>
creator: reviewer_nuur

<content>
summary:
The authors constructed a large synthetic dataset to test the motif discovery ability of MPNNs, and showed in general that MPNNs do not generalize well beyond synthetic dataset.

strengths:
The authors formulated the motif discovery into a multitarget regression problem on normalized z-scores. And have done an empirical study on a large synthetic dataset to understand the boundaries of MPNNs on motif discovery. The problem they are trying to understand is close to many real world scientific questions (such as motifs in biology).

weaknesses:
I found the conclusions in the paper a bit weaker and satisfying. 

The authors spent some time explaining the differences between subgraph counting and motif discovery. The latter can be easier or harder than the subgraph counter depending on the null hypothesis construction. Then the authors tried to answer three key questions (line 402-404), and found the model seems to learn the graph generators and perform better on intra-generator graphs. Following that, the model trained on synthetic data does not generalize well onto real-world graphs. Such findings are pretty expected and I wonder if the readers would learn more from the study.

questions:
The authors mentioned normalizing the z-scores imposes a “mathematical interconnectivity” and further supports multi-target regression tasks, adding an additional layer of interdependence. I wonder if the authors could elaborate on how such a simple constraint has a meaningful impact on the model. Shouldn’t it be a trivial task to learn?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732449171249

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We express our sincere appreciation to the reviewers for their invaluable insights. 

We also appreciate the reviewers acknowledging that our work “(...) tackles an important and challenging problem (...)” (uysJ), it is “(...) close to many real world scientific questions (...)” (nUUR), and uses a “(...) unique formulation” (DuKG). 
We value the recognition by the reviewers of our strategy being “(...) reasonable and seemingly effective.” (QMx2), “(...) well motivated and contextualized (...)” (LUCZ), and the usage of “(...) large synthetic dataset (...)” (nUUR) that “(...) could be useful for subsequent articles on motif discovery.” (QMx2). Finally, we deeply value the recognition that our paper “(...) raises interesting questions (...)” (LUCZ) regarding motif discovery using GNNs.

However, despite some positive comments, after careful consideration, an initial round of discussions, and preliminary evaluations, we have determined that we are unable to submit a revised manuscript that fully addresses the reviewers' many important concerns. Since we cannot adhere to the standards of the conference in the coming timeline, we will formally withdraw the paper in the coming days. Nevertheless, we have provided responses to each review to clarify any potential misunderstandings, answer the questions of the reviewers and to ensure that the paper's review is well-positioned for future endeavours. If the reviewers want to make extra comments, we will promptly respond to them to the best of our ability. 

Thank you once again for your time, consideration, and commitment.
</content>
</thread_object>

</thread>


Metareview: