Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs – one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.[-]

While message-passing neural networks (MPNNs) are the most popular architectures for graph learning, their expressive power is inherently limited. In order to gain increased expressive power while retaining efficiency, several recent works apply MPNNs to subgraphs of the original graph. As a starting point, the talk will introduce the Equivariant Subgraph Aggregation Networks (ESAN) architecture, which is a representative framework for this class of methods. In ESAN, each graph is represented as a set of subgraphs, selected according to a predefined policy. The sets of subgraphs are then processed using an equivariant architecture designed specifically for this purpose. I will then present a recent follow-up work that revisits the symmetry group suggested in ESAN and suggests that a more precise choice can be made if we restrict our attention to a specific popular family of subgraph selection policies. We will see that using this observation, one can make a direct connection between subgraph GNNs and Invariant Graph Networks (IGNs), thus providing new insights into subgraph GNNs' expressive power and design space.[-]

Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs – one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.[-]