Source-linked AI summary
Higher-order organization of complex networks
Austin R. Benson, David F. Gleich, Jure Leskovec
TL;DR
Existing approaches can be difficult to interpret, motivating higher-order network partitioning. The framework uses motif-based weighted graphs and retains a Cheeger inequality, while motifs with more than three nodes require higher-degree rather than quadratic formulations.
Problem
Existing approaches proceeding from graph circulations or random walks are difficult to interpret.
Method
The framework represents motif structure through a motif Laplacian formed from a motif-weight matrix and a corresponding weighted graph.
Results
A Cheeger inequality still holds for the weighted graph, while the four-element indicator formulation is quartic rather than quadratic.
Takeaways & Limitations
Higher-order partitioning can retain mathematical guarantees through the weighted-graph formulation, even when direct motif inequalities no longer apply.
Takeaways & Limitations
For motifs with more than three nodes, the framework no longer provides the motif Cheeger inequalities.
Abstract
from arXiv · showhide
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
The framework generalizes spectral clustering to higher-order network motifs by defining motif instances, motif conductance, and associated weighted graphs. It provides Cheeger-style guarantees for three-anchor motifs, while larger anchored motifs retain weaker guarantees and extensions support multiple motif types.
- Motif definitions: The method defines structural motifs using a binary edge-pattern matrix B and an anchor set A, with motif instances formed from induced subgraphs matching B.Anchors identify the nodes used to define motif conductance; anchored motifs generalize simple motifs.
- Motif conductance: Motif conductance replaces graph edges with motif instances and counts cuts when anchor nodes lie on both sides of a partition.The corresponding volume counts motif-instance endpoints in a set.
- Guarantees: The motif Cheeger inequality guarantees that Algorithm 1 finds a cluster within a quadratic factor of the optimal motif conductance and can identify motifs that cannot yield good clusters.The framework therefore supplies a mathematical optimality guarantee for the clustering procedure.
- Spectral formulation: For three-anchor motifs, motif conductance equals conductance on a weighted graph constructed from the motif adjacency matrix.This equivalence follows from the motif cut and volume relationships.
- Scope and extensions: For motifs with more than three anchors, the indicator function is quartic rather than quadratic, so the motif Cheeger inequalities guaranteed for three anchors no longer hold.The weighted-graph formulation still yields a Cheeger inequality, but it is expressed in terms of the weighted graph rather than the original motif conductance.
- Scope and extensions: The framework extends to simultaneous clustering with several motifs and to signed, colored, and weighted motifs, while also connecting motif clustering to directed-graph partitioning and hypergraph partitioning.Motifs can supply hyperedges rather than taking hyperedges as given a priori.
S2 Computational complexity and scalability of the method
The method’s computational cost depends on motif enumeration and scales from worst-case guarantees to empirical performance on large real-world networks. Experiments show practical computation of triangular and larger clique motifs across networks ranging up to billions of edges.
- Computational analysis: Motif adjacency construction is governed by the cost of finding motif instances, while subsequent spectral and sweep-cut steps are also analyzed.The framework forms W_M, computes a motif-Laplacian eigenvector, orders nodes, and performs a sweep cut.
- Computational analysis: Sparse-network assumptions enable practical algorithms based on edge count and maximum degree, but motif adjacency matrices can require additional storage for wedges.Wedge motifs create fill-in among two-hop neighbors, potentially producing more nonzeros than the original adjacency matrix.
- Computational analysis: For triangular motifs, the worst-case computational complexity is Θ(m^1.5), including directed networks.The same bound applies after undirecting a directed graph, enumerating triangles, and checking their directed motif types.
- Experimental scalability: On 16 real-world networks, empirical scaling for W_M was Θ(m^1.2), with the largest regression coefficient 1.31 for M3 and a combined coefficient of 1.17.The networks ranged from hundreds of thousands to two billion edges, and the observed scaling was better than the worst-case guarantee.
S4 Alternative clustering algorithms for evaluation
The evaluation compares motif-based spectral clustering with edge-based spectral clustering, Infomap, and Louvain across neural and transportation networks. Motif-based methods identify structures that differ from conventional clusters and, in transportation data, better capture airport hubs and geography.
- Alternative methods: The evaluation compares motif-based spectral clustering with edge-based spectral clustering, Infomap, and Louvain.Infomap and Louvain directly output node labels, whereas spectral methods also provide Euclidean node embeddings and allow control over cluster number.
- C. elegans network: Only 2 of the 63 nodes in the M8-based cluster are in the edge-based cluster, indicating that these partitions provide roughly the same information.The Mbifan cluster is the smallest and has substantial overlap with Infomap, but existing methods do not capture the same information as motif Mbifan.
- C. elegans network: Edge-based and M8 spectral clustering find spatially coherent C. elegans clusters rather than the control structure formed by the bi-fan motif.The comparison uses the cluster from each method with the largest overlap with the Mbifan-based cluster.
- Transportation network: In the transportation reachability network, motif-based embeddings more strongly capture airport hubs and the network’s west-east geography.The analysis ignores travel times and compares embeddings derived from several connectivity matrices.
S7 Additional case studies
Additional case studies show that motif-based clusters reveal structures that differ from edge-based clusters across several real-world networks. They also more accurately identify known functional modules in a yeast transcription-regulation network.
- Additional case studies: Motif-based clusters find markedly different structures from edge-based clusters in many real-world networks.The case studies span yeast transcription regulation, English Wikipedia, Twitter, the Stanford web graph, and collaboration networks.
- Yeast transcription regulation: In the yeast transcription-regulation network, motif-based clustering more accurately finds known functional modules than existing methods.The comparison concerns a transcription-regulation network of yeast.
- Web, Twitter, and collaboration networks: Motifs identify anomalous clusters in the English Wikipedia article network and the Twitter network.Other case studies use previously studied motifs to reveal organizational structure in the Stanford web graph and collaboration networks.
S7.1 Motif M6 in the Florida Bay food web
In the Florida Bay food web, motif M6 reveals higher-order modular organization associated with mutual feeding and shared predation, whereas M5 and M8 do not reveal comparable low-conductance structure. The resulting four clusters align with ecological organization, and motif-based embedding plus k-means performs best on the reported classification criteria.
- Motif interpretation: Motif M6 models two mutually feeding species that also prey on a common third species, while M5 and M8 encode different energy-flow patterns.M5 represents hierarchical energy flow, and M8 represents one species serving as an energy source for two non-interacting species.
- Higher-order organization: 0.12: the algorithm’s M6 cluster has lower motif M6-conductance than any possible cluster’s lower bound.The lower bounds for M5, M6, and M8 are 0.2195, 0.0335, and 0.2191, while the corresponding algorithmic conductances are 0.4414, 0.1200, and 0.4145.
- Food-web clusters: Motif M6 clustering reveals four food-web clusters, including aquatic layers, predators, macroinvertebrates, and microfauna supported by particulate organic carbon and free bacteria.The clusters include pelagic, benthic, and sea-floor ecological groupings, with a fourth cluster identifying microfauna.
- Evaluation: Motif-based embedding plus k-means has the best performance for every classification criterion on both ecological classifications.The criteria are adjusted Rand index, F1 score, normalized mutual information, and purity; the comparison includes six methods.
- Higher-order organization: Motif M6 reveals rich higher-order modular structure in the food web, whereas M5 and M8 have high motif conductance and do not reveal higher-order organization.The framework identifies low-conductance clusters only for M6, with motif conductance 0.12.
S7.3 Motif M6 in the English Wikipedia article network
The English Wikipedia hyperlink network contains millions of articles and links, and motif M6 clustering identifies a small Philippine cities-and-administrative-divisions cluster with a distinctive linking pattern. The motif-based cluster is presented as anomalous relative to the larger edge-based cluster.
- Network and method: The English Wikipedia network contains 4.21 million article nodes and 101.31 million hyperlink edges.An edge from node i to node j represents a hyperlink from the ith article to the jth article.
- Network and method: Algorithm 1 finds motif-based clusters for motifs M6 and Medge on the largest connected components of their motif adjacency matrices.The resulting clusters are shown in Figure S13.
- Motif M6 cluster: The M6 motif-based cluster consists of cities and small administrative divisions in the Philippines.The cluster contains 22 nodes and 338 links, with nodes having many outgoing links that form the source node in motif M6.
- Comparison: The linking pattern in the motif-based cluster appears anomalous and suggests that pages receiving uplinks might receive reciprocated links.The edge-based cluster is much larger and contains several high-degree nodes but does not have much structure.
S7.4 Motif M6 in the Twitter follower network
In the Twitter follower network, motif-based clustering identifies anomalous structures that differ from edge-based clusters. The M6-based cluster groups photography-company holding accounts, while the edge-based cluster forms a near-clique with similar usernames.
- The Twitter follower graph contains 41.65 million users and 1.47 billion edges.
- The edge-based cluster contains 44 nodes, providing a different partition from the M6-based cluster.
- The motif-based cluster consists of photography-company holding accounts, with completed profiles linked bidirectionally and incomplete profiles followed by completed accounts.
- The edge-based cluster is a near-clique whose usernames begin with “LC ”, whereas the M6 and edge-based methods identify anomalous clusters with different structures.
- Protected tweets prevent verification of whether the similar usernames represent social communities, holding accounts, or bots.
S7.5 Motif M7 in the Stanford web graph
Motif M7 reveals a core–periphery organization in the Stanford web graph that differs from the edge-based partition. Its core contains high-in-degree sink nodes, while peripheral groups contain bidirectional links and uplinks to the core.
- The Stanford web graph contains 281,903 nodes and 2,312,497 edges linking pages within the Stanford domain.
- M7 is over-expressed in web graphs, and Algorithm 1 identifies a motif-based cluster based on this motif.
- The M7 cluster contains several high-in-degree core nodes serving as motif sink nodes and peripheral groups with many bidirectional links.
- Peripheral groups uplink to the core, suggesting that similar pages tend to link to more central pages.
- The edge-based cluster also has a small core of high-in-degree nodes, with mostly unconnected neighbors on the periphery.
- S7.6 Semi-cliques in collaboration networks: In collaboration networks, semi-clique motif clusters form degree-structured cores and peripheries, unlike edge-based clique clusters.
S8 Data availability
The project website provides access to the datasets used throughout the experiments and supplementary material.
- All experimental data are available at the project website.
- The website links to datasets used throughout the supplementary material.