GRAPH DATA MINING

[9] Inderjit S. Dhillon. Co-clustering documents and words using bipartitespectral graph partitioning. In Knowledge Discovery and Data Mining,pages 269–274, 2001.[10] J. L. Durant, B. A. Leland, D. R. Henry, and J. G. Nourse. Reoptimizationof mdl keys for use in drug discovery.[r]

ligands ([40]), mining databases to retrieve other relevant compounds, cluster-ing of chemical compounds based on common sub-structures, and predictingTrends in Chemical Graph Data Mining 583compound bioactivity by classification, regression and ranking techniques ([2],[28[r]

have become available. However, the vast majority of these approaches relyon object representations given in terms of feature vectors. Such object repre-sentations have a number of useful properties. For instance, the dissimilarity,or distance, of two objects can be easily computed by means of the E[r]

The measures described above set an absolute standard for what constitutesa dense component. Another approach is to find the most dense components ona relative basis. This is the domain of clustering. It may seem that clustering,a thoroughly-studied topic in data mining with many excell[r]

graphs, Bell System Tech. Journal, vol. 49, Feb. 1970, pp. 291-307.[117] M S. Kim, J. Han. A Particle-and-Density Based Evolutionary Cluster-ing Method for Dynamic Networks, VLDB Conference, 2009.[118] J. M. Kleinberg. Authoritative Sources in a Hyperlinked Environment.Journal of the ACM, 46(5):pp.[r]

predicate and object may be a variable. The SPARQL query processor willsearch for sets of triples that match the triple patterns, binding the variables inthe query to the corresponding parts of each triple [154].Another line of work in graph indexing uses important structural charac-teristics[r]

[26] Kenneth L. Calvert, Matthew B. Doar, and Ellen W. Zegura. Model-ing Internet topology. IEEE Communications Magazine, 35(6):160–163,1997.[27] Jean M. Carlson and John Doyle. Highly optimized tolerance: A mecha-nism for power laws in designed systems. Physical Review E, 60(2):1412–1427, 1999.[28][r]

[18] D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense sub-graphs in massive graphs. In VLDB ’05: Proc. 31st Intl. Conf. on VeryLarge Data Bases, pages 721–732. ACM, 2005.[19] A. V. Goldberg. Finding a maximum density subgraph. Technical report,UC Berkeley, 1984.[20] G. Grimmett. P[r]

Drug discovery is a time consuming and extremely expensive undertak-ing. Graphs are natural representations for chemical compounds. In chemicalgraphs, nodes represent atoms and edges represent bonds between atoms. Bi-ology graphs are usually on a higher level where nodes represent amino acidsand edg[r]

336 MANAGING AND MINING GRAPH DATA[42] N. Pr»zulj, D. Wigle, and I. Jurisica. Functional topology in a network ofprotein interactions. Bioinformatics, 20(3):340–348, 2004.[43] R. Rymon. Search through systematic set enumeration. In Proc. ThirdIntl. Conf. on Knowledge Representat[r]

vectorization operator. The left hand side requires 𝑂(𝑀2𝑁2) time, while theright hand side requires only 𝑂(𝑀𝑁(𝑀 + 𝑁 )) time. Notice that this trick(“vec-trick”) has recently been used in link prediction tasks as well [20].A random walk can trace the same edge back and forth many times (“tot-tering”)[r]

graphs, without the need to explicitly enumerate the walks. In order to han-dle continuous labels the random walk kernel has been extended in [5]. Thisextension allows one to also take non-identically labeled walks into account.A third class of graph kernels is given by diffusion kernels. The[r]

can reach 𝑣 (3rd hop). The algorithm to compute the 3-hop cover codes issimilar to the algorithm to compute the 2-hop cover codes. The only differenceGraph Reachability Queries: A Survey 205is that it needs to consider the set of pairs that can be encoded by each chainrather than each node. The time[r]

𝑗and 𝐺𝑖∕= 𝐺𝑗. Schenkelet al. compute the 2-hop cover for 𝐺 by encoding all reachability via (𝑢, 𝑣)according to the following two operations.For all 𝑎 ∈ 𝑎𝑛𝑐𝑠(𝑢), 𝐿𝑜𝑢𝑡(𝑎) ← 𝐿𝑜𝑢𝑡(𝑎) ∪{𝑢}, andFor all 𝑑 ∈ 𝑑𝑒𝑠𝑐(𝑣) ∪{𝑣}, 𝐿𝑖𝑛(𝑑) ← 𝐿𝑖𝑛(𝑑) ∪{𝑢}.It means that, 2-hop clusters, (𝑎𝑛𝑐𝑠(𝑢), 𝑢, 𝑑𝑒𝑠𝑐(𝑢)), for all cro[r]

find subgraphs with the highest statistical significance, one has to enumerateall the frequent subgraphs first, and then calculate their p-value one by one.Obviously, this two-step process is not scalable due to the following two rea-sons: (1) for many objective functions, the minimum frequency thresho[r]

of each 𝛿-TCFG, which is resident in disk. Using this two-level index structure,many graph queries could be processed directly without verification.2.5 TreesZhao et al. [38] analyzed the effectiveness and efficiency of paths, trees, andgraphs as indexing features from three aspects: feature siz[r]

trieval by node attributes and search without the optimized order on the base-line space. The query processing time in the “Optimized" case is improvedgreatly due to the reduced search space.The SQL-based approach takes much longer time and does not scale to largeclique queries. This is due to the u[r]

paths, and graphs. As in OQL, GOQL uses the usual select from wherestatement to specify queries. In addition, it uses temporal operators next, un-til and connected to define path formulas. The path formulas can be used aspredicates on sequences and paths in the queries. For query processing, GOQLtran[r]

to be a set cover problem. Cohen et al. propose an approximate algorithm toconstruct an index in 𝑂(𝑛𝑚1/2) space. The time complexity for constructingsuch an index remains open. In [26], the conjecture is 𝑂(𝑛3⋅∣𝑇 𝐶∣) where ∣𝑇 𝐶∣is the size of the edge transitive closure of 𝐺. Several efficient algorit[r]

The matching process of SAGA has three steps. The first step is to findsmall hits. In this step, the query graph is broken into small fragments and thegraph index is probed to find database fragments that are similar to the queryfragments. The second step is to assemble small hits retrieved in t[r]