Label Propagation (LP) is a classic method in semi-supervised learning, where labels diffuse across graph edges until convergence. Its main obstacle on large dense graphs is scalability: classical LP requires an n x n adjacency, with quadratic memory and runtime costs. We focus on the common class of low-rank graphs, where the adjacency has the form VV⊤ for an embedding matrix V ∈ ℝ> n x d. Such graphs arise naturally in applications including similarity graphs from embeddings, recommender systems, kernel methods, and dense affinity graphs in vision and biology. We introduce VLP (Vector-Based Label Propagation), which operates entirely in the embedding space without explicit edges. VLP reduces memory from O (n2) to O (nd), runs efficiently on GPUs, and is mathematically equivalent to classical LP. We further give the first convergence proof of LP in this low-rank setting. VLP makes label propagation feasible for graphs with millions of nodes, far beyond the reach of traditional methods.

The influence estimation and maximization problems study the expected reach of a seed set in social networks under a stochastic propagation model. Motivated by the practical utility of characterizing the distribution of reach values, we systematically analyze the tail behaviour of the reach of a seed set. We study tail bound query problems that, for a given seed set, compute either the maximum reach for a given probability threshold or the highest probability of achieving a target reach. We prove #P-hardness and propose algorithms that balance efficiency and accuracy. We also examine tail bound optimization problems that find a seed set maximizing reach for a target probability or maximizing the probability of achieving a target reach, and establish strong inapproximability results.

Influence Maximization aims to select a subset of elements in a social network to maximize information spread under a diffusion model. While existing work primarily focuses on selecting influential nodes, these approaches assume unrestricted message propagation-an assumption that fails in closed social networks, where content visibility is constrained and node-level activations may be infeasible. Motivated by the growing adoption of privacy-focused platforms such as Signal, Discord, Instagram, and Slack, our work addresses the following fundamental question: How can we learn effective edge activation strategies for influence maximization in closed networks? To answer this question we introduce Reinforcement Learning for Link Activation (RELINK), the first DRL framework for edge-level influence maximization in privacy-constrained networks. It models edge selection as a Markov Decision Process, where the agent learns to activate edges under budget constraints. Unlike prior node-based DRL methods, RELINK uses an edge-centric Q-learning approach that accounts for structural constraints and constrained information propagation. Our framework combines a rich node embedding pipeline with an edge-aware aggregation module. The agent is trained using an n-step Double DQN objective, guided by dense reward signals that capture marginal gains in influence spread. Extensive experiments on real-world networks show that RELINK consistently outperforms existing edge-based methods, achieving up to 15% higher influence spread and improved scalability across diverse settings.

Autism Spectrum Disorder (ASD) is extensively studied by medical practitioners, health researchers, and educators. ASD symptoms appear in early childhood, within the first two years of life, but diagnosing it remains challenging due to its complex and diverse nature. Nevertheless, early diagnosis is crucial for effective intervention. Traditional methods rely on behavioral observations, while modern approaches involve applying machine learning (ML) to brain networks derived from fMRI scans. Limited explainability of these advanced techniques poses a significant challenge in gaining clinicians trust.

Structural clustering is one of the most widely used graph clustering frameworks. In this paper, we focus on structural clustering of probabilistic graphs, which comes with significant computational challenges and has, so far, resisted efficient solutions that are able to scale to large graphs, e.g. the state-of-art can only handle graphs with a few million edges. We address the main bottleneck step of probabilistic structural clustering, computing the structural similarity of vertices based on their Jaccard similarity over the set of possible worlds of a given probabilistic graph. The state-of-art used Dynamic Programming, a quadratic run-time algorithm, that does not scale to pairs of vertices of high degree. In this paper we present a novel approach based on Lyapunov Central Limit Theorem. By using a carefully chosen set of random variables we are able to cast the computation of structural similarity to computing a one-tailed area under the Normal Distribution. Our approach has linear runtime as opposed to quadratic, and as such, it scales to much larger inputs. Extensive experiments show that our approach can handle massive graphs at web-scale which the state-of-art cannot.

