Graph neural networks (GNNs) face dual challenges of limited structural expressiveness and opaque decision-making processes. Recent research on Subgraph Neural Networks (SGNNs) enhance model expressiveness through subgraph ensembles. However, their reliance on predefined sampling strategies leads to poor interpretability and computational inefficiency. Meanwhile, post-hoc GNN explainers enhance model interpretability but still struggle to translate their explanations into model improvements. This paper presents a novel framework that fundamentally bridges this gap by developing SGNNs with intrinsic interpretability. Our key innovation lies in constructing a self-interpretable architecture where the explanation generation mechanism is organically integrated with the prediction process. Our proposed Self-Interpretable SGNN introduces a reinforcement walk exploration (RWE-SGNN) as its data-driven sampling strategy, which can dynamically extract discriminative substructures during model training. This reinforcement walk exploration module not only provides inherent interpretability, but also enables: (1) efficient substructure extraction with less candidate number and simper embedding than traditional subgraph generation methods; and (2) provable equivalence in node coverage to traditional subgraph generation methods for connected subgraphs. Experiments on graph classification tasks show accuracy improvements over state-of-the-art GNNs, with case studies validating that the automatically identified subgraphs align with domain-specific knowledge.

Multidimensional Scaling (MDS) is an essential technique in multivariate analysis, with Weighted MDS (WMDS) commonly employed for tasks such as dimensionality reduction and graph drawing. However, the optimization of WMDS poses significant challenges due to the highly non-convex nature of its objective function. Stress Majorization, a method classified under the Majorization-Minimization algorithm, is among the most widely used solvers for this problem because it guarantees non-increasing loss values during optimization, even with a non-convex objective function. Despite this advantage, Stress Majorization suffers from high computational complexity, specifically $\mathcal{O}(\max(n^3, n^2 p))$ per iteration, where $n$ denotes the number of data points, and $p$ represents the projection dimension, rendering it impractical for large-scale data analysis. To mitigate the computational challenge, we introduce StableMDS, a novel gradient descent-based method that reduces the computational complexity to $\mathcal{O}(n^2 p)$ per iteration. StableMDS achieves this computational efficiency by applying gradient descent independently to each point, thereby eliminating the need for costly matrix operations inherent in Stress Majorization. Furthermore, we theoretically ensure non-increasing loss values and optimization stability akin to Stress Majorization. These advancements not only enhance computational efficiency but also maintain stability, thereby broadening the applicability of WMDS to larger datasets.

In machine learning, optimal transport (OT) theory is extensively utilized to compare probability distributions across various applications, such as graph data represented by node distributions and image data represented by pixel distributions. In practical scenarios, it is often necessary to solve multiple OT problems. Traditionally, these problems are treated independently, with each OT problem being solved sequentially. However, the computational complexity required to solve a single OT problem is already substantial, making the resolution of multiple OT problems even more challenging. Although many applications of fast solutions to OT are based on the premise of a single OT problem with arbitrary distributions, few efforts handle such multiple OT problems with multiple distributions. Therefore, we propose the anchor space OT (ASOT) problem: an approximate OT problem designed for multiple OT problems. This proposal stems from our finding that in many tasks the mass transport tends to be concentrated in a reduced space from the original feature space. By restricting the mass transport to a learned anchor point space, ASOT avoids pairwise instantiations of cost matrices for multiple OT problems and simplifies the problems by canceling insignificant transports. This simplification greatly reduces its computational costs. We then prove the upper bounds of its 1-Wasserstein distance error between the proposed ASOT and the original OT problem under different conditions. Building upon this accomplishment, we propose three methods to learn anchor spaces for reducing the approximation error. Furthermore, our proposed methods present great advantages for handling distributions of different sizes with GPU parallelization.

