Differentially Describing Groups of Graphs

Differentially describing groups of graphs lies at the heart of many scientific and societal challenges. Neuroscientists, for example, might want to characterize brain activity in healthy subjects, elucidate how it differs from brain activity in subjects diagnosed with certain disorders or diseases (e.g., autism or Alzheimer’s), and investigate whether their findings are the same across different groups of subjects (e.g., children, adolescents, and adults; or men and women). Policymakers, security experts, and epidemiologists alike could seek to understand patterns of human mobility, be it to improve the resilience of traffic infrastructure to random failures and targeted attacks, or to curb the spread of infectious diseases. And international economists might want to investigate patterns of world trade, e.g., imports and exports between countries, and ask how these vary across different years and product classes.

We refer to the common task underlying these scenarios as graph group analysis: Given a set of graphs and a partition of this set into graph groups, succinctly summarize the commonalities and differences between graphs in the same group, between graphs in different groups, and between the relationships connecting the groups. In this paper, we formalize graph group analysis as a maximum likelihood modeling problem, using significant subgraphs as graph patterns to factorize our probability distribution. We introduce Gragra (Graph group analysis) as an algorithm to solve this problem, which jointly discovers a set of graph patterns and an assignment of these patterns to graph groups.

As a real-world example of graph group analysis, consider Fig. 1. Here, we show the top shared (left) and specific (right) patterns identified in resting-state functional brain networks of adolescents with and without autism spectrum disorder, where nodes in the graphs correspond to brain regions, and edges signal strong connectivity between regions. On the right, patterns with red edges are characteristic of autistic adolescents, and patterns with blue edges are characteristic of non-autistic adolescents. They indicate over- and underconnectivity, respectively, in the brains of autistic adolescents when compared to typically developed controls. Although there is no consensus regarding the relationships between autism and neural connectivity (Hull et al. 2017), our method identifies graph patterns that permit neuroscientific interpretation: For example, the dark blue pattern in Fig. 1 indicates underconnectivity between the visual cortex, responsible for processing visual information, and the lingual gyrus, involved in vision and word processing.

Graph group analysis is related to graph classification (e.g., Lee, Rossi, and Kong 2018), but we are interested not only in what is different but also in what is similar among our graph groups. Our task further shares some of its motivation with significant subgraph mining (e.g., Sugiyama et al. 2015), graph summarization (e.g., Liu et al. 2018), and data clustering with graphs as data points (e.g., Mukherjee, Sarkar, and Lin 2017). However, we focus on a complete characterization of a set of graphs under a given partition—a cornerstone of scientific discovery involving graph data.

The remainder of the paper is structured as follows. After settling our basic notation, we describe the theoretical foundations of our method and introduce our algorithm. Having covered related work, through experiments on synthetic and real-world data, we demonstrate that Gragra works well in practice, before rounding up with discussion and conclusions. All our data, code, and results are publicly available.​¹¹1https://doi.org/10.5281/zenodo.6342823

We consider a set $\mathcal{G}=\{G_{1},\dots,G_{|\mathcal{G}|}\}$ of $|\mathcal{G}|$ node-aligned graphs $G_{i}=(V,E_{i})$ with $n=|V|$ nodes and $m_{i}=|E_{i}|$ edges, omitting the subscripts when clear from context. A partition $\Pi=\{\mathcal{G}_{1},\dots,\mathcal{G}_{k}\}$ is a set of $k$ non-empty subsets of $\mathcal{G}_{i}\subseteq\mathcal{G}$, called graph groups, of cardinalities $c_{i}=|\mathcal{G}_{i}|$, whose disjoint union is $\mathcal{G}$. Our graphs can be undirected or directed, loopy or non-loopy, and unweighted, edge-labeled, or integer weighted, where for the purposes of our model, we treat distinct edge labels or edge weights as a set $W$ of categories, and edges $e\in E_{i}$ are drawn from the set $\mathcal{E}=V\times V\times W$ of all possible weighted edges.

