DEIM Forum 2023 3a-5-2

User-Interactive Molecular Graph Suggestion for Drug Discovery
Sheng HU† , Ichigaku TAKIGAWA†,†† , and Chuan XIAO†††† ICReDD, Hokkaido University Kita-ku, Sapporo, Japan†† RIKEN Center for AIP Seika-cho, Kyoto, Japan††† Graduate School of Information Science and Technology, Osaka University
1-5, Yamadaoka, Suita, Osaka, Japan
E-mail: †{hu.sheng,takigawa}@icredd.hokudai.ac.jp, ††chuanx@ist.osaka-u.ac.jp
Abstract We present a novel molecular graph generation method by auto-completing a privileged scaﬀold which
represents a core graph substructure step-by-step. We propose a generative GNN model thus providing the ability
to generate unseen molecular graphs outside the given training set. An edit-aware graph autocompletion paradigm
that follows the “substructure-by-substructure” process is designed to complete the scaﬀold queries in multiple
substructure adopt operations and allow meaningful edit operations to show the user’s intention. Such operations
enable the involvement of user decisions when interacting with a generative user-centered AI system, which diﬀerentiates our work from existing single-run generation paradigms. Particularly, a Monte Carlo tree search (MCTS)
method is employed to satisfy the property requirements and navigate the search space when complying with users’
edit operations. Moreover, we design a top-k ranking function which considers the preferences on popularity anddiversity for diﬀerent applications, such as query compositions for graph database and drug discovery respectively.
Such techniques enable human experts to synergistically interact with the generative models grounded on large data.
Key words Graph generation, graph neural networks, drug discovery

1 Introduction

Due to surprising success of deep neural network (DNN)
models these days, two categories of representations used in

The ultimate goal of modern drug discovery is to ﬁnd the

DNN-based models emerge in the drug discovery domain.

target molecules with desired chemical properties, while the(1) simpliﬁed molecular input line entry system (SMILES)

potential chemical space of drug-like compounds is 10 23 −strings representation. Several early works [1, 8, 9, 21, 23] are60

10 . Until recent years, such chemical space exploration

proposed to learn the SMILES grammar using RNN archi-

was traditionally conducted by expert chemists and phar-tectures and then generate corresponding SMILES strings

macologists, along with huge time and monetary cost beingfrom the trained models. These methods have limitations todevoted.

learning the unrelated grammar and thus have low chemical

Visual graph query composition can assist modern drug

validity from generated SMILES. A recent trend is (2) undi-

discovery, which did not attract much attention comparedrected labeled graph representation [27]. It is more natural

with the success in the graph database community [3, 4,

to learn the original graph structure by using graph neu-

10, 13, 25, 29, 30]. Instead of exploratory searching given a

ral networks (GNNs). This representation can easily achieve

subgraph query in graph databases and showing matchedhigher chemical validity. In this work, we adopt the graph-graphs [29, 30], we prefer to use generative models to growbased representation along with GNN models as our gener-

novel molecules on the given subgraph. In the applications

ative models. GNN models are employed during the visualof drug discovery, such a subgraph query is usually called agraph query composition process to generate completed can-

scaﬀold (i.e., privileged or bioactive scaﬀold), and performs

didates. A motivating example is shown in Figure 1.（注 1）

as a core structure in the molecule to preserve the prefer-［Example 1］ In Figure 1, a user wants to design a newable bioactivity properties. The generated novel molecularmolecule with a scaﬀold shown in user’s query. Thisgraphs are supergraphs of the scaﬀold thus being guaranteed（注 1）

to contain the scaﬀold to reveal the chemical properties. Fixing the scaﬀold usually dramatically reduces the search space

While we only show an example for the scenario of drug discovery,

our autocompletion system can be simply applied to traditional graphquery suggestions for graph databases.

of the desired drug thus saving experts’ time and cost.
—1—user ﬁrst adopts a suggested candidate to complete thegraphs. Users can draw various scaﬀold queries in our pre-polygon and then erases a vertex to show the label on