Optimal Transport (OT) has emerged as an effective metric in machine learning. However, its application to large-scale problems remains limited due to stringent usage conditions and significant computational complexity. Unbalanced Optimal Transport (UOT) is rapidly gaining attention by expanding the scope of its use through the relaxation of the original problem. Observing a recent connection between the UOT problem and the Lasso problem, this paper introduces safe screening—a technique prevalent in the Lasso community—to the UOT domain. Safe screening can significantly reduce computational time by identifying and disregarding zero elements in the sparse solution of the UOT problem. This represents the first successful application of the safe screening technique to the ℓ2penalized UOT problem. Addressing the specific structure of the constraint matrix in the UOT problem, a new projection method, and a cruciform two-hyperplane safe region construction method are proposed. Numerical evaluations of synthetic and real-world datasets demonstrate the extraordinary effectiveness of our proposed safe screening method without markedly increasing the computational burden.

With the increasing applications of Optimal Transport (OT) in the machine learning field, the Unbalanced Optimal Transport (UOT) problem, as a variant of the OT problem, has gained attention for its improved generality. There is an urgent need for fast algorithms that can efficiently handle large penalty parameters. In this paper, we prove that the recently proposed Majorize-Minimization algorithm for the UOT problem can be viewed as a form of the Bregman Proximal Descent (BPD), and we propose to use the dynamic penalty updating to overcome the substantial degradation of its convergence rate in response to large penalties. Using the dynamic scheme and Nesterov acceleration of the BPD algorithm, we can successfully compute more accurate and sparser solutions for the large penalty parameter and approach the computational speed of the well-known Sinkhorn’s algorithm, which sacrifices accuracy by adding an entropy item.

The Weisfeiler-Lehman (WL) test is a widely used algorithm in graph machine learning, including graph kernels, graph metrics, and graph neural networks. However, it focuses only on the consistency of the graph, which means that it is unable to detect slight structural differences. Consequently, this limits its ability to capture structural information, which also limits the performance of existing models that rely on the WL test. This limitation is particularly severe for traditional metrics defined by the WL test, which cannot precisely capture slight structural differences. In this paper, we propose a novel graph metric called the Wasserstein WL Subtree (WWLS) distance to address this problem. Our approach leverages the WL subtree as structural information for node neighborhoods and defines node metrics using the L1-approximated tree edit distance (L1-TED) between WL subtrees of nodes. Subsequently, we combine the Wasserstein distance and the L1-TED to define the WWLS distance, which can capture slight structural differences that may be difficult to detect using conventional metrics. We demonstrate that the proposed WWLS distance outperforms baselines in both metric validation and graph classification experiments.

The optimal transport (OT) problem has been used widely for machine learning. It is necessary for computation of an OT problem to solve linear programming with tight mass-conservation constraints. These constraints prevent its application to large-scale problems. To address this issue, loosening such constraints enables us to propose the relaxed- OT method using a faster algorithm. This approach has demonstrated its effectiveness for applications. However, it remains slow. As a superior alternative, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm for a convex semi-relaxed OT. Specifically, we prove their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Additionally, we develop two fast variants of the proposed BCFW. Numerical experiments have demonstrated that our proposed algorithms are effective for color transfer and surpass state-of-the-art algorithms. This report presents a short version of [1]. The source code is available at https://github.com/hiroyuki-kasai/srot.

For graph classification tasks, many traditional kernel methods focus on measuring the similarity between graphs. These methods have achieved great success on resolving graph isomorphism problems. However, in some classification problems, the graph class depends on not only the topological similarity of the whole graph, but also constituent subgraph patterns. To this end, we propose a novel graph embedding method using a multi-layer adjacent point merging model. This embedding method allows us to extract different sub-graph patterns from train-data. Then we present a flexible loss function for feature selection which enhances the robustness of our method for different classification problems. Finally, numerical evaluations demonstrate that our proposed method outperforms many state-of-the-art methods.

