The Sylvester equation offers a powerful and unifying primitive for a variety of important graph mining tasks, including network alignment, graph kernel, node similarity, subgraph matching, etc. A major bottleneck of Sylvester equation lies in its high computational complexity. Despite tremendous effort, state-of-the-art methods still require a complexity that is at least \em quadratic in the number of nodes of graphs, even with approximations. In this paper, we propose a family of Krylov subspace based algorithms (\fasten) to speed up and scale up the computation of Sylvester equation for graph mining. The key idea of the proposed methods is to project the original equivalent linear system onto a Kronecker Krylov subspace. We further exploit (1) the implicit representation of the solution matrix as well as the associated computation, and (2) the decomposition of the original Sylvester equation into a set of inter-correlated Sylvester equations of smaller size. The proposed algorithms bear two distinctive features. First, they provide the \em exact solutions without any approximation error. Second, they significantly reduce the time and space complexity for solving Sylvester equation, with two of the proposed algorithms having a \em linear complexity in both time and space. Experimental evaluations on a diverse set of real networks, demonstrate that our methods (1) are up to $10,000\times$ faster against Conjugate Gradient method, the best known competitor that outputs the exact solution, and (2) scale up to million-node graphs.
more »
« less
Sylvester Tensor Equation for Multi-Way Association
How can we identify the same or similar users from a collection of social network platforms (e.g., Facebook, Twitter, LinkedIn, etc.)? Which restaurant shall we recommend to a given user at the right time at the right location? Given a disease, which genes and drugs are most relevant? Multi-way association, which identifies strongly correlated node sets from multiple input networks, is the key to answering these questions. Despite its importance, very few multi-way association methods exist due to its high complexity. In this paper, we formulate multi-way association as a convex optimization problem, whose optimal solution can be obtained by a Sylvester tensor equation. Furthermore, we propose two fast algorithms to solve the Sylvester tensor equation, with a linear time and space complexity. We further provide theoretic analysis in terms of the sensitivity of the Sylvester tensor equation solution. Empirical evaluations demonstrate the efficacy of the proposed method.
more »
« less
- NSF-PAR ID:
- 10299100
- Date Published:
- Journal Name:
- KDD
- Page Range / eLocation ID:
- 311 to 321
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Multi-sourced networks naturally appear in many application domains, ranging from bioinformatics, social networks, neuroscience to management. Although state-of-the-art offers rich models and algorithms to find various patterns when input networks are given, it has largely remained nascent on how vulnerable the mining results are due to the adversarial attacks. In this paper, we address the problem of attacking multi-network mining through the way of deliberately perturbing the networks to alter the mining results. The key idea of the proposed method (ADMIRING) is effective influence functions on the Sylvester equation defined over the input networks, which plays a central and unifying role in various multi-network mining tasks. The proposed algorithms bear two main advantages, including (1) effectiveness, being able to accurately quantify the rate of change of the mining results in response to attacks; and (2) generality, being applicable to a variety of multi-network mining tasks ( e.g., graph kernel, network alignment, cross-network node similarity) with different attacking strategies (e.g., edge/node removal, attribute alteration).more » « less
-
Abstract In this article, the recently discovered phenomenon of delayed Hopf bifurcations (DHB) in reaction–diffusion partial differential equations (PDEs) is analysed in the cubic Complex Ginzburg–Landau equation, as an equation in its own right, with a slowly varying parameter. We begin by using the classical asymptotic methods of stationary phase and steepest descents on the linearized PDE to show that solutions, which have approached the attracting quasi-steady state (QSS) before the Hopf bifurcation remain near that state for long times after the instantaneous Hopf bifurcation and the QSS has become repelling. In the complex time plane, the phase function of the linearized PDE has a saddle point, and the Stokes and anti-Stokes lines are central to the asymptotics. The non-linear terms are treated by applying an iterative method to the mild form of the PDE given by perturbations about the linear particular solution. This tracks the closeness of solutions near the attracting and repelling QSS in the full, non-linear PDE. Next, we show that beyond a key Stokes line through the saddle there is a curve in the space-time plane along which the particular solution of the linear PDE ceases to be exponentially small, causing the solution of the non-linear PDE to diverge from the repelling QSS and exhibit large-amplitude oscillations. This curve is called the space–time buffer curve. The homogeneous solution also stops being exponentially small in a spatially dependent manner, as determined also by the initial data and time. Hence, a competition arises between these two solutions, as to which one ceases to be exponentially small first, and this competition governs spatial dependence of the DHB. We find four different cases of DHB, depending on the outcomes of the competition, and we quantify to leading order how these depend on the main system parameters, including the Hopf frequency, initial time, initial data, source terms, and diffusivity. Examples are presented for each case, with source terms that are a uni-modal function, a smooth step function, a spatially periodic function and an algebraically growing function. Also, rich spatio-temporal dynamics are observed in the post-DHB oscillations. Finally, it is shown that large-amplitude source terms can be designed so that solutions spend substantially longer times near the repelling QSS, and hence, region-specific control over the delayed onset of oscillations can be achieved.more » « less
-
Survival analysis aims at predicting time to event of interest along with its probability on longitudinal data. It is commonly used to make predictions for a single specific event of interest at a given time point. However, predicting the occurrence of multiple events simultaneously and dynamically is needed in many applications. An intuitive way to solve this problem is to simply apply the regular survival analysis method independently to each task at each time point. However, it often leads to a suboptimal solution since the underlying dependencies between tasks are ignored, which motivates us to analyze these tasks jointly to select common features shared across all tasks. In this paper, we formulate a temporal Multi-Task learning framework (MTMT) using tensor representation. More specifically, given a survival dataset and a sequence of time points, which are considered as the monitored time points, we model each task at each time point as a regular survival analysis problem and optimize them simultaneously. We demonstrate the performance of MTMT model on two real-world datasets. We show the superior performance of the MTMT model compared to several state-of-the-art models. We also provide the list of important features selected to demonstrate the interpretability of our model.more » « less
-
This paper combines two control design aspects for a class of infinite dimensional systems, and each of the designs aims at significantly reducing the implementation complexity and computational load. A functional observer, and its extension of an unknown input functional observer, aims to reconstruct a functional of the infinite dimensional state. The resulting compensator only requires the solution to an operator Sylvester equation plus one differential equation for each dimension of the control signal, as opposed to an infinite dimensional filter evolution equation and an associated operator Riccati equation for the filter operator covariance. When the functional to be estimated coincides with the expression of a full state feedback control signal, then the functional observer becomes the minimum order compensator. When the parabolic system admits a decomposition whereby the system is decomposed into a lower finite dimensional subspace comprising the unstable eigenspectrum and an infinite stable subspace, then the functional observer-based compensator design becomes the minimum order compensator for the finite dimensional subsystem. This approach dramatically reduces the computation for solving the ARE needed for the full state controller and the associated Sylvester equation needed for the functional observer. Numerical results for a parabolic PDE in one and two spatial dimensions are included.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3447548.3467336