The empirical frequency of edge set $X\subseteq\mathcal{E}$ in group $\mathcal{G}_{i}$ is $q_{i}(X)=\left\lvert\{(V,E)\in\mathcal{G}_{i}\mid X\subseteq E\}\right\rvert/c_{i}$, and we denote by $V_{X}$ the set of nodes incident with at least one edge in $X$.

We base our probabilistic model on the maximum entropy principle, by which the distribution that best reflects a given set of constraints without introducing additional assumptions is the distribution with maximum Shannon entropy (Jaynes 1982). Thus, the expected frequency of $X$ in $\mathcal{G}_{i}$ under a given set of edge sets $S\subseteq 2^{\mathcal{E}}$ is

where $2^{\mathcal{E}}$ is the power set of $\mathcal{E}$, and $f$ is the distribution maximizing $\operatorname*{arg\,max}_{f}\{-\sum f_{X}\log f_{X}\}$, subject to linear constraints $\operatorname{\mathbb{E}}_{f}[X]=q_{i}(X)$ for all elements in $S$ (Csiszár 1975). That is,

where $\theta_{0}$ and all $\theta_{i}$ are real-valued model parameters. Finding the distribution $f$ is a convex problem that involves computing the expected frequency $p_{i}(X\mid S)$ over exponentially many elements. This is intractable if done naïvely, but there exist practical approaches that factorize $p_{i}$ into a product of independent distributions (Mampaey, Vreeken, and Tatti 2012; Dalleiger and Vreeken 2020a, b).

We now lay the theoretical foundations of our method, introducing our probabilistic model, our objective function, and our statistical test. At a high level, our goal in graph group analysis is to discover a set $S$ of graph patterns, i.e., edge sets of connected subgraphs, and an association matrix $A$ assigning graph patterns to graph groups, such that $S$ and $A$ together reveal the similarities and differences between graphs in the same group, between graphs in different groups, and between the relationships connecting the groups. A pattern is specific if we assign it to only one graph group, and it is shared if we assign it to several graph groups. We choose which patterns to include in our model based on the information we gain from them, testing whether this gain is statistically significant to rule out spurious results.

To avoid redundancy, we assign a pattern $X$ to a group $\mathcal{G}_{i}$ iff $X$ is informative for $\mathcal{G}_{i}$, given what we already know about all groups. More precisely, using $X$ as a column index of $A$ in a slight abuse of notation, we set $A_{iX}=1$ iff $X$ is informative for $\mathcal{G}_{i}$ under our current model $(S,A)$. We assess this by comparing the empirical frequency of $X$ in group $\mathcal{G}_{i}$, $q_{i}(X)$, to its expected frequency in that group under our current model, $p_{i}(X\mid S_{i})$, where $S_{i}=\{X\in S\mid A_{iX}=1\}$, and $p_{i}$ is obtained from a practical approximation of the maximum entropy distribution with constraint set $S_{i}$. $X$ is informative for $\mathcal{G}_{i}$ iff $q_{i}(X)$ is significantly different from $p_{i}(X\mid S_{i})$, as judged by a statistical test, and we add $X$ to $S$ (and column $X$ to $A$) if $X$ is informative for some $\mathcal{G}_{i}\in\Pi$.

To identify a suitable set of graph patterns $S$ and an adequate association matrix $A$, we exploit the interplay between two steps. First, we discover the best pattern $X$ to add to $S$, given the current $(S,A)$, and second, we identify the best assignment of $X$ to graph groups to update $A$, given the current $(S,A)$ and a new pattern $X$. We now describe each step in more detail.

Having stated its theoretical foundations, we now introduce Gragra as an algorithm to differentially describe groups of graphs using sets of significant subgraphs. Gragra, whose pseudocode is given as Alg. 1, revolves around the procedure stated in Eq. (1), a greedy process that iteratively selects the graph pattern candidate that best enhances our model. This could involve myriad searches through the exponentially-sized space of all possible graphs with nodes from $V$, which is not only computationally infeasible in most cases but also unnecessary, as most candidates will be eliminated as uninformative by Vuong’s test. Hence, rather than exhaustively searching for the best graph patterns, we propose to grow graphs by systematically adding edges to candidates.

