CS Paper Radar

Beyond the Clique: Comparing Clique and Dowker Complexes for Co-occurrence Data in Learning Analytics

Koichi Yasutake, Wakana Tsuji, Hitoshi Inoue

cs.SI ·submitted 2026-10-01 08:38 UTC · v3
code/data

Abstract

Learning analytics increasingly represents the relations in co-occurrence data (codes in a window of discourse, participants in a thread, tags on a post) as simplicial complexes and analyses them with persistent homology. The standard approach uses the clique complex. Because its simplices are determined by the pairwise network alone, it cannot distinguish "three elements co-occurred together" from "each of the three pairs co-occurred separately". The Dowker complex, in contrast, takes as simplices the sets of entities actually observed to co-occur. We compare the two. First, we show that, on the same 1-skeleton, the Dowker complex is a subcomplex of the clique complex, the map on first homology induced by the inclusion is surjective, and its kernel is generated by phantom triangles that never co-occurred; that is, the clique construction can only erase holes. We also give a criterion for agreement that can be checked on triples of groups. We then test this on real data. On four Stack Exchange data sets, 46-91% of clique triangles are phantom and 522-1,970 holes are erased. On the example data of the learning-analytics R packages tna/Nestimate, the first Betti number $β_1$ of the clique complex is 0 at every threshold, whereas the Dowker complex detects holes. Against a degree-preserving null model, the Dowker complex departs strongly in five of the six data sets. This difference is invisible at the fixed thresholds used in practice. We conclude that the construction should follow the data type and that, for observed groups, the Dowker complex is the appropriate choice. Code is available at https://github.com/igu-lab/beyond-the-clique.

Comment
v3: corrects an error in the ordering of events for the human_long data; results and statements on human_long revised; code archived at doi:10.5281/zenodo.23147037

Closest papers

Nearest neighbours by meaning across the whole index.

When Connected Does Not Mean Similar: Charting the Homophily Boundary of SNAP-KG for Streaming Entity Integration

cs.LG ·2026-09-11 ·Jui-Chien Lin, Oshani Seneviratne
publishedpositionhot direction similarity 0.59
Abstract · Accepted to the ISWC 2026 Companion Volume

SNAP-KG is a framework for assigning newly arriving entities to semantic communities in a growing knowledge graph (KG) using only their raw features, with no graph access and no retraining at inference time. It was evaluated on five multi-view benchmarks and a 2.4M-node OGB-WikiKG2 KG. In each of these datasets, at least one graph view is homophilous, meaning that connected nodes usually belong to the same class, and SNAP-KG performs well on all of them. This paper asks what happens outside that setting. We extend the evaluation to three heterophilous graphs (Texas, Wisconsin, Chameleon) and measure the edge homophily of every view. When no homophilous view is available, clustering quality drops sharply for both SNAP-KG and the transductive baselines used in its original evaluation. What decides this is the homophily of the relation, not the number of relations. Multi-view fusion still helps, but only when at least one homophilous relation provides a reliable foundation. The homophily assumption is therefore shared by the whole method family, not specific to SNAP-KG. We argue that heterophilous multi-view clustering is a separate research problem, outside the scope of this work. As future work, we outline how a heterophily-aware teacher could be distilled into SNAP-KG's projector to serve both homophilous and heterophilous KGs.

0.30

PathFinder: Joint Decompositions of Linked Multimodal Datasets

cs.LG eess.IVq-bio.QMstat.ML ·2026-08-15 ·Ying-Qiu Zheng, Alex Fung, Stephen M Smith, Rogier B Mars, Saad Jbabdi
similarity 0.57
Abstract

Low-rank matrix decompositions can uncover patterns and structure in data and have a number of different applications across many disciplines. Extensions to "joint" low-rank decompositions have been proposed to link datasets from different modalities. While these methods enable the discovery of common patterns across modalities, they require that all the multimodal data share one or more dimensions. We propose a new analysis method, PathFinder, that enables co-analysis of datasets that do not necessarily all share a dimension. The key insight is that as long as pairs or subgroups of matrices do share some dimension, and that there are one or more paths that link across the data matrices, a global joint decomposition can be sought out. This enables the joint estimation of common patterns across different modalities, species, or scales, where a one-to-one mapping across all data along some dimension is not necessarily available. We show that PathFinder is a general umbrella under which many matrix decomposition methods fall as special cases. It can be used to discover common patterns across disparate datasets and to make predictions for missing data or modalities.

