Massey Documents by Type

Permanent URI for this communityhttps://mro.massey.ac.nz/handle/10179/294

Browse

Has files: YesSubject: search.filters.subject.Graph algorithms

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    BatchHL+: batch dynamic labelling for distance queries on large-scale networks
    (Springer-Verlag GmbH Germany, part of Springer Nature, 2024-01) Farhan M; Koehler H; Wang Q
    Many real-world applications operate on dynamic graphs to perform important tasks. In this article, we study batch-dynamic algorithms that are capable of updating distance labelling efficiently in order to reflect the effects of rapid changes on such graphs. To explore the full pruning potentials, we first characterize the minimal set of vertices being affected by batch updates. Then, we reveal patterns of interactions among different updates (edge insertions and edge deletions) and leverage them to design pruning rules for reducing update search space. These interesting findings lead us to developing a new batch-dynamic method, called BatchHL+ , which can dynamize labelling for distance queries much more efficiently than existing work. We provide formal proofs for the correctness and minimality of BatchHL+ which are non-trivial and require a delicate analysis of patterns of interactions. Empirically, we have evaluated the performance of BatchHL+ on 15 real-world networks. The results show that BatchHL+ significantly outperforms the state-of-the-art methods with up to 3 orders of magnitude faster in reflecting updates of rapidly changing graphs for distance queries.
  • Thumbnail Image
    Item
    Graph learning and its applications : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science, Massey University, Albany, Auckland, New Zealand
    (Massey University, 2022) Hu, Rongyao
    Since graph features consider the correlations between two data points to provide high-order information, i.e., more complex correlations than the low-order information which considers the correlations in the individual data, they have attracted much attention in real applications. The key of graph feature extraction is the graph construction. Previous study has demonstrated that the quality of the graph usually determines the effectiveness of the graph feature. However, the graph is usually constructed from the original data which often contain noise and redundancy. To address the above issue, graph learning is designed to iteratively adjust the graph and model parameters so that improving the quality of the graph and outputting optimal model parameters. As a result, graph learning has become a very popular research topic in traditional machine learning and deep learning. Although previous graph learning methods have been applied in many fields by adding a graph regularization to the objective function, they still have some issues to be addressed. This thesis focuses on the study of graph learning aiming to overcome the drawbacks in previous methods for different applications. We list the proposed methods as follows. • We propose a traditional graph learning method under supervised learning to consider the robustness and the interpretability of graph learning. Specifically, we propose utilizing self-paced learning to assign important samples with large weights, conducting feature selection to remove redundant features, and learning a graph matrix from the low dimensional data of the original data to preserve the local structure of the data. As a consequence, both important samples and useful features are used to select support vectors in the SVM framework. • We propose a traditional graph learning method under semi-supervised learning to explore parameter-free fusion of graph learning. Specifically, we first employ the discrete wavelet transform and Pearson correlation coefficient to obtain multiple fully connected Functional Connectivity brain Networks (FCNs) for every subject, and then learn a sparsely connected FCN for every subject. Finally, the ℓ1-SVM is employed to learn the important features and conduct disease diagnosis. • We propose a deep graph learning method to consider graph fusion of graph learning. Specifically, we first employ the Simple Linear Iterative Clustering (SLIC) method to obtain multi-scale features for every image, and then design a new graph fusion method to fine-tune features of every scale. As a result, the multi-scale feature fine-tuning, graph learning, and feature learning are embedded into a unified framework. All proposed methods are evaluated on real-world data sets, by comparing to state-of-the-art methods. Experimental results demonstrate that our methods outperformed all comparison methods.
  • Thumbnail Image
    Item
    Genetic network programming with reinforcement learning and optimal search component : a thesis presented in partial fulfilment of the requirements for the degree of Master of Science in Computer Sciences at Massey University, Auckland, New Zealand
    (Massey University, 2019) Alshehri, Mona Abdulrahman M
    This thesis presents ways of improving the genetic composition, structure and learning strategies for a graph-based evolutionary algorithm, called Genetic Networking Programming with Reinforcement Learning (GNP-RL), particularly when working with multi-agent and dynamic environments. GNP-RL is an improvement over Genetic Programming, allowing for the concise representation of solutions in terms of a networked graph structure and uses RL to further refine the graph solutions. This work has improved GNP-RL by combining three new techniques: Firstly, it has added a reward and punishment scheme as part of its learning strategy that supports constraint conformance, allowing for a more adaptive training of the agent, so that it can learn how to avoid unwanted situations more effectively. Secondly, an optimal search algorithm has been combined in the GNP-RL core to get an accurate analysis of the exploratory environment. Thirdly, a task prioritization technique has been added to the agent’s learning by giving promotional rewards, so they are trained on how to take priority into account when performing tasks. In this thesis, we applied the improved algorithm to the Tile World benchmarking testbed, which is considered as one of the standard complex problems in this domain, having only a sparse training set. Our experiment results show that the proposed algorithm is superior than the best existing variant of the GNP-RL algorithm [1]. We have achieved 86.66% test accuracy on the standard benchmarking dataset [2]. In addition, we have created another benchmarking dataset, similar in complexity to the one proposed in [1], to test the proposed algorithms further, where it achieved a test accuracy of 96.66%; that is 33.66% more accurate.