To enable our model to infer all possible graphs, we initialize it with the set $\mathcal{E}$ of all possible edges. As our initial graph to grow, we then select the most promising graph pattern from our initial candidates, i.e., the connected triples

Starting with a graph pattern $X$, we explore all its expansions, $((V_{X}\times V\times W)\cup(V\times V_{X}\times W))\setminus X$, from which we select the best candidate pattern to grow further, as long as we gain information and $\Delta(X)$ is significant. We summarize these steps in the function Grow of Alg. 1 (l. 1–1).

Grow requires many inferences of $\Delta$, which involve inferring many more expected frequencies $p_{i}$, rendering exact computation impractical. We thus design a practical, pessimistic heuristic that only considers the information gain from graphs $G\in\mathcal{G}$ in which $X$ is fully present:

We use $h(X)$ instead of $\Delta(X)$ because it involves inferring only one expected frequency per graph group. A derivation of this heuristic can be found in the Online Appendix.

To summarize, Gragra proceeds as follows. Starting with an initial set of candidates $C$ (l. 1), we select (l. 1) and grow (l. 1) the best candidate, and retain all significant expansions (l. 1), until we have grown $X$ to its fullest potential (l. 1–1). Afterwards, we test if the information gain provided by $X$ is significant, and if so, we keep track of its graph group associations (l. 1), and insert $X$ into $S$ (l. 1).

The computational complexity of Gragra depends on the number of candidates, which can grow to at most $|2^{\mathcal{E}}|$. In practice, Gragra’s complexity depends on the number of times we grow graph patterns, which is data-dependent and bounded by the size $\gamma$ of the largest connected component observed in an input graph, as growing beyond that reduces the information gain. Multiplying $\gamma$ by the initial set of candidates, Gragra achieves a complexity of $\mathcal{O}\big{(}\binom{n}{3}|W|\gamma\big{)}$ for all practical purposes, where we assume that the complexity of inferring the expected frequency is bounded.

To the best of our knowledge, we are the first to differentially describe groups of graphs through sets of significant subgraphs. Our method is inspired by advances in graph similarity description (Momo, Coupette and Vreeken 2021) and explainable pattern set mining using maximum-entropy modeling (DISC, Dalleiger and Vreeken 2020a, b). However, Momo focuses on pairs and unpartitioned sets of graphs; DISC is designed for itemset data, ignores graph structure, and does not scale on graphs; and neither method uses a statistical test to select patterns. Further related work broadly falls into two categories: statistical inference on network populations, and graph mining for groups of graphs.

Statistical Inference on Network Populations. In the statistics literature, the task of analyzing multiple graphs simultaneously is typically framed as an inference problem for network-valued random variables (Durante, Dunson, and Vogelstein 2017; Lovato et al. 2020; Lunagómez, Olhede, and Wolfe 2020). Here, Ghoshdastidar et al. (2020) establish limits for distinguishing two population distributions given small sample sizes, and Lunagómez, Olhede, and Wolfe (2020) propose notions of mean and dispersion for a single population of networks, where the population mean is itself a network. Maugis et al. (2020) use subgraph counts to test if all graphs in a sample are drawn from the same distribution, and Signorelli and Wit (2020) propose a model-based clustering approach to describe subpopulations within a population of networks. Finally, Durante, Dunson, and Vogelstein (2017) extend latent space approaches designed for single graphs to capture the probabilistic mechanism that generates multiple graphs from a single population distribution. Their model has been used to characterize and test for differences between groups of brain networks (Durante, Dunson et al. 2018)—an actively studied application for which numerous statistical methods, mostly focusing on testing for differences, have been developed (Ginestet et al. 2017; Wang et al. 2019; Lukemire et al. 2020; Kundu et al. 2021; Lovato et al. 2021; Lehmann et al. 2021).