Abnormal production of thyroid hormones in our body causes thyroid disorders such as hypothyroidism, hyper-thyroidism, Hashimoto's disease, Graves' disease, and thyroid nodules. Undiagnosed thyroid disorders can affect the quality of life of an individual both physically and mentally. Thyroid disorders are common but sometimes become difficult to diagnose since the symptoms can be easily associated with other health conditions. Clinicians identify thyroid disorders by measuring the levels of thyroid hormones in our blood stream. This work aims to help clinicians by carefully investigating if thyroid diagnosis improves when all important features (a complete thyroid panel) is measured as opposed to a select few. Much of previous work has focused on the performance of classifiers, supervised and unsupervised, for the prediction of this disorder. Departing from this tradition, we focus on the concept of feature importance and its clinical implications. We identify the top-4 important features that predict the presence of thyroid disorder and show that these can be measured by clinicians cost-effectively. We also identify the pitfalls of current clinical practice of not checking the entire thyroid panel, prevalent in many countries with universal health care. Finally, we show that our results are quite robust and are unlikely to change with the choice of classifier or due to the inherent nature of a dataset in hand like imbalance.

Dynamic graph summarization is the task of obtaining and updating a summary of the current snapshot of a dynamic graph when changes (edge insertions/deletions) occur in the graph. As real graphs are massive and undergoing lots of changes, we need dynamic summarization algorithms that scale and are able to respond rapidly to changes in the graph. In this paper, we present two algorithms for lossless summarization of dynamic graphs. We first give an algorithm (Optimal) that is able to obtain and dynamically update the smallest-possible-anytime lossless summary in terms of node reduction. We achieve up to 8 orders of magnitude running time improvement over batch counterparts, and up to 12x improvement over the state-of-art in dynamic graph summarization, while at the same time offering up to 6x improvement in node reduction. We then present an even faster lossless summarization algorithm (Scalable), which goes further into speeding up dynamic updates by offering an additional order of magnitude improvement over Optimal at the cost of having lesser node reduction. Extensive experiments show that Scalable offers node reduction rates that are close to those of Optimal for many datasets. As such, Scalable is a preferred choice when speed of change is very high.

Finding dense components in graphs is of great importance in analysing the structure of networks. Popular frameworks for discovering dense subgraphs are core and truss decompositions. Recently, Sarıyüce et al. introduced nucleus decomposition, which uses$r$-cliques contained in$s$-eliques, where$s > r$, as the basis for defining dense subgraphs. Nucleus decomposition can reveal interesting subgraphs that can be missed by core and truss decompositions. In this paper, we present nucleus decomposition in probabilistic graphs. The major questions we address are: How to define meaningfully nucleus decomposition in probabilistic graphs? How hard is computing nucleus decomposition in probabilistic graphs? Can we devise efficient algorithms for exact or approximate nucleus decomposition in large graphs? We present three natural definitions of nucleus decomposition in probabilistic graphs: local, global, and weakly-global. We show that the local version is in PTIME, whereas global and weakly-global are #P-hard and NP-hard, respectively. We present an efficient and exact dynamic programming approach for the local case. Further, we present statistical approximations that can scale to bigger datasets without much loss of accuracy. For global and weakly-global decompositions we complement our intractability results by proposing efficient algorithms that give approximate solutions based on search space pruning and Monte-Carlo sampling. Extensive experiments show the scalability and efficiency of our algorithms. Compared to probabilistic core and truss decompositions, nucleus decomposition significantly outperforms in terms of density and clustering metrics.

