Search

The task of multi-label image recognition is to predict a set of object labels that present in an image. As objects normally co-occur in an image, it is desirable to model label dependencies to improve recognition performance. To capture and explore such important information, we propose Graph Convolutional Networks based models for multi-label recognition, where directed graphs are constructed over classes and information is propagated between classes to learn inter-dependent class-level representations. Following this idea, we design two particular models that approach multi-label classification from different views. In our first model, the prior knowledge about the class dependencies is integrated into classifier learning. Specifically, we propose Classifier-Learning-GCN to map class-level semantic representations (\eg, word embedding) into classifiers that maintain the inter-class topology. In our second model, we decompose the visual representation of an image into a set of label-aware features and propose Prediction-Learning-GCN to encode such features into inter-dependent image-level prediction scores. Furthermore, we also present an effective correlation matrix construction approach to capture inter-class relationships and consequently guide information propagation among classes. Empirical results on generic multi-label recognition demonstrate that the effectiveness of both two proposed models. Moreover, the proposed methods also show advantages in other multi-label related applications.

Differential privacy (DP) has become the de facto standard of privacy protection. For graphs, there are two widely used definitions of differential privacy, namely, edge differential privacy (edge-DP) and node differential privacy (node-DP), and node-DP is preferred when the minimal unit of interest is a node. To preserve node-DP, one can develop different methods to answer each specific graph query, or develop a graph publishing method to answer all graph queries. However, no existing works worked on such graph publishing methods. In this work, we propose two methods for publishing graphs under node-DP. One is the node-level perturbation algorithm which modifies the input graph by randomly inserting and removing nodes. The other one is the edge-level perturbation algorithm which randomly removing edges and inserting nodes. Both methods can achieve a flexible privacy guarantee by adjusting the running parameters. We conduct extensive experiments on both real-world and synthetic graphs to show the effectiveness and efficiency of proposed algorithms.

Temporal point process is widely used for sequential data modeling. In this paper, we focus on the problem of modeling sequential event propagation in graph, such as retweeting by social network users, news transmitting between websites, etc. Given a collection of event propagation sequences, conventional point process model consider only the event history, i.e. embed event history into a vector, not the latent graph structure. We propose a Graph Biased Temporal Point Process (GBTPP) leveraging the structural information from graph representation learning, where the direct influence between nodes and indirect influence from event history is modeled respectively. Moreover, the learned node embedding vector is also integrated into the embedded event history as side information. Experiments on a synthetic dataset and two real-world datasets show the efficacy of our model compared to conventional methods and state-of-the-art., Comment: 9 pages, 6 figures, 2 tables

Influential community search aims to find cohesive subgraphs (communities) with considerable influence. It is a fundamental graph management operator that can play a crucial role in biological network analysis, activity organization, and other real-life applications. Existing research on influential community search is mainly focused on deterministic graphs with the assumption that influences between entities are certain. This assumption is invalid in many cases because it ignores the uncertainty which is an inherent property of influence. Against this backdrop, in this paper, we introduce an uncertain influential community model, namely (k,)-influential community, based on which the influential community search problem over uncertain graphs is formulated. Furthermore, we propose an online approach by integrating a peeling-pruning strategy that can progressively refine the given uncertain graph to find the (k,)-influential communities. To further improve the search performance, two novel indexes, ICU-Index and FICU-Index, are developed to organize the (k,)-influential communities at different probabilistic intervals. The indexes decompose the probabilistic interval into multiple subintervals and based on this, the (k,)-influential communities are divided into different groups in turn. Compared with ICU-Index, FICU-Index requires considerably less space with the introduction of two optimization strategies.

In this paper, we propose and analyze SPARQ-SGD, an event-triggered and compressed algorithm for decentralized training of large-scale machine learning models over a graph. Each node can locally compute a condition (event) which triggers a communication where quantized and sparsified local model parameters are sent. In SPARQ-SGD, each node first takes a fixed number of local gradient steps and then checks if the model parameters have significantly changed compared to its last update; it communicates further compressed model parameters only when there is a significant change, as specified by a (design) criterion. We prove that SPARQ-SGD converges as $O\left( {\frac{1}{{nT}}} \right)$ and $O\left( {\frac{1}{{\sqrt {nT} }}} \right)$ in the strongly-convex and non-convex settings, respectively, demonstrating that aggressive compression, including event-triggered communication, model sparsification and quantization does not affect the overall convergence rate compared to uncompressed decentralized training; thereby theoretically yielding communication efficiency for ‘free’. We evaluate SPARQ-SGD over real datasets to demonstrate significant savings in communication bits over the state-of-the-art.

International audience; Gradient methods subject images to a series of operations to enhance some characteristics and facilitate image analysis, usually the contours of large objects. We argue that a gradient must show other characteristics, such as minor components and large uniform regions, particularly for the image segmentation task where subjective concepts such as region coherence and similarity are hard to interpret from the pixel information. This work extends the formalism of a previously proposed graph-based image gradient method that uses edge-weighted graphs aggregated with Random Forest (RF) to create descriptive gradients. We aim to explore more extensive input image areas and make changes driven by the RF mechanics. We evaluated the proposals on the edge and segmentation tasks, analyzing the gradient characteristics that most impacted the final segmentation. The experiments indicated that sharp thick contours are crucial, whereas fuzzy maps yielded the worst results even when created from deep methods with more precise edge maps. Also, we analyzed how uniform regions and small details impacted the final segmentation. Statistical analysis on the segmentation task demonstrated that the gradients created by the proposed are significantly better than most of the best edge maps methods and validated our original choices of attributes.

