M.Sc. (Tech) Chamalee Wickrama Arachchi defends her PhD thesis "Methods for Finding Structures in Feature-rich Graph Networks: Multilayered, Labeled, and Temporal" on Friday the 10th of October 2025 at 13 o'clock in the University of Helsinki Exactum building, Auditorium B222 (Pietari Kalmin katu 5, 2nd floor). Her opponent is Professor Panagiotis Papapetrou (Stockholm University, Sweden) and custos Professor Nikolaj Tatti (University of Helsinki). The defence will be held in English.
The thesis of Chamalee Wickrama Arachchi is a part of research done in the Department of Computer Science and in the Data Analytics and Cyber Security group at the University of Helsinki. Her supervisor has been Professor Nikolaj Tatti (University of Helsinki).
Methods for Finding Structures in Feature-rich Graph Networks: Multilayered, Labeled, and Temporal
A graph is a fundamental structure for modelling data in various domains, including sociology, finance, bioinformatics, and transportation. In this thesis, we develop methods to solve graph problems in feature-rich networks. A feature-rich network is a graph with additional information, such as timestamps, vertex labels, or multiple graph snapshots. Here, graph snapshots are defined as a collection of graphs that share the same set of vertices but may contain different sets of edges.
First, we formulate two problems focused on identifying dense components given multiple graph snapshots as input. In the first problem, we search for a collection of dense subgraphs, one from each snapshot. The vertex set of each subgraph is allowed to vary under a user-defined pairwise Jaccard constraint. Our objective is to maximize the sum of densities of the induced subgraphs while enforcing a pairwise Jaccard constraint. We also consider an alternative problem where subgraphs with large pairwise Jaccard indices are rewarded. To do this, we in- corporate the indices directly into the objective function. In the second problem, we aim to find a subset of vertices such that the density induced by this set is evenly distributed across the graph snapshots while maximizing their total density. We refer to such a subset of vertices as a fair densest subgraph.
In our next problem, we find a dense subgraph that favors strong triadic relationships within the subgraph. In many social networks, interactions between entities differ in strength, with some ties stronger than others. To label the edges as either strong or weak, we use strong triadic closure: if a vertex connects strongly to two others, these two should be connected by at least a weak edge.
Next, we consider directed graphs in which each vertex has a set of labels. Our goal is to rank vertices such that each rank is succinctly explained by a set of labels, while minimizing a score called agony, which penalizes edges from higher ranks to lower ranks as well as edges between vertices with the same rank.
Finally, we study temporal networks, where the edges are timestamped. Our goal is to partition vertices while simultaneously identifying recurring segments with shared model parameters.
For all of these problems, we analyze their computational complexity, design algorithms, and then present extensive experimental results showing that our algorithms produce good solutions on synthetic datasets and perform fast enough on real-world datasets.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available in the University of Helsinki open repository Helda at http://urn.fi/URN:ISBN:978-952-84-1917-4.
Printed copies will be available on request from Chamalee Wickrama Arachchi: chamalee.wickramaarachch@helsinki.fi