Mining dense subgraphs where vertices connect closely with each other is a common task when analyzing graphs. A very popular notion in subgraph analysis is core decomposition. Recently, Esfahani et al. presented a probabilistic core decomposition algorithm based on graph peeling and Central Limit Theorem (CLT) that is capable of handling very large graphs. Their proposed peeling algorithm (PA) starts from the lowest degree vertices and recursively deletes these vertices, assigning core numbers, and updating the degree of neighbour vertices until it reached the maximum core. However, in many applications, particularly in biology, more valuable information can be obtained from dense sub-communities and we are not interested in small cores where vertices do not interact much with others. To make the previous PA focus more on dense subgraphs, we propose a multi-stage graph peeling algorithm (M-PA) that has a two-stage data screening procedure added before the previous PA. After removing vertices from the graph based on the user-defined thresholds, we can reduce the graph complexity largely and without affecting the vertices in subgraphs that we are interested in. We show that M-PA is more efficient than the previous PA and with the properly set filtering threshold, can produce very similar if not identical dense subgraphs to the previous PA (in terms of graph density and clustering coefficient).

Clique counting is considered to be a challenging problem in graph mining. The reason is combinatorial explosion; even moderate graphs with a few million edges could have clique counts in the order of many billions. In this paper, we propose a fast and scalable algorithm for approximating 4-clique counts in a single-pass streaming model. By leveraging a combination of sampling approaches, we estimate the 4-clique count with high accuracy. Our algorithm performs well on massive graphs containing several billions of 4-cliques, and terminates within a reasonable amount of time.

We present new algorithms for graph summarization where the loss in utility is fully controllable by the user. Specifically, we make three key contributions. First, we present a utility-driven graph summarization method G-SCIS, based on a clique and independent set decomposition, that produces optimal compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Second, we propose a highly scalable, utility-driven algorithm, T-BUDS, for fully controlled lossy summarization. It achieves high scalability by combining memory reduction using Maximum Spanning Tree with a novel binary search procedure. T-BUDS outperforms state-of-the-art drastically in terms of the quality of summarization and is about two orders of magnitude better in terms of speed. In contrast to the competition, we are able to handle web-scale graphs in a single machine without performance impediment as the utility threshold (and size of summary) decreases. Third, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank and shortest paths.

Summarizing graphs is of paramount importance due to diverse applications of large-scale graph analysis. A popular family of summarization methods is the group-based approach. The general idea consists of merging nodes of the original graph into supernodes of the summary graph, encoding original edges into superedges/correction set edges, and dropping certain superedges or correction set edges (for lossy summarization). The current state of the art has several steps in its computation that are serious bottlenecks in terms of running time and scalability. In this work, we propose algorithm LDME, a correction set based graph summarization algorithm that produces compact output representations in a fast and scalable manner. To achieve this, we introduce (1) weighted locality sensitive hashing to drastically reduce the number comparisons required to find good node merges, (2) an efficient way to compute the best quality merges that produces more compact outputs, and (3) a new sort-based encoding algorithm that is faster and more robust. More interestingly, our algorithm provides performance tuning settings to allow the option of trading compression for running time. On high compression settings, LDME achieves compression equal to or better than the state of the art with up to 53x speedup in running time. On high speed settings, LDME achieves up to two orders of magnitude speedup with only slightly lower compression.

Truss decomposition is a popular approach for discovering cohesive subgraphs. However, truss decomposition on probabilistic graphs is challenging. State-of-the-art either do not scale to large graphs or use approximation techniques to achieve scalability. We present an exact and scalable algorithm for truss decomposition of probabilistic graphs. The algorithm is based on progressive tightening of the estimate of the truss value of each edge based on h-index computation and novel use of dynamic programming. Our proposed algorithm (1) is significantly faster than state-of-the-art and scales to much larger graphs, (2) is progressive by allowing the user to see near-results along the way, (3) does not sacrifice the exactness of final result, and (4) achieves all these while processing only an edge and its immediate neighbors at a time, thus resulting in smaller memory footprint. Our extensive experimental results confirm the scalability and efficiency of our algorithm.

