Optimization of learning on graphs and spatio-temporal data
Creators: name: Qin, Kai
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 460506
subject: Graph, social and multimedia data
classificationCode: 460511
subject: Stream and sensor data
classificationCode: 460809
subject: Pervasive computing

description: A variety of information can be naturally encapsulated with graphs. They can effectively represent entities' roles and relationships in different contexts, such as user communication in social networks, human mobility in location-based networks, and parking locations in road graphs. These robust data structures allow better extraction of potential knowledge from the represented datasets for different learning tasks. For instance, online social networks, modelled as graphs, can provide us with many insights into the communication patterns of users and potential demographic information. Representing sensor data for road traffic or parking slots as graphs allow us better to monitor the flows, utilization, and neighborhood influences. Moreover, location-based social networks are used to record the movements or check-ins of online users, which is essential for urban planning and improving location-based services for individuals.

Modern graphs are often large, sparse, and complex. Studying them encounters several common challenges. First, computational complexity can be an issue in search problems of large graphs, which are often NP-complete or NP-hard. For example, matching each pair of nodes among two large graphs will be time-consuming. And finding an optimal path on graphs is another common task that could face an exponential increase in computation and space with the extension of graph size. Second, some graph data will exhibit its dynamic or evolution in the spatial or temporal dimension, such as constant updates of the status of parking nodes in sensor networks of car parking or users' movements in location-based social networks. In addition, many networks have the issue of sparsity due to the missing of partial nodes or connections, which will cause bias in other learning work such as node prediction. Specific solutions are required to handle these challenges in relevant learning missions, such as graph matching, inference of missing properties, routing problems, and scheduling issues. This study aims to explore and analyze modern networks from three perspectives: the optimization of efficiency on large graph alignment, the imputation of missing graph properties with spatial-temporal features, and improving effectiveness in multiple-agent traveling issues.

Matching nodes (e.g., users in social networks) among multiple graphs can provide additional insights for association learning and recommendations. However, modern networks have become increasingly large, making this task difficult. Graph alignment is a task to match the corresponding entities between different graphs with topological structure or node feature similarity. In this case, graph compression is necessary to transform large graphs into smaller ones while maintaining specific characteristics for boosting data processing or learning. The essential question we try to solve is how to enable compression on graphs to achieve more effective and efficient network alignment. The proposed framework integrates a novel graph compression algorithm to maintain the topological consistency between different networks during shrinking to speed up the overall procedure of node alignments. More specifically, the new compression mechanism can preserve the consistency of topological structure among different coarsened graphs by leveraging the advantages of node embedding. And the embedding similarity of nodes was employed for matching super-nodes and uncompressed nodes in coarsened graphs.

An increasing number of graphs have been developed in spatial or temporal dimensions. For instance, various GPS-based social applications can record users' visiting locations with time. However, missing values commonly exist in studying this human mobility data, which brings difficulties or bias to relevant learning tasks. Significantly, human mobility data at the macro-city scale is usually accompanied by arbitrary movements, no uniform frequency of point collection, and sparsity. The patterns and factors can vary dramatically along with the different distribution of check-in positions. Intuitively, the imputation of missing human locations can be solved based on spatial-temporal features in mobility networks. The proposed algorithm solves the imputation of human positions in city areas and improves forward movement forecasting. It was built on attention-based modules to learn point embeddings in graph structures, capturing dependencies or coexistence patterns between observed locations and missing values in trajectories.

We also extend the research to the path-searching issues on transportation graphs, such as the sensor networks for car parking management. A classical optimization issue, the traveling salesman problem, was studied extensively to find an optimal path for one agent to travel on a graph with minimum cost. This concept provides a basis to solve the concern regarding the arrangement of multiple officers to patrol the parking facilities. It has been known that illegal parking could lead to wasted resources and exacerbation of traffic jams. We presented new solutions based on established parking networks to alleviate the car parking issues for better parking management. The Multiple Traveling Officers Problem (MTOP) was newly introduced to model this type of concern. It requires a number of parking officers to work together to patrol parking points and issue tickets to illegally parked vehicles in the city areas, where the parking status is dynamically changed. Simultaneously, a family of novel meta-heuristic variations was proposed to solve this multiple-agent orienteering problem.

In conclusion, this study aims to solve and optimize machine learning tasks performed over complex graphs, including network alignment, graph compression, missing-location imputation, and orienteering problems. We expect the proposed solutions to supply new alternatives for the relevant issues and inspire the research community to conduct further work on these topics in the future.