We consider an attributed graph G(O, E) where E is the edge set and whose vertices in O are labelled by a description in an attribute pattern language with a lattice structure, typically 2 I where I is a set of binary attributes. A way recently investigated to search for frequent patterns is to define a restricted extensional space which is the range of an interior operator on 2 O (see Section 3). The idea of such an operator in the case of an attributed graph is to minimally reduce a vertex subset until all the vertices of the reduced vertex subset, also called an abstract vertex subset, satisfies some connectivity property within the corresponding induced subgraph [1]. We call a graph abstraction the corresponding extensional space, i.e. the range of the interior operator mentioned above. A typical example of a connectivity property is the degree ≥ k property which is such that all vertices of an abstract vertex subset e have a degree greater than or equal to k in the subgraph G e induced by e. Another example is the k-clique abstraction in which vertices in e have to belong to some k-clique in G e . This approach, based on a previous work on abstraction in Formal Concept Analysis [2] produces abstract closed patterns i.e. maximal attribute patterns, obtained by applying a closure operator on the abstract support sets obtained when applying the interior operator to the support sets 3 .
In this case, the set of (abstract support set, abstract closed pattern) pairs forms a lattice called an abstract concept lattice, and we obtain a set of related abstract implications denoted by 2q → 2w that hold whenever the abstract support set of q is included in the abstract support set of w.
Recent works in attributed graph mining are interested in searching for local patterns made of a constraint on a subset of attributes together with a density constraint on a vertex subset, and this using various notions of maximality [3,4]. In a companion article [5], we have defined local closed patterns corresponding to maximal attribute patterns each associated to one dense subgraph, allowing to extract local implications, particular to specific dense groups of objects. For that purpose Formal Concept Analysis (FCA) had to be extended in order to take into account this notion of locality. In that case, several closure operators may be applied to the same pattern: a closed pattern will then be local as the closure will depend on which region of the extensional space is concerned. The simplest example is obtained by considering that the support set of a pattern induces a subgraph made of various connected components, and associating to each connected component a local closed pattern, i.e. the most specific pattern shared by the vertices of this connected component. In what follows, the subgraph induced by the pattern q support set is simply called the pattern q subgraph. Formally, the dense vertex subsets we consider as elements of the extensional space form a partial order called a confluence in a recent investigation in Formal Concept Analysis [6] and close to, but different from, confluent familiies recently investigated in [7]. The confluence structure generalizes the abstraction structure and may have several minimal elements (see Section 4). In the case mentioned above, a simple graph confluence, the minimal elements are the singletons {v}, where v is a vertex, and the elements of the confluence are connected vertex subsets i.e. vertex subsets each inducing a connected subgraph. The structure of the set of (local support set, local closed pattern) pairs, we call local concepts, has been shown to be a more general structure generalizing the lattice structure, and called a pre-confluence [5]. We call local concept pre-confluence the ordered set of local concepts. Again we may associate to this structure a set of implications, called local implications written 2 m q → 2 m w where m is any minimal element of the confluence. Such a local implication means that the (unique) local support set including m of pattern q is included in the local support set of w including m. In the simple example mentioned above, 2 {v} q → 2 {v} w holds whenever i) v belongs to the support set of q and ii) the connected component containing v of the pattern q subgraph is included in the connected component containing v of the pattern w subgraph.
Both approaches can be mixed by considering the simple graph confluence F mentioned above together with a graph abstraction A. What happens then is that F A = F ∩A also is a confluence, we call a cc-confluence. In practice, this means that we choose some abstraction A, for instance considering the degree >= k graph abstraction and then consider among its elements only connected vertex subsets. When investigating some attributed graph we have then to chose A, or consider a set of graph abstractions ordered by set theoretic inclusion A 1 , . . . , A n obtained for instance by increasing k of the degree >= k. As we will see in our experiments, we may extract this way local patterns and implications at different levels.
However connected components of abstract subgraphs as represented in cc-confluences does not always completely capture the idea of communities as considered in social network analysis. As discussed in [5], we may however enlarge the local closed patterns approach by deriving a new graph G T from G whose vertex set T is a set of vertex subsets of G. Figure 1 displays a graph whose vertices represents pupils on a school in the West of Scotland, whose edges represent friendship relations and whose vertex attributes concern substance use and sporting activity4 . As a running example we consider the empty pattern subgraph i.e. the whole graph. By applying a 3-clique graph abstraction we select the vertices related by colored or bold edges. We will then obtain 4 local closed patterns l i each representing the most specific attribute pattern occurring in a connected component of the empty pattern abstract subgraph. However, in this example the largest connected component is clearly made of distinct dense parts, i.e. communities, we would like to consider when defining local closed patterns. Fortunately, when considering k-communities [8] we can solve this problem by applying the cc-confluence approach to a new graph derived from the original graph. More precisely, a k-community is a vertex subset in a graph G that corresponds to a connected component in a derived graph G T . The vertices of G T are k-cliques in G and an edge relates two vertices whenever the corresponding k-cliques share k − 1 vertices in G. Each colored subgraph in Figure 1 defines such a 3-community. When labelling each vertex in G T by the intersection of the corresponding k-clique vertex labels, the local closed pattern associated to the connected component of some pattern subgraph in G T represents the most specific attribute pattern occurring in the corresponding k-community.
Section 2 describes the attributed graphs used in our experiments. Section 3 presents abstract concept lattices, abstract implications and graph abstractions. Section 4 defines local concept pre-confluences, related local implications and cc-confluences. In Section 5 we show how using derived c-confluences we extract the set of 3-communities associated to pattern subgraphs, and we display the local concept pre-confluence of the teenage friendship attributed network displayed Figure 1. In Section 6 we briefly discuss the implementation used in our experiments.
We will further consider experiments in two datasets. In both cases the data is described as a graph G = (O, E) whose vertices have as labels elements of 2 I where I is a set of items, i.e. binary attributes. As objects are not always described using binary attributes, the binarization preprocessing is described when necessary.
The dataset is denoted as s50-1 and is a standard attributed graph dataset 5 . It represents 148 friendship relations between 50 pupils of a school in the West of Scotland, and labels concern the substance use (tobacco, cannabis and alcohol) and sporting activity. Values of the corresponding variables are ordered. The binarization process consists in defining variables representing the value intervals. T stands for Tobacco consumption and has values 1 (no smoking), 2 (occasional) and 3 (regular). C stands for cannabis consumption and has values 1 (never tries) to 4, D stands for alcohol consumption and has values 1 (does not drink) to 5, and S stands for sporting activity and has two values 1 (occasional) and (2) regular. A binary variable represents an interval, as for instance C23 that has value 1 whenever the value of C is in [2,3]. For sake of simplicity we have merged the two highest values in variables T,C and D. For instance values 4 and 5 in alcohol consumption are merged into a 4m (4 and more) value. We report hereunder the binary attributes whose conjunctions allow to represent any interval (for instance D=2 is obtained as {D12,D23m}):
Cannabis Alcohol T1,T2m C1,C12,C23m,C3m D1,D12,D123,D23m,D34m,D4m
This is the DBLP dataset as described in [9]. There is 45131 vertices, 228188 edges and 555 connected components. Vertices are authors that have published at least one paper in one among 29 journal or conference of the Database and Datamining communities 6 during the 1/1990 to 2/2011 period. An edge links two authors whenever they are coauthors of at least one article. The conferences are clustered in three clusters: DB (databases), DM (data mining) and AI (artificial intelligence) according to a conference ranking site categorization 7 .
The binary attributes are the journal and conference names together with the three clusters. An attribute has value 1 if the author has published in the corresponding journal or conference or cluster.
3 Abstract closed patterns in attributed networks
A standard pattern mining consists in considering the set of occurrences of a pattern q, belonging to some pattern language L with a lattice structure8 , as a subset of an object set O. This language is partially ordered following a general-to-specific ordering and each object o is described as a particular pattern d(o). A pattern q occurs in object o whenever d(o) is less specific than q. The set of occurrences ext(q) of a pattern q is called its support set or its extension in O. A pattern q is said support-closed whenever it is a maximal pattern (i.e. maximally specific) among those that are equivalent in what they share the same support set as q. Now, whenever there is a unique support closed pattern corresponding to a given support set e, as it is the case in the standard FCA or itemset mining framework, an intension function int(e) returns the support-closed pattern associated to the support set e. This means that we relate a pattern q to the corresponding support closed pattern by applying the closure operator int • ext to q. The pattern language L typically is 2 I where I is a set of binary attributes (aka items). With no loss of generality we will further use such a pattern language. The closure operator then simply intersects the object descriptions of the support set of the entry pattern.
The set of frequent support closed patterns, i.e. the support-closed elements with support greater than or equal to some threshold minsupp represents then all the equivalence classes corresponding to frequent supports. Such a class has also minimal elements, called generators. When the patterns belong to 2 X , the min-max basis of implication rules [10] that represents all the implications t → t that hold on O, i.e. such that ext(t) ⊆ ext(t ), is defined as follows:
We define hereunder closure operators and also interior operators that will be further used to restrict the support sets to be abstract support sets. In what follows all ordered sets are finite, and in particular any topped meet-semilattice (resp. pointed joinsemilattice) is a lattice. Definition 1 Let U be an ordered set and f : U → U a self map such that for any x, y ∈ U , f is monotone, i.e. x ≤ y implies f (x) ≤ f (y) and idempotent, i.e. f (f (x)) = f (x), then:
-
f is called a dual closure operator, an interior operator, or also a projection.
In the first case, an element such that x = f (x) is called a closed element.
Ranges of interior operators on lattices are called abstractions and are characterized by the following Proposition:
of some interior operator p on X, if and only if for any elements x, y in A, their join x ∪ y also belongs to A and A contains the empty set. The interior operator is related to its range as follows:
p(x) = sup {a∈A|a≤x} a.
Let then p be the interior operator associated to some abstraction A, p(x) is the greatest element of A included in x. Closed pattern analysis has been recently extended to abstract closed pattern analysis by noticing that applying an interior operator on the extensional space 2 O we obtain again closure operators on the pattern language 2 I [11,2]:
Proposition 2 Let X = 2 O and L = 2 I , p be an interior operator on 2 O , and A = p[X] be the associated abstraction, we have that
The abstract support set of pattern q is defined as p • ext(q). There is then a unique abstract support closed pattern, i.e. a most specific pattern among all patterns sharing the same abstract support set, which is obtained as f (q) = int • p • ext(q). f (q) is then called an abstract closed pattern. This leads to the definition of abstract concepts organized in a concept lattice:
Corollary 1 [2]. The set of (abstract support set, abstract closed pattern) pairs (e = ext(c), c = int(e)), ordered following A, is a lattice called an abstract concept lattice.
Note that, as p is monotone, whenever ext(q) ⊆ ext(w), i.e. q → w is valid we also have ext
This way we obtain abstract min-max basis with the same definition as in section 3.1 except that ext A replaces ext and therefore abstract implications relate minimal elements (i.e. A-generators) to maximal element (the abstract closed pattern, or A-closed pattern) of the same abstract equivalence class. We have then the following definition: Definition 2 The abstract min-max basis m A of valid abstract implications is defined as
These ideas has been applied to attributed graphs by defining graph abstractions [1]. The set of objects O is then the set of vertices of a graph G = (O, E) and each vertex o is labelled by an attribute pattern d(o) ∈ 2 I .
A graph abstraction is an abstraction of 2 O defined through a characteristic property P (x, e) which expresses some minimal connectivity requirement of the vertex x within the subgraph G e induced by some vertex subset e:
Lemma 1 Let P be such that -P (x, e) implies x ∈ e and e ⊆ e and P (x, e) implies P (x, e ), and let q be a mapping defined by q(e) = {x ∈ e|P (x, e)}, then the mapping p defined by p(e) = fixedpoint(q, e) is an interior operator on 2 O p(e) represents the greatest vertex subset of e inducing a subgraph whose vertices all satisfy the associated characteristic property. We give hereunder examples of graph abstractions, defined through their characteristic property and exemplified in Figure 2.
1. degree ≥ k. 2. k-club ≥ s: x has to belong to at least one k-club of size at least s in G e . This is a relaxation of the notion of clique [12]: a k-club is a subset c of vertices such that there is a path of length ≤ k between any pair of vertices in G c . A triangle, a 3-clique, is a 1-club of size 3 (Figure 2-a). Figure 2-b represents a 2-club of size 6 and therefore a 2-club≥ 6 abstract group. 3. nearStar(k, d): x has to have degree at least k or there must be a path of length at most d between x and some y with degree at least k. For instance, the simplest nearStar(8, 1) abstract group is a central node connected with 8 nodes. Such an abstraction is useful when we want the abstraction to preserve hubs [13](i.e high degree vertices) together with their (low degree) neighbors (see Figure 2-c). 4. cc ≥ s: x has to belong to a connected component of size at least s in G e (see Figure 2-d). 5. k-cliqueGroup ≥ s: x has to belong to a k-clique group of size at least s. A kclique group is a union of k-vertex cliques that can be reached from each other through a series of adjacent k-vertex cliques (where adjacency means sharing k -1 nodes). Maximal k-clique groups are denoted as k-cliques communities and formalize the idea of community in complex networks [14].
Finally, it is interesting to note that we can combine two (or more) abstractions A 1 and A 2 in two ways, defining a new composite abstraction either stronger or weaker than both A 1 and A 2 . For instance, we may want to consider an abstract subgraph where vertices both have a degree larger than some k and belong to a connected component exceeding a minimal size s. On the contrary, we may want an abstract subgraph such that at least one of the two characteristic properties is satisfied by all the vertices. This would be the case for instance, if we want to keep both vertices that have a degree larger than, say 10, and vertices in a star, i.e connected to a hub which degree is at least 50. The following lemma states that we can freely combine abstractions in both directions.
high degree vertices) together with their (low degree) neighbors (see Figure 2-c). 4. cc s: x has to belong to a connected component of size at least s in Ge (see Figure 2-d). 5. k-cliqueGroup s: x has to belong to a k-clique group of size at least s. A k-clique group is a union of k-cliques (cliques of size k) that can be reached from each other through a series of adjacent k-cliques (where adjacency means sharing k -1 nodes). Maximal k-cliques groups are denoted as k-cliques communities and formalize the idea of community in complex networks [10]. Finally, it is interesting to note that we can combine two (or more) abstractions A1 and A2 in two ways, defining a new composite abstraction either stronger or weaker than both A1 and A2. For instance, we may want to consider an abstract subgraph where vertices both have a degree larger than some k and belong to a connected component exceeding a minimal size s. On the contrary, we may want an abstract subgraph such that at least one of the two characteristic properties is satisfied by all the vertices. This would be the case for instance, if we want to keep both vertices that have a degree larger than, say 10, and vertices in a star, i.e connected to a hub which degree is at least 50. The following lemma states that we can freely combine abstractions in both directions. Finally note that requiring a frequency property also corresponds to an abstraction whose characteristic property is Pm(x, e) = |e| minsupp, and that can be therefore combined to any abstraction, therefore defining frequent abstract closed patterns.
When we have defined abstractions and corresponding projections, graph-based abstract closed patterns are also de facto defined. Using and abstract closures int p ext(t). All top-down generate and clos algorithms, like LCM [16] can then be adapted to direct computatio of abstract closed patterns 4 . In the experiments in the next section w have used an indirect approach: we first compute frequent closed pa terns and corresponding generators using the CORON software[15 Starting from the closed patterns t and their supports, we then com pute the abstract closed patterns int p ext(t). Finally we consid for each abstract closed pattern tA the generators of all the closed pa terns that have produced tA and select the minimal elements amon them in order to obtain the corresponding abstract generators 5 . Fro abstract generators and abstract closed terms, computing the min max implication rule basis is straightforward. On one hand, the in direct approach needs prior computation of the (non abstract) close patterns, and this can be much more costly than the direct compu tation of abstract closed patterns. On the other hand, once this fir computation is performed, we can apply as many abstract comput tions we need, varying graph abstractions and their parameters, an this can be cost-saving when investigating some new large attribute graph (see Section 4.3). We describe hereunder a generic algorithm, relying on the abstra tion characteristic property, to compute the projection of some subs of the set of objects O: // Given e ✓ O and a characteristic property P u false e 0 e While u = false u true For all vertex x in e 0
If P (x, e 0 ) is false u false e 0 e 0 {x} endIf endFor endWhile // As u = false, P (x, e 0 ) is true for all x in e 0 // e 0 = p(e 0 ) is the abstraction of e with respect to P This generic algorithm is in O(n 2 ⇤ d) where d is the cost of com puting P (x, e 0 ). In the graph abstraction case, computing P (x, e requires to update the induced subgraph G e 0 when some vertex is r moved from e 0 . Furthermore, the cost d depends on the characterist property and will be small as far as the property needs to consid only close neighbors of x. For instance, considering the degree abstraction, first, there is no need to access neighbors of x, and fu thermore, rather than explicitly updating G e 0 when some x is r moved from e 0 it is more efficient to decrease the degree of the ve tices connected to x in e 0 . Another example is the cc s graph ab straction, in which computing the abstraction of some e comes dow to compute the connected components of Ge and remove the sma ones with no need to iterate the process.
We consider here some preliminary experiments in three datasets. I all three experiments, the data is described as a graph G = (O, E 4 Work in progress 5 Recall that each closed pattern that produces an abstract closed pattern t represents an equivalence class of patterns that will be included in the cla of t A in the new equivalence relation relying on abstract supports. Lemma 2 Let P 1 and P 2 two characteristic properties of abstractions defined on the same object set O, and let P 1 ∧ P 2 and P 1 ∨ P 2 be defined as follows:
-P 1 ∧ P 2 (x, e) = P 1 (x, e) ∧ P 2 (x, e) -P 1 ∨ P 2 (x, e) = P 1 (x, e) ∨ P 2 (x, e)
Both P 1 ∧ P 2 and P 1 ∨ P 2 are characteristic properties of abstractions.
Some experiments on the two datasets described in Section 2 have been performed and presented in [1]. We discuss here some new details and experiments on the DBLP dataset. The experiment consisted in applying a degree ≥ k abstraction with increasing k-values and we focussed in abstract patterns obtained with k = 16 which corresponds to a very strong abstraction: in an abstract support set each author is required to have 16 co-authors within the abstract support set. We obtained few abstract closed patterns and in particular the abstract closed pattern VLDBJ, ICDE, SIGMOD, VLDB and the related abstract implication 2 VLDBJ → 2 ICDE, SIGMOD, VLDB. Both the abstract closed pattern and its abstract generator VLDBJ have an abstract support set of 38 among the 1276 VLDBJ authors in the dataset. The implication states that a dense group of co-authors that have published in the Very Large Database Journal also have published in several database conferences. We present Figure 3 the corresponding subgraph. Such a very dense co-authoring subgraph within the VLDBJ subgraph is somewhat unexpected. We made then some investigations in the DBLP repository, focussing of these authors, and found an article whose abstract begins as follows:
A group of senior database researchers gathers every few years to assess the state of database research ... with the following reference: In some sense the explanation of the pattern we discovered is straightforward. However, the whole purpose of pattern mining is to find unexpected patterns, hidden within large datasets, and interpret them in order to acquire some new knowledge. It is exactly what happens here: we were not aware of these regular meetings of senior database researchers, and we learned something new, though, of course, this knowledge is clearly widely known within the database community.
When considering a weaker abstraction, namely here a degree ≥ 4 abstraction, we obtain more abstract closed patterns sometimes made of several connected components.
In [5] we introduced locality in the closure framework with as main motivation investigating local patterns in attributed graphs. We first summarize here main definitions and results. For that purpose we have to consider pre-confluences and confluences which are structures weaker than lattices investigated in [1,5]. Confluences, in particular, are close to but different from confluent families as defined in [7]. We further denote by E x the up sets {y ∈ E|y ≥ x} of an ordered set E, by E x its down sets {y ∈ E|y ≤ x}, and by min(E) the set of its minimal elements. First note that partial orders considered here are all finite. We first define a preconfluence as an ordered structures that generalize the lattice structure: Definition 3 F is a pre-confluence if and only if for any m ∈ min(F ),
A consequence of this definition is that a (finite) lattice is a pre-confluence with a minimum. The structure has a partial join operator: Lemma 3 For any x, y ∈ F m their least upper bound does not depend on m:
This means that a pre-confluence is a union of lattices in which joins coincide. A particular case is which of a pre-confluence included in a host lattice and which is join preserving: Definition 4 Let T be a lattice and F ⊆ T be a pre-confluence with as join ∨ F = ∨ T , F is called a confluence of T .
An abstraction of T , as defined above is a confluence of T with ⊥ T as minimum. We have then the following property when considering 2 O as the host lattice: Proposition 3 Let X = 2 O be a lattice, F ⊆ X is a confluence of X if and only if for any x, y ∈ F m with m ∈ min(F ), we have that x ∪ y belongs to F .
A confluence, is then associated to a set of interior operators: Proposition 4 Let F be a confluence of a lattice X, and m ∈ min(F ),
We are concerned here with extensional confluences, i.e. confluences of X = 2 O [5] that generalize extensional abstractions as graph abstractions. In this case, let x be an element of X greater than or equal to some minimal element m of F , then p m (x) returns the greatest subset of x in F that includes m. In the example that follows we define a graph confluence by only considering vertex subsets inducing connected subgraphs of some graph G = (O, E). Example 1. Let G = (O, E) be a graph (displayed at the bottom of Figure 5) whose vertex set is O = {1, 2, 3, 4}. Let F ⊆ 2 O be the set of vertex subsets inducing connected subgraphs of G. We call them connected vertex subsets. F is a confluence whose set of minimal elements is min(F ) = {{1}, {2}, {3}, {4}}, i.e. the set of singletons of 2 O . The union of two connected vertex subsets that each contains a given vertex s obviously also is a connected vertex subsets and therefore F is a confluence of 2 O . In what follows, by abuse of notation we write p s and F s rather than p {s} and F {s} .The interior operator p s projects then any vertex subset e containing vertex s on the connected component of the subgraph G e induced by e that contains s. The up set F s is then the set of connected vertex subsets containing s and the union of all these F s represents the whole set of connected subgraphs of G. The subset F 1+3 = F 1 ∪ F 3 representing connected vertex subsets containing vertices 1 or 3 also is a confluence. Figure 5 displays the diagram of F 1+3 . 2
The support set e of a pattern q may then be projected, through interior operators, on various smaller local support sets {e i } corresponding, in the graph confluence case, to the connected components of the pattern subgraph. These interior operators are associated to local closure operators [5]:
Proposition 5 Let F be a confluence of X = 2 O , m a minimal element of F and L int(m) be the down set of the pattern lattice L whose elements q are such that q ≥ int(m), then
In the graph confluence case, let e = ext(q), p s (e) is the connected component of the pattern subgraph G e to which belongs the vertex s. Obviously p s (e) = p v (e) for any vertex v in the same connected component. Therefore f s (q) is a local closed pattern w.r.t. any vertex in this connected component, i.e. the most specific pattern shared by the vertices in the connected component.
Now an important result is that that the set of local support sets is a pre-confluence:
h(e) is therefore the local support set of int(e) that contains m ≤ e. h[F ] is a pre-confluence isomorphic to the set P of local concept pairs defined as follows: To summarize we have defined local concepts as (local support set, local closed patterns) pairs and shown they were organized in a structure with possibly several minimal elements, therefore generalizing the concept lattice definition. In the simple graph confluence exemplified above the local support sets simply are the connected components of the pattern subgraphs. We will now extend graph confluences by intersecting this simple graph confluence with abstractions.
We remark now that we can freely intersect confluences:
And as abstractions of X are confluences of X with the bottom element of X as their unique minimal element, the above proposition means we can freely intersect abstractions with confluences to build smaller confluences. Many confluences can then be derived from a graph confluence by intersecting it with some abstractions. We call this family of confluences the cc-confluences. For instance, considering A as the kclique abstraction, we obtain the cc-confluence of connected subgraphs of G made of k-cliques. Note that cc-confluences have an important property: rather than considering the minimal elements of F when defining local closure operators we can consider vertices. This is because given a vertex subset v in some pattern subgraph, all minimal elements containing v belong to the same connected component as v, and therefore the local support sets are the same. This is computationally important as this means that when considering local support sets we only need to consider each vertex in the support set and associate it to the connected component to which it belongs.
Inclusion of local support sets define local implication rules 2 m q → 2 m w where m is a minimal element of F A in the support set of q. Note that, as the local support set of pattern q is obtained by applying an interior operator, which is monotone, to the support set of q, we have that whenever 2q → 2w is valid and m ⊆ ext A (w), we also have that 2 m q → 2 m w is valid, i.e. we may infer the latter local rule from the former abstract rule.
We search now for a basis B of valid local implication rules from which we may infer any local implication rules. We will consider a basis B m for a given minimal element m of F and obtain the whole basis B = ∪B m by joining these bases. Consider a given abstract closed pattern c whose abstract support set has a connected component that contains m, and let l = f m (c) be the corresponding local closed pattern, with respect to the cc-confluence F A . We have then that the implication rule 2 m c → 2 m l holds. We select then a basis B m of informative (l = c) and irredundant ( there is no other rule 2 m c → 2 m l with c less specific than c in the rule set) ones. From B m we may infer all local implication rules associated to m by applying standard axioms in the same way as in the case of the min-max basis in the standard closed or abstract framework. The basis B = ∪B m represents the local knowledge deriving from the reduction of the extensional space from abstraction A to cc-confluence F A .
To shortly examplifiy local implications and local concepts we come back to our experiments on the DBLP dataset in Section 3.3 and specifically the abstract closed pattern DMKD, IDArev, with respect to the degree ≥ 4 abstraction, whose abstract support set is represented in red on Figure 4. When considering the connected component on the left of FIgure 4, we obtain the local implication DMKD,IDArev → 268924 DMgroup stating that in the connected component of the abstract subgraph to which belongs the author 268924, each author has also published in some data mining conference belonging to DMgroup. Now, when considering the Teenage Friends attributed graph displayed Figure 1, clearly the friendship relations are organized in 3-cliques, therefore any stronger abstraction will be poorly informative. However, as mentioned in Section 1, when considering the 3-clique abstract graph associated to the empty pattern the unique connected component could be separated in several (overlapping) communities (displayed in various colors). We discuss and exemplify in the next section how to apply the local closure strategy to discover such subcommunities in an attributed graph.
In what follows, we will consider a family T ⊆ 2 O of vertex subsets, and consider T as the vertex set of a graph G T = (T, E T ) derived from G. The simple graph confluence F of 2 T is then the new extensional space and we will search for the corresponding local closed patterns. The local support sets are afterwards transformed into support sets in 2 O . Let u : 2 T → 2 O be such that u(e T ) = ∪ t∈e T t. u(e T ) is called the flattening of e T . We consider then the two maps ext T and int T defined as follows:
ext T (q) represents the support set of q in T when considering that q occurs in t whenever q occurs in all elements of t (seen as a subset of O). Conversely int T (e T ) represents the greatest pattern in L whose support set in T includes e T , i.e. whose support set in O contains, as subsets, the elements of e T . Now, consider as T the family of k-cliques of G and that (t 1 , t 2 ) ∈ E T whenever t 1 and t 2 share k − 1 vertices in G. A k-community in G [8] is a vertex subset that results from the flattening (in the sens defined above) of some connected component of G T . The local closed patterns w.r.t. F are then most specific patterns occurring in k-communities of pattern subgraphs of G. This way we obtain a local concept pre-confluence, and associated local implications, whose local support sets are these k-communities.
Coming back to our Teenage Friendship attributed graph, we have applied this strategy and built the derived graph G T where T is the set of 3-cliques of the original attributed graph. We display Figures 6 and 7 the local concept pre-confluence of 3-communities which size is greater than or equal to 4 members9 . The minimal 3-communities are the lowest ones on both Figures. Each element of the pre-confluence represents a (3community, local closed pattern) pair but may be associated to several non redundant local implications. This happens for one 3-community displayed on the right at the bottom of Figure 6 and associated to two local implications each represented in a square. Each square displays in red the 3-community, and in red+green+blue the abstract support set of the abstract closed pattern forming the left part of the implication. In Figure 7 we have a unique maximal 3-community on the top, and a hierarchy of sub-communities.
In our experiments we use the CORON software [15] to compute frequent closed patterns, according to some frequency threshold, then apply a set of PYTHON functions In a work in progress, we consider a more efficient computation of abstract and local closed patterns and related implications. The corresponding algorithm uses a divide and conquer strategy similar to that proposed in [7], and therefore allows to directly apply the frequency constraints at the abstract and local level.
In the present article we are interested in addressing problems in which the extensional space, made of the vertex subsets of an attributed network, is constrained according to connectivity properties. We have first considered abstract vertex subsets in which a constraint have to be satisfied by each vertex in the subgraph they induce, as for instance a minimum degree constraint. The extensional space is in this case a particular lattice called an abstraction. We have then shown, benefiting from previous work in FCA, how abstract support closed patterns, i.e. maximal patterns among those sharing the same abstract support set, could be obtained using a closure operator. This led to define a wide class of abstract concept lattices, whose elements are (abstract support set, abstract closed pattern) pairs, each corresponding to a particular abstraction. We obtain this way a global information on how the graph topology is related to the patterns support sets. We have then considered a way to extract local knowledge from an attributed network. For that purpose, using a recent extension of FCA to local extensional spaces, called confluences, we have related each pattern to various local support sets, corresponding to connected components in subgraphs induced by abstract vertex subsets. We obtain this way a set of local concepts, organized in a generalization of the lattice structure called a pre-confluence. Furthermore we have defined both abstract implications and local implications rules representing knowledge which is valid at the abstract and local levels, i.e., regarding the latter, in the vicinity of particular vertices. Finally we have applied these ideas to define the pre-confluence of 3-communities in a social network. These 3-communities are in fact sub-communities as each is a 3-community in some subnetwork induced by an attribute pattern. Overall, what we propose here is a new way, brought by recent developments in Formal Concept Analysis, to explore social networks as attributed graphs. Future works concerns, on the extensional side, applying these ideas to attributed directed graphs or multiplex networks. We also consider to use abstract and local extensional constraints while extending the pattern language to a
wider class of pattern languages. First, as in [16,11,17] by building a meet-semilattice adatpted to the mining problem and using interior operators to reduce it to a tractable language. This has been in particular successfully applied to graph mining [18].Then, as in [6,7] by considering confluent languages allowing to consider connectivity within the pattern language.