Tsuyoshi Murata
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Tsuyoshi Murata has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Xin Liu
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
3 shared publications - Aurora Rossi2 shared publications
- Emanuele Natale2 shared publications
- Frederik Mallmann-Trenn
King's College London, London, United Kingdom
2 shared publications - Frédéric Giroire
Université Côte d’Azur Inria CNRS I3S
2 shared publications - Justin Dachille2 shared publications
Latest Publications
- Open Access
BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures.A particularly well‑known centrality measure is betweenness centrality, which becomes computationally prohibitive on large‑scale networks.Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.We propose BRAVA‑GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree‑based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks.Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power‑law exponents outside the scale‑free regime, better capturing the structure of real‑world graphs like road networks.This design enables BRAVA-GNN to generalize across diverse graph families while using 54$\times$ fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214\% improvement in Kendall–Tau correlation and up to 70$\times$ speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
Open AccessBRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures.A particularly well‑known centrality measure is betweenness centrality, which becomes computationally prohibitive on large‑scale networks.Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.We propose BRAVA‑GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree‑based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks.Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power‑law exponents outside the scale‑free regime, better capturing the structure of real‑world graphs like road networks.This design enables BRAVA-GNN to generalize across diverse graph families while using 54$\times$ fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214\% improvement in Kendall–Tau correlation and up to 70$\times$ speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
- Open Access
BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, which becomes computationally prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state-of-the-art methods fail to generalize to high-diameter graphs such as road networks. We propose BRAVA-GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree-based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks. Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power-law exponents outside the scale-free regime, better capturing the structure of real-world graphs like road networks. This design enables BRAVA-GNN to generalize across diverse graph families while using 54x fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214% improvement in Kendall-Tau correlation and up to 70x speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
Open AccessBRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, which becomes computationally prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state-of-the-art methods fail to generalize to high-diameter graphs such as road networks. We propose BRAVA-GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree-based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks. Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power-law exponents outside the scale-free regime, better capturing the structure of real-world graphs like road networks. This design enables BRAVA-GNN to generalize across diverse graph families while using 54x fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214% improvement in Kendall-Tau correlation and up to 70x speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
- Open Access
- 28 December 2025
- Published by Springer Nature in Social Network Analysis and Mining
- Vol. 16 (1)
A multi-rounded adversarial scenario for graph-based promo fraud detection
Developing reliable models for detecting fraud is increasingly vital amidst the digitalization of our financial institutions and activities. While graph-based fraud detection models showed promising performances in recent years, the underpinning fraud definition and evaluation process they utilized rely heavily on a limited set of labeled datasets. This raises concerns about their vulnerability to distributional shifts and adversarial strategies often exhibited by real-life fraudsters. In response, we propose a novel scenario for graph fraud detection called Multi-round Adversarial Fraud Detection. Here, the fraud detection model is trained and evaluated iteratively on an adversarially evolving graph. This scenario more closely mimics fraud detection activities in real life while being less reliant on the underlying datasets since the graph evolution is induced by generator functions rooted in common fraud behavior. We show that existing models struggle to achieve good multi-round performance under the proposed scenario with F1 scores that consistently hover below 56 percent on subsequent rounds. To improve the aforementioned performance we propose Temporally Pre-trained Node Embedder (TPNE), a module that leverages self-supervised pre-training approach, explicitly separating and enhancing temporal information across multiple rounds. TPNE is both model and label-agnostic, improving the best-performing baseline by up to 4.6 percent in on-round F1 score and up to 32.9 percent in final recall.
- 28 December 2025
- Published by Springer Nature in Social Network Analysis and Mining
- Vol. 16 (1)
Open AccessA multi-rounded adversarial scenario for graph-based promo fraud detection
Developing reliable models for detecting fraud is increasingly vital amidst the digitalization of our financial institutions and activities. While graph-based fraud detection models showed promising performances in recent years, the underpinning fraud definition and evaluation process they utilized rely heavily on a limited set of labeled datasets. This raises concerns about their vulnerability to distributional shifts and adversarial strategies often exhibited by real-life fraudsters. In response, we propose a novel scenario for graph fraud detection called Multi-round Adversarial Fraud Detection. Here, the fraud detection model is trained and evaluated iteratively on an adversarially evolving graph. This scenario more closely mimics fraud detection activities in real life while being less reliant on the underlying datasets since the graph evolution is induced by generator functions rooted in common fraud behavior. We show that existing models struggle to achieve good multi-round performance under the proposed scenario with F1 scores that consistently hover below 56 percent on subsequent rounds. To improve the aforementioned performance we propose Temporally Pre-trained Node Embedder (TPNE), a module that leverages self-supervised pre-training approach, explicitly separating and enhancing temporal information across multiple rounds. TPNE is both model and label-agnostic, improving the best-performing baseline by up to 4.6 percent in on-round F1 score and up to 32.9 percent in final recall.