pared Web-based canvas and check the suggestion quality bythis vertex is diﬀerent with his original intention. Thenthemselves.

the system sends the input to the learned GNN and returns two candidates rank1 and rank2, with detailed

3 Edit-Aware Graph Autocompletion

molecule properties (e.g., MW, logP and QED). The user

Scaﬀold input.

can interact with rank1 and rank2, such as adopt rank1

carrying important characteristics of molecules. The basis

as a new query or even erase a part. The new query will

scaﬀolds of a molecule are usually the set of all unique ring

be taken as input and sent into the GNNs for further gen-systems in the molecule, while a ring system is deﬁned as

erations. This process repeats until a proper molecularsingle/multiple rings sharing an internal bond. The graph

graph is found.

representing a molecule itself is called a full molecular graph.
Scaﬀolds can be extracted by utilizing general graph min-2 Related WorkScaﬀold-based Molecular Graph Generation.

Scaﬀolds are generally those subgraphs

ing algorithms [16], but as for molecular applications, we use
The

HierS [26] to obtain the scaﬀolds to keep in line with [18].

idea of growing molecules on scaﬀolds using DNN models［Deﬁnition 1］（Scaﬀold input） Given a well-trained gener-

did not receive too much attention except the ScaﬀoldVAE

ative model M and a scaﬀold input q, the candidate

model [20] and DeepScaﬀold [18]. ScaﬀoldVAE focused ongraphs generated by M is a set Mq = { g | q ⊆ g },growing side chains from Bemis-Murcko scaﬀolds [2], which

where q ⊆ g means q is a subgraph of g.

is a special kind of scaﬀold that only preserves ring systems.

Deﬁnition 1 guarantees that the generated graphs {g | g ∈DeepScaﬀold is similar with ScaﬀoldVAE but includes allMq } are supergraphs of q.

subscaﬀolds in their dataset to provide the ability of growing

Autoregressive GNNs. We adopt the GNN model useda full molecule from a much smaller subscaﬀold. However,in [18] and [19] for generating our graph candidates. The

both above methods generate the ﬁnal molecule in a sin-

entire model architecture is shown in Figure 2. Compared

gle step without allowing users to edit on the intermediatewith variational autoencoders (VAEs) or generative adver-graph to show their real intentions. This prevents the users,sarial networks (GANs), autoregressive GNNs have uniqueespecially for expert chemists, from utilizing their reliableability to model edge dependencies, which guarantees thechemical intuitions and experience during the molecule de-nodes are generated in a sequential way.

sign process. The generated molecules reported in both [20]sequence-like graph knowledge representation used in [19]and [18] also proved to be far from practical molecules usedwhich builds a full molecular graph in a sequential fashionin real experimental chemistry.

(⟨g0 , t0 ⟩, ⟨g1 , t1 ⟩, · · · , ⟨gN , tN ⟩), where gn is a speciﬁc graph

We adopt a

In this work, we built a system GNNGAC (GNN-basedstate (q equals g0 here) and tn is an action that transforms

Graph Autocompletion), to allow users to edit the interme-

gn → gn+1 . Such a sequential molecular generative process

diate graph candidates during the molecule design process

is essentially a Markov decision process thus being modeledin multiple steps, utilizing the edit operations to understandas either Markovian or recurrent using a global recurrent

the user’s real intention by adjusting the heuristic functions

neural network (RNN). In other words, the GNNs are used

employed in MCTS. We design an interactive substructure-

to decide whether to generate a new atom or bond along

by-substructure adopt process to verify this idea. This pro-with its atom/bond type. In [19], three types of actions ti

cess guarantees the involvement of user decisions to interact

are allowed to build a full molecule: (1) add an atom andwith a generative user-centered AI system, which diﬀerenti-

connect it with an existing atom v (with a probability pAv

ates our work from previous studies that generate graphs in), (2) connect an existing atom v to the new atom (with aa single run [18, 20]. Compared with generating a bunch ofprobability pCv ), and (3) terminate the generating process

