Learning to Count Isomorphisms with Graph Neural Networks
Subgraph isomorphism counting is an important problem on graphs, as many
graph-based tasks exploit recurring subgraph patterns. Classical methods
usually boil down to a backtracking framework that needs to navigate a huge
search space with prohibitive computational costs. Some recent studies resort
to graph neural networks (GNNs) to learn a low-dimensional representation for
both the query and input graphs, in order to predict the number of subgraph
isomorphisms on the input graph. However, typical GNNs employ a node-centric
message passing scheme that receives and aggregates messages on nodes, which is
inadequate in complex structure matching for isomorphism counting. Moreover, on
an input graph, the space of possible query graphs is enormous, and different
parts of the input graph will be triggered to match different queries. Thus,
expecting a fixed representation of the input graph to match diversely
structured query graphs is unrealistic. In this paper, we propose a novel GNN
called Count-GNN for subgraph isomorphism counting, to deal with the above
challenges. At the edge level, given that an edge is an atomic unit of encoding
graph structures, we propose an edge-centric message passing scheme, where
messages on edges are propagated and aggregated based on the edge adjacency to
preserve fine-grained structural information. At the graph level, we modulate
the input graph representation conditioned on the query, so that the input
graph can be adapted to each query individually to improve their matching.
Finally, we conduct extensive experiments on a number of benchmark datasets to
demonstrate the superior performance of Count-GNN.
Xingtong Yu, Zemin Liu, Yuan Fang, Xinming Zhang
# Learning to Count Isomorphisms with Graph Neural Networks

###### Abstract

Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort to graph neural networks (GNNs) to learn a low-dimensional representation for both the query and input graphs, in order to predict the number of subgraph isomorphisms on the input graph. However, typical GNNs employ a node-centric message passing scheme that receives and aggregates messages on nodes, which is inadequate in complex structure matching for isomorphism counting. Moreover, on an input graph, the space of possible query graphs is enormous, and different parts of the input graph will be triggered to match different queries. Thus, expecting a fixed representation of the input graph to match diversely structured query graphs is unrealistic. In this paper, we propose a novel GNN called Count-GNN for subgraph isomorphism counting, to deal with the above challenges. At the edge level, given that an edge is an atomic unit of encoding graph structures, we propose an _edge-centric message passing_ scheme, where messages on edges are propagated and aggregated based on the edge adjacency to preserve fine-grained structural information. At the graph level, we _modulate the input graph representation_ conditioned on the query, so that the input graph can be adapted to each query individually to improve their matching. Finally, we conduct extensive experiments on a number of benchmark datasets to demonstrate the superior performance of Count-GNN.

1 University of Science and Technology of China, China

2 National University of Singapore, Singapore

3 Singapore Management University, Singapore

yxt95@mail.ustc.edu.cn, zemiliu@nus.edu.sg, yfang@smu.edu.sg, ximming@ustc.edu.cn

## 1 Introduction

Research in network science and graph mining often finds and exploits recurring subgraph patterns on an input graph. For example, on a protein network, we could query for the hydroxy groups which consist of one oxygen atom covalently bonded to one hydrogen atom; on a social network, we could query for potential families in which several users form a clique and two of them are working and the rest are studying. These queries essentially describe a subgraph pattern that repeatedly occurs on different parts of an input graph, which expresses certain semantics such as the hydroxy groups or families. These subgraph patterns are also known as network motifs on homogeneous graphs [12] or meta-structures on heterogeneous graphs [23, 24]. To leverage their expressiveness, more sophisticated graph models [13, 25, 26, 27] have also been designed to incorporate motifs or meta-structures.

The need for subgraph patterns in graph-based tasks and models leads to a high demand of _subgraph isomorphism counting_[12]. Classical methods usually employ search-based algorithms such as backtracking [11, 10, 1] to exhaustively detect the isomorphisms and return an exact count. However, their computational costs are often excessive given that the detection problem is NP-complete and the counting form is #P-complete [10]. With the rise of graph neural networks (GNNs) [26], some recent approaches for subgraph isomorphism counting also leverage on the powerful graph representations from GNNs [12, 13, 14]. They generally employ GNNs to embed the queries and input graphs into low-dimensional vectors, which are further fed into a counter module to predict the approximate number of isomorphisms on the input graph. Compared to classical approaches, they can significantly save computational resources at the expense of approximation, providing a useful trade-off between accuracy and cost since many applications do not necessarily need an exact count.

However, previous GNN-based isomorphism counting models adopt a node-centric message-passing scheme, which propagates and aggregates messages on nodes. While this scheme is effective for node-oriented tasks, it falls short of matching complex structures for isomorphism counting. In particular, they rely on message aggregation to generate representations centering on nodes, failing to explicitly and fundamentally capture the complex interactions among nodes. Thus, as the first challenge, _how do we capture fine-grained structural information_ beyond node-centric GNNs? Moreover, on an input graph, the space of possible query graphs is enormous. Different queries are often characterized by distinct structures that match with different parts of the input graph. A fixed graph representation to match with
all possible queries is likely to underperform. Thus, as the second challenge, _how do we adapt the input graph to each query individually_, in order to improve the matching of specific structures in every query?

In this paper, we propose a novel model called Count-GNN for approximate subgraph isomorphism counting, which copes with the above challenges from both the edge and graph perspectives. To be more specific, at the edge level, Count-GNN is built upon an _edge-centric_ GNN that propagates and aggregates messages on and for edges based on the edge adjacency, as shown in Fig. 1(a). Given that edges constitute the atomic unit of graph structures, any subgraph is composed of one or more edge chains. Thus, treating edges as first-class citizens can better capture fine-grained structural information. Theoretically, our proposed edge-centric GNN model can be regarded as a generalization of node-centric GNNs, with provably stronger expressive power than node-centric GNNs. At the graph level, Count-GNN resorts to a modulation mechanism [14] by adapting the input graph representation to each query graph, as shown in Fig. 1(b). As a result, the input graph can be tailored to each individual query with varying structures. Coupling the two perspectives, Count-GNN is able to precisely match complex structures between the input graph and structurally diverse queries.