Graphlet enumeration is a basic task in graph analysis with many applications. Thus it is important to be able to perform this task within a reasonable amount of time. However, this objective is challenging when the input graph is very large, with millions of nodes and edges. Known solutions are limited in terms of scalability. Distributed computing is often proposed as a solution to improve scalability. However, it has to be done carefully to reduce the overhead cost and to really benefit from the distributed solution. We study the enumeration of four-node graphlets in undirected graphs using a distributed platform. We propose an efficient distributed solution which significantly surpasses the existing solutions. With this method we are able to process larger graphs that have never been processed before and enumerate quadrillions of graphlets using a modest cluster of machines. We show the scalability of our solution through experimental results. Finally, we also extend our algorithm to enumerate graphlets in probabilistic graphs and demonstrate its suitability for this case.

In this work, we consider misinformation propagating through a social network and study the problem of its prevention. In this problem, a "bad" campaign starts propagating from a set of seed nodes in the network and we use the notion of a limiting (or "good") campaign to counteract the effect of misinformation. The goal is to identify a set of k users that need to be convinced to adopt the limiting campaign so as to minimize the number of people that adopt the "bad" campaign at the end of both propagation processes. This work presents RPS (Reverse Prevention Sampling), an algorithm that provides a scalable solution to the misinformation prevention problem. Our theoretical analysis shows that RPS runs in O((k + l)(n + m)(1/(1 - γ)) log n / ε²) expected time and returns a (1 - 1/e - ε)-approximate solution with at least 1 - n^{-l} probability (where γ is a typically small network parameter and l is a confidence parameter). The time complexity of RPS substantially improves upon the previously best-known algorithms that run in time Ω(m n k ⋅ POLY(ε^{-1})). We experimentally evaluate RPS on large datasets and show that it outperforms the state-of-the-art solution by several orders of magnitude in terms of running time. This demonstrates that misinformation prevention can be made practical while still offering strong theoretical guarantees.

Triad enumeration yields more detailed information than triangle enumeration. However, triad enumeration is more complex as it has to list the edges as well as the nodes of the triads. Furthermore, it is challenging to do on large graphs because of two reasons: how to deal with large amounts of data using limited memory, and how to do the computation in a reasonable amount of time. While distributed computing can take care of both problems, it requires large investment and high operating cost, as well as a distributed algorithm design which is not always possible. In this paper we show that triad enumeration of very large graphs at the web-scale can actually be done on a single commodity machine. Memory space limitation can be overcome by using data compression and partial loading. Performance can be greatly improved through optimized preprocessing and parallelization.

k-truss decomposition of a graph is a method to discover cohesive subgraphs and to study the hierarchical structure among them. The existing algorithms for computing k-truss of today's massive networks mainly focus on reducing the runtime using parallel computation on a powerful multi-core server. Our focus, by contrast, is to investigate the feasibility of computing the k-truss on a single consumer-grade machine within a reasonable amount of time. We engineer two efficient k-truss decomposition algorithms: the edge-peeling algorithm proposed by J. Wang and J. Cheng and the asynchronous h-index-updating algorithm proposed by A. E. Sariyuce, C. Seshadhri, and A. Pinar. We reduce their memory usage significantly by optimizing the underlying data structures and by using WebGraph, an efficient framework for graph compression. With our optimized implementation, we show that we can efficiently compute k-truss decomposition of large networks (e.g., a graph with 1.2 billion edges) on a single consumer-grade machine.

Often graph theory is used to model and analyze different behaviors of networks including social networks. Nowadays, social networks have become very popular and social network providers try to expand their networks by encouraging people to stay engaged and active. Studies show that engagement and activities of people in social networks influence engagement of their connections. This behavior has been modeled by the k-core problem in graph theory with the assumption that a person stays active in the network if he or she has k or more connections. In the above model if a person drops out, his or her friends can become discouraged and they might also drop out. An approach called anchored k-core algorithm has been introduced lately that prevents a cascade of drop-outs by finding nodes which have the most influence on their connections and rewarding them to stay in the network. In this work, an efficient implementation of the anchored 2-core approach has been proposed. The proposed implementation method was applied to a set of real world network data that includes very large graphs with millions of links. The results show that with only a few anchors, it is possible to save hundreds of nodes for the 2-core graph. Also, the execution time of our implementation is in order of minutes for huge datasets which proves the efficiency of our implementation.