For graph learning tasks, many existing methods utilize a message-passing mechanism where vertex features are updated iteratively by aggregation of neighbor information. This strategy provides an efficient means for graph features extraction, but obtained features after many iterations might contain too much information from other vertices, and tend to be similar to each other. This makes their representations less expressive. Learning graphs using paths, on the other hand, can be less adversely affected by this problem because it does not involve all vertex neighbors. However, most of them can only compare paths with the same length, which might engender information loss. To resolve this difficulty, we propose a new Graph Kernel based on a Longest Common Subsequence (LCS) similarity. Moreover, we found that the widely-used R-convolution framework is unsuitable for path-based Graph Kernel because a huge number of comparisons between dissimilar paths might deteriorate graph distances calculation. Therefore, we propose a novel metric space by exploiting the proposed LCS-based similarity, and compute a new Wasserstein-based graph distance in this metric space, which emphasizes more the comparison between similar paths. Furthermore, to reduce the computational cost, we propose an adjacent point merging operation to sparsify point clouds in the metric space.

Network embedding is intended to produce low-dimensional vector representations of nodes in a network to preserve and extract the latent network structure, which has higher robustness to noise, outliers, and redundant data. Although a recently proposed multi-level nonnegative matrix factorization (NMF)-based approach has exhibited superior performance on network analysis, it is adversely affected by performance degradation because of discarded negative residual and redundant base selection throughout sequential multiple factorization processes. To alleviate this shortcoming, this paper presents a proposal of a sequential semi-orthogonal NMF with negative residual reduction for the network embedding (SSO-NRR-NMF). The proposed approach reduces the negative residuals to be discarded, and avoids redundant bases with a semi-orthogonal constraint. Numerical evaluations conducted using several real-world datasets demonstrate the effectiveness of the proposed SSO-NRR-NMF.

Analysis of multi-view data has recently garnered growing attention because multi-view data frequently appear in real-world applications, which are collected or taken from many sources or captured using various sensors. A simple and popular promising approach is to learn a latent subspace shared by multi-view data. Nevertheless, because one sample lies in heterogeneous structure types, many existing multi-view data analyses show that discrepancies in within-class data across multiple views have a larger value than discrepancies within the same view from different views. To evaluate this discrepancy, this paper presents a proposal of a multi-view Wasserstein discriminant analysis, designated as MvWDA, which exploits a recently developed optimal transport theory. Numerical evaluations using three real-world datasets reveal the effectiveness of the proposed MvWDA.

Efficient analysis of multiple sequential data is becoming necessary for identifying sequential patterns of multiple objects of interest. This analysis has major practical and technical importance because finding such patterns necessitates extraction and discovery of latent but meaningful groups of sequences from apparently extraneous but mutually interrelated multiple sequences. However, conventional sequential data analysis methods have not specifically examined this particular technical direction. To tackle this challenge, we propose a new model designated as overlapped state hidden semi-Markov model (OS-HSMM). The model represents the lengths of intervals and overlap among multiple events that are semantically interpretable and appearing across multiple sequences. The salient contribution is that OS-HSMM represents the overlap of two states by extending the state duration probability in HSMM to allow a negative value. Consequently, it handles the state interval and the state overlap simultaneously. Results of our evaluations underscore the effectiveness of our model.

This paper presents a proposal of a faster Wasser-stein k-means algorithm for histogram data by reducing Wasser-stein distance computations and exploiting sparse simplex projection. We shrink data samples, centroids, and the ground cost matrix, which leads to considerable reduction of the computations used to solve optimal transport problems without loss of clustering quality. Furthermore, we dynamically reduced the computational complexity by removing lower-valued data samples and harnessing sparse simplex projection while keeping the degradation of clustering quality lower. We designate this proposed algorithm as sparse simplex projection based Wasserstein k-means, or SSPW k-means. Numerical evaluations conducted with comparison to results obtained using Wasserstein k-means algorithm demonstrate the effectiveness of the proposed SSPW k-means for real-world datasets.

