Forming Scalable, Convergent GNN Layers that Minimize a Sampling-Based Energy

## Abstract

Abstract This document is a model and instructions for L a T e X .
This and the IEEEtran.cls file define the components of your paper [title, text, heads, etc.]. *CRITICAL: Do Not Use Symbols, Special Characters, Footnotes,
or Math in Paper Title or Abstract.

###### Index Terms:

## I Introduction

This document is a model and instructions for LaTeX.
Please observe the conference page limits.

## II Ease of Use

### II-A Maintaining the Integrity of the Specifications

The IEEEtran class file is used to format your paper and style the text. All margins,
column widths, line spaces, and text fonts are prescribed; please do not
alter them. You may note peculiarities. For example, the head margin
measures proportionately more than is customary. This measurement
and others are deliberate, using specifications that anticipate your paper
as one part of the entire proceedings, and not as an independent document.
Please do not revise any of the current designations.

## III Prepare Your Paper Before Styling

Before you begin to format your paper, first write and save the content as a
separate text file. Complete all content and organizational editing before
formatting. Please note sections [III-A](#S3.SS1)–[III-E](#S3.SS5) below for more information on
proofreading, spelling and grammar.

Keep your text and graphic files separate until after the text has been
formatted and styled. Do not number text heads—LaTeX will do that
for you.

### III-A Abbreviations and Acronyms

Define abbreviations and acronyms the first time they are used in the text,
even after they have been defined in the abstract. Abbreviations such as
IEEE, SI, MKS, CGS, ac, dc, and rms do not have to be defined. Do not use
abbreviations in the title or heads unless they are unavoidable.

### III-B Units

- •
Use either SI (MKS) or CGS as primary units. (SI units are encouraged.) English units may be used as secondary units (in parentheses). An exception would be the use of English units as identifiers in trade, such as “3.5-inch disk drive”.
- •
Avoid combining SI and CGS units, such as current in amperes and magnetic field in oersteds. This often leads to confusion because equations do not balance dimensionally. If you must use mixed units, clearly state the units for each quantity that you use in an equation.
- •
Do not mix complete spellings and abbreviations of units: “Wb/m^2” or “webers per square meter”, not “webers/m^2”. Spell out units when they appear in text: “. . . a few henries”, not “. . . a few H”.
- •
Use a zero before decimal points: “0.25”, not “.25”. Use “cm^3”, not “cc”.)

### III-C Equations

Number equations consecutively. To make your
equations more compact, you may use the solidus ( / ), the exp function, or
appropriate exponents. Italicize Roman symbols for quantities and variables,
but not Greek symbols. Use a long dash rather than a hyphen for a minus
sign. Punctuate equations with commas or periods when they are part of a
sentence, as in:

$$ $a+b=\gamma$ (1) $$

