Search

Explaining the decisions made by machine learning models for high-stakes applications is critical for increasing transparency and guiding improvements to these decisions. This is particularly true in the case of models for graphs, where decisions often depend on complex patterns combining rich structural and attribute data. While recent work has focused on designing so-called post-hoc explainers, the question of what constitutes a good explanation remains open. One intuitive property is that explanations should be sufficiently informative to enable humans to approximately reproduce the predictions given the data. However, we show that post-hoc explanations do not achieve this goal as their explanations are highly dependent on fixed model parameters (e.g., learned GNN weights). To address this challenge, this paper proposes RAGE (Robust Ante-hoc Graph Explainer), a novel and flexible ante-hoc explainer designed to discover explanations for a broad class of graph neural networks using bilevel optimization. RAGE is able to efficiently identify explanations that contain the full information needed for prediction while still enabling humans to rank these explanations based on their influence. Our experiments, based on graph classification and regression, show that RAGE explanations are more robust than existing post-hoc and ante-hoc approaches and often achieve similar or better accuracy than state-of-the-art models.

Event detection is a critical task for timely decision-making in graph analytics applications. Despite the recent progress towards deep learning on graphs, event detection on dynamic graphs presents particular challenges to existing architectures. Real-life events are often associated with sudden deviations of the normal behavior of the graph. However, existing approaches for dynamic node embedding are unable to capture the graph-level dynamics related to events. In this paper, we propose DyGED, a simple yet novel deep learning model for event detection on dynamic graphs. DyGED learns correlations between the graph macro dynamics -- i.e. a sequence of graph-level representations -- and labeled events. Moreover, our approach combines structural and temporal self-attention mechanisms to account for application-specific node and time importances effectively. Our experimental evaluation, using a representative set of datasets, demonstrates that DyGED outperforms competing solutions in terms of event detection accuracy by up to 8.5% while being more scalable than the top alternatives. We also present case studies illustrating key features of our model., Comment: Longer version of "Graph Macro Dynamics with Self-Attention for Event Detection" accepted to DLG-AAAI 2023

Recently, online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, ''bad actors'' are increasingly exploiting these platforms, becoming a key challenge for their administrators, businesses and the society in general. The spread of fake news is a classical example of the abuse of social networks by these actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper we study how to limit the influence of a target set of users in a network via the removal of a few edges. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. Moreover, we consider two types of constraints over the set of edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and matroid version of the problem, respectively. Our experiments show that the proposed solutions outperform the baselines by up to 40%.

Network centrality plays an important role in many applications. Central nodes in social networks can be influential, driving opinions and spreading news or rumors.In hyperlinked environments, such as the Web, where users navigate via clicks, central content receives high traffic, becoming targets for advertising campaigns. While there is an extensive amount of work on centrality measures and their efficient computation, controlling nodes' centrality via network updates is a more recent and challenging problem. Performing minimal modifications to a network to achieve a desired property falls under the umbrella of network design problems. This paper is focused on improving the coverage centrality of a set of nodes, which is the number of pairs of nodes that have a shortest path passing through the set, by adding edges to the network. We prove strong inapproximability results and propose a greedy algorithm for maximizing coverage centrality. To ensure scalability to large networks, we also design an efficient sampling algorithm for the problem. In addition to providing an extensive empirical evaluation of our algorithms, we also show that, under some realistic constraints, the proposed solutions achieve almost-optimal approximation for coverage centrality maximization.

Recent spatio-temporal data applications, such as car-shar\-ing and smart cities, impose new challenges regarding the scalability and timeliness of data processing systems. Trajectory compression is a promising approach for scaling up spatio-temporal databases. However, existing techniques fail to address the online setting, in which a compressed version of a trajectory stream has to be maintained over time. In this paper, we introduce ONTRAC, a new framework for map-matched online trajectory compression. ONTRAC learns prediction models for suppressing updates to a trajectory database using training data. Two prediction schemes are proposed, one for road segments via a Markov model and another for travel-times by combining Quadratic Programming and Expectation Maximization. Experiments show that ONTRAC outperforms the state-of-the-art offline technique even when long update delays (4 mininutes) are allowed and achieves up to 21 times higher compression ratio for travel-times. Moreover, our approach increases database scalability by up to one order of magnitude.