Adaptive stochastic gradient algorithms in the Euclidean space have attracted much attention lately. Such explorations on Riemannian manifolds, on the other hand, are relatively new, limited, and challenging. This is because of the intrinsic non-linear structure of the underlying manifold and the absence of a canonical coordinate system. In machine learning applications, however, most manifolds of interest are represented as matrices with notions of row and column subspaces. In addition, the implicit manifold-related constraints may also lie on such subspaces. For example, the Grassmann manifold is the set of column subspaces. To this end, such a rich structure should not be lost by transforming matrices to just a stack of vectors while developing optimization algorithms on manifolds. We propose novel stochastic gradient algorithms for problems on Riemannian matrix manifolds by adapting the row and column subspaces of gradients. Our algorithms are provably convergent and they achieve the convergence rate of order $O(log(T)/sqrt(T))$, where $T$ is the number of iterations. Our experiments illustrate that the proposed algorithms outperform existing Riemannian adaptive stochastic algorithms.

Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite number of loss functions. The present paper proposes a Riemannian stochastic quasi-Newton algorithm with variance reduction (R-SQN-VR). The key challenges of averaging, adding, and subtracting multiple gradients are addressed with notions of retraction and vector transport. We present convergence analyses of R-SQN-VR on both non-convex and retraction-convex functions under retraction and vector transport operators. The proposed algorithm is evaluated on the Karcher mean computation on the symmetric positive-definite manifold and the low-rank matrix completion on the Grassmann manifold. In all cases, the proposed algorithm outperforms the state-of-the-art Riemannian batch and stochastic gradient algorithms.

Nonnegative matrix factorization (NMF), a dimensionality reduction and factor analysis method, is a special case in which factor matrices have low-rank nonnegative constraints. Considering the stochastic learning in NMF, we specifically address the multiplicative update (MU) rule, which is the most popular, but which has slow convergence property. This present paper introduces on the stochastic MU rule a variance-reduced technique of stochastic gradient. Numerical comparisons suggest that our proposed algorithms robustly outperform state-of-the-art algorithms across different synthetic and real-world datasets.

We consider an inexact variant of the popular Riemannian trust-region algorithm for structured big-data minimization problems. The proposed algorithm approximates the gradient and the Hessian in addition to the solution of a trust-region sub-problem. Addressing large-scale finite-sum problems, we specifically propose sub-sampled algorithms with a fixed bound on sub-sampled Hessian and gradient sizes, where the gradient and Hessian are computed by a random sampling technique. Numerical evaluations demonstrate that the proposed algorithms outperform state-of-the-art Riemannian deterministic and stochastic gradient algorithms across different applications.

We propose an online tensor subspace tracking algorithm based on the CP decomposition exploiting the recursive least squares (RLS), dubbed OnLine Low-rank Subspace tracking by TEnsor CP Decomposition (OLSTEC). Numerical evaluations show that the proposed OLSTEC algorithm gives faster convergence per iteration comparing with the state-of-the-art online algorithms.

We propose a novel Riemannian manifold preconditioning approach for the tensor completion problem with rank constraint. A novel Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry that exists in Tucker decomposition. The specific metric allows to use the versatile framework of Riemannian optimization on quotient manifolds to develop preconditioned nonlinear conjugate gradient and stochastic gradient descent algorithms in batch and online setups, respectively. Concrete matrix representations of various optimization-related ingredients are listed. Numerical comparisons suggest that our proposed algorithms robustly outperform state-of-the-art algorithms across different synthetic and real-world datasets.

This paper addresses network anomography, that is, the problem of inferring network-level anomalies from indirect link measurements. This problem is cast as a low-rank subspace tracking problem for normal flows under incomplete observations and an outlier detection problem for abnormal flows. Since traffic data is large-scale time-structured data accompanied with noise and outliers under partial observations, an efficient modeling method is essential. To this end, this paper proposes an online subspace tracking of a Hankelized time-structured traffic tensor for normal flows based on the Candecomp/PARAFAC decomposition exploiting the recursive least squares algorithm. We estimate abnormal flows as outlier sparse flows via sparsity maximization in the underlying under-constrained linear-inverse problem. A major advantage is that our algorithm estimates normal flows by low-dimensional matrices with time-directional features as well as the spatial correlation of multiple links without using the past observed measurements and the past model parameters. Extensive numerical evaluations show that the proposed algorithm achieves faster convergence per iteration of model approximation and better volume anomaly detection performance compared to state-of-the-art algorithms.