To summarize, our contributions are three-fold. (1) We propose a novel model Count-GNN that capitalizes on edge-centric aggregation to encode fine-grained structural information, which is more expressive than node-centric aggregation in theory. (2) Moreover, we design a query-conditioned graph modulation in Count-GNN, to adapt structure matching to different queries from the graph perspective. (3) Extensive experiments on several benchmark datasets demonstrate that Count-GNN can significantly outperform state-of-the-art GNN-based models for isomorphism counting.

## 2 Related Work

We present the most related studies here, while leaving the rest to Appendix G due to the space limitation.

Graphs usually entail abundant local structures to depict particular semantics, which gives rise to the importance of subgraph isomorphism counting [10]. To solve this problem, most traditional methods resort to backtracking [10, 11, 12]. Although they can obtain the exact counts, the search space usually grows intractably as graph size increases. In fact, subgraph isomorphism counting is a #P-complete problem [10]. Subsequently, several approaches [13, 14] are proposed to utilize some constraints to reduce the search space, and others [15] try to filter out infeasible graphs to speed up the backtracking process. Another line of approaches [1, 16] rely on the color coding for subgraph isomorphism counting in polynomial time. They are usually fixed-parameter tractable and can only be employed for some limited subcases. Other studies perform count estimation [18, 19, 20], such as in the setting where access to the entire network is prohibitively expensive [18], or using the counts of smaller patterns to estimate the counts for larger ones [19]. However, these attempts still face high computational costs.

Recently, a few studies [15, 17] propose to address subgraph isomorphism counting from the perspective of machining learning. One study [15] proposes to incorporate several existing pattern extraction mechanisms such as CNN [11], GRU [12] and GNNs [21] on both query graphs and input graphs to exploit their structural match, which is then followed by a counter module to predict the number of isomorphisms. Another work [17] analyzes the ability of GNNs in detecting subgraph isomorphism, and proposes a Local Relational Pooling model based on the permutations of walks according to breadth-first search to count certain queries on graphs. However, they need to learn a new model for each query graph, limiting their practical application. Compared to traditional methods, these machine learning-based models can usually approximate the counts reasonably well, and at the same time significantly save computational resources and time, providing a practical trade-off between accuracy and cost. However, these approaches only adopt node-centric GNNs, which limit their ability to capture finer-grained structural information.

There also exist a few recent GNNs based on edge-centric aggregation [13, 14], node-centric aggregation with the assistance of edge features [16, 17, 18], or both node- and edge-centric aggregation at the same time [15]. Except DMPNN [15], they are not specifically devised for subgraph isomorphism counting. In particular, they all lack the key module of structural matching between query and input graphs. Besides, the edge-centric approaches do not theoretically justify their enhanced expressive power compared to the node-centric counterparts.

## 3 Problem Formulation

A _graph_\(\mathcal{G}=(V_{\mathcal{G}},E_{\mathcal{G}})\) is defined by a set of nodes \(V_{\mathcal{G}}\), and a set of edges \(E_{\mathcal{G}}\) between the nodes. In our study, we consider the general case of directed edges, where an undirected edge can be treated as two directed edges in opposite directions. We further consider _labeled_ graphs (also known as heterogeneous graphs), in which there exists a node label function \(\ell:V_{\mathcal{G}}\to L\) and an edge label function \(\ell^{\prime}:E_{\mathcal{G}}\to L^{\prime}\), where

Figure 1: Illustration of Count-GNN.
\(L\) and \(L^{\prime}\) denote the set of labels on nodes and edges, respectively. A graph \(\mathcal{S}=(V_{\mathcal{S}},E_{\mathcal{S}})\) is a _subgraph_ of \(\mathcal{G}\), written as \(\mathcal{S}\subset\mathcal{G}\), if and only if \(V_{\mathcal{S}}\subseteq V_{\mathcal{G}}\) and \(E_{\mathcal{S}}\subseteq E_{\mathcal{G}}\).

Next, we present the definition of subgraph isomorphism on a labeled graph.

**Definition 1** (Labeled Subgraph Isomorphism).: _Consider a subgraph \(\mathcal{S}\) of some input graph, and a query graph \(\mathcal{Q}\). \(\mathcal{S}\) is isomorphic to \(\mathcal{Q}\), written as \(\mathcal{S}\simeq\mathcal{Q}\), if there exists a bijection between their nodes, \(\psi:V_{\mathcal{S}}\to V_{\mathcal{Q}}\), such that_

* \(\forall v\in V_{\mathcal{S}}\)_,_ \(\ell(v)=\ell(\psi(v))\)_;_
* \(\forall e=\langle u,v\rangle\in E_{\mathcal{S}}\)_, it must hold that_ \(e^{\prime}=\langle\psi(u),\psi(v)\rangle\in E_{\mathcal{Q}}\) _and_ \(\ell^{\prime}(e)=\ell^{\prime}(e^{\prime})\)_._ 

In the problem of _subgraph isomorphism counting_, we are given a query graph \(\mathcal{Q}\) and an input graph \(\mathcal{G}\). We aim to predict \(n(\mathcal{Q},\mathcal{G})\), the number of subgraphs on \(\mathcal{G}\) which are isomorphic to \(\mathcal{Q}\), _i.e._, the cardinality of the set \(\{\mathcal{S}|\mathcal{S}\subseteq\mathcal{G},\mathcal{S}\simeq\mathcal{Q}\}\). Note that this is a non-trivial #P-complete problem [1]. In practice, the query \(\mathcal{Q}\) usually has a much smaller size than the input graph \(\mathcal{G}\), _i.e._, \(|V_{\mathcal{Q}}|\ll|V_{\mathcal{G}}|\) and \(|E_{\mathcal{Q}}|\ll|E_{\mathcal{G}}|\), leading to a huge search space and computational cost.