0.04

Dessins d'Enfants as a Topological Lens on Temporal Hypergraphs

cs.SI math.ATmath.CO ·2026-11-18 ·Mehmet Emin Aktas, Esra Akbas
theory similarity 0.54
Abstract

Hypergraphs are the natural language for group interactions, and topological data analysis has given us several ways to look at them: simplicial and cell complexes, persistent homology, and sheaves. All of these treat a hyperedge as an unordered set. In this paper, we introduce a different and, to our knowledge, new viewpoint that comes from Grothendieck's theory of dessins d'enfants and, unlike these approaches, takes into account the order in which vertices appear in each hyperedge and hyperedges appear around each vertex. A dessin is a bipartite graph drawn on a closed orientable surface. Through Walsh's classical correspondence between hypermaps and bipartite maps, every hypergraph equipped with a cyclic order of incidences at each vertex and inside each hyperedge is a dessin, and therefore determines a surface with faces and a genus. We develop this idea for temporal hypergraphs and build the surface by replaying history: incidences are added in the order in which they occurred, and each new incidence is inserted into the cyclic orders built so far, next to the earlier incidence to which it is related. We prove that every insertion either grows the hypergraph without creating a cycle, closes a cycle locally by splitting a face, or closes it globally by adding a handle; the number of independent cycles equals the number of local plus handle events, and the genus equals the number of handle events. These counts give interpretable, size-controlled measures of how a temporal hypergraph's cycles organize on a surface as it grows. We apply our method to five Stack Exchange communities and show that it separates communities that standard statistics cannot tell apart and quantifies how much the real order of interactions matters. We further discuss what the surface viewpoint adds to existing higher-order network analysis and how it opens a path toward dessin-based learning on hypergraphs.

0.34

Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts

cs.SI cs.DS ·2026-09-04 ·Sabyasachi Basu, C. Seshadhri
theory similarity 0.53
Abstract

Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meaning the average degree is small (in the tens, while the number of vertices is more than millions). When graph data is collected from a source, a major task is to perform data exploration. Thus, any region of ``density" is of interest, since it indicates special structure. An important goal is to cover a significant portion of the graph using dense subgraphs. Existing algorithms that find many dense subgraphs do not have overlapping output, and hence provide limited coverage. Other methods that produce overlapping clusters do not generate dense subgraphs. The main goal of this paper is to develop provable and practical methods that can provide overlapping dense subgraphs that can cover large portions of real-world networks. Our contribution is an algorithm CohortRecovery that achieves this goal. We first develop a mathematical framework of triadic cohorts that captures the notion of ``detectable dense subgraphs'' that potentially overlap. We prove that CohortRecovery can output a set of dense subgraphs, such that each triadic cohort is almost completely contained in some dense subgraph. We give a practical implementation of CohortRecovery and demonstrate it on a variety of datasets. It typically runs in under ten minutes on a commodity machine even on graphs with tens of millions of edges. For numerous datasets, CohortRecovery is able to cover more than 25\% of the vertices in non-trivial subgraphs of density more than 0.8, and is significantly better than a wide variety of scalable graph clustering/community detection algorithms. Moreover, we demonstrate that output of CohortRecovery captures ground truth clusters obtained by manual curation.

0.26

Statistical Detectability of Coordination

cs.SI ·2026-10-27 ·Letizia Iannucci, Antonis Matakos, Mikko Kivelä
similarity 0.53
Abstract

