Date of Award

5-11-2025

Date Published

June 2025

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Reza Zafarani

Keywords

graph mining;higher-order network;link prediction

Subject Categories

Computer Sciences | Physical Sciences and Mathematics

Abstract

Networks are natural representations of interactions in the real world (social networks, bio-networks, road networks, and the like) and are utilized across various disciplines. By default, network interactions are pairwise; in recent years, the demand for model ing higher-order interactions has kept increasing. For example, in collaboration networks, we aim to distinguish between one publication coauthored by three or three publications coauthored by two in a triangle. In this work, we perform higher-order network analysis in the following two directions. First, we explore the influence of higher-order structures on dyadic (pairwise) graphs; second, we model higher-order interactions by ordered hy pergraphs and analyze their cross-order properties. Followed by applications such as link prediction and representation learning, we verify the effectiveness of higher-order network modelings. In dyadic graphs, specific subgraph patterns with high frequencies are called network mo tifs. Inspired by the study of motifs, we first introduce a neighborhood motif-based link prediction method. Through extensive observation of real-world graphs, we found that the network structure of the neighborhood has a strong influence on getting two nodes connected. Specifically, a more well-connected and compact structure leads to a higher probability of wiring rather than a sparser structure. Based on this discovery, we propose a novel scoring method based on neighborhood motifs. By learning a γ-decaying model, we measure the pairwise similarities between nodes more accurately, even when only using the information of the common neighbors, which is often used in current techniques. We further model higher-order interactions directly using ordered hypergraphs. We ex plore and quantify similarities among various orders of the network. Our goal is to build relationships between different network orders and to solve higher-order problems using lower-order information. Similarities between different orders are not directly compara ble. Hence, we introduce a set of general cross-order similarities and a measure: subedge rate. Our experiments on multiple real-world datasets demonstrate that most higher-order networks have considerable consistency as we move from higher orders to lower orders. Using this discovery, we develop a new cross-order framework for a higher-order link pre diction method. These methods can predict higher-order links from lower-order edges, which cannot be attained by current higher-order methods that rely on data from a single order. Using the same topology, we explore the relationship between higher-order structure and spectral properties. These spectral properties are closely related to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. Specifically, we prove that the second moment provides an upper bound on the degree distributions while the third moment provides an upper bound on the number of on triangles. With the theoretical support, we use all such spec tral moments across different orders as the higher-order graph representation. Extensive experiments show the utility of this new representation in various settings. For instance, graph classification on higher-order graphs shows that this representation significantly out performs other techniques.

Access

Open Access

Download

Share

COinS