cluttered results, involving user decisions can exploit human(with a probability p∗ ). According to Figure 2, the MLP

capability, i.e., domain knowledge or experiences, to generate

layer outputs a tensor with a size |V | × (|A| + 1) × |B|, wheremuch more insightful candidates. Also, to make the utmost

V is the atom node set that v ∈ V , A is the atom typeof graph training data set for eﬃcient training, we design

set, and B is the bond type set. This tensor is further split

scaffold-trie for data augmentation and eﬃciently train

AC
into [pA , pC ] = [tensor|V|×|A|×|B| , tensor|V |×1×|B| ]. On the

the GNN from the computer memory. A pairwise Tanimotoother side, the MLP* layer outputs a scalar value p∗ to rep-similarity-based top-k ranking algorithm is also proposed toresent the probability of termination. Eventually, after aenhance the practicability. We demonstrate our system using

softmax computation, {pA , pC , p∗} decides which action ti

a real-world molecular dataset containing nearly one million

should be taken when gn+1 ← ti (gn ).
—2—

① Edit-aware graph autocompletion② Graph partition method to generate training set

user’s query
adopt

G1:

erase

G2:
rank1:

MW: …
logP: …
QED: …

MW: …
logP: …
QED: …

rank2:

G3:
training pair:(G1, G2)(G1, G3)(G2, G3)

Figure 1 An Example of GNN-based Graph Autocompletion

Query reformulation. The composition process of an intermediate molecular graph can seem like a query reformula-

text query reformulation
Add Delete

Keep

Transform

OthersFirst Querytion. The user interaction and behavior correlates much withgraph query reformulation

if they are satisﬁed with the intermediate molecular graphs.

add erase adopt
replacerollback start graph
Table 1 graph query reformulation operations and the counter-

For example, if one user adopt the intermediate graph withno hesitation, she probably is very satisﬁed because the sug-parts in text query reformulation researchgestion matched her original intention. Conversely, if shechooses to ignore all the provided suggestions but began toically [30]. Without losing the possibility of extending in

add the incremental part on the current graph, she is unsat-

the future, we consider four types of composition operation

isﬁed and showed implicit negative feedback [31] to all sug-

OP = {add, adopt, erase, replace, rollback}. Particularly, we

gestions. If the user ﬁrst adopt a suggestion but then begins

call add, erase, and replace as edit to allow users to perform

to modify (erase or replace or add) a part of the suggestion,

speciﬁc operations on modifying the intermediate resulting

she is also unsatisﬁed with the provided suggestion. Fromgraphs. The edit that the user has performed is usually im-

these interactions, we can learn the user’s preference or in-plicit indicators of his/her real intention. After deﬁning thetent. This is called learning the user’s preference online [31].

operations set that users can make on a graph query refor-

If we obtain an editing query log, we can model a likelihood

mulation, we ﬁnd that the operations can have counterparts

function and train such a preference vector of a new user toin the traditional textual query reformulation operations [6].

avoid the cold-start problem.

We show the mappings in Table 1.

User operations during query reformulation. While

By adapting our edit-aware paradigm, the MCTS algo-users’ operations during the query reformulation of textual

rithm is able to take advantage of users’ ideas, especially forquery settings have been well studied [6, 7, 15, 17, 24], we

those chemical experts who possess drug design experience.

found that there are few works discussing the similar prob-

User preferences and satisfaction. Users’ preferences

lem in the graph query settings. When a user operates onshow the search intent in the drug discovery. The users’ sat-a visual graph composition interface, there are some fun-isfaction can be reﬂected in the sequential behavior during

damental operations he/she can make. For example, edge

the graph query reformulation interactions. There have been

addition is the most fundamental one. Also, we consider

some studies focusing on revealing the satisfactions from tex-that it is natural to allow the user to slightly modify thetual query reformulation interactions [5–7, 11, 12, 17]. Par-

provided suggestion which produces the need for erasing andticularly in [7], two main reasons correlating to satisfaction

