Learning Graph Representation
via Formal Concept Analysis

Yuka Yoneda
ISIR, Osaka University
yoneda@ar.sanken.
osaka-u.ac.jp

Mahito Sugiyama
National Institute of Informatics
JST, PRESTO
mahito@nii.ac.jp

Takashi Washio
ISIR, Osaka University
washio@ar.sanken.
osaka-u.ac.jp

Abstract
We present a novel method that can learn a graph representation from multivariate
data. In our representation, each node represents a cluster of data points and eachedge represents the subset-superset relationship between clusters, which can be
mutually overlapped. The key to our method is to use formal concept analysis(FCA), which can extract hierarchical relationships between clusters based on thealgebraic closedness property. We empirically show that our method can effectively
extract hierarchical structures of clusters compared to the baseline method.

1

Introduction

Representation learning has become one of the most important tasks in machine learning (Bengio
et al., 2013; Goodfellow et al., 2016). The typical task is to find a numerical (vectorized) representationfrom structured objects, such as images (Krizhevsky et al., 2012), speeches (Graves et al., 2013),
and texts (Mikolov et al., 2013), which have discrete structures between variables. However, to date,learning of a structured representation from numerical data has not been studied at sufficient depth,
while the task is crucial for relational reasoning aiming at finding relationships between objects tobridge between a symbolic approach and a gradient-based numerical approach (Santoro et al., 2017).
A classic yet promising branch of research for learning structures from numerical data is hierarchicalclustering (Maimon and Rokach, 2005), which is a widely used unsupervised learning method in
multivariate data analysis from natural language processing (Brown et al., 1992) to human motion
analysis (Zhou et al., 2013). Given a set of data points without any class labels, hierarchical clustering
can learn a tree structured representation, called a dendrogram, whose nodes correspond to clusters
and leaves correspond to the input data points. The resulting tree structures can be used for further
analysis of relational reasoning and other machine learning tasks.
However, the representation in hierarchical clustering is restricted to the form of a binary tree sinceclusters must be disjoint with each other in the exiting approaches. Nevertheless, clusters of objects
can often overlap in real-world data analysis. Therefore the technique that can find a hierarchicalstructure of overlapped clusters from multivariate data is needed, which leads to a more flexible graphstructured representation of numerical data.
To solve the problem, we propose to combine nearest neighbor-based binarization and formal concept
analysis (FCA) (Davey and Priestley, 2002). FCA can extract a hierarchical structure of data using thealgebraic closedness property, which consists of mutually overlapped clusters (Valtchev et al., 2004).
Since FCA is designed for binary data, we first binarize numerical data by nearest neighbor-based
binarization, which can model local geometric relationships between data points.
The remainder of this paper is organized as follows. Section 2 introduces our method; Section 2.1
explains nearest neighbor based binarization and Section 2.2 introduces FCA. Section 3 empiricallyexamines our method and Section 4 summarizes our contribution.
32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.

2

The Proposed Method

We introduce our method that learns a graph representation from numerical data. It consists of
two stages. It first binarizes numerical data by nearest neighbor-based binarization, followed byapplying formal concept analysis (FCA) (Davey and Priestley, 2002) to the binarized data, which isan established method to analyze relational databases (Kaytoue et al., 2011). Input to our method is
an unlabeled real-valued vectors. Let D = {d1 , d1 , . . . , dn } be an input dataset. Each data point ism
an m-dimensional vector and is denoted by di = (d1i , d2i , . . . , dmi )∈R .
2.1

Nearest Neighbor-based Binarization

In the first stage, we convert each m-dimensional vector di ∈ Rm into an n-dimensional binary
vector z i ∈ {0, 1}n , where n coincides with the number of data points. The jth feature in theconverted binary vector z i shows whether or not the jth data point dj belongs to nearest neighbors of
di . Formally, given a dataset D ⊂ Rm and a parameter k ∈ N, each data point di ∈ D is binarized
to the binary vector z i = (zi1 , zi2 , . . . , zin ) ∈ {0, 1}n , where each component zij is defined as
1 if dj is the lth nearest data point from di for l ≤ k,
zij =
(1)
0 otherwise.
Hence our binarization models local relationships between data points in terms of the relative
closeness in the original feature space, which is often used as k-nearest neighbor graphs in spectralclustering (von Luxburg, 2007).
When we regard indices of data points as items, every binary vector z i ∈ {0, 1}n can be directly
treated as a transaction Xi ⊆ {1, 2, . . . , n} defined as Xi = { j ∈ {1, 2, . . . n} | zij = 1 }.
In other words, Xi is the set of indices of the data points which are the lth nearest data points(l ≤ k) from di , and hence |Xi | = k always holds. Output in this stage is the transaction databaseT = {X1 , X2 , . . . , Xn }. Transaction databases are the standard data format in frequent patternmining (Aggarwal and Han, 2014) and other fields in databases.
2.2