Prior work in the statistics literature has focused on describing one network population or distinguishing two populations. In contrast, with Gragra, we aim to construct a differential description of any number of populations. Furthermore, we ask not only if these populations are different, but also how they are different and how they are similar.

Graph Mining for Groups of Graphs. In the graph mining literature, groups of graphs have been studied in contexts as diverse as significant subgraph mining (Llinares-López et al. 2015; Sugiyama et al. 2015), graph classification (Vogelstein et al. 2013; Yan et al. 2019; Lanciano, Bonchi, and Gionis 2020), graph clustering with graphs as data points (Mukherjee, Sarkar, and Lin 2017), anomalous graph detection (Gomes, Rao, and Neville 2018), and graph summarization for time series of graphs (Shah et al. 2015). Significant subgraph mining commonly considers small, node-labeled graphs with unaligned node sets, and hence, does not target our problem. However, our setup—i.e., medium-sized graphs with aligned node sets—, has received heightened attention in the graph classification community, again inspired by challenges from neuroscience (Vogelstein et al. 2013; Yan et al. 2019; Lanciano, Bonchi, and Gionis 2020).

The methods that are closest to our work are contrast subgraphs (Lanciano, Bonchi, and Gionis 2020) and signal subgraphs (Vogelstein et al. 2013), both designed for two groups of node-aligned graphs. Contrast subgraphs discover the densest subgraph in the difference of the summary graphs of the input groups (obtained by adding the graphs in each group separately and then subtracting the results), where the size of this subgraph depends on a user-specified regularization parameter $\alpha$. Signal subgraphs assume edge independence as a prior to rank edges by the $p$-values of an edge-wise statistical test for distributional difference (e.g., Fisher’s exact test). Like signal subgraphs, Gragra combines ideas from structural and statistical pattern mining to produce interpretable results that—unlike contrast subgraphs—are based on a statistical foundation. Gragra is more exploratory and more flexible than both competitors, however, because it treats graph group description as an end in itself and can handle any number of graph groups.

We now present an extensive evaluation of our algorithm. To this end, we implement Gragra in C++ and expose a Python interface to facilitate experimentation. We run our experiments on Intel E5-2643 CPUs with $128$ or $256$ GB RAM, testing at a conservative significance level of $1\times 10^{-7}$ (or $1\times 10^{-5}$ when operating with less than $50$ samples), and make all data, code, and results publicly available.​²²2https://doi.org/10.5281/zenodo.6342823 Our experiments revolve around two questions:

1. 1.

   Can Gragra reliably recover the ground truth from groups of synthetic graphs?

2. 2.

   Does Gragra discover meaningful patterns in groups of real graphs?

We study the graph group analysis problem: Given a set of graphs and a partition of this set into graph groups, succinctly summarize the commonalities and differences between graphs in the same group, between graphs in different groups, and between the relationships connecting the groups. We introduce Gragra as an algorithm to solve the problem, which uses maximum likelihood modeling, paired with a model selection criterion and a statistical test, to jointly discover a set of significant subgraphs, called graph patterns, and an assignment of these patterns to graph groups. In our experiments, we demonstrate that Gragra differentially describes synthetic and real-world graph groups, even when faced with heterogeneity, noise, or large group numbers. As a byproduct, we introduce two novel datasets of node-aligned graphs, which might be of independent interest to the graph mining community.

However, our work also has limitations. First of all, we model edge weights as categories, which works well for binned edge weights in practice but is theoretically dissatisfying. Therefore, a natural enhancement of Gragra would be able to handle real edge weights, possibly using a maximum entropy model on its edge weight distribution. Second, we currently test all our graph patterns at the same alpha level. While this is theoretically defensible, given that we combine our statistical test with a model selection criterion, dynamically adjusting our alpha level might be an option worth exploring. Finally, Gragra is currently limited to groups of node-aligned graphs, and extending it to other graph types constitutes an open opportunity for future work.