
==== Front
Proc Natl Acad Sci U S A
Proc Natl Acad Sci U S A
PNAS
Proceedings of the National Academy of Sciences of the United States of America
0027-8424
1091-6490
National Academy of Sciences

38470928
202315931
10.1073/pnas.2315931121
research-articleResearch Articleapp-physApplied Physical Sciencessoc-scienceSocial Sciences405
432
Physical Sciences
Applied Physical Sciences
Social Sciences
Social Sciences
Higher-order homophily on simplicial complexes
Sarker Arnab arnabs@mit.edu
a 1 https://orcid.org/0000-0003-1680-9421

Northrup Natalie b
Jadbabaie Ali a b https://orcid.org/0000-0003-1122-3069

aInstitute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA 02139
bDepartment of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139
1To whom correspondence may be addressed. Email: arnabs@mit.edu.
Edited by Matthew Jackson, Stanford University, Stanford, CA; received September 19, 2023; accepted February 12, 2024

12 3 2024
19 3 2024
12 9 2024
121 12 e231593112119 9 2023
12 2 2024
Copyright © 2024 the Author(s). Published by PNAS.
2024
https://creativecommons.org/licenses/by-nc-nd/4.0/ This article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

Significance

Homophily, the nearly universal tendency for individuals to interact with those resembling themselves, has predominantly been studied in the context of interactions between pairs of individuals. This study broadens this notion to study homophily in “higher-order” interactions between three or more individuals. Our results indicate that natural extensions of homophily to larger groups can be confounded by the pre-existing tendency for homophily in pairs. Hence, we develop measures which control for this bias. In certain instances, higher-order interactions may display anti-homophily when pairwise interactions show homophily, demonstrating that the nature of higher-order homophily is fundamentally different from the pairwise notion. Our methods provide a framework for extracting information about higher-order interactions which cannot be explained by traditional network models.

Higher-order network models are becoming increasingly relevant for their ability to explicitly capture interactions between three or more entities in a complex system at once. In this paper, we study homophily, the tendency for alike individuals to form connections, as it pertains to higher-order interactions. We find that straightforward extensions of classical homophily measures to interactions of size 3 and larger are often inflated by homophily present in pairwise interactions. This inflation can even hide the presence of anti-homophily in higher-order interactions. Hence, we develop a structural measure of homophily, simplicial homophily, which decouples homophily in pairwise interactions from that of higher-order interactions. The definition applies when the network can be modeled as a simplicial complex, a mathematical abstraction which makes a closure assumption that for any higher-order relationship in the network, all corresponding subsets of that relationship occur in the data. Whereas previous work has used this closure assumption to develop a rich theory in algebraic topology, here we use the assumption to make empirical comparisons between interactions of different sizes. The simplicial homophily measure is validated theoretically using an extension of a stochastic block model for simplicial complexes and empirically in large-scale experiments across 16 datasets. We further find that simplicial homophily can be used to identify when node features are valuable for higher-order link prediction. Ultimately, this highlights a subtlety in studying node features in higher-order networks, as measures defined on groups of size k can inherit features described by interactions of size ℓ<k.

homophily
networks
higher-order
simplicial complexes
DOD | Office of the Secretary of Defense (OSD) 100005713 Vannevar Bush Faculty Fellowship Arnab SarkerAli Jadbabaie
==== Body
pmcNetwork models provide powerful insights into the study of complex systems by representing elements of the system as nodes and describing dyadic interactions between nodes as a set of pairwise relationships (1–5). Recently, higher-order network models have gained relevance for their ability to explicitly model interactions that occur between three or more nodes in a network (6–9). In many domains, higher-order interactions between three or more nodes are common and fundamentally distinct from pairwise interactions (7, 10–12). For example, in social settings group interactions are well documented to facilitate phenomena such as conformity (13–15), social loafing (16, 17), and polarization of group decisions (18–20). Higher-order network models hence provide value in the study of complex systems as they are more expressive in the types of interactions that can occur between nodes and they allow for a broader set of structural measures which describe the underlying organizational principles of the data (6–8).

In this work, we augment previous models of higher-order networks by including node features, which refer to attributes describing individual elements of the complex system. The relationship between node features and network structure is important in its own right as it enables the description of homophily, a core organizing principle in many networks which describes the tendency for individuals to disproportionately form relationships with those similar to themselves (21). Consequently, understanding homophily in complex networks is valuable for prediction tasks on networks (22) and provides useful descriptions of polarization in social networks (23).

The study of homophily in traditional network models leads to two open questions with respect to its presence in higher-order networks. The first is whether there exist structural measures on higher-order networks which provide new information about homophily that cannot be captured by traditional models of pairwise interactions. Although measures of homophily have been proposed on hypergraphs and provide insights on the distribution of node features across groups of the same size in a network (24), we provide empirical evidence that these measures are highly correlated with homophily measures defined on standard graph-based network models, and theoretically show that such measures can be confounded by homophily present in pairwise relationships. The second open question regarding homophily in higher-order networks is, if there are indeed metrics which capture new information about homophily, whether this new information is of any consequence. In this work, we show that both questions are answered in the affirmative when the higher-order network data can be appropriately modeled with a simplicial complex.

A simplicial complex is a specific data structure used to represent higher-order information which has a specific closure property: If the simplicial complex includes a relationship between any set of nodes in the network, then all subsets of nodes in that relationship are also included in the simplicial complex (Fig. 1). As a concrete example, a network where individuals are connected if they have coauthored with one another could be modeled as a simplicial complex. If three individuals write a paper with one another, then the three are clearly connected by a triangle, and edges would also be formed to link each pair of authors as each pair would have coauthored with one another. Simplicial complexes represent one way to model higher-order interactions in complex systems, and other data structures are also able to handle this task including hypergraphs, set systems, and bipartite affiliation graphs (7). In particular, hypergraphs have also seen recent interest in analyzing higher-order network structure, as they are a more general class of models which explicitly encode higher-order interactions as hyperedges but do not require the closure property of simplicial complexes (9).

