PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher-order organization of complex networks

Austin R. Benson, David F. Gleich, Jure Leskovec

arXiv:1612.08447v1cs.SIcs.DMphysics.soc-ph

TL;DR

Existing directed-graph partitioning methods can be difficult to interpret, motivating higher-order network organization analysis. The paper defines motif-based conductance and shows that, for larger motifs, a Cheeger inequality still follows from an associated weighted graph, although the original inequalities no longer hold when |A| > 3.

Abstract

from arXiv · show

Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks---at the level of small network subgraphs---remains largely unknown. Here we develop a generalized framework for clustering networks based on higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.

S1 Derivation and analysis of the motif-based spectral clustering method

This section develops and analyzes motif-based spectral clustering by generalizing graph partitioning concepts to higher-order motifs. It establishes guarantees for three-node motifs and extends the framework to larger motifs, multiple clusters, diverse motif types, directed graphs, and related hypergraph partitioning settings.

S1.1 Review of the graph Laplacian for weighted, undirected graphs

  • The framework begins from the graph Laplacian and conductance of weighted undirected graphs, using quadratic forms that later generalize to motif cuts.Disconnected graphs are typically split into connected components before low-conductance clustering.Source: S1.1 Review of the graph Laplacian for… · pp. 10–11

S1.2 Definition of network motifs

  • Motifs are specified by a binary edge-pattern matrix B and an anchor-node set A, with motif instances defined from induced subgraphs matching B.The anchor set identifies the nodes used to define motif conductance, and the set operator avoids duplicate instances from symmetries.Source: S1.2 Definition of network motifs · pp. 11–12

S1.3 Definition of motif conductance

  • Motif conductance replaces edges with motif instances: a motif is cut when its anchor nodes lie on both sides, while volume counts anchored motif-instance endpoints.Instances contribute proportionally when the same anchored nodes occur in multiple motif instances.Source: S1.3 Definition of motif conductance · pp. 13–14

S1.4 Definition of the motif adjacency matrix and motif Laplacian

  • The motif adjacency matrix weights node pairs by their shared motif participation, counting only pairs that both appear in the anchor set, and yields a motif Laplacian.The normalized motif Laplacian supplies the eigenvector used by the clustering theory.Source: S1.4 Definition of the motif adjacency… · pp. 14–15

S1.5 Algorithm for finding a single cluster

  • The single-cluster algorithm constructs motif weights, computes a Fiedler partition, and selects the minimum-conductance prefix in the eigenvector sweep.Either side of the partition may represent the cluster, with the smaller side treated as the module in practice.Source: S1.5 Algorithm for finding a single… · p. 15
  • For three-node motifs, the algorithm returns a cluster whose motif conductance is at most 4√φ∗, making it nearly optimal.Here φ∗ is the smallest motif conductance over all node sets.Source: S1.5 Algorithm for finding a single… · p. 16

S1.6 Motif Cheeger inequality for network motifs with three nodes

  • The method defines a motif Cheeger inequality by relating motif conductance to a weighted motif adjacency matrix for motifs with three anchor nodes.The inequality follows from this relationship between conductance and the motif adjacency matrix.Source: S1.6 Motif Cheeger inequality for… · p. 16
  • With three anchor nodes, motif conductance equals weighted-graph conductance, and Algorithm 1 finds a cluster within a quadratic factor of optimal.The eigenvalue bound can also show that some motifs cannot provide good clusters, regardless of how the set is selected.Source: S1.6 Motif Cheeger inequality for… · pp. 19–20

S1.7 Discussion of motif Cheeger inequality for network motifs with four or more nodes

S1.8 Methods for simultaneously finding multiple clusters

  • For k > 2 clusters, the graph can be partitioned by recursively cutting the largest remaining cluster until a prespecified number of clusters is reached.This procedure is called recursive bipartitioning; an alternative motif-based clustering algorithm for several clusters is also introduced following Ng et al. (19).Source: S1.8 Methods for simultaneously… · p. 23
  • For multiple clusters, the method embeds nodes using eigenvectors of the motif Laplacian and applies k-means, but this choice lacks the single-cluster Cheeger-like quality guarantee.Alternative clustering algorithms can provide performance guarantees, while k-means is retained for simplicity.Source: S1.8 Methods for simultaneously… · p. 23

S1.9 Extensions of the method for simultaneously analyzing several network motifs

  • The method generalizes to simultaneously analyzing several motifs, including user-specified nonnegative weights whose cut and volume measures combine by linearity.All results carry through for several motifs simultaneously, with weighted motif adjacency matrices producing weighted motif conductance.Source: S1.9 Extensions of the method for… · pp. 23–24

S1.10 Extensions of the method to signed, colored, and weighted motifs

  • The framework extends to signed, colored, labeled, and weighted motifs by modifying adjacency information and counting or weighting motif instances accordingly.Signed edges are represented through a signed adjacency matrix; colored nodes require counting only instances matching the specified pattern, and weighted motifs use nonnegative instance weights.Source: S1.10 Extensions of the method to… · p. 24