replacing a part of the graph. Finally, the most essential op-

are reported: （ 1 ）Users left (clicked or adopted) the query

eration is adopting, which completes the current query by awith satisfaction. （ 2 ）Being unsatisﬁed with most results,suggestion that accelerates the query composition dramat-

users were forced to change the query. We can categorize

Figure 2 Model Architecture

similarly with [17] in Table 2.
Softmax

MLP* (1)
MLP

AvgPooling…
×20

DenseGCN (256)

DenseGCN

BN-ReLU-Conv (64)

Conv (32)

Embedding (16)the sequential behaviors into satisﬁed and unsatisﬁed class

p*

pA
pC

Adopt training. The operation adopt means the user accepts a provided graph suggestion q ′ and incrementally adds
a substructure ∆q to current query q. To make sure q ′ hasa strong correlation with the current query q, we need tocreate the training pair (q, q ′ ) and insert it into the train-—3—Satisﬁed

adopt → M CT S

Case 2 Unsatisﬁed

add → M CT S

Case 3 Unsatisﬁed

adopt → erase → M CT S

Case 1

Selection

Expansion

Simulation

Backpropagation
update stats

Case 4 Unsatisﬁed adopt → replace → M CT S…

Case 5 Unsatisﬁed
adopt → add → M CT S
Table 2 Satisﬁed and Unsatisﬁed sequential behaviors…

…

complete a random rollout
and obtain reward R

ing set. In another word, a simplest case is scaﬀold → q
and molecule → q ′ . Nevertheless, when a relatively larger…

backpropagate the reward
along the traversal path

Figure 3 MCTS ﬂow

molecule requires multiple steps to compose which results ina long composition sequence, more ﬁne-grained training pairuseful drug. To improve the eﬀectiveness of produced graphs

enumerations are expected, i.e., q and ∆q becomes muchfrom the GNN model, we use MCTS to optimize the molec-

smaller and the recursive case q ′′ = q ′ + ∆q must be consid-

ular property such as QED, while considering the user’s edit

ered.

operation at the same time.

Data augmentation. Instead of only using (scaﬀold → q,′

In MCTS, the root node of the search tree represents one

molecule → q ) pairs for training, we need to conduct data

candidate molecular graph from the GNN model. The inter-augmentation to enumerate subgraphs to handle cases suchmediate node in the search tree is associated with a reward

as q ′′ = q +∆q +· · ·+∆q ′ For graph structures, such enumer-

Vi along with the visited times ni . Additionally, we also at-ations are impossible because of the combination explosion oftach a ﬂag showing the action types, which will be used tosubgraphs. Therefore, we decide to only preserve subgraphs

match the user’s last edit operation. These statistics will bewith chemical signiﬁcance (i.e., ring or chain systems). We

updated during the MCTS backpropagation. Figure 3 shows

choose to store each basis scaﬀold q and their incremental

the overall ﬂow of all steps.

′′′

graphs q = q + ∆q + · · · + ∆q in a trie structure according to the super-subgraph relationship in memory and as-

MCTS usually consists of four steps [14, 22, 28]:•

function.

sembly them as training pairs on-the-ﬂy. The advantagesof building the scaffold-trie is multifold: (1) the trie is•

Expansion: expand the selected node by autocompleting
it with a subgraph building block.

memory-resident thus avoiding the I/O overhead which will
deteriorate the training time-cost. (2) the granularity of in-

Selection: select the best node according to a heuristic•

Simulation: conduct the recursive generation until en-

crement size ∆q can be controlled ﬂexibly without rebuilding

countering a leaf node (termination of the molecular

additional indices. (3) a single scaffold-trie can generategraph) and a ﬁnal reward is gained according to its corresponding QED.

training pairs for diﬀerent GNN models’ training requirements beginning with diﬀerent q for diﬀerent problem set-•

Backpropagation: backpropagate the reward V on alltings such as macromolecules. We set a uniform thresholdthe visited nodes along the path that has traversed.

δ = |∆q| as a granularity constraint of incremental subgraphs