Fig. 1. Example of a simplicial complex to model coauthorship. (A) A sample dataset of relational data with higher-order information, i.e., there are several papers with more than two authors. Rather than represent these papers solely with a set of dyadic edges, we will additionally include a higher-order interaction in our representation of the data indicating there is a group relationship among those authors. (B) An example of metadata we may have for each node, in this case, each node is assigned a color. This could, for example, be an indicator of the author’s gender or affiliated institution. (C) A visual depiction of the network which denotes both the relationships between nodes (that is, a subset of authors are connected if they have coauthored with one another) and the metadata associated with each node. Notably, here triads are only “filled in” as higher-order interactions if three authors have explicitly coauthored a paper with one another, which is distinct from studying triadic motifs in the form of three dyadic edges as has been considered in previous work (c.f. ref. 25). For expository and visualization purposes, we have restricted this example to have at most three authors in each paper; our models and data also account for situations in which there are higher-order relationships between four or more elements of the complex network.

The simple closure property of simplicial complexes has been used at length by mathematicians to develop a rich theory in algebraic topology (26, 27). While these topics have been the purview of pure mathematics in the distant past, simplicial complexes have been increasingly used in applied domains, from sensor networks to robotics teams, and more importantly in data analysis (8, 11, 25, 28). Here, we use this closure assumption as an empirical tool, as it allows us to compare the structure of pairwise relationships to that of higher-order relationships between three or more agents. Specifically, the closure property ensures any simplicial complex has an underlying graph (also referred to as a 1-skeleton), and we are able to use this underlying graph to create statistical baselines that can be used to understand the structure of higher-order interactions. For example, the underlying graph of the network described in Fig. 1C can be seen in Fig. 3B. Moreover, the notion of a skeleton of simplicial complex can be generalized such that we may decouple the dynamics of size k group interactions from those of size ℓ<k.

Contributions.

In this paper, we investigate homophily in networks which can be modeled as simplicial complexes. This work relates to an initial empirical exploration of homophily on simplicial complexes in ref. 29 and offers several contributions beyond this prior work by providing more substantial empirical analyses and by providing a formal justification for the use of simplicial homophily through theoretical analyses.

We expand upon the measure of homophily introduced in ref. 29 which we now refer to as simplicial homophily*, and provide evidence that this homophily measure captures information that is not characterized by traditional network models. This measure of homophily is observational in nature, as it characterizes observed data on group interactions where nodes share features as opposed to explicitly describing the causal mechanisms which underlie homophily.

We provide an empirical analysis of simplicial homophily for higher-order interactions ranging from size 3 to size 8 across 16 large-scale datasets. This extends our previous work which restricted to the analysis of higher-order interactions of size 3. These results indicate that, regardless of the interaction size being considered, straightforward extensions of traditional homophily scores are highly correlated with dyadic homophily whereas simplicial homophily scores are uncorrelated with dyadic homophily. We find that this bias from dyadic homophily can even obfuscate when anti-homophily occurs in higher-order interactions.

Theoretically, we show that simplicial homophily isolates the effect of homophily in higher-order interactions. We do so by considering the simplicial stochastic block model (SSBM), a generative model for simplicial complexes which can encode community structure. This model extends the traditional stochastic block model (30) by incorporating elements of the Δ-ensemble introduced by Kahle et al. (31). We believe the SSBM is interesting in its own right as it may offer insights in the detection of community structure in complex systems more broadly (c.f. ref. 32). The stochastic model was originally introduced in ref. 29, but no formal theoretical analysis of the model was provided. Here, we prove that simplicial homophily can identify when group interactions in the SSBM are influenced by community labels of nodes. In contrast, previous measures of higher-order homophily can be biased to yield both Type I and Type II errors regarding the presence of homophily in higher-order interactions.

We then show the empirical importance of simplicial homophily by using this family of measures to assess when metadata can augment higher-order link prediction. That is, we show that simplicial homophily can be used to determine when node features are useful in predicting the formation of group interactions. Namely, we extend previous results on higher-order link prediction using node metadata by predicting the formation of higher-order relationships of size four and five. In contrast, prior work has either focused primarily on predicting the formation of triadic interactions (25, 29), or not focused on the implications of homophily for higher-order link prediction (33, 34). Our results suggest that structural measures on past data are valuable for predicting future higher-order interactions.

1. Simplicial Complexes and Node Features

We have gathered 16 datasets from diverse domains, each of which records higher-order interactions between individuals and contains features about each node in the dataset. Formally, each dataset consists of a set of nodes V and a set of simplices X, where each simplex x∈X is a subset of nodes in V and indicates the presence of a (potentially higher-order) relationship between the nodes in x. [The closure property of the simplicial complex then ensures that for any subset σ of x, σ∈X as well.] We refer to all simplices with size 2 as the edges of X, all simplices of size 3 as triangles or triads of X, and simplices of size 4 as tetrahedra of X. For simplices of larger sizes, we will be explicit about the number of nodes in the simplex, and we process each dataset’s higher-order interactions up to interactions with at most eight nodes.

Each dataset also contains metadata about each individual in the dataset, which here represents some kind of category or label for the individual. That is, there is some mapping from each vertex in V to a set C, where C is a set of m different categories.

For 10 of the 16 datasets, the data are also timestamped, such that each simplex x∈X is associated with some time tx at which the simplex was formed. This allows us to study the temporal dynamics of each dataset and study higher-order link prediction on these datasets. For concreteness, we describe the nodes, simplices, node features, and temporal structure of each dataset below.

Coauthorship data [coauth-dblp (35)]: Nodes are authors and a simplex forms if authors have coauthored a paper with one another. Node features for each node correspond to the gender of each author as described by Agarwal et al. (35), and timestamps correspond to the year of publication for each work.

Contact data [cont-village (36), cont-hospital, cont-workplace-13, cont-workplace-15, cont-primary-school, cont-high-school (37)]: Nodes are individual people and simplices form when individuals are physically near one another at the same point in time according to Bluetooth contact tracking. Node features for each node correspond to a group associated with the node (e.g., for cont-village this is a household, for cont-workplace-13 it is the department in the workplace, and for cont-primary-school it is the student’s homeroom). For some datasets, timestamped data are available which describes the time at which each simplex forms.