S1.11 Connections to directed graph partitioning

  • The framework provides a simple, rigorous approach to directed graph partitioning, unlike existing circulation- or random-walk-based generalizations that are difficult to interpret.Symmetrizing a directed graph corresponds to weighting bi-directional edges twice and uni-directional edges once, whereas removing direction treats them equally.Source: S1.11 Connections to directed graph… · p. 25

S1.12 Connections to hypergraph partitioning

  • Motifs can induce hyperedges rather than taking them as given, and the motif Laplacian respects standard cut and volume metrics for graph partitioning.Theorem 6 explains why this Laplacian is appropriate for 3-regular hypergraphs.Source: S1.12 Connections to hypergraph… · p. 26

S2 Computational complexity and scalability of the method

This section examines the method’s computational complexity and scalability across motif types and network sizes. It covers motif-adjacency construction, spectral computation, and sweep cuts, including practical implementations and performance on large sparse and real-world networks.

S2.1 Analysis of computational complexity

  • Theoretical runtime is governed by forming WM, computing an eigenvector, and performing a sweep cut; fast Laplacian solvers compute the eigenvector in O((m + n)(log n)O(1)) time.The sweep requires O(n log n) sorting plus linear-time motif-conductance evaluation and is usually a small fraction of total runtime.Source: S2.1 Analysis of computational… · p. 27
  • For sparse graphs, motif-counting complexity depends on edges and maximum degree: directed triangle listing achieves Θ(m1.5), while wedge fill-in can make WM storage impractical.Triangle WM has fewer nonzeros than the original adjacency matrix, whereas wedge WM includes two-hop-neighbor fill-in and requires additional storage.Source: S2.1 Analysis of computational… · pp. 27–28

S2.2 Experimental results on triangular motifs

  • Up to two billion edges: the method scales across 16 real-world directed graphs, and motif adjacency matrices remain practically computable for motifs up to size 9.The tested networks contain roughly 10 thousand to over 50 million nodes.Source: S2 Computational complexity and… · p. 26, S2.2 Experimental results on… · p. 29
  • 1.62 hours was the longest eigenvector computation and 52.8 hours the longest WM computation across triangular motifs, while observed WM scaling remained below the O(m^1.5) worst-case bound.The largest regression coefficient was 1.31 for M3, and the aggregate coefficient was 1.17, supporting better-than-worst-case performance on real-world datasets.Source: S2.2 Experimental results on… · pp. 31–32

S3 Matrix-based interpretation of the motif-weighted adjacency matrix

S4 Alternative clustering algorithms for evaluation

This section evaluates motif-based clustering and embedding methods against standard and alternative algorithms across C. elegans and transportation networks. It examines how these approaches capture neuronal structure, airport hubs, geographic organization, and network connectivity.

S4 Alternative clustering algorithms for evaluation

  • Edge-based spectral clustering is a special case of motif-based clustering, while Infomap and Louvain provide alternative purely clustering-based comparisons.Infomap uses the map equation, and directed networks are handled with directed links in Infomap and the oriented Louvain method.Source: S4 Alternative clustering algorithms… · p. 38

S5.1 Connected components of the motif adjacency matrices

  • Motif adjacency preprocessing leaves 112 of 131 neurons in the largest Mbifan component, 127 in the M8 component, and all nodes connected for Medge.The 19 Mbifan-isolated neurons and 4 M8-isolated neurons are specified in the supplied passages.Source: S5.1 Connected components of the motif… · p. 39

S5.2 Comparison of bi-fan motif cluster to clusters found by existing methods

  • Sbifan is by far the smallest of the compared sets, while existing methods do not capture the same information as motif Mbifan.The M8 and edge-based spectral clusters contain 63 of 127 and 64 of 131 nodes, respectively; Sbifan is a subset of both and substantially overlaps with Infomap.Source: S5.2 Comparison of bi-fan motif… · pp. 40–41
  • M8- and edge-based spectral clustering mainly recover spatially coherent partitions, whereas the Mbifan cluster captures a distinct control structure in frontal neurons.Figure S8 shows that the M8 and edge-based partitions include the Mbifan nodes but also many additional spatially organized nodes.Source: S5.2 Comparison of bi-fan motif… · p. 41, Figure S8 · p. 42

S6 Details and comparison against existing methods for the transportation reachability network

S6.1 Methods for spectral embeddings

  • The transportation analysis compares motif, undirected, and undirected-complement adjacency matrices using two-dimensional normalized-Laplacian spectral embeddings.The motif matrix sums motif adjacency matrices, whereas the undirected method ignores edge direction and the complement connects non-hubs preferentially.Source: S6.1 Methods for spectral embeddings · pp. 43–44

S6.2 Comparison of motif-based embedding to other embeddings

  • Motif-based spectral embedding has the strongest correlations with metropolitan population and longitude, with its confidence interval separated from those of the other three embeddings for population.These comparisons are summarized in Table S7 and visualized with Loess regressions in Figure S9.Source: S6.2 Comparison of motif-based… · p. 45, Table S7 · p. 45
  • The motif adjacency matrix embedding more strongly captures the hub nature of airports and the network’s West–East geography.Source: S6.2 Comparison of motif-based… · p. 45
  • The spectral ordering provided by the motif adjacency matrix reveals a clear relationship with network connectivity.Figure S10 orders nodes by this spectral ordering and visualizes the transportation reachability network.Source: S6.2 Comparison of motif-based… · p. 45, Figure S10 · p. 46
  • Loess regressions compare how motif, undirected, and undirected-complement adjacency matrices relate spectral coordinates to population and longitude.Source: Figure S9 · p. 46

