TY - GEN
T1 - Sylvester Tensor Equation for Multi-Way Association
AU - Du, Boxin
AU - Liu, Lihui
AU - Tong, Hanghang
N1 - Funding Information:
9 CONCLUSION In this paper, we formulate the multi-way association problem as a convex optimization problem, and show that it can be solved optimally by a Sylvester tensor equation. We propose two fast algorithms to solve this Sylvester tensor equation, with a linear complexity w.r.t. the size of input networks. On top of that, we provide theoretical analysis on the sensitivity of the Sylvester tensor equation solution. Extensive empirical evaluations demonstrate (1) the effectiveness on a variety of multi-network mining tasks (e.g., multi-network alignment, multi-network node retrieval and high-order recommendation), and (2) the linear scalability of the proposed methods. 10 ACKNOWLEDGEMENT This work is supported by National Science Foundation under grant No. 1947135, and 2003924 by the NSF Program on Fairness in AI in collaboration with Amazon under award No. 1939725, by the United States Air Force and DARPA under contract number FA8750-17-C-0153 8, and IBM-ILLINOIS Center for Cognitive Computing Systems Research (C3SR) - a research collaboration as part of the IBM AI Horizons Network. The content of the information in this document does not necessarily reflect the position or the policy of the Government or Amazon, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. REFERENCES
Publisher Copyright:
© 2021 ACM.
PY - 2021/8/14
Y1 - 2021/8/14
N2 - 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.
AB - 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.
KW - graph mining
KW - multi-network mining
KW - multi-way association
KW - sylvester tensor equation
UR - http://www.scopus.com/inward/record.url?scp=85114951453&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85114951453&partnerID=8YFLogxK
U2 - 10.1145/3447548.3467336
DO - 10.1145/3447548.3467336
M3 - Conference contribution
AN - SCOPUS:85114951453
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 311
EP - 321
BT - KDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
PB - Association for Computing Machinery
T2 - 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021
Y2 - 14 August 2021 through 18 August 2021
ER -