Formal Concept Analysis

In the second stage, we apply formal concept analysis (FCA) (Davey and Priestley, 2002) to thetransaction database obtained from the first stage, which is a mathematical way to analyze databases
based on the lattice theory and can be viewed as a co-clustering method for binary data. FCA canobtain hierarchical relationships of the original numerical data via the binarized transaction database.
Let A ⊆ T be a subset of transactions and B ⊆ [n] = {1, 2, . . . , n} be a subset of data indices. We
define that A0 is the set of indices common to all transactions in A and B 0 is the set of transactions
possessing all indices in B; that is,
A0 = { j ∈ [n] | j ∈ Xi for all Xi ∈ A },B 0 = { Xi ∈ T | B ⊆ Xi }.

The pair (A, B) is called a concept if and only if A0 = B and B 0 = A. Here the mapping 00 is a
closure operator, as it satisfies A ⊆ A00 , A ⊆ C ⇒ A00 ⊆ C 00 , and (A00 )00 = A00 , and A is closed if
and only if (A, B) is a concept. A concept (A1 , B1 ) is less general than a concept (A2 , B2 ) if A1
is contained in A2 ; that is, (A1 , B1 ) ≤ (A1 , B1 ) ⇐⇒ A1 ⊆ A2 , where the relation “≤” becomesa partial order. The concept lattice is the set of concepts equipped with the order ≤. Intuitively,
concepts are representative clusters in the dataset.
From the set L of concepts, we finally construct a graph representation G = (V, E), where V ={S ⊆ D | (T (S), T (S)0 ) ∈ L} with T (S) = {Xi ∈ T | di ∈ S} and a directed edge (v, w) ∈ E
exists if v covers w; that is, v ⊂ w and v ⊆ u ⊂ w ⇒ u = v. Hence v ⊆ w if and only if w isreachable from v. This graph coincides with the Hasse diagram of the concept lattice using the partial
order ≤. We illustrate an example of a graph representation in Figure 1(b) obtained by our methodfrom a dataset in Figure 1(a).
Since the set of concepts is equivalent to that of closed itemsets used in closed itemset mining (Pasquieret al., 1999), we can efficiently enumerate all concepts using a closed itemset mining algorithm
such as LCM (Uno et al., 2004). Moreover, we can directly obtain more compact representations
by pruning nodes with small clusters using frequent closet itemset mining as the frequency (or the
support) of an itemset coincides with the size of a cluster.
2

Dataset

(a)
4
3

d5

d7
d3
d8

2

d6

1
0

d2

d4

–1

0

1

1

d1
2

Graph structure

(b)

2

6

3

7

4

8

5

9

10

12

14
16

11

13

15

3

Figure 1: (a) Example of dataset. (b) Graph representation obtained from the dataset with k = 3.
All edges are directed from left to right. Numbers of nodes indicate clusters as follows: 1: ∅,2: {d1 }, 3: {d6 }, 4: {d3 }, 5: {d8 }, 6: {d2 , d4 }, 7: {d1 , d6 }, 8: {d3 , d8 }, 9: {d5 , d7 }, 10:{d1 , d2 , d4 }, 11: {d2 , d3 , d4 }, 12: {d1 , d2 , d4 , d6 }, 13: {d5 , d6 , d7 , d8 }, 14: {d1 , d5 , d6 , d7 , d8 },15: {d3 , d5 , d6 , d7 , d8 }, 16: {d1 , d2 , d3 , d4 , d5 , d6 , d7 , d8 }.

3Experiments

