Graph Neural Networks (GNNs) have shown promising potential in graph representation learning. The majority of GNNs define a local message-passing mechanism, propagating information over the graph by stacking multiple layers. These methods, however, are ...

Scale-free networks are prevalently observed in a great variety of complex systems, which triggers various researches relevant to networked models of such type. In this work, we propose a family of growth tree networks \(\mathcal{T}_{t}\), which turn ...

We revisit ApproxContributions, the classic local graph exploration algorithm proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW ’07, Internet Math. ’08) for computing an є-approximation of the PageRank contribution vector for a ...

Graph kernels used to be the dominant approach to feature engineering for structured data, which are superseded by modern GNNs as the former lacks learnability. Recently, a suite of Kernel Convolution Networks (KCNs) successfully revitalized graph ...

In the last two decades, we are witnessing a huge increase of valuable big data structured in the form of graphs or networks. To apply traditional machine learning and data analytic techniques to such data it is necessary to transform graphs ...

Machinery for data analysis often requires a numeric representation of the input. Towards that, a common practice is to embed components of structured data into a high-dimensional vector space. We study the embedding of the tuples of a relational ...

In this paper, we revisit the problem of classical meeting times of random walks in graphs. In the process that two tokens (called agents) perform random walks on an undirected graph, the meeting times are defined as the expected times until they ...

According to Tsallis’ seminal book on complex systems: “an entropy of a system is extensive if, for a large number n of its elements, the entropy is (asymptotically) proportional to n". According to whether the focus is on the system or on the ...

Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is ...

Structural bias or segregation of networks refers to situations where two or more disparate groups are present in the network, so that the groups are highly connected internally, but loosely connected to each other. Examples include polarized ...

We prove a strengthening of the trickle down theorem for partite complexes. Given a (d + 1)-partite d-dimensional simplicial complex, we show that if "on average" the links of faces of co-dimension 2 are [EQUATION]-(one-sided) spectral expanders, then ...

In swarm robotics, random walks have proven to be efficient behaviours to explore unknown environments. By adapting the parameters of the random walk to environmental and social contingencies, it is possible to obtain interesting collective ...

We study the following problem: Given an integer k ≥ 3 and a simple graph G, sample a connected induced k-vertex subgraph of G uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, ...

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ξ_u(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k ...

We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of O(λ/t^1/2−o(1)), where λ is the second largest eigenvalue of ...

This work initiates the study of property testing in signed graphs, where every edge has either a positive or a negative sign. We show that there exist sublinear query and time algorithms for testing three key properties of signed graphs: balance (or 2-...

Performing computation in the presence of faulty and malicious nodes is a central problem in distributed computing. Over 35 years ago, Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] studied the fundamental Byzantine agreement problem in ...

We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta [3]. This process starts with m balls arbitrarily distributed across n bins. At each step t = 1, 2, . . ., we select one ball from each non-empty ...

Recommender systems typically suggest to users content similar to what they consumed in the past. If a user happens to be exposed to strongly polarized content, she might subsequently receive recommendations which may steer her towards more and more ...

Session-based recommendation (SR) predicts the next items from a sequence of previous items consumed by an anonymous user. Most existing SR models focus only on modeling intra-session characteristics but pay less attention to inter-session relationships ...