In the literature, several methods have been proposed for the analysis of network data, but they usually focus on homogeneous networks. More recently, the complexity of real scenarios has impelled researchers to design classi cation and clustering methods able to work also on heterogeneous networks, which consist of di erent types of objects and links. However, they often make assumptions on the structure of the network that are too restrictive or do not exploit di erent forms of network correlation and autocorrelation. Moreover, when several nodes of the network have missing values, standard methods can lead to either building incomplete classi cation models or to discarding relevant dependencies (correlation or autocorrelation). In this discussion paper, we describe an ensemble learning approach for multi-type classi cation that we proposed recently, which is able to exploit i) the possible presence of correlation and autocorrelation phenomena, and ii) the classi cation of instances (with missing values) of other node types in the network. Experiments performed on real-world datasets show that the proposed method is able to signi cantly outperform state-of-the-art algorithms.
In the real world we can easily nd objects which appear to be connected to each other, thus forming complex networks. Connections among these objects can represent di erent types of relationships, which can be found in several elds, including biology, epidemiology, geography, nance, etc. Most of the works in the literature about mining networked data focus on homogeneous networks, where all the objects are of the same type (and can, accordingly, be represented by a prede ned set of features/characteristics) and the links among them describe a single type of relationship. A common example of a homogeneous network is that of social networks: objects represent people and links represent the friendship relationships. However, real scenarios are more complex due to the presence of multiple types of objects that are connected through di erent types of links, forming heterogeneous networks. For example, in well-known databases about movies (e.g., IMDb) we have movies, actors, users, tags, etc. In the bio-medical domain, databases contain genes, proteins, tissues, pathways and diseases. In all these cases, objects of di erent types establish di erent types of relationships.
Consequently, recent works have proposed new data mining methods that
work on heterogeneous information networks. For example, in [
In this discussion paper, we describe the approach proposed in [
Before describing the proposed method, in the following we introduce the notation used. We work on heterogeneous networks, which we formally de ne as G = (V; E), where V is the set of nodes and E is the set of edges among nodes. Both nodes and edges can be of di erent types. Moreover:
Each node type Tp implicitly de nes a subset of nodes Vp V .
Each node v0 2 V is associated with a node type tv(v0) 2 T , where T is the nite set fTpg of all the possible types of nodes in the network.
A node type Tp de nes a set of attributes Xp = fXp;1; Xp;2; : : : ; Xp;mp g.
An edge type Rj de nes a subset of edges Ej (Vp Vq) E, where Vp and Vq are not necessarily based on di erent types.
An edge e between two nodes v0 and v00 is associated with an edge type Rj 2 R, where R is the nite set fRj g of possible edge types in the network.
In the considered task, we de ne a role for each node type: Tt (primary targets), which are considered as the targets of the main classi cation task; Tst (secondary targets), which are strongly related to the main classi cation task, for which a prediction of missing values is considered relevant; Ttr (task-relevant), which are the other node types. An example is reported in Figure 1. Only nodes of target (primary and secondary) types are actually classi ed, on the basis of all the nodes. However, we are actually interested in the maximization of the prediction accuracy only of objects of the primary target types. 3
In this section we describe the two solutions ST-MrSBC and MT-MrSBC. Both
take as input a partially labeled heterogeneous network and work iteratively. At
each iteration, they build an ensemble of Mr-SBC [
Following the idea in [
Once the order of analysis has been de ned, MT-MrSBC samples a subset of nodes of the rst target type and builds a weak (since built from a subset of instances) predictive model through Mr-SBC. This predictive model is applied to classify unlabeled nodes which are then added to the labeled network. The obtained probabilities are also stored for the nal combination of the outputs. Then, we select a new target type and repeat the process. Note that, at this stage, predictions performed for the previous target types are available to Mr-SBC when building a prediction model for the new target. Target types are shu ed again every time they are all processed. The number of iterations is limited by a user-de ned threshold and the outputs obtained for each target type over all the iterations are combined to obtain the nal (strong) predictive model. ST-MrSBC uses a similar process, but works on a single target type. Therefore, it exploits predictions obtained on the same target type in the previous iterations. The main di erence with respect to the standard self-training is in the construction of the labeled network when a new iteration starts. Speci cally, ST-MrSBC builds an ensemble of weak classi ers from di erent subsets of labeled nodes, instead of considering only the output of the last iteration.
At each iteration, we select the target attribute of the next target type and build two separate networks: the rst contains only labeled nodes, and the second contains only unlabeled nodes. These networks are built by considering the complete network and by removing unlabeled and labeled nodes, respectively. This means that all the nodes of other target types, as well as nodes of task-relevant types, are included in both networks. While the network of labeled nodes, for each target type, changes at di erent iterations, the network of unlabeled nodes remains stable and the algorithm classi es the same nodes several times.
The way nodes are considered as training instances at each iteration is
random. In fact, the algorithm randomly selects, according to a uniform distribution,
a given percentage perc of labeled nodes from the labeled network. Note that,
at a given iteration, the labeled network could contain also nodes that were
initially unlabeled but that were classi ed during a previous iteration. In the case
of ST-MrSBC, the last available predictions will regard the same target type,
whereas in the case of MT-MrSBC, the last available predictions will regard all
the target types (primary and secondary). This behavior is coherent with the
assumption that predictions performed on other target types (primary or
secondary) can help in the predictions of the label of nodes of the current target
type. This implies that, at the next iteration, the algorithm will take into account
some labels predicted at the previous iterations. This choice is, apparently, in
contrast with most of the self-training approaches, which usually select the most
reliable predictions for the next iterations. However, 1) this solution does not
necessarily lead to better results with respect to a random selection [
At the end of each iteration, we build a classi cation model through Mr-SBC for
the current target type from the network of labeled nodes. We remind that
MrSBC is a nave Bayes classi er which relies on a set of rst-order rules induced
from data stored in the tables of a relational database (see [
For each unlabeled node v0, the identi ed classi cation model is exploited to compute the posterior probability (which takes into account both network correlation and network autocorrelation) and its label t(v0), according to the following equation based on the Bayes' theorem: t(v0) = argmaxYc P (YcjRv0 ) = argmaxcP (Yc) P (Rv0 jYc)=P (Rv0 ); (1) where Yc is a possible class value of the target attribute y, and Rv0 RD is the subset of rst-order rules, identi ed by Mr-SBC, covering the object v0.
The labeled nodes are then added to the labeled network for the subsequent iterations, as described before. The probabilities are exploited at the end of the entire process. In fact, after the last iteration, the nal classi er combines the probabilities computed during all the iterations: for each target type Tt and for each node v0, the method computes the nal probability as the average of the probabilities computed over the ensemble in the following way:
z t(v0) = argmaxc 1 X P (YcjRv0k) = argmaxc z k=1 k=1
z
1 X P (Yc)P (Rv0kjYc) ;
z P (Rv0k)
(2)
where z is the number of iterations, i.e., the number of classi ers in the ensemble,
for each target type (the total number of iterations is z jLtj) and Rv0k is the set
of rules identi ed from the labeled network at the k-th iteration. The rationale
behind the combination in Equation (2) is twofold: a) the predictions obtained at
each iteration are based on di erent training sets, which may focus on di erent
properties of the concept to be learned; b) the predictions are made more stable.
We performed our experiments on ve heterogeneous networks: MOVIE, NBA,
YELP, IMDB and STACK. Some quantitative information about these datasets
can be found in Table 4, while additional information can be found in [
In order to perform a comparison with other systems, we also ran the
experiments with four competitor methods. In particular, we considered i) the
relational version of the nearest neighbour algorithm (RelIBK), ii) the SVM-based
algorithm SMO (RelSMO), iii) the algorithm GNetMine [
As regards the parameter setting of ST-MrSBC and MT-MrSBC, we considered a random sampling of 20% of nodes for each classi er in the ensemble and the number of iterations for each target type z ranging from 1 to 50.
We collected all the classi cation accuracy values and performed the Nemenyi post-hoc tests on single datasets, on all the datasets and on the reduced datasets for the comparative evaluation. The result of the statistical tests are depicted in Figure 3. In particular, we can observe that for the datasets NBA and for the target type users of the dataset Yelp, the improvement provided by LexicographicMT-MrSBC and RandomMT-MrSBC over the competitors is statistically signi cant at p-value= 0:05. Focusing on LexicographicMT-MrSBC, we observe two specular and interesting cases: for the dataset IMDB it provides the best result, while for the target type Business of the dataset Yelp it appears to be the worst approach. This instability is again caused by the static ordering on the target types. Indeed, in the rst case, the exploitation of the dependency movies ! users (which is surely strong, if we observe the result) led LexicographicMT-MrSBC to obtain a better result with respect to RandomMT-MrSBC, which alternatively (and randomly) exploited the dependencies movies ! users and users ! movies (which appears weak). On the contrary, in the second case, the static (unlucky) choice of the dependency to be exploited brought LexicographicMT-MrSBC to the bottom of the ranking.
Finally, the results obtained by our comparative evaluation (Figure 3 - last chart) shows that the improvement provided by the proposed method is able to give Mr-SBC the advantage of outperforming the competitors Indeed, the original Mr-SBC is not able to outperform the considered competitors, while the ensemble learning (ST-MrSBC) leads to outperform all the competitors (although not statistically w.r.t. HENPC and RelIBk). The advantage comes from the combination of capturing label dependencies between multiple types and of the ensemble learning approach (MT-MrSBC), which improves the accuracy.
Overall, we can conclude that the application of the proposed method, which is able to capture both correlation and autocorrelation phenomena, as well as to predict missing values, by exploiting the same classi cation method adopted for primary targets, can lead to better, more stable predictions when applied to real-world data organized in heterogeneous networks. Fig. 3. Results of the Nemenyi post-hoc test on the average accuracy. Better algorithms are positioned on the right-hand side, and those that do not signi cantly di er in performance (at p-value = 0:05) are connected with a line.
In this paper, we proposed an extension of the system Mr-SBC which works on heterogeneous networks and that is able to solve multi-type classi cation tasks, by capturing both correlation and autocorrelation phenomena. Experiments performed on real datasets show that both the proposed variants are able to significantly outperform the original Mr-SBC, especially with a random ordering of the target types, as well as four other well-known competitor algorithms.
As future work, we plan to study the sensitivity to the sampling size and the possibility to select only a subset of labeled nodes for the next iteration.
We would like to acknowledge the European project MAESTRA - Learning from Massive, Incompletely annotated, and Structured Data (ICT-2013-612944).