Particularly, there are many choices for the subgraph buildingthat grows from previous intermediate graph q. The value δ

block. In [22], the work adopted an atom/bond-wise build-

can be ﬁxed to a number or can be a variable as a ratio suching block which means adding/removing an atom/bond in

as 1/2 size of the full molecular graph. To eﬃciently utilize

the Expansion step. We slightly extend the action space

the training set, we set δ = 1 by default, i.e., we put the pair(q, q ′′ ) into the training set when |∆q| = |q ′′ | − |q| >= 1.

in [22] as {Atom addition, Atom removal, Bond addition,

Moreover, generating the training set only requires for amodify the strategy to select the node as:
√
Vi
lnNi
child = arg max+c+ editbonus (editlast ) (1)niniisingle full traversal of the scaffold-trie thus leading to atime complexity of O(|T |) where |T | represents the numberof nodes in the trie. The training pair set is then taken as
input fed into the GNN model for training purpose.
Property optimization and MCTS details. The realworld drug discovery scenario usually places many property
requirements for the generated molecular graphs. For example, a higher QED represents better drug-likeness considering the main molecular properties together, which meansthat the molecular graph is more likely to be synthesized as a

Bond removal, Atom replacement, Bond replacement} . We

where Vi represents the current value of the node, ni andNi are the visit times of node ni along with its parent Ni ,and c is the balance constant of exploration and exploitation.
editbonus will add a particular bonus weight to the child to
encourage a more aggressive strategy to select nodes withsimilar actions as the user’s edit operations.
User-interactive MCTS. In our edit-aware paradigm, we
design a user-interactive variation of MCTS method to catch—4—

adopt→MCTS

add→MCTS

adopt→erase(or replace or add)→MCTS…

…

…
satisﬁed

not satisﬁed, add a new node

Algorithm 1: Top-k (R)1R′ ← ∅ ;2

foreach ⟨i, j⟩ ∈ R do3

not satisﬁed, modify the suggestion

Figure 4 Interactive selection and preferred expansion.

Compute STanimoto (i, j);4Choose the largest STanimoto (i, j) and R′ ← R′ ∪ i ∪ j;5

for n = 1 · · · k − 2 do

6

Find an i′ to make the util(R′ ∪ i′ ) the largest;

7

R ′ ← R ′ ∪ i′ ;the user’s query intents better. Figure 4 shows the diﬀer8

ences. There are two strategies in this interactive variation/* final set R’ */return R′ ;of MCTS.
interactive selection. As shown in Fig. 4, the red node rep-

ber of bits set to 1 in result i’s(j’s) ﬁngerprint, bi&j means

resents the node selected. We allow users to select the ar-

the number of bits set to 1 in the the intersection of i andbitrary node despite the score of Equation 1. This helps

j’s ﬁngerprints.

ﬁx some valuable subgraphs (functional groups) already ob-

4 2 Top-k Ranking

tained, which are also being favored by users. When users

Along with diversiﬁcation, we also need to rank the results

are not satisﬁed with all results, they can draw their own

according to the substructure popularity to assist the users in

scaﬀold, and then it will be inserted into the search tree aseasily adding the most possible subgraphs. Here, we adapt a

the green node. When users just modify a part of the sug-

statistic sel∆ (q ′ ) used in [30] which represents the number ofgestion, the modiﬁed graph will be derived as a new yellow

supergraphs of the increments (∆q ′ ) in the database (train-node.

ing set) D. This can ensure that novel molecular graphs

preferred expansion The interaction behavior from thegenerated will not have low ranks (which are not contained

user’s edition will be collected through the query logs. Thenin the database). Diﬀerently, we further extend the ∆q ′ asthe expansion step will consider the preferences by learning∆q ′ ∪ q∆ , where q∆ represents the smallest subgraph in q

the preference vectors and return diﬀerent suggestions ac-

which connects ∆q ′ to avoid meaningless increments. Notecording to diﬀerent users.

