Decision trees have advantages such as high model interpretability and low computational complexity. However, because they grow trees greedily, they cannot optimize the learnable parameters of entire trees. By contrast, Soft Trees use both decision trees and neural networks to optimize learnable parameters of entire trees by inducing the trees end-to-end. Generally, the smaller the decision trees, the better their generalization performance and interpretability. However, the Probabilistic Decision Tree (PDT), a type of Soft Tree, tends to construct larger trees. To overcome this difficulty, we propose the Adaptive Soft Tree (AST) to construct small soft trees. In our AST, each sample has a weight that quantifies the amount of emphasis that should be placed on the sample. AST assigns larger weights to samples that are misclassified by the tree at a certain point in time. AST focuses on samples with large weights and repeats growing the tree. In our experiments, we show that our AST constructs small trees with fewer leaves and achieved better classification accuracy than PDT on several benchmark datasets.

Although graph neural networks (GNNs) are powerful tools for analyzing data that can be represented as a graph, they generally suffer from the problem of over-smoothing as the number of layers in the networks increases. This paper focuses on two recent methods for overcoming this problem, namely JKNet-lstm and TwinGNN, and presents a simpler GNN interface that achieves a similar reduction in over-smoothing and its implementations that require much lower computational cost. The proposed approach utilizes the relationship between the convolution operation in GNNs and the reproductive property of the normal distribution. In particular, our method does not require any computationally intensive long short-term memory calculations, and achieves complexity that is independent of the number of layers in the GNN. We present mathematical arguments to prove that our proposed interface achieves the same functionality as JKNet-lstm and TwinGNN, and perform experiments on six benchmark datasets to demonstrate the remarkable performance of our method in terms of the classification accuracy, computational cost, and degree of over-smoothing. Overall, the proposed interface enables complex graph network structures to be analyzed at reasonable computational cost with no loss of accuracy.

Clustering vertices in graphs or in sequences of graphs has important applications in network science, bioinformatics, and other areas. Most research to date has focused on static graphs or sequences where the number of vertices does not change. We propose a new algorithm that successfully partitions the vertices of a graph sequence into smooth clusters, even when the number of vertices is allowed to vary over time. Our approach uses spectral clustering and relies on applying the k partition problem to a graph constructed from the input graph sequence. Several experiments demonstrate the performance of our method and its advantages over existing methods.

Kernel methods such as Support Vector Machines (SVMs) are becoming increasingly popular because of their high performance on graph classification problems. In this paper, we propose two novel graph kernels called the Hadamard Code Kernel (HCK) and the Shortened HCK (SHCK). These kernels are based on the Hadamard code, which is used in spread spectrum-based communication technologies to spread message signals. The proposed graph kernels are equivalent to the Neighborhood Hash Kernel (NHK), one of the fastest graph kernels, and comparable to the Weisfeiler-Lehman Subtree Kernel (WLSK), one of the most accurate graph kernels. The fundamental performance and practicality of the proposed graph kernels are evaluated using three real-world datasets.

The mining of a complete set of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences (dynamic graphs or evolving graphs). In this paper, we define a novel class of subgraph subsequence called an “induced subgraph subsequence” to enable efficient mining of a complete set of frequent patterns from graph sequences containing large graphs and long sequences. We also propose an efficient method to mine frequent patterns, called “FRISSs (Frequent Relevant, and Induced Subgraph Subsequences)”, from graph sequences. The fundamental performance of the method has been evaluated using artificial datasets, and its practicality has been confirmed through experiments using a real-world dataset.

In recent years, the mining of a complete set of frequent subgraphs from labeled graph data has been extensively studied.However, to our best knowledge, almost no methods have been proposed to find frequent subsequences of graphs from a set of graph sequences. In this paper, we define a novel class of graph subsequences by introducing axiomatic rules of graph transformation, their admissibility constraints and a union graph. Then we propose an efficient approach named "GTRACE'' to enumerate frequent transformation subsequences (FTSs) of graphs from a given set of graph sequences. Its fundamental performance has been evaluated by using artificial datasets, and its practicality has been confirmed through the experiments using real world datasets.

We consider a regression problem where target values are given as intervals, and propose a statistical approach to it. Although it is hard to solve the optimization problem directly, we propose an approximation method based on the EM algorithm. Experiments using the benchmark datasets show effectiveness of our approach.

There are increasingly visible demands for structured/ unstructured information integration and advanced analytics. However, conventional database technology has not been able to present a robust and practical implementation of a truly integrated architecture for such purposes. After working on several industrial applications (in particular, in the healthcare and life sciences area), we have identified fundamental issues and technical approaches to tackle the issues. In this paper, we propose data representations and algebraic operations for integrating semantic information (e.g., ontologies) into OLAP systems, which allow us to analyze a huge set of textual documents with their underlying semantic information. The performance of the prototype implementation has been evaluated using real world datasets, and the high scalability and flexibility of our approach have been confirmed with respect to the computation time.

The problem of mining frequent itemsets in transactional data has been studied frequently and has yielded several algorithms that can find the itemsets within a limited amount of time. Some of them can derive "generalized" frequent itemsets consisting of items at any level of a taxonomy (Srikant and Agrawal, 1995). Several approaches have been proposed to mine frequent substructures (patterns) from a set of labeled graphs. The graph mining approaches are easily extended to mine generalized patterns where some vertices and/or edges have labels at any level of a taxonomy of the labels by extending the definition of "subgraph". However, the extended method outputs a massive set of the patterns most of which are over-generalized, which causes computation explosion. In this paper, an efficient method is proposed to discover all frequent patterns which are not over-generalized from labeled graphs, when taxonomies on vertex and edge labels are available.

In recent years, the problem of mining association rules over frequent itemsets in transactional data has been frequently studied and yielded several algorithms that can find association rules within a limited amount of time. Also more complex patterns have been considered such as ordered trees, unordered trees, or labeled graphs. Although some approaches can efficiently derive all frequent subgraphs from a massive dataset of graphs, a subgraph or subtree that is mathematically defined is not necessarily a better knowledge representation. We propose an efficient approach to discover significant rules to classify positive and negative graph examples by estimating a tight upper bound on the statistical metric. This approach abandons unimportant rules earlier in the computations, and thereby accelerates the overall performance. The performance has been evaluated using real world datasets, and the efficiency and effect of our approach has been confirmed with respect to the amount of data and the computation time.