Clustering-Based Relational Unsupervised Representation Learning with an Explicit Distributed Representation

1 Introduction

Every machine learning task inherently depends on the quality of provided features. A good set of features is thus a crucial precondition for the good performance of any classifier. Yet, finding such a set in practice has proven to be a tedious and time-consuming task. Furthermore, substantial domain knowledge and exploration are often required. To address this issue, representation learning [Bengio, 2009] focuses on automatic learning of good multi-level data representations.

One of the prominent paradigms within representation learning, and the one this work focuses on, is unsupervised representation learning (URL) [Hinton and Salakhutdinov, 2006; Bengio et al., 2007; Ranzato et al., 2007]. These approaches take a generative stance on learning a feature hierarchy and require no supervision. As supervision is ignored, the obtained representation are not tailored for one specific task but can rather be shared among multiple tasks. Intuitively, these methods find useful features by compressing the original data by means of a multiple-clustering procedure, in which an instance can belong to more than one cluster. The obtained features indicate cluster assignments of instances and, thus, a classifier learns from cluster memberships instead of the original data.

One major limitation of the existing approaches is that they focus on vectorized data representations. Hence, the ubiquitous and abundant structured and relational data, which additionally describes relationships between instances, are not well supported. This data is often viewed as a hypergraph 1 , in which instances form vertices and their relationships form hyperedges. Such data emerges in many real-life problems. For instance, chemical and biological data describing molecules or protein interaction networks are naturally expressed in graphstructured formats. In social networks, many instances interact with each other. Relational data is commonly expressed in predicate logic, a powerful language unifying the representation of vectors, graphs and sequences. This, consequently, subsumes any data stored in a relational database.

Here we focus on the problem of unsupervised learning a feature hierarchy with relational data. To this end, we introduce CUR2LED - a clustering-based unsupervised relational representation learning with explicit distributed representation. CUR2LED is inspired by the work of Coates et al. (2011) in which the authors introduce a general pipeline for learning a feature hierarchy by means of clustering. Assuming a spatial order of features (i.e., pixels), the introduced framework (i) extracts image patches, i.e., subsets of pixel from the original images candidating as a potential high-level feature, (ii) pre-processes each patch (e.g. normalization), and (iii) learns a feature-mapping by clustering image patches. The authors show that such general procedure with a simple k-means algorithm can perform as well as the specialized algorithms, such as auto-encoders and Restricted Boltzmann machines.

CUR2LED learns a new representation by clustering both instances and their relationships. A distinctive feature of CUR2LED is that the relational structure is preserved throughout the hierarchy, contrasted to the existing approaches that replace relational structures with vectors. Another distinctive feature is the notion of similarity interpretation. When clustering relational data, a similarity of relational objects is an ambiguous concept. Two relational objects might be similar according to their attributes, relationships, or a combination of both. The notion of similarity interpretation precisely states the exact source of similarity used.

CUR2LED exploits this ambiguity to its advantage by using the similarity interpretations to encode a distributed representation of data - one of the pillars underlying the success of representation learning methods. Intuitively, it refers to a concept of reasonably-sized representation that captures a huge number of possible configurations [Bengio et al., 2013]. In contrast to the one-hot representations which require N parameters to represent N regions, distributed representations require N parameters to represent up to 2N regions. The main difference is that a concept within a distributed representation is represented with several independently manipulated factors, instead of exactly one factor as with one-hot representations. Thus, such representations are substantially more expressive. The similarity interpretation defines the exact factors that can be manipulated individually to represent individual concepts.

1 A hypergraph is a graph in which edges can connect more than two vertices.

The contributions of this paper include (i) a general framework for learning relational feature hierarchies by means of clustering, (ii) a principled way of generating distributed relational representations based on different similarity interpretations, (iii) a general framework for hyperedge clustering and (iv) the experimental evaluation of the proposed framework.

In the following section, we briefly review related work. Next, we outline our approach and discuss arising issues in Section 3. We then briefly present the similarity measure used for clustering relational data, discuss its extension towards hyperedge clustering, and formally define the notion of similarity interpretation. Experimental results are discussed in Section 5.

2 RelatedWork

