"Graphlets give a spectral approach to graph limits for general graph sequences in a framework that unifies previous disparate approaches for dealing with dense graphs and sparse graphs. We will show that the con- vergence to graphlets under the appropriate spectral distance is equivalent to the convergence using the (normalized) cut distance. We then examine the geometry of graphlets, illustrated by examples of several families of graphlets and, in particular, graphlets with low ranks. We further dis- cuss a number of usages of graphlets, including universal scalable bases, universal embeddings vis heat kernels and the preservation of Cheeger cuts."

ETA: This is so not an easy read. I like what I understand, but I definitely have to make another attack on it.

"Human brain functional networks are embedded in anatomical space and have topological properties—small-worldness, modularity, fat-tailed degree distributions—that are comparable to many other complex networks. Although a sophisticated set of measures is available to describe the topology of brain networks, the selection pressures that drive their formation remain largely unknown. Here we consider generative models for the probability of a functional connection (an edge) between two cortical regions (nodes) separated by some Euclidean distance in anatomical space. In particular, we propose a model in which the embedded topology of brain networks emerges from two competing factors: a distance penalty based on the cost of maintaining long-range connections; and a topological term that favors links between regions sharing similar input. We show that, together, these two biologically plausible factors are sufficient to capture an impressive range of topological properties of functional brain networks. Model parameters estimated in one set of functional MRI (fMRI) data on normal volunteers provided a good fit to networks estimated in a second independent sample of fMRI data. Furthermore, slightly detuned model parameters also generated a reasonable simulation of the abnormal properties of brain functional networks in people with schizophrenia. We therefore anticipate that many aspects of brain network organization, in health and disease, may be parsimoniously explained by an economical clustering rule for the probability of functional connectivity between different brain areas."

"We propose a framework for analyzing and comparing distributions, which we use to construct statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS), and is called the maximum mean discrepancy (MMD). We present two distribution-free tests based on large deviation bounds for the MMD, and a third test based on the asymptotic distribution of this statistic. The MMD can be computed in quadratic time, although efficient linear time approximations are available. Our statistic is an instance of an integral probability metric, and various classical metrics on distributions are obtained when alternative function classes are used in place of an RKHS. We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests."

"We present a comparative power analysis, via Monte Carlo, of various graph invariants used as statistics for testing graph homogeneity versus a “chatter” alternative—the existence of a local region of excessive activity. Our results indicate that statistical inference on random graphs, even in a relatively simple setting, can be decidedly nontrivial. We find that none of the graph invariants considered is uniformly most powerful throughout our space of alternatives. Code for reproducing all the simulation results presented in this article is available online."

"Adaptation of cells to environmental changes requires dynamic interactions between metabolic and regulatory networks, but studies typically address only one or a few layers of regulation. For nutritional shifts between two preferred carbon sources of Bacillus subtilis, we combined statistical and model-based data analyses of dynamic transcript, protein, and metabolite abundances and promoter activities. Adaptation to malate was rapid and primarily controlled posttranscriptionally compared with the slow, mainly transcriptionally controlled adaptation to glucose that entailed nearly half of the known transcription regulation network. Interactions across multiple levels of regulation were involved in adaptive changes that could also be achieved by controlling single genes. Our analysis suggests that global trade-offs and evolutionary constraints provide incentives to favor complex control programs."

"Functional connectivity networks have become a central focus in neuroscience because they reveal key higher-dimensional features of normal and abnormal nervous system physiology. Functional networks reflect activity-based coupling between brain regions that may be constrained by relatively static anatomical connections, yet these networks appear to support tremendously dynamic behaviors. Within this growing field, the stability and temporal characteristics of functional connectivity brain networks have not been well characterized. We evaluated the temporal stability of spontaneous functional connectivity networks derived from multi-day scalp encephalogram (EEG) recordings in five healthy human subjects. Topological stability and graph characteristics of networks derived from averaged data epochs ranging from 1 s to multiple hours across different states of consciousness were compared. We show that, although functional networks are highly variable on the order of seconds, stable network templates emerge after as little as ∼100 s of recording and persist across different states and frequency bands (albeit with slightly different characteristics in different states and frequencies). Within these network templates, the most common edges are markedly consistent, constituting a network “core.” Although average network topologies persist across time, measures of global network connectivity, density and clustering coefficient, are state and frequency specific, with sparsest but most highly clustered networks seen during sleep and in the gamma frequency band. These findings support the notion that a core functional organization underlies spontaneous cortical processing and may provide a reference template on which unstable, transient, and rapidly adaptive long-range assemblies are overlaid in a frequency-dependent manner."

"A new family of tree models is proposed, which we call "differential trees." A differential tree model is constructed from multiple data sets and aims to detect distributional differences between them. The new methodology differs from the existing difference and change detection techniques in its nonparametric nature, model construction from multiple data sets, and applicability to high-dimensional data. Through a detailed study of an arson case in New Zealand, where an individual is known to have been laying vegetation fires within a certain time period, we illustrate how these models can help detect changes in the frequencies of event occurrences and uncover unusual clusters of events in a complex environment."

--- After reading, I think their exposition is needlessly hard to follow, but let me take a stab at it. In an ordinary classification tree, we are interested in the distribution of the class labels Y given the predictors X, i.e., Pr(Y|X), and make splits on X so that (in essence) the conditional entropy H[Y|X] becomes small. This is of course equivalent to making splits so that the divergence of Pr(Y|X) from Pr(Y) is maximized. What they are interested in is not classification but _describing_ how the different classes are distinct, so the relevant distribution is Pr(X|Y), and they want a big divergence between Pr(X) and Pr(X|Y).

"When comparing networks (with the same number of nodes) with direct methods, a number of possible distances is already available in literature. Among others, two of the most common families are the set of edit-like distances and the spectral distances. The functions in the former family quantitatively evaluate the differences between two networks in terms of minimum number of edit operations (with possibly different costs) transforming one network into the other, that is, deletion and insertion of links, while spectral measures relies on functions of the eigenvalues of one of the connectivity matrices of the underlying graph.
A noticeable issue affecting edit distance is the fact of being local, i.e. not taking into account the global structure of the networks but only summing the contributions coming from each single link. On the other hand, spectral measures cannot distinguish isomorphic or isospectral graphs. We propose here a possible solution to overcome both issues: combining together an edit and a spectral distance in a product metric we will define textit{glocal}. In what follows we define the two components and the glocal metric itself, with a few examples of applications."

The metric is not at all compelling, but it's nice to see this attempted at all.

"We present a comparative power analysis, via Monte Carlo, of various graph invariants used as statistics for testing graph homogeneity versus a “chatter” alternative—the existence of a local region of excessive activity. Our results indicate that statistical inference on random graphs, even in a relatively simple setting, can be decidedly nontrivial. We find that none of the graph invariants considered is uniformly most powerful throughout our space of alternatives. Code for reproducing all the simulation results presented in this article is available online."

Heard Martin talk about this at SFI last week. Nice, though I think the MDL frame-tale needs some work.
The "alluvial diagrams" are very pretty.