Email data [email-Enron (7)]: Nodes are email addresses and simplices form based on whether individuals have been in the same email communication through direct emails or CCs. Node features correspond to the gender associated with the user of the email address.

Cosponsorship data [bills-house, bills-senate (38, 39)]: Nodes are members in the United States Congress and simplices form if members have cosponsored a bill with one another. Node features correspond to the party affiliation of each member, and timestamps correspond to the date on which each bill was cosponsored.

Drug use data in hospital admissions [hosp-DAWN (7)]: Nodes are drugs and simplices form if a group of drugs are taken by the same patient admitted to a hospital. Node features correspond to the medical categorization (DRUGID) of each drug, and timestamps correspond to the date of the hospital admission where drugs co-occur.

Social network datasets [soc-youtube, soc-flickr, soc-livejournal, soc-orkut (40)]: Nodes are users of a social network. Each user of the social network can be a part of multiple user communities. Edges in the network form based on pairwise friendships, and higher-order simplices form if a set of three or more users are all friends and share at least one user community. Node features correspond to the user community of a node that is most frequently associated with a user’s friends.

Retail data [clicks-trivago (7)]: Nodes are hotels and a simplex forms if a set of hotels are visited in the same Trivago user session. Node features correspond to the country where each hotel is located.

Some summary statistics of each dataset are provided in Table 1 and information on higher-order interactions of size 6 or more is provided in SI Appendix.

Table 1. Summary statistics for the 16 datasets

Dataset	Nodes	Classes	Edges	Triangles	Tetrahedra	Groups of size 5	Timesteps	
cont-village (36)	46	5	327	582	572	386	—	
cont-hospital (37)	81	5	1,380	6,078	9,985	7,802	12,605	
cont-workplace-13 (37)	100	5	3,545	14,593	16,929	11,600	20,129	
email-Enron (7)	148	2	1,298	2,076	2,285	1,639	10,788	
cont-workplace-15 (37)	232	12	13,844	59,532	74,909	54,077	21,536	
cont-primary-school (37)	242	11	14,990	102,270	188,994	161,182	3,124	
bills-senate (38, 39)	294	2	17,691	103,446	127,887	85,896	4,975	
cont-high-school (37)	332	9	26,788	105,907	182,849	177,247	8,938	
bills-house (38, 39)	1,494	2	101,066	226,725	230,127	151,852	4,871	
hosp-DAWN (7)	2,558	364	87,150	340,364	420,503	257,976	32	
soc-youtube (40)	13,899	20	59,735	20,244	12,107	5,322	—	
soc-flickr (40)	100,690	20	5,268,929	2,285,874	4,831,845	4,796,733	—	
coauth-dblp (35)	105,256	2	267,332	236,507	140,513	62,719	55	
clicks-trivago (7)	172,738	160	662,337	677,434	512,995	287,421	—	
soc-orkut (40)	851,224	20	27,593,624	6,539,929	3,673,224	1,859,776	—	
soc-livejournal (40)	1,858,693	20	13,867,341	4,496,227	3,822,864	2,823,024	—	
Additional summary statistics regarding higher-order interactions of size 6 and higher can be found in SI Appendix. Ten datasets additionally include timestamps and are used for higher-order link prediction experiments.

2. Defining Homophily on Simplicial Complexes

When defined on traditional graph-based representations of networks, homophily is well known to occur in a wide variety of contexts such as marriage, friendship, information transfer, physical contact, and online social networks (21, 41, 42). In such networks, ties are correlated with node features such as age, occupation, religion, and/or each individual’s local network structure (21, 43).

Although this empirical ubiquity of homophily makes it valuable in understanding network structure, most previous studies have restricted to analysis of pairwise relationships between individuals. Here, we maintain information on each simplex in order to understand whether group interactions are more likely than random to show correlation in node features. That is, instead of breaking each simplex into a set of (induced) pairwise interactions, we analyze each higher-order interaction as the unit of measurement.

Having a higher-order interaction as the unit of measurement as opposed to the dyad creates several complexities in defining homophily. The first is that there are combinatorially many ways that node categories can be assigned in a group of size k. That is, for a pairwise interaction in a traditional network model, homophily is easily defined because the nodes are either similar to one another or not. In contrast, groups of size 3 or more in a higher-order network model may have several individuals each with their own associated features. As discussed in ref. 24, this complexity leads to interesting combinatorial characterizations of higher-order homophily and creates an impossibility result when each node in the network corresponds to one of two classes. Namely, in this setting, a hyperedge of size k can have t members of one group, and k−t members of the other for any 0≤t≤k. For a fixed group size k, the authors define a homophily score for each t≤k and prove impossibility results showing their homophily scores cannot be strictly increasing in t and both classes cannot simultaneously show homophily for all t≥k/2.

An additional complexity for defining homophily in group interactions is that measures of group homophily may be correlated with scores solely defined on pairwise interactions. This issue is the focus of this section. That is, group dynamics may be influenced by pairwise relationships, and hence, it is important to control for the effect of pairwise relationships when analyzing homophily in groups. Otherwise, it would be sufficient to look at measures of homophily on graphs to study homophily in higher-order interactions.

Here, we first discuss why decoupling homophily from pairwise interactions is a difficult task and then provide a measure of homophily, simplicial homophily, which appropriately decouples homophily from pairwise interactions when defining homophily on higher-order interactions. We find theoretical and empirical evidence that simplicial homophily appropriately decouples the effect of pairwise interactions. Moreover, the measure isolates the homophily inherent in size k interactions from lower-order interactions of size ℓ<k. This is not to say that simplicial homophily is a superior structural measure of homophily to previous work, but rather that it provides different insights by isolating homophily inherent in group dynamics.

2.1. The Importance of Decoupling Lower-Order Interactions.