## 4 Proposed Model: Count-GNN

In this section, we present the overall framework of Count-GNN first, followed by individual modules.

### Overall Framework

We give an overview of the proposed Count-GNN in Fig. 2. Consider some query graphs and an input graph in Fig. 2(a). On both the query and input graphs, we first conduct edge-centric aggregation in which messages on edges are propagated to and aggregated for each edge based on the edge adjacency, as shown in Fig. 2(b). This module targets at the edge level, and enables us to learn edge-centric representations for both input graphs and queries that capture their fine-grained structural information for better structure matching. Furthermore, to be able to match diverse queries with distinct structures, the edge representations of the input graph are modulated w.r.t. each query, as shown in Fig. 2(c). The query-conditioned edge representations then undergo a readout operation to fuse into a query-conditioned whole-graph representation for the input graph. The module targets at the graph level, and enables us to adapt the input graph to each query individually to improve the matching of specific structures in each query. Finally, as shown in Fig. 2(d), a counter module is applied to predict the isomorphism counting on the input graph for a particular query, forming the overall objective.

### Edge-Centric Aggregation

Typical GNNs [11, 12, 13] and GNN-based isomorphism counting models [13, 14] resort to the key mechanism of node-centric message passing, in which each node receives and aggregates messages from its neighboring nodes. For the problem of subgraph isomorphism counting, it is crucial to capture fine-grained structural information for more precise structure matching between the query and input graph. Consequently, we exploit edge-centric message passing, in which each edge receives and aggregates messages from adjacent edges. The edge-centric GNN captures structural information in an explicit and fundamental manner, given that edges represent the atomic unit of graph structures.

More concretely, we learn a representation vector for each edge by propagating messages on edges. A message can be an input feature vector of the edge in the input layer of the GNN, or an intermediate embedding vector of the edge in subsequent layers. Specifically, given a directed edge \(e=\langle u,v\rangle\) on a graph (either an input or query graph), we initialize its message as a \(d_{0}\)-dimensional vector

\[\mathbf{h}^{0}_{\langle u,v\rangle}=\mathbf{x}_{u}\parallel\mathbf{x}_{\langle u,v\rangle}\parallel\mathbf{x}_{v}\in\mathbb{R}^{d_{0}}, \tag{1}\]

where \(\mathbf{x}_{*}\) encodes the input features of the corresponding nodes or edges and \(\parallel\) is the concatenation operator. In general, \(\mathbf{h}^{0}_{\langle u,v\rangle}\neq\mathbf{h}^{0}_{\langle v,u\rangle}\) for directed edges. Note that, in the absence of input features, we can employ one-hot encoding as the feature vector; it is also possible to employ additional embedding layers to further transform the input features into initial messages.

Given the initial messages, we devise an edge-centric GNN layer, in which each edge receives and aggregates messages along the directed edges. The edge-centric message passing can be made recursive by stacking multiple layers. Formally, in the \(l\)-th layer, the message on a directed edge \(\langle u,v\rangle\), _i.e._, \(\mathbf{h}^{l}_{\langle u,v\rangle}\in\mathbb{R}^{d_{l}}\), is updated as

\[\mathbf{h}^{l}_{\langle u,v\rangle}=\sigma(\mathbf{W}^{l}\mathbf{h}^{l-1}_{ \langle u,v\rangle}+\mathbf{U}^{l}\mathbf{h}^{l-1}_{\langle,u\rangle}+\mathbf{ b}^{l}), \tag{2}\]

where \(\mathbf{W}^{l}\), \(\mathbf{U}^{l}\in\mathbb{R}^{d_{l}\times d_{l-1}}\) are learnable weight matrices, \(\mathbf{b}^{l}\in\mathbb{R}^{d_{l}}\) is a learnable bias vector, and \(\sigma\) is an activation function (we use LeakyReLU in the implementation). In addition, \(\mathbf{h}^{l-1}_{\langle,u\rangle}\in\mathbb{R}^{d_{l-1}}\) is the intermediate message aggregated from the preceding edges of \(\langle u,v\rangle\), _i.e._, edges incident on node \(u\) from other nodes, which can be materialized as

\[\mathbf{h}^{l-1}_{\langle,u\rangle}=\textsc{Aggr}(\{\mathbf{h}^{l-1}_{ \langle i,u\rangle}|\langle i,u\rangle\in E\}), \tag{3}\]

where \(E\) denotes the set of directed edges in the graph, and \(\textsc{Aggr}(\cdot)\) is an aggregation operator to aggregate messages from the preceding edges. We implement the aggregation operator as a simple mean, although more sophisticated approaches such as self-attention [15] and multi-layer perceptron [13] can also be employed. To boost the message passing, more advanced mechanisms can be imported into the layer-wise edge-centric aggregation, _e.g._, a residual [14] can be added to assist the message passing from previous layers to the current layer.

The above multi-layer edge-centric aggregation is applied to each query and input graph in a dataset. All query graphs share one set of GNN parameters (_i.e._, \(\mathbf{W}^{l},\mathbf{U}^{l},\mathbf{b}^{l}\)), while all input graphs share another set. On all graphs, the aggregated message on an edge \(e=\langle u,v\rangle\) in the last layer is taken as the representation vector of this edge, denoted as \(\mathbf{h}_{\langle u,v\rangle}\in\mathbb{R}^{d}\).
### Query-Conditioned Graph Modulation

Beyond the edge level, Count-GNN fuses the edge representations into a whole-graph representation to facilitate structure matching between query and input graphs.

**Query graph representation.** We employ a typical readout function [23, 14, 15] on a query graph, by aggregating all edge representations in the query. Given a query graph \(\mathcal{Q}\), its whole-graph representation is computed as

\[\mathbf{h}_{\mathcal{Q}}=\sigma(\mathbf{Q}\cdot\textsc{Aggr}(\{\mathbf{h}_{ \langle u,v\rangle}|\langle u,v\rangle\in E_{\mathcal{Q}}\})), \tag{4}\]

