Source-linked AI summary
Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections
Johan Ugander, Lars Backstrom, Jon Kleinberg
TL;DR
The paper asks how large collections of small, dense social graphs can be represented in a common coordinate system and how mathematical graph constraints can be separated from social properties. It represents graphs through induced subgraph frequencies, develops complementary empirical and extremal frameworks, and finds that real social graphs concentrate near a one-dimensional curve while the representation also supports classification by graph origin.
Problem
Large collections of small, dense social graphs lack a general coordinate system for representing their structures and separating social regularities from mathematical graph constraints.
Method
The paper uses frequencies of small induced subgraphs as coordinates, models empirical structure with a single-parameter stochastic extension of Erdős-Rényi graphs, and bounds feasible frequencies using extremal graph theory.
Results
Real social graph families lie near a simple one-dimensional curve, the extended random-graph model closely tracks their 3-node and 4-node subgraph frequencies, and the framework distinguishes neighborhoods, groups, and events.
Takeaways & Limitations
Subgraph-frequency coordinates provide a common framework for studying both social structure and graph-wide combinatorial limits, while also supporting graph-type classification.
Takeaways & Limitations
The empirical study uses only undirected Facebook friendship graphs and does not include subscriptions, pages, or user-to-page connections.
Abstract
from arXiv · showhide
A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs -- these range from sets of social groups, events, or collaboration projects to the vast collection of graph neighborhoods in large social networks. A natural question is how to usefully define a domain-independent coordinate system for such a collection of graphs, so that the set of possible structures can be compactly represented and understood within a common space. In this work, we draw on the theory of graph homomorphisms to formulate and analyze such a representation, based on computing the frequencies of small induced subgraphs within each graph. We find that the space of subgraph frequencies is governed both by its combinatorial properties, based on extremal results that constrain all graphs, as well as by its empirical properties, manifested in the way that real social graphs appear to lie near a simple one-dimensional curve through this space. We develop flexible frameworks for studying each of these aspects. For capturing empirical properties, we characterize a simple stochastic generative model, a single-parameter extension of Erdos-Renyi random graphs, whose stationary distribution over subgraphs closely tracks the concentration of the real social graph families. For the extremal properties, we develop a tractable linear program for bounding the feasible space of subgraph frequencies by harnessing a toolkit of known extremal graph theory. Together, these two complementary frameworks shed light on a fundamental question pertaining to social graphs: what properties of social graphs are 'social' properties and what properties are 'graph' properties? We conclude with a brief demonstration of how the coordinate system we examine can also be used to perform classification tasks, distinguishing between social graphs of different origins.
1. INTRODUCTION
The paper proposes subgraph frequencies as a common coordinate system for large collections of small, dense graphs. It separates mathematical constraints shared by all graphs from empirical regularities of real social graphs, including their concentration near a one-dimensional curve.
- Motivation: Large online applications generate collections of small, dense graphs from neighborhoods, groups, events, forums, and collaborative projects.These collections can contain very large numbers of graphs, motivating a shared representation.
- Representation: The proposed coordinate system represents each graph by frequencies of its induced k-node subgraphs, with k commonly set to 3 or 4.For k = 3, this is related to the triad census.
- Subgraph space: Subgraph-frequency space reflects both extremal combinatorial constraints and empirical concentration of real graphs near a simple one-dimensional curve.The framework is designed to study these two effects separately.
- Extremal constraints: Extremal analysis shows that the forbidden triad has a non-trivial upper bound in all graphs, and every non-complete, non-empty k-node subgraph has frequency bounded away from one.Thus, some apparent absences in social graphs reflect mathematical graph constraints rather than only social behavior.
- Empirical model: The extended random-graph model closely matches observed frequencies for all possible 3-node and 4-node subgraphs, unlike standard Erdős-Rényi graphs, which contain fewer triangles and more triangle-free subgraphs.The model uses a single parameter and improves the empirical fit of the one-dimensional curve.
- Classification: Using Facebook data, the representation distinguishes structural differences among neighborhood, group, and event graphs.These differences suggest corresponding distinctions among the audiences users interact with.
2. DATA DESCRIPTION
The study analyzes Facebook-derived undirected friendship graphs from neighborhoods, groups, and events. It uses temporally defined collections and samples 11,000 induced four-node subgraphs to estimate their frequencies.
- Data scope: All analyzed graphs are induced from Facebook’s undirected friendship graph and exclude subscriptions, pages, and user-to-page connections.The data were analyzed anonymously and in aggregated form.
- Graph collections: The three collections comprise user neighborhoods, Facebook groups, and confirmed event attendees.Neighborhood graphs exclude the ego and contain friendship connections among the ego’s friends.
- Collection procedure: Neighborhood and group data were assembled in October 2012, while event data covered events from 2010 and 2011.For events, only friendship edges formed before each event were included.
- Frequency estimation: Four-node subgraph frequencies were estimated by uniformly sampling 11,000 induced subgraphs with replacement instead of enumerating them.The sampling procedure was intended to provide sufficiently precise frequency estimates.
3. SUBGRAPH SPACE
The paper represents graphs by induced subgraph-frequency vectors, revealing both a concentrated empirical backbone and combinatorial constraints on feasible frequencies. A triadic-closure model closely fits this backbone while distinguishing structural variation across graph collections.
- Coordinate system: Subgraph-frequency vectors map each graph into a simplex whose coordinates are induced subgraph frequencies.For k = 3, the four possible induced subgraphs form a 4-simplex; larger k rapidly increases the dimension.
- Empirical structure: Facebook graph collections occupy a sharply concentrated region that increasingly sharpens around a one-dimensional backbone as graph size grows.Neighborhoods, groups, and events also form distinct structural loci within this shared region.
- Empirical structure: The Erdős-Rényi curve tracks the empirical density but systematically underestimates triangles at matched edge density.The three-node frequencies in G_n,p are ((1 − p)^3, 3p(1 − p)^2, 3p^2(1 − p), p^3).
- Stochastic model: A single triadic-closure parameter extends the random-graph model and accurately captures the empirical concentration of subgraph frequencies.The model fits the mean four-node frequency vectors by adjusting λ, with striking agreement across graph collections.
- Stochastic model: The fitted model precisely describes the scarcity of four-node cycles and yields higher λ/ν for neighborhoods than for groups or events.This ratio is interpreted as indicating greater susceptibility of neighborhood open triads to closure.
4. EXTREMAL BOUNDS
The paper separates empirical subgraph-frequency patterns from universal combinatorial constraints by using homomorphism-based inequalities and a linear program. These bounds reveal feasible regions that real social graphs often leave unoccupied, while proving sharp limits for particular subgraphs.
- Extremal bounds: The analysis addresses both the observed distribution of subgraph frequencies and the combinatorial structure of the space containing them.Stochastic models address empirical values, while extremal analysis addresses universal graph constraints.
- Linear-program framework: Homomorphism-based inequalities become linear at fixed edge density, enabling a linear program that maximizes or minimizes each subgraph frequency.The resulting program maps outer bounds on the feasible geography of subgraph frequencies.
- Linear constraints: Subgraph-frequency vectors on k nodes lie in a linear subspace of the corresponding vectors on larger induced subgraphs.Consequently, constraints on one subgraph frequency propagate to frequencies of related larger subgraphs.
- Sharp extremal bounds: The 3-node path satisfies s(F, G) ≤ 3/4 + o(1) for every graph, and the balanced complete bipartite graph attains 3/4 at edge density p = 1/2.The bound is therefore asymptotically tight, and exactly tight for even graph sizes according to the paper.
- Empirical versus universal structure: Large portions of the theoretically feasible subgraph-frequency region remain unpopulated by the empirical social graphs examined.The bounds do not fully characterize the feasible region, but they expose a gap between graph-theoretic possibility and observed social-graph structure.
- Arbitrary subgraphs: For k-node subgraphs that are neither cliques nor empty graphs, frequencies cannot approach 1 and induced copies can be eliminated at any specified asymptotic edge density.The paper gives both a strict upper bound below 1 and graph families with zero induced frequency for every edge density.
5. CLASSIFICATION OF AUDIENCES
The paper tests whether neighborhoods, groups, and events have distinguishable structural signatures beyond size by classifying them with subgraph frequencies and residual features. These local features achieve strong accuracy, especially when combined with global graph features.
- Results: The Edge Formation Random Walk model provides the best overall classification accuracy among the reported feature constructions.It serves as a meaningful baseline for constructing classification features.
- Task: The classification task distinguishes neighborhoods, groups, and events using structural graph features beyond audience size.The motivating question is whether these audience types differ meaningfully in graph structure even when edge density is similar.
- Empirical structure: Neighborhoods, groups, and events follow different edge-density trends, with groups crossing neighborhoods near 400 nodes and events near 75 nodes.Small groups and events are denser than neighborhoods, whereas larger groups and events are sparser.
- Features: The model uses subgraph frequencies and residuals from an Edge Formation Random Walk backbone, alongside global graph features for comparison.The global feature set includes component, k-core, degeneracy, and k-brace statistics.
- Results: 77% accuracy is achieved in both tasks using only 4-node subgraph frequencies and residuals.Evaluation used five-fold cross-validation on a balanced set of 10,000 instances.
- Results: 81−82% accuracy is achieved by combining global and subgraph-frequency features, compared with 69% and 76% using global features alone.Residuals relative to either the Erdős-Rényi or Edge Formation Random Walk baseline consistently improved classification.
6. CONCLUSION
The paper presents subgraph frequencies as a coordinate system for studying locally dense social graphs. Its complementary empirical and combinatorial frameworks identify social and graph structure, while also supporting accurate graph-type classification.
- Conclusion: Subgraph frequencies provide a coordinate system for analyzing locally dense social graphs in addition to traditional global network perspectives.The approach focuses on the dense structure of small graph collections such as neighborhoods, groups, and events.
- Conclusion: The paper develops complementary frameworks for identifying empirical social structure and fundamental combinatorial limits shared by graphs.The empirical framework characterizes graph-formation forces, while the extremal framework uses combinatorial constraints.
- Conclusion: The same coordinate system supports accurate classification of graph types using simple subgraph-frequency descriptions.The conclusion connects the representational framework to the demonstrated classification application.
- Resources: Implementations of the equilibrium solver and subgraph-frequency bounds optimization program are available from the first author’s webpage.The paper identifies these released implementations as covering both major computational frameworks.