We evaluate the proposed method using synthetic and real-world datasets. Since our method can beviewed as hierarchical clustering, to assess the effectiveness of our method, we compare our methodwith the standard hierarchical agglomerative clustering (HAC) with Ward’s method (Ward Jr, 1963).
We performed all experiments on Windows10 Pro 64bit OS with a single processor of Intel Core
i7-4790 CPU 3.60 GHz and 16GB of main memory. All experiments were conducted in Python 3.5.2.
In our method, we used LCM (Uno et al., 2004) version 5.31 for closed itemset mining. HAC is
implemented in scipy (Jones et al., 2001–).
We use dendrogram purity (DP) (Heller and Ghahramani, 2005) for evaluation. Dendrogram purity
is the standard measure to evaluate the quality of hierarchical clusters (Kobren et al., 2017). GivenaSdataset D = {d1 , d2 , . . . , dn } and its ground truth partition C = {C1 , C2 , . . . , CP } such thatCi ∈{1,...,P } Ci = D and Ci ∩ Cj = ∅, and let H be a set of clusters obtained by a hierarchicalclustering algorithm. We denote by LCA(di , dj ) ∈ H the smallest cluster that includes both di ,dj in H and pur(F, G) = |F ∩ G|/|F | for a pair of clusters F, G ⊆ D. Assume that Q be thepair of data points in the same cluster; that is, Q = {(di , dj ) | di , dj ∈ Cl for some Cl ∈ C}. The
dendrogram purity of hierarchical clusters H is defined as
1 XP X
pur(LCA(di , dj ), Cl ).
DP (H) =l=1
di ,dj ∈Cl|Q|
The dendrogram purity takes values from 0 to 1 and larger is better.
We use three types of synthetic datasets synth1, synth2, and synth3. synth1 consists of two equal
sized clusters sampled from two normal distributions (µ0 , σ02 ) = (0, 1) and (µ1 , σ12 ) = (2, 1) for
each feature. synth2 consists of two equal sized clusters sampled from two normal distributions(µ0 , σ02 ) = (0, 1) and (µ1 , σ12 ) = (2, 4) for each feature. synth3 consists of three clusters with thesize ratio (2, 1, 1) sampled from three two-dimensional multivariate normal distributions, where themean is randomly sampled from [−25, 25] and the variance is always 1 for each feature. For eachdataset, we obtained the averaged dendrogram purity from 10 trials.
We collected six real-world datasets from UCI machine learning repository (Lichman, 2013) andused only continuous features. The statistics of datasets are summarized in Table 1.
3.1

Results and Discussion

First we examine the sensitivity of our method with respect to the parameter k for k-nearest neighborbinarization using the synthetic dataset synth1 with n = 100 and m = 2 and the real-world dataset
parkinsons with n = 197 and m = 23. We plot results in Figure 2, where we varied k from 10 to 90
for synth1 and from 10 to 190 for parkinsons. It shows that when k ≥ 20, the dendrogram purity1

http://research.nii.ac.jp/~uno/code/lcm53.zip

3Table 1: Experimental results, where c denotes the number of classes.
n

Name

m

c

# clusters
Ours HAC

DP
Ours HAC

Ours

Runtime (sec.)
HAC

synth1synth1_large
synth2synth3

100
1,000
100
100

2
500
2
2

2
2
2
3

77,364.5
58.4
27,445.3
425.2

199
1,999
199
199

0.937
1.0
0.842
0.976

0.812
1.0
0.705
0.936

1.24×100
1.42×101
5.88×10−1
1.64×10−1

1.01×10−3
4.52×10−1
9.02×10−4
9.12×10−4

parkinsons
vertebralbreast_cancer
wine_red
ctg
seismic_bumps

197
310
569
1,600
2,126
2,584

23
6
10
12
20
25

2
2
2
2
2
2

263,189
503,476,064
3,142
24,412,834
1,426,981
91,059

393
619
1,137
3,199
4,251
5,167

0.828
0.872
0.869
0.849
0.800
0.931

0.738
0.686
0.771
0.845
0.765
0.943

1.30×101
2.55×104
3.40×100
3.73×103
2.52×102
9.48×101

5.32×10−3
4.25×10−3
8.43×10−3
8.09×10−2
1.23×10−1
1.52×10−1

Synthetic

0.9
0.8
Our method
HAC

0.7
0.6
0

20

40

k

60

Parkinsons

0.84
Dendrogram purity

Dendrogram purity

1.0

80

0.80
0.76

0.68

100

Our method
HAC

0.72
0

50

100
k

150

200