We first study how pairwise interactions may influence homophily in higher-order interactions. In this section, we provide a broad definition of homophily measures and consider a variant of higher-order homophily discussed by Veldt et al. (24) which we refer to as “hypergraph homophily.” We refer to the measure as hypergraph homophily because its definition does not require the structural assumption of a simplicial complex and hence can be applied to any hypergraph (24). In a later section, we will discuss our measure of simplicial homophily which decouples the effect of lower-order interactions.

Homophily measures on higher-order network models have two components: an affinity score which measures how often a specific pattern of node features occurs in the dataset and a baseline measure which quantifies how frequently we would expect that pattern to occur according to some randomization procedure wherein node features are independent of group formation (44). For simplicity, we will consider the pattern where all nodes in a group relationship share the same features. We restrict to this case in the main text because our goal here is to understand the relationship between different sizes of group relationships, rather than the combinatorial complexity of defining homophily for higher-order relationships. The extension to other patterns of metadata which allow for heterogeneous group compositions is discussed in SI Appendix, where we find similar results to those presented here.

Formally, hypergraph homophily is defined as follows: For a simplicial complex (or arbitrary hypergraph) X and a fixed group size k, let ak(X) be the proportion of group relationships of size k where all nodes have the same features. [Equivalently, in our data, this means that all nodes in the group belong to the same category.]

Hypergraph homophily then uses a random baseline based on randomization of node labels to determine whether the affinity is higher or lower than expected. Let nc represent the number of nodes in category c∈C, where C is the set of possible categories that can be associated with a node. Further, let n=∑c∈Cnc represent the total number of nodes in the network. The baseline used in hypergraph homophily is defined (24):[1] bkH(X)=∑c∈Cnck/nk.

Here, the superscript H in bkH(X) denotes that it is specifically the random baseline for hypergraph homophily. This is in contrast to the baseline for simplicial homophily, which we consider later in the work. Conceptually, Eq. 1 measures the probability that all nodes in a group relationship would share the same features if the features for each node were assigned randomly. The hypergraph homophily score skH(X) can be defined[2] skH(X)=ak(X)/bkH(X).

We see that this score is above 1 if the observed number of group interactions with all nodes of the same type is greater than the random baseline, and below 1 otherwise. Hence, this score provides one possible statistical baseline to assess whether groups in a dataset are more likely than random to be between nodes with the same features. It is worth noting that when k=2, i.e., the unit of measure is dyads in the network, then this definition recovers the standard definition of homophily in traditional network models (2).

While this definition is valid in the sense that it provides a baseline in which node features are independent of network structure, our key finding is that this definition is highly correlated with pairwise measures of homophily, i.e., it does not provide much value beyond what can be ascertained from pairwise measures of homophily. In Fig. 2, we compare hypergraph homophily scores for higher-order interactions in the 16 datasets to the dyadic homophily scores where k=2, i.e., we compare the information from hypergraph homophily to the classical measure of homophily. We find that the coefficient of determination (R2) between the two measures is at least 0.48 (P<0.001) for all considered sizes of higher-order interactions, and that the high correlation between hypergraph homophily scores and dyadic scores is robust to the removal of outlier datasets. This suggests that dyadic measures of homophily can explain most of the variance in higher-order homophily under this particular definition.

Fig. 2. Comparison of hypergraph homophily to dyadic homophily scores. For each plot, each point represents a dataset and is plotted according to the standard edge homophily score and the hypergraph homophily score for group sizes ranging from 3 to 6. Regardless of the group size considered, we find a strong correlation between hypergraph homophily score and dyadic homophily score (R2=0.79,0.66,0.57, and 0.49 for group sizes 3,4,5, and 6, respectively, with all associated P-values below 0.01). This suggests that a large portion of the variance in hypergraph homophily scores for higher-order interactions can be explained by pairwise relationships and motivates the need for a homophily definition which can isolate homophily in group dynamics.

2.1.1. Theoretical foundations of bias from pairwise interactions.

Moreover, we are able to provide a theoretical justification as to how homophily in pairwise relationships can influence hypergraph homophily scores in triads and higher-order group interactions. We consider an extension of the simplicial stochastic block model (SSBM) introduced in previous work (29), which is also described formally in SI Appendix.

The SSBM is a generalization of the Δ−ensemble model of Kahle et al. (31) which allows for community structure and begins with m disjoint sets of vertices belonging to different communities (i.e., each node has one of m possible features associated with it). The relationships between nodes in the model are determined sequentially: first edges form, then triangles, then tetrahedra, followed by group relationships of size 5, 6, 7, and so on. First, for each pair of nodes, edges form with probability p1 between nodes in the same community and with probability q1 between nodes in different communities.† Then, for every set of three nodes A,B, and C for which all edges are present, a triangle forms with probability p2 if A,B, and C are in the same community, and with probability q2 otherwise. Similarly, after all triangles are determined, then for every set of four nodes A,B,C, and D for which all possible triangles are present, a tetrahedra is placed with probability p3 if A,B,C, and D are in the same community, and with probability q3 otherwise. This pattern continues for group relationships of larger sizes, where the likelihood a group relationship of size k occurs is determined by the parameter pk−1 if all nodes are in the same community (and have all lower-order connections of size ℓ<k) or qk−1 if the nodes are not all in the same community. This model extends that of ref. 29 to higher-order interactions beyond size 3, and may be of broad interest in studying questions regarding community detection on higher-order networks.

Using the SSBM, we are able to show the ways in which lower-order connections can bias hypergraph homophily scores and lead to errors in analysis.

Proposition 1 (Informal). In the Simplicial stochastic block model, let k≥3 and recall pk−1 and qk−1 govern the formation of group interactions of size k within community and between communities, respectively. Then, the following claims hold

(Possibility of Type I Error) If pk−1=qk−1, there is always a configuration of model parameters for lower-order interactions such that E[skH(X)]>1.

(Possibility of Type II Error) If pk−1>qk−1, there is always a configuration of model parameters for lower-order interactions such that E[skH(X)]=1.

The above claims are proven in SI Appendix, which provides a closed-form expression of the expected hypergraph homophily score and uses this expression to prove the proposition.