Be sure that the
symbols in your equation have been defined before or immediately following
the equation. Use “([1](#S3.E1))”, not “Eq. ([1](#S3.E1))” or “equation ([1](#S3.E1))”, except at
the beginning of a sentence: “Equation ([1](#S3.E1)) is . . .”

### III-D L a T e X -Specific Advice

Please use “soft” (e.g., \eqref{Eq}) cross references instead
of “hard” references (e.g., (1)). That will make it possible
to combine sections, add equations, or change the order of figures or
citations without having to go through the file line by line.

Please don’t use the {eqnarray} equation environment. Use
{align} or {IEEEeqnarray} instead. The {eqnarray}
environment leaves unsightly spaces around relation symbols.

Please note that the {subequations} environment in LaTeX
will increment the main equation counter even when there are no
equation numbers displayed. If you forget that, you might write an
article in which the equation numbers skip from (17) to (20), causing
the copy editors to wonder if you’ve discovered a new method of
counting.

BibTEX does not work by magic. It doesn’t get the bibliographic
data from thin air but from .bib files. If you use BibTEX to produce a
bibliography you must send the .bib files.

LaTeX can’t read your mind. If you assign the same label to a
subsubsection and a table, you might find that Table I has been cross
referenced as Table IV-B3.

LaTeX does not have precognitive abilities. If you put a
\label command before the command that updates the counter it’s
supposed to be using, the label will pick up the last counter to be
cross referenced instead. In particular, a \label command
should not go before the caption of a figure or a table.

Do not use \nonumber inside the {array} environment. It
will not stop equation numbers inside {array} (there won’t be
any anyway) and it might stop a wanted equation number in the
surrounding equation.

### III-E Some Common Mistakes

- •
The word “data” is plural, not singular.
- •
The subscript for the permeability of vacuum $\mu_{0}$, and other common scientific constants, is zero with subscript formatting, not a lowercase letter “o”.
- •
In American English, commas, semicolons, periods, question and exclamation marks are located within quotation marks only when a complete thought or name is cited, such as a title or full quotation. When quotation marks are used, instead of a bold or italic typeface, to highlight a word or phrase, punctuation should appear outside of the quotation marks. A parenthetical phrase or statement at the end of a sentence is punctuated outside of the closing parenthesis (like this). (A parenthetical sentence is punctuated within the parentheses.)
- •
A graph within a graph is an “inset”, not an “insert”. The word alternatively is preferred to the word “alternately” (unless you really mean something that alternates).
- •
Do not use the word “essentially” to mean “approximately” or “effectively”.
- •
In your paper title, if the words “that uses” can accurately replace the word “using”, capitalize the “u”; if not, keep using lower-cased.
- •
Be aware of the different meanings of the homophones “affect” and “effect”, “complement” and “compliment”, “discreet” and “discrete”, “principal” and “principle”.
- •
Do not confuse “imply” and “infer”.
- •
The prefix “non” is not a word; it should be joined to the word it modifies, usually without a hyphen.
- •
There is no period after the “et” in the Latin abbreviation “et al.”.
- •
The abbreviation “i.e.” means “that is”, and the abbreviation “e.g.” means “for example”.

An excellent style manual for science writers is [].

### III-F Authors and Affiliations

The class file is designed for, but not limited to, six authors. A
minimum of one author is required for all conference articles. Author names
should be listed starting from left to right and then moving down to the
next line. This is the author sequence that will be used in future citations
and by indexing services. Names should not be listed in columns nor group by
affiliation. Please keep your affiliations as succinct as possible (for
example, do not differentiate among departments of the same organization).

### III-G Identify the Headings

Headings, or heads, are organizational devices that guide the reader through
your paper. There are two types: component heads and text heads.

Component heads identify the different components of your paper and are not
topically subordinate to each other. Examples include Acknowledgments and
References and, for these, the correct style to use is “Heading 5”. Use
“figure caption” for your Figure captions, and “table head” for your
table title. Run-in heads, such as “Abstract”, will require you to apply a
style (in this case, italic) in addition to the style provided by the drop
down menu to differentiate the head from the text.

Text heads organize the topics on a relational, hierarchical basis. For
example, the paper title is the primary text head because all subsequent
material relates and elaborates on this one topic. If there are two or more
sub-topics, the next level head (uppercase Roman numerals) should be used
and, conversely, if there are not at least two sub-topics, then no subheads
should be introduced.

### III-H Figures and Tables

#### Positioning Figures and Tables

Place figures and tables at the top and
bottom of columns. Avoid placing them in the middle of columns. Large
figures and tables may span across both columns. Figure captions should be
below the figures; table heads should appear above the tables. Insert
figures and tables after they are cited in the text. Use the abbreviation
“Fig. [1](#S3.F1)”, even at the beginning of a sentence.

**TABLE I: Table Type Styles**
| Table | Table Column Head |  |  |
| --- | --- | --- | --- |
| Head | Table column subhead | Subhead | Subhead |
| copy | More table copy^a |  |  |
| ^aSample of a Table footnote. |  |  |  |

Figure: Figure 1: Example of a figure caption.
Refer to caption: /html/2310.12457/assets/fig1.png

Figure Labels: Use 8 point Times New Roman for Figure labels. Use words
rather than symbols or abbreviations when writing Figure axis labels to
avoid confusing the reader. As an example, write the quantity
“Magnetization”, or “Magnetization, M”, not just “M”. If including
units in the label, present them within parentheses. Do not label axes only
with units. In the example, write “Magnetization (A/m)” or “Magnetization
{A[m(1)]}”, not just “A/m”. Do not label axes with a ratio of
quantities and units. For example, write “Temperature (K)”, not
“Temperature/K”.

## Acknowledgment

The preferred spelling of the word “acknowledgment” in America is without
an “e” after the “g”. Avoid the stilted expression “one of us (R. B.
G.) thanks $\ldots$”. Instead, try “R. B. G. thanks$\ldots$”. Put sponsor
acknowledgments in the unnumbered footnote on the first page.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Refer to the content in the Weaknesses.
soundness: 3
strengths: 1). The organization and writing of this paper are excellent.

2). The model enhances UGNN framework by incorporating sampling into its energy function design and demonstrates solid convergence properties.

3).  Empirical results suggest that MuseGNN maintains competitive accuracy and scalability across various task sizes, performing well on large node classification datasets exceeding 1TB.
summary: The paper proposes a GNN model  that scales effectively to large datasets by incorporating sampled subgraphs into its energy function design. This approach allows the model to handle graphs with around 100 million nodes and high-dimensional features, achieving competitive accuracy on benchmarks exceeding 1TB in size. Additionally, it maintains desirable inductive biases and convergence guarantees.
weaknesses: 1). How to determine \alpha and \lambda for different datasets?

2). Does the model's improvement differ for homogeneous and heterogeneous graphs? Can you provide some additional explanation?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - How is the method compared to SGC and its variants in terms of efficiency and accuracy?
- How does the method perform on heterophilic graphs? The energy-related loss seems to highly rely on the homophilic assumption.
soundness: 3
strengths: - The paper provides an analysis of the convergence properties of the proposed energy function and the iterative reduction process. 
- MuseGNN is designed to handle very large graphs, as evidenced by its performance on the node classification benchmark exceeding 1TB in size. 
- The experimental results show that MuseGNN achieves competitive accuracy compared to state-of-the-art GNN.
summary: This paper introduces MuseGNN, a novel Graph Neural Network (GNN) architecture designed to address the challenges of scaling and convergence in GNNs. The core idea behind MuseGNN is to iteratively minimize a sampling-based energy function during the forward pass, which allows the node embeddings to serve dual purposes: as predictive features for downstream tasks and as minimizers of the energy function. The authors present a scalable GNN that is able to deal with large-scale node classification benchmarks, including datasets exceeding 1TB in size.
weaknesses: - The paper focuses on comparing MuseGNN with a few specific GNN architectures and frameworks. A more comprehensive comparison with a wider range of state-of-the-art GNNs. In particular, I want to see the comparison to SGC [1] and its variants in terms of efficiency and accuracy.
- The training speed of the proposed method seems to be slower than GAT as shown in Table 1, while GAT is a well-known slow GNN.