where \(\mathbf{Q}\in\mathbb{R}^{d\times d}\) is a learnable weight matrix shared by all query graphs, and we use sum for the aggregation. Intuitively, the query graph representation simply pools all edge representations together uniformly.

**Input graph representation.** To generate a whole-graph representation for the input graph, a straightforward way is to follow Eq. (4) by regarding all edges uniformly. However, for an input graph, the space of possible query graphs is enormous. In particular, different queries are often characterized by distinct structures, which implies that different parts of the input graph will be triggered to match different queries. Therefore, aggregating all edges in the input graph uniformly cannot retain sufficiently specific structural properties w.r.t. each query. In other words, using a fixed whole-graph representation for the input graph cannot tailor to each query well for effective structure matching. Thus, we propose to modulate the input graph conditioned on the query, to adapt the whole-graph representation of the input graph to each query. To this end, we leverage Feature-wise Linear Modulation (FiLM) [14, 15, 16] on the edge representations in the input graph, conditioned on the query, in order to retain query-specific structures. The modulation is essentially a scaling and shifting transformation to adapt the edge representations of the input graph to the query. Given an input graph \(\mathcal{G}\), for each edge \(e=\langle u,v\rangle\in E_{\mathcal{G}}\) we modulate its representation \(\mathbf{h}_{\langle u,v\rangle}\) into \(\tilde{\mathbf{h}}_{\langle u,v\rangle}\), as follows.

\[\tilde{\mathbf{h}}_{\langle u,v\rangle}=(\gamma_{\langle u,v\rangle}+\mathbf{ 1})\odot\mathbf{h}_{\langle u,v\rangle}+\beta_{\langle u,v\rangle}, \tag{5}\]

where \(\gamma_{\langle u,v\rangle}\) and \(\beta_{\langle u,v\rangle}\in\mathbb{R}^{d}\) are FiLM factors for scaling and shifting, respectively, \(\odot\) denotes the Hadamard product, and \(\mathbf{1}\in\mathbb{R}^{d}\) is a vector filled with ones to center the scaling factor around one. Note that the FiLM factors \(\gamma_{\langle u,v\rangle}\) and \(\beta_{\langle u,v\rangle}\) are not directly learnable, but are instead generated by a secondary network [16] conditioned on the original edge representation \(\mathbf{h}_{\langle u,v\rangle}\) and the query representation \(\mathbf{h}_{\mathcal{Q}}\). More specifically,

\[\gamma_{\langle u,v\rangle} =\sigma(\mathbf{W}_{\gamma}\mathbf{h}_{\langle u,v\rangle}+ \mathbf{U}_{\gamma}\mathbf{h}_{\mathcal{Q}}+\mathbf{b}_{\gamma}), \tag{6}\] \[\beta_{\langle u,v\rangle} =\sigma(\mathbf{W}_{\beta}\mathbf{h}_{\langle u,v\rangle}+ \mathbf{U}_{\beta}\mathbf{h}_{\mathcal{Q}}+\mathbf{b}_{\beta}), \tag{7}\]

where \(\mathbf{W}_{\gamma},\mathbf{U}_{\gamma},\mathbf{W}_{\beta},\mathbf{U}_{\beta} \in\mathbb{R}^{d\times d}\) are learnable weight matrices, and \(\mathbf{b}_{\gamma},\mathbf{b}_{\beta}\in\mathbb{R}^{d}\) are learnable bias vectors. The modulated edge representations can be further fused via a readout function, to generate a modulated whole-graph representation for the input graph, which is tailored toward each query to enable more precise matching between the input graph and query. Concretely, consider a query graph \(\mathcal{Q}\) and an input graph \(\mathcal{G}\). We formulate the \(\mathcal{Q}\)-conditioned representation for \(\mathcal{G}\), denoted \(\mathbf{h}_{\mathcal{G}}^{\mathcal{Q}}\in\mathbb{R}^{d}\), by aggregating the modulated edge representations of \(\mathcal{G}\) in the following.

\[\mathbf{h}_{\mathcal{G}}^{\mathcal{Q}}=\sigma(\mathbf{G}\cdot\textsc{Aggr}( \{\tilde{\mathbf{h}}_{\langle u,v\rangle}|\langle u,v\rangle\in E_{\mathcal{G }}\})), \tag{8}\]

where \(\mathbf{G}\in\mathbb{R}^{d\times d}\) is a learnable weight matrix shared by all input graphs, and we use sum for the aggregation.

### Counter Module and Overall Objective

With the whole-graph representations of the query and input graphs, we design a counter module to estimate the count of subgraph isomorphisms, and formulate the overall objective.

**Counter module.** We estimate the count of isomorphisms based on the structure matchability between the query and input graph. Given the query graph \(\mathcal{Q}\) and input graph \(\mathcal{G}\), we predict the number of subgraphs on \(\mathcal{G}\) which are isomorphic to \(\mathcal{Q}\) by

\[\hat{n}(\mathcal{Q},\mathcal{G})=\textsc{ReLU}(\mathbf{w}^{\top}\textsc{Match }(\mathbf{h}_{\mathcal{Q}},\mathbf{h}_{\mathcal{G}}^{\mathcal{Q}})+b), \tag{9}\]

where \(\textsc{Match}(\cdot,\cdot)\) outputs a \(d_{m}\)-dimensional vector to represent the matchability between its arguments, and \(\mathbf{w}\in\mathbb{R}^{d_{m}},b\in\mathbb{R}\) are the learnable weight vector and bias, respectively. Here a ReLU activation is used to ensure that the prediction is non-negative. Note that \(\textsc{Match}(\cdot,\cdot)\) can be any function--we adopt a fully connected layer (FCL) such that \(\textsc{Match}(\mathbf{x},\mathbf{y})=\textsc{FCL}(\mathbf{x}\parallel \mathbf{y}\parallel\mathbf{x}-\mathbf{y}\parallel\mathbf{x}\odot\mathbf{y})\).