that sel∆ (q ′ ) can be eﬃciently computed oﬄine using graph

Learning the preference vector by satisfactions.

indexing techniques proposed in [29].

rule set, lhs, rhs, similarity

The ﬁnal ranking function (util) can be written as below:

4 Top-k Diversifying and Ranking Resultsutil(R′ ) =w ∑sel∆ (q ′ ) + (1 − w)AP T (R′ )
k ′ ′

(3)

q ∈R

4 1 Diversiﬁcation
After running either GNN inference or MCTS, we can obtain our results set R. When |R| is a large number, displaying

where a weight parameter w ∈ [0, 1] is added to balance thepopularity and diversity scores.

all the graphs in R will only mess up the interface with sim-

The value of w also has inﬂuences on diﬀerent applica-

ilar results. In this section, we propose a method to only

tions. For example, for traditional graph query suggestions

choose top-k diversiﬁed graphs out of R to form the ﬁnal

on database search, a larger w is expected to add more fre-result set R′ thus |R′ | = k < |R|.

quent subgraph fragments to formulate the query quickly.

We take advantage of the metric proposed in [26], whichis called average pairwise Tanimoto (APT). Here, Tanimoto

On the contrary, drug discovery requires a smaller w to improve the diversity for generating novel molecules.

means Tanimoto coeﬃcient which is computed using molec-

Finding the most optimal set R′ out of R means util(R′ )ular ﬁngerprint to describe how similar two molecular graphs

should be larger than any other alternative set R′′ with theare. By adopting APT, we sum up the computed Tanimoto

same set size. This process proved to be a NP-hard prob-

coeﬃcients between each pair of graphs appearing in R, andlem, which is a reduction from the maximum independent set

divide the sum by total number of pairs as shown in Equa-

problem shown in [29]. Similar with [29], we use a greedy al-tion 2.

gorithm (Algorithm 1) to obtain the optimal solution. When|R′ | = k, the time complexity of ﬁnding the APT(R′ ) isO(k×|R|×STanimoto ), where |R| represents the unique graphs

|R|

∑
1
bi&j
AP T (R) =|R|(|R| − 1)bi + bj − bi&j

(2)

i=j
|

generated and STanimoto means the Tanimoto similarity computation.

where |R| represents the size of result set R, bi (bj ) is the num—5—

Figure 5 A Screenshot

5 System Architecture
Front end. The front end is a Web-based graphical interface for drawing queries and navigating through graph candidates. The editor is a canvas where users can input the
scaﬀold queries using various canned patterns or drawingedge-by-edge. The user can click on the candidate to adopt
the completion and add it to the working canvas.
Back end.

Five modules are included in the back end.

(1) GNN module, (2) MCTS module, (3) Graph generation
module, (4) Top-k ranking module, and (5) Query logging
module.
A demo interface. To verify the idea of multi-step graphgenerations, we prepared a demonstration system. We set
up the system as shown in Figure 5. In Figure 5, button
MCTS means generating graphs by MCTS, and GNN
will trigger generations with a GNN model. After checking the checkbox With Erase , the erase toolkit will collectthe erased information to adjust the heuristic functions in
MCTS. The operations of add and replace will also change
the behavior of MCTS as erase does. In this demo, we aim
to show that GNNGAC gives graph suggestions (right panels
in Figure 5) in an interactive way. The users can take thereference of the chemical properties (MW, logP, QED) for
judgement in drug discovery.

Acknowledgment
This work is partly supported by JSPS KAKENHI
Grant Number JP21K17745, JP21K12041, JP20H00323,
JP20H00605,

JP20H05962,

JP17H06099,

JP18H04093,

JP19K11979 and JST CREST Grant Number JPMJCR18K.
References[1] J. Arús-Pous, A. Patronov, E. J. Bjerrum, C. Tyrchan, J.-L.
Reymond, H. Chen, and O. Engkvist. Smiles-based deep generative scaﬀold decorator for de-novo drug design. Journalof Cheminformatics, 12(1):1–18, 2020.
[2] G. W. Bemis and M. A. Murcko. The properties of known
drugs. 1. molecular frameworks. Journal of medicinal chemistry, 39(15):2887–2893, 1996.