The first part of Proposition 1 indicates that, even when there is no explicit tendency for interactions of size k to depend on node labels, hypergraph homophily scores can be biased by lower-order interactions to suggest the presence of hypergraph homophily. Conversely, the second part indicates that lower-order interactions can bias the score in the other direction, i.e., the hypergraph homophily score can be 1 even when higher-order interactions of size k do explicitly depend on node labels. Hypergraph homophily scores are therefore susceptible to both forms of statistical error in the sense that these scores may claim the existence of higher-order homophily when it does not exist (Type I error) or state that there is no higher-order homophily when in fact there is a tendency for group interactions to disproportionately form between nodes of the same type (Type II error).

2.2. Simplicial Homophily.

In order to isolate homophily in higher-order interactions interactions, we consider the notion of simplicial homophily. To provide an intuition for simplicial homophily, we first consider the case of measuring homophily for triadic interactions and accounting for a potential influence from pairwise interactions. Namely, we wish to derive a measure which indicates whether higher-order relationships are more likely than not to occur between individuals with the same features, given that lower-order (e.g., pairwise) relationships exist between the individuals in the network.

To account for these underlying relationships, we appeal to the notion of a skeleton of the simplicial complex. Formally, for a simplicial complex X, the j-skeleton of the simplicial complex is the collection of all simplices x∈X which have at most j+1 elements (26). The j-skeleton, which we denote X(j), is itself a simplicial complex and is guaranteed to exist given the definition of a simplicial complex (26). In contrast, an arbitrary hypergraph need not have a well-defined skeleton for any j as hypergraphs do not impose structural assumptions on the data.

2.2.1. Intuition: simplicial homophily for groups of size 3.

To decouple the effect of pairwise relationships from triadic relationships, we use the 1-skeleton of the simplicial complex, often referred to as the underlying graph. The 1-skeleton contains all of the relevant information about pairwise relationships in the network model, and hence can be used to create a random baseline which determines whether triadic interactions are more likely to occur between individuals with the same features than the underlying graph would suggest. In defining simplicial homophily on triads, it is important to distinguish between two types of sub-networks between three nodes: 1) closed triangles which refer to three nodes who have three dyadic edges between them in the underlying graph, and 2) filled triangles which refer to three nodes who have a higher-order interaction. In particular, for a simplicial complex, every filled triangle is a closed triangle due to the closure property but not every closed triangle must be filled.

Hence, to establish the random baseline from the underlying graph, we use the fraction of closed triangles (that is, sets of three nodes connected by dyadic edges) where all nodes share the same features. A concrete example of this definition is provided in Fig. 3, which shows how hypergraph homophily and simplicial homophily can differ when defined on triangles.

Fig. 3. Small example comparing hypergraph and simplicial homophily. In this example, we find that all of the homophily associated with group interactions can be explained by the underlying graph, emphasizing the importance of simplicial homophily. (A) represents the simplicial complex X, taken from Fig. 1. (B) represents the 1-skeleton, or underlying graph, of this complex, which we denote X(1). (C) The triad affinity can be computed from (A) by seeing that there are two triads with all nodes of the same type, and three triads in total. (D) The hypergraph baseline computes the number of expected triangles with all nodes of the same type if the node features were assigned randomly, in this case b3H(X)=43/83+43/83=17. (E) In contrast, the simplicial baseline uses the 1-skeleton as depicted in (B), where we see that the underlying graph has six closed triangles (denoted by stars), 4 of which are between nodes with the same features (denoted by yellow stars). (F) The associated hypergraph homophily score is the ratio of triad affinity a3(X) and the hypergraph baseline b3H(X) and suggests the presence of homophily since the score exceeds 1. (G) However, the simplicial homophily score is the ratio of a3(X) and b3S(X) and suggests that all of the homophily from the hypergraph homophily score can actually be explained by underlying pairwise relationships.

2.2.2. Mathematical definition of simplicial homophily.

The definition of simplicial homophily is similar to that of hypergraph homophily in that it has the same two components: an affinity score and a baseline measure from a random procedure. The affinity score for simplicial homophily is exactly the same as for hypergraph homophily, such that for a fixed group size k and a simplicial complex X, the affinity score ak(X) is the proportion of group relationships of size k where all nodes share the same features.

Simplicial homophily assesses whether higher-order interactions of size k in X are likely to be among nodes of the same type relative to the possible interactions of size k that could have existed in X given all lower-order interactions. Specifically, consider X(k−2), the (k−2)-skeleton of the simplicial complex which contains all interactions of size at most k−1 in X. X(k−2) exactly captures the structure of lower-order interactions in X. We can denote X(k−2)¯ as the “completion” of the (k−2)-skeleton of X, such that X(k−2)¯ is the simplicial complex which contains the maximal set of higher-order interactions of size k that could have possibly been in X. The random baseline used in simplicial homophily for groups of size k is defined[3] bkS(X)=ak(X(k−2)¯).

This is exactly the likelihood that a randomly placed group interaction of size k into X(k−2) has nodes of the same type, and we may use this as a baseline to compare to the observed affinity score ak(X). As before, the superscript S clarifies that this baseline is used for simplicial homophily rather than hypergraph homophily. Hence, the simplicial homophily score can ultimately be defined[4] skS(X)=ak(X)/bkS(X).

Fig. 3 provides a concrete example of this measure, outlines the associated 1-skeleton and its completion, and shows how simplicial homophily can differ from hypergraph homophily by accounting for underlying pairwise interactions.

It is worth noting that the simplicial homophily measure in Eq. 4 and its associated baseline Eq. 3 may be seen as generalizations of the standard measures defined on traditional network models (2), as discussed in SI Appendix. That is, hypergraph homophily and simplicial homophily coincide when the unit of analysis is the dyad (k=2) and this also corresponds to a standard measure of homophily (2, 29). However, the two measures differ significantly when k>2, as we discuss in the following section.

2.3. Evidence of Decoupling.

Empirically, we find that simplicial homophily defined on higher-order interactions is uncorrelated with homophily scores defined on dyads (Fig. 4). Moreover, for all datasets which show homophily in pairwise interactions, the hypergraph homophily score on triads is higher than the simplicial homophily score on triads, providing empirical evidence that simplicial homophily appropriately controls for the presence of dyadic homophily (29).