Clustering has been previously recognized as an effective way of enhancing relational learners. Popescul and Ungar (2004) apply k-means clustering to instances, create predicates for new clusters and add them to the original data. Multiple relational clustering (MRC) [Kok and Domingos, 2007; 2008] is a relational probabilistic clustering framework based on Markov logic networks [Richardson and Domingos, 2006] clustering both vertices and relationships. Both approaches are instances of predicate invention [Kramer, 1995; Craven and Slattery, 2001], concerned with extending the vocabulary given to a learner by discovering novel concepts in data. CUR2LED differs in several ways. Whereas Popescul and Ungar develop a method specifically for document classification, CUR2LED is a general off-the-shelf procedure that can be applied to any relational domain. Moreover, CUR2LED clusters both instances and relations, whereas Popescul and Ungar cluster only instances. In contrast to MRC which does not put any assumptions in the model, CUR2LED is a more informed approach that explicitly defines different notions of relational similarity to be used for clustering. Though MRC was used as a component in structure learning, it does not provide new language constructs, but simplifies the search over possible formulas. CUR2LED learns a model directly from the new features.

A related problem is community detection [Karypis and Kumar, 1998; Fortunato, 2010] concerned with identifying a densely connected components in graphs. CUR2LED considers a more general problem in which disconnected vertices (and edges) can form clusters as well.

Much of the recent work focused on embedding relational data into vector spaces [Nickel et al., 2016; Niepert, 2016; Bordes et al., 2011; 2013; Niepert et al., 2016]. The essential idea behind these approaches is to map relational concepts to a low-dimensional vectors spaces, and replace logical reasoning with algebra. Rather than inventing an Euclidean space of relational instances, CUR2LED relies on clustering and a variety of similarity measures to create new features.

3 Representation Learning via Clustering

The complexity of relational data causes several issues in devising a general relational feature hierarchy: (1) what should be clustered, (2) how to estimate a similarity in relational data, and (3) how to choose the structure of a feature hierarchy?

(1) In the i.i.d. case (drawn independently from the same population), the dataset contains only instances and their features, thus, one clusters the instances. However, relational data additionally describes relationships among instances and varies from a single large network of many interconnected entities (a mega-example) to a set of many disconnected networks where each network is an example. Ideally, one would address both cases. CUR2LED assumes that relational data is provided as a labelled hypergraph, where examples form vertices and relations between them form hyperedges, and does not make a distinction between the above-mentioned cases. Formally said, the data structure is a typed, labelled hypergraph H = (V, E, τ, λ) with V being a set of vertices, E a set of hyperedges, τ a function assigning a type to each vertex and hyperedge, and λ a function assigning a vector of values to each vertex. CUR2LED learns a new representation by clustering both vertices and hyperedges in a hypergraph. Considering that vertices have associated types, CUR2LED does not allow mixing of types, i.e., a cluster can contain only vertices of the same type. The same holds for hyperedges which connect vertices of different types.

(2) The features are the only source of similarity between instances in the i.i.d. data. In the relational context, a similarity is an ambiguous notion that can originate in the features of relational objects, structures of their neighbourhoods (both feature- and relationship-wise), interconnectivity or graph proximity, just to name a few. Furthermore, which interpretation is needed for a particular task is not known in advance, making URL inherently more difficult. To find a representation effective for many tasks, CUR2LED addresses multiple interpretations of relational similarity simultaneously. How exactly that is achieved is discussed in the next section, together with a similarity measure used for this purpose.

(3) Defining a feature hierarchy requires the specification of the number of layers and the number of hidden features (i.e., clusters) within each layer. How to automatically construct such hierarchies is currently under-explored. Consequently, the performance of these methods is sensitive to the parameter setting, requiring substantial expertise in order to choose the optimal number of features. This constitutes a major bottleneck for relational type-aware feature hierarchies, as separate values should be chosen for each type in data (and combination thereof for hyperedges).

To tackle this infeasibility, CUR2LED builds upon a vast literature on the clustering selection problem [Arbelaitz et al., 2013], which is concerned with the selection of optimal number of clusters from data. This automatic clustering selection strategies mitigate the problem of the manual specification of feature hierarchies. CUR2LED leverages two distinct approaches: (1) a difference-like criterion [Vendramin et al., 2010], and (2) a quality based criterion of Silhouette index [Rousseeuw, 1987].

Difference-like criteria assess relative improvements on some relevant characteristic of the data (e.g. within-cluster similarity) over a set of successive data partitions produced by gradually increasing the number of clusters (N). It attempts to identify a prominent knee - a point when the given quality measure saturates and the further increase of N can offer only marginal benefit. Following the suggestion in [Vendramin et al., 2010], we choose the number of clusters as the one that achieves the highest value of the following formula:

where C(k) is the intra-cluster similarity, k is the number of clusters and α a user-specified penalty on the number of clusters.

The Silhouette index evaluates a cohesion, i.e., how similar an instance is to its own cluster, and a separation, i.e., how similar an instance is to the other clusters. It is defined as:

where i is an instance, a(i) is an average dissimilarity of i to the rest of the instances in the same cluster, and b(i) the lowest dissimilarity of i to any other cluster. Higher values indicate a better fit of the data.

C-representation. Once the clusters are obtained, we will represent them in the following form. For each cluster of vertices we create a unary predicate in the form of clusterID(vertex) where vertex is an identifier of a specific vertex. Similarly, for each cluster of hyperedges we create a n-ary predicate in the form of clusterID(vertex1,...,vertexn), which takes an ordered set of n vertices as arguments. Truth instantiations of defined predicates reflect cluster memberships. We refer to the cluster-induced representation as a C-representation.

The introduced pipeline is illustrated in Figure 1. CUR2LED specified thus far describes a meta-procedure how to use any clustering algorithm to obtain a latent representation. In the experiments we use spectral and hierarchical clustering.

4 Similarity of Relational Structures

CUR2LED relies on ReCeNT [Dumanˇci´c and Blockeel, 2017], a relational clustering framework focused on clustering vertices in a hypergraph. What makes ReCeNT an attractive relational clustering framework is the wide range of similarities it considers. Furthermore, which similarity is used is easily adaptable with just a few parameters. We provide a concise and intuitive description here, and refer the reader to the original paper for the details.

The core concept of ReCeNT is a neighbourhood tree (NT). The NT is a rooted directed graph describing a neighbourhood of a certain vertex in the hypergraph. It provides a summary of all paths that can be taken, starting from that particular vertex. The depth of a NT, i.e., how many vertices a path can contain excluding the root vertex, is pre-specified. ReCeNT compares two vertices by comparing their NTs.

This comparison is achieved by first decomposing the NT into different multisets. The multiset V l t (g) contains all vertices of type t at distance l of a particular NT g. El (g) is the multiset of hyperedge labels between vertices of distances l and l +1. Finally, Bl t,a (g) is the multiset of values of attribute a observed among the nodes of type t at distance l. Using only these three types of multisets, one can express a wide range of similarities. What ReCeNT considers are:

1. the similarity of the root vertices in terms of attribute values, by means of B0 t,a
2. the similarity of attribute values of the neighbouring vertices, by means of Bl>0 t,a
3. the connectivity of the root vertices, by means of V l t
4. the similarity of neighbourhoods in terms of the vertex identities, by means of V l t
5. the similarity of hyperedge labels of two neighbourhoods, by means of El .

Each of the components represents a distinct notion of similarity. We will refer to them as core similarities. These core similarities can further be combined to represent more complex similarities.

4.1 Hyperedge Similarity

In its original form, ReCeNT clusters vertices in a hypergraph. To support hyperedge clustering with CUR2LED , we introduce a general framework for hyperedge similarity. It views hyperedges as ordered sets of vertices, and thus ordered sets of NTs.

Let N be a set of NTs. Let Θ denote summary operations on sets of values such as mean, minimum and maximum. Let Λ denote set operators such as union and intersection. Let f : N 2 → R be a similarity between two NTs, e.g. the similarity measure introduced by ReCeNT. The framework introduces two types of hyperedge similarity, namely combination and merging.

Definition 1. A combination similarity is a function c : N n × N n × Θ → R which compares two hyperedges, e1 = (v1 1 , ..., vn 1 ) and e1 = (v1 2 , ..., vn 2 ), by comparing the individual NTs respecting the order, s = (f(v1 1 , v1 2 ), . . . , f(vi1 , vi2 )), and summarizing respective similarities with θ ∈ Θ, θ(s).

Definition 2. A merging similarity is a function m : 2N × 2N × Λ → R which compares two hyperedges, e1 = (v1 1 , ..., vn 1 ) and e1 = (v1 2 , ..., vn 2 ), by first merging the NTs within a hyperedge with merging operator λ ∈ Λ, s1 = λ(v1 1 , . . . , vi1 ) and s2 = λ(v1 2 , . . . , vi2 ) and comparing the resulting NTs, f(s1, s2).

