Mining Path Association Rules in Large Property Graphs (with Appendix)

• URL: http://arxiv.org/abs/2408.02029v2
• Date: Sun, 15 Sep 2024 09:54:08 GMT
• Title: Mining Path Association Rules in Large Property Graphs (with Appendix)
• Authors: Yuya Sasaki, Panagiotis Karras,
• Abstract summary: Association rule mining successfully discovers regular patterns in item sets and substructures. We introduce the problem of path association rule mining (PARM) We develop an efficient and scalable algorithm PIONEER that exploits an anti-monotonicity property to effectively prune the search space.
• Score: 15.11494401922146
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How can we mine frequent path regularities from a graph with edge labels and vertex attributes? The task of association rule mining successfully discovers regular patterns in item sets and substructures. Still, to our best knowledge, this concept has not yet been extended to path patterns in large property graphs. In this paper, we introduce the problem of path association rule mining (PARM). Applied to any \emph{reachability path} between two vertices within a large graph, PARM discovers regular ways in which path patterns, identified by vertex attributes and edge labels, co-occur with each other. We develop an efficient and scalable algorithm PIONEER that exploits an anti-monotonicity property to effectively prune the search space. Further, we devise approximation techniques and employ parallelization to achieve scalable path association rule mining. Our experimental study using real-world graph data verifies the significance of path association rules and the efficiency of our solutions.

Related papers

• Improving Graph Neural Networks by Learning Continuous Edge Directions [0.0]
  Graph Neural Networks (GNNs) traditionally employ a message-passing mechanism that resembles diffusion over undirected graphs. Our key insight is to assign fuzzy edge directions to the edges of a graph so that features can preferentially flow in one direction between nodes. We propose a general framework, called Continuous Edge Direction (CoED) GNN, for learning on graphs with fuzzy edges.
  arXiv  Detail & Related papers  (2024-10-18T01:34:35Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  We propose a general learnable graph matching method to address these issues. Our method achieves state-of-the-art performance on several MOT datasets. For image matching, our method outperforms state-of-the-art methods on a popular indoor dataset, ScanNet.
  arXiv  Detail & Related papers  (2023-03-27T17:39:00Z)
• Efficient Subgraph Isomorphism using Graph Topology [10.332465264309693]
  Subgraph isomorphism or subgraph matching is generally considered as an NP-complete problem. Almost all subgraph matching methods utilize node labels to perform node-node matching. We propose a method for identifying the node correspondence between a subgraph and a full graph in the inexact case without node labels.
  arXiv  Detail & Related papers  (2022-09-15T02:45:05Z)
• Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
  We present a generalized spectral clustering framework that can address both directed and undirected graphs. Our approach is based on the spectral relaxation of a new functional that we introduce as the generalized Dirichlet energy of a graph function. We also propose a practical parametrization of the regularizing measure constructed from the iterated powers of the natural random walk on the graph.
  arXiv  Detail & Related papers  (2022-03-07T09:18:42Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  We propose a graph kernel to compute more comprehensive similarity between paths and walks. We also combine it with optimal transport theory to extract more in-depth features of graphs. Our proposed method outperforms many state-of-the-art graph kernel methods.
  arXiv  Detail & Related papers  (2020-12-07T11:59:14Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.