Fig. 4. Comparing simplicial homophily scores across different group sizes. Each point in the figure is one of the 16 datasets and is plotted according to the homophily score for a particular group size. In all plots, the correlation coefficient is not statistically significant, even when outliers are removed.

There are several datasets for which the simplicial homophily score on triangles is noteworthy in its difference from the edge homophily score. For clicks-trivago, soc-flickr, email-Enron, and coauth-dblp, the simplicial homophily score suggests anti-homophily in the formation of triadic relationships. That is, in these datasets, triadic interactions are more likely to form between nodes with different features when compared to the underlying graph, and this anti-homophily in triads is obfuscated by the presence of homophily in edges. For example, in clicks-trivago, the triadic anti-homophily could be explained by consumer preferences and the complementarity of node features within the dataset. Namely, travelers who search for two hotels in one browsing session may do so to compare cost and amenities of similar hotels (i.e., they are comparing substitutes), whereas travelers browsing more than three hotels are more likely to be taking a longer trip or have more geographic flexibility such that they are searching for complements (29). In fact, we see that the simplicial homophily scores for tetrahedra and groups of size 5 for this dataset are also below 1, further supporting this explanation (Fig. 5).

Fig. 5. Homophily scores as a function of group size. Each point is either the simplicial homophily score (red) or the hypergraph homophily score (blue) for a particular group size k, and denoted with a “+” if the score is above 1 or a “−” if the score is below 1. In the retail dataset clicks-trivago, there is strong dyadic homophily which biases all hypergraph homophily scores to exceed 1, whereas the simplicial scores actually suggest anti-homophily. In cont-hospital, there is dyadic anti-homophily but triadic homophily, and hence the hypergraph homophily score ultimately underestimates the tendency for triadic interactions to be between nodes (here, medical professionals) of the same type (role in the hospital).

Furthermore, Fig. 5 indicates that the cont-hospital dataset is particularly interesting as it has dyadic anti-homophily but simplicial homophily for higher-order interactions of size 3 and 4. As a result, the simplicial homophily score on triads is higher than the hypergraph homophily score as the latter becomes deflated due to the anti-homophily in edges. This suggests an interesting dynamic with respect to interactions among hospital staff which would not be revealed by traditional networks: whereas dyadic interactions are often between different staff members (e.g., a nurse working with a doctor), higher-order interactions are relatively more likely to take place between individuals with the same role.

Theoretically, we are able to study how simplicial homophily behaves in the simplicial stochastic block model (SSBM) discussed in the previous section. We are able to show the following proposition relating simplicial homophily scores to the parameters in the SSBM, which is proved in SI Appendix.

Proposition 2. In the Simplicial Stochastic Block Model, E[skS(X)]>1, if and only if pk−1>qk−1.

Because pk−1 governs the probability a size k interaction occurs between nodes in the same community and qk−1 governs the probability a size k interaction occurs between nodes who are not all in the same community, we see that this score effectively isolates the homophily for size k interactions. That is, whereas hypergraph homophily scores are affected by the formation of lower-order relationships, simplicial homophily scores are not.

3. Higher-Order Link Prediction with Node Features

Higher-order link prediction was introduced by Benson et al. (7) as a “benchmark problem to assess models and algorithms that predict higher-order structure.” One is given a partial time series of data up to a time t, and then is asked to predict if a particular set of nodes will form a group relationship after time t. Here, we augment previous higher-order link prediction models by considering the effect of node features, i.e., we compare models which use node features to those which do not. Moreover, we predict higher-order interactions of size 4 and 5 as well as triadic interactions. Ultimately, we find that when the first half of the data shows extreme simplicial homophily or anti-homophily, then node features increase the performance of the prediction model on the second half of the data.

We learn two separate logistic regression models on the first 50% of simplices observed in the data, and test the logistic regression model on the remaining 50% of data. The first model serves as a baseline and uses the local features described in Benson et al. (7) (Materials and Methods). For predicting size k interactions, each data point in the regression model represents a subset of k nodes which have all associated k−1 size interactions but no group interaction of size k. The features of this regression include the frequency with which each tie occurs between each pair within the k nodes, the degree of each node (in the traditional graph sense and weighted by the number of simplices each node is in), the number of common neighbors between the nodes, and logarithmic rescalings of all of these factors. The second model uses the features of the first model and an additional binary indicator feature which is 1 if and only if all k nodes share the same metadata.

Fig. 6 displays the results of the two regression models evaluated across the 10 datasets above for predicting higher-order interactions of size 3, 4, and 5. For some datasets, there are no subsets of 4 or 5 nodes which have all lower-order interactions in the first half of the data and have a group interaction in the second half of the data, and hence we can not use every dataset for all prediction tasks. We evaluate performance of each model using the area under the precision–recall curve (AUC-PR) and report the score relative to a random baseline in order to be consistent with previous work (7, 29). Higher-order link prediction is in general a difficult task given the low base rate at which higher-order interactions occur (7), and hence any statistically significant improvement in link prediction is valuable for the prediction task.

Fig. 6. Higher-order link prediction performance with and without node features. Each data point represents the difference in performance between two regression models for predicting if a set of k nodes with all lower-order interactions in the first 50% of the data eventually has a size k interaction in the last 50% of the data. Performance is measured as the area under the precision–recall curve (AUC-PR) relative to a random baseline. We find that the simplicial homophily score can predict the increase in performance of using node labels (R2=0.172,P<0.05), whereas the hypergraph homophily score is uncorrelated with these performance improvements.

