Source-linked AI summary
Random walks on hypergraphs
Timoteo Carletti, Federico Battiston, Giulia Cencetti, Duccio Fanelli
TL;DR
Pairwise network models cannot represent many interactions involving groups of arbitrary size, motivating a hypergraph-based random walk. The paper derives transition and stationary-state formulas from a microscopic within-hyperedge exchange model, and shows that the framework changes rankings and supports classification while reducing to the standard network walk in the pairwise case.
Problem
Interactions involving more than two nodes are not properly described by pairwise networks, motivating higher-order models for such systems.
Method
The paper defines a hypergraph random walk in which multi-body proximity makes exchanges within shared hyperedges more probable, and derives its stationary distribution and generalized Laplacian.
Results
The framework is compared with projected-network random walks for node ranking and is applied to classification tasks, while its Laplacian reduces to the standard one for pairwise edges.
Takeaways & Limitations
Higher-order interactions can alter stationary rankings relative to projected networks, and random-walk information can be used for ranking and classification.
Takeaways & Limitations
The analysis is limited to discrete-time random walks, with continuous-time dynamics left for future work.
Abstract
from arXiv · showhide
In the last twenty years network science has proven its strength in modelling many real-world interacting systems as generic agents, the nodes, connected by pairwise edges. Yet, in many relevant cases, interactions are not pairwise but involve larger sets of nodes, at a time. These systems are thus better described in the framework of hypergraphs, whose hyperedges effectively account for multi-body interactions. We hereby propose a new class of random walks defined on such higher-order structures, and grounded on a microscopic physical model where multi-body proximity is associated to highly probable exchanges among agents belonging to the same hyperedge. We provide an analytical characterisation of the process, deriving a general solution for the stationary distribution of the walkers. The dynamics is ultimately driven by a generalised random walk Laplace operator that reduces to the standard random walk Laplacian when all the hyperedges have size 2 and are thus meant to describe pairwise couplings. We illustrate our results on synthetic models for which we have a full control of the high-order structures, and real-world networks where higher-order interactions are at play. As a first application of the method, we compare the behaviour of random walkers on hypergraphs to that of traditional random walkers on the corresponding projected networks, drawing interesting conclusions on node rankings in collaboration networks. As a second application, we show how information derived from the random walk on hypergraphs can be successfully used for classification tasks involving objects with several features, each one represented by a hyperedge. Taken together, our work contributes to unveiling the effect of higher-order interactions on diffusive processes in higher-order networks, shading light on mechanisms at the hearth of biased information spreading in complex networked systems.
INTRODUCTION
The paper addresses the limits of pairwise network models by introducing random walks on heterogeneous hypergraphs with arbitrary-size group interactions. The framework analytically characterizes stationary behavior and supports ranking and classification applications.
- Motivation: Real-world interactions often involve more than two nodes and are therefore not fully represented by traditional pairwise networks.Higher-order network models are motivated by biological and social systems with group dependencies.
- Higher-order representation: Hypergraphs represent arbitrary-size interactions through hyperedges, including author collaborations, group social interactions, and biochemical reactions.Unlike simplicial complexes, a hyperedge need not imply all associated lower-order pairwise interactions.
- Higher-order representation: Projecting a hypergraph into a network replaces each hyperedge with a clique, potentially obscuring its original higher-order structure.The projection converts each group interaction into pairwise links.
- Proposed dynamics: The proposed random walk treats exchanges within the same hyperedge as more probable, allowing information to remain longer in clustered groups.This physical motivation differs from uniformly choosing among all neighboring nodes.
- Proposed dynamics: The dynamics has an analytically derived stationary distribution and a generalized Laplacian that becomes the standard random-walk Laplacian for pairwise edges.The framework is developed without restricting hyperedge sizes to triangles or another fixed dimension.
- Applications: Applications compare hypergraph and projected-network rankings and extend the framework to ranking and classification tasks.The paper presents these as two directions for exploiting the dynamical framework.
MODEL
The model defines transition probabilities from hypergraph incidence and adjacency structure, favoring movement within shared hyperedges. It derives an exact stationary distribution and a generalized Laplacian, while identifying the corresponding weighted projected-network representation.
- Representation: A hypergraph consists of nodes grouped into unordered hyperedges, reducing to an ordinary network when every hyperedge contains exactly two nodes.This establishes the pairwise case as a limiting case of the formalism.
- Transition probability: The transition rule favors nodes sharing a hyperedge because higher-order proximity makes exchanges within that group more probable.The resulting dynamics can keep information inside a hyperedge for extended periods.
- Transition probability: The hyperdegree combines the number and sizes of hyperedges containing a node.It provides a structural quantity used in the transition probabilities.
- Stationary solution: The stationary distribution is the left eigenvector of the transition matrix associated with eigenvalue 1, and an exact analytical solution is obtained.The solution incorporates the higher-order structure of the hypergraph.
- Laplacian: The generalized random-walk Laplacian reduces to the standard network Laplacian when all hyperedges have size 2.The associated operator is non-negative definite, has real eigenvalues, and has smallest eigenvalue zero.
- Scope: The analysis is restricted to discrete-time random walks, leaving the continuous-time case for future work.The formalism is stated to extend to continuous time, but that case is not analyzed here.
- Weighted projection: The process is equivalent to a random walk on a weighted projected network whose link weights scale with the sizes of the hyperedges containing the nodes.These weights arise from the microscopic model rather than being arbitrary assignments.
RESULTS
Higher-order interactions can change stationary occupancy and node rankings relative to projected-network random walks, especially at intermediate structural regimes. In controlled synthetic hypergraphs, these differences disappear at limiting configurations but can produce ranking inversions and strong top-list turnover between limits.
- Star-clique rankings: The hypergraph walk can rank nodes differently from the projected-network walk because it accounts for higher-order relations rather than only degree.In the star-clique model, the projected walk ranks by degree, whereas the hypergraph walk incorporates the organisation of nodes within hyperedges.
- Star-clique rankings: For fixed hyperedge size k, ranking inversion occurs when ˆk < m < ˜k: the hypergraph ranks c first, while the projected network ranks h first.The rankings coincide when m < ˆk or m > ˜k, with ˆk = k + 1 and ˜k = 1 + (k − 1)^2.
- Three-body interactions: Intermediate fractions of 3-hyperedges create heterogeneous hypergraph stationary states despite uniform projected-network occupancy, while f = 0 and f = 1 yield homogeneous states.The controlled model keeps every node's projected degree unchanged, so q_i = 1/N throughout; only intermediate f changes the hypergraph stationary state.
- Three-body interactions: At f = 0 and f = 1, hypergraph and projected-network rankings coincide, but intermediate f lowers the modified Jaccard index and produces larger turnover among shorter top lists.The comparison uses M = 100, 300, and 500; smaller M values show much lower similarity, indicating stronger changes near the top.
- Larger hyperedges: In the ring-to-dense-network model, rankings match at the initial ring and fully connected limits but change abruptly after adding only a few links.For M = 5, 10, and 20, ˆJ reaches 1 at l = 20 and then drops to low values as small 3-hyperedges appear.
Node ranking
Random walks on hypergraphs produce node rankings that can differ from those of random walks on projected networks, especially when collaboration groups carry higher-order structure. In arXiv collaboration data, these differences reflect authors’ participation in papers with varying numbers of co-authors and reveal domain-specific publication habits.
- ArXiv collaborations: ArXiv collaboration data are analysed by comparing stationary distributions from random walks on hypergraphs and their projected networks.The stationary probabilities are normalised by their relative maxima for visual comparison.
- ArXiv collaborations: Authors are ranked differently by the two processes because the hypergraph walk is more sensitive to group organisation.Departures from the main diagonal indicate information added by the hypergraph-based ranking.
- ArXiv collaborations: Authors highly ranked by both processes have written many papers with many different collaborators and have also contributed to papers with many co-authors.The scatter plot’s top-right region identifies this combination of high degree and large hyperedge size.
- ArXiv collaborations: Authors favoured by the network walk tend to publish several papers with few co-authors, whereas authors favoured by the hypergraph walk tend to participate in fewer, larger collaborations.These patterns correspond respectively to the bottom-right and top-left regions of the comparison plot.
- Publication habits: Different publication habits occur across arXiv-hep subdomains despite similar broad distributions of node degrees and hyperedge sizes.The four subdomains are experimental, lattice, phenomenology, and theory.
- Implications: Higher-order rankings can support bibliographic corrections by weighting participation in large collaborations differently from work performed in small groups.The hypergraph Laplacian is equivalent to that of a suitably weighted projected network.
Classification task
The paper applies a hypergraph spectral embedding to classify animals represented by multiple features. On the zoo dataset, the resulting embedding clusters known classes and outperforms the projected-network random-walk framework.
- Method: The method embeds animals using eigenvectors associated with the smallest eigenvalues of the hypergraph random-walk Laplacian.The first three eigenvectors define the reported three-dimensional embedding.
- Interpretation: The hypergraph formulation improves classification by retaining feature-based higher-order structure rather than reducing similarities to pairwise links.This setting treats groups of objects sharing features as the relevant relational structure.
- Setup: The classification task represents 101 animals as nodes and their 16 features as hyperedges, with animals assigned to zoological classes.Features include tail, hair, and legs; classes include mammals, birds, reptiles, fish, amphibians, bugs, and invertebrates.
- Results: ARI = 0.54 for K-means clustering in the three-dimensional embedding against the seven-class ground truth.The embedding visually places animals with the same class label into clusters.
- Results: The projected-network Laplacian gives a less performant classification and is less sensitive to differences among nodes.Its embedding causes multiple nodes to overlap and leaves some classes confusingly mixed.
CONCLUSIONS
The paper introduces random walks on heterogeneous hypergraphs, derives their stationary distributions, and evaluates their sensitivity to higher-order structure. Applications to collaboration ranking and animal classification show information unavailable from corresponding projected-network walks.
- Contributions: The paper introduces a random-walk class for heterogeneous hypergraphs and derives an analytical stationary distribution based on hypergraph structure.Hyperedge sizes are incorporated through a self-consistent weighting recipe grounded in a microscopic random process.
- Findings: The resulting dynamics produces stationary distributions that differ from those of random walks on corresponding projected networks and remain sensitive to higher-order structure.The comparison is supported by numerical simulations and analytical arguments on synthetic and real-world networks.
- Applications: In collaboration networks, the framework provides richer node-ranking and centrality information than traditional methods.The additional information reflects how individuals participate in groups of collaborators.
- Applications: The framework also supports classification using objects’ multi-feature higher-order structure.The conclusion identifies classification as a second application alongside collaboration analysis.
Appendix A: About the projected network
The projected network can erase the distinction between nested hyperedges, making the original hypergraph unrecoverable from the unweighted projection. Weighted projections preserve some multiplicity information but do not remove all computational difficulty.
- Definitions: A hypergraph is simple when no hyperedge contains another; nested hyperedges make it non-simple.H1 is simple, whereas H2 is non-simple because E4 is contained in E3.
- Projection: The unweighted projection of H2 becomes a complete three-node clique and loses the existence of the smaller hyperedge E4.Consequently, inverting the projection cannot recover H2.
- Limitation: Recovering the original hypergraph from projections can become computationally costly when hyperedges are large.The difficulty follows from the combinatorial structure of the inversion problem.
- Weighted projection: A weighted projection assigns edge weights according to the number of hyperedges containing each pair.In H2, edge (a, b) has weight 2 because it belongs to both E3 and E4.
Appendix B: Transition probability
The appendix derives transition probabilities by weighting shared hyperedges according to their sizes, normalizing over connected hyperedges, and allowing optional nonlinear size biases.
- Transition construction: Transition probabilities count each shared hyperedge’s size minus one, then normalize over the hyperedges connected to the starting node.A shared hyperedge contributes C_αα − 1 when both nodes belong to it.
- Matrix formulation: The transition matrix is rewritten using the hyper adjacency matrix and a diagonal matrix retaining the diagonal of the hyperedge-overlap matrix.This compact form connects the generalized process to network random-walk notation.
- Generalization: The resulting probabilities apply to non-simple hypergraphs, including repeated and weighted hyperedges.The framework therefore does not require every hyperedge to be unique or unweighted.
- Nonlinear transition rates: A nonlinear exponent γ can bias target selection toward larger hyperedges when γ > 0 or toward smaller hyperedges when γ < 0.The linear size-probability assumption is thus an extensible modeling choice rather than a fixed requirement.
- Nonlinear transition rates: Further choices of nonlinear transition rates are possible, but their exploration is left for future work.
Appendix C: Stationary solution and ranking
The stationary distribution provides a hypergraph-based node ranking that can differ from projected-network degree ranking because it incorporates higher-order structure.
- Stationary solution: The stationary state is obtained analytically as the fixed point p(∞) = p(∞)T of the transition matrix.The proposed stationary expression is verified by substitution into the governing dynamics.
- Ranking principle: Hypergraph random-walk ranking scales with dH, whereas projected-network random-walk ranking scales with node degree k_i.The two processes therefore emphasize different structural properties.
- Ranking inversion: In the left Fig. 10 example, a node in three 2-hyperedges is ranked below a node in one 3-hyperedge by the hypergraph walk, reversing the projected-network ordering.The example demonstrates that higher-order organization can invert rankings.
- Ranking inversion: In the right Fig. 10 example, node i has k_i = 4 and dH_i = 6, while node j has k_j = 3 and dH_j = 9.Thus k_i > k_j but dH_i < dH_j, producing the same type of ranking inversion.
Appendix D: Heterogeneity of stationary solution
The hypergraph stationary distribution is more heterogeneous than the projected-network distribution in the examined synthetic models, as measured by the Gini coefficient.
- Heterogeneity measure: The hypergraph stationary solution is more sensitive to how nodes are organized into groups than the corresponding projected-network solution.The Gini coefficient quantifies the resulting heterogeneity in equilibrium occupation probabilities.
- Star-clique model: The hypergraph-to-projected-network Gini ratio is examined while varying clique and star sizes in the star-clique model.
- Lattice-to-fully-connected model: The lattice-to-fully-connected model compares hypergraph and projected-network Gini coefficients as links are added.The hypergraph values are shown in red and projected-network values in green.
- Comparison: The hypergraph walk has a larger stationary-state Gini coefficient than the projected-network walk throughout the reported comparisons.Accordingly, walker occupation is more heterogeneous on the hypergraph.
Appendix E: Co-authorship networks from arXiv
The appendix applies the hypergraph walk to arXiv co-authorship data, comparing rankings based on group size with rankings based on distinct collaborators.
- Data construction: The co-authorship hypergraph represents authors as nodes and papers’ author groups as hyperedges, alongside the associated projected network.
- Data preparation: The analysis retains the largest connected component and maximal unique hyperedges to compare the hypergraph with its projection.Table I reports component sizes, hyperedge counts, links, largest hyperedge size, and maximum degree.
- Data limitation: The dataset’s maximality and uniqueness assumptions prevent estimating subset co-authorships and paper counts between collaborator pairs.The method itself also works without these assumptions.
- Cross-domain structure: Degree and hyperedge-size distributions have similarly broad tails across the arXiv subdomains despite differing publication habits.
- Ranking interpretation: The hypergraph walk emphasizes co-author counts, while the projected-network walk emphasizes the number of distinct collaborators.Both are applied to unweighted hypergraphs and networks.
- Ranking regions: Authors in the top-right ranking region score highly under both walks because they combine many papers, collaborators, and large author groups.
- Ranking regions: Authors in the bottom-right region favor network ranking, whereas authors in the top-left region favor hypergraph ranking.These regions correspond respectively to many small-group papers and fewer large-group papers.
Appendix F: The zoo UCI database
The zoo dataset represents animals as nodes and shared features as hyperedges, with classes used as a classification benchmark. Projecting each feature hyperedge into a clique produces less distinct embeddings than preserving higher-order information.
- Dataset: The zoo dataset contains 101 animals described by 15 boolean features and an additional number-of-legs class.The number-of-legs attribute was replaced with five boolean features for homogenisation.
- Dataset: The dataset is intended to benchmark assigning animals to their correct class from associated features.
- Hypergraph construction: Animals form hypergraph nodes, while each feature forms a hyperedge containing all animals sharing that feature.
- Hypergraph construction: The projected network replaces every feature hyperedge with a complete clique linking all animals that share the property.This projection is equivalent to projecting a bipartite animal-feature network.
- Results: Projected-network embeddings are less sensitive to node differences, causing overlaps and confusing mixtures of differently classified animals.Some nodes cluster correctly, but others remain mixed; analogous 3D embeddings show similar conclusions according to the cited ARI scores.