In this article, we introduce a new generalization of WBM, Conflict-Aware Weighted Bipartite b-Matching (CA-WBM), that can address the conflict challenges mentioned above.

The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling.

Portable smart devices have become prevalent and are used for ubiquitous access to the Internet in our daily life. Taking advantage of this trend, brick-and-mortar retailers have been increasingly deploying free Wi-Fi hotspots to provide easy Internet access for their customers. This opens the opportunity for retailers to collect customer information and perform data mining to improve the quality of their service. In this paper, we propose a novel value-added service to Wi-Fi data mining, Rec2PI, which can infer users' preference profiles based on recommendations pushed by third-party apps. Such profiles can be used to improve users' online experience and enable a brick-and-mortar retailer to participate in the global advertising business. Since the goal and technical difficulties of Rec2PI significantly differ from those of traditional recommender systems, we present a general framework of Rec2PI to illustrate its process. To tackle the technical challenges in profile inference, we propose novel algorithms built using copulas, a statistical tool suitable for capturing complex dependence structure beyond the scope of linear dependence. In the context of rating-based recommendations, we evaluate the proposed algorithms using an open dataset and a real-world recommender system. The evaluation results show that Rec2PI creates consistent and accurate inference results.

The minimum feedback arc set problem is an NP-hard problem on graphs that seeks a minimum set of arcs which, when removed from the graph, leave it acyclic. In this work, we investigate several approximations for computing a minimum feedback arc set with the goal of comparing the quality of the solutions and the running times. Our investigation is motivated by applications in Social Network Analysis such as misinformation removal and label propagation. We present careful algorithmic engineering for multiple algorithms to improve the scalability of each approach. In particular, two approaches we optimize (one greedy and one randomized) provide a nice balance between feedback arc set size and running time complexity. We experimentally compare the performance of a wide range of algorithms on a broad selection of large online networks including Twitter, LiveJournal, and the Clueweb12 dataset. The experiments reveal that our greedy and randomized implementations outperform the other approaches by simultaneously computing a feedback arc set of competitive size and scaling to web-scale graphs with billions of vertices and tens of billions of arcs. Finally, we extend the algorithms considered to the probabilistic case in which arcs are realized with some fixed probability and provide detailed experimental comparisons.

The weighted bipartite b-matching problem (WBM) plays a significant role in many real-world applications, including resource allocation, scheduling, Internet advertising, and E-commerce. WBM has been widely studied and efficient matching algorithms are well known. In this work, we study a novel variant of WBM, called conflict-aware WBM (CA-WBM), where conflict constraints are present between vertices of the bipartite graph. In CA-WBM, if two vertices (on the same side) are in conflict, they may not be included in the matching result simultaneously. We present a generalized formulation of CA-WBM in the context of E-commerce, where diverse matching results are often desired (e.g., movies of different genres and merchants selling products of different categories). While WBM is efficiently solvable in polynomial-time, we show that CA-WBM is NP-hard. We propose approximate and randomized algorithms to solve CA-WBM and show that they achieve close to optimal solutions via comprehensive experiments using synthetic datasets. We derive a theoretical bound on the approximation ratio of a greedy algorithm for CA-WBM and show that it is scalable on a large-scale real-world dataset.

In this work, we study the problem of clearing contamination spreading through a large network where we model the problem as a graph searching game. The problem can be summarized as constructing a search strategy that will leave the graph clear of any contamination at the end of the searching process in as few steps as possible. We show that this problem is NP-hard even on directed acyclic graphs and provide an efficient approximation algorithm. We experimentally observe the performance of our approximation algorithm in relation to the lower bound on several large online networks including Slashdot, Epinions, and Twitter.