We find that the further the simplicial homophily score is from 1, the larger the increase in performance of models which use node labels. Specifically, the absolute value of the logarithm of the simplicial homophily score correlates with the prediction performance increase when using node labels (r=0.415, P<0.05) This effect holds even when removing outliers or when considering Spearman and Kendall correlation coefficients. In contrast, hypergraph homophily scores are uncorrelated with this increase in performance (r=0.05,P>0.8). Hence, we see that the simplicial homophily scores, which are only computed using the first 50% of the data, provide valuable information about whether node labels may be useful in prediction. While this predictive power of simplicial homophily need not hold in general—for example, a dataset may show simplicial homophily for the first 50% of data and then simplicial anti-homophily for the remaining 50%—our results suggest that simplicial homophily does carry information about the temporal dynamics of relationships in empirical data.

4. Discussion

Incorporating node features in the analysis of higher-order networks provides many opportunities for analyzing complex networks. Here, we show that when data can be modeled with a simplicial complex, the closure property required by simplicial complexes provides a principled way to compare homophily in pairwise and higher-order interactions.

We are able to use this closure property to define simplicial homophily, which empirically and theoretically decouples the effect of pairwise homophily from higher-order homophily. Empirically, we find that homophily in pairwise interactions often inflates hypergraph homophily scores, and sometimes this inflation is so extreme that it can obfuscate the presence of anti-homophily in higher-order interactions. Theoretically, we introduce a generalization of the SSBM from ref. 29 and provide a theoretical analysis of the stochastic model. Our results illustrate the ways in which hypergraph homophily can be biased by lower-order interactions. By showing that the SSBM allows for tractable analyses, we also open several possible directions for future research in exploring when communities can be identified (c.f. ref. 32).

For the task of prediction on higher-order networks, we show that simplicial homophily can be used to understand when node features are valuable in improving the performance of higher-order link prediction. Specifically, when existing data already shows extreme simplicial anti-homophily or homophily, then we would expect that using node labels to augment prediction should result in better prediction performance. Our findings suggest a “temporal stability” to homophily in higher-order networks, as trends of homophily in the first half of a dataset describe the predictive capability of node features in the second half of the dataset. This ultimately highlights how we can use node features in higher-order networks toward a data-driven end.

This approach to defining homophily on simplicial complexes has broader implications for the analysis of higher-order network models. Because the metric compares features of higher-order interactions to a baseline having to do with the underlying graph of the simplicial complex, we are effectively able to control for any well-known feature of graph-based networks such as triadic closure, edge homophily, or dyadic clustering. By controlling for these graph-based features, we can accurately capture novel information about the structure and dynamics of higher-order interactions.

5. Materials and Methods

5.1. Computing Homophily Scores.

To compute simplicial homophily and hypergraph homophily scores, we first create a simplicial complex X for each dataset described in Table 1. For each k ranging from 3 to 8, where k represents the size of the higher-order interaction, we then compute hypergraph homophily scores according to Eq. 2 and simplicial homophily scores according to Eq. 4. To compute dyadic (edge) homophily scores, we use the score defined in Easley and Kleinberg (2) which corresponds to both the hypergraph homophily score and simplicial homophily score for k=2. These scores are used for the plots in Figs. 2, 4, and 5.

5.2. Link Prediction Experiments.

For each dataset and applicable higher-order interaction size k, we build two logistic regression models—one which only uses network-based features and one which uses network-based features as well as metadata about nodes. We train these models using the first 50% of the timestamped data, which we divide into a sub-training set consisting of the first quartile of the data and validation set consisting of the second quartile of the data. We train a logistic regression model using the scikit-learn library (45): Each data point is a set of k nodes with all (k−1) sized interactions but no size k interactions in the sub-training set, the features for each data point (listed in Section 3) are computed using the sub-training set, and the label for the data point is 1 if these nodes have a size k interaction in the validation set and 0 otherwise. Once the model is trained, it is applied to the entire training set to predict whether size k interactions will occur in the test set. We measure prediction performance using the area under the precision–recall curve (AUC-PR) relative to a random baseline, and the difference in performance between models with and without node labels as features is presented in Fig. 6.

Supplementary Material

Appendix 01 (PDF)

This work was supported through funding from a Vannevar Bush Fellowship from the Office of the Secretary of Defense and from Army Research Office Multidisciplinary University Research Initiative W911-NF-19-1-0217.

Author contributions

A.S., N.N., and A.J. designed research; performed research; analyzed data; and wrote the paper.

Competing interests

The authors declare no competing interest.

Data, Materials, and Software Availability

Previously published data were used for this work (7, 29, 35, 36, 37, 38, 39, 40). Software and available data for replication are available at https://github.com/arnabsarker/Higher-Order-Homophily-Simplicial-Complexes (46).

Supporting Information

This article is a PNAS Direct Submission.

*In previous work, we denoted this measure as k-simplicial homophily, where k-simplicial homophily was defined on group interactions with size k+1 to be consistent with the algebraic topology literature. Here, we have renamed the measure as simplicial homophily to avoid any confusion on group size when comparing this measure to previous work.