S7 Additional case studies

Additional case studies show that motif-based clustering reveals structures in real-world networks that differ markedly from edge-based clustering. Across several networks, it identifies functional modules, anomalous clusters, and organizational structure more effectively or distinctively than existing approaches.

Additional case studies

  • Motif-based clustering finds markedly different structures in many real-world networks compared to edge-based clustering.The case studies use motif-based clusters to expose higher-order organization across diverse networks.Source: S7 Additional case studies · p. 47
  • In a yeast transcription regulation network, motif-based clustering more accurately identifies known functional modules than existing methods.Source: S7 Additional case studies · p. 47
  • Motifs identify anomalous clusters in the English Wikipedia article network and the Twitter network.Source: S7 Additional case studies · p. 47
  • In the Stanford web graph and collaboration networks, previously studied motifs reveal organizational structure.These analyses apply motifs from the literature to examine network organization.Source: S7 Additional case studies · p. 47

S7.1 Motif M6 in the Florida Bay food web

This section examines how higher-order clustering and motif adjacency reveal modular organization and functional structure in the Florida Bay food web and the S. cerevisiae transcriptional regulation network.

S7.1 Motif M6 in the Florida Bay food web

S7.1.1 Identifying higher-order modular organization

  • Motif M6 alone produced low-conductance clusters, with conductance 0.12 versus high conductance for M5 and M8.The motif Cheeger inequality guarantees that M5- or M8-based clusters have larger conductance than the M6 cluster found by the algorithm.Source: S7.1.1 Identifying higher-order… · p. 48

S7.1.3 Connected components of the motif adjacency matrices

S7.2 Coherent feedforward loops in the S. cerevisiae transcriptional regulation network

  • Coherent feedforward loops are sign-sensitive delay elements, but the DAL80–GAT1–GLN3 induced subgraph also contains a bidirectional DAL80–GAT1 edge.It has unidirectional edges from DAL80 and GAT1 to GLN3, so the loop itself is not an induced three-node subgraph in this instance.Source: S7.2 Coherent feedforward loops in the… · pp. 54–55

S7.2.1 Connected components of the adjacency matrices

S7.2.2 Comparison against existing methods

  • An 18-node cluster containing CLN2, CLN1, SWI4/SWI6, SPT16, and HO contains three coherent feedforward loops, all corresponding to “cell cycle and mating type switch”.The Medge result produces a cluster {CLN1, CLN2, SPT16, SWI4/SWI6} and breaks the coherent feedforward loop formed by HO, SWI4/SWI6, and SPT16.Source: S7.2.2 Comparison against existing… · p. 56
  • 97% accuracy versus 68–82% for existing methods shows higher-order clustering identifies functional modules more accurately in the transcriptional regulation network.Motif-based clustering coherently labels all 29 labeled motifs, compared with 25 for edge-based spectral clustering and 23 each for Infomap and Louvain.Source: S7.2.2 Comparison against existing… · pp. 56–57, Figure S12 · p. 58

S7.3 Motif M6 in the English Wikipedia article network

Motif-based clustering of the English Wikipedia hyperlink network reveals a compact, structured cluster of Philippine cities and barangays, unlike the larger, less structured edge-based cluster.

Network

Motif M6

Medge

S7.4 Motif M6 in the Twitter follower network

In the 2010 Twitter follower network, motif M6 and edge-based clustering identify anomalous clusters with distinct structures, suggesting M6 can reveal new social-network anomalies.

Motif M6 in the Twitter follower network

S7.5 Motif M7 in the Stanford web graph

Motif-based clustering reveals distinct core–periphery organization in Stanford’s web graph and in two co-authorship networks. These structures differ systematically from edge-based clusters and suggest interpretable organizational mechanisms.

S7.5 Motif M7 in the Stanford web graph

  • The Stanford web graph contains 281,903 nodes and 2,312,497 edges, with directed edges representing hyperlinks between Stanford-domain pages.The network data was downloaded for analysis using Algorithm 1.Source: S7.5 Motif M7 in the Stanford web graph · p. 64
  • In the Stanford web graph, motif M7 produces a core of high in-degree sink nodes and peripheral groups linked bidirectionally that uplink to the core.This organization suggests that similar pages tend to uplink to more central pages, explaining M7’s over-expression.Source: S7.5 Motif M7 in the Stanford web graph · p. 64, Figure S15 · p. 65

S7.6 Semi-cliques in collaboration networks

S8 Data availability

All data and the datasets used throughout the supplementary experiments are available through the project website.

  • The project website provides all data and links to datasets used throughout the supplementary experiments.Available at http://snap.stanford.edu/higher-order/.Source: S8 Data availability · p. 68

Related papers

Loading 1612.08447v1…