Figure 2: Overall framework of Count-GNN.
**Overall objective.** Based on the counter module, we formulate the overall training loss. Assume a set of training triples \(\mathcal{T}=\{(\mathcal{Q}_{i},\mathcal{G}_{i},n_{i})\mid i=1,2,\ldots\}\), where \(n_{i}\) is the ground truth count for query \(\mathcal{Q}_{i}\) and input graph \(\mathcal{G}_{i}\). The ground truth can be evaluated by classical exact algorithms [13]. Subsequently, we minimize the following loss:

\[\frac{1}{|\mathcal{T}|}\sum_{(\mathcal{Q}_{i},\mathcal{G}_{i},n_{i})\in \mathcal{T}}|\hat{n}(\mathcal{Q}_{i},\mathcal{G}_{i})-n_{i}|+\lambda\mathcal{L }_{\text{FiLM}}+\mu\|\Theta\|_{2}^{2}, \tag{10}\]

where \(\mathcal{L}_{\text{FiLM}}\) is a regularizer on the FiLM factors and \(\|\Theta\|_{2}^{2}\) is a L2 regularizer on the model parameters, and \(\lambda,\mu\) are hyperparameters to control the weight of the regularizers. Specifically, the FiLM regularizer is designed to smooth the modulations to reduce overfitting, by encouraging less scaling and shifting as follows.

\[\mathcal{L}_{\text{FiLM}}=\sum_{(\mathcal{Q}_{i},\mathcal{G}_{i},n_{i})\in \mathcal{T}}\sum_{(u,v)\in E_{\mathcal{G}_{i}}}\|\gamma_{(u,v)}\|_{2}^{2}+\| \beta_{(u,v)}\|_{2}^{2}. \tag{11}\]

We also present the training algorithm and a complexity analysis in Appendix A.

### Theoretical Analysis of Count-GNN

The proposed Count-GNN capitalizes on edge-centric message passing, which is fundamentally more powerful than conventional node-centric counterparts. This conclusion can be theoretically shown by the below lemma and theorem.

**Lemma 1** (Generalization).: _Count-GNN can be reduced to a node-centric GNN, i.e., Count-GNN can be regarded as a generalization of the latter. _

In short, Count-GNN can be reduced to a node-centric GNN by removing some input information and merging some edge representations. This demonstrates that Count-GNN is at least as powerful as the node-centric GNNs. We present the proof of Lemma 1 in Appendix B.

**Theorem 1** (Expressiveness).: _Count-GNN is more powerful than node-centric GNNs, which means (i) for any two non-isomorphic graphs that can be distinguished by a node-centric GNN, they can also be distinguished by Count-GNN; and (ii) there exists two non-isomorphic graphs that can be distinguished by Count-GNN but not by a node-centric GNN. _

Intuitively, edge-centric GNNs are capable of capturing fine-grained structural information, as any node can be viewed as a collapse of edges around the node. Therefore, by treating edges as the first-class citizens, Count-GNN becomes more powerful. The proof of Theorem 1 can be found in Appendix B.

## 5 Experiments

In this section, we empirically evaluate the proposed model Count-GNN in comparison to the state of the art.

### Experimental Setup

**Datasets.** We conduct the evaluation on four datasets shown in Table 1. In particular, _SMALL_ and _LARGE_ are two synthetic datasets, which are generated by the query and graph generators presented by a previous study [15]. On the other hand, _MUTAG_[11] and _OGBPPA_[12] are two real-world datasets. In particular, MUTAG consists of 188 nitro compound graphs, and OGB-PPA consists of 6,000 protein association graphs. While graphs in MUTAG and OGB-PPA are taken as our input graphs, we use the query generator [15] to generate the query graphs. As each dataset consists of multiple query and input graphs, we couple each query graph \(\mathcal{Q}\) with an input graph \(\mathcal{G}\) to form a training triple \((\mathcal{Q},\mathcal{G},n)\) with \(n\) denoting the ground-truth count given by an exact algorithm VF2 [13]. More details of the datasets are given in Appendix C.

**Baselines.** We compare Count-GNN with the state-of-the-art approaches in two main categories. We provide further details and settings for the baselines in Appendix D.

(1) _Conventional GNNs_: GCN [12], GAT [21], GraphSAGE [10], DPGCNN [14], GIN [15], and DiffPool [16]. They capitalize on node-centric message passing, followed by a readout function to obtain the whole-graph representation. Except DiffPool which utilizes a specialized hierarchical readout, we employ a sum pooling over the node representations for the readout in other GNNs.

(2) _GNN-based isomorphism counting models_, including four variants proposed by [15], namely RGCNN, RGCN-Sum, RGIN-DN, RGIN-Sum, as well as LRP [17] and DMPNN-LRP [15], a better variant of DMPNN. They are purposely designed GNNs for subgraph isomorphism counting, relying on different GNNs such as RGCN [10], RGIN [15] and local relational pooling [1]) for node representation learning, followed by a specialized readout suited for isomorphism matching. In particular, the two variants RGCN-DN and RGIN-DN utilize DiamNet [15], whereas RGCN-Sum and RGIN-Sum utilize the simple sum-pooling.

Finally, we also include a classical approach VF2 [13] and a state-of-the-art approach Pere

