Search

Link prediction, which consists of predicting edges based on graph features, is a fundamental task in many graph applications. As for several related problems, Graph Neural Networks (GNNs), which are based on an attribute-centric message-passing paradigm, have become the predominant framework for link prediction. GNNs have consistently outperformed traditional topology-based heuristics, but what contributes to their performance? Are there simpler approaches that achieve comparable or better results? To answer these questions, we first identify important limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem -- due to the graph sparsity -- in their training and evaluation. Moreover, we propose Gelato, a novel topology-centric framework that applies a topological heuristic to a graph enhanced by attribute information via graph learning. Our model is trained end-to-end with an N-pair loss on an unbiased training set to address class imbalance. Experiments show that Gelato is 145% more accurate, trains 11 times faster, infers 6,000 times faster, and has less than half of the trainable parameters compared to state-of-the-art GNNs for link prediction., 15 pages

Graphs are a powerful tool for the study of dynamic processes, where a set of interconnected entities change their states according to the time-varying behavior of an underlying complex system. For instance, in a social network, an individual's opinions are influenced by their contacts; while, in a traffic network, traffic conditions are spatially localized due to the fact that vehicles are often constrained to move along roads. Understanding the interplay between structure and dynamics in networked systems enables new models, algorithms, and data structures for managing and learning from large amounts of data arising from these processes.This dissertation is focused on recent work on the analysis of dynamic graph processes. More specifically, we will show how sampling and spectral graph theory can be applied to effectively represent data from such processes. We also present efficient algorithms for learning Interleaved Markov Models (IHMMs). These are powerful latent variable models that enable the clustering of discrete sequences without training data and lead to interesting challenges in terms of inference. Furthermore, we also discuss how graphs can be modified in order to control a process of interest via network design and introduce three ongoing projects on the subject of this dissertation. The statement of the thesis is that mining and modeling processes on graphs leads often to problems that are not not only hard computationally but also in terms of inference. They can be solved using spectral, probabilistic, and combinatorial optimization algorithms, and must take into account the graph structure and also large amounts of data traces from these processes.

From the 2016 U.S. presidential election to the 2021 Capitol riots to the spread of misinformation related to COVID-19, many have blamed social media for today's deeply divided society. Recent advances in machine learning for signed networks hold the promise to guide small interventions with the goal of reducing polarization in social media. However, existing models are especially ineffective in predicting conflicts (or negative links) among users. This is due to a strong correlation between link signs and the network structure, where negative links between polarized communities are too sparse to be predicted even by state-of-the-art approaches. To address this problem, we first design a partition-agnostic polarization measure for signed graphs based on the signed random-walk and show that many real-world graphs are highly polarized. Then, we propose POLE (POLarized Embedding for signed networks), a signed embedding method for polarized graphs that captures both topological and signed similarities jointly via signed autocovariance. Through extensive experiments, we show that POLE significantly outperforms state-of-the-art methods in signed link prediction, particularly for negative links with gains of up to one order of magnitude., Accepted to WSDM 2022

Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. While there have been several attempts to capture group fairness in the $k$-clustering problem, fairness at an individual level is relatively less explored. We introduce a new notion of individual fairness in $k$-clustering based on features not necessarily used for clustering. We show that this problem is NP-hard and does not admit a constant factor approximation. Therefore, we design a randomized algorithm that guarantees approximation both in terms of minimizing the clustering distance objective and individual fairness under natural restrictions on the distance metric and fairness constraints. Finally, our experimental results against six competing baselines validate that our algorithm produces individually fairer clusters than the fairest baseline by 12.5% on average while also being less costly in terms of the clustering objective than the best baseline by 34.5% on average.