In 1943, Hadwiger conjectured that every graph with no K t + 1 minor is t-colorable for every t ≥ 0 . While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980 s, Kostochka and Thomason independently proved that every graph with no K t minor has average degree O ( t log ⁡ t ) and thus is O ( t log ⁡ t ) -list-colorable. Recently, the authors and Song proved that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -colorable for every β > 1 4 . Here, we build on that result to show that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -list-colorable for every β > 1 4 . Our main new tool is an upper bound on the number of vertices in highly connected K t -minor-free graphs: We prove that for every β > 1 4 , every Ω ( t ( log ⁡ t ) β ) -connected graph with no K t minor has O ( t ( log ⁡ t ) 7 / 4 ) vertices.

Graph Mining has gained importance due to its wide range of applications. As graph mining is a form of data mining where data is depicted in the form of graphs. The data when represented in the form of graphs helps to model the real scenario and relationship well. Discovery of interesting pattern from real relationship is of utmost beneficial. Frequent Subgraph Mining (FSM) is a significant area of graph mining. We accompany our approach in the field of FSM by adding a graph sampling function. This sampling function takes the single graph and a sampling percentage as input and produces a sampled graph which is similar in properties with original graph. This sampled graph is then taken as input while implementing the GraMi framework. Our sampling approach successfully mines the subgraphs with lower frequency threshold thus significantly improving the efficiency of the original GraMi framework.

For a graph G and a set Z of four distinct vertices of G, a diamond on Z is a subgraph of G such that, for some labeling Z = { v 1 , v 2 , v 3 , v 4 } , there are three internally disjoint paths P 1 , P 2 , P 3 with end vertices v 1 , v 2 with v 3 , v 4 on P 1 , P 2 , respectively. Therefore, this yields a K 4 − -subdivision with branch vertices on Z. We characterize graphs G that contain no diamond on a prescribed set Z of four vertices, under the assumption that for every v ∈ Z there are three paths of G from v to Z − { v } , mutually disjoint except for v. Moreover, we can find two “different” such subdivisions, if one exists. Our proof is based on Mader's S-paths theorem.

International audience; The architecture of supercomputers is evolving to expose massive parallelism. MPI and OpenMP are widely used in application codes on the largest supercomputers in the world. The community primarily focused on composing MPI with OpenMP before its version 3.0 introduced task-based programming. Recent advances in OpenMP task model and its interoperability with MPI enabled fine model composition and seamless support for asynchrony. Yet, OpenMP tasking overheads limit the gain of task-based applications over their historical loop parallelization (parallel for construct).This paper identifies the OpenMP task dependency graph discovery speed as a limiting factor in the performance of task-based applications.We study its impact on intra and inter-node performances over two benchmarks (Cholesky, HPCG) and a proxy-application (LULESH). We evaluate the performance impacts of several discovery optimizations, and introduce a persistent task dependency graph reducing overheads by a factor upto 15 at run-time. We measure 2x speedup over parallel for versions weak scaled to 16K cores, due to improved cache memory use and communication overlap, enabled by task refinement and depth-first scheduling.

Dijkstra algoritam i Bellman-Ford algoritam su algoritmi koji se koriste za pronalaženje najkraćeg puta u težinskom grafu. Dijkstra algoritam djeluje na pozitivnim težinama bridova i koristi se za pronalaženje najkraćeg puta od jednog početnog vrha do svih ostalih vrhova u grafu. Bellman-Ford algoritam, s druge strane, može se koristiti čak i kada postoje negativne težine bridova, ali ima složenost vremena veću od Dijkstra algoritma. Ford-Fulkerson algoritam koristi se za pronalaženje maksimalnog mrežnog protoka, a temelji se na uvećavajućim putevima. Ovaj algoritam iterativno pronalazi uvećavajuće puteve i uvećava protok dok ne postigne maksimalni protok. Ovi algoritmi su važan alat za rješavanje različitih problema u području grafova i optimizacije., Dijkstra’s algorithm and Bellman-Ford algorithm are algorithms used to find the shortest path in a weighted graph. Dijkstra’s algorithm works with positive edge weights and is used to find the shortest path from a single source node to all other nodes in the graph. On the other hand, the Bellman-Ford algorithm can handle graphs with negative edge weights but has a higher time complexity compared to Dijkstra’s algorithm. The Ford-Fulkerson algorithm is used to find the maximum flow in a network and is based on augmenting paths. This algorithm iteratively finds augmenting paths and increases the flow until it reaches the maximum flow. All algorithms are important tools for solving various graph and optimization problems.

