Main | Articles

Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters

@inproceedings{maehara2021learning,
  author={Takanori Maehara and Hoang NT},
  title={Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters},
  booktitle={Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS'21), Online, December 7--10, 2021},
  month={December},
  year={2021},
  url={https://proceedings.neurips.cc/paper/2021/hash/08f36fcf88c0a84c19a6ed437b9cbcc9-Abstract.html},
}

What we wanted

Message passing is deployed on networks far larger than anything GNN theory describes: the theory is written for a graph you hold in full, but production only ever holds a piece of one. We wanted a theory that reaches the regime the models are actually used in.

At that scale you never observe the whole graph: vertices and edges are missing, and what you have is a sample. So the theory has to call two graphs close even when they share no vertices and have different numbers of them.

That kind of closeness is a topology on graph space. The topology has to be settled before anything else, since without one there is nothing to state a theorem about. Most existing GNN theory fails at this point rather than at some later technical step: it has no way to compare two graphs of different sizes at all.

Choosing the topology

We tried the two candidates that graph limit theory supplies.

Graphon convergence. The usual notion of convergence for graphs of differing size, and the one built for the dense case. Under it sparse graphs are all identified with one another. Real networks are sparse, so that collapses exactly the distinctions the theory has to make.

Benjamini–Schramm. Compares graphs through the distribution of balls around random vertices, which is the right shape of idea. But it is defined for graphs of bounded degree, which is the one assumption we could not make: real networks have power-law degree distributions.

The fix is to sample rather than assume, imposing the degree bound at access time instead of requiring it of the data: run a random breadth-first search from a random vertex to a fixed depth, keeping a fixed number of neighbours at each step. That is the only access to the graph we assume. We call that access restriction the random neighbourhood model.

What comes out is a sample of bounded degree and bounded size, so we can compare two graphs by comparing their samples in the Benjamini–Schramm topology. Comparing graphs that way induces a topology on all graphs, and we call it the randomised Benjamini–Schramm topology.

Three things make it the right choice.

First, the input graph may have any degree, because the bound comes from the sampling rather than from an assumption on the data. The theory therefore covers every graph.

Second, continuity in this topology means something concrete: the value of a graph parameter does not move much when you resample. Mini-batch GraphSAGE and its relatives cap the number of neighbours expanded per step, so every batch is already a bounded-degree sample of the kind this topology measures. Production adopted that constraint to bound the batch size, but it is the same constraint that continuity asks for.

Third, the space is totally bounded: for every ε > 0 there is a finite set of graphs such that every graph lies within ε of one of them. That is Lemma 8, which comes with an explicit covering number — a tower of exponentials in 1/ε, but explicit. Total boundedness is what makes the topology worth having.

Total boundedness is close enough to compactness for what we need. Compactness is the workhorse of approximation theory and statistical learning theory: once a space has it, ε-nets, covering-number arguments and uniform approximation are all available.

This is why the choice of topology carries the weight. Ours admits graphs of any degree, so the theory reaches real networks; and it makes the space totally bounded, so the standard approximation and learning-theoretic arguments go through.

What we got out of it

None of the results below are deep. Each one is a standard recipe from approximation theory or statistical learning theory, applied to a space that now supports it. The contribution is the formulation, not the theorems it makes available.

The characterisation (Theorem 7). A graph parameter is constant-time estimable in the random neighbourhood model if and only if it is uniformly continuous in the randomised Benjamini–Schramm topology. Total boundedness is what proves the "only if" direction, that an estimable parameter is uniformly continuous. Triangle density and the local clustering coefficient are estimable; the number of vertices, the minimum and maximum degree, and connectivity are not.

A generalisation bound with no assumption on the graphs (Theorem 10). We get a Rademacher complexity for 1-Lipschitz graph parameters over all graphs, with no bound on size, degree or spectrum. Existing bounds assume bounded size or bounded degree, or else a random graph model, so on unbounded graphs they either do not apply or give a trivial bound. The gap our bound gives decays only as o(1/log log log n) in the number n of training graphs, slow enough to be of no practical use at any realistic training-set size. We read that as the price of assuming nothing rather than as a defect of the argument.

Size generalisation, in two senses worth separating. In the approximation-theoretic sense, every estimable parameter is size-generalisable: an ε-net built out of total boundedness lets a model fitted on graphs of bounded size work on all graphs (Theorem 11). In the learning-theoretic sense, size generalisation is a domain adaptation problem, so the error is bounded by the Wasserstein distance between the small-graph and large-graph distributions (Theorem 13); we compute or bound that distance for the configuration model, for graphons, and for an arbitrary distribution projected onto graphs of bounded size (Propositions 14 to 16). Existing size-generalisation results stop at the first sense: they show a generalising model exists, not that training finds one.

Universality (Theorems 4 and 17). These results come from a different property: the samples have bounded size. Universality for graphs of bounded size was already established, and the samples put us in exactly that case, so Theorem 4 follows by applying that result unchanged. Theorem 17 runs the same argument for the non-universal GNNs people actually run: they are universal relative to whatever they can distinguish. One concrete consequence: mini-batch GraphSAGE can estimate the local clustering coefficient (Proposition 18).