Information operations exploit coordinated activity on social media to amplify messages and manipulate public discourse. A common approach to coordination detection is to project account-entity interactions into account similarity networks based on temporal proximity, action counts, or behavioural similarity, and identify dense subgraphs or behavioural clusters. However, the current methodology finds groups of co-activated accounts or partitions all users into most similarly acting clusters, even when the accounts are acting independently of each other or the co-activity is due to some expected source. We formulate coordination detection based on hypothesis testing of account pairs and compare different null models. We connect the resulting pairwise scores to the planted-submatrix detection problem and derive statistical and computational limits as functions of group size, population size, and signal strength. We estimate the signal for 7 modalities of coordination over 26 labelled information-operation datasets, and compare the predicted regime with the performance of recovery heuristics. Our method achieves higher agreement with the labelled ground truth than previously reported, but the choice of null model is important and it changes the regime of most modalities. While it is always possible to extract a set of significantly densely co-acting accounts across nearly all modalities regardless of regime, density alone is uninformative of detection performance, rendering anomalous cluster discovery a poor proxy for recovering an information operation. Detectability boundaries establish whether an operation of a given size and signal can be recovered at all, and how much confidence a flagged group warrants.

0.13

Motifs in temporal hypergraphs

cs.SI cs.DSphysics.soc-ph ·2026-09-10 ·Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
similarity 0.52
Abstract

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

0.22

Declining Modularity of Intellectual Bases During the Emergence of Research Areas

cs.DL physics.soc-phcs.SI ·2026-08-17 ·Kazuki Nakajima, Yuya Sasaki, Masaki Aida
similarity 0.52
Abstract · 21 pages, 6 figures; supplementary information included as ancillary file

Understanding how research areas emerge can help identify nascent areas early and inform research strategy, yet how the intellectual base of a field restructures as an area takes shape remains unclear. We hypothesize that the emergence of a research area is accompanied by the integration of largely separate knowledge communities, observable as a decline in the modularity of its co-citation network, which represents its intellectual base. We propose a framework that tracks this modularity over time, evaluates the statistical robustness of its changes, and identifies the papers highly associated with the decline. We applied it to three areas with different modes of growth: higher-order network science, superstring theory, and graph representation learning. In all three, modularity declined in correspondence with each area's emergence or transformation, and in superstring theory, the decline aligns with an independently documented transition. Further analysis of higher-order network science shows that its decline reflects a cross-disciplinary integration. In graph representation learning, the gradual decline is followed by a rise, which we interpret as a re-differentiation after the emergence period. Our results suggest that a decline in the modularity of a co-citation network can serve as a structural signature that retrospectively characterizes this integrative mode of emergence.

0.19

HeteGCD: Statistics-Aware Dual-Prototype Learning for Generalized Category Discovery on Heterophilous Graphs

cs.LG cs.AI ·2026-10-27 ·Xuanzhi Xi, Tongze Zhang, Zhili Qin, Yulin Tao, Hongliang Wang +3 more
similarity 0.52
Abstract

Heterophilous graphs are prevalent in real-world applications, where connected nodes often exhibit dissimilar attributes or belong to different classes, posing significant challenges to conventional graph learning methods based on homophily. This limitation becomes particularly pronounced in generalized category discovery (GCD), which requires models to recognize known classes and discover novel ones using labels from known classes only. However, existing graph GCD methods typically rely on aforementioned homophily-based inductive biases, which are ill-suited to heterophilous graphs. Meanwhile, although current heterophilous graph learning methods exploit diverse neighborhood signals, their selection and fusion are often guided by supervision across all classes, including novel classes whose labels are unavailable in GCD. These limitations raise a key question: how can heterogeneous neighborhood information be effectively leveraged for category discovery without any novel-class supervision? To answer this question, in this study we propose HeteGCD, a new statistics-aware dual-prototype learning perspective for generalized category discovery on heterophilous graphs. The key idea is to examine both statistics of local attribute differences and neighborhood class distribution to extract discriminative information in feature and probability spaces simultaneously. Specifically, a gated dual-stream encoder integrates both node attributes and local attribute-difference statistics to learn informative node representations. Afterwards, a dual-prototype classifier combines feature-based similarity with distribution-based consistency to support category discovery. Experiments on five heterophilous graphs show that HeteGCD achieves competitive performance against 24 baseline combinations.

0.25