Informacijsko komunikacijska omrežja že nekaj časa rastejo in postajajo vse pomembnejša. Uporabljamo jih vsi in posegajo v vse pore sodobne družbe. S pomembnostjo in razvojem informacijsko komunikacijskih omrežij raste tudi odgovornost, ki je na strani tistih, kateri upravljajo z omrežji. Omrežja je potrebno dograjevati, jih nadzirati in učinkovito upravljati, da lahko uporabnikom zagotovijo kvalitetno in varno uporabniško izkušnjo. Zadnja leta opažamo pospešen razvoj orodij, ki lajšajo delo omrežnim inženirjem in zmanjšujejo vpliv človeškega faktorja. V magistrski nalogi obravnavamo načine avtomatizacije upravljanja in nadziranja omrežnih naprav. V nalogi so opisani različni omrežni protokoli in orodja za avtomatizacijo kot so NETCONF, RESTCONF, gRPC, Ansible, Chef in ostali. Poudarek je na načinu avtomatizacije z uporabo lastnih skript, napisanih v programskem jeziku Python in uporabi knjižnic Netmiko in NAPALM. Avtomatizacija v kontekstu IKT-omrežij predstavlja nadomestek človeške interakcije z omrežnimi napravami. Z avtomatizacijo se med sistemi izmenjujejo podatki, ki jih je potrebno obdelati, jih shraniti in jih interpretirati, da nam lahko podajo potrebne informacije. Zato sem v nalogi obravnaval možnosti hranjenja podatkov v relacijskih in nerelacijskih podatkovnih bazah in kritično vrednotil primernost obeh načinov pri avtomatizaciji. Poleg tega sem podrobno predstavil eno izmed orodij za učinkovito razčlenjevanje podatkov, to je Python knjižnica TextFSM. V nalogi je predstavljen primer, kako lahko več členov in orodij, ki skrbijo za različne funkcionalnosti, ki nam lajšajo delo z omrežij, združimo v celoto in jih povežemo v uporabnikom prijazno platformo. V primeru platforme gSmart, ki je opisana v magistrski nalogi, so za avtomatizacijo uporabljene lastne Python skripte, podatki se hranijo v graf bazi, upravljanje platforme pa je dogodkovno vodeno. Information and communication networks have been growing for some time now and are becoming increasingly important. We all use them, and they permeate every aspect of modern society. With the significance and development of information and communication networks, the responsibility of those who manage the networks also grows. Networks need to be expanded, monitored, and efficiently managed in order to provide users with a quality and secure user experience. In recent years, there has been accelerated development of tools that facilitate the work of network engineers and reduce the impact of the human factor. In my master's thesis, I address methods of automating the management and monitoring of network devices. The thesis describes various network protocols and automation tools such as NETCONF, RESTCONF, gRPC, Ansible, Chef, and others. The emphasis is on automation using custom scripts written in the Python programming language and the use of libraries such as Netmiko and NAPALM. Automation in the context of ICT networks represents a replacement for human interaction with network devices. Through automation, data is exchanged between systems, which needs to be processed, stored, and interpreted in order to provide us with the necessary information. Therefore, I explored the options for storing data in relational and non-relational databases and critically evaluated the suitability of both approaches for automation. Additionally, I provided a detailed presentation of one of the tools for effective data parsing, namely the Python library TextFSM. The thesis presents an example of how multiple components and tools that handle various functionalities, making our work with networks easier, can be integrated into a whole and connected to a user-friendly platform. In the case of the gSmart platform described in the master's thesis, custom Python scripts are used for automation, data is stored in a graph database, and the management of the platform is event-driven.

Problem najkraćeg puta modelira se pomoću grafova, a svodi se na traženje podgrafa s najmanjom težinom. Dijeli se na četiri varijante: najkraći put od jednog početnog vrha do svih ostalih, od svih ostalih do jednog odredišnog, između jednog para vrhova te između svih parova vrhova u grafu. Detaljno su objašnjeni algoritmi BFS, Dijkstrin i Bellman-Ford koji rješavaju prva dva navedena tipa problema, Floyd-Warshall i Johnson se primjenjuju kod četvrte varijante problema te A* koji pronalazi najkraći put kod trećeg navedenog tipa problema. Problem svoju primjenu nalazi u navigaciji kao što je to Google Maps, komunikacijskim sustavima, Internet usmjeravanju, društvenim mrežama i brojnim drugim. U sklopu rada implementirani su i uspoređeni Dijkstrin i A* algoritmi na jednostavnom navigacijskom programu. The shortest path problem is modeled using graphs, and is based on searching for the subgraph with the smallest weight. Four types of shortest path problem are: Single-Source Shortest-Path Problem, Single-Destination Shortest-Path Problem, Single-Pair Shortest-Path Problem and All-Pairs Shortest-Path Problem. The explained algorithms are BFS, Dijkstra and Bellman-Ford algorithms that solve the first two types of problems, Floyd-Warshall and Johnson used for the fourth variant of the problem, and A*, which finds the shortest path for the third type of problem. The problem finds its application in navigation such as Google Maps, communication systems, Internet routing, social networks and many others. As part of the work, Dijkstra's and A* algorithms were implemented and compared on a simple navigation program.

Let {\alpha} be a prime Hurwitz integer. H{\alpha}, which is the set of residual class with respect to related modulo function in the rings of Hurwitz integers, is a subset of H, which is the set of all Hurwitz integers. We consider left congruent module {\alpha} and, the domain of related modulo function in this study is ZN({\alpha}), which is residual class ring of ordinary integers with N({\alpha}) elements, which is the norm of prime Hurwitz integer {\alpha}. In this study, we present an algebraic construction technique, which is a modulo function formed depending on two modulo operations, for codes over Hurwitz integers. Thereby, we obtain the residue class rings of Hurwitz integers with N({\alpha}) size. In addition, we present some results for mathematical notations used in two modulo functions, and for the algebraic construction technique formed depending upon two modulo functions. Moreover, we present graphs obtained by graph layout methods, such as spring, high-dimensional, and spiral embedding, for the set of the residual class obtained with respect to the related modulo function in the rings of Hurwitz integers.

A graph G is said to be fractional ( a , b , k ) -critical covered if for any W ⊆ V ( G ) with | W | = k , G − W is fractional [ a , b ] -covered. In this article, we demonstrate that a graph G of order n is fractional ( a , b , k ) -critical covered if G satisfies δ ( G ) ≥ ( t − 1 ) ( a + 1 ) + k , n ≥ ( a + b ) ( t ( a + b ) − 2 ) + b k + 2 b , and | N G ( x 1 ) ∪ N G ( x 2 ) ∪ ⋯ ∪ N G ( x t ) | ≥ a n + b k + 2 a + b for any independent subset { x 1 , x 2 , … , x t } of G , which is an improvement and extension of Yuan and Hao’s previous result (Yuan and Hao, 2020).