Merging two NTs involves merging their respecting multisets with a merging operator λ, respecting the level. For instance, consider set union as λ, and g′ and g′′ as the NTs to be merged. Then, merging the multisets V l t (g′ ) and V l t (g′′ ) results in a multiset V l t (λ(g′ , g′′ )) = V l t (g′ ) ∪ V l t (g′′ ).

Both formulations reduce the problem to the comparison of NTs, but offer alternative views. While merging ignores the order of vertices in a hyperedge, combination respects it. Accordingly, merging describes the neighbourhood of a hyperedge, while combination examines the similarity of vertices participating in a hyperedge. In this work we use union as the merging operator, and mean as the combination operator.

4.2 Similarity Interpretation

Finally, we formally introduce the notion of similarity interpretation.

Definition 3. Let (w1,w2,w3,w4,w5) be the weights associated with the core similarities. A similarity interpretation is the value assignments to the weights (w1, w2, w3, w4, w5).

Thus, it allows us to precisely control aspects of similarity considered for representation learning. For example, setting w1 = 1, w2,3,4,5 = 0 uses only the attributes of vertices for comparison. Setting w3 = 1, w1,2,4,5 = 0 on the other hand would identify clusters as a densely connected components. As the similarity interpretation is provided by the user, we say it explicitly defines the distributed representation.

5 Experiments and Results

Datasets. We have used the following 6 datasets to evaluate the potential of this approach. The IMDB dataset describes a set of movies with people acting in or directing them. The UW-CSE dataset describes the interactions of employees at the University of Washington and their roles, publications and the courses they teach. The Mutagenesis dataset describes chemical compounds and atoms they consist of. The WebKB dataset consists of pages and links collected from the Cornell University's web page. The Terrorists dataset describes terrorist attacks each assigned one of 6 labels indicating the type of the attack. The Hepatitis dataset describes a set of patients with hepatitis types B and C.

Evaluation procedure. In principle, a latent representation should make learning easier by capturing complex dependencies in data more explicitly. Though that is difficult to formalize, a consequence should be that a model learned on the latent representation is (i) less complex, and (ii) possibly performs better. To verify whether that is the case with the representation created by CUR2LED , we answer the following questions:

• (Q1) do representations learned by CUR2LED induce models of lower complexity compared to the ones induced on the original representation?
• (Q2) if the original data representation is sufficient to solve a task efficiently, does C-representation preserves the relevant information?
• (Q3) if the original data representation is not sufficient to solve the task, does a C-representation improve the performance of a relational classifier?
• (Q4) can the appropriate parameters for a specific dataset be found by the model selection?
• (Q5) how does CUR2LED compare to MRC, which is the closest related work?

In order to do so, we use TILDE [Blockeel and De Raedt, 1998], a relational decision tree learner, and perform 5-fold cross validation. C-representations and TILDE were learned on training folds, and the objects from the test fold were mapped to the C-representation and used to test TILDE. The following similarity interpretation were used for each dataset: (0.5,0.5,0.0,0.0,0.0), (0.0,0.0,0.33,0.33,0.34),

(0.2,0.2,0.2,0.2,0.2). The first set of weights uses only the attribute information, the second one only the link information, while the last one combines every component.

As a complexity measure of a model we use the number of nodes a trained TILDE model has. We use the following values for the α parameter in Equation 1: {0.1, 0.05, 0.01}. In the case of MRC, we used the following values for the λ parameter: {-1,-5,-10}. The λ parameter has the same role as α in the proposed approach, affecting the number of clusters chosen for each type 2 .

Results

To answer the above mentioned questions, we perform two types of experiments. Table 1 summarizes the results of cross validation. The accuracies on test set and the complexities of TILDE models are stated for both original and C-representations. Table 2 summarizes the results of the model selection where we dedicate one fold as a validation set, and perform the cross validation on the remaining folds to identify the best parameter values (i.e., the choice of a clustering algorithm, a clustering selection procedure and the appropriate hyperedge similarity) for each dataset.

Q1. Table 1 shows that the models learned on Crepresentation consistently have lower complexity than the ones learned on the original data. That is especially the case when C-representation is obtained by spectral clustering, which consistently results in a model of a lower complexity. The reduction of complexity can even be surprisingly substantial, for instance on the Mutagenesis and Hepatitis datasets where the model complexities are reduced by factors of 10 and 4, respectively. When the C-representation is obtained with hierarchical clustering, models of lower complexity are obtained on all datasets except the WebKB and UWCSE datasets. These results suggest that the C-representation in general makes complex dependencies easier to detect and express.