Analysis of sequential event data has been recognized as one of the essential tools in data modeling and analysis field. In this paper, after the examination of its technical requirements and issues to model complex but practical situation, we propose a new sequential data model, dubbed Duration and Interval Hidden Markov Model (DI-HMM), that efficiently represents “state duration” and “state interval” of data events. This has significant implications to play an important role in representing practical time-series sequential data. This eventually provides an efficient and flexible sequential data retrieval. Numerical experiments on synthetic and real data demonstrate the efficiency and accuracy of the proposed DI-HMM.

This paper discusses a new paradigm of network service and in-network resource control: relational metric based control. The relational metrics indicate the closeness relationship between objects in the real world, and these objects could be people, locations, things, and content. Closeness is measured by using a fusion of online and physical sensing. We will describe the system model and discuss possible service applications of this technology.

It can be essential in the new-generation content services to predict the potential demands of people, which they themselves have not recognized or cannot express precisely. Social graphs representing the relationships between people are used for predicting demand in current Internet-based services. However, these graphs cannot represent the relationships of two users residing in common communities or common places. We propose representing not only a person but also things like communities and social events together as a single node in a social graph. This representation allows us to estimate who shares potential interests with a given person. We evaluated the estimation accuracy of our representation using an actual relational dataset from an academic database. Results show that our representation can estimate if two people share common interests that cannot be found with conventional methods that only use human nodes for estimation, and it can estimate the relations without using human nodes.

It is well-known that TCP has difficulty in achieving desirable levels of performance in multi-hop ad hoc networks. TCP implements a loss-based congestion control mechanism for adjusting traffic in the networks. However, when TCP reacts to a loss event in a multi-hop ad hoc network, contentions raised in the IEEE 802.11 MAC layer among nodes usually becomes excessive. This problem eventually induces packets scheduling variation at the MAC layer. As a result, the quality of service (QoS) assurances given to multimedia traffic streams, such as UDP traffic, are violated. This paper focuses on preventing the TCP congestion window (CWND) size at the network layer from becoming excessive. We propose an interference drop scheme (IDS) at the network layer to prevent excessive increases in MAC contention by dropping over-delayed packets held by local queues. Simulations show that the proposed approach yields better a TCP performance and the assurance of QoS provision to UDP flows in multi-hop ad hoc networks.

The passive optical network (PON) shares feeder transmission facilities to provide broadband services economically. To enhance PON survivability, ITU-T Rec. G.983.5 defines some protection switching methods. These methods, however, always bring about signal loss when switching is performed. Another related problem occurs when the network operator replaces one optical fiber cable with another that takes a different route due to construction activities like social infrastructure renewal. If hitless switching is available, the operator can carry out that activity anytime without impacting users, and can also offer higher-grade broadband services. Thus a hitless protection technology for PON systems is very attractive and useful. This paper proposes hitless switching schemes for protected PON systems based on the PON's ranging functionalities. We also present a specific design example for GE-PON.

A light-weight, smooth, and quick-responsible accessibility to contents are truly needed for a practical usage of the mobile video services. We research on and develop a new innovative mobile video technology, which utilizes pre-download, pre-fetching and asynchronous network streaming schemes. This paper describes its innovative mechanisms, especially an asynchronous streaming technique and an asynchronous thumbnail data pre-fetching technique. Two prototype implementations of mobile video client are described in detail, and performance evaluations are given at the end of this paper.