Dockless E-scooter Sharing (DES) has become a popular means of last-mile commute for many smart cities. As e-scooters are getting deployed dynamically and exibly across city regions that expand and/or shrink, accurate prediction of the e-scooter distribution given the recongured regions becomes essential for city planning. We present GCScoot, a novel ow distribution prediction approach for reconguring urban DES systems. Based on real-world datasets with reconguration, we analyze e-scooter distribution features and ow dynamics for the data-driven designs. We propose a novel spatio-temporal graph capsule neural network within GCScoot to predict future dockless e-scooter ows given the recongured regions. GCScoot pre-processes historical spatial e-scooter distributions into ow graph structures, where discretized city regions are considered as nodes and inter-region ows as edges. To facilitate initial training, we cluster the regions and generate virtual data for new deployment regions based on their peers in the same cluster. Given above designs, the region-to-region correlations embedded within the temporal ow graphs are captured via the multi-graph capsule convolutional neural network which accurately predicts the DES ows. Extensive studies upon four e-scooter datasets (total >3.4 million rides) in four populous US cities have corroborated accuracy and effectiveness of GCScoot in predicting the e-scooter distributions.

Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of $k$ interval graphs, by splitting the graph in some special way. As a recent example of such an approach, the classes of $k$-thin and proper $k$-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. The complexity of the recognition of each of these classes is still open, even for fixed $k \geq 2$. In this work, we introduce a subclass of $k$-thin graphs (resp. proper $k$-thin graphs), called precedence $k$-thin graphs (resp. precedence proper $k$-thin graphs). Concerning partitioned precedence $k$-thin graphs, we present a polynomial time recognition algorithm based on $PQ$-trees. With respect to partitioned precedence proper $k$-thin graphs, we prove that the related recognition problem is \NP-complete for an arbitrary $k$ and polynomial-time solvable when $k$ is fixed. Moreover, we present a characterization for these classes based on threshold graphs., 33 pages

This paper is inspired by the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph.

Power of cycle graphs C n k have been extensively studied with respect to coloring problems, being both the vertex and the edge-coloring problems already solved in the class. The total coloring problem (of determining the minimum number of colors needed to color the vertices and the edges of a graph in a manner that no two adjacent elements are colored the same), however, is still open for power of cycle graphs. Actually, despite partial results for specific values of n and k , not even the well-known Total Coloring Conjecture is settled in the class. A remarkable conjecture by Campos and Mello of 2007 states that if C n k is neither a cycle nor a complete graph, then it has total chromatic number χ T = Δ + 2 if n is odd and n 3 ( k + 1 ) , and χ T = Δ + 1 otherwise. We provide strong evidences for this conjecture: we settle a dichotomy for all power of cycle graphs with respect to conformability (a well-known necessary condition for a graph to have χ T = Δ + 1 ) and we develop a framework which may be used to prove that, for any fixed k , the number of C n k graphs with χ T ≠ Δ + 1 is finite. Moreover, we prove this finiteness for any even k and for k ∈ { 3 , 5 , 7 } . We also use our composition technique to provide a proof of Campos and Mello’s conjecture for all C n k graphs with k ∈ { 3 , 4 } .

Graph Neural Networks (GNNs) are a popular approach for predicting graph structured data. As GNNs tightly entangle the input graph into the neural network structure, common explainable AI approaches are not applicable. To a large extent, GNNs have remained black-boxes for the user so far. In this paper, we show that GNNs can in fact be naturally explained using higher-order expansions, i.e. by identifying groups of edges that jointly contribute to the prediction. Practically, we find that such explanations can be extracted using a nested attribution scheme, where existing techniques such as layer-wise relevance propagation (LRP) can be applied at each step. The output is a collection of walks into the input graph that are relevant for the prediction. Our novel explanation method, which we denote by GNN-LRP, is applicable to a broad range of graph neural networks and lets us extract practically relevant insights on sentiment analysis of text data, structure-property relationships in quantum chemistry, and image classification., Comment: 14 pages + 6 pages supplement

Urban density is central to urban research and planning and can be defined in numer- ous ways. Most measures of urban density however are biased by arbitrary chosen spatial units at their denominator and ignore the relative location of elementary urban objects within those units. We solve these two problems by proposing a new graph-based density index which we apply to the case of buildings in Belgium. The method includes two main steps. First, a graph-based spatial descending hierarchical clustering (SDHC) delineates clusters of buildings with homogeneous inter-building distances. A Moran scatterplot and a maximum Cook’s distance are used to prune the minimum spanning tree at each iteration of the SDHC. Second, within each clus- ter, the ratio of the number of buildings to the sum of inter-building distances is cal- culated. This density of buildings is thus defined independently of the definition of any basic spatial unit and preserves the built-up topology, i.e. the relative position of buildings. The method is parsimonious in parameters and can easily be transferred to other punctual objects or extended to account for additional attributes.

The median of a graph consists of those vertices which minimize the average distance to all other vertices. It plays an important role in optimization scenarios like facility location problems. Sierpinski graphs are the state graphs of the Switching Tower of Hanoi problem, a variant of the Tower of Hanoi game. They also provide optimum models for interconnection networks. In this study, we present our observations on the median of Sierpinski graphs. We conjecture that the number of median vertices in S 3 n is always 12, if n ≥ 3 , and that they lie around the inner ring of the standard drawing.

Clustering graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be considered, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. Also, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets demonstrate the effectiveness and efficiency of our proposals. Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insights into the effectiveness and efficiency of our proposals.

Since real-world objects and their interactions are often multi-modal and multi-typed, heterogeneous networks have been widely used as a more powerful, realistic, and generic superclass of traditional homogeneous networks (graphs). Meanwhile, representation learning (\aka~embedding) has recently been intensively studied and shown effective for various network mining and analytical tasks. In this work, we aim to provide a unified framework to deeply summarize and evaluate existing research on heterogeneous network embedding (HNE), which includes but goes beyond a normal survey. Since there has already been a broad body of HNE algorithms, as the first contribution of this work, we provide a generic paradigm for the systematic categorization and analysis over the merits of various existing HNE algorithms. Moreover, existing HNE algorithms, though mostly claimed generic, are often evaluated on different datasets. Understandable due to the application favor of HNE, such indirect comparisons largely hinder the proper attribution of improved task performance towards effective data preprocessing and novel technical design, especially considering the various ways possible to construct a heterogeneous network from real-world application data. Therefore, as the second contribution, we create four benchmark datasets with various properties regarding scale, structure, attribute/label availability, and \etc.~from different sources, towards handy and fair evaluations of HNE algorithms. As the third contribution, we carefully refactor and amend the implementations and create friendly interfaces for 13 popular HNE algorithms, and provide all-around comparisons among them over multiple tasks and experimental settings., Accepted by IEEE TKDE. All code and data available at https://github.com/yangji9181/HNE