Studying the topology of a network is critical to inferring underlying dynamics such as tolerance to failure, group behavior and spreading patterns. k -core decomposition is a well-established metric which partitions a graph into layers from external to more central vertices. In this paper we aim to explore whether k -core decomposition of large networks can be computed using a consumer-grade PC. We feature implementations of the "vertex-centric" distributed protocol introduced by Montresor, De Pellegrini and Miorandi on GraphChi and Webgraph. Also, we present an accurate implementation of the Batagelj and Zaversnik algorithm for k -core decomposition in Webgraph. With our implementations, we show that we can efficiently handle networks of billions of edges using a single consumer-level machine within reasonable time and can produce excellent approximations in only a fraction of the execution time. To the best of our knowledge, our biggest graphs are considerably larger than the graphs considered in the literature. Next, we present an optimized implementation of an external-memory algorithm (EMcore) by Cheng, Ke, Chu, and Özsu. We show that this algorithm also performs well for large datasets, however, it cannot predict whether a given memory budget is sufficient for a new dataset. We present a thorough analysis of all algorithms concluding that it is viable to compute k -core decomposition for large networks in a consumer-grade PC.

We report experimental results for the MapReduce algorithms proposed by Afrati, Das Sarma, Menestrina, Parameswaran and Ullman in ICDE'12 to compute fuzzy joins of binary strings using Hamming Distance. Their algorithms come with complete theoretical analysis, however, no experimental evaluation is provided. They argue that there is a tradeoff between communication cost and processing cost, and that there is a skyline of the proposed algorithms; i.e. none dominates another. We observe via experiments that, from a practical point of view, some algorithms are almost always preferable to others. We provide detailed experimental results and insights that show the different facets of each algorithm.

In this work, we study the problem of clearing contamination spreading through a large network where we model the problem as a graph searching game. The problem can be summarized as constructing a search strategy that will leave the graph clear of any contamination at the end of the searching process in as few steps as possible. We introduce an efficient algorithm and experimentally observe its performance on several large online networks including Slashdot, Epinions and Twitter.

Regret minimizing sets are a recent approach to representing a dataset D by a small subset R of size r of representative data points. The set R is chosen such that executing any top-1 query on R rather than D is minimally perceptible to any user. However, such a subset R may not exist, even for modest sizes, r. In this paper, we introduce the relaxation to k -regret minimizing sets, whereby a top-1 query on R returns a result imperceptibly close to the top- k on D. We show that, in general, with or without the relaxation, this problem is NP-hard. For the specific case of two dimensions, we give an efficient dynamic programming, plane sweep algorithm based on geometric duality to find an optimal solution. For arbitrary dimension, we give an empirically effective, greedy, randomized algorithm based on linear programming. With these algorithms, we can find subsets R of much smaller size that better summarize D , using small values of k larger than 1.

In an emerging trend, more and more Internet users search for information from Community Question and Answer (CQA) websites, as interactive communication in such websites provides users with a rare feeling of trust. More often than not, end users look for instant help when they browse the CQA websites for the best answers. Hence, it is imperative that they should be warned of any potential commercial campaigns hidden behind the answers. Existing research focuses more on the quality of answers and does not meet the above need. Textual similarities between questions and answers are widely used in previous research. However, this feature will no longer be effective when facing commercial paid posters. More context information, such as writing templates and a user's reputation track need to be combined together to form a new model to detect the potential campaign answers. In this paper, we develop a system that automatically analyzes the hidden patterns of commercial spam and raises alarms instantaneously to end users whenever a potential commercial campaign is detected. Our detection method integrates semantic analysis and posters' track records and utilizes the special features of CQA websites largely different from those in other types of forums such as microblogs or news reports. Our system is adaptive and accommodates new evidence uncovered by the detection algorithms over time. Validated with real-world trace data from a popular Chinese CQA website over a period of three months, our system shows great potential towards adaptive online detection of CQA spams.