\begin{table}
\begin{tabular}{l|r r r r} \hline \hline  & SMALL & LARGE & MUTAG & OGB-PPA \\ \hline \# Queries & 75 & 122 & 24 & 12 \\ \# Graphs & 6,790 & 3,240 & 188 & 6,000 \\ \# Triples & 448,140 & 395,280 & 4,512 & 57,940 \\ \(\mathsf{Avg}(|\mathcal{Q}_{\mathcal{Q}}|)\) & 5.20 & 8.43 & 3.50 & 4.50 \\ \(\mathsf{Avg}(|E_{\mathcal{Q}}|)\) & 6.80 & 12.23 & 2.50 & 4.75 \\ \(\mathsf{Avg}(|V_{\mathcal{G}}|)\) & 32.62 & 239.94 & 17.93 & 152.75 \\ \(\mathsf{Avg}(|E_{\mathcal{Q}}|)\) & 76.34 & 559.68 & 39.58 & 1968.29 \\ \(\mathsf{Avg}(\text{Counts})\) & 14.83 & 34.42 & 17.76 & 13.83 \\ \(\mathsf{Max}(|L|)\) & 16 & 64 & 7 & 8 \\ \(\mathsf{Max}(|L^{\prime}|)\) & 16 & 64 & 4 & 1 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of datasets.
grine Jamshidi et al. (2020), both of which evaluate the exact counts. Note that there are many other exact approaches, but they are not suitable baselines due to their lack of generality. In particular, many approaches have algorithmic limitations that can only process small queries, _e.g._, up to 4 nodes in PGD Ahmed et al. (2015), 5 nodes in RAGE Marcus and Shavitt (2012) and ORCA Hocevar and Demsar (2014), and 6 nodes in acc-Motif Meira et al. (2014). More broadly speaking, since the counting task is #P-complete, any exact algorithm is bound to suffer from prohibitively high running time once the queries become just moderately large. Besides, some approaches cannot handle certain kinds of queries or input graphs. For example, SCMD Wang et al. (2012) and PATCOMP Jain et al. (2017) are not applicable to directed graphs, and PGD Ahmed et al. (2015) and RAGE Marcus and Shavitt (2012) do not handle graphs with node or edge labels. Although Peregrine does not support directed edges or edge labels either, we run it on our datasets by ignoring edge directions/labels if any, and focus on its time cost only. In addition, there are also a number of statistically approximate methods, but they have similar shortcomings. For example, tMotivo and L8Motif Bressan et al. (2021) can only handle query graphs with no more than 8 or 16 nodes.

**Settings and parameters.** For SMALL and LARGE datasets, we randomly sample 5000 triples for training, 1000 for validation, and the rest for testing. For MUTAG, due to its small size, we randomly sample 1000 triples for training, 100 for validation, and the rest for testing. For OGB-PPA, we divide the triples into training, validation and testing sets with a proportion of 4:1:5. We also evaluate the impact of training size on the model performance in Appendix F. We report further model and parameter settings of Count-GNN in Appendix E.

**Evaluation.** We employ mean absolute error (MAE) and Q-error Zhao et al. (2021) to evaluate the effectiveness of Count-GNN. The widely used metric MAE measures the magnitude of error in the prediction. In addition, Q-error measures a relative error defined by \(\max(\frac{n}{n},\frac{\tilde{n}}{n})\), where \(n\) denotes the ground-truth count and \(\hat{n}\) denotes the predicted count.1 Both metrics are better when smaller: the best MAE is 0 while the best Q-error is 1. We further report the inference time for all the approaches to evaluate their efficiency on answering queries, as well as their training time. We repeat all experiments with five runs, and report their average results and standard deviations.

Footnote 1: If the ground-truth or predicted count is less than 1, we assume a pseudocount of 1 for the calculation of q-error.

### Performance Evaluation

To comprehensively evaluate the performance, we compare Count-GNN with the baselines in two settings: (1) a main setting with triples generated by all the query graphs and input graphs; (2) a secondary setting with triples generated by all input graphs associated with only one query graph. Note that the main setting represents a more general scenario, in which we compare with all baselines except LRP. However, due to the particular design of LRP that requires a number of input graphs coupled with one query graph and the corresponding ground-truth count during training, we use the secondary setting only for this baseline. Our model can flexibly work in both settings.

**Testing with main setting.** As discussed, we compare Count-GNN with all baselines except LRP in this more general scenario, where the triples are generated by coupling every pair of query and input graphs.

We report the results in Table 2, and compare the aspects of effectiveness and efficiency. In terms of _effectiveness_ measured by MAE and Q-error, Count-GNN can generally outperform other GNN-based models. In the several cases where Count-GNN is not the best among the GNN-based models, it still emerges as a competitive runner-up. This demonstrates the two key modules of Count-GNN, namely, edge-centric aggregation and query-conditioned graph modulation, can improve structure matching between input graphs and structurally diverse queries. In terms of _efficiency_ measured by the query time, we make three observations. First, Count-GNN achieves 65x\(\sim\)324x speedups over