We introduce the notion of m -bonacci-sum graphs denoted by G m , n for positive integers m , n . The vertices of G m , n are 1 , 2 , … , n and any two vertices are adjacent if and only if their sum is an m -bonacci number. We show that G m , n is bipartite and for n ≥ 2 m − 2 , G m , n has exactly ( m − 1 ) components. We also find the values of n such that G m , n contains cycles as subgraphs. We use this graph to partition the set { 1 , 2 , … , n } into m − 1 subsets such that each subset is ordered in such a way that sum of any 2 consecutive terms is an m -bonacci number.

A radio k -labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that the absolute value of the difference between the labels of any two distinct vertices u and v is not less than k + 1 − d ( u , v ) , where d ( u , v ) denotes the distance between u and v . The radio k -labeling number of G is the minimum span of a radio k -labeling of G . For a given set of integers D = { d 1 , d 2 , … , d t } , the distance graph G ( Z , D ) , denoted also by D ( d 1 , d 2 , … , d t ) , has the set of integers Z as its vertex set, while two distinct vertices i , j ∈ Z are adjacent in G ( Z , D ) if and only if | i − j | ∈ D . Radio k -labelings of three families of distance graphs are considered. Some improved theoretical lower and upper bounds on the radio k -labeling number are presented and some computer-based methods for computing radio k -labelings of these families of graphs are proposed.

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben's strategy) is called the indicated chromatic number of $G$, denoted by $\chi_i(G)$. In this paper, we have shown that for any graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for all $k\geq\mathrm{col}(G)\mathrm{col}(H)$. Also, we have shown that for any graph $G$ and for some classes of graphs $H$ with $\chi(H)=\chi_i(H)=\ell$, $G[H]$ is $k$-indicated colorable if and only if $G[K_\ell]$ is $k$-indicated colorable. As a consequence of this result we have shown that for some particular families of graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for every $k\geq \chi(G[H])$. This serves as a partial answer to one of the questions raised by A. Grzesik in \cite{and}. In addition, if $G$ is a Bipartite graph or a $\{P_5,K_3\}$-free graph (or) a $\{P_5,Paw\}$-free graph and if $H$ is from the same families of graphs, then we have shown that $\chi_i(G[H])=\chi(G[H])$.

A subset D ⊆ V of a graph G = ( V , E ) is called a global total k -dominating set of G if D is a total k -dominating set of both G and G ¯ , the complement of G . The Minimum Global Total k - Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and the Decide Global Total k - Domination problem is the decision version of the Minimum Global Total k - Domination problem. The Decide Global Total k - Domination problem is known to be NP -complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k - Domination problem. We show the Decide Global Total k - Domination problem remains NP -complete for bipartite graphs and chordal graphs. We also show that Minimum Global Total k - Domination cannot be approximated within a factor of ( 1 − ϵ ) ln | V | for any ϵ > 0 unless P = NP for bipartite graphs as well as for chordal graphs. Next, we show that Minimum Global Total k - Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Total k - Domination problem is APX -complete for bounded degree graphs. We also show that Decide Global Total k - Domination problem is W[2] -hard for bipartite graphs and for chordal graphs when we choose the size of the GTkD-set as the parameter.

The nullity of a vertex-weighted graph is equal to the number of zero eigenvalues of its adjacency matrix. In this article, we give a linear time algorithm to calculate the nullity of vertex-weighted block graphs, i.e., graphs in which every block is a clique, with weights assigned to the vertices.

Large-scale graphs are widely used to model the entities and their complex relations. Uncertain graphs are adopted when the relations between entities contain some uncertainty. However, the inherent uncertainties, which are embedded underlying the data and structure of the graphs derived from various sources introduce difficulties on data analysis. To understand the underlying characteristics of large graphs, graph aggregation techniques are critical. However, the existing graph aggregation techniques are designed for deterministic graphs therefore are not applicable on uncertain graphs. In this paper, we provide the first attempt on addressing the aggregation problem on uncertain graphs. To deal with the computation complexity of the aggregation problem, we propose a heuristic-based aggregation algorithm for uncertain graphs and some optimization methods to improve its efficiency in real world implementation. Besides the optimization, to further speed up the process, we design a parallel aggregation implementation approach. The intensive evaluations on the two datasets, DBLP and Flickr, demonstrate that our proposed algorithms are able to produce high quality aggregation results within reasonable operation time and the parallel implementation accelerates the aggregation by up to 82 times compared with the baseline algorithm.

For a given graph $G$, the metric and edge metric dimensions of $G$, $\dim(G)$ and ${\rm edim}(G)$, are the cardinalities of the smallest possible subsets of vertices in $V(G)$ such that they uniquely identify the vertices and the edges of $G$, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph $G$ such that $\dim(G)=a$ and ${\rm edim}(G)=b$ for every pair of integers $a,b$, where $4\le b, Comment: 12 pages