†Here, we use the notation pk and qk to describe the formation of higher-order interactions of size k+1 to be consistent with the terminology of the Δ-ensemble model.
==== Refs
1 A. L. Barabási, R. Albert, Emergence of scaling in random networks. Science 286 , 509–512 (1999).10521342
2 D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Connected World (Cambridge University Press, 2010).
3 M. S. Granovetter, The strength of weak ties. Am. J. Sociol. 78 , 1360–1380 (1973).
4 D. J. Watts, S. H. Strogatz, Collective dynamics of “small-world’’ networks. Nature 393 , 440–442 (1998).9623998
5 M. E. Newman, The structure and function of complex networks. SIAM Rev. 45 , 167–256 (2003).
6 F. Battiston , Networks beyond pairwise interactions: Structure and dynamics. Phys. Rep. 874 , 1–92 (2020).
7 A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, J. Kleinberg, Simplicial closure and higher-order link prediction. Proc. Natl. Acad. Sci. U.S.A. 115 , E11221–E11230 (2018).30413619
8 M. T. Schaub, A. R. Benson, P. Horn, G. Lippner, A. Jadbabaie, Random walks on simplicial complexes and the normalized Hodge 1-Laplacian. SIAM Rev. 62 , 353–391 (2020).
9 L. Torres, A. S. Blevins, D. Bassett, T. Eliassi-Rad, The why, how, and when of representations for complex systems. SIAM Rev. 63 , 435–485 (2021).
10 R. H. Atkin, From cohomology in physics to q-connectivity in social science. Int. J. Man-Mach. Stud. 4 , 139–167 (1972).
11 C. Giusti, R. Ghrist, D. S. Bassett, Two’s company, three (or more) is a simplex: Algebraic-topological tools for understanding higher-order structure in neural data. J. Comput. Neurosci. 41 , 1–14 (2016).27287487
12 G. Simmel, The number of members as determining the sociological form of the group. I. Am. J. Sociol. 8 , 1–46 (1902).
13 S. E. Asch, Opinions and social pressure. Sci. Am. 193 , 31–35 (1955).
14 R. B. Cialdini, M. R. Trost, Social Influence: Social Norms, Conformity and Compliance (McGraw-Hill, 1998).
15 S. Chowdhary, A. Kumar, G. Cencetti, I. Iacopini, F. Battiston, Simplicial contagion in temporal higher-order networks. J. Phys.: Compl. 2 , 035019 (2021).
16 B. Latané, K. Williams, S. Harkins, Many hands make light the work: The causes and consequences of social loafing. J. Person. Soc. Psychol. 37 , 822 (1979).
17 D. R. Comer, A model of social loafing in real work groups. Hum. Relat. 48 , 647–667 (1995).
18 R. Brown, Social Psychology (Simon and Schuster, 1986).
19 C. R. Sunstein, Group polarization and 12 angry men. Negotiation J. 23 , 443–447 (2007).
20 T. Kugler, E. E. Kausel, M. G. Kocher, Are groups more rational than individuals? A review of interactive decision making in groups. Wiley Interdisc. Rev. Cognit. Sci. 3, 471–482 (2012).
21 M. McPherson, L. Smith-Lovin, J. M. Cook, Birds of a feather: Homophily in social networks. Annu. Rev. Sociol. 27 , 415–444 (2001).
22 L. Lü, T. Zhou, Link prediction in complex networks: A survey. Phys. A: Stat. Mecha. Appl. 390 , 1150–1170 (2011).
23 M. Conover et al., “Political polarization on Twitter” in Proceedings of the International AAAI Conference on Web and Social Media (2011), vol. 5, pp. 89–96.
24 N. Veldt, A. R. Benson, J. Kleinberg, Combinatorial characterizations and impossibilities for higher-order homophily. Sci. Adv. 9 , eabq3200 (2023).36608141
25 A. R. Benson, D. F. Gleich, J. Leskovec, Higher-order organization of complex networks. Science 353 , 163–166 (2016).27387949
26 A. Hatcher, Algebraic Topology (Cambridge University Press, 2002).
27 W. V. D. Hodge, W. V. D. Hodge, The Theory and Applications of Harmonic Integrals (CUP Archive, 1989).
28 A. Tahbaz-Salehi, A. Jadbabaie, Distributed coverage verification in sensor networks without location information. IEEE Trans. Autom. Control 55 , 1837–1849 (2010).
29 A. Sarker, N. Northrup, A. Jadbabaie, “Generalizing homophily to simplicial complexes” in Complex Networks and Their Applications XI: Proceedings of The Eleventh International Conference on Complex Networks and their Applications: COMPLEX NETWORKS 2022–Volume 2 (Springer, 2023), pp. 311–323.
30 M. E. Newman, Assortative mixing in networks. Phys. Rev. Lett. 89 , 208701 (2002).12443515
31 M. Kahle , Topology of random simplicial complexes: A survey. AMS Contemp. Math 620 , 201–222 (2014).
32 F. Krzakala , Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. U.S.A. 110 , 20935–20940 (2013).24277835
33 N. Yadati et al., “Nhp: Neural hypergraph link prediction” in Proceedings of the 29th ACM International Conference on Information & Knowledge Management (Association for Computing Machinery, New York, NY, 2020), pp. 1705–1714.
34 H. Se Yoon, K. Shin Song, Y. Yi, “How much and when do we need higher-order information hypergraphs? A case study on hyperedge prediction” in Proceedings of the Web Conference 2020 (Association for Computing Machinery, New York, NY, 2020), pp. 2627–2633.
35 S. Agarwal, N. Mittal, R. Katyal, A. Sureka, D. Correa, Women in computer science research: What is the bibliography data telling us? Acm Sigcas Comput. Soc. 46 , 7–19 (2016).
36 L. Ozella , Using wearable proximity sensors to characterize social contact patterns in a village of rural Malawi. EPJ Data Sci. 10 , 46 (2021).
37 M. Génois, A. Barrat, Can co-location be used as a proxy for face-to-face contacts? EPJ Data Sci. 7 , 11 (2018).
38 J. H. Fowler, Connecting the congress: A study of cosponsorship networks. Polit. Anal. 14 , 456–487 (2006).
39 J. H. Fowler, Legislative cosponsorship networks in the US house and senate. Soc. Netw. 28 , 454–465 (2006).
40 A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, B. Bhattacharjee, “Measurement and analysis of online social networks” in Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (2007), pp. 29–42.
41 G. Kossinets, D. J. Watts, Empirical analysis of an evolving social network. Science 311 , 88–90 (2006).16400149
42 J. Stehlé , High-resolution measurements of face-to-face contact patterns in a primary school. PloS One 6 , e23176 (2011).21858018
43 Y. Dong, R. A. Johnson, J. Xu, N. V. Chawla, “Structural diversity and homophily: A study across more than one hundred big networks” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2017), pp. 807–816.
44 J. Park, A. L. Barabási, Distribution of node characteristics in complex networks. Proc. Natl. Acad. Sci. U.S.A. 104 , 17916–17920 (2007).17989231
45 F. Pedregosa , Scikit-learn: Machine learning in Python. J. Mach. Learn. Res. 12 , 2825–2830 (2011).
46 A. Sarker, Higher-Order-Homophily-Simplicial-Complexes. GitHub. https://github.com/arnabsarker/Higher-Order-Homophily-Simplicial-Complexes. Deposited 22 February 2024.
