In materials science, micro-level (atomic-scale) activities are considered to be the key to understanding various macro-level (bulk) properties of a material. Molecular dynamics simulations are widely used to obtain atom dynamics. However, researchers are often too overwhelmed by the amount of simulation data to discover relevant atomic activities. Furthermore, mining the structure graph of a material (the graph where the constituent atoms form nodes and the bonds between the atoms form edges) offers little help in this scenario. It is the patterns among the atomic dynamics that may reveal the mechanisms underlying a particular material property. Discovery of such patterns can lead to a better model and better predictions of the properties and behaviors of the materials. We propose an event graph to model the atomic dynamics and propose a graph mining algorithm to discover popular subgraphs in the event graph. Because the event graph is a directed acyclic graph, our mining algorithm uses a new graph encoding scheme that is based on topological-sorting. This encoding scheme ensures that our algorithm enumerates candidate subgraphs without any duplication. Experiments with simulation data of silica liquid demonstrate the effectiveness of our mining system which we call ``ToPoMine''.
AllenM.P. and TildesleyD.J., Computer Simulation of Liquids, 1987.
2.
HumphreyW., DalkeA. and SchultenK., VMD: Visual molecular dynamics, Journal of Molecular Graphics (1996), 33-38.
3.
BhattaraiD. and KarkiB., Atomistic visualization: Space-time multiresolution integration of data analysis and rendering, Journal of Molecular Graphics and Modelling27(951) (2009), 33-38.
4.
GrottelS., ReinaG., DachsbacherC. and ErtlT., Coherent culling and shading for large molecular dynamics visualization, in: Proceedings of the 12th Eurographics/IEEE - VGTC Conference on Visualization, (2010), 953-962.
5.
DehaspeL., ToivonenH. and KingR.D., Finding frequent substructures in chemical compounds, in: 4th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (1998), 30-36.
6.
BorgeltC. and BertholdM.R., Mining molecular fragments: Finding relevant substructures of molecules, in: Proceedings of the 2002 IEEE International Conference on Data Mining, (2002), 51-58.
7.
CookD.J. and HolderL.B., Substructure discovery using minimum description length and background knowledge, Journal of Artificial Intelligence Research (1994), 231-255.
8.
KuramochiM. and KarypisG., Frequent subgraph discovery, in: Proceedings of the 2001 IEEE International Conference on Data Mining, (2001), 313-320.
9.
YanX. and HanJ., gSpan: Graph-based substructure pattern mining, in: Proceedings of the 2002 IEEE International Conference on Data Mining, (2002), 721-724.
10.
HuanJ., WangW. and PrinsJ., Efficient mining of frequent subgraphs in the presence of isomorphism, in: Proceedings of the Third IEEE International Conference on Data Mining, (2003), 549-552.
11.
KuramochiM. and KarypisG., Finding frequent patterns in a large sparse graph, Data Min Knowl Discov (2005), 243-271.
12.
ThomasL.T., ValluriS.R. and KarlapalemK., Margin: Maximal frequent subgraph mining, ACM Trans Knowl Discov Data10 (2010), 1-42.
13.
YouC.H., HolderL.B. and CookD.J., Graph-based data mining in dynamic networks: Empirical comparison of compression-based and frequency-based subgraph mining, in: Proceedings of the 2008 IEEE International Conference on Data Mining Workshops, (2008), 929-938.
14.
HorbachJ. and KobW., Static and dynamic properties of a viscous silica melt, Physical Review B60 (1999), 3169-3181.
15.
KarkiB.B. and StixrudeL.P., First-principles study of enhancement of transport properties of silica melt by water, Physical Review Letters (2010), 744-751.
16.
ShakyaS.S., KarkiB.B. and ZhangJ., Analyzing molecular dynamics scattered data for large atomic movements, Computational Materials Science95 (2014), 198-206.
17.
NijssenS. and KokJ.N., A quickstart in frequent structure mining can make a difference, in: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2004), 647-652.
18.
HsiehH.-P. and LiC.-T., Mining temporal subgraph patterns in heterogeneous information networks, in: Proceedings of the 2010 IEEE Second International Conference on Social Computing, (2010), 282-287.
19.
LiY., LinQ., ZhongG., DuanD., JinY. and BiW., A directed labeled graph frequent pattern mining algorithm based on minimum code, in: Proceedings of the 2009 Third International Conference on Multimedia and Ubiquitous Engineering, (2009), 353-359.
20.
AsaiT., AbeK., KawasoeS., SakamotoH. and ArikawaS., Efficient substructure discovery from large semi-structured data, in: SIAM SDM, (2002), 158-174.
21.
ZakiM.J., Efficiently mining frequent trees in a forest, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2002), 71-80.
22.
InokuchiA., WashioT. and MotodaH., An apriori-based algorithm for mining frequent substructures from graph data, in: PKDD, (2000), 13-23.
23.
KuramochiM. and KarypisG., Grew-a scalable frequent subgraph discovery algorithm, in: Proceedings of the Fourth IEEE International Conference on Data Mining, (2004), 439-442.
24.
WaleN., NingX. and KarypisG., Trends in Chemical Graph Data Mining, Springer, 2010, pp. 581-606.
25.
OzkanlarA., KelleyM.P. and ClarkA.E., Water organization and dynamics on mineral surfaces interrogated by graph theoretical analyses of intermolecular chemical networks, Minerals4(1) (2014), 118-129.
26.
OzkanlarA. and ClarkA.E., Chemnetworks: A complex network analysis tool for chemical systems, J Comput Chem35(6) (2014), 495-505.
27.
WaleN., WatsonI.A. and KarypisG., Comparison of descriptor spaces for chemical compound retrieval and classification, Knowledge and Information Systems14 (2008), 347-375.
28.
WassermannA.M., GeppertH. and BajorathJ., Searching for target-selective compounds using different combinations of multiclass support vector machine ranking methods, kernel functions, and fingerprint descriptors, J Chem Inf Model (2009).
29.
MahéP. and VertJ.-P., Graph kernels based on tree patterns for molecules, Machine Learning75(1) (2009), 3-35.
30.
ChenY.Z. and UngC.Y., Prediction of potential toxicity and side effect protein targets of a small molecule by a ligand-protein inverse docking approach, J Mol Graph Model20(3) (2001), 199-218.
31.
BorgwardtK.M., OngC.S., SchonauerS., VishwanathanS.V., SmolaA. and KriegelH.P., Protein function prediction via graph kernels, BMC Bioinformatics21 (2005), 47-56.
32.
DeshpandeM., KuramochiM., WaleN. and KarypisG., Frequent substructure-based approaches for classifying chemical compounds, IEEE TKDE17(8) (2005), 1036-1050.
33.
TatsisV.A., TjortjisC. and TzirakisP., Evaluating data mining algorithms using molecular dynamics trajectories, International Journal of Data Mining and Bioinformatics8(2) (2013), 169-187.
ShachterR.D., Probabilistic inference and influence diagrams, Operations Research36(4) (1988), 589-604.
36.
HowardR.A. and MathesonJ.E., Influence diagrams, Decision Analysis2(3) (2005), 127-143.
37.
PearlJ., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
38.
CooperG.F. and HerskovitsE., A bayesian method for the induction of probabilistic networks from data, Machine Learning9(4) (1992), 309-347.