\begin{table}
\begin{tabular}{l|c c c|c c c|c c c|c c c|c c c} \hline \hline \multirow{2}{*}{Methods} & \multicolumn{3}{c|}{SMALL} & \multicolumn{3}{c|}{LARGE} & \multicolumn{3}{c|}{MUTAG} & \multicolumn{3}{c}{OGB-PPA} \\  & MAE \(\downarrow\) & Q-error \(\downarrow\) & Time/s \(\downarrow\) & MAE \(\downarrow\) & Q-error \(\downarrow\) & Time/s \(\downarrow\) & MAE \(\downarrow\) & Q-error \(\downarrow\) & Time/s \(\downarrow\) & MAE \(\downarrow\) & Q-error \(\downarrow\) & Time/s \(\downarrow\) \\ \hline GCN & 14.8 \(\pm\) 0.5 & 2.1 \(\pm\) 0.1 & 7.9 \(\pm\) 0.2 & 33.0 \(\pm\) 0.4 & 3.5 \(\pm\) 1.0 & 29.8 \(\pm\) 0.7 & 19.9 \(\pm\) 9.7 & 4.2 \(\pm\) 1.5 & 0.88 \(\pm\) 0.02 & 36.8 \(\pm\) 1.4 & 2.1 \(\pm\) 0.4 & 12.5 \(\pm\) 0.3 \\ GraphSAGE & 14.0 \(\pm\) 2.7 & 2.5 \(\pm\) 0.8 & **7.0** \(\pm\) 0.1 & 33.8 \(\pm\) 1.6 & 3.1 \(\pm\) 0.4 & **27.5** \(\pm\) 1.3 & 13.9 \(\pm\) 2.8 & 4.7 \(\pm\) 0.8 & 0.88 \(\pm\) 0.02 & 32.5 \(\pm\) 4.5 & 2.5 \(\pm\) 0.5 & **11.1** \(\pm\) 0.1 \\ GAT & 12.2 \(\pm\) 0.7 & 2.0 \(\pm\) 0.5 & 14.3 \(\pm\) 0.3 & 37.3 \(\pm\) 5.2 & 6.0 \(\pm\) 1.2 & 59.4 \(\pm\) 0.7 & 30.8 \(\pm\) 6.7 & 6.0 \(\pm\) 0.3 & 0.91 \(\pm\) 0.01 & 35.8 \(\pm\) 2.4 & 2.2 \(\pm\) 0.6 & 30.4 \(\pm\) 0.8 \\ DPGCNN & 16.8 \(\pm\) 0.7 & 2.9 \(\pm\) 0.2 & 21.7 \(\pm\) 0.4 & 39.8 \(\pm\) 3.7 & 5.4 \(\pm\) 1.6 & 64.8 \(\pm\) 0.9 & 27.5 \(\pm\) 2.5 & 4.9 \(\pm\) 0.6 & 15.4 \(\pm\) 0.01 & 38.4 \(\pm\) 1.2 & 2.3 \(\pm\) 0.3 & 19.4 \(\pm\) 0.7 \\ DiffPool & 14.8 \(\pm\) 2.6 & 2.1 \(\pm\) 0.4 & **7.0** \(\pm\) 0.1 & 34.9 \(\pm\) 1.4 & 33.8 \(\pm\) 0.7 & 32.5 \(\pm\) 0.7 & 6.4 \(\pm\) 0.3 & 2.5 \(\pm\) 0.2 & 0.86 \(\pm\) 0.00 & 35.9 \(\pm\) 4.7 & 2.7 \(\pm\) 0.3 & 15.4 \(\pm\) 2.2 \\ GIN & 12.6 \(\pm\) 0.5 & 2.1 \(\pm\) 0.1 & 7.1 \(\pm\) 0.0 & 35.9 \(\pm\) 0.6 & 4.8 \(\pm\) 0.2 & 33.5 \(\pm\) 0.6 & 21.3 \(\pm\) 1.0 & 5.6 \(\pm\) 0.7 & 0.41 \(\pm\) 0.01 & 34.6 \(\pm\) 1.4 & 2.5 \(\pm\) 0.5 & 12.3 \(\pm\) 0.4 \\ \hline RGCN-Sum & 24.2 \(\pm\) 6.1 & 3.7 \(\pm\) 1.2 & 13.2 \(\pm\) 0.1 & 80.9 \(\pm\) 26.3 & 6.3 \(\pm\) 1.3 & 61.8 \(\pm\) 0.2 & 8.0 \(\pm\) 0.8 & **1.5** \(\pm\) 0.1 & 0.89 \(\pm\) 0.01 & 34.5 \(\pm\) 13.6 & 4.7 \(\pm\) 0.8 & 33.0 \(\pm\) 0.2 \\ RGCN-DN & 16.6 \(\pm\) 2.3 & 3.2 \(\pm\) 1.3 & 4.8 \(\pm\) 0.2 & 73.7 \(\pm\) 2.9 & 2.1 \(\pm\) 4.2 & 10.9 \(\pm\) 0.4 & 7.3 \(\pm\) 0.8 & 2.6 \(\pm\) 0.2 & 1.9 \(\pm\) 0.04 & 57.1 \(\pm\) 15.7 & 5.0 \(\pm\) 1.3 & 31.2 \(\pm\) 0.1 \\ RGIN-WN & 10.7 \(\pm\) 0.3 & 3.2 \(\pm\) 0.2 & 12.2 \(\pm\) 0.0 & 33.2 \(\pm\) 2.2 & 4.2 \(\pm\) 1.3 & 61.4 \(\pm\) 1.0 & 10.8 \(\pm\) 0.9 & 1.9 \(\pm\) 0.1 & 0.45 \(\pm\) 0.02 & 29.1 \(\pm\) 1.7 & 1.2 \(\pm\) 0.6 & 20.6 \(\pm\) 1.2 & 1.1 \(\pm\) 0.6 \\ RGIN-DN & 11.6 \(\pm\) 0.2 & 2.4 \(\pm\) 0.0 & 49.7 \(\pm\) 1.8 & 32.5 \(\pm\) 1.9 & 4.3 \(\pm\) 2.0 & 104.0 \(\pm\) 1.5 & 8.6 \(\pm\) 1.9 & 3.3 \(\pm\) 0.8 & 0.73 \(\pm\) 0.33 & 35.8 \(\pm\) 6.4 & 4.4 \(\pm\) 1.1 & 28.8 \(\pm\) 0.3 \\ DMPNN-LRP & 9.1 \(\pm\) 0.2 &
the classical VF2. While the other exact method Peregrine is orders of magnitude faster than VF2, Count-GNN can still achieve 8x\(\sim\)26x speedups over Peregrine. Second, Count-GNN is also more efficient than other GNN-based isomorphism counting models. On the one hand, Count-GNN achieves 3.1x\(\sim\)6.5x speedups over DMPNN-LRP, which is generally the second best GNN-based method after Count-GNN in terms of effectiveness. On the other hand, Count-GNN also obtains consistent and notable speedups over the fastest RGCN/RGIN variant (_i.e._, RGIN-Sum), while reducing the errors by 20% or more in most cases. Finally, although many conventional GNNs can achieve a comparable or faster query time, their efficiency comes at the expense of much worse errors than Count-GNN, by at least 30% in most cases.

Furthermore, we compare the training time of GNN-based approaches in Table 3. Our proposed Count-GNN generally requires relatively low training time on SMALL and MUTAG, while having comparable training time to the baselines on LARGE and OGB-PPA.