Figure 2: Result on synth1 (left) and parkinsons (right).
is higher than HAC in both datasets and it is stable for larger k except for k = 190 in parkinsons,which is almost the same as the dataset size. This means that our method is robust to changes in k if
k is set to be sufficiently large. In the following, we set k to be the half of the respective dataset size.
Next we examine the clustering performance of our method compared to HAC across various
types of datasets. Results are summarized in Table 1. To prune unnecessary small clusters in our
method, we set the lower bound of the size of clusters as 190 for ctg, seismic_bumps, and 490
for synth1_large. They clearly show that our method is consistently superior to HAC across allsynthetic and real-world datasets except for seismic_bumps. The reason is that our method canlearn overlapped clusters while HAC cannot. Although the number of clusters in HAC is always fixed
to 2n − 1 as it learns a binary tree, our method allows more flexible clustering, resulting in a larger
number of clusters as shown in Table 1. How to effectively use the lower bound of the size of clusters
to reduce clusters is our future work.
To summarize, our results show that the proposed method is robust to the parameter setting and canobtain better quality hierarchical structures than the standard baseline, hierarchical agglomerative
clustering with Wald’s method. This means that a graph representation learned by our method can beeffective for further data analysis for relational reasoning.

4

Conclusions

In this paper, we have proposed a novel method that can learn graph structured representation ofnumerical data. Our method first binarizes a given dataset based on nearest neighbor search andthen applies formal concept analysis (FCA) to the binarized data. The extracted concept latticecorresponds to a hierarchy of clusters, which leads to a directed graph representation. We haveexperimentally showed that our method can obtain more accurate hierarchical clusters compared tothe standard hierarchical agglomerative clustering with Wald’s method.
Acknowledgments: This work was supported by JSPS KAKENHI Grant Numbers JP16K16115,
JP16H02870, and JST, PRESTO Grant Number JPMJPR1855, Japan (M.S.); and JSPS KAKENHI
Grant Number 15H05711 (T.W.).
4

References
C. C. Aggarwal and J. Han, editors. Frequent Pattern Mining. Springer, 2014.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013.
P. F. Brown, P. V. deSouza, R. L. Mercer, V. J. D. Pietra, and J. C. Lai. Class-based n-gram models ofnatural language. Computational Linguistics, 18(4):467–479, 1992.
B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 2
edition, 2002.
I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016.
A. Graves, A. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In
2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 6645–
6649. IEEE, 2013.
K. A. Heller and Z. Ghahramani. Bayesian hierarchical clustering. In Proceedings of the 22ndInternational Conference on Machine Learning, pages 297–304, 2005.
Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python,
2001–. URL http://www.scipy.org/. [Online; accessed <today>].
M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis. Mining gene expression data with pattern
structures in formal concept analysis. Information Sciences, 181:1989–2001, 2011.
A. Kobren, N. Monath, A. Krishnamurthy, and A. McCallum. A hierarchical algorithm for extreme
clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, pages 255–264, 2017.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neuralnetworks. In Advances in Neural Information Processing Systems 25, pages 1097–1105, 2012.
M. Lichman. UCI machine learning repository, 2013.
O. Maimon and L. Rokach, editors. Data Mining and Knowledge Discovery Handbook. Springer,
2005.
T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words
and phrases and their compositionality. In Advances in Neural Information Processing Systems 26,
pages 3111–3119, 2013.
N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Efficient mining of association rules using closed
itemset lattices. Information Systems, 24(1):25–46, 1999.
A. Santoro, D. Raposo, D. G. T. Barrett, M. Malinowski, R. Pascanu, P. Battaglia, and T. Lillicrap. A
simple neural network module for relational reasoning. arXiv:1706.01427, 2017.
T. Uno, T. Asai, Y. Uchida, and H. Arimura. An efficient algorithm for enumerating closed patterns
in transaction databases. In Discovery Science, volume 3245 of LNCS, pages 16–31, 2004.
P. Valtchev, R. Missaoui, and R. Godin. Formal concept analysis for knowledge discovery and data
mining: The new challenges. In Concept Lattices, volume 2961 of LNCS, pages 352–371, 2004.
U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.
J. H. Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American
Statistical Association, 58(301):236–244, 1963.
F. Zhou, F. D. l. Torre, and J. K. Hodgins. Hierarchical aligned cluster analysis for temporal clusteringof human motion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(3):582–596, 2013.

5