In this work, we introduce the publish/subscribe paradigm to support continuous query processing over evolving graphs and motivate it for a number of applications and a variety of possible continuous queries. To the best of our knowledge, this is the rst work in the literature that considers supporting publish/subscribe in graphs; we focus speci cally on massive and dynamically evolving graphs due to the nature of the problem and the type of targeted applications. To this end, we design a proof-of-concept ltering algorithm for supporting structural matching of continuous graph queries against updates in the evolving graph and demonstrate the need for e cient ltering by experimentally comparing our algorithm against a baseline approach.
In the modern digital era, graphs are ubiquitous and everpresent as they model a vast number of di erent problems, including social networks, knowledge bases, information and communication networks, distributed systems, biological interactions, and hyper-linked web-pages. Moreover, in many of these problems, graphs are not the reasonably-sized, static snapshots that data scientists are commonly assuming. Contrary, in typical applications graphs are massive in scale, evolving at varying rates (depending on the nature of the problem modelled), and often naturally distributed among di erent machines. Thus, the typical computational paradigm of posing a graph-related query (e.g., aiming at structural matching or certain graph properties) to the system and waiting to receive an answer seems insu cient at environments with such scale and dynamicity.
To address the aforementioned issues, researchers have shifted their attention towards less static modelling of graphs by adopting paradigms such as evolving graphs or graph streams. In these scenarios, a graph is considered as a stream of modi cations (i.e., node and edge additions/deletions/ updates) that trigger the (incremental) re-computation of some graph properties (e.g., density), cumulative measures (e.g., diameter), or subgraph matching/mining. Thus, the graph itself is considered to be dynamic, but the actual queries (i.e., computations) on the streaming input are typically static and cannot be modi ed. Moreover, the e cient evaluation of such computations is heavily dependent on the algorithm chosen for the task and evaluating more query types (let alone more than one queries) at once against the evolving graph is currently not supported. This happens because the adopted model focuses on mining the evolving graph and proves insu cient to address the challenges posed by applications that require the ltering of graph changes against a set of (user) queries.
In our work, we adopt the publish/subscribe (pub/sub) paradigm to evaluate continuous queries against an evolving graph. In this context, users (or services that act on users' behalf) pose continuous queries containing sub-graph, path, and structural/attribute constraints. In this model, continuous queries are appropriately indexed and e ciently evaluated against graph updates, avoiding the matching of the entire query database against every change in the graph stream. In this way, the matching queries are identi ed and the appropriate users are noti ed accordingly. This computational model allows us to o er functionality beyond anything supported by the current state-of-the-art and enables us to provide useful tools that allow users to subscribe to graph changes of interest. In the next section, we outline possible applications that may bene t from graph pub/sub and identify useful query classes for each application.
To this end, our contributions are summarised as follows. Initially, we advocate the application of the pub/sub paradigm in an evolving graph domain and highlight possible applications and useful queries; to the best of our knowledge this is the rst work in the literature that deviates from the typical mining of evolving graphs to o er continuous query functionality to the end-user. Additionally, we highlight the problem of indexing the continuous query database to achieve e cient ltering of graph updates and demonstrate the necessity of e ective indexing structures to support pub/sub in dynamically evolving graphs. Finally, we develop a proof-of-concept ltering algorithm that supports structural matching of continuous graph queries and experimentally demonstrate that it accelerates ltering by four orders of magnitude compared to a baseline approach. 2.
To demonstrate the wide applicability of the proposed graph pub/sub paradigm we identify representative applications and useful query classes for these applications. 2.1
In this section, we discuss the application of graph pub/sub in di erent domains.
Pub/sub on social graphs. Advertising in social networks is becoming a major source of revenue for large corporations such as Facebook and Twitter. Social networks attract advertisers as they can target users by leveraging on publicly available user pro les/demographics. Prompt identi cation of in uential users, active monitoring of their evolving interests over time, and fast adaptation to social graph changes could increase the e ectiveness of advertisements and provide an advantage over the competition. To realise the above requirements, there is a need for a pub/sub tool that will allow advertisers to subscribe to evolving social graphs for subgraphs with given properties and notify them in real time whenever a match occurs.
Moreover, identifying communities of users with similar interests in a network of user purchases (such as Amazon) may provide a valuable extension for (social) recommendation systems. In such a scenario, given the explicit or implicit preferences of a given user, the challenge lies in identifying a community with similar interests and using their purchases to provide useful recommendations to the user. Given that such communities are dynamic in nature, there is a need for a pub/sub tool that will process continuous queries targeted to real-time community identi cation and/or group formation detection incrementally as the graph evolves. Pub/sub in protein interaction graphs. Protein-protein interactions (PPIs) are particularly useful in biology research and are typically modelled as graphs, with proteins as nodes and identi ed interactions between them as edges, stored in central repositories. In this setup, the resulting PPI graph for an organism is continuously evolving by (i) the addition of new nodes/edges through the identi cation of new proteins/interactions, (ii) the deletion of edges due to false positives in the interaction identi cations methods, and (iii) the modi cation of edge weights though the verication (or invalidation) of already discovered interactions. Moreover, bias in the PPI identi cation method may lead to di erences between the actual and observed PPI network, which means that the graph may continuously change.
In such a setting, scientists that want to stay informed about newly discovered interactions, their relation and interplay with existing ones, and the important properties that may be inferred from such discoveries have to repeatedly resort to querying tools that are unable to capture the evolution of the graph. Thus, there is a clear need for a pub/sub solution that provides continuous querying functionality over the PPI networks; such a service would notify subscribed users whenever a graph structure of interest or of certain properties is identi ed/registered in the repository. Pub/sub in other graphs. Other interesting graph pub/ sub applications include curation and pattern identi cation in knowledge graphs, monitoring of tra c networks, and intrusion detection in communication networks. 2.2
In this section, we brie y discuss useful query classes that could be supported in the context of graph pub/sub. Structural and attribute matching. In our model, users will be able to subscribe to speci c subgraphs or motifs (subgraphs with a xed number of nodes found often in a graph) that match given attribute-value predicates and get noti ed when the evolving graphs matches their queries. This would allow user/product monitoring in social graphs, clique/kmotif identi cation for certain proteins in PPIs, and quality control for monitored entities in knowledge graphs. Clustering coe cient. Continuous queries that specify a clustering coe cient (or any similar) measure will be useful to identify communities for targeted advertising, predict/validate PPI interactions, and track trending entities/ items in knowledge graphs.
Shortest path. Shortest path continuous queries are especially useful on PPI graphs as they enable biologists to perform functional correlations and structural annotations between (closely located) proteins. In this scenario biologists want to get noti ed when the shortest path between two given proteins drops below a provided threshold; tracking shortest paths between nodes can be bene cial for several other continuous queries such as betweenness centrality and Steiner tree computation discussed below.
Clique and motif enumeration. Continuous queries that
are used to subscribe for certain thresholds or top-K style
statistics for given cliques and motifs are particularly useful
in PPI graphs for detecting functionally related proteins and
protein complexes. In this scenario, a user would like to be
noti ed when a given clique or motif becomes frequent (i.e.,
its number of instances exceeds a prede ned threshold or is
within the top-k most frequent patterns) in the PPI graph.
Betweenness centrality. Betweenness centrality is
dened as the fraction of shortest paths passing through a
node. Intuitively, nodes with higher betweenness centrality
in social graphs have higher visibility and injecting promoted
content at those nodes would increase the advertising e ect.
Similarly, betweenness centrality is a key measure for
identifying important proteins in a PPI network since proteins
that demonstrate high betweenness centrality are more likely
to be essential proteins with interesting functional and
dynamic properties. Betweenness centrality may be used as an
additional constraint in continuous queries once a subgraph
of interest (e.g., a subgraph with speci c attribute values or
above a certain clustering coe cient) is identi ed.
Node degree. Even though node degree is a simple
metric, together with betweenness centrality constitute the two
key characteristics for identifying important proteins in PPI
graphs, while continuous queries with node degree constraints
could be used (in conjunction with other metrics) to notify
knowledge graph curators of new/trending entities/items.
Dense subgraph. Trending story/topic detection is an
important area where dense subgraphs are known to be of
bene t [
In this section, we outline two proof-of-concept ltering algorithms that match continuous queries against graph updates and present a concise experimental evaluation of their performance that highlights the need for e cient ltering. 3.1
In the context of our proof-of-concept implementation, we developed two algorithms that are able to lter continuous queries aiming at structural properties of the evolving graph. In our setup, continuous queries were arbitrary graphs that express user interests and are appropriately indexed depending on the ltering algorithm at hand. The evolving graph (against which the continuous queries are constantly, i.e., in every update, evaluated) is also indexed to allow for faster matching against the query database.
The rst algorithm we developed has no query indexing strategy and scans the query database sequentially in a brute force manner (hence the name BF) on every graph update to determine matching queries. The BF algorithm stores the full query database in a linked list using an appropriate representation that allows it to match (at publication time) each continuous query against the indexed (evolving) graph. BF was implemented to serve as a simple baseline that would demonstrate the necessity of appropriate query indexing structures that will enhance the ltering process.
The second algorithm we designed decomposes the continuous query to the vertex pairs that form the query graph and uses these pairs as keys to store the query identi er at an inverted index (hence the name INV). In this way, a continuous query graph with k edges is decomposed into k vertex pairs and its identi er is stored at k di erent hash table buckets, one for each pair. An auxiliary table T is used to store the number of vertex pairs that are contained in each continuous query and the number of already matched pairs. When a new graph update is published, the vertexes that are involved in the update are used to locate all a ected continuous queries in the inverted index and appropriately update T . Subsequently, T is scanned to determine whether any newly matching queries have arisen as a result of the new update. If so, the appropriate noti cations are created and sent to the subscribed users.
As we show in the next section, employing even a simple indexing solution such as INV leads in signi cant improvements in ltering time over an exhaustive method. 3.2
In this section, we present a series of experiments that compare the performance of algorithms BF and INV. Evolving graph. We utilised the Wikipedia Pagelinks graph obtained from the DBpedia website as our evolving graph; the initial Wikipedia Pagelinks graph contains more than 19M unique pages (graph nodes) and over 158M links between these pages. To simulate the graph evolution, we obtained a snapshot of the original graph that contained 1M triples and simulated the graph evolution by adding those triples to an (initially empty) graph. The publication events (graph updates) resulted to a directed graph with more than 1:2M pages (vertices) connected by 1M links (edges). Continuous query database. Since no database of continuous (graph) queries was available to us, we used the nal graph to arti cially generate realistic query databases of varying sizes and characteristics. The generated continuous queries belonged to three di erent query classes that capture di erent information needs, i.e., chains, stars, and arbitrary graphs, and each query class was chosen equiprobably. For our evaluation we generated query databases of varying (i) sizes {namely qDB = f10K; 30K; 50Kg queries, (ii) average query length {namely qL = f4; 5; 6g triples/query, and (iii) matching percentage {namely qP er = f5%; 10%; 15%g of all queries matched the nal graph.
Technical con guration. All algorithms were implemented in Java. For the indexing of the graph the JGraphT graph library was used. A PC with a Core Xeon 2:0GHz and 10GB RAM running Ubuntu Linux 14:04 was used. The time shown in the graphs is wall-clock time and the results of each experiment are averaged over 10 executions to eliminate any uctuations in time measurements.
Evaluation results. Figure 1 presents the results from the evaluation of the algorithms INV and BF. Speci cally, Figure 1(a) shows the time in nanoseconds required to insert 50K continuous queries with qP er = 5% when varying the query length qL and the query database size qDB is increasing. We observe that the insertion time of all algorithms remains the same as the qDB size increases, while insertion time increases with the average query length. Algorithm BF is 9 times faster to index a continuous query with qL = 6 compared to Algorithm INV. This happens due to the nature of each algorithm; BF simply inserts the continuous query at the end of a linked list, whereas INV needs to decompose the query into triples, access the involved inverted index buckets, and update table T . Figure 1(b) shows the time in nanoseconds required to match a graph update against a database of stored queries when varying the query database size qDB, while qL = 5 and qP er = 5%. We observe that the ltering time of all algorithms increases with the query database size; algorithm INV is more than four orders of magnitude, i.e., 45000 times, faster in ltering an update against a database of 50K continuous queries compared to BF. In Figure 1(c) the ltering performance of the two algorithms when varying the query length qL, while qDB = 50K and qP er = 5%, is presented. The same performance is demonstrated from both algorithms; INV is again more than four orders of magnitude faster than BF. Finally, Figure 1(d) shows the ltering performance of the two algorithms when varying the matching percentage qP er, while qDB = 50K and qL = 5; similarly INV outperforms BF by more than four orders of magnitude.
Summing up. In summary, for a query database of 50K queries, algorithm INV is able to support a throughput of more than 2M updates/sec in contrast to BF that supports around 500 updates/sec. This signi cant di erence in the performance of the two algorithms demonstrates the need for e cient query indexing structures that will enable us to support real-life dynamically evolving graphs. 4.
Structural graph pattern search using graph isomorphism
has been studied in the literature before [
Pub/sub is a widely used communication paradigm to
process continuous queries on dynamic data. Several classes of
pub/sub systems and subscription languages have been
proposed in the literature [
1000 BF qL = 4 BF qL = 5 BF qL = 6
50 1200 INV qL = 4 INV qL = 5
INV qL = 6 500 600 700 800 Edges in graph (x1000)
(c) 108320
102 constraints between publishers and subscribers is presented and applied to a distributed Web advertising scenario.
Another relevant area of research is graph streams; in [
Sub-graph properties such as clustering coe cient and
density have been considered with respect to evolving graphs
before (e.g., top-k densest sub-graph maintenance [
We plan to investigate more sophisticated query indexing solutions that utilise statistical information on graph updates and commonalities between queries to achieve faster ltering. We also plan to extend our solutions to additional query classes (as identi ed in Section 2). Finally, we plan to develop a distributed solution for graph pub/sub that will t naturally distributed evolving graphs and will be able to scale to massive amounts of data.
Vertices in graph (x1000) 820 400 600
Edges in graph (x1000) 580 INV qDB = 10K INV qDB = 30K INV qDB = 50K 800 1000 BF qP er = 5% BF qP er = 10% BF qP er = 15% INV qP er = 5% INV qP er = 10%
INV qP er = 15% 500 600 700 800 Edges in graph (x1000)