210 research outputs found
Multi-relation graph summarization
No full textGraph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In
this paper, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for
the classic problem of lossless single-relation graph summarization. Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of k-Median clustering for the single relation solution can
be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms.Ministry of Education (MOE)Arijit Khan is supported by MOE Tier 1 and Tier 2 grants RG117/19 and MOE2019T2-2-042
Data mining – project II
No full textThe purpose of this report is to document what the author had done in the project to investigate
problems in data mining and designing novel algorithms to solve it and compare against existing
approaches. The objective of the project is to determine whether the current approaches to
datamining are optimal and come up with possibly better methods to go about it. The project
requires the author to data mine from a given set of data, analyze the results and attempt to
improve upon existing methodologies.Bachelor of Engineering (Computer Engineering
Measurements, analyses, and insights on the entire ethereum blockchain network
No full textBlockchain has become increasingly popular with the prevalence of cryptocurrencies and decentralized applications. In this project, interactions in Ethereum’s blockchain will be analysed. Ethereum is a distributed public blockchain network that focuses on creation and execution of codes (smart contracts) for decentralized applications. It is a platform for sharing of information in a global state that is immutable. Ethereum blockchain introduces a novel ecosystem of human users and autonomous agents (smart contracts). In this project, the entire interaction network from entire Ethereum blockchain data is reconstructed in order to analyse the possible interaction types in the network: user-to-user, user-to-contract, contract-to-contract and contract-to-user. Vertices refers to the account in the network (addresses of users or smart contracts) and edges refers to interaction between them. Analyses done on the different interactions in the network reveal new insights by combining information from the four networks. In this project, several graph properties are applied, both local and global properties, to study these networks in detail. From the results, discuss their similarities and differences with social networks and the Web, draw interesting conclusions and highlight important, future research directions. Results and analyses are compiled into a full research paper and submitted, as the first author, to the WebConf (WWW) 2020 conference.Bachelor of Engineering (Computer Science
Population balance equation for collisional breakage: A new numerical solution scheme and its convergence
No full text<p><strong>Synopsis</strong></p><p>These files represent a reference implementation of the finite volume method for the solution of the discretised population balance equation for collisional breakge. Several test cases are provided. </p><p>Implementation language: Matlab (FORTRAN-derivative)</p><p>The method and its capabilities are described in<br>P. Kuswah, A. Das, J. Saha, A. Bück, "Population balance equation for collisional breakage: A new numerical solution scheme and its convergence", Communications in Nonlinear Science and Numerical Simulation, vol 121, 107244, 2023. </p><p>If the method or code is used in other work, cite<br>P. Kuswah, A. Das, J. Saha, A. Bück, "Population balance equation for collisional breakage: A new numerical solution scheme and its convergence", Communications in Nonlinear Science and Numerical Simulation, vol 121, 107244, 2023. </p><p><strong>License</strong></p><p>The implementation is distributed as-is without taking over any responsibility by the authors or their affiliated institutions for potential damages resulting from its use. </p><p>The implementation is made available under Creative Commons Attribution Non Commercial No Derivatives 4.0 International. </p><p><strong>Folder contents</strong></p><p>The reference implementations are provided for the cases discussed in the mentioned publication. The implementation of the finite volume methode is stored in the sub-folders "DPBE_Brk", calling sequence and required initialisiations are given in the files "Main_FPT.m".</p><p>In case of problems, bug reports, feel free to contact any author.</p><p>On behalf of all authors,</p><p>Andreas Bück<br>Institute of Particle Technology<br>Friedrich-Alexander-Universität Erlangen-Germany<br>[email protected]<br>www.spg.forschung.fau.de</p><p> </p><p>v1.0: 31.08.2023</p>
Knowledge Graphs Querying
No full textKnowledge graphs (KGs) such as DBpedia, Freebase, YAGO, Wikidata, and NELL were constructed to store large-scale, real-world facts as (subject, predicate, object) triples - that can also be modeled as a graph, where a node (a subject or an object) represents an entity with attributes, and a directed edge (a predicate) is a relationship between two entities. Querying KGs is critical in web search, question answering (QA), semantic search, personal assistants, fact checking, and recommendation. While significant progress has been made on KG construction and curation, thanks to deep learning recently we have seen a surge of research on KG querying and QA. The objectives of our survey are two-fold. First, research on KG querying has been conducted by several communities, such as databases, data mining, semantic web, machine learning, information retrieval, and natural language processing (NLP), with different focus and terminologies; and also in diverse topics ranging from graph databases, query languages, join algorithms, graph patterns matching, to more sophisticated KG embedding and natural language questions (NLQs). We aim at uniting different interdisciplinary topics and concepts that have been developed for KG querying. Second, many recent advances on KG and query embedding, multimodal KG, and KG-QA come from deep learning, IR, NLP, and computer vision domains. We identify important challenges of KG querying that received less attention by graph databases, and by the DB community in general, e.g., incomplete KG, semantic matching, multimodal data, and NLQs. We conclude by discussing interesting opportunities for the data management community, for instance, KG as a unified data model and vector-based query processing.</p
Explainable graph classification with deep learning models
No full textGraph Classification is a promising area of deep learning, but it has a significant drawback. We need to understand the reasons behind the model’s predicted label of an input graph to trust the prediction, but these reasons are not supplied by Graph Classification models. Hence, Graph Classification Interpretability Methods were conceived. To analyse a new interpretability method, GNNExplainer, on a comparative basis with established methods in our main reference, saliency (also known as CG), GRAD-CAM and DeepLIFT, we develop a bridging algorithm and find the node attribution score of each node in a test graph. The scores of all the nodes in the test graph dataset are then used to produce quantitative metrics (fidelity, contrastivity and sparsity) for comparison.Bachelor of Engineering (Computer Science
Influence maximization on dynamic graphs
No full textIn the real world, there are many applications of the stream such as social networks and telecommunication networks. Due to the great potential in targeted recommendations and viral marketing, there is a tremendous incentive to find the top k influencers. However, due to the nature of the dynamic graph, we will tackle the inherent problem of finding the top k influencers as the dynamic graph is constantly changing. We model the stream as slip shots of the static graph that changes over the time. From there, we take note of the incoming changes to the edges and attempt in handling those mutually exclusive cases. Under the popular use of the independent cascade model, we develop an algorithm that performs an update to the top k nodes based on the mutually exclusive cases of edge addition, edge deletion and edge modification. Using up to date research by other paper and the DBLP collaboration network dataset, we validate the use of our method on the network and present a timeline of the most influential authors in the network.Bachelor of Engineering (Computer Science
Graph classification with DFS code and LSTM
No full textGraphs are data structures constructed by a set of nodes connected by edges. Graph-structured data are highly prevalent in addressing real-world applications and problems within the area of mathematics, computing, molecular biology, and many other related fields. In recent times, machine learning associated with graphs is discovered to be a powerful approach to explore graph information and address various tasks. The graph classification task is one of the tasks that is to predict the class label of a given graph. In this report, we will focus on the graph classification task.
The graph convolutional neural networks, including GCNN + global average pool (GCNN+GAP), GraphSage, GCNN with sort pool (DGCNN), GCNN with differentiable pool (DIFFPOOL), can extract the local and global graph information with convolution layers, and thus perform well on the graph classification tasks. At the same time, the recurrent neural networks (RNN) such as GraphRNN and GraphGen show good performance in graph generation tasks. Hence, we would like to try RNN on graph classification tasks to understand if RNN can bring benefits to this area. In this report, we are going to compare both graph convolutional neural networks (GCNN) and recurrent neural networks (RNN) on four graph classification datasets.Bachelor of Engineering (Computer Engineering
Querying and mining complex graphs : uncertainty and multi-relations
No full textGraphs are important data representations that can ubiquitously model objects and their relations in a wide diversity of real-word applications. Effective and efficient graph analytics provide users with a deeper understanding of what is behind the data, thus can bene t a lot of useful applications such as node classification, node recommendation, link prediction, etc. Nowadays, besides the rapid growth in the volume of graphs, the inherent complexity on graphs has attracted great attention from data management community. This thesis will therefore focus on querying and mining uncertain and multi-relation graphs. Uncertain graphs can characterize the inherent uncertainty in the data due to many reasons, including noisy measurements, inference and prediction models, and explicit manipulations. For example, in a road network, each road junction can be represented as a node, and each road segment can serve as an edge with a blocking (e.g., traffic jam) probability. Meanwhile, the multi-relation graphs, where multiple edges may exist between a same pair of nodes, are even more expressive. Using the same example of a road network, the probability of traffic jam occurrence may vary with time. Other examples include interaction conditions and transformation probabilities from a protein to many others in a protein-protein interaction network, the topics and the corresponding probabilities that a user may re-tweet her friends' posts, etc. The uncertainty and the multi-relations over graphs bring about additional complexities to graph querying and mining. In this thesis, I investigated the following research problems. First, I conducted an experimental analyses about six state-of-the-art s-t reliability algorithms. The s-t reliability measures the probability that a target node t is reachable from a source node s. We introduced the algorithms and provided several corrections or adaptions. Then I implemented all of them on a same code base, and conducted the evaluation with uni ed metrics, medium to large real-world datasets, and same query workloads. We summarized their trade-offs, and provided guidelines for future researchers
and practitioners.
Then, I examined a network modification problem, aiming at maximizing the network reliability through adding a small budget of new edges. We designed solutions to the basic two-terminal reliability case, then generalized them to the multiple-source-target case, and further studied a restricted version of only considering most reliable paths. The experimental results and the real-world applications well validated the effectiveness and the efficiency of our solutions.
Next, I studied a novel variant of well-known influence maximization problem by finding influential seed users and relevant topics simultaneously. Instead of using a fixed information diffusion probability between each pair of users, variations of diffusion probability in different topics were allowed. We formally characterized the problem and provided an iterative solution. The efficiency of the seed finding part was improved by up to 30%, while the accuracy of the topic finding part was improved by up to 30%.
Furthermore, I applied the uncertain graph to model the crowd errors in the solution to the crowdsourcing entity resolution problem. With the help of our novel metric, the "reliability" of a clustering, the next crowdsourcing questions could be selected wisely, which thus improved the accuracy by 15%, and reduced the crowdsourcing cost by 50%. I also developed a demo software for the proposed PERC system.
Finally, I presented our multi-relation graph summarization techniques. In our twostep baselines, a final summary was generated by properly aggregating the summary of each relation. I demonstrated their drawbacks and designed holistic solutions. Among them, the k-median clustering approach was able to return a summary with a provable bounded size.Doctor of Philosoph
A demonstration for influence maximization over graph
No full textThis report introduces the final year project of visualisation of
simulated social networking influence spread, conducted by Goh Shao
Peng using Java (Eclipse), Gephi graph visualisation platform, and
Sigma.js as a cross platform visualisation. It starts with introduction
of the importance and advantages of social networking as a medium
for widespread information cascade, along with its definitions and
limitations, followed by how does the process flow for visualisation
of a small simulated social network in a graph form. This report
discusses the process, the basics of influence maximization, the pros
and cons of using said technique to visualise a graph network along
with testing of various simulated datasets, and finally the conclusion
for possible and further improvement and implementation. Step by
step images will be attached in the report as well.Bachelor of Engineering (Computer Science
- …
