248 citations · 479 across the 39 of their papers we have counts for
45 papers
Distinguishing graphs with simple spectrum by homomorphism counts
Takanori Maehara
We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewid…
Self-Supervised Pretraining for Heterogeneous Hypergraph Neural Networks
Abdalgader Abubaker, Takanori Maehara, Madhav Nimishakavi +1
Recently, pretraining methods for the Graph Neural Networks (GNNs) have been successful at learning effective representations from unlabeled graph data. However, most of these meth…
Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters
Takanori Maehara, Hoang NT
Theoretical analyses for graph learning methods often assume a complete observation of the input graph. Such an assumption might not be useful for handling any-size graphs due to t…
Abelian Neural Networks
Kenshin Abe, Takanori Maehara, Issei Sato
We study the problem of modeling a binary operation that satisfies some algebraic requirements. We first construct a neural network architecture for Abelian group operations and de…
r-Gathering Problems on Spiders:Hardness, FPT Algorithms, and PTASes
Soh Kumabe, Takanori Maehara
We consider the min-max -gathering problem described as follows: We are given a set of users and facilities in a metric space. We open some of the facilities and assign each use…
Stacked Graph Filter
Hoang NT, Takanori Maehara, Tsuyoshi Murata
We study Graph Convolutional Networks (GCN) from the graph signal processing viewpoint by addressing a difference between learning graph filters with fully connected weights versus…
Rank axiom of modular supermatroids: A connection with directional DR submodular functions
Takanori Maehara, So Nakashima
A matroid has been one of the most important combinatorial structures since it was introduced by Whitney as an abstraction of linear independence. As an important property of a mat…
Graph Homomorphism Convolution
Hoang NT, Takanori Maehara
In this paper, we study the graph classification problem from the graph homomorphism perspective. We consider the homomorphisms from to , where is a graph of interest (e…
Tightly Robust Optimization via Empirical Domain Reduction
Akihiro Yabe, Takanori Maehara
Data-driven decision-making is performed by solving a parameterized optimization problem, and the optimal decision is given by an optimal solution for unknown true parameters. We o…
Learning Directly from Grammar Compressed Text
Yoichi Sasaki, Kosuke Akimoto, Takanori Maehara
Neural networks using numerous text data have been successfully applied to a variety of tasks. While massive text data is usually compressed using techniques such as grammar compre…
State-Space Based Network Topology Identification
Mario Coutino, Elvin Isufi, Takanori Maehara +1
In this work, we explore the state-space formulation of network processes to recover the underlying structure of the network (local connections). To do so, we employ subspace techn…
A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks
Takanori Maehara, Hoang NT
We present a simple proof for the universality of invariant and equivariant tensorized graph neural networks. Our approach considers a restricted intermediate hypothetical model na…
Empirical Hypothesis Space Reduction
Akihiro Yabe, Takanori Maehara
Selecting appropriate regularization coefficients is critical to performance with respect to regularized empirical risk minimization problems. Existing theoretical approaches attem…
Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---
Takanori Maehara, So Nakashima, Yutaro Yamaguchi
We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Since a distributive lattice i…
-Gather Clustering and -Gathering on Spider: FPT Algorithms and Hardness
Soh Kumabe, Takanori Maehara
We consider min-max -gather clustering problem and min-max -gathering problem. In the min-max -gather clustering problem, we are given a set of users and divide them into…
PTAS and Exact Algorithms for -Gathering Problems on Tree
Soh Kumabe, Takanori Maehara
r-gathering problem is a variant of facility location problems. In this problem, we are given a set of users and a set of facilities on same metric space. We open some of the facil…
Stochastic Monotone Submodular Maximization with Queries
Takanori Maehara, Yutaro Yamaguchi
We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain def…
State-Space Network Topology Identification from Partial Observations
Mario Coutino, Elvin Isufi, Takanori Maehara +1
In this work, we explore the state-space formulation of a network process to recover, from partial observations, the underlying network topology that drives its dynamics. To do so,…
Data Cleansing for Models Trained with SGD
Satoshi Hara, Atsushi Nitanda, Takanori Maehara
Data cleansing is a typical approach used to improve the accuracy of machine learning models, which, however, requires extensive domain knowledge to identify the influential instan…
Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
Hoang NT, Takanori Maehara
Graph neural networks have become one of the most important techniques to solve machine learning problems on graph-structured data. Recent work on vertex classification proposed de…
Incorrect implementations of the Floyd--Warshall algorithm give correct solutions after three repeats
Ikumi Hide, Soh Kumabe, Takanori Maehara
The Floyd--Warshall algorithm is a well-known algorithm for the all-pairs shortest path problem that is simply implemented by triply nested loops. In this study, we show that the i…
Optimal Algorithm to Reconstruct a Tree from a Subtree Distance
Takanori Maehara, Kazutoshi Ando
This paper addresses the problem of finding a representation of a subtree distance, which is an extension of the tree metric. We show that a minimal representation is uniquely dete…
Faking Fairness via Stealthily Biased Sampling
Kazuto Fukuchi, Satoshi Hara, Takanori Maehara
Auditing fairness of decision-makers is now in high demand. To respond to this social demand, several fairness auditing tools have been developed. The focus of this study is to rai…
Convex Hull Approximation of Nearly Optimal Lasso Solutions
Satoshi Hara, Takanori Maehara
In an ordinary feature selection procedure, a set of important features is obtained by solving an optimization problem such as the Lasso regression problem, and we expect that the…