Search

Networks are an adequate representation for modeling and analyzing a great variety of complex systems. However, understanding networks with millions of nodes and billions of connections can be pretty challenging due to memory and time constraints. Therefore, selecting the relevant nodes and edges of these large-scale networks while preserving their core information is a major issue. In most cases, the so-called backbone extraction methods are based either on coarse-graining or filtering approaches. Coarse-graining techniques reduce the network size by gathering similar nodes into super-nodes, while filter-based methods eliminate nodes or edges according to a statistical property.In this work, a filter-based method is proposed and investigated. It uses the overlapping community structure to build the backbone in weighted networks. While most filtering techniques rely on link features to extract the backbone, the proposed method exploits both nodes and links. It takes advantage of the network communities through their main features (overlapping nodes, hubs, and bridging connections) to select influential edges and nodes while preserving the ability of the information dissemination of the original network. The so-called "Modular filtering backbone" combines two components. The first one is the network connecting the overlapping nodes and the top connected nodes (also called the hubs).One discards the edges with the lowest weights as long as connected components are maintained. The second component uses the network of the inter-community links with the nodes at their extremities. The disparity filter algorithm allows preserving only its most crucial connections. An extensive investigation is performed on a set of real-world weighted networks of various sizes and a wide range of origin. Results show the advantage of the proposed method over alternative filtering-based methods used for comparative purposes. Furthermore, this sheds new light on the most relevant parts of empirical networks hidden by their complexity. [ABSTRACT FROM AUTHOR]

In graph representation learning, Graph Convolutional Networks (GCNs) and their variants have received much attention. However, GCNs encounter oversmoothing as the models get deeper, limiting their ability to aggregate node representations within high-order neighborhood. Inspired by the modular structure of the brain network, we propose Modularity-based Siamese Simple Graph Convolution (MS-SGC), a Siamese network architecture that incorporates the characteristics of brain modular structure into graph convolutional networks. Spectral clustering is leveraged to detect the modular structure in the graph, and then the weight of cross edges between modules is lowered. Siamese network is adopted to combine the modularity-preserved graph representation with the original graph representation, improving classification performance and reducing oversmoothing. Furthermore, a graph convolution method that functions as a linear low-pass graph filter is elaborated through spectral analysis to preserve the similarity of nodes within the same module and further alleviate the oversmoothing problem. We validate the effectiveness of MS-SGC on citation networks and extend our experimental analysis to various downstream tasks. Extensive experiments demonstrate that MS-SGC outperforms state-of-the-arts while reducing the time and computation complexity for node classification. Moreover, MS-SGC achieves competitive performance compared to other state-of-the-arts in node clustering, community prediction and text classification tasks. • Low-pass filtered features can alleviate oversmoothing. • Nodes in the graphs have similar characteristics as brain modules. • The nonlinearity is not necessary in graph convolutional networks. • Preservation of modular structure alleviates oversmoothing and improves accuracy. [ABSTRACT FROM AUTHOR]