2 Note that it is difficult to exactly match the values of α and λ as both methods operate on different scales, and the authors do not provide a way how to choose an appropriate value

Q2. The IMDB and UWCSE datasets are considered as easy relational datasets, where the classes are separable by a single attribute or a relationship. Thus, TILDE is able to achieve almost perfect performance with the original data. The original representation is therefore sufficient to solve the task, and we are interested whether the relevant information will be preserved within the C-representation. The results in Table 1 do suggest so, as TILDE achieves identical performance regardless of the representation.

Q3. The remaining datasets are more difficult than the previously discussed ones. On the Mutagenesis, Hepatitis and WebKB datasets, C-representation improves the performance. On the Terrorists dataset, however, no improvement in performance is observed. What distinguishes this dataset from the others is that it contains only two edge types (indicating colocated attack, or ones organized by the same organization), an abundant number of features, while other datasets are substantially more interconnected. Thus, focusing on the relational information is not as beneficial as the features themselves.

These results suggest that C-representations indeed improve performance of the classifier, compared to the one learned on the original data representation. First, the C-representation created with spectral clustering consistently performs better on all datasets, except the Terrorists one. Second, if the learning task does not have a strong relational component, then Crepresentations are not beneficial and can even hurt the performance. Third, the choice of a clustering algorithmmatters, and spectral clustering does a better job in our experiments - it always results in improved or at least equally good performance. Fourth, the choice of treating hyperedges as ordered (by combination) or unordered (merging) sets is data-dependent, and the difference in performance is observed.

Combining the results from Q1, Q2 and Q3 shows that the main benefit of CUR2LED is the transformation of data such that it becomes easier to express complex dependencies. Consequently, the obtained models have lower complexities and their performance often improves.

Q4. To ensure that the previously discussed results do not over-fit the data, we additionally perform model selection. We dedicate one fold as the validation set, and use the remaining folds to find the best parameter values of both CUR2LED and TILDE. Table 2 summarizes the results and reports the selected choice of parameter, together with the performance on the validation set. These results are consistent with the ones in Table 1: C-representation improves the performance in the majority of cases, and the selected parameters correspond to the best performing ones in Table 1.

Q5. Table 1 shows that CUR2LED substantially outperforms MRC on all datasets, achieving better performance on all datasets except the IMDB. Moreover, MRC rarely shows benefit over the original data representation, with an exception on the Hepatitis dataset. Considering the model complexity, the models learned on MRC-induced representation are substantially more complex than the ones learned on Crepresentations. Table 3 summarize the number of clusters created by CUR2LED and MRC. MRC creates substantially more clusters than CUR2LED . Because of this, the found clusters contain only a few objects which makes it difficult to generalize well, and increases the model complexity. The number of clusters found by CUR2LED is relatively high, because it finds a representation of data suitable for many classification tasks over the same datasets. Thus, most of the features are redundant for one specific task, but clearly contain better information as the models learned on them perform better and have lower complexity.

The computational complexity of CUR2LED is impossible to state in general, as it depends on the choice of (and is dominated by) the clustering algorithm. Performing a 5-fold cross validation on a single CPU took approximately 5 minutes for the IMDB and UWCSE datasets, 24 hours for the Terrorists dataset and approximately a week for the remaining datasets. Though expensive, latent representation has to be created only once and can be reused for many tasks with the same dataset. Moreover, CUR2LED is easily parallelizable which can substantially improve its efficiency.

6 Conclusion

This work introduces CUR2LED - a clustering-based framework for unsupervised representation learning with relational data, which describes both instances and relationships between them. Viewing relational data as hypergraph, CUR2LED learns new features by clustering both instances and their relationships. i.e., vertices and hyperedges in the corresponding hypergraph. To support such procedure, we introduce a general hyperedges clustering framework based on similarity of vertices participating in the hyperedge. A distinct feature of CUR2LED is the way it uses the ambiguity of similarity within relational data, i.e., whether two relational objects are similar due to their features of relationships, to generate distributed representation of data. We design several experiments to verify the usefulness of latent representation generated by CUR2LED . The results show that the latent representations created by CUR2LED provide a better representation of data that results in models of lower complexity and better performance. In future work, we will extend CUR2LED towards semi-supervised settings, and investigate alternative ways for learning a distributed representations directly from data.

Acknowledgments

This research is supported by Research Fund KU Leuven (GOA/13/010).