Studying and Improving Graph Neural Network-based Motif Estimation
Graph Neural Networks (GNNs) are a predominant method for graph representation learning. However, beyond subgraph frequency estimation, their application to network motif significance-profile (SP) prediction remains under-explored, with no established benchmarks in the literature. We propose to address this problem, framing SP estimation as a task independent of subgraph frequency estimation. Our approach shifts from frequency counting to direct SP estimation and modulates the problem as multitarget regression. The reformulation is optimised for interpretability, stability and scalability on large graphs. We validate our method using a large synthetic dataset and further test it on real-world graphs. Our experiments reveal that 1-WL limited models struggle to make precise estimations of SPs. However, they can generalise to approximate the graph generation processes of networks by comparing their predicted SP with the ones originating from synthetic generators. This first study on GNN-based motif estimation also hints at how using direct SP estimation can help go past the theoretical limitations that motif estimation faces when performed through subgraph counting.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph GenerationGraph Neural NetworkGraph Representation LearningRepresentation LearningSubgraph CountingSimilar Papers 제목 키워드 기반
CN-Motifs Perceptive Graph Neural Networks
Graph neural networks (GNNs) have been the dominant approaches for graph representation learning. However, most GNNs are applied to homophily graphs and perform poorly on heterophily graphs. Meanwhile, these GNNs fail to…
Graph Representation LearningNode ClassificationRepresentation LearningAccurate and Fast Estimation of Temporal Motifs using Path Sampling
Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. Many real-world networks are directed and temporal, where edges have timestamps. Motif counting…
GPUGraph MiningHigher-Order Ranking and Link Prediction: From Closing Triangles to Closing Higher-Order Motifs
In this paper, we introduce the notion of motif closure and describe higher-order ranking and link prediction methods based on the notion of closing higher-order network motifs. The methods are fast and efficient for rea…
Link PredictionPredictionodeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
Counting the number of occurrences of small connected subgraphs, called temporal motifs, has become a fundamental primitive for the analysis of temporal networks, whose edges are annotated with the time of the event they…
Computing Expected Motif Counts for Exchangeable Graph Generative Models
Estimating the expected value of a graph statistic is an important inference task for using and learning graph models. This note presents a scalable estimation procedure for expected motif counts, a widely used type of g…
Vocal Bursts Type Prediction