Benefit from avoiding the utilization of labeled samples, which are usually insufficient in the real world, unsupervised learning has been regarded as a speedy and powerful strategy on clustering tasks. However, clustering directly from primal data sets leads to high computational cost, which limits its application on large-scale and high-dimensional problems. Recently, anchor-based theories are proposed to partly mitigate this problem and field naturally sparse affinity matrix, while it is still a challenge to get excellent performance along with high efficiency. To dispose of this issue, we first presented a fast semisupervised framework (FSSF) combined with a balanced K -means-based hierarchical K -means (BKHK) method and the bipartite graph theory. Thereafter, we proposed a fast self-supervised clustering method involved in this crucial semisupervised framework, in which all labels are inferred from a constructed bipartite graph with exactly k connected components. The proposed method remarkably accelerates the general semisupervised learning through the anchor and consists of four significant parts: 1) obtaining the anchor set as interim through BKHK algorithm; 2) constructing the bipartite graph; 3) solving the self-supervised problem to construct a typical probability model with FSSF; and 4) selecting the most representative points regarding anchors from BKHK as an interim and conducting label propagation. The experimental results on toy examples and benchmark data sets have demonstrated that the proposed method outperforms other approaches.

Universal and fault-tolerant quantum computation is a promising new paradigm that may efficiently conquer difficult computation tasks beyond the reach of classical computation. It motivates the development of various quantum technologies. The rapid progress of quantum technologies accelerates the realization of quantum computers. In this paper, we survey the recent advances in quantum technologies and quantum computation from the design automation perspective.

The issue of bipartite time-varying formation (BTVF) tracking for linear multiagent systems (MASs) with a leader of unknown input on signed digraphs is investigated. An adaptive nonsmooth protocol is taken in this article that utilizes only the local output feedback information among neighbors and, thus, can avoid employing the eigenvalue information of the Laplacian matrix of the graph. It is proven that if the interaction network of agents containing a spanning tree is structurally balanced, the BTVF tracking can be achieved with a leader of the bounded input via the proposed scheme. This leader-following BTVF includes two time-varying subformations, whose relationship is antagonistic. A convergence analysis of the proposed protocol for MASs is reflected by the Lyapunov method. Finally, the validly numerical simulations are illustrated to show the performance of the proposed schemes.

Motivation Bacteriophages and plasmids usually coexist with their host bacteria in microbial communities and play important roles in microbial evolution. Accurately identifying sequence contigs as phages, plasmids and bacterial chromosomes in mixed metagenomic assemblies is critical for further unraveling their functions. Many classification tools have been developed for identifying either phages or plasmids in metagenomic assemblies. However, only two classifiers, PPR-Meta and viralVerify, were proposed to simultaneously identify phages and plasmids in mixed metagenomic assemblies. Due to the very high fraction of chromosome contigs in the assemblies, both tools achieve high precision in the classification of chromosomes but perform poorly in classifying phages and plasmids. Short contigs in these assemblies are often wrongly classified or classified as uncertain. Results Here we present 3CAC, a new three-class classifier that improves the precision of phage and plasmid classification. 3CAC starts with an initial three-class classification generated by existing classifiers and improves the classification of short contigs and contigs with low confidence classification by using proximity in the assembly graph. Evaluation on simulated metagenomes and on real human gut microbiome samples showed that 3CAC outperformed PPR-Meta and viralVerify in both precision and recall, and increased F1-score by 10–60 percentage points. Availability and implementation The 3CAC software is available on https://github.com/Shamir-Lab/3CAC. Supplementary information Supplementary data are available at Bioinformatics online.

Heterogeneous information networks (HINs), which are typed graphs with labeled nodes and edges, have attracted tremendous interest from academia and industry. Given two HIN nodes ${s}$ and ${t}$ , and a natural number ${k}$ , we study the discovery of the ${k}$ most important meta paths in real time, which can be used to support friend search, product recommendation, anomaly detection, and graph clustering. In this work, we argue that the shortest path between ${s}$ and ${t}$ may not necessarily be the most important path. As such, we combine several ranking functions, which are based on frequency and rarity, to redefine the unified importance function of the meta paths between ${s}$ and ${t}$ . Although this importance function can capture more information, it is very time-consuming to find top- ${k}$ meta paths using this importance function. Therefore, we integrate this importance function into a multi-step framework, which can efficiently filter some impossible meta paths between ${s}$ and ${t}$ . In addition, we combine bidirectional searching algorithm with this framework to further boost the efficiency performance. The experiment on different datasets shows that our proposed method outperforms state-of-the-art algorithms in terms of effectiveness with reasonable response time.

For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set $M$ of at most $3n-7$ processors is deleted from an $n$ -star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-3$ . We then prove that when a set $M$ of at most $4n-9$ processors is deleted from an $n$ -star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-5$ . Finally, we also calculate the $r$ -component connectivity of the $n$ -star graph for $2\leq r\leq 5$ .

Deep-neural network-based fault diagnosis methods have been widely used according to the state of the art. However, a few of them consider the prior knowledge of the system of interest, which is beneficial for fault diagnosis. To this end, a new fault diagnosis method based on the graph convolutional network (GCN) using a hybrid of the available measurement and the prior knowledge is proposed. Specifically, this method first uses the structural analysis (SA) method to prediagnose the fault and then converts the prediagnosis results into the association graph. Then, the graph and measurements are sent into the GCN model, in which a weight coefficient is introduced to adjust the influence of measurements and the prior knowledge. In this method, the graph structure of GCN is used as a joint point to connect SA based on the model and GCN based on data. In order to verify the effectiveness of the proposed method, an experiment is carried out. The results show that the proposed method, which combines the advantages of both SA and GCN, has better diagnosis results than the existing methods based on common evaluation indicators.

Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group (community) search over a weighted graph is to find a connected k-core containing all query nodes with the smallest group weight. However, existing state-of-the-art methods start from the maximal k-core to refine an answer, which is practically inefficient for large networks. In this paper, we develop an efficient framework, called local exploration k-core search (LEKS), to find intimate-core groups in graphs. We propose a small-weighted spanning tree to connect query nodes, and then expand the tree to a connected k-core, which is finally refined as an intimate-core group. In addition, to support the intimate group search over large weighted graphs, we develop a weighted-core index (WC-index) and two new WC-index-based algorithms for expansion and refinement phases in LEKS. Specifically, we propose a WC-index-based expansion to efficiently find a candidate graph of intimate-core group, leveraging on a two-level expansion of k-breadth and 1-depth. We propose coarse-grained/fine-grained deletion strategies to achieve high-quality answers in a few iterations. Extensive experiments on real-life networks with ground-truth communities validate the effectiveness and efficiency of our proposed methods.