[3] S. S. Bhowmick, B. Choi, and C. Dyreson. Data-driven visual graph query interface construction and maintenance:
Challenges and opportunities. PVLDB, 9(12):984–992, Aug.
2016.
[4] S. S. Bhowmick, B. Choi, and C. Li. Graph querying meets
hci: State of the art and future directions. In ACM SIGMOD
2017, page 1731–1736, New York, NY, USA, 2017.
[5] F. Cai and M. de Rijke. Selectively Personalizing Query AutoCompletion. In Proceedings of the 39th International ACM
SIGIR conference on Research and Development in Information Retrieval, pages 993–996, Pisa Italy, July 2016. ACM.
24 citations (Semantic Scholar/DOI) [2022-10-26].
[6] J. Chen, Y. Liu, J. Mao, F. Zhang, T. Sakai, W. Ma,
M. Zhang, and S. Ma. Incorporating Query Reformulating Behavior into Web Search Evaluation. In Proceedingsof the 30th ACM International Conference on Information& Knowledge Management, pages 171–180, Virtual Event
Queensland Australia, Oct. 2021. ACM. 3 citations (Semantic Scholar/DOI) [2022-11-01].
[7] J. Chen, J. Mao, Y. Liu, F. Zhang, M. Zhang, and S. Ma. Towards a Better Understanding of Query Reformulation Behavior in Web Search. In Proceedings of the Web Conference
2021, pages 743–755, Ljubljana Slovenia, Apr. 2021. ACM.
14 citations (Semantic Scholar/DOI) [2022-11-01].
[8] H. Dai, Y. Tian, B. Dai, S. Skiena, and L. Song. Syntaxdirected variational autoencoder for structured data. ICLR
2018, 2018.
[9] R. Gómez-Bombarelli, J. N. Wei, D. Duvenaud, J. M.
Hernández-Lobato, B. Sánchez-Lengeling, D. Sheberla,
J. Aguilera-Iparraguirre, T. D. Hirzel, R. P. Adams, and
A. Aspuru-Guzik. Automatic chemical design using a datadriven continuous representation of molecules. ACS central
science, 4(2):268–276, 2018.
[10] W. Han, J. Lee, M. Pham, and J. X. Yu. igraph: A framework
for comparisons of disk-based graph indexing techniques.
Proc. VLDB Endow., 3(1):449–459, 2010.
[11] A. Hassan, X. Shi, N. Craswell, and B. Ramsey. Beyond
clicks: query reformulation as a predictor of search satisfaction. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, CIKM
’13, pages 2019–2028, New York, NY, USA, Oct. 2013. Association for Computing Machinery. 112 citations (Semantic
Scholar/DOI) [2022-11-02].
[12] K. Hofmann, S. Whiteson, and M. de Rijke. A probabilistic
method for inferring preferences from clicks. In Proceedingsof the 20th ACM international conference on Informationand knowledge management - CIKM ’11, page 249, Glasgow,
Scotland, UK, 2011. ACM Press. 129 citations (Semantic
Scholar/DOI) [2022-10-26].
[13] K. Huang, H. Chua, S. S. Bhowmick, B. Choi, and S. Zhou.
CATAPULT: data-driven selection of canned patterns foreﬃcient visual graph query formulation. In P. A. Boncz,
S. Manegold, A. Ailamaki, A. Deshpande, and T. Kraska,
editors, ACM SIGMOD 2019, pages 900–917, 2019.
[14] J. H. Jensen. A graph-based genetic algorithm and generative model/Monte Carlo tree search for the exploration ofchemical space. Chemical Science, 10(12):3567–3572, 2019.
[15] J.-Y. Jiang, Y.-Y. Ke, P.-Y. Chien, and P.-J. Cheng. Learning user reformulation behavior for query auto-completion.
In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval,
pages 445–454, Gold Coast Queensland Australia, July 2014.
ACM. 97 citations (Semantic Scholar/DOI) [2022-10-26].
[16] W. Jin, R. Barzilay, and T. Jaakkola. Junction tree variational autoencoder for molecular graph generation. ICML
2018, 2018.
[17] L. Li, H. Deng, A. Dong, Y. Chang, H. Zha, and R. BaezaYates. Analyzing User’s Sequential Behavior in Query Auto-