As an appliance that achieves rate reduction of MPEG-2 multi-program transport streams, MPEG-2 multi-program transport stream trans coder has been proposed. This transcoder needs to multiplex packets without any STD buffer failure. However, no efficient packet-multiplexing scheme has been reported until now. In this paper, we propose packet-multiplexing scheme that no STD buffer failure occurs in MPEG-2 multi-program transport stream transcoder. This proposed scheme is implemented by the following ways: 1) PSI packets are output in constant interval, 2) audio packets are output in the same PCR as that of input transport stream, 3) video packets are output so that the intervals of each output packet for every video elementary stream should be constant. From simulation experiments, we show the status of STD buffer and show the effectiveness for our proposed scheme.

Multimedia transcoding technology can provide interoperability between different types of audiovisual terminals and between terminals that connect to different networks. This paper describes a flexible multimedia transcoder that enables service interoperability between different types of terminals across heterogeneous networks.

In this paper, we propose a scalable video transmission system based on transcoding. First, we focus on the transcoder to reduce the bitrate of MPEG-2 bitstreams. We show that it is realized the layered coding by using the differential data between input and output of a transcoder. Next, we show the coding algorithm of this differential data. This algorithm can improve the coding efficiency by removing unnecessary code for differential data. By simulation experiments, we show that the proposed coding algorithm prevents the loss of coding efficiency in traditional hierachical coding, and show the effectiveness of proposed scheme.

MPEG-2 Multi-program Transport stream (TS) achieves improvement of transmission efficiency by multiplexing several MPEG-2 streams. In this paper, we propose a transcoder which achieves rate reduction of MPEG-2 multi-program TS. For the purpose of realizing MPEG-2 multi-program TS transcoder, this transcoder requires a rate control method and re-multiplexing method: The former improves average SNR values in total of streams, and the latter achieves the evasion from failure of STD buffer. Next, from simulation experiments, we compare the conventional rate control methods to the proposed one. On the other hand, we show the state of STD buffer. Finally, we show the effectiveness for our proposed scheme.

In this paper, we focus on the video transcoder as a bit rate reducer in a network node and propose a rate control scheme for a low-delay MPEG-2 video transcoder. First, we summarize the requirements of a rate control algorithm for low-delay transcoding. Next, based on these requirements, we describe the proposed rate control scheme in detail. Then, we analyze the input and output buffer delay and calculate the total delay time of the proposed transcoder. Finally, we evaluate the proposed scheme from the simulation results of experiments on picture quality, transcoding delay time and GOP (group of pictures) structure information (N/M value) of the input bit stream. Consequently, we showed that the proposed scheme can provide the same picture quality as a traditional scheme and is independent of the GOP structure.

As the transform method of video bit stream to the required bit stream format, the video transcoder has been adopted in various applications. In this paper, we focus on a MPEG video transcoder that can reduce the required bit rate by using re-quantization in the DCT domain. Furthermore, we propose a rate control method for this MPEG video transcoder that takes into consideration the estimation of drift-error propagation. Next, from simulation experiments, we compare the proposed rate control method to the traditional rate control method in terms of complexity, required buffer size and picture quality.

800 Mbit/s digital transmission systems, using nonredundant three-level and four-level codes, have been studied as a means of providing an economically attractive digital transmission system. These systems have been designed to be compatible with a 60 MHz analog system in repeater spacing and repeater size, so as to be easily introduced into the existing network. These systems with 11 520 telephone channels, exceed the 60 MHz analog system in both capacity and economy. Due to repeater construction factors, it became clear that the three-level code is more suitable. This paper describes the design and performance of 800 Mbit/s digital transmission systems and repeaters.

Jitter suppression in a chain of baseband PCM repeaters is studied. It is shown that a scrambler is very effective for systematic jitter suppression and that beyond 5 stages little additional suppression results. The probability of mark in the scrambler output converges to 0.5, independently of that in the input PCM signal. Experimental results confirm the analysis and show the ability of the scrambler to reduce the systematic jitter. The timing information disappearance of PCM repeatered lines when the scrambler is applied is also discussed.