Block-Structured Optimization for Subgraph Detection in Interdependent Networks

• URL: http://arxiv.org/abs/2210.02702v1
• Date: Thu, 6 Oct 2022 06:37:39 GMT
• Title: Block-Structured Optimization for Subgraph Detection in Interdependent Networks
• Authors: Fei Jie, Chunpai Wang, Feng Chen, Lei Li, Xindong Wu
• Abstract summary: We design an effective, efficient, parallelizable algorithm, namely Block-structured Graph Gradient Projection (GBGP), to optimize a general non-linear function subject to graph constraints. We demonstrate how our framework can be applied to two very practical applications and conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm.
• Score: 29.342611925278643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a generalized framework for block-structured nonconvex optimization, which can be applied to structured subgraph detection in interdependent networks, such as multi-layer networks, temporal networks, networks of networks, and many others. Specifically, we design an effective, efficient, and parallelizable projection algorithm, namely Graph Block-structured Gradient Projection (GBGP), to optimize a general non-linear function subject to graph-structured constraints. We prove that our algorithm: 1) runs in nearly-linear time on the network size; 2) enjoys a theoretical approximation guarantee. Moreover, we demonstrate how our framework can be applied to two very practical applications and conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm.

Related papers

• Component-based Sketching for Deep ReLU Nets [55.404661149594375]
  We develop a sketching scheme based on deep net components for various tasks. We transform deep net training into a linear empirical risk minimization problem. We show that the proposed component-based sketching provides almost optimal rates in approximating saturated functions.
  arXiv  Detail & Related papers  (2024-09-21T15:30:43Z)
• SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization [24.55623897747344]
  Neural network pruning is a key technique towards engineering large yet scalable, interpretable, generalizable models. We show how many existing differentiable pruning techniques can be understood as non regularization for group sparse optimization. We propose SequentialAttention++, which advances state the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.
  arXiv  Detail & Related papers  (2024-02-27T21:42:18Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• Layer Collaboration in the Forward-Forward Algorithm [28.856139738073626]
  We study layer collaboration in the forward-forward algorithm. We show that the current version of the forward-forward algorithm is suboptimal when considering information flow in the network. We propose an improved version that supports layer collaboration to better utilize the network structure.
  arXiv  Detail & Related papers  (2023-05-21T08:12:54Z)
• Graph Reinforcement Learning for Network Control via Bi-Level Optimization [37.00510744883984]
  We argue that data-driven strategies can automate this process and learn efficient algorithms without compromising optimality. We present network control problems through the lens of reinforcement learning and propose a graph network-based framework to handle a broad class of problems.
  arXiv  Detail & Related papers  (2023-05-16T03:20:22Z)
• Automatic structural optimization of tree tensor networks [0.0]
  We propose a TTN algorithm that enables us to automatically optimize the network structure by local reconnections of isometries. We demonstrate that the entanglement structure embedded in the ground-state of the system can be efficiently visualized as a perfect binary tree in the optimized TTN.
  arXiv  Detail & Related papers  (2022-09-07T14:51:39Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
  Domain-adaptive hash learning has enjoyed considerable success in the computer vision community. We develop an unsupervised domain-adaptive hash learning method for networks, dubbed UDAH.
  arXiv  Detail & Related papers  (2021-08-20T12:09:38Z)
• Reframing Neural Networks: Deep Structure in Overcomplete Representations [41.84502123663809]
  We introduce deep frame approximation, a unifying framework for representation learning with structured overcomplete frames. We quantify structural differences with the deep frame potential, a data-independent measure of coherence linked to representation uniqueness and stability. This connection to the established theory of overcomplete representations suggests promising new directions for principled deep network architecture design.
  arXiv  Detail & Related papers  (2021-03-10T01:15:14Z)
• Joint Multi-Dimension Pruning via Numerical Gradient Update [120.59697866489668]
  We present joint multi-dimension pruning (abbreviated as JointPruning), an effective method of pruning a network on three crucial aspects: spatial, depth and channel simultaneously. We show that our method is optimized collaboratively across the three dimensions in a single end-to-end training and it is more efficient than the previous exhaustive methods.
  arXiv  Detail & Related papers  (2020-05-18T17:57:09Z)
• Progressive Graph Convolutional Networks for Semi-Supervised Node Classification [97.14064057840089]
  Graph convolutional networks have been successful in addressing graph-based tasks such as semi-supervised node classification. We propose a method to automatically build compact and task-specific graph convolutional networks.
  arXiv  Detail & Related papers  (2020-03-27T08:32:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.