—6—

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Completion via Markov Processes. In Proceedings of the 38th
International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 123–132, Santiago
Chile, Aug. 2015. ACM. 28 citations (Semantic Scholar/DOI)[2022-10-26].
Y. Li, J. Hu, Y. Wang, J. Zhou, L. Zhang, and Z. Liu. Deepscaﬀold: a comprehensive tool for scaﬀold-based de novo drug
discovery using deep learning. Journal of Chemical Information and Modeling, 60(1):77–91, 2019.
Y. Li, L. Zhang, and Z. Liu. Multi-objective de novo drug
design with conditional graph generative model. Journal ofcheminformatics, 10(1):33, 2018.
J. Lim, S.-Y. Hwang, S. Moon, S. Kim, and W. Y. Kim.
Scaﬀold-based molecular design with a graph generativemodel. Chemical Science, 11(4):1153–1164, 2020.
M. Olivecrona, T. Blaschke, O. Engkvist, and H. Chen.
Molecular de-novo design through deep reinforcement learning. Journal of cheminformatics, 9(1):48, 2017.
A. A. Rajasekar, K. Raman, and B. Ravindran. Goal directed molecule generation using Monte Carlo Tree Search,
Dec. 2020.
M. H. Segler, T. Kogej, C. Tyrchan, and M. P. Waller. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS central science, 4(1):120–131,
2018.
L. Tamine, J. L. Melgarejo, and K. Pinel-Sauvagnat. What
Can Task Teach Us About Query Reformulations? In J. M.
Jose, E. Yilmaz, J. Magalhães, P. Castells, N. Ferro, M. J.
Silva, and F. Martins, editors, Advances in Information Retrieval, volume 12035, pages 636–650. Springer International
Publishing, Cham, 2020. Series Title: Lecture Notes in Computer Science.
C. Wang, M. Xie, S. S. Bhowmick, B. Choi, X. Xiao, andS. Zhou. Ferrari: an eﬃcient framework for visual exploratory
subgraph search in graph databases. The VLDBJ, pages 1–
26, 2020.
S. J. Wilkens, J. Janes, and A. I. Su. Hiers: hierarchical scaffold clustering using topological chemical graphs. Journal of
medicinal chemistry, 48(9):3182–3193, 2005.
X. Xia, J. Hu, Y. Wang, L. Zhang, and Z. Liu. Graph-based
generative models for de novo drug design. Drug Discovery
Today: Technologies, 2020.
X. Yang, J. Zhang, K. Yoshizoe, K. Terayama, and K. Tsuda.
ChemTS: an eﬃcient python library for de novo molecular
generation. Science and Technology of Advanced Materials,
18(1):972–976, Dec. 2017.
P. Yi, B. Choi, S. S. Bhowmick, and J. Xu. Autog: a visual
query autocompletion framework for graph databases. The
VLDBJ, 26(3):347–372, 2017.
P. Yi, B. Choi, Z. Zhang, S. S. Bhowmick, and J. Xu. Gfocus:
User focus-based graph query autocompletion. IEEE TKDE,
pages 1–1, 2020.
A. Zhang, A. Goyal, W. Kong, H. Deng, A. Dong, Y. Chang,
C. A. Gunter, and J. Han. adaQAC: Adaptive Query AutoCompletion via Implicit Negative Feedback. In Proceedings of the 38th International ACM SIGIR Conference on
Research and Development in Information Retrieval, pages
143–152, Santiago Chile, Aug. 2015. ACM. 43 citations (Semantic Scholar/DOI) [2022-10-26].

—7—