Social content such as social network posts, tweets, news articles and more generally web page fragments is often structured. Such social content is also frequently enriched with annotations, most of which carry semantics, either by collaborative effort or from automatic tools. Searching for relevant information in this context is both a basic feature for the users and a challenging task. We present a data model and a preliminary approach for answering queries over such structured, social and semantic-rich content, taking into account all dimensions of the data in order to return the most meaningful results.
In this work, we introduce S3, a novel data model for structured, semantic-rich content
exchanged in a social context. The data model builds on widespread Web standards for
structured documents (XML/JSON) and semantic Web data (RDF), while it also
extends well-established models for data shared and queried in social applications. Based
on this data model, we revisit top-k keyword search, well studied in the social context
for unstructured (flat) data items, to also take into account document structure and
semantics. The implementation and evaluation of a query answering algorithm for this
framework is currently ongoing; more details are provided in our technical report [
Fig. 1. RDFS statements. p and the value of that property is the object o. A triple is well-formed whenever its subject, s, belongs to U , its property, p, belongs to U and its object, o, belongs to K. In what follows, we only consider well-formed triples.
RDF Schema A valuable feature of RDF is RDF Schema (RDFS), which allows enhancing the resource descriptions provided by RDF graphs. An RDFS declares semantic constraints between the classes and the properties used in these graphs, through the use of RDF built-in properties, as summarized in Figure 1. In this figure, s, o ∈ U , while domain and range denote respectively the first and second attribute of every property.
Within the RDF standard [
We distinguish a non-empty set Ω ⊂ U of social network users and for each u ∈ Ω we add u a S3:user 1 to I where S3:user is a dedicated RDF class.
We introduce the property S3:social generalizing the various relationships which may connect users in the social network. For every relationship from a user u1 to a user u2 having the weight w, we have: u1 S3:social u2 w ∈ I.
In our model, the higher the weight, the closer we consider the two users are.
We consider that content is created under the form of structured documents e.g., XML, JSON, etc. A document is an unranked, ordered tree of nodes. Let N be a set of node names (e.g., legal XML or JSON node names), and be a special symbol denoting the empty node name (allowed in JSON for instance). Any node has an URI.
We denote by D the subset of U consisting of node URIs. Each node has a name from N ∪ { }, and a content: a set of keywords from K. We assume every text node has been broken in words, stop words have been removed, and the remaining words are URI and structure
Name
Content stemmed to obtain our version of the node’s text content. For example, in Figure 2, the original text of URI 0.0.0 could be “Troops are attacking Crimea”. For simplicity, we consider the URI of a document to be that of its root node.
We term any subtree rooted at a node in document d a fragment of d. The set of fragments (nodes) of a document d is denoted F rag(d). We may use f to refer interchangeably to a fragment f and to its URI.
Document-derived triples We capture the relationships between documents, fragments and keywords through a set of RDF statements using S3-specific properties.
We introduce a dedicated RDF class S3:doc corresponding to the documents, and: – For each d ∈ D, we have d a S3:doc 1 ∈ I; – For each document d ∈ D and each fragment n of d: n S3:partOf d 1 ∈ I; – For each node n and keyword k in the content of n: n S3:contains k 1 ∈ I; – For each node n with name m: n S3:nodeName m 1 ∈ I.
Example 1. Based on the document in Figure 2, the following triples are in I: URI 0.1 S3:partOf URI 0 1, URI 0.0.0 S3:contains ”Crimea” 1, and URI 0.0 S3:nodeName text 1.
Fragment position We assume available a function pos(d, f ) returning the position of fragment f within document d, as the sequence of nodes from node d to node f .
The multiple facets of our data model are interconnected, reflecting the relationships between users, content, and semantics. We model these relationships by using a set of S3 classes and properties, as we outline below.
Connections between documents and semantics Document semantics can be characterized by I quadruples relying on a class we call hereafter S3:relatedTo. Intuitively, S3:relatedTo accounts for the multiple ways in which a node of a document can be related to a keyword by a user. S3:relatedTo is thus used to make statements about the semantics of a document (or node), as illustrated by the following example, where user u4 states that the fragment URI 0.0.0 is somehow related to Russia:
a a S3:relatedTo 1 a S3:hasKeyword ”Russia” 1 a S3:hasSubject URI 0.0.0 1 a S3:hasAuthor u4 1 The above four triples are part of I; a is an ad-hoc resource whose role is to encapsulate the S3:relatedTo statement.
The property S3:hasSubject can take values either from D or from other instances of S3:relatedTo. The latter allows to express higher-level annotations, i.e., make statements about the semantics of other statements.
We define by T the set of resources of type S3:relatedTo and we refer to them as tags.
S3:partOf, 1 S3:postedBy, 1 S3:partOf, 1
S3:social, 0.3 S3:commentsOn, 1
S3:social, 0.7
S3:postedBy, 1 S3:commentsOn, 1 S3:postedBy, 1
S3:contains, 1
URI1 u2
We stress that we do not aim at a single, “standard”, interpretation of S3:relatedTo, since there are already many concrete instantiations thereof. For instance, a natural language processing (NLP) tool may recognize a text fragment as related to a person or a topic, a user may state that a document is related to a certain topic, etc. Any such concrete flavors of “being related to” can be used, and we consider that they are all stated to be subclasses (in RDFS sense) of our special class S3:relatedTo. Connections between users and documents We identify two different relationships between users and documents, as detailed below. 1. Users can post documents. We model this using a dedicated property S3:postedBy; for each user u having posted a document d, d S3:postedBy u 1 is in I. 2. Users can also create documents that comment on other documents. We capture this using the dedicated property S3:commentsOn. For each user u having created a document c as a comment on the document d, the following hold:
c S3:commentsOn d 1 ∈ I and c S3:postedBy u 1 ∈ I.
Observe that when user u posts a document c, which comments on a document d, and possibly cites part of d, each fragment of d exactly replicated in the comment is now part of c, and thus has a new URI.
Example 2. Assuming that URI 1, posted by u1, is a comment on URI 0, we have: URI 1 S3:postedBy u1 1 ∈ I and URI 1 S3:commentsOn URI 0 1 ∈ I.
Inverse properties Observe that the relations introduced previously are interesting to explore in both directions. For instance, it is interesting to know what comments have been posted on a given document d, and by whom, but it is also interesting to know “What are the comments posted by user u?”, or “What does this comment refer to?”. To support bidirectional manipulation of such relationship, we introduce in our model a set of inverse properties for S3:postedBy, S3:commentsOn, S3:hasSubject and S3:hasAuthor, denoted respectively:
S3:postedBy, S3:commentsOn, S3:hasSubject, S3:hasAuthor with the straightforward semantics: s p¯ o 1 ∈ I iff o p s 1 ∈ I, for p ∈ {S3:postedBy, S3:commentsOn, S3:hasSubject, S3:hasAuthor}.
As we will show, in our framework, user queries are expressed using search keywords. Based on the semantics encoded in the RDF schema, we define for every keyword k ∈ K a simple semantic extension as follows: Definition 1 (Keyword extension). Given a S3 instance I and a keyword k ∈ K, the extension of k, denoted Ext(k), is defined as follows: – k ∈ Ext(k); – for any weighted triple b a k 1, b ≺sc k 1 or b ≺sp k 1 in I, we have b ∈ Ext(k).
For example, given the keyword fish and assuming that tuna ≺sc fish 1 holds in I, we have tuna ∈ Ext(fish). Note that the extension is not a generalization, in the sense that it does not introduce any loss of precision: whenever we include a keyword (URI) k2 in the extension of another keyword k1, it follows from the RDFS in I that k2 is an instance of or a specialization (particular case) of k1.
Social components A notion of distance is natural in a social context such as the one we consider. We consider that a subset Inet of I’s edges encapsulate quantitative information on the strength of the links between users, documents and tags. The network edges, Inet, are exactly those labeled with properties from the S3 namespace (other than S3:partOf), and whose subject and object are either users, documents, or tags.
For instance in Figure 3, u1 S3:social u3 0.5 and URI 0 S3:postedBy u1 1 are network edges but URI 0.0 S3:contains k0 1 and URI 0.1 S3:partOf URI 0 1 are not: the first triple’s object is neither a user, a document, or a tag but a keyword while the second has the property S3:partOf.
Observe that the above notion of network edges: (i) includes any edge between two social network users (given that for any s-labeled edge between two users u1, u2 ∈ Ω, s is a sub-class of S3:relatedTo); (ii) includes all the S3-prefixed properties we introduced, such as commenting upon, authoring, annotating etc.; (iii) does not include relations between document fragments. While a document node can be seen as “close” to its children or ancestors, two distant nodes from the same document may be harder to relate. We formalize the possible connections between document nodes by introducing: Definition 2 (Document vertical neighbourhood). Two documents are vertical neighbours if one of them is a fragment of the other. We define by neigh the set of vertical neighbours of an URI.
In Figure 3, URI 0 and URI 0.0.0 are vertical neighbours; URI 0.0.0 and URI 0.1 are not.
We are interested in vertical neighborhoods, because we consider that a social interaction (e.g., a comment or tag) upon a document fragment carries over to both the descendants and the ancestors of this fragment. As a consequence, we define: Definition 3 (Social path). A social path (or simply a path) in I is a chain of network edges such that the end of each edge and the beginning of the next one are either the same or vertical neighbours. We may also designate a path simply by the list of nodes it traverses, when there is no ambiguity as to the edges taken.
u2 S3:hasAuthor a0 1 a0 S3:hasSubject URI 0.0.0 1 In Figure 3, u2 −−−−−−−−−−−−−→ a0 −−−−−−−−−−−−−−−−−−→ URI 0.0.0 99K
URI 0 S3:postedBy u0 1 URI 0 −−−−−−−−−−−−−−−→ u0 is an example of such a path, stepping from URI 0.0.0 to its vertical neighbour URI 0 (the dotted arrow denotes this).
We use the notation x y to denote the set of all social paths leading from node x or one of its vertical neighbours to y or one of its vertical neighbours in I. Finally, |p| denotes the number of edges along the path p.
Given a path p, the normalized path from p is the copy of p where the edge weights have been modified so that the sum of the weights of the edges outgoing from any source of social edge is 1. In more details, let n be the end point of a network edge in a path and e be the next edge in this path, the normalized weight of e for this path is: wnormalized e = we/ Pe0∈out(neigh(n)) we0 where we denotes the weight of the edge e and out(X) the network edges outgoing from a set of edges X. In the following, whenever we work with a path, we first obtain its normalized version and manipulate it instead. 3
Users can search S3 instances by means of ranked search queries; the answer consists of the k top score fragments, according to a joint structured, social and semantic score. Definition 4 (Query). A query is a pair of the form (u, φ) where u ∈ Ω is a user and φ ⊂ K is a set of keywords. We call u the seeker.
The ranked results to be computed in response to a query require the presence of a numeric score function. More precisely, score(q, d) assigns a numerical score from R to any document d or any fragment f thereof in the graph, for a given query q. Definition 5 (Query answer). The top-k answer to a query q is the k highest scoring documents or fragments for q, such that the presence of a document or fragment in a given rank prevents the inclusion of its vertical neighbours at lower ranks in the result.
Our approach for effective search over the structured, social and semantic graph relies on two core ingredients: (i) a model of relationships between keywords and various graph components (users, documents etc.); (ii) a score function quantifying the interest of a fragment w.r.t. a query. We outline these two components next.
Relationships to keywords, and their sources We need to capture both the explicit and the implicit relationships connecting a document or a resource of type S3:relatedTo to a search keyword. The relationship can be explicit, for instance, when the document contains the keyword, or a member of its extension Ext(k) (Definition 1). Implicit relationships are due to a document (or the S3:relatedTo resource) being connected through a succession of comments and tags, to a search keyword k. For instance, a document d2 which has been stated as related to k may be a comment on another document d1; in this case, d1 is related to k through d2.
To model these relationships, we introduce a function relation source, denoted rel(d, k). For any document d and keyword k, rel(d, k) is a set of tuples of the form (type, f rag, src) such that: – type ∈ {S3:contains, S3:relatedTo, S3:commentsOn} is the kind of relation, – f ∈ F rag(d) is the exact fragment of d due to which d is involved in this relation, – src ∈ Ω ∪ D (users or documents) records the origin of this relation between d and k, as we explain next.
Concretely, the relation source tuples are built as follows. Let d be in D ∪ T , let f ∈ F rag(d), let k ∈ K, and let src ∈ Ω ∪ D be a user or a document4.
1. Documents connected to the keywords of their fragments If the fragment f contains a keyword k, then (S3:contains, f, d) ∈ rel(d, k). This holds even if f does not contain k itself, but some k0 ∈ Ext(k).
2. Connections due to S3:relatedTo statements Whenever I comprises an annotation a of a fragment f (of document d) by a source (author) src, with a specialization of the keyword k, we record the resulting connection between d and k, as well as the 4 This is a slight abuse of notation (tags do not have fragments): if t ∈ T we use F rag(t) = {t}. fact that the connection is due to the source of the annotation on f , through the tuple (S3:relatedTo, f, src) ∈ S3:relatedTo(d, k).
Moreover, if the annotation a itself is related to a keyword k (directly or indirectly, due to a source src0, and no matter what the relationship type is: we denote this by (_, a, src0) ∈ rel(a, k)), and a is about the fragment f of document d, then rel(d, k) includes the tuple (S3:relatedTo, f, src0). This records that a connects (relates) f and all its ancestors, to the keyword k, and keeps the source src0 of the connection.
3. Connections due to S3:commentsOn statements Finally, if a relation source tuple connects a comment c on a document d to the keyword k due to some relation source src, then rel(d, k) includes (S3:commentsOn, c, src). Intuitively, social connections to a comment on d also extend to d.
Social proximity Our second ingredient for a score function is a comprehensive social proximity measure on I. To each pair of vertices connected by at least one social path, it associates a global measure (of all the paths betwen them).
First, for each path we define a proximity function path_prox, returning values in
[
Based on this, we express the social proximity prox : (Ω ∪ D ∪ T )2 → [
prox(a, b) = ⊕path({path_prox(p), p ∈ a b})
where ⊕path is a function which aggregates a set of values in [
Based on the rel tuples and the proximity measure introduced above, we define: Definition 6 (Generic score). Given a document d and a query q = (u, φ), the score of d for q is: score(d, (u, φ)) = ⊕gen({(k, type, pos(d, f ), prox(u, src)) |k ∈ φ, (type, f, src) ∈ rel(d, k)}), where ⊕gen aggregates four-tuples of the form (keyword, relationship type, importance of fragment f in d, social proximity) into a value from R.
Let us comment on how various aspects of the graph reflect in the generic score.
First, ⊕gen aggregates over all the keywords in φ. Further, recall that tuples from rel(d, k) account not only for k but also for all keywords k0 ∈ Ext(k). This is how semantics is injected into the score.
Second, the score of d takes into account the relationships between fragments f of d, and the keyword k (or some k0 ∈ Ext(k)). We use pos(d, f ) as an indication of the structural importance of the fragment within the document. Document structure is thus taken into account both directly through pos, and indirectly, since the rel tuples previously introduced also propagate relationships from fragments to their documents.
Third, the score takes into account the social component of the graph, through prox. This function accounts for the relationships between the seeker u, and the various parties (users, documents and tags), denoted src, due to which f is related to k.
We outline concrete methods for implementing the ⊕path, path_prox and ⊕gen
functions in our technical report [
The core idea of our algorithm is the following. The graph is explored starting from the seeker and moving to vertices (users, documents, or tags) at increasing distance, looking for candidate fragments that may be part of the top-k answer. We compute Ext(k) for each query keyword, since the members of these extensions will be used to compute scores. For each candidate c we maintain a score interval with its lowest and highest possible real scores, which are refined during the exploration. When a candidate fragment is discovered, we are aware of at least one path from the seeker to it, but not of all of them, and the candidate’s score w.r.t. the query may be significantly impacted by a path not visited yet. During the search, candidate documents are kept sorted by their highest possible score. The exploration ends when we are certain that no candidate document outside the current top-k candidates may have an upper bound above the minimum lower bound within the current top k.
For the particular proximity and score functions we considered (based on the
literature and adapted to our setting), we have the guarantee that our algorithm correctly
produces the query result (Definition 5), as we show in [
To the best of our knowledge, this is the first attempt to model social media with both
structured and semantis content. Past research has considered keyword search on
structured XML documents, e.g., [
Our work seeks to extend and integrate the aforementioned models, to support the three dimensions (structured, semantic and social), in the most common query paradigm: the one of keyword query.