We initiate a systematic study to help distinguish a special group of online users, called hidden paid posters, or termed "Internet water army" in China, from the legitimate ones. On the Internet, the paid posters represent a new type of online job opportunities. They get paid for posting comments or articles on different online communities and websites for hidden purposes, e.g., to influence the opinion of other people towards certain social events or business markets. While being an interesting strategy in business marketing, paid posters may create a significant negative effect on the online communities, since the information from paid posters is usually not trustworthy. When two competitive companies hire paid posters to post fake news or negative comments about each other, normal netizens may feel overwhelmed and find it difficult to put any trust in the information they acquire from the Internet. In this paper, we thoroughly investigate the behavioral pattern of online paid posters based on real-world trace data. We design and validate a new detection mechanism, using both non-semantic analysis and semantic analysis, to identify potential online paid posters. Our test results with real-world datasets show a very promising performance.

In recent years, concerns of privacy have become more prominent for social networks. Anonymizing a graph meaningfully is a challenging problem, as the original graph properties must be preserved as well as possible. We introduce a generalization of the degree anonymization problem posed by Liu and Terzi. In this problem, our goal is to anonymize a given subset of nodes while adding the fewest possible number of edges. The main contribution of this paper is an efficient algorithm for this problem by exploring its connection with the degree-constrained subgraph problem. Our experimental results show that our algorithm performs very well on many instances of social network data.

The growing need to address privacy concerns when social network data is released for mining purposes has recently led to considerable interest in various techniques for graph anonymization. In this paper, we study the following problem: Given a social network modeled as an edge-labeled graph G, we aim to make a pre-specifled subset of vertices of G k-label sequence anonymous with the minimum number of edge additions. Here, the label sequence of a vertex is the sequence of labels of edges incident to it. The contributions of this paper are two fold: We provide a framework to show hardness results for different variants of social network anonymization using a common approach. We start by showing that k-label sequence anonymity of arbitrary labeled graphs is hard, and use this result to prove NP-hardness results for many other recently proposed notions of graph anonymization. Secondly, we present interesting algorithms and hardness for bipartite graphs. For unlabeled bipartite graphs, we show k-degree anonymity is in P for all k ≥ 2. For labeled bipartite graphs, we show that k-label sequence anonymity is in P for k = 2 but it is NP-hard for k ≥ 3.

In this paper, we focus on XML data integration by studying rewritings of XML target schemas in terms of source schemas. Rewriting is very important in data integration systems where the system is asked to find and assemble XML documents from the data sources and produce documents which satisfy a target schema.As schema representation, we consider Visibly Pushdown Automata (VPAs) which accept Visibly Pushdown Languages (VPLs). The latter have been shown to coincide with the family of (word-encoded) regular tree languages which are the basis of formalisms for specifying XML schemas. Furthermore, practical semi-formal XML schema specifications (defined by simple pattern conditions on XML) compile into VPAs which are exponentially more concise than other representations based on tree automata.Notably, VPLs enjoy a well-behavedness which facilitates us in addressing rewriting problems for XML data integration. Based on VPAs, we positively solve these problems, and present detailed complexity analyses.

Regular path queries (RPQ's) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ's have received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. One of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. The well-know paradigm of computing first a view-based rewriting of the query, and then evaluating the rewriting on the view extensions is indeed possible for RPQ's. However, computing the rewriting is computationally hard as it can only be done (in the worst case) in not less than 2EXPTIME. In this paper, we provide practical evidence that computing the rewriting is hard on the average as well. On the positive side, we propose automata-theoretic techniques, which efficiently compute and utilize instead the complement of the rewriting. Notably using the latter, it is possible to answer a query, and this makes the view-based answering of RPQ's fairly feasible in practice.