**Testing with secondary setting.** We also generate another group of triples for comparison with the baseline LRP, in the so-called secondary setting due to the design requirement of LRP. In particular, we only evaluate on three datasets SMALL, LARGE and MUTAG, as LRP is out-of-memory on OGB-PPA with large and dense graphs. For each dataset we select three query graphs of different sizes (see Appendix C). On each dataset, we couple each query graph with all the input graphs, thus forming 6790/3240/188 triples for each query in SMALL/LARGE/MUTAG, respectively. Besides, we split the triples of SMALL and LARGE in the ratio of 1:1:2 for training, validation and testing, while using the ratio of 1:1:1 for MUTAG.

The results are reported in Table 4. We observe that Count-GNN consistently outperforms LRP in terms of effectiveness, significantly reducing MAE by 43% and Q-error by 64% on average. This verifies again the power of the two key modules in Count-GNN. For efficiency, neither Count-GNN nor LRP emerges as the clear winner.

**Summary.** Compared to existing GNN-based models, Count-GNN generally achieves significant error reductions with comparable or faster training and inference, advancing the research of GNN-based isomorphism counting.

### Model Analysis

We further investigate various aspects of Count-GNN on the three datasets SMALL, LARGE and MUTAG.

**Ablation Study.** To evaluate the impact of each module in Count-GNN, we conduct an ablation study by comparing Count-GNN with its two degenerate variants: (1) Count-GNN\(\backslash\)E, which replaces the edge-centric aggregation with the node-centric GIN; (2) Count-GNN\(\backslash\)M, which replaces the query-conditioned modulation with a simple sum-pooling as the readout for the input graph.

We report the results in Table 5. Not surprisingly, the full model generally outperforms the two variants, further demonstrating the benefit of edge-centric aggregation and query-conditioned modulation. Furthermore, Count-GNN\(\backslash\)M is usually better than Count-GNN\(\backslash\)E, which implies that edge-centric aggregation may contribute more to the performance boost, possibly due to its more central role in capturing fine-grained structure information by treating edges as the first-class citizen.

**Scalability, impact of parameters and training size.** We present these results in Appendix F due to space limitation.

## 6 Conclusions

In this paper, we proposed a novel model called Count-GNN to approximately solve subgraph isomorphic counting on labeled graphs. In terms of modelling, we designed two key modules for Count-GNN, namely, edge-centric message passing and query-conditioned graph modulation, to improve structure matching between the query and input graphs. In terms of theory, we showed that edge-centric message passing is more expressive than its node-centric counterpart. In terms of empirical results, we conducted extensive experiments on several benchmark datasets to demonstrate the effectiveness and efficiency of Count-GNN.

\begin{table}
\begin{tabular}{c c|c c|c c|c c c} \hline \hline \multirow{2}{*}{Methods} & \multicolumn{3}{c|}{SMALL} & \multicolumn{3}{c|}{LARGE} & \multicolumn{3}{c}{MUTAG} \\  & \multicolumn{1}{c}{MAE} & Q-err & Time/s & \multicolumn{1}{c}{MAE} & Q-err & Time/s & \multicolumn{1}{c}{MAE} & Q-err & Time/s \\ \hline \multirow{2}{*}{\(\mathcal{Q}_{1}\)} & LRP & 11.5 & 3.6 & 0.13 & 126.1 & 38.3 & **0.04** & 12.3 & 2.1 & 0.01 \\  & Count-GNN & **3.0** & **1.4** & **0.04** & **111.2** & **2.9** & 0.22 & **2.5** & **1.2** & **0.00** \\ \hline \multirow{2}{*}{\(\mathcal{Q}_{2}\)} & LRP & 12.6 & 4.6 & 0.12 & 19.8 & 3.7 & **0.04** & 7.8 & 2.9 & **0.01** \\  & Count-GNN & **4.6** & **1.1** & **0.05** & **4.3** & **1.1** & 0.07 & **5.0** & **2.1** & **0.01** \\ \hline \multirow{2}{*}{\(\mathcal{Q}_{3}\)} & LRP & 31.5 & 4.1 & 0.05 & 87.2 & 7.1 & **0.04** & 8.3 & 2.8 & 0.01 \\  & Count-GNN & **23.2** & **1.3** & **0.03** & **58.0** & **1.8** & 0.08 & **4.3** & **1.8** & **0.01** \\ \hline \multirow{2}{*}{Avg} & LRP & 18.5 & 4.1 & 0.10 & 77.7 & 16.4 & **0.04** & 9.5 & 2.6 & 0.01 \\  & Count-GNN & **10.3** & **1.3** & **0.04** & **57.8** & **1.9** & 0.12 & **3.9** & **1.7** & 0.01 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Evaluation in the secondary setting. Time refers to the total inference time on all test triples, in seconds. The better method for each query is bolded.

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline Methods & SMALL & LARGE & MUTAG & OGB-PPA \\ \hline GCN & 0.8 & 1.1 & 0.35 & 1.0 \\ GraphSAGE & 0.8 & 1.0 & 0.35 & 0.9 \\ GAT & 1.0 & 2.4 & 0.39 & 1.5 \\ DiffPool & 0.8 & 1.3 & 0.34 & 1.2 \\ GIN & 0.5 & 1.0 & 0.19 & 0.7 \\ RGCN-SUM & 1.0 & 2.4 & 0.38 & 1.7 \\ RGCN-DN & 1.5 & 3.7 & 0.50 & 2.2 \\ RGIN-SUM & 0.7 & 1.9 & 0.23 & 1.3 \\ RGIN-DN & 1.4 & 2.9 & 0.39 & 1.8 \\ Count-GNN & 0.4 & 2.5 & 0.04 & 1.3 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Comparison of training time per epoch, in seconds.
## Acknowledgments

This work was supported in part by the National Key Research and Development Program of China under Grant 2020YFB2103803. Dr. Yuan Fang acknowledges the Lee Kong Chian Fellowship awarded by Singapore Management University for the support of this work. The authors wish to thank Dr. Yuchen Li from Singapore Management University for his valuable comments on this work.