We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast with the static case, it is NP-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an FPT-algorithm with respect to a new parameter called interval-membership-width which restricts the times assigned to different edges; we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open question of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars. Furthermore, we introduce a vertex-variant of interval-membership-width (which can be arbitrarily larger than its edge-counterpart) and use it to obtain an FPT-time algorithm for a natural vertex-exploration problem that remains hard even when interval-membership-width is bounded., Extended abstract of this paper appeared in IWOCA 2021: Combinatorial Algorithms pp 107-121 (doi: https://doi.org/10.1007/978-3-030-79987-8_8 )

code available at the following address:https://gitlab.inria.fr/marmando/deep-mesh-denoizing; International audience; We examine the problem of mesh denoising, which consists of removing noise from corrupted 3D meshes while preserving existing geometric features. Most mesh denoising methods require a lot of mesh-specific parameter fine-tuning, to account for specific features and noise types. In recent years, data-driven methods have demonstrated their robustness and effectiveness with respect to noise and feature properties on a wide variety of geometry and image problems. Most existing mesh denoising methods still use hand-crafted features, and locally denoise facets rather than examine the mesh globally. In this work, we propose the use of a fully end-to-end learning strategy based on graph convolutions, where meaningful features are learned directly by our network. It operates on a graph of facets, directly on the existing topology of the mesh, without resampling, and follows a multi-scale design to extract geometric features at different resolution levels. Similar to most recent pipelines, given a noisy mesh, we first denoise face normals with our novel approach, then update vertex positions accordingly. Our method performs significantly better than the current state-of-the-art learning-based methods. Additionally, we show that it can be trained on noisy data, without explicit correspondence between noisy and ground-truth facets. We also propose a multi-scale denoising strategy, better suited to correct noise with a low spatial frequency.

Few-shot learning (FSL) for human-object interaction (HOI) aims at recognizing various relationships between human actions and surrounding objects only from a few samples. It is a challenging vision task, in which the diversity and interactivity of human actions result in great difficulty to learn an adaptive classifier to catch ambiguous interclass information. Therefore, traditional FSL methods usually perform unsatisfactorily in complex HOI scenes. To this end, we propose dynamic graph-in-graph networks (DGIG-Net), a novel graph prototypes framework to learn a dynamic metric space by embedding a visual subgraph to a task-oriented cross-modal graph for few-shot HOI. Specifically, we first build a knowledge reconstruction graph to learn latent representations for HOI categories by reconstructing the relationship among visual features, which generates visual representations under the category distribution of every task. Then, a dynamic relation graph integrates both reconstructible visual nodes and dynamic task-oriented semantic information to explore a graph metric space for HOI class prototypes, which applies the discriminative information from the similarities among actions or objects. We validate DGIG-Net on multiple benchmark datasets, on which it largely outperforms existing FSL approaches and achieves state-of-the-art results.

Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including σ-periodic k-core and σ-periodic k-clique, that represent periodic communities in temporal networks. Specifically, a σ-periodic k-core (or σ-periodic k-clique) is a k-core (or clique with size larger than k) that appears at least σ times periodically in the temporal graph. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph. Subsequently, we propose a decomposition algorithm to search maximal σ-periodic k-core, a Bron-Kerbosch style algorithm to enumerate all maximal σ-periodic k-cliques, and a branch-and-bound style algorithm to find the maximum σ-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorith

The problem of session-aware recommendation aims to predict users' next click based on their current session and historical sessions. Existing session-aware recommendation methods have defects in capturing complex item transition relationships. Other than that, most of them fail to explicitly distinguish the effects of different historical sessions on the current session. To this end, we propose a novel method, named Personalized Graph Neural Networks with Attention Mechanism (A-PGNN) for brevity. A-PGNN mainly consists of two components: one is Personalized Graph Neural Network (PGNN), which is used to extract the personalized structural information in each user behavior graph, compared with the traditional Graph Neural Network (GNN) model, which considers the role of the user when the node embeddding is updated. The other is Dot-Product Attention mechanism, which draws on the Transformer net to explicitly model the effect of historical sessions on the current session. Extensive experiments conducted on two real-world data sets show that A-PGNN evidently outperforms the state-of-the-art personalized session-aware recommendation methods., Comment: 12 pages

V práci studujeme efekt hranové eliminace na cyklickou souvislost kubického grafu. Dokážeme, že kromě tří výjimečných grafů, v kubickom grafe existuje hrana, jejíž eliminace zmenší cyklickou souvislost nejvýše o jednotku. Zvláštní chování kubických grafů souvislosti 6 vzhledem k eliminaci hran nás přivedlo k charakterizaci Issacsových grafů, které hrají důležitou roli při studiu kubických grafů. Hlavní výsledek je použitý na důkaz tvrzení, že pro každý 5-souvislý kubický graf existuje rozklad vrcholové množiny na indukovaný strom a indukovaný podgraf s nejvýše jednou hranou. Tento výsledek zobecňuje větu Payana a Sakharoviche z roku 1975. Edge-elimination is an operation of removing an edge of a cubic graph together with its endvertices and suppressing the resulting 2-valent vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. The proof reveals an unexpected behaviour of connectivity 6, which requires a detailed structural analysis featuring the Isaacs flower snarks and their natural generalisation, the twisted Isaacs graphs, as forced structures. A complete characterisation of this family, which includes the Heawood graph as a sporadic case, serves as the main tool for excluding the existence of exceptional graphs in connectivity 6. As an application we show that every cyclically 5-edge-connected cubic graph has a decycling set of vertices whose removal leaves a tree and the set itself has at most one edge between its vertices. This strengthens a classical result of Payan and Sakarovitch (1975) .

Recently, the compacted de Bruijn graph (cDBG) of complete genome sequences was successfully used in read mapping due to its ability to deal with the repetitions in genomes. However, current approaches are not flexible enough to fit frequently building the graphs with different k-mer lengths. Instead of building the graph directly, how can we build the compacted de Bruijin graph of longer k-mer based on the one of short k-mer? In this article, we present StLiter, a novel algorithm to build the compacted de Bruijn graph either directly from genome sequences or indirectly based on the graph of a short k-mer. For 100 simulated human genomes, StLiter can construct the graph of k-mer length 15-18 in 2.5-3.2 hours with maximal ∼70GB memory in the case of without considering the reverese complements of the reference genomes. And it costs 4.5-5.9 hours when considering the reverse complements. In experiments, we compared StLiter with TwoPaCo, the state-of-art method for building the graph, on 4 datasets. For k-mer length 15-18, StLiter can build the graph 5-9 times faster than TwoPaCo using less maximal memory cost. For k-mer length larger than 18, given the graph of a short (k- x)-mer, such as x= 1-2, compared with TwoPaCo building the graph directly, StLiter can also build the graph more efficiently. The source codes of StLiter can be downloaded from web site https://github.com/BioLab-cz/StLiter.

We present a multi-level area balancing technique for laying out clustered graphs to facilitate a comprehensive understanding of the complex relationships that exist in various fields, such as life sciences and sociology. Clustered graphs are often used to model relationships that are accompanied by attribute-based grouping information. Such information is essential for robust data analysis, such as for the study of biological taxonomies or educational backgrounds. Hence, the ability to smartly arrange textual labels and packing graphs within a certain screen space is therefore desired to successfully convey the attribute data . Here we propose to hierarchically partition the input screen space using Voronoi tessellations in multiple levels of detail. In our method, the position of textual labels is guided by the blending of constrained forces and the forces derived from centroidal Voronoi cells. The proposed algorithm considers three main factors: (1) area balancing, (2) schematized space partitioning, and (3) hairball management. We primarily focus on area balancing, which aims to allocate a uniform area for each textual label in the diagram. We achieve this by first untangling a general graph to a clustered graph through textual label duplication, and then coupling with spanning-tree-like visual integration. We illustrate the feasibility of our approach with examples and then evaluate our method by comparing it with well-known conventional approaches and collecting feedback from domain experts.

Scaling adaptive traffic-signal control involves dealing with combinatorial state and action spaces. Multi-agent reinforcement learning attempts to address this challenge by distributing control to specialized agents. However, specialization hinders generalization and transferability, and the computational graphs underlying neural-networks architectures -- dominating in the multi-agent setting -- do not offer the flexibility to handle an arbitrary number of entities which changes both between road networks, and over time as vehicles traverse the network. We introduce Inductive Graph Reinforcement Learning (IG-RL) based on graph-convolutional networks which adapts to the structure of any road network, to learn detailed representations of traffic-controllers and their surroundings. Our decentralized approach enables learning of a transferable-adaptive-traffic-signal-control policy. After being trained on an arbitrary set of road networks, our model can generalize to new road networks, traffic distributions, and traffic regimes, with no additional training and a constant number of parameters, enabling greater scalability compared to prior methods. Furthermore, our approach can exploit the granularity of available data by capturing the (dynamic) demand at both the lane and the vehicle levels. The proposed method is tested on both road networks and traffic settings never experienced during training. We compare IG-RL to multi-agent reinforcement learning and domain-specific baselines. In both synthetic road networks and in a larger experiment involving the control of the 3,971 traffic signals of Manhattan, we show that different instantiations of IG-RL outperform baselines., Comment: 11 pages, 10 figures, 1 table. IEEE Transactions on Intelligent Transportation Systems (2021)

Problem. The paper presents an example of using a methodology for automated calculation of working equipment for construction machines, which are represented by hinge-lever mechanisms. The approach employed in the methodology is based on graph theory and provides semi-automatic generation of the mechanism's structure description and automatic formation of systems of equations for its static calculation. Based on the methodology, software has been developed that automates the performance of force calculations in arbitrary positions of the mechanism for different loading schemes. Methodology. To automate the force calculation, an incidence matrix describing the structure of the mechanism is formed and used. Results. The developed software not only provides results in numerical form but also generates images of the mechanism's diagram. Additionally, the software includes exporting capabilities for results to a separate file that can be further used for selecting hydraulic cylinders and pumps, calculating hydraulic systems, and assessing the strength of working equipment components. Originality. Certain rules for numbering mechanism links and joints, as well as methods for indicating the coordinates of the joints and points of application of external forces, have been developed. These rules and methods not only ensure the automatic formation and solution of systems of equations for the mechanism's static equilibrium but also automate the construction of the incidence matrix. Practical value. The developed software and the data representation method proposed by the authors automate the majority of stages in the force calculation of hinge-lever mechanisms for construction machinery. It can be applied not only in the design stage but also before the use of new types of variable working equipment., В роботі представлено приклад використання методики автоматизованого розрахунку робочого обладнання будівельних машин, яке представлено шарнірно-важільними механізмами. Підхід, що застосовується в методиці, базується на теорії графів і забезпечує напівавтоматичне отримання опису структури механізму і автоматичне формування систем рівнянь його статичної рівноваги. На основі методики розроблено програмне забезпечення, яке автоматизує виконання силового розрахунку у довільних положеннях механізму при різних схемах його навантаження.