Source-linked AI summary
Emergence in Network Systems is Bounded by Boundary-Crossing Paths
Johnny Jingze Li, Gabriel A. Silva
TL;DR
Emergence is often discussed in complex systems, but its source is rarely located, and its measurement depends on the observation. This paper gives a structural, path-based account of emergence in coupled networks. Boundary-crossing paths attribute emergent features and bound the discrepancy, with the framework validated across network experiments.
Problem
The source of emergence in coupled systems is rarely located, despite its importance across complex systems.
Source: §1 · p. 1Method
The paper compares observations of a coupled network with combined observations of its parts and analyzes the paths crossing their interface.
Source: §1 · p. 1, §1.2 · p. 3Results
The path-based identity and bound hold exactly across experiments, and boundary-crossing paths bound the total discrepancy while accounting exactly for route-summing observables.
Source: §6.10 · p. 25, §8 · p. 28Takeaways & Limitations
Boundary-crossing paths locate the components and interactions responsible for emergence and predict how removing interaction edges changes it.
Source: §8 · p. 28The witness-map treatment is for disjoint parts; extending it to overlapping parts or graph-derived partitions remains open.
Source: §7.3 · pp. 27–28
Abstract
from arXiv · showhide
Emergence, features of a whole that no part shows alone, is central to complex systems but rarely measured so as to locate its source. Viewing a system structurally, as a network of interacting parts, we evaluate emergence as what observing the coupled whole reveals beyond, or erases from, the combined observations of the parts. For observations that build what they see route by route, we show that every emergent feature is produced by its own route across the interface between parts, a route that traces it to the components and interactions responsible. We show the number of all such boundary-crossing paths bounds the total emergence discrepancy, and equals the emergence of measures that count routes. The bound is computed locally around the interface, validated through network examples, and in a nervous system the routes show that interneurons relay most of the emergence. Our work associates emergence with path structure in the network system that can be anticipated, attributed, and engineered.
1 Introduction
The paper asks how to locate and quantify emergence in coupled systems, treating it as the discrepancy between observing the whole and combining observations of its parts. It traces route-based emergence to boundary-crossing paths, which bound the discrepancy and identify its structural sources.
1 Introduction
- The paper frames emergence as a structural question: which interactions produce it, and how much a coupling can create.It motivates these questions with examples from interdependent networks, neural computation, and language models.Source: §1 · p. 1
1.1 Emergence from a structural perspective
- A structural account makes the observation explicit and locates emergence at the interface between interacting parts.Emergence is relative to the observation: it is what the observed whole adds beyond, or erases from, the observed parts joined by their interaction.Source: §1.1 · p. 2
1.2 The idea: emergence travels along boundary-crossing paths
- For observations acting on paths, each emergent edge has a distinct boundary-crossing witness, and the number of such paths bounds emergent edges.The whole discrepancy, including lost edges, is bounded by all boundary-crossing paths; for observables that sum over routes, those paths give emergence exactly.Source: §1.2 · p. 3
1.3 Why this matters
- The bound is mechanistic: crossing paths identify responsible components and interactions, and cutting channels suppresses emergence while bridges between structured modules can amplify it.For observations reading at least three steps, the path count ranks candidate couplings better than cut size, interface degrees, or edge betweenness.Source: §1.3 · pp. 3–4
1.4 Contributions and organization
- The contributions include a path-based theorem with attribution and locality results, analyses of removing interaction edges, and experiments across synthetic and empirical networks.The paper also describes a subsystem bound based on walks through its boundary.Source: §1.4 · p. 4
2 A structural framework
The framework represents systems as disjoint network parts joined by cross-edge interactions and makes the observation rule explicit. It uses bounded paths to turn coupling into an additive, route-by-route account.
2.1 Systems, interaction, and boundary
- Parts are directed graphs on disjoint vertex sets; their interaction consists of cross edges, and the boundary is the set of interaction-edge endpoints.The join preserves each part and adds the prescribed interaction; the framework also applies to multiple pairwise-disjoint parts.Source: §2.1 · p. 5
2.2 Observations
- An observation is a graph rule with a fixed vertex map; examples include reachability, thresholding, coarse-graining, and context-reading deletion rules.Among the listed examples, only observations that read routes produce emergence.Source: §2.2 · p. 6
2.3 Paths as the basic objects
- Paths restore additivity: paths in the joined system divide into those within either part and those traversing an interaction edge.Simple paths are used as channels because a walk that revisits a vertex retraces a channel already opened; in feedforward networks, every walk is already a path.Source: §2.3 · p. 7
3 Emergence as the gap between the whole and its parts
Emergence is the gap between observing the joined system and combining observations of its parts with their interaction. The gained and lost edges identify what the whole reveals or erases.
3 Emergence as the gap between the whole and its parts
- Forming the interaction after observation fixes the baseline, so coupling edges themselves are not emergent; identity observation produces no discrepancy.Source: §3 · pp. 7–8
- Emergence is the structure revealed by observing the whole beyond the observed parts and their interaction; lost edges are structure that combination shows but the whole erases.Source: §3 · pp. 7–8
- In Figure 4, observing the joined chain adds (a, c) and (b, d), each from a length-two path through (b, c), while the lost-edge set is empty.Source: §3 · p. 8, Figure 4 · p. 8
- For monotone observations, lost edges are exactly interaction edges destroyed by observing the whole; thresholding away a weak interaction edge loses that edge.Source: §3 · p. 8
- Degree-based deletion shows both directions: joining erases all four edges under Φhi, while Φlo retains three edges because coupling raises b and c's degrees.Source: §3 · p. 9
- Unlike route-by-route observations, degree-based observations can retain two edges entering one vertex even when they share no route and each is deleted alone.Source: §3 · p. 9
4 Emergence is bounded by boundary-crossing paths
The section examines how boundary-crossing paths produce emergence, identify its causes, and bound the discrepancy for observations built route by route. Scalar emergence is the total weight of these paths; they exactly account for path-count emergence and bound emergence for every observation acting on paths.
4.1 Observations acting on paths
- An observation acts on each path of length at most L independently of its containing graph; examples include graph powers, coarse-graining, and dropping sinks.These observations build observed edges from individual routes, and monotone observations lose only images of interaction edges they destroy.Source: §4.1 · p. 9
4.2 Boundary-crossing paths and the main theorem
- Emergent edges are exactly produced by boundary-crossing paths that are absent from the observed union, and the whole discrepancy is bounded by the number of all boundary-crossing paths.The number of emergent edges is also bounded by the number of boundary-crossing paths that produce an edge.Source: §4.2 · pp. 10–11
- Every emergent edge has a length-at-most-L witness through an interaction edge, with vertices before and after it within L−1 steps of the interface.Witness routes attribute edges to responsible components; splitting credit equally among paths producing a shared edge gives choice-free attribution, and the interface’s credit equals the number of emergent edges.Source: §4.2 · pp. 10–11
4.3 A single bridge: emergence multiplies reach
- For a G≤3 bow-tie, N∂=1+k+m+km and emergence is k+m+km; the km term pairs vertices reaching and reached from the interface.The bound exceeds emergence only by the interaction edge in this example.Source: §4.3 · p. 13
4.4 Scalar observations
- For scalar measures decomposed over simple paths, boundary-crossing paths give exact emergence; for walk sums, interaction-crossing walks play the same role.Examples include path counts and attenuated Katz and communicability sums.Source: §4.4 · p. 14
- Scalar emergence equals the total weight of boundary-crossing paths, with one route for each emergent edge.The same paths bound the emergence of every observation acting on paths.Source: §4.4 · p. 15
- With disjoint parts, path-count emergence equals the number of boundary-crossing paths; under graph power G≤L, it also equals the bound N∂.Source: §4.4 · p. 15
- For positive edge weights, weighted path-count emergence sums the weights of boundary-crossing paths; when weights are below one, maximum path weight decays geometrically with path length.Source: §4.4 · p. 15
5 What produces emergence
For route-reading observations, boundary-crossing paths account for emergence and identify its source. Removing productive paths suppresses emergence, while adding interaction edges can open many channels.
5.1 Emergence requires routes
- Observations that decide edges from single edges produce no emergence; route-reading observations can produce it through boundary-crossing routes of length at least two.Thresholding and fixed-partition coarse-graining are edgewise when fixed in advance; path closures and coarse-grained powers read routes.Source: §5.1 · pp. 15–16
5.2 Observations that read routes
- In three examples, a sink rule yields one witness path, a four-cycle yields two emergent edges from four crossing cycles, and coarse-grained G≤2 attains the sharpened bound.In the coarse-grained example, two length-two paths produce new links between blocks even though the block X straddles the interface.Source: §5.2 · pp. 16–17
5.3 Suppressing emergence by cutting channels
- When no boundary-crossing path is productive, the observed whole shows the parts side by side, as when thresholding removes the sole light interaction edge.With N∂=0, the whole's observation equals the union of the parts' observations.Source: §5.3 · p. 17
- Removing interaction edges preserves emergence exactly when some productive boundary-crossing path avoids the removed edges; otherwise, features whose routes all use them are removed.Removed interaction-edge images can themselves become emergent when the reduced observed union no longer contains them.Source: §5.3 · p. 17
- To suppress an emergent edge, cut every channel producing it; suppress all emergence by removing productive boundary-crossing paths, while adding bridges between internally rich regions can open many channels.The paths to cut lie within L −1 steps of the interface; removing interaction edges removes features whose whole share passes through them.Source: §5.3 · p. 18
6 Numerical experiments
Across the tested observations and network families, the boundary-crossing-path bound held, while route-reading observations produced emergence and edgewise observations did not. The experiments also show that the discrepancy relative to the bound depends chiefly on the observation.
6 Numerical experiments
- The bound held across observations and network families and was approached when routes were distinct, as in large sparse networks.The experiments compute both sides of Theorem 4.4 exactly.Source: §6 · p. 18, Figure 8 · p. 19
6.1 Method
- Experiments enumerated bounded-length paths and cycles for smaller networks, and used local search checked against direct computation for larger experiments.Emergent edges came from comparing the observed whole with the observed union; N∂ was separately computed by enumerating producing boundary-crossing paths.Source: §6.1 · p. 18
6.2 Validity across observations and network families
- Across all 3,510 Experiment 1 instances, the bound held; edgewise observations produced no emergent edges in 810 cases, while route-reading observations produced them in 1,804.The bound was attained in 37 of 3,107 instances with N∂>0, all under deletion rules.Source: §6.2 · p. 20
- The bound and its sharpened form held in all 2,560 Experiment 2 instances spanning sixteen network families and four observations.The ratio |E+Φ|/N∂ varied mainly by observation, from [0.72, 0.82] for G≤2 to [0.33, 0.47] for coarse-grained G≤2 across thirteen synthetic families.Source: §6.2 · p. 20
- The identity and equality criterion, sharpened and whole-discrepancy bounds, and local search were verified across all 8,935 tested instances.This set includes Experiments 1–3 and 1,560 random joins of three or four parts.Source: §6.2 · p. 20
6.3 Tightness
The bound is tight when boundary-crossing routes produce distinct edges, while route redundancy accounts for slack. At longer reach, network topology affects emergence, with Barabási–Albert parts producing more emergent edges than the comparison families.
6.3 Tightness
- When routes are distinct, emergence approaches the path bound: on bow-ties the ratio rose from 0.75 to 0.96 as k and m increased from 1 to 4.Adding internal chords creates alternative routes and increases redundancy, which accounts for slack.Source: §6.3 · p. 20
- With 20 added internal chords, the bound averaged 31.4 while emergent edges averaged 22.0; redundancy rose to 8.4 and the ratio fell to 0.71 ± 0.01.Across all 1,001 realizations, slack equaled one plus redundancy; sharpening raised the mean ratio from 0.62 to 0.86 in a further 4,800 instances.Source: §6.3 · p. 20
6.4 Topology and reach
- At mean total degree 4 and reach L = 4, Barabási–Albert parts yielded 154.2 ± 16.5 emergent edges against 107.7 ± 11.4 for Erdős–Rényi parts.At L = 2 the families coincided within 95% intervals; at L = 3 Barabási–Albert yielded 53.7 ± 5.1 against 43.4 ± 3.3 and 43.4 ± 3.1.Source: §6.4 · p. 21
6.5 Coarse-graining granularity
Coarse-graining makes more emergence visible as partitions are refined, while a single bridge between internally structured modules can connect many routes. In large sparse networks, boundary-crossing paths account for emergence nearly one for one, and local search scales with interface neighborhoods.
6.5 Coarse-graining granularity
- Emergence under coarse-grained G≤2 rose from 0 at c = 2 blocks to 3.55 at c = 10, with the highest values at the two finest partitions.Coarser partitions fold more boundary-crossing routes into single blocks or block pairs already in the observed union.Source: §6.5 · pp. 21–22
6.7 Scaling to large networks
- At n = 10^5, the mean |E+Φ|/N∂ ratio was 0.979–0.993 for L = 4 and 16 one-directional interaction edges, within 0.02 of the ceiling.The local search needed at most 5,029 operations for Erdős–Rényi and configuration parts, while direct computation grew by factors of 1,084 to 1,435; the ratio was within 0.001 of the ceiling at L ≤3.Source: Figure 10 · p. 22, §6.7 · p. 23
6.6 Bridging internally structured modules
- With one interaction edge and G≤4, emergent edges rose to 39.3 ± 0.7 at internal mean out-degree d = 3, while the bound reached 111.2 ± 3.4.The exact expectations were 39.0 and 110.8 at d = 3; both matched within 95% confidence intervals, and emergence rose toward 63 cross pairs.Source: §6.6 · p. 22
6.8 Comparison with simpler statistics
The section compares boundary-crossing path counts with simpler coupling statistics, then applies route-based attribution and intervention analysis to real directed networks.
6.8 Comparison with simpler statistics
- N∂ correlates with emergence more strongly than cut size, interface degree statistics, and edge betweenness across the tested conditions.Every paired difference had a bootstrap 95% interval above zero, and the advantage persisted within fixed-family, density, and interface-size cells.Source: §6.8 · p. 23
- N∂ ranked the best single coupling highest in 80% of pairs under G≤3 and 55% under G≤4, versus at most 63% and 37% for other statistics.The selected coupling realized on average 99% and 96% of the largest available emergence under G≤3 and G≤4, respectively.Source: §6.8 · p. 23
6.9 Real directed networks: attribution and intervention
- Local route search matched direct computation in the real networks; in the e-mail network under G≤3, 8.4 × 10^7 boundary-crossing paths were counted by an exact identity.The shares and intervention prediction also held exactly on 3,200 random joins of two and three parts and across 20,872 removals.Source: §6.9 · pp. 24–25
- Under G≤2, the connectome gained 16,944 emergent edges and the blog network 37,290, from 42,682 and 89,544 boundary-crossing paths.Each emergent edge was produced by an average of 1.8 routes in the connectome and 1.9 in the blog network under G≤2.Source: §6.9 · p. 24
- In the connectome, interneurons relay 66% of emergence under G≤2, with AVAR and AVAL contributing 7.1% and 6.9%.Interneuron-to-motor synapses are 25% of interaction edges but carry credit 0.42 |E+Φ|.Source: §6.9 · pp. 24–25
- Removing interaction edges in all 42 interventions removed exactly the emergent edges whose whole share passed through those edges, and the loss never exceeded their credit.New emergent edges were exactly those images of removed edges that other routes still produced.Source: §6.9 · p. 25
6.10 Summary
Boundary-crossing paths provide a structural account of emergence: they bound the whole discrepancy, attribute features to routes, and predict the effects of changing interfaces.
6.10 Summary
- For observations that act on paths, boundary-crossing paths produce the emergent edges, while their total number bounds gained and lost edges together.The number of producing paths bounds emergent-edge count, with an exact equality criterion; observables that sum over paths have emergence exactly accounted for by these paths.Source: §6.10 · p. 25
- The local search computes the bound around the interface, and N∂ predicts and ranks couplings better than cut size, interface degrees, and edge betweenness.The summary states that the search cost is set by the interface.Source: §6.10 · p. 25
- Experiments show emergence depends on observation reach and topology, rises with coarse-graining granularity, and surges when one edge bridges internally structured modules.On real directed networks, route shares locate interfaces, edges, and relay vertices carrying emergence and predict the effects of removing interaction edges.Source: §6.10 · p. 25
7 Discussion
The discussion distinguishes this structural, route-based account from prior measures and network analyses, then outlines applications and extensions that remain open.
7.1 Relation to existing work
- Unlike measures derived from dynamics or statistics, this framework computes emergence from network structure for given parts and observations, assigning it to routes across their interface.It relates boundary-crossing routes to generative effects, graph operators, path measures, incremental computation, and circuit attribution.Source: §7.1 · pp. 25–27
7.2 Applications
- For C. elegans, interface and relay credits rank the synapses and interneurons through which sensory-to-motor reach arises, while Proposition 5.7 identifies the effects of removals.The discussion connects structural connectivity and interaction among brain modules to observations at different scales.Source: §7.2 · p. 27
- Because N∂ is computed locally, candidate couplings can be ranked before they are made; in Experiment 8, its top-ranked coupling produced maximum emergence in 80% of cases under G≤3.For candidate cuts, Proposition 5.7 identifies the emergent edges destroyed, bounded by the removed edges’ credit.Source: §7.2 · p. 27
- In computational graphs, layer blocks can define parts, and boundary-crossing paths can attribute interface-level features and predict effects of removing connections.The path count can be computed exactly using sparse matrix–vector products.Source: §7.2 · p. 27
7.3 Open questions
- Open extensions include observations retaining edges confirmed by alternative routes, graph-derived partitions, evolving networks or processes, overlapping parts, and broader estimates from summary statistics.These extensions require, respectively, edge–route witnesses, handling changing vertex maps, links to dynamics, witnesses for overlapping or multi-part interactions, and expectations beyond a single bridge or homogeneous setting.Source: §7.3 · pp. 27–28
8 Conclusion
The conclusion presents emergence as a discrepancy between observations of a coupled network and its parts. For path-based observations, boundary-crossing routes bound and attribute that discrepancy, with experiments and real networks illustrating the framework’s scope.
8 Conclusion
- For path-based observations, emergent edges are exactly those produced by boundary-crossing paths, and distinct emergent edges have distinct witnesses.The number of producing paths bounds the emergent-edge count, while all boundary-crossing paths bound gained and lost edges together and account exactly for path-summing observables.Source: §8 · p. 28
- The route framework attributes features to their producing components and interactions and predicts exactly how emergence changes when interaction edges are removed.The conclusion reports exact confirmation of the identity and bound across 8,935 instances, and describes computation as local to the interface.Source: §8 · p. 28
- In real directed networks, route shares locate emergence at interfaces and relay vertices, including interneurons in C. elegans.The conclusion also reports that for observations reading three or more steps, boundary-crossing paths predict emergence better than cut size, interface degrees, and edge betweenness.Source: §8 · p. 28
- Counting the routes a coupling opens indicates how much emergence to expect and where it comes from.Source: §8 · p. 28
A Computing the discrepancy and the bound
The section gives direct and local methods for computing emergence discrepancies and bounds them using routes that cross the interaction boundary. When short directed cycles are absent, the walk discrepancy equals the boundary-crossing path count.
A Computing the discrepancy and the bound
- The discrepancy itself is computed in O(TΦ + eΦ + |I|) time by applying the observation to both parts and their join, then comparing outputs.The walk discrepancy can instead be computed with 3L sparse matrix–vector products, in O(mL) time when every vertex has an edge.Source: A Computing the discrepancy and the… · p. 29
- The boundary-path set, its count, and the set containing every emergent edge can be found in O(L |I| d^(L−1)) local-search time for d ≥ 2.This search does not require applying the observation to either part or their join; its cost is independent of part size for fixed reach and maximum degree.Source: A Computing the discrepancy and the… · pp. 29–30
- The walk discrepancy bounds the boundary-crossing paths, which bound the number of emergent edges; without short directed cycles, it equals the path count.The discrepancy counts walks in the joined system that traverse an interaction edge.Source: A Computing the discrepancy and the… · p. 29
- A local search lists boundary-crossing paths once, assigning each to its first interaction edge and searching backward in one part and forward in the join.For graph powers, bounded breadth-first searches identify endpoint pairs produced by routes staying in the destination part.Source: A Computing the discrepancy and the… · pp. 29–30
B The emergence potential of a subsystem
The emergence potential of a subsystem measures the greatest path-count emergence available from its couplings within a host network. Walks through the subsystem boundary bound that potential and connect it to familiar centrality measures.
B The emergence potential of a subsystem
- The emergence potential is the maximum path-count discrepancy over couplings the host provides for a subsystem.A coupling consists of a disjoint partner subgraph and interaction edges joining it to the subsystem.Source: B The emergence potential of a subsystem · p. 30
- For every coupling, boundary-crossing paths are walks through the subsystem boundary in the host, so their count bounds the emergence potential.The maximum is attained using the host's complement and every edge between it and the subsystem.Source: B The emergence potential of a subsystem · pp. 30–31
- The walk bound decomposes into boundary vertices’ forward reach, backward reach, and walks passing through them, with the reach terms given by truncated Katz centralities.At L = 1 the truncated sums are degrees; for strongly connected, aperiodic networks, normalized sums converge to the left and right Perron eigenvectors as L grows.Source: B The emergence potential of a subsystem · pp. 31–32
- Ranking subsystems by the walk bound requires 2L sparse matrix–vector products, followed by O(L^2) operations per boundary vertex.The bound uses walks in the host that visit the subsystem boundary.Source: B The emergence potential of a subsystem · p. 32
C Details of the experiments
The experiments test path rules, bounds, and computation across synthetic and empirical network settings. Their designs vary network families, coupling structure, observation types, and scale.
C Details of the experiments
- The path rules reproduce directly defined observations on 400 random graphs and on 1,200 additional small graphs, as well as every part and join in Experiment 1.The additional tests cover drop-sink and cycle-edge rules under several cycle-length limits.Source: C Details of the experiments · p. 32
- Experiment 1 varies thirteen observations over random weighted networks, while Experiment 2 tests standard and additional network models plus three empirical networks.Experiment 1 uses ten vertices grouped in pairs and thresholded paths of length at most three; Experiment 2 splits networks into halves.Source: C Details of the experiments · p. 32
- The bridge-law checks use 3,000 joins, and the shares and Proposition 5.7 checks use 3,200 joins with varied part counts, interaction edges, and observations.For the latter checks, every nonempty subset of interaction edges is removed in turn.Source: C Details of the experiments · p. 32
- Experiment 3 compares random four-vertex parts with a tree design placing every vertex within two steps of the interface.The tree design uses two directed binary trees of depth two and varies the number of added chords.Source: C Details of the experiments · p. 32
- Experiment 7 scales directed Erdős–Rényi, Barabási–Albert, and configuration-model parts up to 10^5 vertices.The number of realizations varies with graph size.Source: C Details of the experiments · p. 32
- Experiment 8 varies network density and interaction size, then ranks candidate subsystem pairs using edge betweenness and coarse-graining across synthetic and empirical networks.It uses bootstrap intervals and size replicates with 12- and 30-vertex synthetic parts.Source: C Details of the experiments · p. 33
- The real-network study uses a C. elegans connectome, an institutional e-mail network, and a political-blog network, with interventions cutting interfaces or high-credit interaction edges.The connectome is partitioned by neuron class; the e-mail network by department; and the blog network by political camp.Source: C Details of the experiments · pp. 33–34