In recent years graph pattern mining took a prominent role in knowledge discovery in many scientific fields. From Web advertising to biology and finance, graph data is ubiquitous making pattern-based graph tools increasingly important. When it comes to financial settings, data is very complex and although many successfully approaches have been proposed often they neglect the intertwined economic risk factors, which seriously affects the goodness of predictions. In this paper, we posit that financial risk analysis can be leveraged if structure can be taken into account by discovering financial motifs. We look at this problem from a graph-based perspective in two ways, by considering the structure in the inputs, the graphs themselves, and by taking into account the graph embedded structure of the data. In the first, we use gBoost combined with a substructure mining algorithm. In the second, we take a subspace learning graph embedded approach. In our experiments two datasets are used: a qualitative bankruptcy data benchmark and a real-world French database of corporate companies. Furthermore, we propose a graph construction algorithm to extract graph structure from feature vector data. Finally, we empirically show that in both graph-based approaches the financial motifs are crucial for the classification, thereby enhancing the prediction results.

Introduction

Nowadays, data is naturally structured in form of trees or graphs, which are structures that may convey important information. A graph is a general and powerful data representation formalism, which found widespread application in many scientific fields. Finding subgraphs capable of compressing data by abstracting instances of the substructures and identifying interesting patterns is thus crucial. The awareness of big data together with the poor understanding of the processes that generate data has enforced techniques to extract frequent structural patterns from such data [27]. Graph mining techniques are sought for a class of problems lying on the crossroads of several research topics including graph theory, data sensing, data mining and data visualization. Graphs are very important mathematical structures that can represent information in many real world domains such as chemistry, biology and, web and text processing. Examples are protein interactions, phylogenetic trees, and molecular graphs [5], computer networks [18], hypertextual and XML documents, social networks, mobile call networks, to name a few [32]. Pattern mining takes essentially two approaches: statistical learning and structural. In the statistical learning, patterns are represented by feature vectors x = (x1, · · · , xn) ∈ IRn of n measurements. It has two main drawbacks: first, the vectors uphold a predefined set of features, despite the size and complexity of the objects they represent; second, the binary relationships among (parts of) objects cannot be captured. The above pitfalls, size constraints and lack of ability to represent relationships, might prevent to expose better models. In the structural approach, patterns are represented by graphs that can overcome above limitations with their inherent structure. Yet the complexity increases, for instance, it takes exponential time for finding the isomorphism between two graphs while linear time is needed for the similarity of two features vectors [6]. In this paper, in the settings of financial risk analysis we take two approaches for graph-based pattern mining. In the first, subgraph mining is employed based on an isomorphism search between two graphs, while, in the second, the goal is to learn a low-dimensional subspace spanned by projected vectors, which are dominant for preserving the intrinsic data structure.