Network robustness is a measure a network's ability to survive adversarial attacks. But not all parts of a network are equal. K-cores, which are dense subgraphs, are known to capture some of the key properties of many real-life networks. Therefore, previous work has attempted to model network robustness via the stability of its k-core. However, these approaches account for a single core value and thus fail to encode a global network resilience measure. In this paper, we address this limitation by proposing a novel notion of network resilience that is defined over all cores. In particular, we evaluate the stability of the network under node removals with respect to each node's initial core. Our goal is to compute robustness via a combinatorial problem: find b most critical nodes to delete such that the number of nodes that fall from their initial cores is maximized. One of our contributions is showing that it is NP-hard to achieve any polynomial factor approximation of the given objective. We also present a fine-grained complexity analysis of this problem under the lens of parameterized complexity theory for several natural parameters. Moreover, we show two applications of our notion of robustness: measuring the evolution of species and characterizing networks arising from different domains., Accepted as a full paper in AAMAS'21

K-cores are maximal induced subgraphs where all vertices have degree at least k. These dense patterns have applications in community detection, network visualization and protein function prediction. However, k-cores can be quite unstable to network modifications, which motivates the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? We investigate this question from an algorithmic perspective. More specifically, we study the problem of computing a small set of edges for which the removal minimizes the $k$-core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and fixed-parameter intractability. Motivated by such a challenge in terms of algorithm design, we propose a novel algorithm inspired by Shapley value -- a cooperative game-theoretic concept -- that is able to leverage the strong interdependencies in the effects of edge removals in the search space. As computing Shapley values is also NP-hard, we efficiently approximate them using a randomized algorithm with probabilistic guarantees. Our experiments, using several real datasets, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization while being able to handle large graphs. Moreover, we illustrate how KCM can be applied in the analysis of the k-core resilience of networks., To appear as an extended abstract in AAMAS 2020 and as a full paper in IJCAI 2020

Modeling information that resides on vertices of large graphs is a key problem in several real-life applications, ranging from social networks to the Internet-of-things. Signal Processing on Graphs and, in particular, graph wavelets can exploit the intrinsic smoothness of these datasets in order to represent them in a both compact and accurate manner. However, how to discover wavelet bases that capture the geometry of the data with respect to the signal as well as the graph structure remains an open question. In this paper, we study the problem of computing graph wavelet bases via sparse cuts in order to produce low-dimensional encodings of data-driven bases. This problem is connected to known hard problems in graph theory (e.g. multiway cuts) and thus requires an efficient heuristic. We formulate the basis discovery task as a relaxation of a vector optimization problem, which leads to an elegant solution as a regularized eigenvalue computation. Moreover, we propose several strategies in order to scale our algorithm to large graphs. Experimental results show that the proposed algorithm can effectively encode both the graph structure and signal, producing compressed and accurate representations for vertex values in a wide range of datasets (e.g. sensor and gene networks) and significantly outperforming the best baseline.

Graph databases that emerge from several relevant scenarios (e.g., social networks, the Web) require powerful data management algorithms and techniques. A fundamental operation in graph data management is computing the similarity between two graphs. However, due to the large scale and high dimensionality of real graph databases, computing graph similarity becomes a challenging problem in real settings. Many graph data management tasks, such as graph mining, classification, and retrieval, can be contextualized in the framework of graph kernels. A graph kernel is, roughly speaking, a function that computes the similarity between graph structures as means to enable the application of linear methods to graph data. Nevertheless, large databases usually require the use of compact representations of graphs known as graph fingerprints (or signatures). Graph fingerprinting techniques provide a solution that is a trade-off among accuracy, efficiency, and compression in graph kernels. In this paper, we study the problem of generating fingerprints for graph kernels. We introduce a graph fingerprinting technique based on the min-hashing scheme, which is a powerful strategy for computing the similarity between large sets of items using a small amount of data. An algorithm for the generation of graph fingerprints as vectors of min-hash values is presented and integrated into the framework of graph kernels. Results show that graph fingerprinting achieves efficiency gains of up to one order of magnitude with up to 97% space savings when compared against the complete set of graph substructures. Moreover, the proposed technique is up to 9 times more accurate than a baseline method.