[1] Simplifying Graph Convolutional Networks

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: At the current stage, my questions are as follows: 

1. The organization of the paper needs to be improved. For example, figure 1 on page 2 is referred to in both the introduction section and the experiment section (ablation study), which is rarely to be observed in other studies. Also, the ablation result for $\gamma$, located in Table 6, in Appendix B2, can be put into the current main page, which only contains 9.5 pages. 

2. In addition to this, I think the ablation on $\gamma$ is very important as this shows how the degree of dependence between subgraphs affects the final training. Therefore, it is recommended that a more detailed analysis of this aspect be input. 

3. Another important empirical verification is the performance of the model via different sampling strategies since this directly affects the power of the term $\|Y_s - \mu_s\|$. I found the related content in the Appendix, but it is recommended that the author put some convincing evidence to the main content.

4. Furthermore, the energy regularizer $\lambda \mathrm{Tr}(\mathbf Y_s \mathbf L_s \mathbf Y_x )$ controls the degree of smoothing via each subgraph, and the quantity of $\lambda$ is shared over all the subgraph. However, in real practice, this may not be ideal as subgraphs shall have different degrees of smoothing.

5. The expressive power of the GNN is usually discussed under the graph pooling tasks (e.g., graph level classification), it would be better and interesting to show some pooling results from the proposed model.

Minor modification. 

1. In row 183, table 4 is missing, and it is allocated in the appendix.
soundness: 3
strengths: 1. The paper resolved the scalability problem on the GNNs induced by their energy optimization form. Empirical studies show the proposed model outperforms many baselines via different graph sizes up to 1TB. 

2. The paper provided theoretical analysis on the convergence of the proposed model under different values of $\gamma$, which controls the degree of dependency between subgraphs.
summary: This paper developed one subgraph sampling strategy induced from the energy regularization process over the GNN learning process. The author also discussed the convergence and expressive power of their proposed model under some conditions (i.e., $\gamma$). The newly proposed model is advanced with a shared weight matrix over all subgraphs and by the consideration of replicated nodes in multiple subgraphs. Empirical studies show promising results via large-scale graph datasets.
weaknesses: 1. Some important analysis and empirical study results are missing and shall be presented via the main text, please see the question part. 

2. The organization of the paper needs to be carefully adjusted.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. The ablation study of hyperparameter gamma shows that MuseGNN preserves high accuracy when gamma=0. In this case, the embedding of the same node in different subgraphs are not aligned. Can the node embeddings in subgraphs capture the global information of the original graph? Are there any theoretical insights about why MuseGNN still shows comparative performance even when gamma = 0?


2. What is the sampling strategy when sampling subgraphs from the large original graph?
soundness: 3
strengths: 1. The paper discusses a critical issue of scalability when adding energy regularization to GCN, where the cost of energy calculation becomes enormous for large-scale graphs and previous methods fail to work on large graphs.

2. The paper proposes a new method, MuseGNN, to enable energy-regularized GNN to efficiently handle large-scale graphs. The paper also comprehensively discusses the optimization procedure and convergence analysis of their method.


3. The paper validates the performance and efficiency of MuseGNN by experiments on multiple-datasets, including large graph datasets where previous methods need huge computational cost.
summary: This paper introduces a scalable graph neural network (GNN) architecture that minimizes an energy function through a sampling-based approach, allowing for interpretable node embeddings optimized for tasks like node classification.
weaknesses: 1. The annotations and formulation in 2.1 may be confusing for new readers. The authors could adopt similar annotations in Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks by Ahn et al, which distinguishes the node embedding by basic model and the embedding by energy optimization by different annotations y and y*, and specify the procedure of UGCN to make the problem formulation clearer to a broader audience.
2. The authors could compare the time and memory cost of MuseGNN with more baselines that also uses energy regularization without sampling to strengthen the superiority of MuseGNN.
3. In the introduction, the authors could provide more specified discussions about the advantages of applying energy regularization to GNN to show the importance of this work.

Meta-review: The manuscript proposes a graphical neural network training strategy based on minimizing a sub-sampled graphs into the energy minimization. Empirical results suggest the effectiveness and scalability of the training strategy. The reviewers largely agree that the approach is novel and interesting. Majority of the concerns by the reviewers have been addressed during the discussion. Thus the metareviewer recommends the paper for acceptance.

Decision: Accept (Poster)