Understanding subgraph patterns in high-dimensional networks

Networks are everywhere, from social networks to the Internet to our brain. Network data is becoming increasingly rich in structure, where network members (vertices) have many features, like clicks, likes and locations. These features position the vertices in a geometric space, where each coordinate represents one feature. In many applications, the number of features is immense, creating a high-dimensional geometry. Connections often appear between similar vertices, such as those representing people with identical hobbies. In mathematical terms, vertices that are close within the geometric space are likely to be connected. Thus, the geometric space strongly influences network connection patterns or subgraphs. Other subgraphs do not result from the geometry, but are characteristic for the particular network. These characteristic subgraphs often signal important network structures such as spam in email networks or crises in financial networks. Thus, it is crucial to identify the characteristic subgraphs for networks with geometric structures. However, due to their complexity current methods to identify characteristic subgraphs do not handle geometric structures, leading to incorrect identification of characteristic subgraphs. This creates the need to understand the relation between high-dimensional geometry and characteristic subgraphs. My first aim is to identify characteristic subgraphs by analyzing networks that have high-dimensional geometry in combination with the frequently observed variability in the number of neighbors. Studying networks with both properties is novel and requires the design of new optimization models and advanced test statistics. The second aim is to investigate the influence of subgraphs on geometry, finding the ‘hidden network information’ that subgraphs capture. I will focus on a new application of subgraphs in embeddings: simpler network descriptions that excel at addressing problems like item recommendation and missing link prediction. This research provides critical insights into characteristic subgraphs in real-world networks, with wide-ranging applications from improved spam identification to breast cancer detection.