[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3583780.3614898acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Graph Inference via the Energy-efficient Dynamic Precision Matrix Estimation with One-bit Data

Published: 21 October 2023 Publication History

Abstract

Graph knowledge discovery from graph-structured data is a fascinating data mining topic in various domains, especially in the Internet of Things, where inferring the graph structure from such informative data can benefit many downstream tasks. Deep neural networks are typically used to perform such predictions, but they produce unreliable results without sufficient high-quality data. Therefore, researchers introduce lightweight statistical precision matrix learning to infer the graph structure in many IoT scenarios with limited communication and resolution of sensors. However, these methods still suffer from low-resolution data or the omission of hidden information in time-series data. To address the challenges, we propose a novel approach for Energy-efficient Dynamic Sparse Graph Structure Estimation with one-bit data, EDGE. Our method proposes a novel estimator to estimate the covariance matrix from one-bit data, and then utilize the covariance matrices to capture the dynamic structure. We theoretically demonstrate the effectiveness of the estimators by deriving two non-asymptotic estimation error bounds for the estimated covariance matrix and precision matrix, respectively. The theoretical results show that our method can achieve a consistent result of the precision matrix at the rate O(log p/n). On multiple synthetic and real-world datasets, the experimental results demonstrate that our proposed estimator is able to obtain a relatively high detection rate using one-bit data, which exceeds the baseline by 35%, and identify potentially perturbed nodes in real-time dynamic network inference.

References

[1]
Amr Ahmed and Eric P Xing. 2009. Recovering time-varying networks of dependencies in social and biological studies. Proceedings of the National Academy of Sciences, Vol. 106, 29 (2009), 11878--11883.
[2]
Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, Vol. 29 (2015), 626--688.
[3]
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, Vol. 3, 1 (2011), 1--122.
[4]
Tony Cai, Weidong Liu, and Xi Luo. 2011. A constrained $ell$ 1 minimization approach to sparse precision matrix estimation. J. Amer. Statist. Assoc., Vol. 106, 494 (2011), 594--607.
[5]
Federico Castanedo. 2013. A review of data fusion techniques. The scientific world journal, Vol. 2013 (2013).
[6]
Eugene F Fama and Kenneth R French. 1993. Common risk factors in the returns on stocks and bonds. Journal of financial economics, Vol. 33, 1 (1993), 3--56.
[7]
Jianqing Fan, Yuan Liao, and Han Liu. 2016. An overview of the estimation of large covariance and precision matrices. The Econometrics Journal, Vol. 19, 1 (2016), C1--C32.
[8]
Salar Fattahi and Somayeh Sojoudi. 2019. Graphical lasso and thresholding: Equivalence and closed-form solutions. Journal of machine learning research (2019).
[9]
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. 2008. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, Vol. 9, 3 (2008), 432--441.
[10]
Alexandre Grothendieck and A Grothendieck. 1955. Produits tensoriels topologiques et espaces nucléaires. Vol. 16. American Mathematical Society Providence.
[11]
Jian Guo, Elizaveta Levina, George Michailidis, and Ji Zhu. 2011. Joint estimation of multiple graphical models. Biometrika, Vol. 98, 1 (2011), 1--15.
[12]
David Hallac, Youngsuk Park, Stephen Boyd, and Jure Leskovec. 2017. Network inference via the time-varying graphical lasso. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 205--213.
[13]
Chansu Han, Jumpei Shimamura, Takeshi Takahashi, Daisuke Inoue, Jun'ichi Takeuchi, and Koji Nakao. 2020. Real-time detection of global cyberthreat based on darknet by estimating anomalous synchronization using graphical lasso. IEICE TRANSACTIONS on Information and Systems, Vol. 103, 10 (2020), 2113--2124.
[14]
Tsuyoshi Idé, Aurelie C Lozano, Naoki Abe, and Yan Liu. 2009. Proximity-based anomaly detection using sparse structure learning. In Proceedings of the 2009 SIAM international conference on data mining. SIAM, 97--108.
[15]
Taehyoun Kim. 2019. Flutter prediction methodology based on dynamic eigen decomposition and frequency-domain stability. Journal of Fluids and Structures, Vol. 86 (2019), 354--367.
[16]
Shancang Li, Li Da Xu, and Shanshan Zhao. 2015. The internet of things: a survey. Information systems frontiers, Vol. 17 (2015), 243--259.
[17]
Leslie Liu, Randy Moulic, and Dennis Shea. 2010. Cloud service portal for mobile device management. In 2010 IEEE 7th International Conference on E-Business Engineering. IEEE, 474--478.
[18]
Rahul Mazumder and Trevor Hastie. 2012. Exact covariance thresholding into connected components for large-scale graphical lasso. The Journal of Machine Learning Research, Vol. 13, 1 (2012), 781--794.
[19]
Nicolai Meinshausen and Peter Bühlmann. 2006. High-dimensional graphs and variable selection with the lasso. (2006).
[20]
Jeferson Menegazzo and Aldo von Wangenheim. 2020. Multi-contextual and multi-aspect analysis for road surface type classification through inertial sensors and deep learning. In 2020 X Brazilian Symposium on Computing Systems Engineering (SBESC). IEEE, 1--8.
[21]
Ricardo Pio Monti, Peter Hellyer, David Sharp, Robert Leech, Christoforos Anagnostopoulos, and Giovanni Montana. 2014. Estimating time-varying brain connectivity networks from functional MRI time series. NeuroImage, Vol. 103 (2014), 427--443.
[22]
Seth Myers and Jure Leskovec. 2010. On the convexity of latent social network inference. Advances in neural information processing systems, Vol. 23 (2010).
[23]
Ali Namaki, Amir H Shirazi, R Raei, and GR Jafari. 2011. Network analysis of a financial market based on genuine correlation and threshold method. Physica A: Statistical Mechanics and its Applications, Vol. 390, 21--22 (2011), 3835--3841.
[24]
Caleb C Noble and Diane J Cook. 2003. Graph-based anomaly detection. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 631--636.
[25]
Saif Ur Rehman, Asmat Ullah Khan, and Simon Fong. 2012. Graph mining: A survey of graph mining techniques. In Seventh International Conference on Digital Information Management (ICDIM 2012). IEEE, 88--92.
[26]
Giulia Rinaldi, Florian Adamsky, Ridha Soua, Andrea Baiocchi, and Thomas Engel. 2019. Softwarization of SCADA: lightweight statistical SDN-agents for anomaly detection. In 2019 10th International Conference on Networks of the Future (NoF). IEEE, 102--109.
[27]
Somayeh Sojoudi. 2016. Equivalence of graphical lasso and thresholding for sparse graphs. The Journal of Machine Learning Research, Vol. 17, 1 (2016), 3943--3963.
[28]
Olaf Sporns. 2003. Graph theory methods for the analysis of neural connectivity patterns. Neuroscience databases: A practical guide (2003), 171--185.
[29]
Huong Thu Truong, Bac Phuong Ta, Quang Anh Le, Dan Minh Nguyen, Cong Thanh Le, Hoang Xuan Nguyen, Ha Thu Do, Hung Tai Nguyen, and Kim Phuc Tran. 2022. Light-weight federated learning-based anomaly detection for time-series data in industrial control systems. Computers in Industry, Vol. 140 (2022), 103692.
[30]
Beilun Wang, Ji Gao, and Yanjun Qi. 2017a. A fast and scalable joint estimator for learning multiple related sparse gaussian graphical models. In Artificial Intelligence and Statistics. PMLR, 1168--1177.
[31]
Beilun Wang, Arshdeep Sekhon, and Yanjun Qi. 2018. A fast and scalable joint estimator for integrating additional knowledge in learning multiple related sparse Gaussian graphical models. In International Conference on Machine Learning. PMLR, 5161--5170.
[32]
Beilun Wang, Ritambhara Singh, and Yanjun Qi. 2017b. A constrained $ell$ 1 minimization approach for estimating multiple sparse Gaussian or nonparanormal graphical models. Machine Learning, Vol. 106 (2017), 1381--1417.
[33]
Beilun Wang, Jiaqi Zhang, Haoqing Xu, and Te Tao. 2022. Fast and scalable learning of sparse changes in high-dimensional graphical model structure. Neurocomputing, Vol. 514 (2022), 39--57.
[34]
Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. 2019. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM). IEEE, 598--607.
[35]
Takashi Washio and Hiroshi Motoda. 2003. State of the art of graph-based data mining. Acm Sigkdd Explorations Newsletter, Vol. 5, 1 (2003), 59--68.
[36]
Jiaqi Zhang, Meng Wang, Qinchi Li, Sen Wang, Xiaojun Chang, and Beilun Wang. 2020. Quadratic Sparse Gaussian Graphical Model Estimation Method for Massive Variables. In IJCAI. 2964--2972.
[37]
Hongchao Zhou, Xiaohong Guan, and Chengjie Wu. 2008. Reliable transport with memory consideration in wireless sensor networks. In 2008 IEEE International Conference on Communications. IEEE, 2819--2824.

Index Terms

  1. Graph Inference via the Energy-efficient Dynamic Precision Matrix Estimation with One-bit Data

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge Management
      October 2023
      5508 pages
      ISBN:9798400701245
      DOI:10.1145/3583780
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 21 October 2023

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. anomaly detection
      2. internet of things
      3. low-quality data
      4. structure learning

      Qualifiers

      • Research-article

      Funding Sources

      • National Key Research and Development Program of China
      • Natural Science Foundation of Jiangsu Province
      • National Natural Science Foundation of China

      Conference

      CIKM '23
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

      Upcoming Conference

      CIKM '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 0
        Total Citations
      • 109
        Total Downloads
      • Downloads (Last 12 months)56
      • Downloads (Last 6 weeks)2
      Reflects downloads up to 13 Dec 2024

      Other Metrics

      Citations

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media